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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание метода[править | править вики-текст]

Пусть дана СЛАУ вида:  AX = B , где:
\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}

Предполагая, что 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 & & \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 & & \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 & & \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.