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

Ме́тод Зе́йделя (метод Зейделя – Гаусса), итерационный метод решения системы линейных алгебраических уравнений ${\displaystyle Ax=b}$. Решение системы ${\displaystyle x^{*}}$ находится как предел последовательности

${\displaystyle x^{(k)}=\left(x_{1}^{(k)},x_{2}^{(k)},\ldots ,x_{n}^{(k)}\right)}$,

вычисляемой по правилу

${\displaystyle {\begin{aligned}x_{i}^{(k)}=-\sum _{j=1}^{i-1}{\frac {a_{ij}}{a_{ii}}}x_{j}^{(k)}-\sum _{j=i+1}^{n}{\frac {a_{ij}}{a_{ii}}}x_{j}^{(k-1)}\div {\frac {b_{i}}{a_{ii}}},\\i=1,\,2,\ldots ,\,n,\end{aligned}}}$ (*)

где ${\displaystyle a_{ij}}$ – элементы матрицы ${\displaystyle A}$, ${\displaystyle b_{i}}$ – компоненты вектора ${\displaystyle b}$; диагональные элементы матрицы ${\displaystyle A}$ предполагаются отличными от нуля. Вычисления ${\displaystyle (*)}$ отличаются от метода простой итерации лишь тем, что на ${\displaystyle k}$-м шаге при вычислении ${\displaystyle i}$-й компоненты учитываются вычисленные ${\displaystyle k}$-е приближения первых ${\displaystyle (i-1)}$ компонент. В матричной записи метод Зейделя представляется следующим образом. Если ${\displaystyle A=B+C}$, где

${\displaystyle {\begin{aligned}B=\left\|{\begin{array}{llll}a_{11}&0&\ldots &0\\a_{21}&a_{22}&\ldots &0\\\ldots &\ldots &\ldots &\ldots \\a_{n1}&a_{n2}&\ldots &a_{nn}\end{array}}\right\|,\quad C=\left\|{\begin{array}{ccccc}0&a_{12}&a_{13}&\ldots &a_{1n}\\0&0&a_{23}&\ldots &a_{2n}\\\ldots &\ldots &\ldots &\ldots &\ldots \\0&0&0&\ldots &0\end{array}}\right\|\end{aligned}}}$,

то соотношение ${\displaystyle (*)}$ соответствует матричному соотношению ${\displaystyle x^{(k)}=-B^{-1}Cx^{(k-1)}+B^{-1}b}$. Метод Зейделя равносилен методу простой итерации, применённому к системе ${\displaystyle x=-B^{-1}Cx+B^{-1}b}$, эквивалентной исходной. Для сходимости метода Зейделя необходимо и достаточно, чтобы все собственные значения матрицы ${\displaystyle B^{-1}C}$ по модулю были меньше ${\displaystyle 1}$. Иначе, чтобы все корни уравнения ${\displaystyle \operatorname {det} (C+B\lambda )=0}$ были по модулю меньше ${\displaystyle 1}$.

На практике более удобны следующие достаточные условия сходимости метода Зейделя. 1) Пусть при всех ${\displaystyle i}$, ${\displaystyle 1\leqslant i<n}$, ${\displaystyle \sum _{i\neq j}\left|a_{ij}\right|\leqslant q\left|a_{ii}\right|}$, ${\displaystyle q<1}$. Тогда метод Зейделя сходится и для скорости сходимости имеет место оценка:

${\displaystyle \left\|x^{(k)}-x^{*}\right\|_{1}\leqslant q\left\|x^{(k-1)}-x^{*}\right\|,\quad \|x\|_{1}=\max _{1\leqslant i\leqslant n}\left|x_{i}\right|}$.

2) Пусть ${\displaystyle A}$ – эрмитова положительно определённая матрица. Тогда метод Зейделя сходится.

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

Известны модификации метода Зейделя, использующие предварительное преобразование исходной системы в эквивалентную ей систему ${\displaystyle x=Mx+f}$ (^[1]).

Метод предложен Ф. Зейделем (^[2]).