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

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

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

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

Пусть дана СЛАУ вида: [math]\displaystyle{ Ax = B }[/math], где

[math]\displaystyle{ 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} }[/math]

Предполагается, что [math]\displaystyle{ a_{ii} \neq 0, \ i = \overline{1,n} }[/math]. Выразим [math]\displaystyle{ x_1 }[/math] через первое уравнение, [math]\displaystyle{ x_2 }[/math] — через второе и т. д.:

[math]\displaystyle{ \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. }[/math]

Пусть

[math]\displaystyle{ \alpha_{ij} = \left\lbrace \begin{array}{cc} -\dfrac{a_{ij}}{a_{ii}}, &i \neq j, \\ 0, &i=j, \end{array} \right. }[/math]

[math]\displaystyle{ \beta_i=\frac{b_i}{a_{ii} }, }[/math]

для [math]\displaystyle{ i,j = \overline{1,n} }[/math] и пусть

[math]\displaystyle{ \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} }[/math]

Тогда исходная система преобразуется к виду [math]\displaystyle{ x = \beta + \alpha x }[/math].

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

[math]\displaystyle{ \begin{bmatrix}x_1^{(0)} \\ \vdots \\ x_n^{(0)}\end{bmatrix} = \begin{bmatrix}\beta_1 \\ \vdots \\ \beta_n\end{bmatrix} }[/math]

Тогда

[math]\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 & \ddots & \vdots \\ \alpha_{n1} & \cdots & \alpha_{nn}\end{bmatrix} \begin{bmatrix}x_1^{(0)} \\ \vdots \\ x_n^{(0)}\end{bmatrix} }[/math] — первое приближение,

[math]\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 & \ddots & \vdots \\ \alpha_{n1} & \cdots & \alpha_{nn}\end{bmatrix} \begin{bmatrix}x_1^{(1)} \\ \vdots \\ x_n^{(1)}\end{bmatrix} }[/math] — второе приближение и т.д.

Общая формула итерационного процесса имеет вид

[math]\displaystyle{ x^{(k)}=\beta+\alpha x^{(k-1)}, \ k =1, 2, \dots }[/math]

За решение исходной системы принимается [math]\displaystyle{ x^*=\lim_{k\to\infty}x^{(k)} }[/math].

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

Необходимое и достаточное условие сходимости: [math]\displaystyle{ \rho(\alpha) \lt 1 }[/math], где — [math]\displaystyle{ \rho(\alpha) }[/math] спектральный радиус [math]\displaystyle{ \alpha }[/math].

Достаточное условие сходимости: [math]\displaystyle{ \Vert\alpha\Vert \lt 1 }[/math].

В частности при выборе нормы, подчинённой векторной [math]\displaystyle{ \| x \|_{\infty} = \max\limits_{1 \le i \le n} |x_i| }[/math] условие сходимости приобретает вид [math]\displaystyle{ \max_{j=1}^n\vert\alpha_{ij}\vert\lt 1 }[/math] (где [math]\displaystyle{ i=1,2,\dots,n }[/math]).

При выборе нормы [math]\displaystyle{ \| x \|_1 = \sum_{i = 1}^n |x_i| }[/math] условие приобретает вид [math]\displaystyle{ \sum_{i=1\atop i\neq j}^n\vert\alpha_{ij}\vert\lt 1 }[/math] (где [math]\displaystyle{ j=1,2,\dots,n }[/math]), что называют условием диагонального преобладания исходной матрицы [math]\displaystyle{ A }[/math].

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

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

• априорная:

[math]\displaystyle{ \Vert x-x^{(k)}\Vert \le ||\alpha||^k ||x^{(0)}|| + \frac{\Vert\alpha\Vert^k }{1-\Vert\alpha\Vert} \Vert\beta\Vert. }[/math]

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

[math]\displaystyle{ \Vert x-x^{(k)}\Vert \le \frac{\Vert\alpha\Vert}{1-\Vert\alpha\Vert}\Vert x^{(k)}-x^{(k-1)}\Vert. }[/math]