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

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

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

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

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

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

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

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

Покажем, что если начать с точки P₀ = (х₁ ⁽⁰⁾ , х₂ ⁽⁰⁾ , х₃ ⁽⁰⁾ , х₄ ⁽⁰⁾ ) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х₁ = 1, х₂ = 2, х₂ = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P₁ = (х₁ ⁽¹⁾ , х₂ ⁽¹⁾ , х3⁽¹⁾ , х₄ ⁽¹⁾ ) = (1.75, 3.375, 3), ближе, чем P₀ .

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

k	х1(k)	х2(k)	х3(k)
0	1.0	2.0	2.0
1	1.75	3.375	3.0
2	1.84375	3.875	3.025
3	1.9625	3.925	2.9625
4	1.990625	3.9765625	3.0
5	1.99414063	3.9953125	3.0009375
…	…	…	…
15	1.99999993	3.99999985	3.0009375
…	…	…	…
19	2.0	4.0	3.0

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

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

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

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

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

k	х1 (k)	х2 (k)	х3 (k)
0	1.0	2.0	2.0
1	1.75	3.75	2.95
2	1.95	3.96875	2.98625
3	1.995625	3.99609375	2.99903125
…	…	…	…
8	1.99999983	3.99999988	2.99999996
9	1.99999998	3.99999999	3.0
10	2.0	4.0	3.0

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

Вывод:

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

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

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

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