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

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

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

Пусть дана СЛАУ вида: $AX=B$, где:
${\mathrm {A}}={\begin{bmatrix}a_{{11}}&\cdots &a_{{1n}}\\\vdots &&\vdots \\a_{{n1}}&\cdots &a_{{nn}}\end{bmatrix}};\qquad {\mathrm {X}}={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}};\qquad {\mathrm {B}}={\begin{bmatrix}b_{1}\\\vdots \\b_{n}\end{bmatrix}}$

Предполагая, что $a_{{ii}}$ не равно 0, $i=\overline {1,n}$. Выразим $x_{1}$ через первое уравнение, $x_{2}$ — через второе и т. д. $\left\{{\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}\\\vdots \\x_{n}={\frac {b_{n}}{a_{{nn}}}}-{\frac {a_{{1n}}}{a_{{nn}}}}x_{1}-{\frac {a_{{2n}}}{a_{{nn}}}}x_{2}-\cdots -{\frac {a_{{n-1,n}}}{a_{{nn}}}}x_{{n-1}}\end{array}}\right.$
Обозначим:

${\frac {b_{i}}{a_{{ii}}}}=\beta _{i};-{\frac {a_{{ij}}}{a_{{ii}}}}=a_{{ij}}$, $i=\overline {1,n}$, $j=\overline {1,n}$
$\alpha ={\begin{bmatrix}\alpha _{{11}}&\cdots &\alpha _{{1n}}\\\vdots &&\vdots \\\alpha _{{n1}}&\cdots &\alpha _{{nn}}\end{bmatrix}};\qquad \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 &&\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 &&\vdots \\\alpha _{{n1}}&\cdots &\alpha _{{nn}}\end{bmatrix}}{\begin{bmatrix}x_{1}^{{(1)}}\\\vdots \\x_{n}^{{(1)}}\end{bmatrix}}$ — второе приближение и т. д.;

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

$X=\lim _{{k\to \infty }}X^{{(k)}}$ — решение системы.

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

Метод итерации применяют в случае, если сходится последовательность приближений по указанному алгоритму . Условия сходимости : $\sum _{{j=1}}^{n}\vert \alpha _{{ij}}\vert <1$ (где $i$=1,2,.n) или $\sum _{{i=1}}^{n}\vert \alpha _{{ij}}\vert <1$ (где $j$=1,2.n).

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

$\Vert x_{i}-x_{i}^{{(k)}}\Vert \leq {\frac {\Vert \alpha \Vert ^{{k+1}}}{1-\Vert \alpha \Vert }}\times \Vert \beta \Vert \leq \varepsilon$, где ε -точность, x_i — вектор точных значений.

$\Vert \alpha \Vert$ — одна из трёх норм матрицы α,$\Vert \beta \Vert$ — одна из трёх норм матрицы β.