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

3.3.1 Обоснование и вывод формул

Пусть задана система линейных алгебраических уравнений (СЛАУ):^[1]c.303

, (1)

где А - квадратная матрица n-го порядка, а- вектор - столбцы, согласованные по размерности с матрицей А.

Прежде чем решать систему линейных алгебраических уравнений (1) приведем ее к нормальному виду:

}, (2)

Но при вычислении последующей компоненты вектора используются уже вычисленные компоненты этого вектора. Вычислительное правило в скалярной форме запишется следующим образом:

Установим связь между методом Зейделя и методом простой итерации. Для этого матрицу В представим в виде суммы двух матриц: , где

H=F=

Правило Зейделя в матричной форме перепишется в виде:

или;, т.е. метод Зейделя эквивалентен методу простой итерации с матрицей.

3.3.2 Условия применимости метода Зейделя

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

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

1) ;

2) ;

3).

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

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

Для того чтобы применить метод Зейделя к решению системы линейных алгебраических уравнений Ax = b с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду x = Bx + c.

Здесь B – квадратная матрица с элементами b_ij(i, j = 1, 2, …, n), c – вектор-столбец с элементами c_ij(i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x₁ = b₁₁x₁ + b₁₂x₂ + b₁₃x₃ + … + b_1nx_n + c₁

x₂ = b₂₁x₁ + b₂₂x₂ + b₂₃x₃ + … + b_2nx_n + c₂

... … …

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃ + … + b_nnx_n + c_n

Вообще говоря, операция приведения системы к виду, удобному для итераций, не является простой и требует специальных знаний, а также существенного использования специфики системы.

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное :

x₁ = a₁₁^–1 (b₁ – a₁₂x₂ – a₁₃x₃ – … – a_1nx_n),

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

x₂ = a₂₁^–1 (b₂ – a₂₂x2 – a₂₃x₃ – … – a_2nx_n),

и т. д.

В результате получим систему,

x₁ = b₁₂x₂ + b₁₃x₃ +…+b₁,n–1x_n–1 +b_1nx_n+c₁ ,

x₂ = b₂₁x₁ + b₂₃x₃ +…+b₂,n–1x_n–1+b_2nx_n+c₂ ,

x₃ = b₃₁x₁ + b₃₂x₂ +…+b₃,n–1x_n–1+b_3nx_n+c₃ ,

… … …

x_n = b_n1x₁ + b_n2x₂ + b_n3x₃+…+b_n,n–1x_n–1+c_n ,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

b_ij = –a_ij / a_ii, c_i = b_i / a_ii (i, j = 1, 2, …, n, j ≠ i)

Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы A были ненулевыми.