%\documentstyle{report}
%\documentclass{report }

%\usepackage[cp866]{inputenc}
%\usepackage[cp1251]{inputenc}

%\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\documentclass[12pt,a4paper]{article}
%\usepackage[cp866]{inputenc}
\usepackage[cp1251]{inputenc}

\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\twocolumn
\oddsidemargin =-2cm
\topmargin -3cm
\textheight=27cm
\textwidth=17cm
\pagestyle{empty}
\begin{document}
{\footnotesize
Лекция 4. Метод Зейделя (пример неявного стационарного метода)

Систему $Ax=f$ в координатной форме
$$
\sum_{j=1}^na_{ij}x_j=f_ i,i=\overline{1,n}
$$
перепишем в форме
$$
x_i=\frac{1}{a_{ii}}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j-\sum_{j=i+1}^na_{ij}x_j)
$$
$i=\overline{1,n}$
и построим следующие итерационные процессы
а)
$$
\begin{array}{l}
x_1^{k+1}=\frac{1}{a_{11}}(f_1-\sum_{j=2}^na_{ij}x_j^k)\\
\\
x_i^{k+1}=\frac{1}{a_{ii}}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j^{k+1}-\sum_{j=i+1}^na_{ij}x_j^k)\\
\end{array}
$$
$i=\overline{2,n},k=0,1,2,\cdots$

б)
$$
\begin{array}{l}
x_n^{k+1}=\frac{1}{a_{nn}}(f_1-\sum_{j=1}^{n-1}a_{ij}x_j^k)\\
\\
x_i^{k+1}=\frac{1}{a_{ii}}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j^{k}-\sum_{j=i+1}^na_{ij}x_j^{k+1})\\
\end{array}
$$
$i={n-1,n-2,\cdots ,1},k=0,1,2,\cdots$

Место метода Зейделя среди множества всех итерационных методов
$$
B_k\frac{x^{k+1}-x^k}{\tau_k}+Ax^k=f, k=0,1,\cdots, x^0\in R_n
$$

Матрицу $A=A^-+A^++D$
$D=\{d_{ii}=a_{ii},d_{ij}=0,i\ne j, i,j=\overline{1,n}   \}$-диагональная,
$A^-=\{a^-_{ij}=0, j\ge i, a^-_{ij}=a_{ij},i,j=\overline{1,n}    \}$
-поддиагональная
$A^+=\{ a^+_{ij}=0, j\le i, a^-_{ij}=a_{ij},i,j=\overline{1,n}    \}$
-наддиагональная

и т.к.
$(Dx)_i=a_{ii}x_i,$ $(A^-x)_i=\sum_{j=1}^{i-1}a_{ij}x_j,$ $(A^+x)_i=\sum_{j=i+1}^{n}a_{ij}x_j,$
то схему а) запишем в виде
$$
Dx^{k+1}+A^-x^{k+1}+A^+x^k=f|\pm (A^-+D)x^k
$$
будем иметь
$$
(D+A^+) (x^{k+1}-x^k)+Ax^k=f , \tau_k=1, B_k=(D+A^+)
$$
т.е. метод Зейделя стационарный неявный метод, с матрицей $B_k$- треугольного вида

{\bf Достаточные условия сходимости метода Зейделя }
Пусть
$$
\sum_{j=1,j\ne i}^n |\frac{a_{ij}}{a_{ii}}|<1, i=\overline{1,n}
$$
тогда метод Зейделя сходится
Док-во сводится к доказательству
$$
\alpha(E-(D+A^+)^{-1}A)<1 ??
$$
Пусть $x^*$- точное решение $Ax=f$
$
\rho_k(x^{k+1},x^*)=\max_{1\le i \le n}|x_i^{k+1}-x_i^k|\{x_i^{k=1}
\mbox{из схемы
а)}, x^k \mbox{ и из} Ax^*= f \}=
$

$
\max_{1\le i\le n}|  \frac{1}{a_{ii}}
(f_i-\sum_{j=1}^{i-1}a_{ij}x_j^{k+1}-\sum_{j=i+1}^na_{ij}x_j^k)-
$

$
\frac{1}{a_{ii}}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j^{*}-\sum_{j=i+1}^na_{ij}x_j^*)|
$

$
\max_{1\le i\le n}|\sum_{j=1}^{i-1}\frac{a_{ij}}{a_{ii}}(x_j^{*}-x^{k+1})+
\sum_{j=i+1}^n\frac{a_{ij}}{a_{ii}}(x_j^*-x^k)|
$

$$
\underbrace {     \max_{1\le i\le n}
\sum_{j=1}^{i-1} | \frac{ a_{ij}} {a_{ii}} | }_{\mbox{ =$\alpha$ } }
\max_j|x_j^*-x_j^{k+1}|+
$$

$$
\underbrace{\max_{1\le i\le n}\sum_{j=i+1}^{n}|\frac{a_{ij}}{a_{ii}}|
}_{\mbox{=$\beta$}}\max_{j}|(x_j^{*}-x^{k}|=
$$
$$
\alpha \rho(x^{k+1},x^*)+\beta\rho(x^k,x^*) \to
$$
$$
\rho(x^{k+1},x^*)\le \frac{\beta}{1-\alpha}\rho(x^k,x^*)
$$
Покажем, что

$
\frac{\beta}{1-\alpha}<1
$

$
\frac{\beta}{1-\alpha}=\frac{(\alpha+\beta)(1-\alpha)-(\alpha+\beta)(1-\alpha)+\beta}{1-\alpha}=
$

$
\underbrace{\alpha+\beta}_{\mbox{<1, из условий устойчивости}} +\frac{\alpha(\alpha+\beta-1)<0}{1-\alpha}\le
\alpha+\beta<1
$
и т.к.

$
\frac{\beta}{1-\alpha}<\alpha+\beta<1
$

то скорость сходимости метода Зейделя выше, чем метода простой итерации

{\bf Релаксационные методы}-отличие от метода Зейделя в ведении ускоряющего
параметра
$$
Ax=f\to \sum_{i=1}^na_{ij}{x_j}=f_i | \mbox{умножим на $\tau$ }\forall i
$$
 и приведем к виду
$$
x_i=x_i+{\tau} (f_i-\sum_{j=1}^{i-1}a_{ij}x_j-\sum_{j=i}^n a_{ij} x_j)
$$
 и применим идею Зейделя для схемы а)


$$
\begin{array}{l}
x_1^{k+1}= x_1^k+{\tau}(f_1-\sum_{j=2}^na_{ij}x_j^k)\\
\\
x_i^{k+1}=x_i^k+{\tau}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j^{k+1}-\sum_{j=i}^na_{ij}x_j^k)\\
\end{array}
$$
$i=\overline{2,n},k=0,1,2,\cdots$
получим релаксационный алгоритм

{\bf Сходимость стационарных методов }
$$
B\frac{x^{k+1}-x^k}{\tau}+Ax^k=f,k\to\infty
$$
Пусть $B$ имеет обратную $B^{-1}$ (  для существования обратной
достаточно потребовать положительности $B$ т.е. $(Bx,x)>0, \forall x\to B>0$

Теорема. Пусть $A=A^*>0$-самосопряженная и выполнены условия
$B>\frac\tau 2 A$,(имеется в виду $((B-\frac\tau 2 A)x,x)>0 )$,
 тогда  последовательность построенная по выше приведенному правилу
сходится к $x^*$,  решению уравнения $Ax^* \equiv f $.

Оператор A- самосопряженный, если $(Ax,x)=(x,Ax)\forall x\in V$
Для матриц $A^*=A'$

a)Если $B=E$ $\tau<\frac{2}{||A||}, A=A^*>0$- метод простой итерации сходится

б) Метод Зейделя сходится если $A=A^*>0$

с) метод релаксации сходится, если  $A=A^*>0$ и $0<\tau <2$


Заметим, что проверка условий положительности матриц общего вида затруднительна
и часто уверенность в положительности дает тот факт, что
матрица является следствием положительности оператора, аппроксимацией которого
она является. Например,

$Au=-\frac{d^2u}{dx^2}, u\in L_{2[a,b]}, u|_a^b=0$

$(Au,u)=-\int_a^b\frac{d^2u}{dx^2}=-u\frac{du}{dx}|_a^b
+\int^b_a(\frac{du}{dx})^2dx>0$


{\bf Нестационарные методы }
Определение. Невязкой системы $Ax=f$ назовем $r^k=Ax^k-f, x^k\in R_n$. Очевидно, что
если $x^k=x^*, \to r^k=0$
Рассмотрим явный нестационарный процесс

$$
\frac{x^{k+1}-x^k}{\tau_k}+Ax^k=f,k\to\infty
$$

$$
x^{k+1}=x^k-\tau_k(Ax^k-f)=x^k-\tau_k r^k|A \pm f
$$
получим
$$
Ax^{k+1}-f=Ax^k-\tau_kAr^k
$$
или
$$
r^{k+1}=r^k-\tau_kAr^k=(E-\tau_kA)r^k
$$


Для нахождения $\tau_k $ предложим следующие алгоритмы
а) метод минимальной невязки

$\tau_k$ выбирается из минимума скалярного произведения
$$
(r^{k+1},r^{k+1}) \to  \min\limits_{\tau_k}
$$
т.к.
$$
(r^{k+1},r^{k+1})=(r^k-\tau_kAr^k,r^k-\tau_kAr^k)=
$$
$$
(r^k,r^k)-2\tau_k(r^k,Ar^k)+
\tau_k^2(Ar^{k},Ar^{k})
$$
$$
\frac{\partial}{\partial \tau_k} (r^{k+1},r^{k+1})=0 \to
\tau_k=\frac{(Ar^k,r^k)} {(Ar^{k},Ar^{k}) }
$$
б) метод наискорейшего спуска
$\tau_k$ выбирается из условия ортогональности $r^{k+1}$ и $r^k$
$$
(r^{k+1},r^k)=(r^k,r^k)-\tau_k(Ar^k,r^k)=0\to
\tau_k=\frac{(r^k,r^k)}{(Ar^{k},r^{k}) }
$$

 Условие сходимости метода $A=A^*>0$

}
\end{document}
