%\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{pscyr}
\usepackage[cp1251]{inputenc}

\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\textheight 22cm \textwidth 16cm \topmargin 0cm \oddsidemargin 0cm \evensidemargin 0cm
%\twocolumn
%\oddsidemargin =-2cm
%\topmargin -3cm
%\textheight=28cm
%\textwidth=19cm
\pagestyle{empty}
\begin{document}
{\footnotesize
Лекция 3.
{

\bf Итерационные методы решения линейных систем} Известно, что всякая квадратная
матрица $A=\{a_{ij},ij=\overline{1,n}\}$ определяет оператор
отображающий n-мерное векторное пространство само в себя $A:R_n\to R_n$ и
уравнение $Ax=f$ можно рассматривать как операторное уравнение I-рода.
Для решения таких уравнений можно применять принцип сжимающих отображений.
{\bf Принцип сжимающих отображений} Пусть V-полное метрическое пространство
с метрикой$\rho$, $A:V\to V$ сжимающее отображение с постоянной сжатия
$\alpha, 0\le\alpha<1$:

Тогда 1) оператор А имеет единственную неподвижную точку $x^*$, т.е.
$$
Ax^*=x^*
$$
2) для любого элемента $x_0\in V$ последовательность $\{x^n\}_{n=0}^{\infty}$
образованная по рекурентному правилу
$$
x^{n+1}=Ax^n
$$
сходится к неподвижной точке $x^*$.

3) имеет место оценка
$$
\rho(x^n,x^*)\le \frac{\alpha^n}{1-\alpha}\rho(x^0,x^1)
$$
{\bf Определение} Оператор А-сжимающий, если имеет место оценка
для любых элементов $x_1,x_2\in V$
$$
\rho(Ax_1,Ax_2)\le \alpha\rho(x_1,x_2), 0\le\alpha <1
$$

n-мерное векторное пространство является полным метрическим пространством т.е.
любая фундаментальная последовательность в этом пространстве сходится
к элементу этого пространства.

Метрика в $R_n$ -задается различным образом. Приняты следующие метрики

1) кубическая $$\rho_k(x,y)=max_{0\le i\le n}|x_i-y_i|$$

2) октаэдрическая $\rho_o(x,y)=\sum_{i=1}^n|x_i-y_i|$

3) эвклидова(сферическая)  $$\rho_s(x,y)=\sqrt{\sum_{i=1}^n|x_i-y_i|^2}$$

Идея применения принципа сжимающих отображений состоит в преобразовании
исходного уравнения первого рода $Ax=f$ к уравнению второго рода $x=Bx+\phi$.
Это преобразование может быть выполнено различными способами, на пример,
$$
Ax=f,\to x-x+ax=f,\to x=(E-A)x+f,\to B=E-A,
$$
 E-тождественное преобразование
Здесь $B:R_n\to R_n$ и последовательность строится по правилу
$x^{k+1}=Bx^k+\phi, k\to \infty  $

Достаточные условия сходимости метода:

Если  отображение $B$  сжимающее т.е. $0\le\alpha(b)<1$ тогда последовательность
$x^{k+1}=Bx^k+\phi, k\to \infty  $ сходится к решению уравнения
$$
x=Bx+\phi
$$

 Действительно,
$$
\rho(Bx_1+\phi,Bx_2+\phi)=\rho(Bx_1,Bx_2)\le\alpha_b\rho(x_1,x_2)
$$
и, следовательно, применим принцип сжимающих отображений.

Признаки сжимаемости отображения $B=\{b_{ij},i,j=\overline{1,n}\}$ различных
метриках

1) кубическая метрика $$\alpha_k(B)=\max\limits_{1\le i \le n} \sum_{j=1}^n|b_{ij}|=||B||_k<1$$
Для $x,y\in R_n$
$$
\rho(Bx,By)=\max_{1\le i\le n}|\sum_{j=1}^nb_{ij}x_j-\sum_{j=1}^nb_{ij}y_{j}|\le
$$
$$
\max_{1\le i\le n}\sum_{j=1}^n|b_{ij}||x_j-y_j|\le
\max_{1\le i\le n}\sum_{j=1}^n|b_{ij}|\max_{1\le j\le n}|x_j-y_j|=
$$
$$
\max_{1\le i\le n}\sum_{j=1}^n|b_{ij}|\rho(x,y)
$$
2)октаэдрическая метрика
$$\alpha_o(B)=\max\limits_{1\le j \le n} \sum_{i=1}^n|b_{ij}|=||B||_o<1$$

Для $x,y\in R_n$
$$
\rho(Bx,By)=\sum_{i=1}^n |\sum_{j=1}^nb_{ij}x_j-\sum_{j=1}^nb_{ij}y_{j}|\le
\sum_{i=1}^n|\sum_{j=1}^nb_{ij}(x_j-y_j)|\le
$$
$$
\sum_{j=1}^n\sum_{i=1}^n|b_{ij}||x_j-y_j|=
\max_{1\le j\le n}\sum_{i=1}^n|b_{ij}|\sum_{j=1}^n|x_j-y_j|=
$$
$$
\max_{1\le j\le n}\sum_{i=1}^n|b_{ij}|\rho(x,y)
$$

3) сферическая метрика
$$\alpha_c (B)=\sum_{i=1}^{n} \sum_{j=1}^n |b_{ij}|^2>||B||_c <1 $$
Для $x,y\in R_n$

$
\rho(Bx,By)=\sqrt{\sum_{i=1}^n[\sum_{j=1}^nb_{ij}x_j -\sum_{j=1}^nb_{ij}y_j   ]^2}=
$

$
\sqrt{\sum_{i=1}^n[\sum_{j=1}^nb_{ij}(x_j -y_j)  ]^2}\le
$

$
\{неравенство Коши \sum_{i=1}^na_ib_i\le \sqrt{\sum_{i=1}^n a_i^2} \sqrt{\sum_{i=1}^n b_i^2} \}
$

$
\sqrt{ \sum_{i=1}^n [{\sum_{j=1}^n b_{ij}^2 }
{ \sum_{j=1}^n (x_j-y_j)^2}     ]^2}=
$

$
\sqrt{\sum_{i=1}^n\sum_{j=1}^nb_{ij}^2} \rho_c(x,y)
$

{\bf Методы построения итерационных последовательностей}
Множество итерационных методов для решения линейных систем можно представить
в канонической форме

$
B_k\frac{x^{k+1}-x^k}{\tau_k}+Ax^k=f, k=0,1,\cdots, x^0\in R_n
$

Здесь А-матрица исходной системы, $\tau_k$ - итерационный параметр,
$B_k:R_n\to R_n$ - матрица, имеющая обратную $B_k^{-1}$
( $A^{-1}A=E, AA^{-1}=E$)

{\bf Опр. } Если $B_k=E$ итерационный метод называют явным с канонической формой

$
\frac{x^{k+1}-x^k}{\tau_k}+Ax^k=f, k=0,1,\cdots, x^0\in R_n
$

в противном случае неявным

Для неявного метода на каждом итерационном шаге необходимо
решать относительно $x^{k+1}$ линейную систему

$
B_kx^{k+1}=B_kx^k-\tau_kAx^k+f, k=0,1,\cdots, x^0\in R_n
$

Отсюда требование - объем вычислений для решения этой системы должен быть не очень
большим. Желательно иметь $B_k$ - треугольной.

{\bfОпр. }  Итерационный метод называют стационарным, если
$B_k=B,\tau_k=\tau$ , в противном случае метод называют нестационарным

1. {\bf Метод простой итерации} (множество вариантов)
С помощью невырожденного преобразования С $det(C)\ne0$ можно описать следующим
образом

$
Ax=f|C\to 0=CAx+Cf\to x-x=-CAx-Cf\to
$

$
x=(E-CA)x+Cf
$

И далее  к полученному уравнению второго рода применяют принцип сжимающих
отображений т.е. строят итерационную последовательность по правилу

$
x^{k+1}=(E-CA)x^k+Cf, k=0,1,2\cdots, x^0\in R_n
$
С достаточными условиями сходимости

$
\alpha(E-CA)<1
$

Метод явный $B_k=E$  и стационарный $\tau_k=1$
Преобразование С выбирают так, чтобы выполнялись достаточные условия сходимости,
как правило, это достигается подбором

а) $C=D^{-1}$ где $D=\{d_{ij}=0, d_{ii}=a_{ii},i,j=\overline{1,n} \}$

$
x^{k+1}=(E-D^{-1}A)x^k+D^{-1}f, k=0,1,2\cdots, x^0\in R_n
$

или в координатной форме

$
x_i =-\frac{a_{i1}} {a_{ii}} x_1-\cdots -\frac{a_{ii-1} }{a_{ii}}x_{i-1} -
\frac{a_{ii+1}}{a_{ii}}x_{i+1}-\cdots -\frac{a_{in}}{a_{ii}}x_{n} +\frac{f_i}{a_{ii}}
$

$\i=\overline{1,n}$

Условия сходимости
в кубической метрике:

$
\max\limits_{1\le i\le n}\sum_{k=1,k\ne i}^n|\frac{a_{ik}}{a_{ii}}|<1
$

 октаэдрической метрике:

$
\max\limits_{1\le k\le n}\sum_{i=1,k\ne i}^n|\frac{a_{ik}}{a_{ii}}|<1
$

 сферической метрике:

$
\sum\limits_{ i=1}^n\sum_{k=1,k\ne i}^n|\frac{a_{ik}}{a_{ii}}|^2<1
$

а) $C=E$

$
x^{k+1}=(E-A)x^k+f, k=0,1,2\cdots, x^0\in R_n
$

б) $C=\tau E$

$
x^{k+1}=(E-\tau A)x^k+\tau f, k=0,1,2\cdots, x^0\in R_n
$


Пример
$$
\left\{
\begin{array}{r}
x_1+x_2=1\\
x_1+2x_2=1\\
\end{array}
\right.
$$
а)
$$
\left\{
\begin{array}{r}
x_1=-x_2+1\\
x_2=-0.5x_1+0.5\\
\end{array}
\right.
$$

$$
B=E-D_1A=\left(
\begin{array}{cc}
0 &-1\\
-0.5&0\\
\end{array}
\right)
$$
$\alpha_k(B)=1,$  $\alpha_j(B)=1,$ $\alpha_c(B)=1+0.25,$ т.е. о сходимости
процесса
$$
\left\{
\begin{array}{r}
x_1^{k+1}=-x_2^k+1\\
x_2^{k+1}=-0.5x_1^k+0.5\\
\end{array}
\right.
k=0,1,2,\cdots
$$
сказать ничего нельзя
б)
$$
\left\{
\begin{array}{r}
x_1=-x_2+1\\
x_2=-x_1-x_2+1\\
\end{array}
\right.
$$
$$
B=E-A=\left(
\begin{array}{cc}
0 &-1\\
-1&-1\\
\end{array}
\right)
$$

$\alpha_k(B)=2,$  $\alpha_j(B)=2,$ $\alpha_c(B)=3,$ т.е.  сходимости нет
с)

$$
\left\{
\begin{array}{r}
x_1=(1-\tau )x_1-\tau x_2+\tau \\
x_2=-\tau x_1+(1-2\tau)x_2+\tau \\
\end{array}
\right.
$$

$$
B=E-\tau A=\left(
\begin{array}{cc}
1-\tau &-\tau \\
-\tau &1-2\tau \\
\end{array}
\right)
$$
$\alpha_c(B)=(1-\tau)^2+\tau^2+\tau^2+(1-2\tau)^2=7\tau^2-6\tau+2<1, \to
\frac{3-\sqrt{2}}{7}<\tau\frac{3+\sqrt{2}}{7} $  сходимость имеет место
для процесса
$$
\left\{
\begin{array}{r}
x_1^{k+1}=(1-\tau )x_1^k-\tau x_2^k+\tau \\
x_2^{k+1}=-\tau x_1^k+(1-2\tau)x_2^k+\tau \\
\end{array}
\right.
$$




}

\end{document}
