Численные методы линейной алгебры

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

Метод Зейделя [3,4,9,11]представляет собой некоторую модификацию метода простой итерации. Основная идея метода заключается в том, что при вычислении (к+1)-го приближения неизвестной x_i учитываются уже вычисленные ранее (к+1)-ые приближения неизвестных x_1, x₂, …, x_n.

Пусть имеется приведенная линейная система
x_i=_i+ , (i=1, 2, …, n).
Выберем произвольно начальные приближения
.
Далее, предполагая, что к-ые приближения неизвестных вычислены, построим формулы для (к+1)-го приближения:
,
,
………………………………….
,
………………………………….
, (k=0, 1, 2,…).
Таким образом, алгоритм метода Зейделя для решения СЛАУ будет следующим

,
_ii=0, k=0, 1, 2, …
Итерация заканчивается по выполнению условия
для всех ;
где 0<<1.
Отметим, что теорема 3.1 и следствия 3.1 и 3.2 верны и для метода Зейделя.
Формулы для оценки погрешности метода Зейделя следующие [3]:
а) по m – норме

где
,
б) по l – норме
,
где
.


3.3. Метод релаксации

Имеем систему уравнений

(3.19)
Для описания метода релаксации [2, 3, 9, 11] преобразуем систему (3.19) следующим образом. Перенесем свободные члены налево и разделим первое уравнение на -а₁₁, второе на -а₂₂ и т.д. Тогда получим
(3.20)
где b_ij=-a_ij/a_ii , (ij), c_i=b_i/a_ii , (i,j=1, 2,…, n).
Пусть х⁽⁰⁾=( ) – начальное приближение, тогда подставляя его в (3.20) получим невязки
(3.21)
Если в (3.21) одной из неизвестных дать приращение  , то соответствующая невязка уменьшится на  , а остальные невязки (iк) увеличатся на величину b_ik , (i=1, 2,…, n; ik; k=1, 2,…,n ).
Следовательно, чтобы обратить невязку в нуль, достаточно величине дать приращение
 = ,
тогда будем иметь следующую систему уравнений на первой итерации
= ,
далее, чтобы на m – ой итерации обратить в нуль невязку дадим переменной приращение
 = .
Тогда получим систему уравнений
= .
Процесс итерации заканчивается, когда все невязки последней преобразованной системы будут равны нулю с требуемой точностью.
В методе рекомендуется на каждой итерации обращать в нуль максимальную по модулю невязку путем изменения значения, соответствующей компоненты приближения.
Алгоритм метода релаксации будет таким.
Задается начальное приближение
х⁽⁰⁾=( ).
Вычисляются невязки начального приближения
.
Находим величину а_к= , которой соответствует невязка и приращение
 = .
Дальше вычисляются невязки первого приближения
=
и т.д.
Затем находим величину а_к= , которой соответствует невязка и приращение
 = , что позволяет вычислить невязку m-го приближения
=
и т.д. m=m+1, m+2,…, M. M.
Итерация заканчивается при выполнении условия
где 0<<1.
Неизвестные вычисляются по формуле
x_i=


Замечание. Описанный здесь метод называется полной релаксацией. Если в процессе полной релаксации для системы уравнений (3.19) с положительно-определенной матрицей выполнено условие: Последовательность индексов i компонент x_i (i=1, 2,…, n) имеет интервал повторяемости L , т.е. на каждом отрезке длины L индекс i принимает хотя бы по одному разу все числа 1, 2,…, n , то процесс сходится к решению системы (3.19), где L – любое натуральное число.