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


 Лекция 2.
{\bf Численные методы решения линейных систем}

Для линейной системы
$$
Ax=f, A=\{a_{ij},i,j=\overline{1,n}\},f=(f_1,f_2,\ldots,f_n),
$$
$$
x=(x_1,x_2,\ldots,x_n)
$$
с невырожденной матрицей и следовательно
$
det(A)\ne0
$
откуда следует существование единственного решения (Вопрос устойчивости
по отношению ошибок округления открыт ???)
рассмотрим различные методы решения с помощью ЭВМ.

Методы можно разделить на две  группы

1. Прямые методы -позволяющие получить решение исходной задачи
за конечное число операций

2. Итерационные -общая идея которых заключается в в построении последовательности,
сходящейся к решению поставленной задачи.

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

{\bf Прямые методы}-основная идея всех алгоритмов - сведение исходной
системы к системе либо с диагональной матрицей, либо к системе с либо с
верхней треугольной матрицей, либо с нижней, которые затем легко решаются
методом исключения.
1. A - диагональная
$$
A=\left(
\begin{array}{ccccc}
 a_{11} & 0    & 0 &\cdots & 0 \\
0     &a_{22}&0 &\cdots& 0\\
&&&\cdots&\\
0&0&0&\cdots&a_{nn}
\end{array}
\right)
$$
или

$
A=\{a_{ii}\ne 0,a_{ij}=0, i\ne j, i,j=\overline{1,n}\}
$

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

$
a_{ii}x_i=f_i, i=\overline{1,n}
$

 и ее решение задается формулой

$
x_i= \frac{f_i }{a_{ii}}, i=\overline{1,n}
$

Заметим, что здесь нет проблемы ошибок округления
2. A- нижняя треугольная матрица
$$
A=\left(
\begin{array}{ccccc}
a_{11}& 0    & 0&\cdots& 0\\
a_{21}     &a_{22}&0 &\cdots& 0\\
&&&\cdots&\\
a_{n1}&a_{n2}&a_{n3}&\cdots&a_{nn}\\
\end{array}
\right)
$$
$
A=\{a_{ij},a_{ij}=0,j>i,i,j=\overline{1,n}\}
$

или в координатной форме
$$
\begin{array}{l}
a_{11}x_1=f_1\\
a_{21}x_1+a_{22}x_{2}=f_2\\
\cdots\\
a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=f_n\\
\end{array}
$$
Ее решение задается формулой

$
x_i=\frac{1}{a_{ii}}(f_i-\sum_{j=1}^{i-1}a_{ij}x_j), i=\overline{1,n}
$

 3. A-верхняя треугольная матрица

$$
A=\left(
\begin{array}{ccccc}
a_{11}& a_{12}    & a_{13}&\cdots& a_{1n}\\
0     &a_{22}&a_{23} &\cdots& a_{2n}\\
&&&\cdots&\\
0&0&0&\cdots&a_{nn}\\
\end{array}
\right)
$$
$
A=\{a_{ij},a_{ij}=0,i>j, i,j=\overline{1,n}\}
$

или в координатной форме
$$
\begin{array}{r}
a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=f_1\\
a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=f_2\\
\cdots\\
a_{nn}x_n=f_n\\
\end{array}
$$
Ее решение задается формулой

$
x_i=\frac{1}{a_{ii}}(f_i-\sum_{j=i+1}^{n}a_{ij}x_j), i={n,n-1,n-2,\cdots,1}
$

Здесь возможно накопление ошибок округления

\centerline{I. \underline{Метод Гаусса}}
     Одним из прямых методов для решения линейных систем общего вида
 является хорошо известный метод последовательного
 исключения, связываемый с именем Гаусса.

   Метод заключается в приведении исходной системы  к системам  уравнений с
 треугольными матрицами
Различные модификации метода отличаются друг от друга путями приведения системы

   Опишем одну из модификаций, которая называется компактной формой Гаусса.
Эта модификация использует представлениe матрицы $A$ как произведение нижней треугольной
матрицы $B=\{b_{ij},b_{ij}=0,j>i,i,j=\overline{1,n} \}$ и верхней треугольной матрицы
$C=\{c_{ij},c_{ii}=1,c_{ij}=0,i>j,i,j=\overline{1,n}  \}:$

$
Ax=BCx=f, Cx=y, By=f
$

(представление  возможно, если, например, все главные миноры матрицы А
отличны от нуля. Решение исходной системы сводится к
последовательному решению
систем $By=f$ и $Cx=y$ с треугольными матрицами.
 Нахождение матриц $В,С$ и вектора у (из системы $By=b$)
является прямым ходом метода, а нахождение вектора $x$ из системы $Cx=y$
 обрaтным ходом.
Формулы для элементов матриц $B$ и $C$ получаются следующим образом:

$
a_{ij}=\sum_{k=1}^n b_{ik} c_{kj}, i,j=\overline{1,n}
$

с другой стороны

$$
\sum_{k=1}^nb_{ik}c_{kj}=\sum_{k=1}^{i-1}b_{ik}c_{kj}+b_{ii}c_{ij}+
\underbrace{\sum_{k=i+1}^nb_{ki} c_{kj}}_{\mbox{=0, b-нижняя треугольная }}
$$

$$
\sum_{k=1}^nb_{ik}c_{kj}=\underbrace{\sum_{k=1}^{j-1}b_{ik}c_{kj}}_{\mbox{=0,c-верхняя треугольная}}
+b_{ij}\underbrace{c_{jj}}_{\mbox{=1}}
+{\sum_{k=j+1}^nb_{ki} c_{kj}}
$$



$$
\begin{array}{l}
c_{ii}=1; \qquad b_{j1}=a_{j1},\qquad j=2,3,...,n;\\
c_{ij}=\frac {a_{ij}-\sum\limits_{k=1}^{i-1} b_{ik}c_{kj}}{b_{ij}} , i\ge j\\
b_{ji}=(a_{ji}-\sum\limits_{k=1}^{j-1}\ b_{jk}c_{ki}),i<j \\
\end{array}
$$

{\bf Метод квадратного корня}-применяется для систем с симметрической матрицей

$
A=\{a_{ij},,a_{ij}=a_{ji}, i,j=\overline{1,n}\}
$

Представим матрицу А в виде произведения
$
A=S'DS
$
где S-верхняя треугольная матрица $S=\{s_{ij},s_{ij}=0, i> j, i,j=\overline{1,n}\}$
$S'$- транспонированная к S, D-диагональная

$
D=\{d_{ii}\ne 0,d_{ij}=0, i\ne j, i,j=\overline{1,n}\}
$

$
Ax=S'DSx=f, обозначим DS=y
$

В результате имеем
$$
\begin{array}{r}
S'y=f-прямой ход\\
DSx=y -обратный ход\\
\end{array}
$$
Для представления $A=S'DS$ заметим, что

$(DS)_{ij}=\sum_{k=1}^nd_{ik}s_{kj}=d_{ii}s_{ij}$ или

$(S'DS)_{ij}=\sum_{k=1}^ns_{ki}d_{kk}s_{kj} $ и, следовательно,

$
a_{ij}=\sum_{k=1}^ns_{ki}d_{kk}s_{kj}, (i,j=\overline{1,n})
$

С другой стороны

$
\sum_{k=1}^ns_{ki}d_{kk}s_{kj}=\sum_{k=1}^{i-1}s_{ki}d_{kk}s_{kj}
 +s_{ii}d_{ii}s_{ij}+
$

$
 \underbrace{\sum_{k=i+1}^ns_{ki} d_{kk} s_{ki}}_{\mbox{=0, s-верхняя треугольная }}
$

Из последних двух равенств имеем
$
a_{ij}=\sum_{k=1}^ns_{ki}d_{kk}s_{kj}=\sum_{k=1}^{i-1}s_{ki}d_{kk}s_{kj}
 +s_{ii}d_{ii}s_{ij}
$

Замечая, что для $i=j$

$
|s_{ii}|^2d_{ii}=a_{ii}-\sum_{k=1}^{i-1}|s_{ki}|^2d_{kk}
$

и выбирая элементы диагональной матрицы D в форме

$
d_{ii}=sign(a_{ii}-\sum_{k=1}^{i-1}|s_{ki}|^2d_{kk})
$

получаем

$
s_{ii}=\sqrt{|a_{ii}-\sum_{k=1}^{i-1}|s_{ki}|^2d_{kk}| }
$

а для $i<j$

$
s_{ij}=\frac{a_{ii}-\sum_{k=1}^{i-1}|s_{ki}|^2d_{kk}}{s_{ii}d_{ii}}
$

Применяя поочередно последние формулы получаем алгоритм для нахождения коэффициентов
матрицы S



{\bf Метод прогонки.} Важным классом линейных систем  являются системы вида:

$$
\begin{array}{l}
x_0=\kappa_1x_1+\mu_1\\
a_ix_{i-1}-c_ix_i+b_ix_{i+1} = f_i,\qquad i=1,3,...,n-1\\
x_{n}=\kappa_2x_{n-1}+\mu_2
\end{array}
$$
с трехдиагональной матрицей

$$
A=\left[
\begin{array}{cccccccc}
1 & -\kappa_1 & 0 & 0 & ... & ... & 0 & 0\\
a_1 & -c_1 & b_1 & 0 & ... & ... & 0 & 0\\
... & ... & ... & ... & ... & ... & ... & ...\\
0 & 0 & ... & ... & 0 & a_{n-1} &-c_{n-1} & b_{n-1}\\
0 & 0 & ... & ... & 0 & 0 & -\kappa_2 & 1\\
\end{array}
\right]
$$
Такие системы возникают при решении краевых задач для дифференциальных
уравнений разностными методами.

Специальный вид матрицы $A$ позволяет применить идею исключения неизвестных
к исходной системе  следующим простым способом, который носит название
метода прогонки.

Первое уравнение системы  дает соотношение
между $x_0$ и $x_1$, в силу
которого второе уравнение системы дает соотношение между $x_1$ и $x_2$. Следовательно,
третье уравнение системы
дает соотношение между $x_2$ и $x_3$ и т.д. Запишем связь между
неизвестными $x_{i-1}$ и $x_i$ в виде:

$
x_{i}=\alpha_{i+1}x_{i+1}+\beta_{i+1},\qquad i=1,3,...,n-1.
$

Из первого уравнения системы  следует, что

$
\alpha_1=\kappa_1,\qquad \beta_1=\mu_1.
$

Подставляя  в $i$--е уравнение системы $x_{i-1}$ получим

$
x_i=-\frac{b_i}{c_i-a_i\alpha_i}x_{i+1}+\frac{-f_i-\beta_i a_i}{c_i-a_i\alpha_i}.
$

Сравнивая,  находим рекуррентные соотношения

$
\alpha_{i+1}=- \frac{b_i}{c_i-a_i\alpha_i},\qquad \beta_{i+1}=\frac{-f_i-\beta_ia_i}{c_i-a_i\alpha_i},\qquad  i=1,...,n,
$

которые вместе с формулами для $\alpha_1,\beta_1$ позволяют последовательно найти
все прогоночные коэффициенты $\alpha_i,\beta_i,i=1,...,n$. Процесс
нахождения этих коэффициентов называется прямым ходом метода
прогонки. Из последнего уравнения системы  и соотношения  для $i=n$ находим

$
x_n=\frac {\mu_2+\kappa_2\beta_n}{1-\alpha_n\kappa_2},
$

что позволяет по формулам $
x_{i}=\alpha_{i+1}x_{i+1}+\beta_{i+1},\qquad i=n-1,n-2,...,0.
$
 последовательно найти все остальные
неизвестные $x_{n},x_{n-1},...,x_1,x_0$. (обратный ход метода прогонки)

{\bf Достаточные условия алгоритма устойчивости прогонки}   Если
$
|c_i|\ge |a_i|+|b_i|, |\kappa_1|\le 1, |\kappa_2| \le 1, |\kappa_1|+|\kappa_2|<2
$
то алгоритм прогонки устойчив относительно ошибок округления

Доказательство:
 Рассмотрим устойчивость обратного хода прогонки. Для этого достаточно
выполнения условия

$
|\alpha_i|\le 1
$

Доказательство проведем по индукции. Предположим, что если

$
| \alpha_i | \le 1, \hskip 0.5cm\mbox{ то, следовательно,} \hskip 0.5cm |\alpha_{i+1}|\le 1
$

Для этого рассмотрим

$
|c_i-a_i\alpha_i|-|b_i|\ge |c_i|-|a_i| |\alpha_i|\ge |a_i|
+|b_i| -|a_i||\alpha_i|-|b_i|=
|a_i|(1-|\alpha_i|)\ge 0
$
и, следовательно,
 $
|\alpha_i|=\frac{|b_i|}{|c_i-a_i\alpha_i|}\le 1
$
Покажем далее, что
$
1-\kappa_2\alpha_n\ne 0
$
Действительно, из предыдущих рассуждений следует, что если для произвольного
$i_0$ имеет место строгое неравенство

$|c_{i_0}| > |a_{i_0}|+|b_{i_0}|,$ \mbox{то и}$|\alpha_i| <1$ для $i>i_0$.

Пусть $|\kappa_1|<1$, тогда $|\alpha_1|=|\kappa_1|<1$ и $|\alpha_n|<1$ а, следовательно,

 $
|1-\alpha_n\kappa_2|\le 1-|\alpha_n||\kappa_2|>1-|\kappa_1|>0
$

Откуда следует, что
$
|1-\alpha_n\kappa_2|\ne0
$

Пусть $|\kappa_1|=1$ а следовательно т.к. $|\kappa_1|+|\kappa_2|<2$, то $|\kappa_2|<1$
И следовательно
$
|1-\alpha_n\kappa_2|\le 1-|\alpha_n||\kappa_2|\le1-|\kappa_1|>0
$

Таким образом, в обратном ходе ошибки округления не нарастают.
В прямом ходе можно показать, что

$
max_{0\le i\le n}|\overline{x_i}-x_i|\le \epsilon_2 n^2
$
где $\epsilon_2$ -ошибка округления, т.е. машинное ерсилон
}
\end{document}
