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

Метод релаксации (от лат. relaxatio тут «уменьшение») — итерационный метод решения систем линейных алгебраических уравнений.

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

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

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

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

[math]\displaystyle{ \left\{ \begin{matrix} P_{11}x_1 + P_{12}x_2 + \ldots + P_{1n}x_n + c_1 & = & 0\\ & \ldots & \\ P_{n1}x_1 + P_{n2}x_2 + \ldots + P_{nn}x_n + c_n & = & 0\\ \end{matrix} \right. }[/math]

где [math]\displaystyle{ P_{ij} = -\frac{a_{ij}}{a_{ii}} }[/math], [math]\displaystyle{ c_i = \frac{b_i}{a_{ii}} }[/math]. То есть все [math]\displaystyle{ P_{ii} }[/math] = -1.

Находятся невязки [math]\displaystyle{ R_{j} }[/math]:

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

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

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

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