Численные методы решения систем

Линейных алгебраических уравнений

«75% всех расчетных математических задач прихо-дится на решение систем линейных алгебраических урав-нений»

Е. Валях

Применение численных методов для решения задач строительства часто сводится к решению систем линейных алгебраических уравнений (СЛАУ).

Системы линейных алгебраических уравнений

Системы линейных алгебраических уравнений могут непосредственно составлять задачу из области строительных технологий, которую необходимо решить. Это канонические уравнения метода сил, метода перемещений, смешанного, комбинированного методов – в расчетах статически неопределимых систем. Это уравнения равновесия (баланс сил) – в расчетах статически определимых систем и др. С другой стороны, многие задачи строительства при их математической постановке сводятся к решению системы линейных алгебраических уравнений той или иной структуры. Это краевые задачи, описываемые дифференциальными уравнениями, вариационные задачи и др.).

Система линейных алгебраических уравнений в общем случае имеет вид

Эту систему удобнее записывать в матричной форме

где А – матрица системы, – вектор решения, – вектор свободных членов.

Решение систем линейных алгебраических уравнений представляет собой типичный образец численных расчетов, которыми занимались еще в древности. Это основной “строительный блок” для алгоритмов решения большинства задач, в которых используются математические модели.

Система (3.1) имеет единственное решение [8], если матрица А невырожденная ( det A 0).

Если использовать понятие обратной матрицы ( А ^-1), то решение СЛАУ можно записать

Такой подход к решению СЛАУ крайне неэффективен, т.к. вычислительные потери при вычислении обратной матрицы очень большие. И если нет необходимости исследовать непосредственно элементы обратной матрицы, то лучше не вычислять ее .

В курсе линейной алгебры решение системы (3.1) обычно находится по формулам Крамара в виде отношения определителей.

Для численного решения систем высокого порядка (а именно такие встречаются при решении задач строительства) этот метод непригоден, так как требует вычисления (n+1)-го определителя. Даже при выборе наилучшего метода вычисление одного определителя потребуется такое же временя, что и для решение самой системы современными численными методами.

Методы решения СЛАУ. Все методы решения СЛАУ можно условно разбить на два класса: прямые ( илиточные ) и итерационные. Имеются и «гибридные» методы [3, 4].

Прямые методы позволяют за конечное число действий получить точное решение системы. Слова “точное решение” нужно понимать условно, как характеристику алгоритма, а не реального вычислительного процесса.

Итерационные методы дают решение СЛАУ в виде предела последовательности некоторых векторов, построение которых осуществляется посредством единообразного процесса, называемого итерационным процессом. Они позволяют найти приближенное решение системы с заданной точностью.

Выбор того или иного метода зависит от многих обстоятельств:

- от вида матрицы коэффициентов;

-

- от порядка системы;

- от имеющегося программного обеспечения;

- от объема оперативной памяти ЭВМ и др.

Прямые методы решения систем линейных алгебраических уравнений

Прямые методы решения систем линейных алгебраических уравнений основаны на сведении матрицы системы А к матрице простой структуры – диагональной (и тогда решение очевидно) или треугольной – и тогда решение отыскивается с помощью последовательных подстановок. Сведение матрицы А к одному из указанных видов осуществляется при помощи конечного числа элементарных преобразований (см. пункт 3.6.1).

Метод Гаусса

Иногда метод Гаусса называют методом последовательного исключения. Алгоритм исключения неизвестных датируется, по крайней мере, 250-м годом до нашей эры, хотя и носит имя Гаусса.

Суть метода заключается в манипуляциях с уравнениями, в результате чего из уравнений последовательно исключаются неизвестные. Полученная эквивалентная система (т.е. система с тем же самым решением) является системой с треугольной матрицей А.

Процесс решения состоит из двух этапов: прямого и обратного хода.

В результате прямого хода система приводится к системе с треугольной матрицей, а при выполнении обратного хода вычисляются последовательно все неизвестные[8, 13].

Продемонстрируем метод Гаусса на примере системы из трех уравнений. Обозначим каждое уравнение буквами A⁽ⁱ⁾ , B⁽ⁱ⁾, C⁽ⁱ⁾ (здесь(i) соответствует номеру шага).

Прямой ход

Шаг 1. Допустим ведущий1 элемент отличен от нуля. Разделим первое уравнение на . Полученное при этом уравнение домножим последовательно на коэффициенты и и сложим с соответствующими элементами 2-й и 3-й строки.

Выполняемые действия показаны справа от системы уравнений. В результате выполнения этого шага из всех уравнений, кроме 1-го, исключается неизвестное х_1.

Действия:

Шаг 2. Выполняя аналогичные действия со вторым и третьим уравнениями (1-е уравнение при этом остается неизменным), исключаем неизвестное х₂ из них:

Действия:

Выполнив два шага для системы 3-го порядка, получили систему, эквивалентную заданной и имеющую верхнюю треугольную матрицу коэффициентов, из которой легко вычисляются все неизвестные. (Для общности можно выполнить 3-й шаг, поделив последнее уравнение на главный коэффициент).

Обратный ход. Из последней строки полученной системы (3.3б) находим значение неизвестного

Подставляя его во 2-ую строку системы (3.3б), получим значение

Имея , аналогичным образом найдем из 1-го уравнения этой же системы:

Рассмотрим простой численный пример.

n Пример 3.1. Методом Гаусса решитьсистему уравнений:

Составим матрицу коэффициентов, включая свободные члены (расширенную матрицу):

Прямой ход

1-й шаг 1-ю строку матрицы делим на а₁₁=2; Умножаем полученную строку сначала на (–3) и складываем со 2-й, а затем на (–4) и складываем с 3-й:

2-й шаг 2-ю строку матрицы А⁽¹⁾делим на а₂₂ = –5; Умножаем полученную строку на (–3) и складываем с 3-й строкой этой же матрицы:

Обратный ход

Из последнего уравнения (3-я строка матрицы) получаем

Из 2-го уравнения находим

Из 1-го уравнения получаем

Таким образом, полученное решение имеет вид

Решение этого примера с использованием электронных таблиц Excel приведено в разделе 3.6.1.

В процессе решения системы возможны три случая:

1) Решение системы существует и является единственным, когда матрица коэффициентов невырожденная (при этом на последнем шаге решения получается одно уравнение с одним неизвестным).

2) Система уравнений вообще не имеет решений (такой случай имеет место, когда на некотором шаге получается строка, в которой все коэффициенты при неизвестных равны нулю, а свободный член не равен нулю).

3) Система уравнений имеет бесконечное множество решений (это получается, когда на некотором шаге в системе получается строка, в которой все коэффициенты и свободный член равны нулю).

G При практическом применении метода Гаусса следует обратить внимание на следующие моменты:

1. Если в ходе приведения матрицы А к треугольному виду на главной диагонали окажется элемент, равный нулю, эта схема расчета формально непригодна, хотя система может иметь единственное решение.

2. В процессе вычислений встречаются ведущие элементы, которые малы по сравнению с другими элементами соответствующих строк. Это обстоятельство может привести к значительным ошибкам округления.

Чтобы избежать всего этого, каждый цикл (шаг) следует начинать с перестановки строк, в результате которой ненулевой элемент перемещается на главную диагональ. При этом среди элементов столбца находится главный элемент, то есть максимальный по модулю в соответствующем столбце, который и выводится на главную диагональ. В таком варианте метода погрешности обычно невелики. Такую модификацию метода называют методом Гаусса с выбором главного элемента.

Метод прогонки

Метод прогонки является модификацией метода Гаусса для частного случая систем уравнений с трехдиагональной матрицей вида:

Векторы:

Метод прогонки состоит из двух этапов: прямой и обратной прогонки . При прямой прогонке каждое неизвестное x_i выражается через x_i₊₁ с помощью прогоночных коэффициентов U_i, V_i:

Из 1-го уравнения системы (3.4) выражаем x₁:

где

Из 2-го уравнения системы (3.4) выражаем x₂:

Продолжая этот процесс при условии, что U₀=0, V₀=0, получим рекуррентную формулу для x_i:

где

После прямого хода система (3.4) примет вид:

Обратная прогонка состоит в последовательном вычислении неизвестных x_i. Сначала вычисляется неизвестное x_n из двух последних уравнений преобразованной системы (3.9):

Затем, используя выражение (3.7), последовательно вычисляются все остальные неизвестные

Алгоритм метода прогонки

1. Вычисляются прогоночные коэффициенты U_i, V_i по формулам (3.8) для i=1, 2, …n-1 при условии, что U₀=0, V₀=0;

2. Определяются x_n из выражения (3.10);

3. По формуле (3.7) последовательно вычисляются все остальные неизвестные

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒