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