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

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

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

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

$\{\begin{array}{ccc}{a}_{11}{x}_1+\dots +a_{1n}{x}_n& =& b_1\\ a_{21}{x}_1+\dots +a_{2n}{x}_n& =& b_2\\ & \dots & \\ a_{n1}{x}_1+\dots +a_{nn}{x}_n& =& b_n\end{array}$

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

$\{\begin{array}{ccc}{P}_{11}{x}_1+P_{12}{x}_2+\dots +P_{1n}{x}_n+c_1& =& 0\\ & \dots & \\ P_{n1}{x}_1+P_{n2}{x}_2+\dots +P_{nn}{x}_n+c_n& =& 0\end{array}$

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

Находятся невязки $R_j$:

$\{\begin{array}{ccc}{R}_1^{(0)}& =& c_1-x_1^{(0)}+\sum _{j=2}^n{P}_{1j}{x}_j^{(0)}\\ R_2^{(0)}& =& c_2-x_2^{(0)}+\sum _{j=1,j\ne 2}^n{P}_{2j}{x}_j^{(0)}\\ & \dots & \\ R_n^{(0)}& =& c_n-x_n^{(0)}+\sum _{j=1}^{n-1}{P}_{nj}{x}_j^{(0)}\end{array}$

Выбирается начальное приближение $X^{(0)}=0$. На каждом шаге необходимо обратить в ноль максимальную невязку: $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)}$.

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

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