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

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

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

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

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

$A={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\cdots &a_{nn}\end{bmatrix}},\ x={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}},\ B={\begin{bmatrix}b_{1}\\\vdots \\b_{n}\end{bmatrix}}$

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

$\left\{{\begin{array}{c}x_{1}={\dfrac {b_{1}}{a_{11}}}-{\dfrac {a_{12}}{a_{11}}}x_{2}-\cdots -{\dfrac {a_{1n}}{a_{11}}}x_{n}\\\vdots \\x_{n}={\dfrac {b_{n}}{a_{nn}}}-{\dfrac {a_{n1}}{a_{nn}}}x_{1}-{\dfrac {a_{n2}}{a_{nn}}}x_{2}-\cdots -{\dfrac {a_{n,n-1}}{a_{nn}}}x_{n-1}\end{array}}\right.$

Пусть

$\alpha _{ij}=\left\lbrace {\begin{array}{cc}-{\dfrac {a_{ij}}{a_{ii}}},&i\neq j,\\0,&i=j,\end{array}}\right.$

$\beta _{i}={\frac {b_{i}}{a_{ii}}},$

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

$\alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}},\ \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}$

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

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

${\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}$

Тогда

${\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}$ — первое приближение,

${\begin{bmatrix}x_{1}^{(2)}\\\vdots \\x_{n}^{(2)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}$ — второе приближение и т.д.

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

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

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

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

Необходимое и достаточное условие сходимости: $\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 .$