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

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

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

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

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

Пусть

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

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

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

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

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

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

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

Тогда

${\displaystyle {\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}}}$ — первое приближение,

${\displaystyle {\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}}}$ — второе приближение и т.д.

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

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

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

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

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

В частности при выборе нормы, подчинённой векторной ${\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}$-м шаге алгоритма[3]:

• априорная:

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