
	\chapter*{Введение}
	\addcontentsline{toc}{chapter}{Введение}
	\myAddDate{09}{02}{09}
		\section*{Колесо Самарского}
		\addcontentsline{toc}{section}{Колесо Самарского}
		\includegraphics[scale=0.7]{wheel.png}
		
		При изучении объектов окружающего мира математическими методами используют
		прницип ``колеса Самарского'', изображенный на рисунке. В данном курсе
		рассматривается фаза ``разработка алгоритма'' этого принципа.
		
		
		
		\section*{Содержание
		курса}
		\addcontentsline{toc}{section}{Содержание курса}
		\begin{description}
			\item[Глава I] Численные методы линейной алгебры.
			\item[Глава II] Интерполирование и приближение функций.
  			\item[Глава III] Решение нелинейных уравнений и систем.
  			\item[Глава IV] Разностные схемы для уравнений математической физики.
  			\item[Глава V] Решение задачи Коши для обыкновенных дифференциальных
  			уравнений и систем обыкновенных дифференциальных уравнений.
		\end{description}
		\subsection{Список литературы}
		\begin{enumerate}
			\item Самарский А. А., Гулин А. В. ``Численные методы'' М. Наука 1983
			\item Самарский А. А. ``Теория разностных схем'' М. Наука 1983
			\item Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. ``Численные методы'' М. Наука 1973
			\item Самарский А. А. ``Введение в численные методы'' М. Наука 1982
			\item Калиткин Н. Н. ``Численные методы'' М. Наука 1978
			\item Самарский А. А., Николаев И. С. ``Методы решения сеточных уравнений''
			\item И. С. Березин, Н. П. Жидков ``Методы вычислений''
		\end{enumerate}
		%\vfill
		%next page
	\chapter{Численные методы линейной алгебры}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		\section{Введение}
		\myRemember{матрица, СЛАУ}
			Рассмотрим систему линейных алгебраических уравнений (СЛАУ) в матричном виде
			\begin{equation}
			\label{eq_1_1_1}
				Ax=f,
			\end{equation}
				где \(A\) --- матрица размера \( (m\times m) \), 
				\( |A|\neq 0, \)
				\[ x=(x_1, \dots , x_m)^T, \]
				\[ f=(f_1, \dots , f_m)^T. \]
			Из невырожденности матрицы \(A\) следует, что решение системы \eqref{eq_1_1_1} существует и единственно.
			Выделяют две группы методов поиска решения СЛАУ:
			\begin{enumerate}
				\item Прямые (точные) методы. Примеры: метод Гаусса (требует \( \sim m^3 \) действий), формула Крамера (требует \( \sim  m! \) действий), метод квадратного корня. Эти методы позволяют за конечное число действий получить точное решение.
				\item Итерационные (метод последовательных приближений).
					\[x_0\text{ --- первое приближение,}\]
					\[x_n \xrightarrow{n \rightarrow \infty} x. \]
					При работе с итерационными методами задача обычно ставится следующим образом: для данного \( \epsilon > 0 \) найти \( n_0(\epsilon) \) такое, что
					\[ |x_n-x|<\epsilon \: \forall n \geq n_0 \]
			\end{enumerate}
			Мы будем также рассматривать задачу на собственные значения. Она формулируется так: найти все такие числа \( \lambda \) и ненулевые векторы \( x \), что для данной матрицы \( A \) выполняется
			\begin{equation}
			\label{eq_1_1_2}
				Ax=\lambda x.
			\end{equation}
			
			\( \lambda \) называется собственным значением, \( x \) - собственным вектором матрицы \( A \).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		\section{Разложение матрицы на множители. Связь этого разложения с методом Гаусса}
		\myRemember{метод Гаусса (прямой ход, обратный ход)}
			\begin{equation}
			\label{eq_1_2_1}
				Ax=f,\: |A| \neq 0
			\end{equation}
			Подсчитаем число действий, необходимое для решения уравнения \eqref{eq_1_2_1} методом Гаусса. Действием будем считать умножение или деление.
		\begin{enumerate}
		\item Прямой ход метода Гаусса: 
			\begin{itemize}
				\item \( A \Rightarrow 
					 \begin{pmatrix}
						  1 & \times & \cdots & \times \\
						  0 & 1 & \cdots & \times \\
						  \vdots  & \vdots  & \ddots & \vdots  \\
						  0 & 0 & \cdots & 1
					 \end{pmatrix}
					\quad \frac{m^3-m}{3}\text{ действий}
					 \)
		
					
					Крестиками отмечены в общем случае ненулевые элементы.
				\item Преобразование правых частей: \( \frac{m(m+1)}{2} \text{ действий} \)
			\end{itemize}
		\item Обратный ход
			\begin{itemize}
				\item \( \frac{m(m-1)}{2} \text{ действий} \)
			\end{itemize}
		\item Всего \( \frac{m^3}{3}+m^2-\frac{m}{3} \) действий
		\end{enumerate}
		\subsection{Разложение матрицы на множители}
		Зададимся целью представить матрицу \( A \) в виде
			\begin{equation}
			\label{eq_1_2_2}
				A=B\cdot C, 
			\end{equation}
			где 
			\[ B=
 					 \begin{pmatrix}
						  b_{11} & 0 & \cdots & 0 \\
						  b_{21} & b_{22} & \cdots & 0 \\
						  \vdots  & \vdots  & \ddots & \vdots  \\
						  b_{m1} & b_{m2} & \cdots & b_{mm}
					 \end{pmatrix} \] --- нижнетреугольная матрица, 


			\[ C=
 					 \begin{pmatrix}
						  1 & c_{12} & \cdots & c_{1m} \\
						  0 & 1 & \cdots & c_{2m} \\
						  \vdots  & \vdots  & \ddots & \vdots  \\
						  0 & 0 & \cdots & 1
					 \end{pmatrix} \] --- верхнетреугольная матрица с единицами на главной диагонали.

		По формуле для элемента произведения матриц:
		\[ a_{ij}=\sum_{l=1}^m b_{il}c_{lj} \]
		Перепишем предыдущее выражение, выделив слагаемое с \( c_{ij} \):
		\[ a_{ij}=\sum_{l=1}^{i-1} b_{il}c_{lj}+b_{ii}c_{ij}+\sum_{l=i+1}^{m}b_{il}c_{lj} \]
		Из вида матрицы \( B \) следует, что
		\[ \sum_{l=i+1}^{m}b_{il}c_{lj}=0 \]
		Таким образом, предпологая, что  \( b_{ii} \neq 0 \), получим
		\begin{equation}
		\label{eq_1_2_3}
		 c_{ij}=\frac{a_{ij} - \sum \limits_{l=1}^{i-1} b_{il}c_{lj}}{b_{ii}},\quad i<j
		\end{equation}
		Теперь из формулы элемента произведения матриц выделим слагаемое с \( b_{ij} \):
		\[ a_{ij}=\sum_{l=1}^{j-1} b_{il}c_{lj}+b_{ij}c_{jj}+\sum_{l=j+1}^{m}b_{il}c_{lj} \]
		Из вида матрицы \( C \) следует, что
		\[ \sum_{l=j+1}^{m}b_{il}c_{lj}=0 \]
		Таким образом, можно записать:
		\begin{equation}
		\label{eq_1_2_4}
		 b_{ij}=a_{ij} - \sum \limits_{l=1}^{j-1} b_{il}c_{lj},\quad i \geq j
		\end{equation}
		Легко видеть, что формулы \eqref{eq_1_2_3} и \eqref{eq_1_2_4} позволяют  вычислить все элементы матриц \( B \) и \( C \).

