Метод Зейделя

Модификацией метода простых итераций Якоби можно считать метод Зейделя.

В методе Якоби на (k +1)-ой итерации значения x, i = 1, 2, …, n. вычисляются подстановкой в правую часть (3.27) вычисленных на предыдущей итерации значений x. В методе Зейделя при вычислении x используются значения x, x, x, уже найденные на (k +1)-ой итерации, а не 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.36)

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

Формулы (3.36) являются расчетными формулами метода Зейделя.

Введем нижнюю и верхнюю треугольные матрицы:

0 0 0 … 0 0 b ₁₂ b ₁₃ … b _{1 n}

b ₂₁0 0 … 000 b ₂₃ … b _{2 n}

B ₁= b ₃₁ b ₃₂0 … 0 и B ₂ = 000 … b _{3 n.}

b_{n 1} b_{n 2} b_{n 3} … 00 0 0 … 0

Матричная запись расчетных формул (3.36) имеет вид:

x^{k+ 1} = B ₁ x^{k+ 1} + B ₂ x^k+ c. (3.37)

Так как B = B ₁ + B ₂, точное решение x ^* исходной системы удовлетворяет равенству:

x^*= B ₁ x^*+ B ₂ x^*+ c. (3.38)

Сходимость метода Зейделя. Достаточным условием сходимости метода Зейделя является выполнение неравенства:

= max | b_ij |,< 1, i, j = 1, 2, …, n. (3.39)

Неравенство (3.39) означает, что для сходимости метода Зейделя достаточно, чтобы максимальный по модулю элемент матрицы B был меньше единицы.

Если выполнено условие (3.39), то справедлива следующая апостериорная оценка погрешности:

max| x - x | max| x - x | i = 1, 2, …, n, (3.40)

где - максимальный элемент матрицы B, ₂- максимальный элемент матрицы B ₂.

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

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

max| x - x | <, i = 1, 2, …, n. (3.41)

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

max| x - x | < ₁, i = 1, 2, …, n. (3.42)

где _{1 =.}

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

max| x - x | <, i = 1, 2, …, n. (3.43)

Метод Зейделя как правило сходится быстрее, чем метод Якоби. Однако возможны ситуации, когда метод Якоби сходится, а метод Зейделя сходится медленнее или вообще расходится.

Пример 3.6.

Применим метод Зейделя для решения системы уравнений (3.33) из примера 3.5. Первые шаги полностью совпадают с процедурой решения по методу Якоби, а именно: система приводится к виду (3.34), затем в качестве начального приближения выбираются элементы столбца свободных членов (3.35). Проведем теперь итерации методом Зейделя.

При k = 1

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

При вычислении x используем уже полученное значение x:

x = -0.0566 x - 0.0708 x - 0.1179 x + 1.2953 = 0.9674

При вычислении x используем уже полученные значения x и x:

x = -0.1061 x - 0.0758 x - 0.0657 x + 1.4525 = 1.1977

При вычислении x используем уже полученные значения x, x, x:

x = -0.0280 x - 0.0779 x - 0.0405x x + 1.5489 = 1.4037

Аналогичным образом проведем вычисления при k = 2 и k = 3. Получим:

при k = 2

x= 0.8019, x= 0.9996, x= 1.9996, x= 1.4000.

при k = 3

x= 0.80006, x= 1.00002, x= 1.19999, x= 1.40000.

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

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

Сравнение с примером 3.5 показывает, что метод Зейделя сходится быстрее и дает более точный результат.