Метод релаксации

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

Метод релаксации - итерационный метод решения систем линейных алгебраических уравнений.

Система линейных уравнений


\left\{
\begin{matrix}
a_{11}x_1 + \ldots + a_{1n}x_n & = & b_1\\
a_{21}x_1 + \ldots + a_{2n}x_n & = & b_2\\
 & \ldots & \\
a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_n\\
\end{matrix}
\right.

приводится к виду

\left\{
\begin{matrix}
b_{11}x_1 + b_{12}x_2 + \ldots + b_{1n}x_n + c_1 & = & 0\\
 & \ldots & \\
b_{n1}x_1 + b_{n2}x_2 + \ldots + b_{nn}x_n + c_n & = & 0\\
\end{matrix}
\right.

где b_{ij} = -\frac{a_{ij}}{a_{ii}}, c_i = \frac{b_i}{a_{ii}}

Находятся невязки R_{j}:


\left\{
\begin{matrix}
R_1^{(0)} & = & c_1 - x_1^{(0)} + \sum \limits_{j = 2}^n b_{1j}x_j^{(0)}\\
R_2^{(0)} & = & c_2 - x_2^{(0)} + \sum \limits_{j = 1, j \neq 2}^n b_{2j}x_j^{(0)}\\
 & \ldots & \\
R_n^{(0)} & = & c_n - x_n^{(0)} + \sum \limits_{j = 1}^{n - 1} b_{nj}x_j^{(0)}\\
\end{matrix}
\right.

Выбирается начальное приближение X^{(0)} = 0. На каждом шаге необходимо обратить в ноль максимальную невязку: R_s^{(k)} = \delta x_s^{(k)} \Rightarrow R_s^{(k + 1)} = 0, R_i^{(k + 1)} = R_i^{(k)} + b_{is} \delta x_s^{(k)}.

Условие остановки: |R_j^{(k)}| < \varepsilon, \forall j = \overline{1, n}.

Ответ находится по формуле: x_i \approx x_i^{(0)} + \sum_j \delta x_i^{(j)}.