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

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

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

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

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

$x=Bx+g$

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

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

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

${\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}}$.

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

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

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

$Ax=b$

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

$(M-N)x=b$

$Mx=Nx+b$

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

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

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

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

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

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

Достаточное условие сходимости: $\Vert \alpha \Vert <1$.

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

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

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

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

• априорная:

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

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

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