\myAddDate{20}{02}{09}


\section{Теоремы о сходимости итерационных методов}

Рассмотрим матричное уравнение вида
\begin{equation}
    \label{eq_1_6_1}
    Ax=f,
\end{equation}
    где \(A\) --- матрица размера \( (m\times m) \),     \( |A|\neq 0 \) 

Рассмотрим также матричное уравнение вида
\begin{equation}
    \label{eq_1_6_2}
    B\frac{ x^{n+1}-x^n }{\tau}+Ax^n=f,
\end{equation}

где \(n=0,1,2,\ldots, ~ \exists B^{-1}\), и задан вектор начального приближения
\(x^0\)

Рассмотрим линейное пространство H, такое что \(\dim H = m\)

Возьмем 2 произвольных вектора x и y из этого пространства:
    \[x \in H, x=(x_1,x_2,\ldots,x_m)^T \] 
    \[y \in H, y=(y_1,y_2,\ldots,y_m)^T \]

Введем скалярное произведение векторов \((x,y)\) по формуле:
    \[(x,y)=\sum_{i=1}^m x_i y_i\]

Введем норму вектора x:
    \[||x||=(x,x)^\frac{1}{2}\]

\begin{myUnnumberedNote}
    Есть ``слабые нормы'', которые обладают не поточечной близостью. Решения
    систем стараются брать в сильной норме, входные данные - в слабой, чтобы максимально
расширить область применения метода.
\end{myUnnumberedNote}

Рассмотрим самосопряженный оператор \(D=D^*>0\)

\begin{myUnnumberedDefinition}
    Будем говорить о скалярном произведении векторов x и y ``в смысле D'', если
    \((x,y)_D = (Dx,y)\)
\end{myUnnumberedDefinition}

Это позволяет нам ввести энергетическеую норму:
\begin{myUnnumberedDefinition}
    Энергетическая норма - норма, которая задается соотношением:
    \[||x||_D=(Dx,x)^\frac{1}{2}\]
\end{myUnnumberedDefinition}


Вспомним некоторые свойства самосопряженного положительно определенного
оператора D, известные из теории операторов:
\begin{enumerate}
  \item \(\exists D^{-1}=(D^{-1})^* > 0\)
  \item \(\exists D^{\frac{1}{2}}  = (D^{\frac{1}{2}})^* > 0\)
  \item \(\exists D^{-\frac{1}{2}} = (D^{-\frac{1}{2}})^* > 0\)  
\end{enumerate}

из этих свойств следует, что существует такое  \(\delta>0:\)
\[(Dx,x)\geq\delta||x||^2\]

В дальнейшем нам потребуется понятие положительной или неотрицательной определенности оператора.

\begin{myUnnumberedDefinition}
    \[C>0 \Leftrightarrow (Cx,x)>0, \quad \forall x \neq 0 \]
    \[C \geq 0 \Leftrightarrow (Cx,x)\geq 0, \quad \forall x \in H \]
\end{myUnnumberedDefinition}

\begin{myUnnumberedTask}
Дано: Оператор \(C>0\), \(H\) - вещественное линейное пространство с заданным
скалярным произведением.
Доказать, что: \[(Cx,x) = (\frac{C+C^*}{2}x,x)\]

\end{myUnnumberedTask}
\begin{proof}
Для решения задачи воспользуемся следующими равенстввами, верными для вещественного простаранства \(H\):
\[ (C^*x,x) = (x,Cx) = (Cx,x), \quad \forall x \in H\]

Представим оператор \(C\) в виде суммы: \( C = \frac{C+C^*}{2} + \frac{C-C^*}{2} \).
Тогда:
\[ (Cx,x) =  
(\frac{C+C^*}{2}x,x) + 
(\frac{C-C^*}{2}x,x) =  \]
\[(\frac{C+C^*}{2}x,x) + 
\frac{1}{2}\Bigl( 
	\underbrace{(C^*x,x)-(Cx,x)}_{=0} 
\Bigr) = 
(\frac{C+C^*}{2}x,x), \quad \forall x \in H\] 
\end{proof}

\begin{myUnnumberedDefinition}
    Погрешность итерационного метода
    \begin{equation}
        \label{eq_1_6_4}
        V^{n}=x^{n}-x
    \end{equation}
\end{myUnnumberedDefinition}

\begin{myUnnumberedDefinition}
    Метод \eqref{eq_1_6_2} сходится, если
    \[||V^{n}||\rightarrow 0 (n \rightarrow \infty) \] 
\end{myUnnumberedDefinition}

Из определения погрешности ясно, что решению матричного уравнения
\eqref{eq_1_6_2} на n-ой итерации соответствует вектор
    \[ x^{n}=V^{n}+x, \]
    где \(x\) -- точное решение системы.

Используя это соотношение, перепишем уравнение \eqref{eq_1_6_2} через вектор
погрешности:
\begin{equation}
    \label{eq_1_6_5}
     B\frac{V^{n+1}-V^{n}}{\tau} + AV^{n} = 0, 
\end{equation}
   где \(n=0,1,2,\ldots\)\\
   
  Умножим уравнение \eqref{eq_1_6_5} на \(B^{-1}\) слева:
\[ \frac{V^{n+1}-V^n}{\tau} + B^{-1}AV^n =0 \]  

  Следовательно,
  \[V^{n+1} = 
   V^n-\tau B^{-1}AV^n = 
   (E-\tau B^{-1}A)V^n =
   SV^n\]
   
  Таким образом, получим матрицу S:
  \begin{equation}
    \label{eq_1_6_6}
    S = E-\tau B^{-1}A
  \end{equation}  

\begin{myUnnumberedDefinition}
    S называется матрицей перехода от n-й итерации к (n+1)-й
\end{myUnnumberedDefinition}


\begin{myTheorem}[о сходимости итерационных методов]
       Итерационный метод \eqref{eq_1_6_2} решения задачи \eqref{eq_1_6_1} сходится при
       любом начальном приближении тогда и только тогда, когда все собственные
       значения матрицы \(S\) по модулю меньше единицы.
\end{myTheorem}

\begin{myUnnumberedNote}
    Эта теорема хороша, но редко применима, т.к. в большинстве случаев искать
    собственные значения трудно.
\end{myUnnumberedNote}

\begin{myUnnumberedNote}
    Далее всюду будем рассматривать только вещественные простарнства.
\end{myUnnumberedNote}


%\begin{myUnnumberedTask}
%    Доказать, что если C>0, то существует такое \(\delta>0\), что:
%    \[(Cx,x) \geq \delta||x||^2, \forall x \in H\]
%\end{myUnnumberedTask}


\begin{myTheorem}[Самарского]
    Пусть оператор \(A=A^*>0 ~ (A^*=A^T)\)\\
    Пусть выполнено неравенство 
    \begin{equation}
        \label{eq_1_6_7}
        B-0,5\tau A>0, ~ (\tau>0)
    \end{equation}

    Тогда итерационный метод \eqref{eq_1_6_2} решения системы \eqref{eq_1_6_1} сходится в
    среднеквадратичной норме при любом начальном приближении, то есть
    \[
        ||x^n-x|| = \left( \sum_{i=1}^m(x_i^n-x_i) \right)^{\frac{1}{2}}
        \rightarrow 0, n\rightarrow \infty 
     \]
\end{myTheorem}
\begin{proof}
    
    Введем \(y_n = (AV^n,V^n)\) \newline
    Рассмотрим \(y_{n+1}\): \newline
    \[  y_{n+1} = 
        (AV^{n+1},V^{n+1}) =
        (ASV^n,SV^n) = 
    \]
    
    \[    
        =(A(E - \tau B^{-1}A)V^n, (E-\tau B^{-1}A)V^n) = 
        ((A-\tau AB^{-1}A)V^n, (E-\tau B^{-1}A)V^n) =
    \]
    
    \[    
        =(AV^n, V^n)-\tau\left[ (AB^{-1}AV^n, V^n) +
                          (AV^n, B^{-1}AV^n) -
                          \tau(AB^{-1}AV^n, B^{-1}AV^n)
                        \right] =
    \] 
    
    если учесть, что
     \(   \left\{ (AB^{-1}AV^n, V^n) = (B^{-1}AV^n,A^*V^n) =
         (AV^n,B^{-1}AV^n) \right\}
    \), получим
    
    \[ = y_n - \tau\left[2(AV^n,B^{-1}AV^n)-\tau(AB^{-1}AV^n,B^{-1}AV^n)\right]
    =
    \]
    
    
    
    \[
        = y^n + 2\tau\left( (B-\frac{\tau}{2}A)B^{-1}AV^n,B^{-1}AV^n \right)
    \]
    
    Итак:
    \[
        \frac{y^{n+1}-y^n}{\tau}+2\left((\underbrace{B-0,5\tau
        A}_{>0 ~ \mbox{по условию}})B^{-1}AV^n, B^{-1}AV^n \right) = 0
    \]
    
    Следовательно, и все скалярное произведение больше либо равно нулю. А
    стало быть,
    \[
        y^{n+1} \leq y^{n},
    \]
    
    и последовательность \(\{y^n\}\) не возрастает и имеет предел.
    
    Воспользуемся свойством положительно определенного оператора: если оператор
    C >0, то \(\exists \delta > 0: (Cx,x) \geq \delta ||x||^2, \forall x \in H\)
    
    Из этого свойства следует неравенство:
    \[
        \left( (B-0,5\tau A)B^{-1}AV^n, B^{-1}AV^n \right) \geq \delta ||
        B^{-1}AV^n ||^2,
    \]
    где \(\delta >0\)
    
    \[
        \frac{y^{n+1}-y^n}{\tau} + 2\delta||B^{-1}AV^n||^2 \leq 0
    \]
    
    При \(n \rightarrow \infty\) получим \[\lim_{n\rightarrow
    \infty}||B^{-1}AV^n|| =0 \]
    
    Введем \(W^n = B^{-1}AV^n \). Отсюда \[V^n=A^{-1}BW^n\]
    
    Оценим норму погрешности:
    \[
        ||V^n|| \leq ||A^{-1}B||*||W^n||
    \]
    
    В силу независимости \(A^{-1}B\) от n и стремлению к нулю нормы \(||W^n||\)
    при \(n \rightarrow \infty \) получим, что
    \[
        \lim_{n \rightarrow \infty} ||V^n|| = 0
    \]
    
    Так как мы нигде не использовали начальное приближение \(x^0\), то
    формулировка теоремы остается верной для любого начального приближения
    \(x^0\)
\end{proof}

\begin{myCorollary}
 Пусть \(A=A^* > 0\).
 (Напомним, что \(A=R_1+D+R_2\), где \(R_1 \mbox{ и } R_2\) - нижнетреугльная и
 верхнетреугольная матрицы, а \(D=diag(a_{11},a_{22},\ldots,a_{mm})\) )
 
 Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном
 приближении \(x^0\), если \(2D > A\).
\end{myCorollary}
\begin{proof}
 \[ D(x^{n+1} - x^n) + Ax^n = f \]
 
 т.е. B=D, \(\tau=1\)
 
 По условию:
 \( 2D > A \Rightarrow D-0,5A > 0 \Rightarrow\) выполнено условие теоремы, а
 значит метод сходится.
 
\end{proof}
 
\begin{myCorollary}
Пусть \[A=A^*>0\] 
\begin{equation}
    \label{eq_1_6_8}
    a_{ii} > \sum_{j=1, j\neq i}^{m}|a_{ij}|, i=\overline{1,m}
\end{equation}


Тогда метод Якоби сходится при любом начальном приближении \(x_0\)
\end{myCorollary}
\begin{proof}

Возьмем произвольный вектор x, и распишем для него скалярное  произведение
\( (Ax,x) \), используя известное неравенство \(ab \leq \frac{a^2+b^2}{2}\):

\[ (Ax,x) = \sum_{i,j=1}^{m}a_{ij}x_{i}x_{j} \leq
\sum_{i,j=1}^{m}|a_{ij}|*|x_{i}|*|x_{j}| \leq \]

\[ \frac{1}{2}\sum_{i,j=1}^{m}|a_{ij}|x_{i}^{2} +
\frac{1}{2}\sum_{i,j=1}^{m}|a_{ij}|x_{j}^{2} = \]

\[ = \frac{1}{2}\sum_{i,j=1}^{m}|a_{ij}|x_{i}^{2} +
\frac{1}{2}\sum_{i,j=1}^{m}|a_{ji}|x_{i}^{2} = \]

\[ = \left\{ a_{ij}=a_{ji} \right\} = \]

\[ \sum_{i,j=1}^{m}|a_{ij}|x^2_i = \sum_{i=1}^{m}x_i^2(a_{ii} +
\sum_{j=1,j\neq i}^{m}|a_{ij}| )
\]

Воспользуемся свойством диагонального преобладания \eqref{eq_1_6_8}

\[(Ax,x) < 2\sum_{i=1}^{m}a_{ii}x_i^2 = (2Dx,x) \Rightarrow 2D>A\]
а значит, по следствию 1 метод Якоби сходится при любом \(x_0\)

\end{proof}

\begin{myCorollary}
    Пусть \[A=A^*>0\]
    Тогда метод Зейделя сходится при любом начальном приближении \(x^0\)
\end{myCorollary}
\begin{proof}
По определению метода Зейделя имеем:  
\[ B=R_1+D, \tau=1 \]

Для доказательства утверждения, в силу теоремы Самарского, достаточно доказать,
что \[ B-0,5A > 0 \]
    
Поскольку \( A= R_1 + D + R_2\), то это соотношение преобразуется к следующему
виду:
 \[ 2(R_1+D) > R_1 + D + R_2 \]
 \[ R_1 + D - R_2 > 0 \]
    
    Следовательно,   
    \[ \left((R_1+D-R_2)x,x\right) > 0, ~ \forall x\neq0, x \in H\]    
    \[ (R_1x,x) + (Dx,x) - (R_2x,x) > 0 \Rightarrow (Dx,x) > 0\]
    
    Последнее следствие верно, так как \( A=A^* \), а значит  
    \[ R_1^* = R_2 \]
    \[ (R_1x,x) = (x, R_1^*x) = (x, R_2x) = (R_2x, x)\]
    
    Стало быть, для любого ненулевого вектора из \( H \) требуется выполнения
    неравенства \( (Dx,x) > 0 \). В силу самосопряженности оператора \( A \) 
    это соотношение выполняется, кроме того, все вышепривиденные переходы
    равносильны, а значит выполнено условие теоремы Самарского.
    \end{proof}
