Численные методы решения систем линейных уравнений

-2x2-3(-3/5) = 1,

-2x2+9/5 = 1,

-2x2 = 1-9/5,

-2x2 = -4/5,

x2 = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2+x3 = 0):

x1-2/5+(-3/5) = 0,

x1-5/5 = 0,

x1 = 5/5 = 1.

Проверка:

т. е.

т. е.

и т. д.

Вывод.

Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1.                 Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей. Эти действия называют прямым ходом.

2.                 Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).

3.                 При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее - треугольному виду в прямом ходе метода.

Итерация для линейных систем.

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

Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:

Разрешим первое уравнение системы относительно х1:

х1 = (-a12/a11)х2-a13/a11х3-a14/a11х4-a15/a11.

Затем разрешим второе уравнение относительно х2 и т. д. Тогда систему можно переписать в виде:

где α = -aik/aii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом  линейная функция L1 фактически не зависит от х1.

Зададим какие-либо начальные значения неизвестных (нулевые приближения):

х1(0), х2(0), х3(0), х4(0).

Подставляя эти значения в правые части системы (*), получим первые приближения:

Полученные первые приближения могут быть так же использованы для получения вторых, третьих и т. д. приближений. Т. е. можно записать:

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х1, х2, х3, х4.

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

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

Итерация Якоби.

Рассмотрим систему линейных уравнений:

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P0 = (х1(0), х2(0), х3(0), х4(0)) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х1 = 1, х2 = 2, х2 = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P1 = (х1(1), х2(1), х3(1), х4(1)) = (1.75, 3.375, 3), ближе, чем P0.

Итерация, использующая (3), генерирует последовательность точек {Pk}, которая сходится к решению (2, 4, 3):

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем.

Итерация Гаусса-Зейделя.

Процесс итерации Якоби иногда можно модифицировать для ускорения сходимости.

Отметим, что итеративный процесс Якоби производит три последовательности – {х1(k)}, {х2(k)}, {х3(k)}, {х4(k)}. Кажется разумным, что х1(k+1) может быть использовано вместо х2(k). Аналогично х1(k+1) и х2(k+1) можно использовать в вычислении х3(k+1). Например, для уравнений из системы (1) это даст следующий вид итерационного процесса Гаусса-Зейделя, использующий (3*):

Такой итерационный процесс даст результаты:

Т. е. к точному решению мы пришли уже на 10-ом шаге итерации, а не на 19, как в итерации Якоби.

Вывод.

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

Эти формулы как раз и задают собственно итерационный процесс.

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

Это условие можно сформулировать и более точно:

Для сходимости процесса итераций достаточно, чтобы в каждом столбце сумма отношений коэффициентов системы к диагональным элементам, взятым из той же строки, была строго меньше единицы:

3.                 Следует так же сказать, что итерационный процесс может проводиться как в виде итерации Якоби, так и в виде итерации Гаусса-Зейделя. В последнем случае сходимость итерационного процесса может существенно улучшиться.

                                                                     II.                Практическая часть.

1) Метод обратной матрицы.

Метод обратной матрицы

x1

x2

x3

x4

12

-4

0

6

2

A=

-4

21

5

3

B=

4

-3

2

-22

1

-2

-2

-3

5

23

4

0,083

0,013

-0,002

-0,023

A-1=

0,016

0,048

0,009

-0,011

-0,009

0,003

-0,044

0,004

0,011

0,007

0,010

0,039

x=

0,129

0,165

0,097

0,186