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

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

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

Пусть дана СЛАУ вида: $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}$

Предполагая, что $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} }=\alpha_{ij}$, $i = \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}$
В матричном виде получим: $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 & \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)}=\beta+\alpha X^{(k-1)}$, $k =1, 2, \dots$

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

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

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

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

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

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