% Lection 6 by wictor
\myAddDate{02}{03}{09}

\begin{myTheorem}[об оценке скорости сходимости ПТИМ]
	Пусть $ A = A^* > 0, \quad \exists \delta, \Delta > 0 \text{, т.ч.}$
    \begin{equation}
    \label{eq_1_8_3}
		A \geq \delta E, \quad R_2^* R_2 \leq \frac{\Delta}{4} A.
	\end{equation}
	Пусть
    \begin{equation}
    \label{eq_1_8_4}
		\omega = \frac{2}{\sqrt{\delta \Delta}}, \quad \tau = \frac{2}{\gamma_1 +
		\gamma _2}, 
	\end{equation}
	где
	
    \begin{equation}
    \label{eq_1_8_5}
		\gamma_1 = \frac{\sqrt{\delta}(\sqrt{\delta\Delta})}{2(\sqrt{\delta} +
		\sqrt{\Delta})}, \quad \gamma_2 = \frac{\sqrt{\delta \Delta}}{4}.
	\end{equation}
	
	Тогда итерационный метод \eqref{eq_1_8_2} решения \eqref{eq_1_8_1} сходится и
	имеет место оценка
    \begin{equation}
    \label{eq_1_8_6}
		\| x^{n+1} - x \|_B \leq \rho \| x^n - x\|_B,
	\end{equation}
	где 
    \begin{equation}
    \label{eq_1_8_7}
		\rho = \frac{1-\sqrt{\eta}}{1+3 \sqrt{\eta}}, \quad \eta =
		\frac{\delta}{\Delta},
	\end{equation}
	
	$$ B = (E + \omega R_2^*)(E + \omega R_2). $$
\end{myTheorem}

\begin{proof}
	Докажем, что $\delta \leq \Delta$.
	
	Из условия \eqref{eq_1_8_3} следует, что $ \forall x \in H:\: x\neq 0$ имеем
	$$ (Ax, x) \geq \delta \| x \|^2, $$
	$$ \| R_2 x \|^2 = (R_2 x, R_2 x) = (R_2^* R_2 x, x) \leq \frac{\Delta}{4}(Ax,
	x) $$
	
	Поскольку $A = R_1 + R_2,\, R_1 = R_2^*,$ то
	$$ (Ax, x) = (R_2^* x, x) + (R_2 x, x) = 2(R_2 x, x). $$
	
	Таким образом,
	$$ \delta \|x\|^2 \leq (Ax, x) = \frac{(Ax, x)^2}{(Ax, x)} = \frac{4(R_2 x,
	x)^2}{(Ax, x)}.$$ Из неравенства Коши-Буняковского: $$ \delta \|x\|^2 \leq
	\frac{4 \|R_2 x \|^2 \cdot \| x \|^2}{(Ax, x)} \leq 4 \frac{\Delta}{4} \|x\|^
2 = \Delta \|x \|^2	$$
	
	Сократив на $\|x\|^2$, получим $\delta \leq \Delta$.
	
	В соответствии со следствием 1 параграфа 7, подберем коэффициенты $\gamma_1$ и
	$\gamma_2$ так, чтобы выполнялось $\gamma_1 B \leq A \leq \gamma_2 B$. 
	
	Из доказательства теоремы 1 данного параграфа $B \geq 2 \omega A$. Таким
	образом, $A \leq \frac{1}{2 \omega}B, \: \gamma_2 (\omega) = \frac{1}{2
	\omega}.$
	
	$$B = E + \omega A + \omega^2 R_2 R^*_2 \leq \frac{1}{\delta}A + \omega A +
	\omega^2 \frac{\delta}{4}A = (\frac{1}{\delta} + \omega + \omega^2
	\frac{\delta}{4})A, $$
	$$ \gamma_1 (\omega) =  (\frac{1}{\delta} + \omega + \omega^2
	\frac{\delta}{4})^{-1}. $$
	
	Таким образом, из следствия 1 параграфа 7 получаем, что для ПТИМ имеет место
	$\rho$-оценка \eqref{eq_1_8_6}, где $\rho (\omega) = \frac{1-\xi (\omega)}{1+\xi (\omega)},
	\, \xi (\omega) = \frac{\gamma_1 (\omega)}{\gamma_2 (\omega)}$.
	
	Минимизируем $\rho(\omega)$. Для этого минимизируем $ f(\omega) =
	\frac{\gamma_2 (\omega)}{\gamma_1 (\omega)}$.
	$$ f'(\omega) = \frac{1}{2}\left( \frac{\Delta}{4} - \frac{1}{\delta \omega^2}
	\right), $$
	$$ f'(\omega)=0 \text{ при } \omega = \omega_0 = \frac{2}{\sqrt{\delta
	\Delta}}. $$
	
	Поскольку $f''(\omega_0) > 0,$ то при $\omega = \omega_0$ достигается минимум
	$f(\omega)$, следовательно, на $\omega_0$ достигается минимум и $\rho (\omega)$ 
	
	Подставив полученное значение $\omega_0$ в выражения для $\gamma_1 (\omega)$,
	$\gamma_2 (\omega)$ и $\rho(\omega)$, получим \eqref{eq_1_8_5}
	и \eqref{eq_1_8_7}.
	
\end{proof}
	
	Напомним, что число итераций, необходимое для достижения точности $\epsilon$,
	можно вычислить по формуле:
	$$ n_0(\epsilon) = \left[ \frac{\ln {\frac{\displaystyle 1}{\displaystyle
	\epsilon}} }{\ln{\frac{\displaystyle 1}{\displaystyle \rho}}} \right]. $$
	
	Величина $\ln{\frac{1}{\rho}}$ называется скоростью сходимости итерационного
	метода.
	
	Сравним ПТИМ и метод простой итерации (ПИ) по скорости сходимости.
	
	Напомним, что метод ПИ имеет вид:
	$$ \frac{x^{n+1} - x^n}{\tau} + Ax^n = f, $$
	$$ \tau > 0,\quad n = 0,1,\ldots,\quad x^0 \text{ -- задано.} $$ 

	В реальных задачах $\eta = O(m^{-2}).$ В соответствии с этим, оценим скорость
	сходимости ПТИМ:
	$$ \ln{\frac{1}{\rho}} = \frac{1 + 3 \sqrt{\eta}}{1 - \sqrt{\eta}} =
	\Theta(\sqrt(\eta)) \: \Rightarrow \: n_0(\epsilon) = \Theta(m) $$
	
	Теперь оценим скорость сходимости ПИ:
	$$ \ln{\frac{1}{\rho}} = \ln{\frac{1 + \xi}{1 - \xi}} =
	\ln{\frac{(1+\xi)^2}{1 - \xi^2}} \cong \ln(1 + 2 \xi) \cong \ln(1 + 2 \eta)
	\cong \eta \Rightarrow n_0(\epsilon) = \Theta(m^2). $$
	
	Таким образом, ПТИМ сходится на порядок быстрее ПИ.
	
\section{Методы решения задач на собственные значения}
	Пусть матрица $A$ имеет размерность $m \times m$. Рассмотрим задачу на
	собственные значения матрицы $A$:
	\begin{equation}
    \label{eq_1_9_1}
    Ax = \lambda x, \quad x \neq 0. 
    \end{equation}
	Если число $\lambda$ и вектор $x$ удовлетворяют \eqref{eq_1_9_1}, то $\lambda$
	называется собственным значением матрицы (оператора) $A$, а $x$ называется
	собственным вектором матрицы (оператора) $A$.
	
	Для нахождения собственных значений $A$ нужно решить уравнение $$ f(\lambda) 
= |A - \lambda E| = 0.	$$ При этом, $f(\lambda)$ -- многочлен степени $m$. При
$m \geq 5$ данная задача аналитически не разрешима в общем случае.
	
	Заметим, что в общем случае $ \lambda \in \mathbb{C} $, даже если $A \in
	\mathbb{R}^{m \times m}$
	
	Различают две проблемы собственных значений:
	\begin{enumerate}
          \item \emph{Частичная проблема собственных значений.} Требуется найти
          некоторое подмножество спектра матрицы A (как правило, минимальное и
          максимальное по модулю собственные значения).
          \item \emph{Полная проблема собственных значений.} Требуется найти
          весь спектр матрицы A.
    \end{enumerate}
    
    Для простоты будем рассматривать только собственные вектора, имеющие норму
    $1$: $\|x\| = 1$.
    
    \subsection{Степенной метод решения частичной проблемы собственных значений}
    	
    	Этот метод имеет вид
		\begin{equation}
	    \label{eq_1_9_2}
		    x_{n+1} = A x_n, 
	    \end{equation}
		$$ n = 0,1,\ldots,\quad x_0 \text{ -- задано.} $$
		
		Пусть собственные значения $\lambda_1, \ldots, \lambda_m$ матрицы $A$
		пронумерованы так, что $ |\lambda_1| \leq |\lambda_2| \leq \ldots \leq
		|\lambda_m|$.
		
		Для доказательства сходимости данного метода потребуем выполнение следующих
		условий:
		\begin{description}
        \item [A)] Существует базис $\{e_k\}_{k=1}^m$ из собственных
        векторов $A: \: Ae_k = \lambda_k e_k,\, k = 1,\ldots, m.$ 
        \item [B)] $ \left| \frac{\lambda_{m-1}}{\lambda_m} \right| < 1.$
        
        \item [C)] При разложении начального приближения по
        базису $\{e_k\}: \: x_0 = c_1 e_1 + c_2 e_2 + \ldots + c_m e_m$
        выполнено $c_m \neq 0$. 
        \end{description}
		
		Запишем $x_n$:
		$$ x_n = c_1 \lambda_1^n e_1 + c_2 \lambda_2^n e_2 + \ldots + c_m \lambda_m^n e_m,$$
		$$ \frac{x_n}{\lambda_m^n} = c_1 \left( \frac{\lambda_1}{\lambda_m} \right)^n
		e_1 + c_2 \left( \frac{\lambda_2}{\lambda_m} \right)^n e_2 + \ldots + c_m
		e_m. $$
		
		Таким образом,  при $n
		\rightarrow \infty$ $x_n$ стремится по направлению к собственному вектору,
		отвечающему максимальному по модулю собственному значению.

		