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

Лекция 5.  Нормированные пространства: Линейное пространство $X$- нормированно,
если определено число $\|x\|$- называемое нормой и удовлетворяющее условиям

1)$\|x\|\le0, \forall x=0$

2) $\|\lambda x\|=|\lambda| \|x\| \forall \lambda \in R$

3) $\|x+y\|\le \|x\|+\|y\|, \forall x,y\in X $

{\bf Опр} Нормой оператора А, согласованной с нормой элемента $x\in X$
пространства в котором действует оператор, называется число

$
\|A\|=\sup\limits_{\|x\|\ne 0}\frac{\|Ax\|}{\|x\|}= \sup\limits_{\|x\|\le 1}{\|Ax\|}
$ $\to$ $\|Ax\|\le \|A\|\|x\|$

Проверим аксиомы нормы
3) аксиома тр-ка $\|A+B\|\le \|A\|+\|B\|$

$\|A+B\|=\sup\limits_{\|x\|\ne 0}\frac{\|(A+B)x\|}{\|x\|} \le
\sup\limits_{\|x\|\ne 0}\frac{\|Ax\|}{\|x\|}+
\sup\limits_{\|x\|\ne 0}\frac{\|Bx\|}{\|x\|}= \|A\|+\|B\|$

Имеет место свойства

$\|ABx\|\le\|A\|\|Bx\|\le\|A\|\|B\|\|x\|$

$\|A^kx\|=\|\underbrace{A\cdots A}_kx\|\le \|A\|^k\|x\| \to \|A^k\|\leq \|A\|^k$

Примеры нахождения норм операторов

1. $X=C_{[a,b]} : Ax=tx, \|x\|=\max\limits_{a\le t\le b}|x(t)|: A:C_{[a,b]}\to C_{[a,b]}$

a)$\|Ax\|=\max\limits_{a\le t\le b}|tx(t)| \le
b \max\limits_{a\le t\le b}|x(t)| =b\|x\|\le \{\|x\|\le 1\}=b$

б) $\forall x^0 x^0=1 \to \|Ax^0\|= \max\limits_{a\le t\le b}|t|=b;$

$\|A\|=\sup\limits_{\|x\|\le1}\|Ax\|\ge \|Ax^0\|=b$

 Из неравенств а) и б) заключаем, что $\|A\|=b$

2. $A:R_n\to R_n, A=\{a_{il}, i,j=\overline{1,n}\} \|A\|=?$

2.1. $\|A\|_k$ -т.е. норма, согласованная с кубической нормой вектора
$\|x\|_k=\max\limits_{1\le i\le n}|x_i|$

a) $\|Ax\|_k= \max\limits_{1\le i\le n}|\sum_{j=1}^na_{ij}x_j| \le
$

$
\max\limits_{1\le i\le n}\sum_{j=1}^n|a_{ij}| \max\limits_{i}|x_i| =
$

$
\max\limits_{1\le i\le n}|\sum_{j=1}^n|a_{ij}| \|x\|_k\le \{
$

$
\forall \|x\|_k=1\|\le 1\} \le \max\limits_{1\le i\le n}|\sum_{j=1}^n|a_{ij}|$


Пусть $ \max\limits_{1\le i\le n}|\sum_{j=1}^n|a_{ij}|$  достигается
при $i=i_0$

Обозначим вектор $x^0=\{sign(a_{i_0j}\}_{j=1}^n \mbox{ c } \|x^0\|=1$

$\|A\|_k=\sup\limits_{\|x\|\le 1}\|Ax\|\ge \|Ax^0\|_k=
\max\limits_{i}|\sum_{j=1}^na_{ij}x_j^0|=
\sum_{j=1}^n|a_{i_0j}|=\max\limits_{1\le i \le n}\sum_{j=1}^n |a_{ij}|$

Из этого и предыдущего неравенств следует, что
$\|A\|_k=\max\limits_{1\le i \le n}\sum_{j=1}^n |a_{ij}|$  и совпадает с кубической
постоянной сжатия матрицы

2. Октаэдрическая норма матрицы -

$\|A\|_o=\max_{1\le j\le n}\sum_{i=1}^n|a_{ij}|$

3. Сферическая норма матрицы -

$\|A\|_c=\sqrt{\max_{i}|\lambda_i(AA^*)|}$

Опр. Оператор $A^*$ назовем сопряженным к оператору $A$, если
$\forall x,y\in R_n, (Ax,y)=(x,A^*y)$

Опр. Если $A=A^*$ то оператор А называют самосопряженным.

Опр. Оператор $A^*A$ - называют сингулярным по отношению к оператору $A$,
а его собственные числа сингулярными собственными числами
оператора $A$

Оператор $A^*A\ge 0$ и является симметрическим или самосопряженным
Действительно, например

$0\le (Ax,Ax)=(x,A^*Ax) \to A^*A\ge 0$

следовательно, оператор $A^*A$- имеет действительные собственные числа

$\|A\|_c=\sup_{\|x\|_c\ne 0}\frac{\|Ax\|_c}{\|x\|_c}=\sup_{\|x\|_c\ne 0}
\sqrt{\frac{(Ax,Ax)} {(x,x)}}
= \sqrt{\sup_{\|x\|_c\ne 0}  \frac{(A^*Ax,x)}{(x,x)} }=
\sqrt{ \max_{i}| \lambda_i(AA^*) | }$



Пусть $\lambda_i,e_i$- собственные числа и собственные вектора оператора B

$x=\sum_ix_ie_i, (Bx,x)=(B\sum_ix_ie_i,\sum_ix_ie_i)=
$

$
(\sum_i\lambda_ix_ie_i,\sum_ix_ie_i)=
\sum_i\lambda_ix_i^2\le \max_i|\lambda_i|\sum_ix_i^2=\max_i|\lambda_i|(x,x)$

Аналогично $(Bx,x)\ge \min_i|\lambda_i|(x,x) \to
\sup_{x,|x\|\ne 0}\frac{(Bx,x)}{(x,x)}=\sqrt{\max_i|\lambda_i|}$
$||A^{-1}||=\frac{1}{\sqrt{min_i|\lambda_i|}}$

Следствие. Если А - симметрический, то $\lambda(A^*A)=\lambda(A^2)=\lambda^2(A)\to$
$\|A\|_c=\max_i|\lambda_i(A)|$,$\|A^{-1}\|=(\min_i\|\lambda_i(A)|)^{-1}$









{\bf Теорема} о достаточных условиях сходимости метода простой итерации

$Ax=f{\to} x=Tx+\phi, \{x^{k+1}\}_{k=0}^\infty=\{x^{k+1}=Tx^k+\phi\}
\to_{x\to\infty}x^*=Tx^*+\phi \mbox{ если } \|T\|<1
$
Пусть $x^*$ т.р. $x^*\equiv=Tx^*+\phi$ тогда

$
\|x^*\|=\|Tx^*+\phi\|\le \|Tx^*\|+\|\phi\|\le
\|T\| \|x^*\|+\|\phi\|
$

откуда, следует, что

$
\|x^*\|\le \frac{\|\phi\|}{1-\|T\|}$, если $\phi=0$, то и $x^*=0$ и следовательно
 однородное уравнение $x=Tx$ $(\|T\|<1$ имеет единственное решение а следовательно
 и неоднородное уравнение имеет единственное решение

 Пусть $r^k=x^k-x^*$

$x^k=Tx^{k-1}+\phi$

$x^*=Tx^*+\phi$ Вычитая из первого второе, будем иметь $x^k-x^*=T(x^{k-1}-x^*)\to$
$\|r^k\|\le \|Tr^{k-1}\|\le \|T\|\|r^{k-1}\|\le \cdots\le \|T\|^k\|r^0\|
\mbox{и т.к.} \|T\|<1 \to \|r^k\|\to 0$

{\bf Практическое правило} оценки погрешности
для решения систем $x=Tx+\phi$ итерационными методами

Если $\|x^k-x^{k-1}\|\le \epsilon \frac{1-\|T\|}{\|T\|}$ то
$\|x^k-x^*\|\le \epsilon$

Док-во:

$x^*=Tx^*+\phi$

$x^k=Tx^{k-1}+\phi$

Вычитая из первого равенства второе имеем
$x^*-x^k=T(x^*-x^{k-1})\to x^*-x^{k-1}+x^{k-1}-x^k=T(x^*-x^{k-1})\to$

$\|x^*-x^{k-1}\|\le\|x^k-x^{k-1}+T(x^{k-1}-x^*)\|\le
\|x^k-x^{k-1}\|+\|T\|\|x^{k-1}-x^*\|\to
\|x^*-x^{k-1}\|\le\frac{\|x^*-x^{k-1}\|}{1-\|T\|}$

С другой стороны $x^k-x^*=T(x^k-x^*)\to
\|x^k-x^*\|\le \|T\|\|x^{k-1}-x^*\|\le
\|T\| \frac{\|x^k-x^{k-1}\|}{1-\|T\|}\le \epsilon \to $ практическое правило

{\bf Погрешности в решении линейных систем при приближенном задании
 матрицы А и правой части}

1. Приближенное задание правой части

(1) $Ax=f$ х - решение

(2) $Ax^*=f+\delta f$, $x^*$- решение $x^*=x+\delta x \to$ $A(x+\delta x)=f+\delta f$

Вычитая из (2)-(1), будем иметь

$A\delta x=\delta f$ $\to \delta x= A^{-1}\delta f\to $

$\|\delta x\|\le \|A^{-1}\|\|\delta f\|$

с другой стороны $f=Ax\to \|f\|\le \|A\|\|x\|$

перемножая два последних неравенства, будем иметь

$\|\delta x\|\|f\|\le \|A^{-1}\|\|A\|\|\delta f\|\|x\|\to$

$\frac{\|\delta x\|}{\|x\|}\le \|A^{-1}\| \|A\| \frac{\|\delta f\|}{\|f\|}$

{\bf Опр.} Число $\|A^{-1}\|\|A\|$ называют числом обусловленности матрицы А и обозначают
через $cond(A)$

2. Приближенное задание матрицы А

(1) $Ax=f$ х-решение

(2) $(A+\delta A)x^*=f$, $x^*$- решение $x^*=x+\delta x
 \to$ $(A+\delta A)(x+\delta x)=f$

Из (1) $\to x=A^{-1}f$

Из (2)$\to x+\delta x=(A+\delta A)^{-1}f$

Вычитая из второго первое равенство, имеем

$\delta x=[(A+\delta A)^{-1}-A^{-1}]f$


Для матриц имеет место тождество

$ C^{-1}-B^{-1}=B^{-1}(B-C)C^{-1}$

Тогда для $\delta x$  имеем

$\delta x=-A^{-1}\delta A(A+\delta A)^{-1} f=-A^{-1}\delta A (x+\delta x) \to$

$\|\delta x\|\le \|A^{-1}\|\|\delta A\|\|x+\delta
 x\|=\|A^{-1}\|\|A\|\frac{\|\delta A\|}{\|A\|}\|x+\delta x\|$

$\frac{\|\delta x\|}{\|x+\delta x\|}\le
\|A^{-1}\|\|A\|\frac{\|\delta A\|}{\|A\|}$

Здесь $ \frac{\|\delta A\|}{\|A\|}$ -мера относительной неопределенности в задании
коэффициентов системы, число
$cond(A)=\|A^{-1}\|\|A\|$ -ограничивает сверху неопределенность в решении системы

Свойства числа $cond(A)=\|A^{-1}\|\|A\|$

1) $cond(A)\to 1$  т.к. $A^{-1}A=E\to \|E\|=1\le \|A^{-1}\|\|A\|$

2) Чем больше число обусловленности, тем больше погрешность в решении
линейных систем
при неопределенном задании коэффициентов матриц и правых частей  иными
словами число обусловленности характеризует качество системы по отношению
к различным ошибкам.

3) Для вырожденных матриц  $cond(A)=\infty$  Иногда величину
$\frac{1}{cond(A)}$-
рассматривают как расстояние от данной матрицы до множества вырожденных матриц


4) Вычислять число обусловленности удобно в сферической норме

$cond_c(A)=\sqrt{\frac{\max_i|\lambda_i(A^*A)|}{\min_i|\lambda_i(A^*A)|}}$
Для симметрических (самосопряженных) матриц
$cond_c(A)={\frac{\max_i|\lambda_i(A)|}{\min_i|\lambda_i(A)|}}$

{\bf Пример 1:} диагональная матрица $D=\{d_{ii}=0.1 , i=\overline{1,n} \}$

$cond(D)=\frac{\max_i|d_{ii}|}{\min_i|d_{ii}|}=1$

$det(D)=(0.1)^{n}$ маленькое число для больших n. Пример показывает,
что величина детерминанта к обусловленности матриц не имеет ни какого отношения.

{\bf Пример 2:}
$$
\begin{array}{rcl}
x_1-x_2 -x_3\cdots-x_n&=&-1\\
x_2-x_3 \cdots-x_n&=&-1\\
 \cdots& &  \\
x_{n-1}-x_n&=&-1\\
x_n&=&1\\
\end{array}
$$
Точное решение этой системы линейных уравненй
 $x=(x_1,x_2,\cdots,x_n)=(0,0,\cdots0,1) $
нетрудно получить метом исключения, начиная с последнего уравнения

Допустим, что при в n- компоненте правой части или, что то же самое при вычислении
$x_n$ допущена ошибка $\epsilon=10^{-15}$!!, достаточно маленькая, т.е.
$x_n-1+\epsilon$. Иными словами, мы решаем систему

$$
\begin{array}{rcl}
\overline x_1-\overline x_2 -\overline x_3\cdots-\overline x_n&=&-1\\
\overline x_2-\overline x_3 \cdots-\overline x_n&=&-1\\
 \cdots& &  \\
\overline x_{n-1}-\overline x_n&=&-1\\
\overline x_n&=&1+\epsilon\\
\end{array}
$$
Вопрос, как различаются решения этих двух систем. Заметим, что исходя из
жизненного опыта,  мы ожидаем небольшое различие.

Итак $|x-\overline x|=?$

Введем обозначения $\overline x=x+\delta,$ $\delta=(\delta_1,\delta_2,\cdots,\delta_n)=?$.

Для нахождения $\delta$ составим систему, полученную вычитанием первой из второй

$$
\begin{array}{rcl}
\delta_1-\delta_2 -\delta_3\cdots-\delta_n&=&0\\
\delta_2-\delta_3 \cdots-\delta_n&=&0\\
 \cdots& &  \\
\delta_{n-1}-x\delta_n&=&0\\
\delta_n&=&\epsilon\\
\end{array}
$$
Решая ее методом исключения, начиная с последнего получаем
$\delta_n=\epsilon$,$\delta_{n-1}=\delta_n=\epsilon$,$\delta_{n-2}=\delta_{n-1}+\delta_n=2\epsilon$ и т.д.
$\delta_1=2^{n-2}\epsilon$.

Если $\epsilon=10^{-15}$, n=102, $\Longrightarrow \delta_1=2^{100}10^{-15}\simeq10^{30}10^{-15}=10^{15}$!!!!


Оценим число обусловленности матрицы заданной системы

$cond(A)\ge \frac{\|\delta x\|/\|x\|}{\|\delta f\|/\|f\|}$

$\|\delta f=\|=\epsilon, \|f\|=1,\|\delta x\|=2^{n-2}, \|x\|=1\to
cond(A)\ge \frac{2^{n-2}\epsilon}{\epsilon}=2^{n-2}$

{\bf Достаточные условия хорошей обусловленности матриц}

$Ax=f$ $\to x=(E-A)x+f$

Пусть $\|E-A\|<1$  тогда матрица А -хорошо обусловлена т.е. ее число
обусловленности достаточно мало

$x=A^{-1}f$ $\to\|x\|\le \|A^{-1}\|\|f\|$ из определения нормы следует, что
существует $f\ne0$ такое, что неравенство обращается в строгое равенство

$\|x\|\le \|E-A\|\|x\|+\|f\|$ $\to \|x\|\le \frac{\|f\|}{1-\|E-A\|}$ -которое
обращается в строгое равенство только при $f=0$ Таким образом из последних
двух неравенств следует, что

$\|A^{-1}\|\le\frac{\|f\|}{1-\|E-A\|}$

$\|A\|=\|E-(E-A)\|\le 1+\|E-A\|$ тогда

$cond(A)=\|A^{-1}\|\|A\|\le \frac{1+\|E-A\|}{1-\|E-A\|}$




}


\end{document}
