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

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

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

Пусть дана СЛАУ вида: $AX=B$$AX=B$, где:
$\mathrm {A} ={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\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}}$$\mathrm {A} ={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\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}$$a_{{ii}}$ не равно 0, $i={\overline {1,n}}$$i={\overline {1,n}}$. Выразим $x_{1}$$x_{1}$ через первое уравнение, $x_{2}$$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_{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}}\right.$$\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_{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}}\right.$
Обозначим:

${\frac {b_{i}}{a_{ii}}}=\beta _{i};-{\frac {a_{ij}}{a_{ii}}}=\alpha _{ij}$${\frac {b_{i}}{a_{ii}}}=\beta _{i};-{\frac {a_{ij}}{a_{ii}}}=\alpha _{ij}$, $i={\overline {1,n}}$$i={\overline {1,n}}$, $j={\overline {1,n}}$$j={\overline {1,n}}$
$\alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}};\qquad \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}$$\alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}};\qquad \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}$
В матричном виде получим: $X=\beta +\alpha x$$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}^{(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}^{(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}}$${\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)}$$X^{(k)}=\beta +\alpha X^{(k-1)}$, $k=1,2,\dots$$k=1,2,\dots$

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

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

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

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

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

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