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

Разделы:
Метод релаксации — приближенный метод решения систем линейных уравнений.

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

{a11x1+…+a1nxn=b1a21x1+…+a2nxn=b2…an1x1+…+annxn=bn{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.} $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.$

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

{−x1+b12x2+…+b1nxn+c1=0…bn1x1+bn2x2+…−xn+cn=0{displaystyle left{{begin{matrix}-x_{1}+b_{12}x_{2}+ldots +b_{1n}x_{n}+c_{1}&=&0\&ldots &\b_{n1}x_{1}+b_{n2}x_{2}+ldots -x_{n}+c_{n}&=&0\end{matrix}}right.} ${displaystyle left{{begin{matrix}-x_{1}+b_{12}x_{2}+ldots +b_{1n}x_{n}+c_{1}&=&0\&ldots &\b_{n1}x_{1}+b_{n2}x_{2}+ldots -x_{n}+c_{n}&=&0\end{matrix}}right.}$

где bij=−aijaii{displaystyle b_{ij}=-{frac {a_{ij}}{a_{ii}}}} $b_{ij} = -frac{a_{ij}}{a_{ii}}$ , (i≠j){displaystyle (ineq j)} ${displaystyle (ineq j)}$ , ci=biaii{displaystyle c_{i}={frac {b_{i}}{a_{ii}}}} $c_i = frac{b_i}{a_{ii}}$

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

{R1(0)=c1−x1(0)+∑j=2nb1jxj(0)R2(0)=c2−x2(0)+∑j=1,j≠2nb2jxj(0)…Rn(0)=cn−xn(0)+∑j=1n−1bnjxj(0){displaystyle left{{begin{matrix}R_{1}^{(0)}&=&c_{1}-x_{1}^{(0)}+sum _{j=2}^{n}b_{1j}x_{j}^{(0)}\R_{2}^{(0)}&=&c_{2}-x_{2}^{(0)}+sum _{j=1,jneq 2}^{n}b_{2j}x_{j}^{(0)}\&ldots &\R_{n}^{(0)}&=&c_{n}-x_{n}^{(0)}+sum _{j=1}^{n-1}b_{nj}x_{j}^{(0)}\end{matrix}}right.} ${displaystyle left{{begin{matrix}R_{1}^{(0)}&=&c_{1}-x_{1}^{(0)}+sum _{j=2}^{n}b_{1j}x_{j}^{(0)}\R_{2}^{(0)}&=&c_{2}-x_{2}^{(0)}+sum _{j=1,jneq 2}^{n}b_{2j}x_{j}^{(0)}\&ldots &\R_{n}^{(0)}&=&c_{n}-x_{n}^{(0)}+sum _{j=1}^{n-1}b_{nj}x_{j}^{(0)}\end{matrix}}right.}$

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

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

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