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

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

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

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

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

$x=Bx+g$

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

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

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

$\begin{array}{cc}{x}_1^{(k+1)}=& b_{11}{x}_1^{(k)}+\dots +b_{1n}{x}_n^{(k)}+g_1\\ \dots \\ x_n^{(k+1)}=& b_{n1}{x}_1^{(k)}+\dots +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 )=\frac{\omega }{2-\omega }(\frac{1}{\omega }D+L)D^{-1}{(\frac{1}{\omega }D+L)}^{𝖳}$ — метод симметричной релаксации.

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

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

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

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

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

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

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

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

• априорная:

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга