Участник:Коростелец: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 3 промежуточные версии этого же участника)
Строка 20: Строка 20:
 
===Математическое описание алгоритма===     
 
===Математическое описание алгоритма===     
 
      
 
      
    В описанном методе невырожденная матрица B не зависит от номера итерации n, решение y системы и последовательные приближения y_n - элементы линейного пространства H размерности m, в котором определены скалярное произведение и норма   
+
В описанном методе невырожденная матрица B не зависит от номера итерации n, решение y системы и последовательные приближения y_n - элементы линейного пространства H размерности m, в котором определены скалярное произведение и норма   
 
<math>||y||=\sqrt{(y,y)}</math>  
 
<math>||y||=\sqrt{(y,y)}</math>  
 
      
 
      
    Можно выразить
+
Можно выразить
 
<math>
 
<math>
 
      
 
      
Строка 31: Строка 31:
 
</math>
 
</math>
  
    Тогда для нахождения  
+
Тогда для нахождения  
 
<math>y_{n+1}</math>
 
<math>y_{n+1}</math>
необходимо определить  
+
необходимо определить  
 
<math>\tau_{n+1}</math>   
 
<math>\tau_{n+1}</math>   
 
      
 
      
    Пусть  
+
Пусть  
 
<math>z_n=y_n-y</math>
 
<math>z_n=y_n-y</math>
- погрешность на n-ой итерации. Выразив  
+
- погрешность на n-ой итерации. Выразив  
 
<math>y_{n+1}</math>  
 
<math>y_{n+1}</math>  
 
и  
 
и  
 
<math>y_n</math>  
 
<math>y_n</math>  
 +
 
через погрешность, можно получить
 
через погрешность, можно получить
 
      
 
      
    <math>B\frac{z_{n+1}+y-z_n-y}{\tau_{n+1}}+Ay_n=f
+
<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>
+
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>
+
<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 - произвольная матрица, удовлетворяющая условиям  
+
Пусть D - произвольная матрица, удовлетворяющая условиям  
 
      
 
      
    <math>D^T=D>0.</math>
+
<math>D^T=D>0.</math>
Выбор итерационных параметров
+
Выбор итерационных параметров
<math>\tau_{n+1}</math>
+
<math>\tau_{n+1}</math>
можно сделать на основе минимизации энергитической нормы
+
можно сделать на основе минимизации энергитической нормы
<math>||z_{n+1}||_D.</math>  
+
<math>||z_{n+1}||_D.</math>  
 
Такой способ построения итерационного процесса называется локальной минимизацией.
 
Такой способ построения итерационного процесса называется локальной минимизацией.
 
      
 
      
    Обозначив
+
Обозначив
    <math>
+
<math>
 
     \begin{equation}
 
     \begin{equation}
 
         w_{n+1}=D^{1/2}z_{n+1}
 
         w_{n+1}=D^{1/2}z_{n+1}
 
     \end{equation}     
 
     \end{equation}     
    </math>
+
</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=\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>||z_{n+1}||_D</math>  
 
эквивалентна минимизации  
 
эквивалентна минимизации  
 
<math>||w_{n+1}||</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=
+
<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=</math>
 
      
 
      
    =(E-\tau_{n+1}D^{-1/2}B^{-1}AD^{1/2})w_n=(E-\tau_{n+1}C)w_n</math>,
+
<math>=(E-\tau_{n+1}D^{-1/2}B^{-1}AD^{1/2})w_n=(E-\tau_{n+1}C)w_n</math>,
 
      
 
      
    где
+
где
    <math>
+
<math>
 
     \begin{equation}
 
     \begin{equation}
 
         C=D^{-1/2}B^{-1}AD^{1/2}
 
         C=D^{-1/2}B^{-1}AD^{1/2}
Строка 91: Строка 92:
  
 
      
 
      
    - невырожденная матрица.
+
- невырожденная матрица.
 
      
 
      
    Пусть  
+
Пусть  
 
<math>w_0\neq 0,</math>  
 
<math>w_0\neq 0,</math>  
 
иначе на n-ой итерации найдено точное решение, тогда  
 
иначе на n-ой итерации найдено точное решение, тогда  
 
   
 
   
    <math>||w_{n+1}||^2=((E-\tau_{n+1}C)w_n,(E-\tau_{n+1}C)w_n)=
+
<math>||w_{n+1}||^2=((E-\tau_{n+1}C)w_n,(E-\tau_{n+1}C)w_n)=</math>
    =||w_n||^2+\tau_{n+1}^2(Cw_n,Cw_n)-2\tau_{n+1}(Cw_n,w_n)=
+
<math>=||w_n||^2+\tau_{n+1}^2(Cw_n,Cw_n)-2\tau_{n+1}(Cw_n,w_n)=</math> 
    =||w_n||^2+(Cw_n,Cw_n)(\tau_{n+1}^2-2\tau_{n+1}\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)})=
+
<math>=||w_n||^2+(Cw_n,Cw_n)(\tau_{n+1}^2-2\tau_{n+1}\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)})=</math> 
    =||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||^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>||w_{n+1}||</math>
достигается при  
+
достигается при  
 
      
 
      
    <math>\tau_{n+1}=\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)},</math>
+
<math>\tau_{n+1}=\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)},</math>
где
+
где
<math>\tau_{n+1}>0,</math>  
+
<math>\tau_{n+1}>0,</math>  
 
если C>0
 
если C>0
 
      
 
      
    В дальнейшем предполагаем условие 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>\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>v_n=B^{-1}(Ay_n-f)</math>
- поправка,  
+
- поправка,  
 
<math>r_n=(Ay_n-f)</math>
 
<math>r_n=(Ay_n-f)</math>
-невязка на n-ой итерации.
+
-невязка на n-ой итерации.
 
      
 
      
    Значит
+
Значит
    <math>
+
<math>
 
     \begin{equation}
 
     \begin{equation}
 
         \tau_{n+1}=\frac{(Dv_n,z_n)}{(Dv_n,v_n)}
 
         \tau_{n+1}=\frac{(Dv_n,z_n)}{(Dv_n,v_n)}
Строка 134: Строка 135:
  
 
==Литература==
 
==Литература==
 +
Абакумов М.В., Гулин А.В. Лекции по численным методам математической физики: Учеб. пособие. - М.:ИНФРА-М,2013

Текущая версия на 04:47, 24 октября 2017

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=[/math]

[math]=(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)=[/math] [math]=||w_n||^2+\tau_{n+1}^2(Cw_n,Cw_n)-2\tau_{n+1}(Cw_n,w_n)=[/math] [math]=||w_n||^2+(Cw_n,Cw_n)(\tau_{n+1}^2-2\tau_{n+1}\frac{(Cw_n,w_n)}{(Cw_n,Cw_n)})=[/math] [math]=||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]

2 Программная реализация алгоритма

3 Литература

Абакумов М.В., Гулин А.В. Лекции по численным методам математической физики: Учеб. пособие. - М.:ИНФРА-М,2013