Ітераційні методи розв'язування СЛАР

${\displaystyle \left\{{\begin{array}{c}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1}\\\vdots \\a_{n1}x_{1}+\cdots +a_{nn}x_{n}=b_{n}\end{array}}\right.}$

АХ = В — у матричному вигляді. ${\displaystyle \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}}}$

Припускаючи, що ${\displaystyle a_{ii}\neq 0}$ ; (${\displaystyle i}$${\displaystyle =}$${\displaystyle 1}$,${\displaystyle 2}$, …,${\displaystyle n}$), виразимо ${\displaystyle x_{1}}$ через перше рівняння, ${\displaystyle x_{2}}$ — через друге і т. д. ${\displaystyle \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.}$ Позначимо:

${\displaystyle {\frac {b_{i}}{a_{ii}}}=\beta _{i};-{\frac {a_{ij}}{a_{ii}}}=\alpha _{ij};}$

${\displaystyle i}$${\displaystyle =}$${\displaystyle 1}$,${\displaystyle 2}$,…,${\displaystyle n}$; ${\displaystyle j}$${\displaystyle =}$${\displaystyle 1}$,${\displaystyle 2}$,…,${\displaystyle n}$; ${\displaystyle \left\{{\begin{array}{c}x_{1}=\beta _{1}+\alpha _{12}x_{2}+\cdots +\alpha _{1n}x_{n}\\\vdots \\x_{n}=\beta _{n}+\alpha _{n1}x_{1}+\cdots +\alpha _{n,n-1}x_{n-1}\end{array}}\right.}$ Система приведена до нормального вигляду.

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

${\displaystyle X}$=${\displaystyle \beta }$+${\displaystyle \alpha }$х — система у матричному вигляді.

За нульове наближення приймемо стовпець вільних членів.

${\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 &&\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}}$ — I наближення;

${\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 &&\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}}$ — II наближення і т. д.;

${\displaystyle X^{(k)}=\beta +\alpha X^{(k-1)}}$ (${\displaystyle k}$${\displaystyle =}$${\displaystyle 0}$, …,${\displaystyle \pi }$).

${\displaystyle X=\lim _{x\to \infty }x^{(k)}}$ — розв'язання системи.

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

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

${\displaystyle \Vert \alpha \Vert }$ — одна з трьох норм матриці ${\displaystyle \alpha }$,${\displaystyle \Vert \beta \Vert }$ — одна з трьох норм матриці ${\displaystyle \beta }$.

Належить до класу т. зв. степеневих алгоритмів, є одним з найефективніших серед них для не надто великих матриць. Ітерація відбувається за наступною схемою:

${\displaystyle A_{k}=Q_{k}R_{k},\qquad A_{k+1}=R_{k}Q_{k}}$

тут ${\displaystyle Q_{k}}$ є ортогональною або унітарною матрицею, а ${\displaystyle R_{k}}$ є правою трикутною матрицею. Таким чином, для переходу до наступного кроку ітерації (від ${\displaystyle A_{k}}$ до ${\displaystyle A_{k+1}}$) спочатку знаходиться ортогонально-трикутний розклад матриці ${\displaystyle A_{k}}$, після чого матриці ${\displaystyle Q_{k}}$ і ${\displaystyle R_{k}}$ перемножуються в оберненому порядку.