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

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

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

Описание методаПравить

Пусть дана СЛАУ вида: $Ax=B$$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}\ne <!--\; \ne \; -->0,i=\stackrel{¯<!--\; ¯\; -->}{1,n}$$a_{ii}\neq 0,\ i={\overline {1,n}}$ . Выразим $x_1$$x_{1}$  через первое уравнение, $x_2$$x_{2}$  — через второе и т. д.:

$\{\begin{array}{c}{x}_1=\frac{b_1}{a_{11}}-<!--\; -\; -->\frac{a_{12}}{a_{11}}{x}_2-<!--\; -\; -->\cdots <!--\; \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 <!--\; \cdots \; -->-<!--\; -\; -->\frac{a_{n,n-<!--\; -\; -->1}}{a_{nn}}{x}_{n-<!--\; -\; -->1}\end{array}$$\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.$ 

${\mathrm{\beta <!--\; \beta \; -->}}_i=\frac{b_i}{a_{ii}},$$\beta _{i}={\frac {b_{i}}{a_{ii}}},$ 

для $i,j=\stackrel{¯<!--\; ¯\; -->}{1,n}$$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=\mathrm{\beta <!--\; \beta \; -->}+\mathrm{\alpha <!--\; \alpha \; -->}x$$x=\beta +\alpha x$ .

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

$\left[\begin{array}{c}{x}_1^{(0)}\\ ⋮<!--\; ⋮\; -->\\ x_n^{(0)}\end{array}\right]=\left[\begin{array}{c}{\mathrm{\beta <!--\; \beta \; -->}}_1\\ ⋮<!--\; ⋮\; -->\\ {\mathrm{\beta <!--\; \beta \; -->}}_n\end{array}\right]$${\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)}=\mathrm{\beta <!--\; \beta \; -->}+\mathrm{\alpha <!--\; \alpha \; -->}{x}^{(k-<!--\; -\; -->1)},k=1,2,\dots <!--\; \dots \; -->$$x^{(k)}=\beta +\alpha x^{(k-1)},\ k=1,2,\dots$ 

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

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

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

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

В частности при выборе нормы, подчинённой векторной $\Vert <!--\; \Vert \; -->x{\Vert <!--\; \Vert \; -->}_{\mathrm{\infty <!--\; \infty \; -->}}=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->n}{max}|x_i|$$\|x\|_{\infty }=\max \limits _{1\leq i\leq n}|x_{i}|$  условие сходимости приобретает вид $\max _{j=1}^{n}\vert \alpha _{ij}\vert <1$  (где $i=1,2,\dots <!--\; \dots \; -->,n$$i=1,2,\dots ,n$ ).

При выборе нормы $\Vert <!--\; \Vert \; -->x{\Vert <!--\; \Vert \; -->}_1=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}|x_i|$$\|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 <!--\; \dots \; -->,n$$j=1,2,\dots ,n$ ), что называют условием диагонального преобладания исходной матрицы $A$$A$ .

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

Пусть $x$$x$  — вектор точного решения. Тогда можно получить следующие оценки погрешности приближённого решения $x^{(k)}$$x^{{(k)}}$  на $k$$k$ -м шаге алгоритма:

• априорная:

$\Vert <!--\; \Vert \; -->x-<!--\; -\; -->x^{(k)}\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->||\mathrm{\alpha <!--\; \alpha \; -->}|{|}^k||x^{(0)}||+\frac{\Vert <!--\; \Vert \; -->\mathrm{\alpha <!--\; \alpha \; -->}{\Vert <!--\; \Vert \; -->}^k}{1-<!--\; -\; -->\Vert <!--\; \Vert \; -->\mathrm{\alpha <!--\; \alpha \; -->}\Vert <!--\; \Vert \; -->}\Vert <!--\; \Vert \; -->\mathrm{\beta <!--\; \beta \; -->}\Vert <!--\; \Vert \; -->.$$\Vert x-x^{(k)}\Vert \leq ||\alpha ||^{k}||x^{(0)}||+{\frac {\Vert \alpha \Vert ^{k}}{1-\Vert \alpha \Vert }}\Vert \beta \Vert .$ 

• апостериорная:

$\Vert <!--\; \Vert \; -->x-<!--\; -\; -->x^{(k)}\Vert <!--\; \Vert \; -->\le <!--\; \le \; -->\frac{\Vert <!--\; \Vert \; -->\mathrm{\alpha <!--\; \alpha \; -->}\Vert <!--\; \Vert \; -->}{1-<!--\; -\; -->\Vert <!--\; \Vert \; -->\mathrm{\alpha <!--\; \alpha \; -->}\Vert <!--\; \Vert \; -->}\Vert <!--\; \Vert \; -->x^{(k)}-<!--\; -\; -->x^{(k-<!--\; -\; -->1)}\Vert <!--\; \Vert \; -->.$$\Vert x-x^{(k)}\Vert \leq {\frac {\Vert \alpha \Vert }{1-\Vert \alpha \Vert }}\Vert x^{(k)}-x^{(k-1)}\Vert .$