\documentclass[12pt,a4paper,oneside,reqno,draft]{amsbook}
\usepackage{amsmath}
\usepackage{amsthm,array,longtable}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsfonts}
\usepackage{latexsym}


\tolerance 750


\renewcommand{\labelenumi}{\theenumi.}
\renewcommand*{\proofname}{Доказательство}
\DeclareMathOperator*{\grad}{grad}
\DeclareMathOperator*{\Div}{div}
\DeclareMathOperator*{\const}{const}
\newcommand*{\Rd}{\mathbb R^d}
\newcommand*{\sk}{\sum_{|\alpha|=k}}
\newcommand*{\Pc}{\mathcal P}
\newcommand*{\Ac}{\mathcal A}
\newcommand*{\Hc}{\mathcal H}
\newcommand*{\la}{\langle}
\newcommand*{\ra}{\rangle}
\newcommand*{\Sd}{\mathbb S^{d-1}}
\newcommand*{\Bd}{\mathbb B^d}
\newcommand*{\ov}{\overline}


\newtheorem{lemma}{Лемма}[section]
%\newtheorem{theorem}{Теорема}
\newtheorem{theorem}{Теорема}[section]

\newtheorem{proposition}{Предложение}[section]
\newtheorem{corollary}{Следствие}[section]
%\textwidth=160mm
%\usepackage{remreset}
%\makeatletter
%\@removefromreset{section}{chapter}
%\makeatother
\makeatletter
\renewcommand{\@biblabel}[1]{#1.}
\makeatother



\newcounter{exam}[section]
\renewcommand{\theexam}{\arabic{section}.\arabic{exam}}
\newcommand*{\ex}{\par\refstepcounter{exam}%
{\bf Пример \theexam.}\ }
\renewcommand*{\thefigure}{}
\pagestyle{plain}

\begin{document}
\renewcommand*\contentsname{СОДЕРЖАНИЕ}
\renewcommand{\figurename}{}

\bigskip

\begin{center} Министерство высшего и среднего специального \\
образования РСФСР

\bigskip

Московский авиационный технологический институт\\
им.\ К.Э.~Циолковского

\rule{115mm}{0,4pt}

\vskip10pt

Кафедра ``Высшая математика''

\vskip25pt

\begin{flushright}
Утверждено\\
редакционно-издательским\\
советом института\\
16.06.87
\end{flushright}

\vskip40pt


\large\rm
ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

\vskip30pt

\rm Методические указания\\
и варианты лабораторных работ

\vskip80pt

\begin{flushright}
Сост.: В.А.~Авакян\\
А.С.~Леонов\\
К.Ю.~Осипенко
\end{flushright}

\vskip 160pt
Москва  1988
\end{center}

\thispagestyle{empty}

\newpage


\tableofcontents

\setcounter{page}{3}
\section*{ВВЕДЕНИЕ}

Данные методические указания и варианты лабораторных работ по высшей математике предназначены для студентов I курса дневного отделения. Рассматриваются три из наиболее употребляемых численных методов решения систем линейных алгебраических уравнений с квадратной невырожденной матрицей: метод Гаусса, метод квадратичного корня и метод прогонки \cite{1}. При этом метод Гаусса используется обычно для решения систем общего вида, метод квадратного корня для решения систем с симметричной положительно определенной матрицей, а метод прогонки --- для решения систем с трехдиагональной матрицей, часто встречающихся в приложениях \cite{2,3}.

\section{МЕТОД ГАУССА}

Рассмотрим систему $n$ линейных алгебраических уравнений с $n$ неизвестными $x_1,x_2,\ldots,x_n$.
\begin{equation}\label{1}
\begin{cases}\arraycolsep=0.05em \begin{matrix}
a_{11}^{(0)}x_1&+&a_{12}^{(0)}x_2&+\ldots+&a_{1n}^{(0)}x_n&=&b_1^{(0)},\\
a_{21}^{(0)}x_1&+&a_{22}^{(0)}x_2&+\ldots+&a_{2n}^{(0)}x_n&=&b_2^{(0)},\\
\hdotsfor{7}\\
a_{n1}^{(0)}x_1&+&a_{n2}^{(0)}x_2&+\ldots+&a_{nn}^{(0)}x_n&=&b_n^{(0)}.
\end{matrix}&\end{cases}
\end{equation}

Предположим, для определенности, что коэффициент $a_{11}^{(0)}\ne0$, хотя на самом деле он может, конечно, оказаться равным нулю, и мы должны будем начать с какого-либо другого уравнения системы \eqref{1}, в котором коэффициент при $x_1$ не равен нулю. Преобразуем систему \eqref{1}, исключая $x_1$ из всех уравнений, кроме первого. Для этого разделим первое уравнение на $a_{11}^{(0)}$ и, умножая его последовательно на $a_{21}^{(0)},a_{31}^{(0)},\ldots,a_{n1}^{(0)}$, вычтем полученные уравнения соответственно из второго, третьего, $\ldots\,\,$, последнего уравнений системы \eqref{1}. В результате получим следующую систему:
\begin{equation}\label{2}
\begin{cases}\arraycolsep=0.05em
\begin{matrix}
x_1+\dfrac{a_{12}^{(0)}}{a_{11}^{(0)}}x_2&+\ldots+&\dfrac{a_{1n}^{(0)}}{a_{11}^{(0)}}
x_n&=\dfrac{b_1^{(0)}}{a_{11}^{(0)}},\\
\left(a_{22}^{(0)}-\dfrac{a_{12}^{(0)}}{a_{11}^{(0)}}a_{21}^{(0)}\right)x_2&+\ldots+&
\left(a_{2n}^{(0)}-\dfrac{a_{1n}^{(0)}}{a_{11}^{(0)}}a_{21}^{(0)}\right)x_n&\\
&&&\hspace{-42pt}=\left(b_2^{(0)}-\dfrac{b_1^{(0)}}{a_{11}^{(0)}}a_{21}^{(0)}\right),\\
\hdotsfor{4}\\
\left(a_{n2}^{(0)}-\dfrac{a_{12}^{(0)}}{a_{11}^{(0)}}a_{n1}^{(0)}\right)x_2&+\ldots+&
\left(a_{nn}^{(0)}-\dfrac{a_{1n}^{(0)}}{a_{11}^{(0)}}a_{n1}^{(0)}\right)x_n&\\
&&&\hspace{-42pt}
=\left(b_n^{(0)}-\dfrac{b_1^{(0)}}{a_{11}^{(0)}}a_{n1}^{(0)}\right).
\end{matrix}\end{cases}
\end{equation}
Теперь первое уравнение оставляем без изменения, а к остальным $n-1$ уравнений применяем указанную выше процедуру, исключив $x_2$ из последних $n-2$ уравнений, и т.д. Таким образом, повторив указанную процедуру $n$ раз, окончательно преобразуем исходную систему \eqref{1} к виду:
\begin{equation}\label{3}
\begin{cases}\arraycolsep=0.05em \begin{matrix}
x_1&+&a_{12}^{(1)}x_2&+&a_{13}^{(1)}x_3&+\ldots+a_{1n}^{(1)}x_n&=&b_1^{(1)},\\
&&\hphantom{a_{12}^{(1)}}x_2&+&a_{23}^{(2)}x_3&+\ldots+a_{2n}^{(2)}x_n&=&b_2^{(2)},\\
&&&\hdotsfor{5}\\
&&&&&x_{n-1}+a_{n-1,n}^{(n-1)}x_n\,\,&=&\,\,b_{n-1}^{(n-1)},\\
&&&&&\hspace{67pt}x_n&=&b_n^{(n)}.
\end{matrix}\end{cases}
\end{equation}
Или сокращенно
\begin{equation}\label{4}
x_i+\sum_{j=i+1}^na_{ij}^{(i)}x_j=b_i^{(i)},\quad i=1,\ldots,n,
\end{equation}
где
\begin{equation}\label{5}
a_{kj}^{(k)}=a_{kj}^{(k-1)}/a_{kk}^{(k-1)},\quad a_{ij}^{(k)}=a_{ij}^{(k-1)}-a_{ik}^{(k-1)}
a_{kj}^{(k)}.
\end{equation}
Процесс приведения системы \eqref{1} к виду \eqref{3} называется прямым ходом метода Гаусса, решения же системы \eqref{1} определяются из системы \eqref{3} в результате обратного хода, задаваемого формулами:
\begin{equation}\label{6}
\begin{cases}\arraycolsep=0.05em \begin{array}{lll}
x_n&=b_n^{(n)},&\\
x_{n-1}&=b_{n-1}^{(n-1)}-a_{n-1,n}^{(n-1)}x_n,&\\
\hdotsfor{2}\\
x_1&=b_1^{(1)}-a_{12}^{(1)}x_2+a_{13}^{(1)}x_3&+\ldots+a_{1n}^{(1)}x_n.
\end{array}\end{cases}
\end{equation}
В результате прямого и обратного ходов метода Гаусса количество действий \cite{1} порядка $Q=2n^3/3$ (при $n>7$).

При решении системы линейных уравнений методом Гаусса большое значение имеет рациональная запись результатов промежуточных вычислений.

\underline{І этап.} В таблицу записываются коэффициенты при неизвестных и свободные члены заданной системы \eqref{1} (см.\ табл.~1). Затем к этим числам присоединяются строка коэффициентов первого уравнения системы \eqref{2}.

\underline{II этап.} Записываются коэффициенты при неизвестных и свободные члены системы \eqref{2}, кроме коэффициентов первого уравнения. Затем к этим числам присоединяются строки коэффициентов второго уравнения системы \eqref{3}.

\underline{$K$-ый этап.} Записываются коэффициенты при неизвестных и свободные члены системы, которая получается после $k$-ой процедуры. Затем к этим числам присоединяются строки коэффициентов $k$-го уравнения системы \eqref{3}. На $n$-ом этапе находится неизвестное $x_n$ и заканчивается прямой ход. Далее, с помощью обратного хода находятся по формулам \eqref{6} остальные неизвестные $x_{n-1},x_{n-2},\ldots,x_1$.

Для контроля вычислений по указанной схеме применяют следующий метод:

Рассмотрим новую систему линейных уравнений с теми же коэффициентами при неизвестных, что и в \eqref{1}, но со свободными членами, равными сумме всех элементов строки.
$$c_i^{(0)}=a_{i1}^{(0)}+a_{i2}^{(0)}+\ldots+a_{in}^{(0)}+b_i^{(0)},\quad i=1,2,\ldots,n.$$
Если числа $\alpha_1,\alpha_2,\ldots,\alpha_n$ --- решение системы \eqref{1}, то легко заметить, что $\alpha_1+1,\alpha_2+1,\ldots,\alpha_n+1$ будут решениями системы со свободными членами $c_i^{(0)}$.

Присоединим к таблице еще один столбец составленный из чисел $c_i^{(0)}$. Выполняя с этим столбцом те же вычисления, что и с предыдущими, мы решаем одновременно две системы уравнений со свободными
членами $b_i^{(0)}$ и $c_i^{(0)}$. При правильных вычислениях решения второй системы должны быть на единицу больше решений системы \eqref{1}. Кроме того, мы имеем возможность контролировать и промежуточные вычисления, поскольку в процессе вычисления сумма элементов строки должна быть равна последнему элементу.

\underline{Пример:}

\noindent Методом Гаусса решить систему уравнений
$$\begin{cases}\arraycolsep=0.05em \begin{matrix}
3,0000x_1&+&0,1123x_2&-&0,1425x_3&-&0,2513x_4&=&-2,1202,\\
0,3113x_1&+&4,0000x_2&+&0,2357x_3&-&0,1273x_4&=&0,6012,\\
-0,2054x_1&+&0,3042x_2&+&5,0000x_3&-&0,2090x_4&=&-3,1723,\\
-0,2932x_1&-&0,1456x_2&+&0,2283x_3&+&3,0000x_4&=&2,0200.
\end{matrix}&\end{cases}$$
Приведем таблицу вычислений при решении этой системы методом Гаусса.

\bigskip

\begin{flushright}
Таблица I
\end{flushright}

\begin{center}
\begin{tabular}[c]{|r|r|r|r|r|r|}
\hline
\multicolumn{1}{|c|}{$x_1$}&\multicolumn{1}{c|}{$x_2$}&\multicolumn{1}{c|}{$x_3$}&
\multicolumn{1}{c|}{$x_4$}&\parbox[c][34pt]{1.9cm}{\begin{center}{\small Свободные члены}\end{center}}&\parbox[c][34pt]{2.6cm}{\begin{center}{\small \rule{0pt}{16pt}Сумма коэфф. строк}\end{center}}\\
\hline
3,0000&0,1123&-0,1425&-0,2513&-2,1202&0,5983\\
0,3113&4,0000&0,2357&0,1273&0,6012&5,2755\\
-0,2054&0,3042&5,0000&-0,2090&-3,1723&1,7175\\
-0,2932&-0,1456&0,2283&3,0000&2,0200&4,8095\\
\hline
1&0,0374&-0,0475&-0,0838&-0,7067&0,1994\\
\hline
&3,9984&0,2505&0,1534&0,8212&5,2134\\
&0,3119&4,9992&-0,2262&-3,3175&1,7585\\
&-0,1346&0,2144&2,9754&1,8128&4,8680\\
\hline
&1&0,0628&0,385&0,2059&1,3071\\
\hline
&&4,9706&-0,2382&-3,3817&1,3508\\
&&0,2229&2,9806&1,8405&5,0439\\
\hline
&&1&-0,0479&-0,6803&0,2718\\
\hline
&&&2,9913&1,9921&4,9833\\
\hline
&&&1&0,6660&1,6660\\
\hline
-0,6899&0,2210&-0,6484&0,6660&&\\
\hline
0,3100&1,2210&0,3516&1,6660&&\\
\hline
\end{tabular}

\bigskip

Варианты систем для решения\\
по методу Гаусса
\end{center}
\begin{tabular}{ll}
$(3,0000-h)x_1+0,1123x_2-0,1425x_3+(-0,2513+h)x_4$&\\
&\hspace{-78pt}$=-2,1202-h,$\\
$(0,3113-h)x_1+(4,0000+h)x_2+0,2357x_3-0,1273x_4$&\\
&\hspace{-69pt}$=0,6012+h,$\\
$-0,2054x_1+(0,3042+h)x_2+(5,0000-h)x_3-(0,2090+h)x_4$&\\
&\hspace{-78pt}$=-3,1723-h,$\\
$(-0,2932+h)x_1+(-0,1456+h)x_2+0,2283x_3+(3,0000-h)x_4$&\\
&\hspace{-69pt}$=2,0200-h,$
\end{tabular}

\bigskip

$h=0,0013N$, $1\le N\le100$.

\section{МЕТОД КВАДРАТНОГО КОРНЯ}
\setcounter{equation}{0}

Этот метод применим для решения линейной системы
\begin{equation}\label{11}
Ax=b,
\end{equation}
в которой матрица $A$ --- симметрическая, т.е. ее элементы удовлетворяют равенствам $A_{ij}=a_{ji}$ и $|A|\ne0$. Представим матрицу $A$ в виде произведения двух транспонированных между собой треугольных матриц
\begin{equation}\label{22}
A=T'T,
\end{equation}
где
$$T=\begin{pmatrix}
t_{11}&t_{12}&\ldots&t_{1n}\\
0&t_{22}&\ldots&t_{2n}\\
\hdotsfor{4}\\
0&0&\ldots&t_{nn}\end{pmatrix},\quad
T'=\begin{pmatrix}
t_{11}&0&\ldots&0\\
t_{12}&t_{22}&\ldots&0\\
\hdotsfor{4}\\
t_{1n}&t_{2n}&\ldots&t_{nn}\end{pmatrix}.$$
Перемножая матрицы $T'$ и $T$, получаем следующие уравнения:
$$t_{1i}t_{1j}+t_{2i}t_{2j}+\ldots+t_{ii}t_{ij}=a_{ij},\quad i\le j.$$
Отсюда последовательно находим:
\begin{equation}\label{33}
\begin{gathered}
t_{11}=\sqrt{a_{11}},\quad t_{1j}=\frac{a_{1j}}{t_{11}},\quad j>1,\\
t_{ii}=\sqrt{a_{ii}-\sum_{k=1}^{i-1}t_{ki}^2},\quad 1<i\le n,\\
t_{ij}=\frac{a_{ij}-\displaystyle\sum_{k=1}^{i-1}t_{ki}t_{kj}}{t_{ii}},\quad i<j.
\end{gathered}
\end{equation}

В силу того, что
$$|A|=|T'||T|=t_{11}^2t_{22}^2\ldots t_{nn}^2\ne0,$$
все элементы $t_{ii}\ne0$, и, значит, величины \eqref{33} имеют смысл. Если $t_{ii}^2<0$, то элементы $t_{ij}$ будут мнимыми. Метод применим и в этом случае.

После представления матрицы $A$ в виде \eqref{22} система \eqref{11} может быть записана в виде
$$T'Tx=b.$$
Последняя система эквивалентна двум системам
$$T'y=b,\quad Tx=y,$$
или в раскрытом виде:
$$\begin{cases}\arraycolsep=0.05em \begin{array}{lll}
t_{11}y_1=b_1,&\\
t_{12}y_1+t_{22}y_2=b_2,&\\
\hdotsfor{1}&\\
t_{1n}y_1+t_{2n}y_2+\ldots+&t_{nn}y_n=b_n
\end{array}\end{cases}$$
и
$$\begin{cases}\arraycolsep=0.05em \begin{array}{llll}
t_{11}x_1+&t_{12}x_2&+\ldots+&t_{1n}x_n=y_1,\\
&t_{22}x_2&+\ldots+&t_{2n}x_n=y_2,\\
&&\hdotsfor{2}\\
&&&t_{nn}x_n=y_n.
\end{array}\end{cases}$$
Отсюда последовательно находим:
\begin{equation}\label{44}
\begin{cases}y_1=\dfrac{b_1}{t_{11}},\\
y_i=\dfrac{b_i-\displaystyle\sum_{k=1}^{i-1}t_{ki}y_k}{t_{ii}},\quad i>1
\end{cases}
\end{equation}
и
\begin{equation}\label{55}
\begin{cases}x_n=\dfrac{y_n}{t_{nn}},\\
x_i=\dfrac{y_i-\displaystyle\sum_{k=i+1}^nt_{ik}x_k}{t_{ii}},\quad i<n.
\end{cases}
\end{equation}

Таким образом, первоначально \underline{прямым ходом} метода квадратного корня находят коэффициенты $t_{ij}$ и $y_i$, а затем \underline{обратным ходом} находятся неизвестные $x_i$. При этом вычисления заносят в таблицу, приведенную в примере, применяя контроль с помощью сумм.

Число операций, необходимых для нахождения решения системы \eqref{11} по методу квадратного корня, имеет порядок $\sim n^3/3$ \cite{1}.

\underline{Пример}. Методом квадратного корня решить систему уравнений:
$$\begin{cases}\arraycolsep=0.05em \begin{matrix}
3x_1&+&0,1123x_2&-&0,1425x_3&-&0,2513x_4&=&-2,1202,\\
0,1123x_1&+&4x_2&+&0,2357x_3&+&0,1273x_4&=&0,6012,\\
-0,1425x_1&+&0,2357x_2&+&5x_3&-&0,2090x_4&=&-3,1723,\\
-0,2513x_1&+&0,1273x_2&-&0,2090x_3&+&3x_4&=&2,0200.
\end{matrix}&\end{cases}$$

\underline{Решение.} Записываем коэффициенты системы $a_{ij}$ и свободные члены $b_i$ в начальный раздел А таблицы I и подставим столбец $\Sigma$, равный сумме всех элементов в каждой строке. Затем приступаем к заполнению раздела Б. Находим элементы $t_{ik}$ по формулам \eqref{33} и $y_i$ по формулам \eqref{44}. Для получения элементов $\ov y_i$ надо столбец свободных членов заменить на столбец $\Sigma$. Проверка на этапе Б состоит в том, что полученные значения $\ov y_i$ должны равняться сумме всех остальных чисел в данной строке. На этапе В по формулам \eqref{55} находим значения $x_i$. Используя вместо $y_i$ значения $\ov y_i$, находим $\ov x_i$. Проверка на этапе В заключается в том, что значения $\ov x_i$ должны быть на единицу больше значений $x_i$.

\newpage

\begin{flushright}
Таблица I
\end{flushright}

\begin{center}
\begin{tabular}{c|r|r|r|r|r|r}
\hline
Разделы&\multicolumn{1}{c|}{$a_{i1}$}&\multicolumn{1}{c|}{$a_{i2}$}&
\multicolumn{1}{c|}{$a_{i3}$}&\multicolumn{1}{c|}{$a_{i4}$}&\multicolumn{1}{c|}{$b_i$}&
\multicolumn{1}{c}{$\Sigma$}\\
\hline
&3\hphantom{,0000}&0,1123&-0,1425&-0,2513&-2,1202&0,5983\\
&0,1123&4\hphantom{,0000}&0,2357&0,1273&0,6012&5,0765\\
\raisebox{6pt}[0pt][-6pt]{А}&-0,1425&0,2357&5\hphantom{,0000}&-0,2090&-3,1723&1,7119\\
&-0,2513&0,1273&-0,2090&3\hphantom{,0000}&2,0200&4,6870\\
\hline
&\multicolumn{1}{c|}{$t_{i1}$}&\multicolumn{1}{c|}{$t_{i2}$}&
\multicolumn{1}{c|}{$t_{i3}$}&\multicolumn{1}{c|}{$t_{i4}$}&\multicolumn{1}{c|}{$y_i$}&
\multicolumn{1}{c}{$\ov y_i$}\\
\hline
&1,7321&0,0648&-0,0823&-0,1451&-1,2241&0,3451\\
&&1,9989&0,1206&0,0684&0,3404&2,5284\\
\raisebox{6pt}[0pt][-6pt]{Б}&&&2,2313&-0,1027&-1,4853&0,6433\\
&&&&1,7215&0,9681&2,6897\\
\hline
&-0,6971&0,1897&-0,6398&0,5624&\multicolumn{1}{c|}{$x_i$}&\\
\cline{2-6}
\raisebox{6pt}[0pt][-6pt]{В}&0,3029&1,1897&0,3602&1,5624&\multicolumn{1}{c|}{$\ov x_i$}&\\
\hline
\end{tabular}

\bigskip

Варианты систем для решения\\
по методу квадратного корня
\end{center}
\begin{tabular}{ll}
$(3,0000-h)x_1+0,1123x_2-0,1425x_3+(-0,2513+h)x_4$&\\
&\hspace{-74pt}$=-2,1202+h,$\\
$0,1123x_1+(4,0000+h)x_2+0,2357x_3+0,1273x_4=0,6012-h,$&\\
$-0,1425x_1+0,2357x_2+(5,0000-h)x_3-(0,2090+h)x_4$&\\
&\hspace{-74pt}$=-3,1723+h,$\\
$(-0,2513+h)x_1+0,1273x_2-(0,2090+h)x_3+(3,0000-h)x_4$&\\
&\hspace{-64pt}$=2,0200-h,$
\end{tabular}

\bigskip

$h=0,0013N$, $1\le N\le747$.

\section{МЕТОД ПРОГОНКИ}
\setcounter{equation}{0}

Рассмотрим систему с ``трехдиагональной'' матрицей вида:
\begin{equation}\label{111}
\arraycolsep=0.1em\begin{bmatrix}
-b_1&c_1&0&0&\ldots&0&0&0\\
a_2&-b_2&c_2&0&\ldots&0&0&0\\
0&a_3&-b_3&c_3&\ldots&0&0&0\\
\hdotsfor{8}\\
0&0&0&0&\ldots&a_{n-1}&-b_{n-1}&c_{n-1}\\
0&0&0&0&\ldots&0&a_n&-b_n\end{bmatrix}
\begin{bmatrix}x_1\\x_2\\x_3\\..\\x_{n-1}\\x_n\end{bmatrix}=
\begin{bmatrix}d_1\\d_2\\d_3\\..\\d_{n-1}\\d_n\end{bmatrix}
\end{equation}
Для решения такой системы по методу Гаусса требуется около $2n^3/3$ операций. Существует, однако, специальный метод --- \underline{метод прогонки}, предназначенный для решения таких трехдиагональных систем, в котором для получения решения требуется всего около $9n$ операций \cite{1}. Таким образом, метод прогонки дает значительный выигрыш в скорости решения систем (для системы размерности $10\times10$ приблизительно в 7,5 раз). 

Метод прогонки состоит из двух этапов. \underline{Этап 1 (прямой ход)} --- нахождение ``прогоночных коэффициентов'' $\xi_i$, $\eta_i$ ($i=1,2,\ldots,n$)
\begin{equation}\label{222}
\begin{gathered}
\xi_1=\eta_1=0,\quad\xi_2=c_1/b_1,\quad\eta_2=-d_1/b_1,\\
\xi_3=c_2/(b_2-a_2\xi_2),\quad\eta_3=(a_2\eta_2-d_2)/(b_2-a_2\xi_2),\\
\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\\
\xi_{i+1}=c_i/(b_i-a_i\xi_i),\quad\eta_{i+1}=(a_i\eta_i-d_i)/(b_i-a_i\xi_i),\\
\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots
\ldots\ldots\ldots\ldots\\
\xi_n=c_{n-1}/(b_{n-1}-a_{n-1}\xi_{n-1}),\\
\eta_n=(a_{n-1}\eta_{n-1}-d_{n-1})/(b_{n-1}-a_{n-1}\xi_{n-1}),\\
\xi_{n+1}=0,\quad\eta_{n+1}=(a_n\eta_n-d_n)/(b_n-a_n\xi_n).
\end{gathered}
\end{equation}
Особенностью формул \eqref{222} является вычисление ``последующих'' величин $\xi_{i+1}$, $\eta_{i+1}$ по уже найденным $\xi_i$, $\eta_i$. Попутно можно найти определитель трехдиагональной матрицы системы \eqref{111}:
$$\det A=(a_1\xi_1-b_1)(a_2\xi_2-b_2)\ldots(a_n\xi_n-b_n).$$
\underline{Этап 2 (обратный ход)} --- нахождение решения системы \eqref{111} по формулам:
\begin{multline}\label{333}
x_n=\eta_{n+1},\quad x_{n-1}=\xi_nx_n+\eta_n,\quad x_{n-2}=\xi_{n-1}x_{n-1}+\eta_{n-1},\ldots,\\
x_i=\xi_{i+1}x_{i+1}+\eta_{i+1},\ldots,x_1=\xi_2x_2+\eta_2.
\end{multline}

Для некоторых матриц метод прогонки может приводить к существенному накоплению ошибок округления при счете и к искажению вследствие этого полученного решения. Однако показано, что этот эффект отсутствует при условии преобладания диагональных элементов матрицы:
$$|b_i|>|a_i|+|c_i|\quad(i=1,\ldots,n).$$

Метод прогонки широко используется при приближенном решении многих задач математической физики (задачи теории упругости, теории теплопроводности и др.) \cite{2,3}.

Пример. Решить методом прогонки систему:
$$\begin{cases}\arraycolsep=0.05em \begin{matrix}
-2x_1&+&x_2&&&&&=&1,\\
\hphantom{-2}x_1&-&4x_2&+&2x_3&&&=&2,\\
&&x_2&-&5x_3&+&x_4&=&3,\\
&&&&x_3&-&4x_4&=&0.
\end{matrix}&\end{cases}$$

Составим таблицу коэффициентов:
\begin{center}
\begin{tabular}{c|c|c|c|c}
\hline
\multicolumn{1}{c|}{$i$}&\multicolumn{1}{c|}{$a_i$}&
\multicolumn{1}{c|}{$b_i$}&\multicolumn{1}{c|}{$c_i$}&\multicolumn{1}{c}{$d_i$}\\
\hline
1&0&2&1&1\\
\hline
2&1&4&2&2\\
\hline
3&2&5&1&3\\
\hline
4&1&4&0&0\\
\hline
\end{tabular}
\end{center}

Результаты расчета по прямому ходу (формулы eqref{222}), а затем по обратному ходу метода прогонки (формулы eqref{333}) оформим в виде таблицы:

\bigskip

\begin{center}\begin{tabular}{c|c|c|c|c||c}
\hline
\multicolumn{1}{c|}{$i$}&\parbox[c][27pt]{2.48cm}{$\scriptstyle\xi_i=\frac{c_{i-1}}
{b_{i-1}-a_{i-1}\xi_{i-1}}$}&
\parbox[c][27pt]{2.0cm}{$\scriptstyle\eta_i=\\[-2pt]\frac{a_{i-1}\eta_{i-1}-d_{i-1}}{b_{i-1}-
a_{i-1}\xi_{i-1}}$}&
\multicolumn{1}{c|}{$\scriptstyle b_i-a_i\xi_i$}&\multicolumn{1}{c||}{$\scriptstyle a_i\eta_i-d_i$}&\\
\hline
1&0&0&2&-1&-1.20792\\
\hline
2&0.5&-0.5&3.5&-2.5&-1.41585\\
\hline
3&0.57143&-0.71426&3.85714&-4.42858&-1.22772\\
\hline
4&0.25926&-1.14815&3.74071&-1.14815&-0.30693\\
\hline
5&0&-0.30693&&&\parbox[c][12pt]{2.6cm}{$\scriptstyle x_i=\xi_{i+1}x_{i+1}+\eta_{i+1}$}\\
\hline
\multicolumn{5}{c||}{прямой ход}&обратный ход\\
\hline
\end{tabular}
\end{center}

\bigskip

Варианты систем для решения методом прогонки
$$\begin{cases}
\arraycolsep=0.05em\begin{matrix}
[-5+(-1)^N/N]x_1+2x_2&=&2+(-1)^N,\\
2x_1+[-7+2(-1)^N/N]x_2-2x_3&=&1,\\
-3x_2+[-9-3/N]x_3+x_4&=&3-(-1)^N,\\
-2x_3+[-11+(-1)^N]x_4&=&4
\end{matrix}\end{cases}$$
($N=1,2,\ldots$).

\renewcommand{\bibname}{ЛИТЕРАТУРА}
\begin{thebibliography}{11}
\bibitem{1} Калиткин~Н.Н. Численные методы. М.: Наука, 1978.
\bibitem{2} Тихонов~А.Н., Самарский~А.А. Уравнения математической физики. М.: Наука, 1966.
\bibitem{3} Самарский~А.А. Введение в теорию разностных схем. М.: Наука, 1971.
\end{thebibliography}
\end{document}