%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}