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

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

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

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

Пусть дана СЛАУ вида: $Ax=B$, где

$A=\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \cdots & a_{nn}\end{array}\right],x=\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right],B=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_n\end{array}\right]$

Предполагается, что $a_{ii}\ne 0,i=\overline{1,n}$. Выразим $x_1$ через первое уравнение, $x_2$ — через второе и т. д.:

$\{\begin{array}{c}{x}_1=\frac{b_1}{a_{11}}-\frac{a_{12}}{a_{11}}{x}_2-\cdots -\frac{a_{1n}}{a_{11}}{x}_n\\ ⋮\\ x_n=\frac{b_n}{a_{nn}}-\frac{a_{n1}}{a_{nn}}{x}_1-\frac{a_{n2}}{a_{nn}}{x}_2-\cdots -\frac{a_{n,n-1}}{a_{nn}}{x}_{n-1}\end{array}$

Пусть

${\alpha }_{ij}=\{\begin{array}{cc}-\frac{a_{ij}}{a_{ii}},& i\ne j,\\ 0,& i=j,\end{array}$

${\beta }_i=\frac{b_i}{a_{ii}},$

для $i,j=\overline{1,n}$ и пусть

$\alpha =\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& \ddots & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right],\beta =\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]$

Тогда исходная система преобразуется к виду $x=\beta +\alpha x$.

За нулевое приближение примем столбец свободных членов:

$\left[\begin{array}{c}{x}_1^{(0)}\\ ⋮\\ x_n^{(0)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]$

Тогда

$\left[\begin{array}{c}{x}_1^{(1)}\\ ⋮\\ x_n^{(1)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]+\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& \ddots & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1^{(0)}\\ ⋮\\ x_n^{(0)}\end{array}\right]$ — первое приближение,

$\left[\begin{array}{c}{x}_1^{(2)}\\ ⋮\\ x_n^{(2)}\end{array}\right]=\left[\begin{array}{c}{\beta }_1\\ ⋮\\ {\beta }_n\end{array}\right]+\left[\begin{array}{ccc}{\alpha }_{11}& \cdots & {\alpha }_{1n}\\ ⋮& \ddots & ⋮\\ {\alpha }_{n1}& \cdots & {\alpha }_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1^{(1)}\\ ⋮\\ x_n^{(1)}\end{array}\right]$ — второе приближение и т.д.

Общая формула итерационного процесса имеет вид

$x^{(k)}=\beta +\alpha x^{(k-1)},k=1,2,\dots$

За решение исходной системы принимается $x^{*}=\underset{k\to \mathrm{\infty }}{\lim }{x}^{(k)}$.

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

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

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

В частности при выборе нормы, подчинённой векторной $\Vert x{\Vert }_{\mathrm{\infty }}=\max {}_{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$-м шаге алгоритма:

• априорная:

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