\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