Участник:Коростелец
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Будем рассматривать систему линейных алгебраических уравнений
[math]Ay=f[/math]
где А - квадратная невырожденная матрица порядка m, у - искомый вектор размерности m, f - заданный вектор той же размерности
Рассмотрим нестационарный одношаговый итерационный метод решения такой системы вида
[math]B \frac{y_{n+1}-y_n}{\tau_{n+1}}+Ay_n=f; n=0,1,...; y_0\in H,[/math]
а так же аналогичный двушаговый метод
[math] B \frac{y_{n+1}-y_n+(1-\alpha_{n+1})(y_n-y_{n-1})}{\alpha_{n+1}\tau_{n+1}}+Ay_n=f, \frac{y_{1}-y_0}{\tau_{1}}+Ay_0=f; n=1,...; y_0\in H[/math] Целью алгоритма является решение такой системы.
1.2 Математическое описание алгоритма
В описанном методе невырожденная матрица B не зависит от номера итерации n, решение y системы и последовательные приближения y_n - элементы линейного пространства H размерности m, в котором определены скалярное произведение и норма
[math]||y||=\sqrt{(y,y)}[/math]
Можно выразить
[math] \begin{equation} y_{n+1}=y_n -\tau_{n+1}B^{-1}(Ay_n-f) \end{equation} [/math]
Тогда для нахождения
[math]y_{n+1}[/math]
необходимо определить
[math]\tau_{n+1}[/math]
Пусть
[math]z_n=y_n-y[/math]
- погрешность на n-ой итерации. Выразив
[math]y_{n+1}[/math] и [math]y_n[/math] через погрешность, можно получить
[math]B\frac{z_{n+1}+y-z_n-y}{\tau_{n+1}}+Ay_n=f B\frac{z_{n+1}-z_n}{\tau_{n+1}}+Ay_n=f[/math] отсюда [math]z_{n+1}=z_n-\tau_{n+1}B^{-1}(Ay_n-f)=(E-\tau_{n+1}B^{-1}A)z_n[/math] Пусть D - произвольная матрица, удовлетворяющая условиям [math]D^T=D\gt 0.[/math] Выбор итерационных параметров [math]\tau_{n+1}[/math] можно сделать на основе минимизации энергитической нормы [math]||z_{n+1}||_D.[/math]
Такой способ построения итерационного процесса называется локальной минимизацией.
Обозначив [math] \begin{equation} w_{n+1}=D^{1/2}z_{n+1} \end{equation} [/math] получим [math]||z_{n+1}||_D=\sqrt{(Dz_{n+1},z_{n+1})}=\sqrt{(D^{1/2}z_{n+1},D^{1/2}z_{n+1})}=||w_{n+1}||[/math] Значит минимизация
[math]||z_{n+1}||_D[/math] эквивалентна минимизации [math]||w_{n+1}||[/math]
Выразим [math]w_{n+1}=D^{1/2}z_{n+1}=D^{1/2}(E-\tau_{n+1}B^{-1}A)z_n=D^{1/2}(E-\tau_{n+1}B^{-1}A)D^{-1/2}D^{1/2}z_n= =(E-\tau_{n+1}D^{-1/2}B^{-1}AD^{1/2})w_n=(E-\tau_{n+1}C)w_n[/math], где [math] \begin{equation} C=D^{-1/2}B^{-1}AD^{1/2} \end{equation} [/math]
- невырожденная матрица. Пусть
[math]w_0\neq 0,[/math] иначе на n-ой итерации найдено точное решение, тогда
[math]||w_{n+1}||^2=((E-\tau_{n+1}C)w_n,(E-\tau_{n+1}C)w_n)= =||w_n||^2+\tau_{n+1}^2(Cw_n,Cw_n)-2\tau_{n+1}(Cw_n,w_n)= =||w_n||^2+(Cw_n,Cw_n)(\tau_{n+1}^2-2\tau_{n+1}\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)})= =||w_n||^2+(Cw_n,Cw_n)(\tau_{n+1}-\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)})^2-\frac{(Cw_n,w_n)^2}{(Cw_n,Cw_n)}[/math] Это значит, что минимальное значение [math]||w_{n+1}||[/math] достигается при [math]\tau_{n+1}=\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)},[/math] где [math]\tau_{n+1}\gt 0,[/math]
если C>0
В дальнейшем предполагаем условие C>0 выполненным.
[math]\tau_{n+1}=\frac{(DB^{-1}Az_n,z_n)}{(DB^{-1}Aw_n,B^{-1}Aw_n)}[/math]
Где
[math]v_n=B^{-1}(Ay_n-f)[/math]
- поправка,
[math]r_n=(Ay_n-f)[/math]
-невязка на n-ой итерации.
Значит
[math]
\begin{equation}
\tau_{n+1}=\frac{(Dv_n,z_n)}{(Dv_n,v_n)}
\end{equation}
[/math]