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

===Метод простой итерации===
<math>Ax = b</math> приводим к виду, удобному для итерации: <math>x = Bx + c</math>

:<math>\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}</math>

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

Если система <math>x = Bx + c</math> получена по вышеописанному (самому простому) методу, то МПИ называется методом Якоби.
{{МатТеорема|Пусть выполнено условие <math>\|B\| < 1</math>, тогда

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

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

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

:<math>\overline x = B \overline x + c, \quad x^{(k+1)} = B x^{(k)} \Rightarrow x^{(k+1)} - \overline x = B (x^{(k)} - \overline x)</math>

:<math>\|x^{(k+1)} - \overline x\| \le \|B\| \|x^{(k)} - \overline x\|</math> - верное <math>\forall k \ge 0</math>

:<math>\|x^{(n)} - \overline x\| \le \|B\| \|x^{(n-1)} - \overline x\| \le \|B\|^2 \|x^{(n-2)} - \overline x\| \le ... \le \|B\|^n \|x^{(0)} - \overline x\|</math>

при <math>n \to \infty</math> получаем <math>\|B\|^n \to 0 \Rightarrow \|x^{(n)} - \overline x\| \to 0 </math> при <math>n \to \infty</math>
}}
{{Замечание|При <math>\|B\| = \|B\|_1</math> получаем: <math>\sum_{i = 1, i \ne j}^{m} |a_{ij}| < |a_{jj}| \quad j = \overline{1,m}</math>.
}}
Апостериорная оценка погрешности:

Если <math>\|B\| < 1</math>, то справедлива апостериорная оценка: <math>\|x^{(n)} - \overline x\| \le \frac{\|B\|}{1 - \|B\|} \|x^{(n)} - x^{(n-1)}\|</math>
{{Доказательство|<math>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\| \le \frac{\|B\|}{1 - \|B\|} \|x^{(n)} - x^{(n-1)}\|</math>
}}

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

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

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

===Метод Зейделя - модификация метода Якоби===
:<math>\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{,} </math>

где <math>b_{ij} = - \frac{a_{ij}}{a_{ii}}</math>,  <math>c_i = \frac{b_i}{a_{ij}}</math>, <math>i, j = 1, 2, \dots, m, j \not= i</math>

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

:<math>\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}</math>

Введем:
<math>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}</math> - верхняя и нижняя  треугольные  матрицы.

<math>x^{(k+1)} = B_1 x^{(k+1)} + B_2 x^{(k)} + c \qquad B = B_1 + B_2 \Rightarrow \overline x</math> удовлетворяет: <math>\overline x = B_1 \overline x + B_2 \overline x + c</math>

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

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

{{Доказательство|:<math>x^{(k+1)} - \overline x = B_1 (x^{(k+1)} - \overline x) + B_2 (x^{(k)} - \overline x)</math>

:<math>\|x^{(k+1)} - \overline x\| = \|B_1\| \|x^{(k+1)} - \overline x\| + \|B_2\| \|x^{(k)} - \overline x\| \Rightarrow </math>

:<math>\|x^{(k+1)} - \overline x\| \le q \|x^{(k)} - \overline x\|, \quad q = \frac{\|B_2\|}{1 - \|B_1\|}</math>

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

{{МатТеорема|<math>A</math> - симметричная положительно определенная матрица. Тогда <math>\forall x^{(0)}</math> метод Зейделя сходится со скоростью геометрической прогресии (без доказательства)
}}
Апостериорная оценка: Если <math>\|B\| < 1</math>, то <math>\|x^{(n)} - \overline x\| \le \frac{\|B_2\|}{1 - \|B\|} \|x^{(n)} - x^{(n - 1)}\|, n \ge 1</math>.

Возьмем <math>k = n - 1 \Rightarrow </math>
<math>x^{(n)} - \overline x = B (x^{(n)} - \overline x) + B_2 (x^{(n - 1)} - x^{(n)})</math>
<math>\|x^{(n)} - \overline x\| = \|B\| \|x^{(n)} - \overline x\| + \|B_2\| \|x^{(n - 1)} - x^{(n)}\| \Rightarrow \|x^{(n)} - \overline x\| \le \frac{\|B_2\|}{1 - \|B\|}</math>

Для данного <math>\varepsilon</math> критерий окончания: <math>\|x^{(n)} - x^{(n-1)}\| \le \varepsilon_2</math>, где <math>\varepsilon_2 = \frac{1 - \|B\|}{\|B_2\|} \varepsilon</math>

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

<math>m = 2 : </math> <math>\begin{cases}a_{11} x_1 + a_{12} x_2 = b_1 & \\ a_{21} x_1 + a_{22} x_2 = b_2 & \end{cases}</math>

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

:<math>\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}</math>

[[Файл:Vmath_1.png|thumb|Метод Якоби]]

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

===Метод релаксации===
После вычисления <math>i</math>-ой компоненты по методу Зейделя (<math>(k+1)</math>-го приближения)
<math>\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</math>
Производится дополнительно смещение этой компоненты на величину <math>(\omega - 1) (\tilde{x}_i^{(k+1)} - x_i^{(k)})</math>, где <math>\omega</math> - параметр релаксации. То есть <math>i</math> -я компонента <math>(k+1)</math>-го приближения вычисляется по формуле:

:<math>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)} </math>

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

:<math>x^{(k+1)} = (1- \omega) x^{(k)} + \omega B_1 x^{(k+1)} + \omega B_2 x^{(k)} + \omega c</math>

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


[[Категория:Вычислительная математика]]