%\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=27cm
%\textwidth=18cm
\pagestyle{empty}
\begin{document}
{\footnotesize

Лекция 6.

{\bf Нахождение максимального  и минимального собственных чисел положительной
симметрической матрицы}

Вспоминаем, что через эти числа вычисляется сферические нормы прямой и
 обратной матрицы

$(Ax,y)=(x,Ay), (Ax,x)>0$ -известно, что спектр таких матриц
действительный

Пусть имеется задача $Ax=\lambda x$. Предположим, что эта задача
имеет полный набор ортонормированных
собственных векторов $\{e_k\}_{k=1}^n, \|e_k\|^2=1$ и соответствующих им
собственных чисел $\lambda_k$ Предположим, что собственные числа упорядочены
т.е.

$\alpha(A)=\lambda_1<\lambda_2<\cdots\lambda_n=\beta(A)$

Для нахождения $\beta(A)$ рассмотрим итерационный процесс

$x=(x_1,x_2,\cdots,x_n), x^{k+1}=A\frac{x^k}{\|x^k\|}, \|x^k\|
=\sqrt{\sum_{i=1}^nx_i^2}$

$x^0$- произвольный вектор

Для

$x^{k+1}=A\frac{x^k}{\|x^k\|}=A(A\frac{x^{k-1}}{\|x^{k-1}\|})\frac{1}{\|x^k\|} = 
\mbox {тут внимательно читаем - формула может содержать ошибки,}$
$\mbox{исходный вариант не компилировался} A^2 \frac{x^{k-1} }{ \|x^{k-1}\| } \|A\frac{x^{k-1}}{\|x^{k-1}\|}\|=$

$\frac{A^2x^{k-1}}{Ax^{k-1}}= \cdots=\frac{A^kx^0}{\|A^{k-1}x^0\|}$
 и следовательно

$\lim\limits_{k\to\infty}\|x^{k+1}\|= \lim\limits_{k\to\infty}
\frac{\|A^kx^0\|}{\|A^{k-1}x^0\|}$

$\{e_k\}_{k=1}^n\}$- полный набор, то

$x^0=\sum_{i=0}^n c_ie_i$, $A^kx^0=\sum_{i=0}^n c_i\lambda_i^k e_i$,

$A^{k-1}x^0=\sum_{i=0}^n c_i\lambda_i^{k-1} e_i$  следовательно для
достаточно больших $k$

$A^kx^0=\beta^k c_ne_n\{1+O[\frac{\lambda_{n-1}}{\lambda_n}]^k\}$

$
\frac{\|A^kx^0\|}{\|A^{k-1}x^0\|}=\beta(A)+O[\frac{\lambda_{n-1}}{\lambda_n}]^k
$
 и следовательно

$
\beta(A)=\lim\limits_{k\to\infty}\frac{\|A^kx^0\|}{\|A^{k-1}x^0\|}
$

Если в качестве начального вектора $x^0$ будет выбран вектор, являющейся
линейной комбинацией собственных векторов, отличающихся от $\lambda_n=\beta(A)$,
то указанный выше процесс  позволяет получить $\beta(A)$ за счет ошибок
округления

Для нахождения $\alpha(A)=\lambda_1$ рассмотрим матрицу
$B=\beta(A)E-A$ т.к. $A>0\to B>0$  и матрицы $B$ и $A$  имеют общий базис
$\{e_k\}_{k=1}^n$  и следовательно

$\beta(B)=\beta(A)-\alpha(A)$

и с помощью аналогичного выше изложенному процессу, мы найдем
$
\beta(B)=\lim\limits_{k\to\infty}\frac{\|B^kx^0\|}{\|B^{k-1}x^0\|}
$



\centerline{\S5.\underline{ Критерий окончания итерационного процесса}}
\centerline{\underline{ при неточных входных данных.}}
\vskip 0.5cm
До сих пор при рассмотрении методов решения линейных систем мы исходили из того,
 что матрица и правые части нашей системы заданы точно. Однако в практических
задачах входные данные т.е. матрица и правая часть линейной системы заданы приближенно
и вместо уравнения
\begin{equation}
Ax=f
\label{kri1}
\end{equation}
мы имеем дело с уравнением
\begin{equation}
A_hx_h=f_h,
\label{kri2}
\end{equation}

где индекс h указывает на приближенность входных данных, которые зависят
либо от случайных ошибок или статистических погрешностей, либо погрешностей
появляющихся при вычислениях.

Будем предполагать, что ошибки правой части и матрицы А нам известны т.е.
заданы оценки вида
\begin{equation}
||(A-A_h)x||\le\varepsilon(h),\quad ||f-f_h||\le\eta(h)
\label{kri3}
\end{equation}

Следовательно, наша задача состоит в решении уравнения ~(\ref{kri1}) имея в распоряжении
уравнение ~(\ref{kri2}) и априорную информацию ~(\ref{kri3}).
Для решения уравнения ~(\ref{kri2}) используем метод простой итерации
\begin{equation}
x_h^{j+1}= (E-\tau A_h) x_h^j+\tau f_h,\quad x_h^0=0,\quad  j \to \infty
\label{kri4}
\end{equation}
при выполнении условия, обеспечивающего сходимость
\begin{equation}
||q= E-\tau A_h||\le 1.
\end{equation}
Заметим, что изложенные ниже результаты без труда распространяются на изложенные
выше методы.

Естественно предположить, что при заданных погрешностях коэффициентов матрицы А
и правой части f в виде ~(\ref{kri3}) последовательные приближения следует
 продолжать
до тех пор, пока ошибка итерационного процесса не станет приблизительно равной
равной ошибке, появляющейся из-за неточности входных данных.
Более того, оказывается если матрица А плохо обусловлена и, следовательно,
обратная матрица $A_h^{-1}$ может отличаться от обратной матрицы $A^{-1}$ значительно,
то продолжение итерационного процесса ~(\ref{kri4}) приводит не к улучшению,
а наоборот, к существенному ухудшению результата.

Для нахождения оптимального числа итераций в итерационном процессе
~(\ref{kri4}) при котором происходит согласование погрешностей из-за неточностей
входных данных и из-за невозможности провести
бесконечное число итераций проведем следующий анализ.

Уравнения ~(\ref{kri1}) и ~(\ref{kri2}) формально разрешим относительно неизвестных
$x$ и $x_h$


\begin{equation}
x=A^{-1}f, \quad x_h=A_h^{-1}f_h.
\label{kri5}
\end{equation}
Вычитая из второго первое и проводя тождественные преобразования получим

\begin{equation}
x_h-x=A_h^{-1}(f_h-f+Ax-A_hA^{-1}f)=A_h^{-1}(f_h-f+(A-A_h)x).
\label{kri6}
\end{equation}
Из последнего следует

\begin{equation}
|| x_h-x||\le||A_h^{-1}||(||f_h-f||+||(A-A_h)x||),
\end{equation}
или с учетом априорных оценок ~(\ref{kri3})
\begin{equation}
||x-x_h||\le ||A_h^{-1}||(\varepsilon(h)+\eta(h)).
\label{kri7}
\end{equation}



Представим уравнение ~(\ref{kri2}) в виде

\begin{equation}
x_h=(E-\tau A_h)x_h+\tau f_h.
\label{kri8}
\end{equation}
Вычитая из ~(\ref{kri8}) ~(\ref{kri4}), получим
\begin{equation}
(x_h-x_h^j)=(E-\tau A_h) (x_h-x_h^j).
\label{kri9}
\end{equation}

Используя метод математической индукции нетрудно получить


\begin{equation}
x_h-x_h^{j}=(E-\tau A_h)^jA_h^{-1}f_h=q^jA_h^{-1}f_h.
\label{kri10}
\end{equation}

В силу неравенства треугольника имеем


\begin{equation}
||x-x_h^j||=||x+x_h-x_h-x_h^j||\le||x_hj-x_h||+||x_h-x||,
\label{kri11}
\end{equation}
откуда с учетом ~(\ref{kri7}) и ~(\ref{kri10}) получаем



\begin{equation}
||x_h-x_h^{j}||=||q||^j||A_h^{-1}||||f_h||+||A_h^{-1}||
(\varepsilon(h)+\eta(h)).
\label{kri12}
\end{equation}


Первое слагаемое в последнем неравенстве дает оценку погрешности
итерационного процесса ~(\ref{kri5}), а второе слагаемое оценивает погрешность
за счет неточностей правой части и матрицы А. Требуя равенства этих погрешностей
получим уравнение для номера итерации $j_0$ на которой следует закончить
итерационный процесс


\begin{equation}
j_0=\frac{1}{\ln q} \ln \frac{(\varepsilon(h)+\eta(h))}{||f_h||}
\label{kri13}
\end{equation}
Следует отметить, что в формуле ~(\ref{kri13}) отсутствует норма обратного оператора,
что существенно упрощает вычисление оптимального числа итераций.


{\bf Регуляризирующие алгоритмы}

Пусть система $Ax=f$ имеет точное решение $x^*$  и пусть далее вместо
точного значения правых частей известно ее приближенные значения
$f_\delta(A_\delta) : \|f_\delta-f\|\le\delta, \|A_\delta-A\|\le\delta$
тогда регуляризирующим алгоритмом назовем оператор $R$, ставящий в соответствие
паре $(f_\delta,\delta),(A_\delta,\delta) $  элемент $x_\delta$ такой,
что $x_\delta\to x^* $ при
$\delta\to 0$

Пример: $Ax=f$ -$A-$симметрическая, неотрицательная. Вместо данной системы
рассмотрим систему

$(A+\alpha E)x=f$ т.к. $A>0$- симметрическая, то собственные числа
$\lambda_k$ матрицы $A$ - действительные. Пусть $\lambda_k>0$ а
$\{e_k\}_{k=1}^n$- собственные вектора матрицы $A$, $\|e_i\|^2=(e_i,e_i)=1$

$
(e_i,e_j)=0,i\ne j
$

Найдем решение уравнения $Ax=f$- методом Фурье. Представим

$
f=\sum_{i=1}^nf_ie_i,\|e_j\to f_i=(f,e_i)$

$x=\sum_{i=1}^nx_ie_i$ подставим в исходное уравнение

$A\sum_{i=1}^nx_ie_i=\sum_{i=1}^nf_ie_i,\to \sum_{i=1}^nx_iA e_i =\sum_{i=1}^nf_ie_i$
$\to\sum_{i=1}^n\lambda_ix_ie_i =\sum_{i=1}^nf_ie_i $
$\sum_{i=1}^n(x_i\lambda_i-f_i)e_i =0\to x_i\lambda_i=f_i,
x_i=\frac{f_i}{\lambda_i}=\frac{(f_i,e_i)}{\lambda_i}\to $

$
x=\sum_{i=1}^n\frac{f_i}{\lambda_i}e_i=\sum_{i=1}^n
\frac{(f,e_i)}{\lambda_i}e_i
$

Аналогично решая уравнение $(A+\alpha E)\underline{x}=f$ , получаем
$
\underline{x}=\sum_{i=1}^n\frac{(f,e_i)}{\lambda_i+\alpha}e_i
$

Сравнивая решения, видим, что

$|\underline{x}-x|\sim |\frac{1}{\lambda_i}-\frac{1}{\lambda_i+\alpha}|
=|\frac{\alpha}{\lambda_i(\lambda_i+\alpha)}| \to 0 при \to \alpha\to 0$

1) Видим, что введение $\alpha$ не существенно изменяет решение нашей системы

2) Видим, что существенную погрешность в решение вносят члены с малыми $\lambda_i,
\frac{1}{\lambda_i}- большие $, в то же время множитель для малых $\lambda_i$
$\frac{1}{\lambda_i+\alpha}<<\frac{1}{\lambda_i}$  и следовательно регуляризованная
 система $(A+\alpha E)x=f$ лучше обусловлена, чем исходная




}

\end{document}
