Метод итерации

Метод итерации или метод простой итерации — численный метод решения системы линейных алгебраических уравнений. Суть метода заключается в нахождении по приближённому значению величины следующего приближения, являющегося более точным.

Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (в результате итерационного процесса). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня.

Описание метода

Пусть СЛАУ представлена в виде:

${\displaystyle x=Bx+g}$

Выбирается начальное приближение ${\displaystyle x^{(0)}}$. На каждом шаге считается новое приближение ${\displaystyle x^{(k+1)}}$ из старого ${\displaystyle x^{(k)}}$ по формуле

${\displaystyle x^{(k+1)}=Bx^{(k)}+g}$

или в координатной форме

${\displaystyle {\begin{array}{rcl}x_{1}^{(k+1)}=&b_{11}x_{1}^{(k)}+\ldots +b_{1n}x_{n}^{(k)}+g_{1}\\\ldots \\x_{n}^{(k+1)}=&b_{n1}x_{1}^{(k)}+\ldots +b_{nn}x_{n}^{(k)}+g_{n}\end{array}}}$.

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

Приведение СЛАУ к нужному виду

Пусть дана СЛАУ

${\displaystyle Ax=b}$

Для того, чтобы воспользоваться методом простой итерации, необходимо привести её к виду ${\displaystyle x=Bx+g}$. Представим матрицу ${\displaystyle A}$ в виде ${\displaystyle A=M-N}$, где ${\displaystyle M}$ — обратима. Тогда система приводится к виду ${\displaystyle x=Bx+g}$ следующим образом:

${\displaystyle (M-N)x=b}$

${\displaystyle Mx=Nx+b}$

${\displaystyle x=M^{-1}Nx+M^{-1}b}$

Матрицы ${\displaystyle M}$ и ${\displaystyle N}$ могут быть выбраны различными способами; в зависимости от конкретного способа получаются различные разновидности метода. Обозначим далее за ${\displaystyle L}$ — строго нижнюю треугольную часть ${\displaystyle A}$, за ${\displaystyle D}$ — диагональную часть ${\displaystyle A}$, за ${\displaystyle U}$ — строго верхнюю треугольную часть ${\displaystyle A}$. Получающиеся таким способом разновидности эквиваленты следующим методам:

• ${\displaystyle M={\frac {1}{\omega }}E}$ — метод Ричардсона;
• ${\displaystyle M=D}$ — метод Якоби;
• ${\displaystyle M={\frac {1}{\omega }}D}$ — взвешенный метод Якоби;
• ${\displaystyle M=D+L}$ — метод Гаусса — Зейделя;
• ${\displaystyle M={\frac {1}{\omega }}D+L}$ — метод релаксации;
• ${\displaystyle M(\omega )={\omega \over {2-\omega }}\left({1 \over \omega }D+L\right)D^{-1}\left({1 \over \omega }D+L\right)^{\mathsf {T}}}$ — метод симметричной релаксации.

Здесь эквивалентность понимается в смысле равенства последовательностей приближений ${\displaystyle x^{(k)}}$ при равенстве начальных приближений ${\displaystyle x^{(0)}}$.

Условия сходимости процесса

Необходимое и достаточное условие сходимости: ${\displaystyle \rho (\alpha )<1}$, где — ${\displaystyle \rho (\alpha )}$ спектральный радиус ${\displaystyle \alpha }$^[1].

Достаточное условие сходимости: ${\displaystyle \Vert \alpha \Vert <1}$^[1].

В частности при выборе нормы, подчинённой векторной ${\displaystyle \|x\|_{\infty }=\max \limits _{1\leq i\leq n}|x_{i}|}$ условие сходимости приобретает вид ${\displaystyle \max _{j=1}^{n}\vert \alpha _{ij}\vert <1}$ (где ${\displaystyle i=1,2,\dots ,n}$).

При выборе нормы ${\displaystyle \|x\|_{1}=\sum _{i=1}^{n}|x_{i}|}$ условие приобретает вид ${\displaystyle \sum _{i=1 \atop i\neq j}^{n}\vert \alpha _{ij}\vert <1}$ (где ${\displaystyle j=1,2,\dots ,n}$), что называют условием диагонального преобладания исходной матрицы ${\displaystyle A}$.

Оценка погрешности

Пусть ${\displaystyle x}$ — вектор точного решения. Тогда можно получить следующие оценки погрешности приближённого решения ${\displaystyle x^{(k)}}$ на ${\displaystyle k}$-м шаге алгоритма^[2]:

• априорная:

${\displaystyle \Vert x-x^{(k)}\Vert \leq ||\alpha ||^{k}||x^{(0)}||+{\frac {\Vert \alpha \Vert ^{k}}{1-\Vert \alpha \Vert }}\Vert \beta \Vert .}$

• апостериорная:

${\displaystyle \Vert x-x^{(k)}\Vert \leq {\frac {\Vert \alpha \Vert }{1-\Vert \alpha \Vert }}\Vert x^{(k)}-x^{(k-1)}\Vert .}$