% 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$ стремится по направлению к собственному вектору, отвечающему максимальному по модулю собственному значению.