Метод простой итерации Якоби

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

Для того, чтобы применить метод простой итерации, необходимо систему уравнений

Ax = b (3.22 )

с квадратной невырожденной матрицей A привести к виду

x = Bx + c, (3.23)

где B – квадратная невырожденная матрица с элементами b_ij, i, j = 1, 2, …, n, x – вектор-столбец неизвестных x_i, c – вектор-столбец с элементами c_i, i = 1, 2, …, n.

Существуют различные способы приведения системы (3.22) к виду (3.23). Рассмотрим самый простой. Представим систему (3.22) в развернутом виде:

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _{1 n} x_n = b ₁

a ₂₁ x ₁ + a ₂₂ x ₂ + a ₂₃ x ₃ + … + a _{2 n} x_n = b ₂

a ₃₁ x ₁ + a ₃₂ x ₂ + a ₃₃ x ₃ + … + a _{3 n} x_n = b ₃ (3.24)

a_{n 1} x ₁ + a_{n 2} x ₂ + a_{n 3} x ₃ + … + a_nnx_n = b_n

Из первого уравнения системы (3.24) выразим неизвестную x ₁:

x ₁ = a (b ₁ – a ₁₂ x ₂ – a ₁₃ x ₃ – … – a _{1 n} x_n),

из второго уравнения – неизвестную x ₂:

x ₂ = a (b ₂ – a ₂₁ x ₁ – a ₂₃ x ₃ – … – a _{2 n} x_n),

и т. д. В результате получим систему:

x ₁ = b ₁₂ x ₂ + b ₁₃ x ₃ + … + b _{1 ,n- 1} x_{n- 1} + b _{1 n} x_n + c ₁

x ₂ = b ₂₁ x ₁ + b ₂₃ x ₃ + … + b _{2 ,n- 1} x_{n- 1} + b _{2 n} x_n + c ₂

x ₃ = b ₃₁ x ₁ + b ₃₂ x ₂ + … + b _{3 ,n- 1} x_{n- 1} + b _{3 n} x_n + c ₃ (3.25)

.

x_n= b_{n 1} x ₁ + b_{n 2} x ₂ + b_{n 3} x ₃ + b_{n,n- 1} x_{n- 1} + c_n

Матричная запись системы (3.25) имеет вид (3.23). На главной диагонали матрицы B находятся нулевые элементы, а остальные элементы вычисляются по формулам:

b_ij = , c_i = , i, j = 1,2, … n, i j. (3.26)

Очевидно, что диагональные элементы матрицы A должны быть отличны от нуля.

Выберем произвольно начальное приближение Обычно в качестве первого приближения берут x= c_i или x= 0. Подставим начальное приближение в правую часть (3.25). Вычисляя левые части, получим значения x, x, …, x. Продолжая этот процесс дальше, получим последовательность приближений, причем (k + 1)-е приближение строится следующим образом:

x = b ₁₂ x + b ₁₃ x+ … + b _{1 ,n- 1} x + b _{1 n} x + c ₁

x = b ₂₁ x ₁ + b ₂₃ x + … + b _{2 ,n- 1} x + b _{2 n} x + c ₂

x = b ₃₁ x+ b ₃₂ x + … + b _{3 ,n- 1} x + b _{3 n} x + c ₃ … (3.27)

x= b_{n 1} x+ b_{n 2} x + b_{n 3} x + b_{n,n- 1} x + c._n

Система (3.27) представляет собой расчетные формулы метода простой итерации Якоби.

Сходимость метода простой итерации. Известно следующее достаточное условие сходимости метода простой итерации Якоби.

Если элементы матрицы A удовлетворяют условию:

| a_ii | > , i = 1, 2, …, n. (3.28)

то итерационная последовательность x^k сходится к точному решению x^*.

Условие (3.28) называют условием преобладания диагональных элементов матрицы A, так как оно означает, что модуль диагонального элемента i- ой строки больше суммы модулей остальных элементов этой строки, i = 1, 2, …, n.

Необходимо помнить, что условие сходимости (3.28) является лишь достаточным. Его выполнение гарантирует сходимость метода простых итераций, но его невыполнение, вообще говоря, не означает, что метод расходится.

Справедлива следующая апостериорная оценка погрешности:

max| x- x | £ max| x– x |, i = 1, 2, …, n, (3.29)

где b = max | b_ij | i, j = 1, 2, …, n.

Правую часть оценки (3.29) легко вычислить после нахождения очередного приближения.

Критерий окончания. Если требуется найти решение с точностью e, то в силу (3.29) итерационный процесс следует закончить как только на (k+ 1)-ом шаге выполнится неравенство:

max| x– x | < e, i = 1, 2, …, n. (3.30)

Поэтому в качестве критерия окончания итерационного процесса можно использовать неравенство

max| x– x | < e ₁, i = 1, 2, …, n. (3.31)

где e _{1 =} e_.

Если выполняется условие b £ , то можно пользоваться более простым критерием окончания:

max| x– x | < e, i = 1, 2, …, n. (3.32)

В других случаях использование критерия (3.32) неправомерно и может привести к преждевременному окончанию итерационного процесса.

Пример 3 .5.

Применим метод простой итерации Якоби для решения системы уравнений

20.9x₁ + 1.2 x ₂ + 2.1 x ₃ + 0.9 x ₄ = 21.70

1.2x₁ + 21.2 x ₂ + 1.5 x ₃ + 2.5 x ₄ = 27.46

2.1x₁ + 1.5 x ₂ + 19.8 x ₃ + 1.3 x ₄ = 28.76 (3.33)

0.9x₁ + 2.5 x ₂ + 1.3 x ₃ + 32.1 x ₄ = 49.72

Заметим, что метод простой итерации сходится, т. к. выполняется условие преобладания диагональных элементов (3.28):

|20.9| > |1.2 + 2.1 + 0.9|,

|21.2| > |1.2| + |1.5| + |2.5|,

|19.8| > |2.1| + |1.5| + |1.3|,

|32.1| > |0.9| + |2.5| + |1.3|.

Пусть требуемая точность e = 10^-3. Вычисления будем проводить с четырьмя знаками после десятичной точки.

Приведем систему к виду (3.25):

x ₁ = – 0.0574 x ₂ – 0.1005 x ₃ – 0.0431 x ₄ + 1.0383

x ₂ = – 0.0566 x ₁ – 0.0708 x ₃ – 0.1179 x ₄ + 1.2953

x ₃ = – 0.1061 x ₁ – 0.0758 x ₂ – 0.0657 x ₄ + 1.4525 (3.34)

x ₄ = – 0.0280 x ₁ – 0.0779 x ₂ – 0.0405 x ₃ + 1.5489

Величина b = max | b_ij |, i, j = 1, 2, 3,4 равна 0.1179, т. е. выполняется условие b £ , и можно пользоваться критерием окончания итерационного процесса (3.32).

В качестве начального приближения возьмем элементы столбца свободных членов:

x = 1.0383, x = 1.2953, x = 1.4525, x = 1.5489. (3.35)

Вычисления будем вести до тех пор, пока все величины | x– x |, i = 1, 2, 3, 4, а следовательно, и max| x– x | не станут меньше e = 10^-3.

Последовательно вычисляем:

при k = 1

x = – 0.0574 x– 0.1005 x – 0.0431 x+ 1.0383 = 0.7512

x = – 0.0566 x – 0.0708 x– 0.1179 x+ 1.2953 = 0.9511

x = – 0.1061 x– 0.0758 x – 0.0657 x+ 1.4525 = 1.1423

x= –0.0280x– 0.0779x – 0.0405x + 1.5489 = 1.3601

при k = 2

x= 0.8106, x= 1.0118, x= 1.2117, x= 1.4077.

при k = 3

x= 0.7978, x= 0.9977, x= 1.1975, x= 1.3983.

при k = 4

x= 0.8004, x= 1.0005, x= 1.2005, x= 1.4003.

Вычисляем модули разностей значений x при k = 3 и k = 4:

| x– x| = 0.026, | x– x| = 0.028, | x– x| = 0.0030, | x– x| = 0.0020.

Так как все они больше заданной точности e = 10^-3, продолжаем итерации.

При k = 5

x= 0.7999, x= 0.9999, x= 1.1999, x= 1.3999.

Вычисляем модули разностей значений x при k = 4 и k = 5:

| x– x| = 0.0005, | x– x| = 0.0006, | x– x| = 0.0006, | x– x| = 0.0004.

Все они меньше заданной точности e = 10^-3, поэтому итерации заканчиваем. Приближенным решением системы являются следующие значения:

x ₁ 0.7999, x ₂ 0.9999, x ₃ 1.1999, x ₄ 1.3999.

Для сравнения приведем точные значения переменных:

x ₁ = 0.8, x ₂ = 1.0, x ₃ = 1.2, x ₄ = 1.4.

Дата добавления: 2014-01-05