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

Метод простой итерации

$Ax=b$ приводим к виду, удобному для итерации: $x=Bx+c$

$\{\begin{array}{c}{x}_1=b_{11}{x}_1+...+b_{1m}{x}_m+c_1\\ \dots \\ x_m=b_{m1}{x}_1+...+b_{mm}{x}_m+c_m\end{array}$

Самый простой метод: из $i$-го уравнения выражаем $x_i$. Возможно только если диагональные элементы матрицы $A$ ненулевые. Иногда приводят к виду $x=x-\tau (Ax-b)$, где $\tau$ - специально выбираемый числовой параметр. Описание: Выбираем начальное приближение $x^{(0)}=(x_1^{(0)},x_2^{(0)},...,x_m^{(0)}{)}^T$ $x^{(1)}=B{x}^{(0)}+c{x}^{(k+1)}=B{x}^{(k)}+c,k=0,1,2,...$

Если система $x=Bx+c$ получена по вышеописанному (самому простому) методу, то МПИ называется методом Якоби. Шаблон:МатТеорема Шаблон:Доказательство Шаблон:Замечание Апостериорная оценка погрешности:

Если $\Vert B\Vert <1$, то справедлива апостериорная оценка: $\Vert x^{(n)}-\bar{x}\Vert \le \frac{\Vert B\Vert }{1-\Vert B\Vert }\Vert x^{(n)}-x^{(n-1)}\Vert$ Шаблон:Доказательство

Критерий окончания итерационного процесса: $\Vert x^{(n)}-x^{(n-1)}\Vert <{\epsilon }_1$, где ${\epsilon }_1=\frac{1-\Vert B\Vert }{\Vert B\Vert }\epsilon$. Если $A$ - симметричная, положительно определенная матрица, то $Ax=b$, часто приводят к виду $x=x-\tau (Ax-b)$

$x^{(k+1)}=x^{(k)}-\tau (A{x}^{(k)}-b)$ - здесь $B=E-\tau A$. Параметр $\tau >0$ выбирают так, чтобы по возможности сделать минимальной $\Vert b{\Vert }_2=\max 1\le j\le m\sqrt{{\lambda }_j(B^{T}B)}$. $\Vert B{\Vert }_2<1$ если $\tau \in (0,\frac{2}{{\lambda }_{max}})$. Оптимально $\tau =\frac{2}{{\lambda }_{min}+{\lambda }_{max}}$

Тогда $\Vert B{\Vert }_2=\frac{{\lambda }_{max}-{\lambda }_{min}}{{\lambda }_{max}+{\lambda }_{min}}$. Если известны не сами ${\lambda }_{min}$ и ${\lambda }_{max}$, а их оценки $0<\mu \le {\lambda }_{min}\le {\lambda }_{max}\le M$ или ${\lambda }_{max}\le M\Rightarrow \tau =\frac{2}{\mu +M}$ или $\tau <\frac{2}{M}(\tau =\frac{1}{M})$. В случае ${\lambda }_{min}\le {\lambda }_{max}$ то $\mathrm{\forall }\tau \in (0,\frac{2}{{\lambda }_{max}}):\Vert B{\Vert }_2=1$ метод сходится медленно.

Метод Зейделя - модификация метода Якоби

$\begin{array}{cc}& x_1=b_{12}{x}_2+b_{13}{x}_3+...+b_{1,m-1}{x}_{m-1}+b_{1m}{x}_m+c_1\\ & x_2=b_{21}{x}_1+b_{23}{x}_3+...+b_{2,m-1}{x}_{m-1}+b_{2m}{x}_m+c_2\\ & x_3=b_{31}{x}_1+b_{32}{x}_2+...+b_{3,m-1}{x}_{m-1}+b_{3m}{x}_m+c_3\\ & \dots \\ & x_m=b_{m1}{x}_1+b_{m2}{x}_2+b_{m3}{x}_3+...+b_{m,m-1}{x}_{m-1}+c_m\end{array}\text{,}$

где $b_{ij}=-\frac{a_{ij}}{a_{ii}}$, $c_i=\frac{b_i}{a_{ij}}$, $i,j=1,2,\dots ,m,j=i$

Метод Зейделя:

$\begin{array}{cc}& x_1=b_{12}{x}_2+b_{13}{x}_3+...+b_{1m}{x}_m+c_1\\ & x_2=b_{21}{x}_1+b_{23}{x}_3+...+b_{2m}{x}_m+c_2\\ & x_3=b_{31}{x}_1+b_{32}{x}_2+...+b_{3m}{x}_m+c_3\\ & \dots \\ & x_m=b_{m1}{x}_1+b_{m2}{x}_2+b_{m3}{x}_3+...++c_m\end{array}$

Введем: $B_1=\left(\begin{array}{cccc}0& 0& \dots & 0\\ b_{21}& 0& \dots & 0\\ \dots \\ b_{m1}& b_{m2}& \dots & 0\end{array}\right),B_2=\left(\begin{array}{cccc}0& b_{12}& \dots & b_{1m}\\ 0& 0& \dots & b_{2m}\\ \dots \\ 0& 0& \dots & 0\end{array}\right)$ - верхняя и нижняя треугольные матрицы.

$x^{(k+1)}=B_1{x}^{(k+1)}+B_2{x}^{(k)}+cB=B_1+B_2\Rightarrow \bar{x}$ удовлетворяет: $\bar{x}=B_1\bar{x}+B_2\bar{x}+c$

Шаблон:МатТеорема Апостериорная оценка: Если $\Vert B\Vert <1$, то $\Vert x^{(n)}-\bar{x}\Vert \le \frac{\Vert B_2\Vert }{1-\Vert B\Vert }\Vert x^{(n)}-x^{(n-1)}\Vert ,n\ge 1$.

Возьмем $k=n-1\Rightarrow$ $x^{(n)}-\bar{x}=B(x^{(n)}-\bar{x})+B_2(x^{(n-1)}-x^{(n)})$ $\Vert x^{(n)}-\bar{x}\Vert =\Vert B\Vert \Vert x^{(n)}-\bar{x}\Vert +\Vert B_2\Vert \Vert x^{(n-1)}-x^{(n)}\Vert \Rightarrow \Vert x^{(n)}-\bar{x}\Vert \le \frac{\Vert B_2\Vert }{1-\Vert B\Vert }$

Для данного $\epsilon$ критерий окончания: $\Vert x^{(n)}-x^{(n-1)}\Vert \le {\epsilon }_2$, где ${\epsilon }_2=\frac{1-\Vert B\Vert }{\Vert B_2\Vert }\epsilon$

Геометрическая интерпретация метода Зейделя

$m=2:$ $\{\begin{array}{cc}{a}_{11}{x}_1+a_{12}{x}_2=b_1& \\ a_{21}{x}_1+a_{22}{x}_2=b_2& \end{array}$

Расчетные формулы:

$\begin{array}{ccc}{x}_1^{(k+1)}=b_{12}{x}_2^{(k)}+c_1& b_{12}=-\frac{a_{12}}{a_{11}}& c_1=\frac{b_1}{a_{11}}\\ x_2^{(k+1)}=b_{21}{x}_1^{(k)}+c_2& b_{21}=-\frac{a_{21}}{a_{22}}& c_2=\frac{b_2}{a_{22}}\end{array}$

Метод Якоби

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

После вычисления $i$-ой компоненты по методу Зейделя ($(k+1)$-го приближения) ${\tilde{x}}_i^{(k+1)}=b_{i1}{x}_1^{(k+1)}+b_{i1}{x}_2^{(k+1)}+...+b_{i,i-1}{x}_{i-1}^{(k+1)}+b_{i,i+1}{x}_{i+1}^{(k+1)}+...+b_{i,m}{x}_m^{(k+1)}+C$ Производится дополнительно смещение этой компоненты на величину $(\omega -1)({\tilde{x}}_i^{(k+1)}-x_i^{(k)})$, где $\omega$ - параметр релаксации. То есть $i$ -я компонента $(k+1)$-го приближения вычисляется по формуле:

$x_i^{(k+1)}={\tilde{x}}_i^{(k+1)}+(\omega -1)({\tilde{x}}_i^{(k+1)}-x_i^{(k)})=\omega {\tilde{x}}_i^{(k+1)}+(1-\omega )x_i^{(k)}$

Компактная формула:

$x^{(k+1)}=(1-\omega )x^{(k)}+\omega B_1{x}^{(k+1)}+\omega B_2{x}^{(k)}+\omega c$

При $\omega =1$ получаем метод Зейделя. Если $\omega >1$ - метод последовательной верхней релаксации. Если $\omega <1$ - метод последовательной нижней релаксации. Если $A$ - симметричная и положительно определенная матрица, то $\mathrm{\forall }\omega :(0<\omega <2)$ метод релаксации сходится. Иногда можно выбрать $\omega >1$ так, чтобы метод сходился существенно быстрее, чем метод Якоби и Зейделя. Выбор параметра - зачастую экспериментально.