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

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

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

${\begin{cases}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{cases}}$

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

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

Теорема. Пусть выполнено условие $\|B\|<1$, тогда

1. $\exists !$ решение ${\overline {x}}$ системы $x=Bx+c$
2. при $\forall$ начальном приближении $x^{(0)}$ МПИ сходится и справедлива оценка погрешности $\|x^{(n)}-{\overline {x}}\|\leq \|B\|^{n}\|x^{(0)}-{\overline {x}}\|$

Доказательство. $\{\exists !$ решение СЛАУ при любой правой части $\}\Leftrightarrow \{$ однородная система имеет только нулевое решение $\}$

Пусть $x$ - решение системы $x=Bx\Rightarrow \|x\|=\|Bx\|\leq \|B\|\|x\|$ так как $\|B\|\leq 1$, то $\|x\|=0\Rightarrow x=0$ и 1. доказано.

${\overline {x}}=B{\overline {x}}+c,\quad x^{(k+1)}=Bx^{(k)}\Rightarrow x^{(k+1)}-{\overline {x}}=B(x^{(k)}-{\overline {x}})$

$\|x^{(k+1)}-{\overline {x}}\|\leq \|B\|\|x^{(k)}-{\overline {x}}\|$ - верное $\forall k\geq 0$

$\|x^{(n)}-{\overline {x}}\|\leq \|B\|\|x^{(n-1)}-{\overline {x}}\|\leq \|B\|^{2}\|x^{(n-2)}-{\overline {x}}\|\leq ...\leq \|B\|^{n}\|x^{(0)}-{\overline {x}}\|$

при $n\to \infty$ получаем $\|B\|^{n}\to 0\Rightarrow \|x^{(n)}-{\overline {x}}\|\to 0$ при $n\to \infty$

Замечание. При $\|B\|=\|B\|_{1}$ получаем: $\sum _{i=1,i\neq j}^{m}|a_{ij}|<|a_{jj}|\quad j={\overline {1,m}}$.

Апостериорная оценка погрешности:

Если $\|B\|<1$, то справедлива апостериорная оценка: $\|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|$

Доказательство. $x^{(n)}-{\overline {x}}=B(x^{(n-1)}-x^{(n)})+B(x^{(n)}-{\overline {x}})\Rightarrow \|x^{(n)}-{\overline {x}}\|=\|B\|\|x^{(n-1)}-x^{(n)}\|+\|B\|\|x^{(n)}-{\overline {x}}\|\Rightarrow \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|$

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

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

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

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

${\begin{matrix}&x_{1}=\qquad \quad 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}+\qquad \quad 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}\qquad \quad +...+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}\qquad \quad +c_{m}\\\end{matrix}}\qquad {\text{,}}$

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

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

${\begin{matrix}&x_{1}=\qquad \quad b_{12}x_{2}+b_{13}x_{3}+...+b_{1m}x_{m}+c_{1}\\&x_{2}=b_{21}x_{1}+\qquad \quad b_{23}x_{3}+...+b_{2m}x_{m}+c_{2}\\&x_{3}=b_{31}x_{1}+b_{32}x_{2}\qquad \quad +...+b_{3m}x_{m}+c_{3}\\&\dots \\&x_{m}=b_{m1}x_{1}+b_{m2}x_{2}+b_{m3}x_{3}+...+\qquad \quad +c_{m}\\\end{matrix}}$

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

$x^{(k+1)}=B_{1}x^{(k+1)}+B_{2}x^{(k)}+c\qquad B=B_{1}+B_{2}\Rightarrow {\overline {x}}$ удовлетворяет: ${\overline {x}}=B_{1}{\overline {x}}+B_{2}{\overline {x}}+c$

Теорема. Пусть $\|B\|<1$, где $\|B\|$ - одна из норм $\|B\|_{\infty },\|B\|_{1}$. Тогда $\forall x^{(0)}$ метод Зейделя сходится со скоростью геометрической прогресии с $q\leq \|B\|$. (без доказательства)

Теорема. Пусть выполнено условие $\|B_{1}\|+\|B_{2}\|<1$. Тогда $\forall x^{(0)}$ метод Зейделя сходится и верна оценка погрешности: $\|x^{(n)}-{\overline {x}}\|\leq q^{n}\|x^{(0)}-{\overline {x}}\|$, где $q={\frac {\|B_{2}\|}{1-\|B_{1}\|}}<1$

Доказательство. :$x^{(k+1)}-{\overline {x}}=B_{1}(x^{(k+1)}-{\overline {x}})+B_{2}(x^{(k)}-{\overline {x}})$

$\|x^{(k+1)}-{\overline {x}}\|=\|B_{1}\|\|x^{(k+1)}-{\overline {x}}\|+\|B_{2}\|\|x^{(k)}-{\overline {x}}\|\Rightarrow$

$\|x^{(k+1)}-{\overline {x}}\|\leq q\|x^{(k)}-{\overline {x}}\|,\quad q={\frac {\|B_{2}\|}{1-\|B_{1}\|}}$

Неравенство верно для $\forall k\Rightarrow \|x^{(n)}-{\overline {x}}\|\leq q^{n}\|x^{(0)}-{\overline {x}}\|$ $0\leq q<1\Rightarrow x^{(n)}\to {\overline {x}}$ при $n\to \infty$

Теорема. $A$ - симметричная положительно определенная матрица. Тогда $\forall x^{(0)}$ метод Зейделя сходится со скоростью геометрической прогресии (без доказательства)

Апостериорная оценка: Если $\|B\|<1$, то $\|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B_{2}\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|,n\geq 1$.

Возьмем $k=n-1\Rightarrow$ $x^{(n)}-{\overline {x}}=B(x^{(n)}-{\overline {x}})+B_{2}(x^{(n-1)}-x^{(n)})$ $\|x^{(n)}-{\overline {x}}\|=\|B\|\|x^{(n)}-{\overline {x}}\|+\|B_{2}\|\|x^{(n-1)}-x^{(n)}\|\Rightarrow \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B_{2}\|}{1-\|B\|}}$

Для данного $\varepsilon$ критерий окончания: $\|x^{(n)}-x^{(n-1)}\|\leq \varepsilon _{2}$, где $\varepsilon _{2}={\frac {1-\|B\|}{\|B_{2}\|}}\varepsilon$

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

$m=2:$ ${\begin{cases}a_{11}x_{1}+a_{12}x_{2}=b_{1}&\\a_{21}x_{1}+a_{22}x_{2}=b_{2}&\end{cases}}$

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

${\begin{matrix}x_{1}^{(k+1)}=b_{12}x_{2}^{(k)}+c_{1}&\qquad b_{12}=-{\frac {a_{12}}{a_{11}}}&\qquad c_{1}={\frac {b_{1}}{a_{11}}}\\x_{2}^{(k+1)}=b_{21}x_{1}^{(k)}+c_{2}&\qquad b_{21}=-{\frac {a_{21}}{a_{22}}}&\qquad c_{2}={\frac {b_{2}}{a_{22}}}\end{matrix}}$

Метод Якоби

Замечание. Метод Якоби ориентирован на системы с матрицами, близкими к диагональным, а метод Зейделя - на матрицы, близкие к нижним треугольным.

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

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