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

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

В методе Якоби на (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 … 0 0 0 b ₂₃ … b _{2 n}

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

b_{n 1} b_{n 2} b_{n 3} … 0 0 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)

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

b = 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, b ₂ – максимальный элемент матрицы B ₂.

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

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

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

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

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

где e _{1 =} e_.

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

max| x– x | < e, 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 показывает, что метод Зейделя сходится быстрее и дает более точный результат.

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