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

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

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

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

{ a 11 x 1 + … + a 1 n x n = b 1 a 21 x 1 + … + a 2 n x n = b 2 … a n 1 x 1 + … + a n n x n = b n {displaystyle left{{egin{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}} ight.}

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

{ P 11 x 1 + P 12 x 2 + … + P 1 n x n + c 1 = 0 … P n 1 x 1 + P n 2 x 2 + … + P n n x n + c n = 0 {displaystyle left{{egin{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}&=&0end{matrix}} ight.}

где P i j = − a i j a i i {displaystyle P_{ij}=-{frac {a_{ij}}{a_{ii}}}} , c i = b i a i i {displaystyle c_{i}={frac {b_{i}}{a_{ii}}}} . То есть все P i i {displaystyle P_{ii}} = -1.

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

{ R 1 ( 0 ) = c 1 − x 1 ( 0 ) + ∑ j = 2 n P 1 j x j ( 0 ) R 2 ( 0 ) = c 2 − x 2 ( 0 ) + ∑ j = 1 , j ≠ 2 n P 2 j x j ( 0 ) … R n ( 0 ) = c n − x n ( 0 ) + ∑ j = 1 n − 1 P n j x j ( 0 ) {displaystyle left{{egin{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 eq 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}} ight.}

Выбирается начальное приближение X ( 0 ) = 0 {displaystyle X^{(0)}=0} . На каждом шаге необходимо обратить в ноль максимальную невязку: R s ( k ) = δ x s ( k ) ⇒ R s ( k + 1 ) = 0 , R i ( k + 1 ) = R i ( k ) + P i s δ x s ( k ) {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)}} .

Условие остановки: | R j ( k ) | < ε , ∀ j = 1 , n ¯ {displaystyle |R_{j}^{(k)}|<varepsilon ,forall j={overline {1,n}}} .

Ответ находится по формуле: x i ≈ x i ( 0 ) + ∑ j δ x i ( j ) {displaystyle x_{i}approx x_{i}^{(0)}+sum _{j}delta x_{i}^{(j)}} .