%lection by wictor
\myAddDate{27}{02}{09}

\begin{myCorollary}
	Пусть $$ A^T = A > 0, $$
	$$ \gamma_2 = \max \lambda_k^A, $$
	$$ 0 < \tau < \frac{2}{\gamma_2}. $$
	Тогда метод простой итерации (релаксации) сходится.
\end{myCorollary}
\begin{proof}
	В нашем случае, $ B = E $ . Докажем, что $$ E - 0.5\tau A > 0, $$ тогда
	утверждение будет следовать из теоремы Самарского. Запишем цепочку неравенств:
	$$ \tau < \frac{2}{\gamma_2}, $$
	$$ 0,5\tau\gamma_2 < 1, $$
	что означает, что для любого $ \lambda_k^A $ -- собственного значения
	матрицы $ A $ -- выполнено
	$$ 0,5\tau \lambda_k^A < 1, $$ 
	$$ 1-0,5\tau \lambda_k^A > 0, $$
	то есть
	$$ E - 0.5\tau A > 0. $$
\end{proof}

\section{Оценка скорости сходимости итерационных методов}
	Рассмотрим СЛАУ
	\begin{equation}
    \label{eq_1_7_1}
    	Ax = f,
    \end{equation}
	где $ A $ -- матрица размера $ m\times m, \quad |A| \neq 0. $
	
	Запишем общий вид итерационного метода решения СЛАУ:
	\begin{equation}
    \label{eq_1_7_2}
    	B \frac{x^{n+1}-x^{n}}{\tau}+Ax^n=f,
    \end{equation}
	где \( B - \text{обратимая матрица}, \quad \tau > 0, \quad  x^0\text{ - задано}, \quad n = 0, 1,
	\ldots \)
	
	Введем обозначение: $$v^{n}=x^n-x.$$
	Тогда для $ v $ можно записать:
	\begin{equation}
    \label{eq_1_7_3}
	B \frac{v^{n+1}-v^{n}}{\tau}+Av^n=0
	\end{equation}

	Для оценки скорости сходимости итерационных методов мы будем стремиться
	для некоторого $\rho$ и некоторой нормы доказать т.н. $\rho$ - оценку:
	\begin{equation}
    \label{eq_1_7_4}
	\| v^{n+1} \| \leq \rho \| v^n \|,\quad 0< \rho <1.
	\end{equation}
	
	Тогда 
	$$ \| v^n \| \leq \rho^n \| v^0 \|, $$
	$$ n\rightarrow \infty \Rightarrow \| v^n \| \rightarrow 0. $$
	
	Пусть $H$ -- линейное пространство размерности $m.$ $\forall x,y \in H$
	определим: 
	$$ (x,y)=\sum \limits_{i=1}^{m}x_i y_i, $$
	$$ \|x \|=\sqrt{(x,x)}. $$
	Пусть $D = D^* > 0.$ Определим:
	$$(x, y)_D = (Dx, y),$$
	$$\| x \|_D = \sqrt{(x,x)_D} \text{ -- энергетическая норма вектора $x$}$$
	
	Найдем число итераций $n_0(\epsilon),$ необходимое для того, чтобы $\forall n >
	n_0(\epsilon)$ выполнялось:
	$$ \|x^n - x \| < \epsilon \|x^0 - x \|.$$
	Из \eqref{eq_1_7_4} следует, что $$ \|x^n - x \| \leq \rho^n\|x^0 - x \|. $$
	Потребуем, чтобы $\rho^n \leq \epsilon.$
	Тогда
	$$ \frac{1}{\epsilon} \leq {\left( \frac{1}{\rho} \right)}^n,  $$
	$$ n\ln{ \frac{1}{\rho} \geq \ln{\frac{1}{\epsilon}}}, $$
	$$ n_0(\epsilon) = \left[ \frac{ \ln{\frac{\displaystyle 1}{\displaystyle \epsilon} } }{
	\ln{\frac{\displaystyle 1}{\displaystyle \rho}} } \right]. $$
	Число $ \ln{\frac{\displaystyle 1}{\displaystyle \rho}} $ называется скоростью сходимости итерационного
	метода.
	
	Пусть $D = D^* > 0.$ Тогда $\exists \{ e_k \} $  --  ортонормированный
	базис (ОНБ) из собственных векторов $ D. $ Разложим вектор $x$ по этому базису:
	$$ x = \sum \limits_{k=1}^{m} c_k e_k .$$
	
	Для вектора $x$ имеет место равенство Парсеваля:
	$$ \|x\|^2 = \sum \limits_{k=1}^{m} c_k^2. $$
	
	\begin{myUnnumberedTheorem}
    	Пусть $A^* = A > 0,\, B^* = B > 0,$
    	$$ \exists \rho : \: 0<\rho<1,$$
    	\begin{equation}
    	\label{eq_1_7_5}
    		\frac{1-\rho}{\tau}B \leq A \leq \frac{1+\rho}{\tau}B.
    	\end{equation}
    	Тогда итерационный метод \eqref{eq_1_7_2} сходится к решению
    	\eqref{eq_1_7_1} и выполнена оценка
    	\begin{equation}
    	\label{eq_1_7_6}
    		\| v^{n+1} \|_B \leq \rho \| v^n \|_B.
    	\end{equation}
    \end{myUnnumberedTheorem}
	\begin{myUnnumberedNote}
    
    	Из того, что $A \leq \frac{1+\rho}{\tau}B$ и $ \rho < 1 $, следует, что 
    	$$ A < \frac{2}{\tau}B,$$
    	т.е.
    	$$ B - 0.5\tau A>0. $$
    	Таким образом, по теореме Самарского, сходимость имеет
    	место.
    \end{myUnnumberedNote}

	\begin{proof}[Доказательство теоремы]
    
    Из положительной определенности матрицы $B$ следует, что
    $$\exists B^{\frac{1}{2}} = (B^{\frac{1}{2}})^* > 0, $$
    $$\exists B^{-\frac{1}{2}} = (B^{-\frac{1}{2}})^* > 0. $$
    
    Домножим обе части \eqref{eq_1_7_3} слева на $B^{-\frac{1}{2}}$:
    $$ B^{\frac{1}{2}} \frac{v^{n+1}-v^{n}}{\tau}+B^{-\frac{1}{2}}Av^n=0. $$
    
    Обозначим $ B^{\frac{1}{2}}v^n = z^n.$
    
    Тогда
    
    \[  \frac{z^{n+1}-z^{n}}{\tau}+B^{-\frac{1}{2}}AB^{-\frac{1}{2}}z^n=0. \]
    
    Выразим $ z^{n+1} $ :
    
    \[ z^{n+1} = z^n - \tau B^{-\frac{1}{2}} A B^{-\frac{1}{2}} z^n. \]
    
    Обозначим 
	\begin{equation}
	\label{eq_1_7_7}
	    S = E - \tau B^{-\frac{1}{2}} A B^{-\frac{1}{2}}.
	 \end{equation}

    Тогда $ z^{n+1} = S z^n. $ Назовем матрицу $S$ матрицей перехода для $ z^n.
    $
    
    Докажем, что из того, что $$ \|z^{n+1}\| \leq \rho \|z^{n}\|, $$ следует,
    что
    $$ \| v^{n+1}\|_B \leq \rho \| v^{n}\|_B. $$ 
    Действительно, $$ \|z^{n}\|^2 = (z^n, z^n) = ( B^{\frac{1}{2}}v^n,
    B^{\frac{1}{2}} v^n) = (B v^n, v^n) =  \| v^{n}\|^2_B.$$
    Таким образом, осталось доказать, что 
	\begin{equation}
	\label{eq_1_7_8}
    	\|z^{n+1}\| \leq \rho \|z^{n}\|.
	\end{equation}
	
	Пусть $ s_k, k = 1, \ldots, m$ -- собственные значения матрицы $S$.
	Зафиксируем $k$, пусть $x$ -- собственный вектор, соответствующий собственному
	значению $s_k$:
	$$ Sx = s_k x \quad (x \neq 0). $$
	
	Заметим, что $$ B^{\frac{1}{2}}Sx = (B^{\frac{1}{2}} - \tau A
	B^{-\frac{1}{2}})x = s_k B^{\frac{1}{2}}x. $$
	
	Обозначим $y = B^{-\frac{1}{2}}x.$ Тогда предыдущее выражение можно переписать
	в виде:
	$$ (B - \tau A)y = s_k B y, $$
	$$ (1-s_k)By = \tau A y, $$
	$$ Ay = \frac{1-s_k}{\tau}By. $$
	
	Из условия \eqref{eq_1_7_5} теоремы следует, что
	$$ \frac{1-\rho}{\tau}(By, y) \leq (Ay, y) = \frac{1-s_k}{\tau}(By, y) \leq
	\frac{1+\rho}{\tau}(By,y). $$
	
	Поскольку $(By, y) > 0,$ то предыдущее неравенство влечёт
	$$ \frac{1-\rho}{\tau} \leq  \frac{1-s_k}{\tau} \leq
	\frac{1+\rho}{\tau}. $$
	
	Следовательно, $ |s_k| \leq \rho, \, k = 1, \ldots, m.$
	
	Поскольку все матрицы, входящие в правую часть выражения \eqref{eq_1_7_7},
	являются самосопряженными, то и матрица $S$ является самосопряженной.
	Следовательно, существует ортонормированный базис $ \{e_k\}_1^m,$ состоящий из
	собственных векторов матрицы $S$:
	$$ Se_k = s_k e_k, \, k = 1, \ldots, m. $$
	
	Разложим вектор $z^n$ по базису $\{e_k\}:$
	$$ z^n = \sum \limits_{k=1}^n c_k^{(n)} e_k. $$
	Тогда
	$$ z^{n+1} = Sz^n = \sum \limits_{k=1}^n c_k^{(n)} S e_k = \sum \limits_{k=1}^n
	c_k^{(n)} s_k e_k. $$
	
	Пользуясь равенством Парсеваля и полученной оценкой для $|s_k|,$ имеем:
	$$ \| z^{n+1} \|^2 = \sum \limits_{k=1}^n
	(c_k^{(n)})^2 s_k^2 \leq \rho^2 \sum \limits_{k=1}^n
	(c_k^{(n)})^2 = \rho^2 \| z^{n} \|^2. $$
	
	Мы доказали \eqref{eq_1_7_8} и \eqref{eq_1_7_6}.
	
    \end{proof}

    \begin{myCorollaryFromUnnumbered} 
    	Пусть $A^* = A > 0,\, B^* = B > 0,$
    	$ \exists \, 0<\gamma_1 < \gamma_2:$
    	\begin{equation}
		\label{eq_1_7_9}
    		\gamma_1 B \leq A \leq \gamma_2 B.
    	\end{equation}
		Тогда, если $\tau = \frac{2}{\gamma_1 + \gamma_2} = \tau_0,$ то
		$ \| v_{n+1} \|_B \leq \rho \| v_{n} \|_B,$ где $\rho = \frac{1-\xi}{1+\xi},
		\, \xi = \frac{\gamma_1}{\gamma_2}$.
    \end{myCorollaryFromUnnumbered}
	\begin{proof}
    	Найдем $\gamma_1$ и $\gamma_2$:
    	\[
    	\begin{cases}
        	\tau = \frac{2}{\gamma_1 + \gamma_2}, \\
        	\rho = \frac{1-\xi}{1+\xi};
        \end{cases}
		\Leftrightarrow
    	\begin{cases}
        	\gamma_1 + \gamma_2 = \frac{2}{\tau}, \\
        	\gamma_2 - \gamma_1 = \rho (\gamma_1 + \gamma_2);
        \end{cases}
		\Leftrightarrow
    	\begin{cases}
        	\gamma_1 + \gamma_2 = \frac{2}{\tau}, \\
        	\gamma_2 - \gamma_1 = \frac{2\rho}{\tau};
        \end{cases}				
		\Leftrightarrow
    	\begin{cases}
        	\gamma_1 = \frac{1-\rho}{\tau}, \\
        	\gamma_2  = \frac{1+\rho}{\tau}.
        \end{cases}
    	\]
    	Таким образом, мы находимся в условиях доказанной теоремы.
    \end{proof}
    
    \begin{myCorollaryFromUnnumbered}
    	Пусть $A^* = A > 0,\, B = E, \, $
    	$$ \gamma^k \text{ -- собственные значения матрицы A,} \, k = 1, \ldots ,
     m,	$$
     	$$ \gamma_1 = \min_{k = 1, \ldots , m} \gamma^k, \: \gamma_2 = \max_{k =
     	1, \ldots , m} \gamma^k. $$
     	Тогда итерационный метод имеет вид
     	$$ B \frac{x^{n+1}-x^{n}}{\tau}+Ax^n=f $$
     	и имеет место $\rho$-оценка
     	$$ \| v_{n+1} \| \leq \rho \| v_{n} \|\text{, где }\rho =
     	\frac{1-\xi}{1+\xi}, \, \xi = \frac{\gamma_1}{\gamma_2} $$.
		
    \end{myCorollaryFromUnnumbered}
    \begin{proof}
    	Утверждение данного следствия вытекает из утверждения предыдущего
    	следствия.
    \end{proof}

    \section{Исследование сходимости попеременно треугольного итерационного
    метода}
    Рассмотрим СЛАУ:
    \begin{equation}
    \label{eq_1_8_1}
     Ax=f, \, |A| \neq 0
	\end{equation}
	
	Запишем попеременно треугольный итерационный метод (ПТИМ):
    \begin{equation}
    \label{eq_1_8_2}
	(E + \omega R_1)(E + \omega R_2)\frac{x^{n+1} - x^n}{\tau} + Ax^n = f,
	\end{equation}
	$$ \omega > 0, \quad \tau > 0, \quad n = 0, 1, \ldots, \quad x^0 \text{
	задано,} $$
	
	$$ A = R_1 + R_2, $$
	
	$$ R_1 =  		\begin{pmatrix}
						  0,5 a_{11} & 0 & \cdots & 0 \\
						  a_{21} & 0,5 a_{22} & \cdots & 0 \\
						  \vdots  & \vdots  & \ddots & \vdots  \\
						  a_{m1} & a_{m2} & \cdots & 0,5 a_{mm}
					 \end{pmatrix} \text{ --- нижнетреугольная матрица,} 
	$$
	
	$$ R_2 = 
	 				\begin{pmatrix}
						  0,5a_{11} & a_{12} & \cdots & a_{1m} \\
						  0 & 0,5a_{22} & \cdots & a_{2m} \\
						  \vdots  & \vdots  & \ddots & \vdots  \\
						  0 & 0 & \cdots & 0,5a_{mm}
					 \end{pmatrix} \text{ --- верхнетреугольная матрица.}
	$$
	
	Обозначим
	$$ B = (E + \omega R_1)(E + \omega R_2). $$
	
	Это обозначение согласуется с обозначением для итерационного метода
	общего вида, рассматриваемого в предыдущих параграфах.
	
	\begin{myTheorem}
    	Пусть $A^* = A > 0,\, \omega > \frac{\tau}{4}.$ Тогда ПТИМ \eqref{eq_1_8_2}
    	сходится при любом начальном приближении $x^0$ в среднеквадратичной норме.
    \end{myTheorem}
	\begin{proof}
    	Распишем $B$:
    	\[
    		B = (E + \omega R_2^*)(E + \omega R_2) = E + \omega A + \omega ^2 R_2^*
    		R_2 = (E - \omega R_2^*)(E - \omega R_2) + 2 \omega A
    	\]
    	Обозначим $ C = E - \omega R_2. $ Тогда $ C^* = (E - \omega R_2^*), \: C^*
    	C > 0, \text{ т.к. } ( C^* C x, x) = (Cx, Cx) > 0 \text{ при } x \neq 0,$
    	$$ B - 0,5 \tau A > B - 2 \omega A = C^* C > 0. $$
    	Таким образом, по теореме Самарского, имеет место сходимость в
    	среднеквадратичной норме.
    \end{proof}
