Участник:Коростелец

Свойства и структура алгоритма

Общее описание алгоритма

Будем рассматривать систему линейных алгебраических уравнений

[math]\displaystyle{ Ay=f }[/math]

где А - квадратная невырожденная матрица порядка m, у - искомый вектор размерности m, f - заданный вектор той же размерности

Рассмотрим нестационарный одношаговый итерационный метод решения такой системы вида

[math]\displaystyle{ B \frac{y_{n+1}-y_n}{\tau_{n+1}}+Ay_n=f; n=0,1,...; y_0\in H, }[/math]

а так же аналогичный двушаговый метод

[math]\displaystyle{ 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] Целью алгоритма является решение такой системы.

Математическое описание алгоритма

   В описанном методе невырожденная матрица B не зависит от номера итерации n, решение y системы и последовательные приближения y_n - элементы линейного пространства H размерности m, в котором определены скалярное произведение и норма  

[math]\displaystyle{ ||y||=\sqrt{(y,y)} }[/math]

   Можно выразить

[math]\displaystyle{ \begin{equation} y_{n+1}=y_n -\tau_{n+1}B^{-1}(Ay_n-f) \end{equation} }[/math]

   Тогда для нахождения 

[math]\displaystyle{ y_{n+1} }[/math]

необходимо определить 

[math]\displaystyle{ \tau_{n+1} }[/math]

   Пусть 

[math]\displaystyle{ z_n=y_n-y }[/math]

- погрешность на n-ой итерации. Выразив 

[math]\displaystyle{ y_{n+1} }[/math] и [math]\displaystyle{ y_n }[/math] через погрешность, можно получить

   [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ D^T=D\gt 0. }[/math]
Выбор итерационных параметров
[math]\displaystyle{ \tau_{n+1} }[/math]
можно сделать на основе минимизации энергитической нормы
[math]\displaystyle{ ||z_{n+1}||_D. }[/math] 

Такой способ построения итерационного процесса называется локальной минимизацией.

   Обозначив
   [math]\displaystyle{ 
    \begin{equation}
        w_{n+1}=D^{1/2}z_{n+1}
    \end{equation}     
     }[/math]
   получим
   
   [math]\displaystyle{ ||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]\displaystyle{ ||z_{n+1}||_D }[/math] эквивалентна минимизации [math]\displaystyle{ ||w_{n+1}|| }[/math]

   Выразим
   
   [math]\displaystyle{ 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]\displaystyle{ 
    \begin{equation}
        C=D^{-1/2}B^{-1}AD^{1/2}
    \end{equation}
 }[/math]

   - невырожденная матрица.
   
   Пусть 

[math]\displaystyle{ w_0\neq 0, }[/math] иначе на n-ой итерации найдено точное решение, тогда

   [math]\displaystyle{ ||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]\displaystyle{ ||w_{n+1}|| }[/math]
достигается при 
   
   [math]\displaystyle{ \tau_{n+1}=\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)}, }[/math]
где
[math]\displaystyle{ \tau_{n+1}\gt 0, }[/math] 

если C>0

   В дальнейшем предполагаем условие C>0 выполненным.
   
   [math]\displaystyle{ \tau_{n+1}=\frac{(DB^{-1}Az_n,z_n)}{(DB^{-1}Aw_n,B^{-1}Aw_n)} }[/math]
   
   Где 

[math]\displaystyle{ v_n=B^{-1}(Ay_n-f) }[/math]

- поправка, 

[math]\displaystyle{ r_n=(Ay_n-f) }[/math]

-невязка на n-ой итерации.
   
   Значит
   [math]\displaystyle{ 
    \begin{equation}
        \tau_{n+1}=\frac{(Dv_n,z_n)}{(Dv_n,v_n)}
    \end{equation}

 }[/math]