[rus] computational_mathematics.tex

\documentclass[a4paper]{article}
\usepackage{fontspec} 
\usepackage{polyglossia}
\setmainlanguage{russian} 
\setotherlanguage{english}
\newfontfamily{\cyrillicfont}{Times New Roman}

\usepackage{mathtools}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage[colorinlistoftodos]{todonotes}


\title{Введение в вычислительную математику}
\author{MIPT DIHT}
\begin{document}
\maketitle

\section{Билет №1}
\subsection{Численное дифференцирование. Простейшие формулы численного дифференцирования.}
Функция заменяется таблицей значений. Производная $$\frac{df}{dx} \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}$$ заменяется $$f'(x) \approx \frac{f(x + h) - f(x)}{h}$$
Пусть функция $f(x)$ имеет достаточное число производных, требуется вычислить ее производную $f'(x)$ в данной точке х. Задачу отыскания h содержащую предельный переход, можно заменить приближенно задачами вычисления по одной из формул
$$f'(x) \approx \frac{f(x + h) - f(x)}{h}$$
$$f'(x) \approx \frac{f(x) - f(x - h)}{h}$$
$$f'(x) \approx \frac{f(x + h) - f(x - h)}{2h}$$
Для замены производной f"(x) можно воспользоваться формулой
$$f''(x) \approx \frac{f(x + h) - 2f(x) + f(x - h)}{h^2}$$

\subsection{Метод неопределенных коэффициентов для вывода формул численного дифференцирования.}
Считаем что сетка равномерная и для первой производной:
$$ f'(x_j) \approx \frac{1}{h} \sum_{\substack{k=-l}}^m \alpha_k f(x_j +kh)$$
l точек слева от рассматриваемого $x_j$ и m справа. $\alpha_k$ - неопределенные коэффициенты. Формула может быть односторонней(l=0 или m=0)
Пусть надо приблизить с точностью до $O(h^{l+m})$
$$ \frac{1}{h} \sum_{\substack{k=-l}}^m \alpha_k f(x_j+kh) = \frac{1}{h}f(x_j)\sum \alpha_k + f'(x_j)\sum k\alpha_k + f''(x_j)\sum \frac{k^2}{2}\alpha_kh + \ldots + f^{(n)}(x_j) \sum \alpha_k \frac{k^n}{n!} h^{n-1} + \ldots$$
Требуем выполнения условий:
$$ \sum \alpha_k = 0;\ \sum k\alpha_h = 1;\ \ldots \sum \alpha_k \frac{k^n}{n!}=0 $$
Получаем СЛАУ с матрицей:
$$ \begin{pmatrix}
1 & 1 & \ldots & 1 \\
l & -l+1 & \ldots & m \\
l^2 & (l-1)^2 & \ldots & m^2 \\
l^3 & (1-l)^3 & \ldots & m^3 \\
\ldots
\end{pmatrix}$$
Детерминант Вандермонда => существует единственный набор коэффициентов $\alpha$ позволяющий найти производную с нужным приближением
Для второй производной почти аналогично:
$$ f''(x_j) \approx \frac{1}{h^2} \sum_{\substack{k=-l}}^m \alpha_k f(x_j +kh)$$
\subsection{Порядок аппроксимации формул численного дифференцирования.}
$\triangleright$ \textbf{Def:} Порядок аппроксимации – показатель степени h в главном члене погрешности 
\subsection{Оптимальный шаг сетки численного дифференцирования.}
Для вычисления оптимального шага найдем минимум суммарной ошибки как функцию шага сетки $\frac{M_2}{2} - \frac{2k\varepsilon}{h^2} \rightarrow$
$$ h_{опт}=2 \sqrt{\frac{k\varepsilon}{M_2}} $$
В случае с большей точностью: $M_3=\max_{\substack{x \in [a;b]}} |f'''(x)|$ и суммарна погрешность:
$$ \Delta = \frac{M_3h^2}{3} + \frac{k\varepsilon}{h} \rightarrow h_{опт}=\sqrt[3]{\frac{3k\varepsilon}{M_3}}$$

\section{Билет №2}
\subsection{Постановка задачи интерполяции.}
Заданы точки $x=x_0 \ldots x=x_n$, значения в этих точках $f(x_0) \ldots f(x_n)$ и таблица значений ф-ции f(x) в этих точках
Задача: найти алгебраический интерполяционный многочлен $P_n(x,f,x_0 \ldots x_n): \ P_n(x) = c_nx^n + \ldots +c_0$, принимающий в узлах заданные значения и степени не выше n
\subsection{Полиномиальная интерполяция, ее существование и единственность.}
$\triangleright$ \textbf{Th:} Пусть заданы $x_0 \neq \ldots \neq x_n,\ f(x_0) \ldots f(x_n). \ \exists !$ многочлен $P_n(x) = P_n(x,f,x_0 \ldots x_n)$ степени не выше n, принимающий в заданных узлах заданные значения \\
	$\circ$ Сначала покажем, что существует единственный, затем построим.
	Если бы было два многочлена $P_n^1(x),\ P_n^2(x) \rightarrow R_n(x) = P_n^1(x)-P_n^2(x)$ обращается в ноль в n+1 точке. Но $\forall R_n(x) \not\equiv 0$ имеет столько корней, какова его степень $\rightarrow R_n(x) \equiv 0 \rightarrow P_n^1(x)=P_n^2(x)$.
	Введем вспомогательные многочлены $$l_k(x) = \frac{(x-x_0) \ldots (x-x_{k-1})(x-x_{k+1}) \ldots (x-x_n)}{(x_k-x_0) \ldots (x_k-x_{k-1})(x_k-x_{k+1}) \ldots (x_k-x_n)}$$ 
	$$l_k(x_j)=\begin{cases} 1,  & \mbox{if }x_j = x_k\\ 0, & \mbox{if }x_j \neq x_k \end{cases}$$
	$$P_n(x) = P_n(x,f,x_0 \ldots x_n) = f(x_0)l_0(x) + \ldots + f(x_n)l_n(x)$$ – искомый интерполяционный многочлен. Каждое слагаемое степени не выше n $\rightarrow$ весь многочлен степени не выше n и очевидно выполнено $P_n(x_j)=f(x_j)$
	$\bullet$
\subsection{Интерполяционный полином в форме Лагранжа.}
	$$P_n(x) = P_n(x,f,x_0 \ldots x_n) = f(x_0)l_0(x) + \ldots + f(x_n)l_n(x)$$ из док-ва

\section{Билет №3}
\subsection{Постановка задачи интерполяции.}
Заданы точки $x=x_0 \ldots x=x_n$, значения в этих точках $f(x_0) \ldots f(x_n)$ и таблица значений ф-ции f(x) в этих точках
Задача: найти алгебраический интерполяционный многочлен $P_n(x,f,x_0 \ldots x_n): \ P_n(x) = c_nx^n + \ldots +c_0$, принимающий в узлах заданные значения и степени не выше n
\subsection{Разделенные разности.}
Пусть f(x) в точках $x_a, x_b, x_c \ldots$ принимает $f(x_a), f(x_b), f(x_c) \ldots$. $f(x_k)$ – разностное отношение нулевого порядка в точке. Разностное отношение первого порядка: $$ f(x_k,x_t) = \frac{f(x_t) - f(x_k)}{x_t - x_k}$$
Разностное отношение n-1 порядка: $$ f(x_0 \ldots x_n) = \frac{f(x_1 \ldots x_n) - f(x_0 \ldots x_{n-1})}{x_n - x_0}$$
$\triangleright$ \textbf{Свойства}
\begin{enumerate}
	\item $P_n(x,f,x_0 \ldots x_n) = P_{n-1}(x,f,x_0 \ldots x_{n-1}) + f(x_0 \ldots x_n)(x-x_0)\ldots (x-x_{n-1})$
	\item $P_n(x,f,x_0 \ldots x_n) = c_nx^n + \ldots + c_0$, т е $f(x_0 \ldots x_n) = c_n$
	\item $f(x_0 \ldots x_n)=0 \iff f(x_0) \ldots f(x_n)$ – значения $Q_m, m<n$
\end{enumerate}
\subsection{Интерполяционный полином в форме Ньютона.}
Интерполяционный многочлен в форме Ньютона: $$P_n(x, f, x_0 \ldots x_n) = f(x_0) + (x-x_0)f(x_0,x_1) + \ldots + (x-x_0)\ldots (x-x_{n-1})f(x_0 \ldots x_n) $$
\subsection{Обусловленность задачи интерполяции и константа Лебега.}
Пусть узлы интерполяции $x_0 \ldots x_n$ лежат на $a \leq x \leq b$, пусть $f(x_0) \ldots f(x_n)$ заданные числа. Соответствующий интерп. мн-н: $P_n(x) = P_n(x,f,x_0 \ldots x_n) = P_n(x,f)$. Приданим значениям $f(x_j)$ возмущение $\delta f(x_j), \ P_n(x,f) \rightarrow P_n(x, f + \delta f) = P_n(x,f) + P_n(x, \delta f)$.
Мера чувствительности интерп. мн-на к возмущению – наименьшее $L_n: \ \forall \delta f$ $$\max_{\substack{x \in (a,b)}} |P_n(x,\delta f)| \leq L_n \max_{\substack{j}} |\delta f(x_j)|$$
$L_n = L_n(x_0 \ldots x_n,a,b)$ – константы Лебега. В случае равномерно расположенных узлов: $$2^{n-1} > L_n > 2^{n-3} \frac{1}{\sqrt{n-1}} \frac{1}{n-3/2} $$ т е чувствительность рез-та интерполяции резко возрастат при росте n  

\section{Билет №4}
\subsection{Теорема об остаточном члене интерполяционного полинома (с доказательством)}
$\triangleright$ \textbf{Def:} Остаточный член интерполяции: $ R_N(t) = f(t) - L_N(t)$\\
$\triangleright$ \textbf{Th:} Пусть функция на отрезке имеет N+1 ограниченную производную. Тогда
$$ R_N(t) = \frac{1}{(N+1)!} \prod_{\substack{j=0}}^N(t-t_j)f^{(N+1)}(\xi), \ \xi \in [a,b] $$
	$\circ$ 
	Рассмотрим функцию $$ \psi(x)=f(x)-L_N(x) - R_N(t) \frac{(x-t_0)\ldots (x-t_N)}{(t-t_0)\ldots (t-t_N)} $$
	Имеет N+1 производную и не меньше N+2 нулей на [a,b]: $x=t_n (n=0\ldots N)$ и $x=t$ из определения остаточного члена. Между двумя нулями ф-ции есть один ноль ее производной => $\exists N+1$ нулей $\psi'(x)$. По аналогии с второй, третьей... => $\exists \xi \in [a,b]: \psi^{(N+1)}(\xi)=0$
	$$ \psi^{(N+1)}(\xi) = f^{(N+1)}(\xi) - L^{(N+1)}(\xi) - \frac{d^{N+1}}{dx^{N+1}} \bigg[ R_N(t)\frac{(x-t_0)\ldots (x-t_N)}{(t-t_0)\ldots (t-t_N)} \bigg]_\xi $$
	$$ L^{(N+1)}(\xi)=0;\ \psi^{(N+1)}(\xi)=0;\ \frac{d^{N+1}}{dx^{N+1}} \bigg[ R_N(t)\frac{(x-t_0)\ldots (x-t_N)}{(t-t_0)\ldots (t-t_N)} \bigg]_{x=\xi} = \frac{(N+1)!}{\prod_{\substack{j=0}}^N(t-t_j)} $$
	$$ => \ f^{(N+1)}(\xi)-R_N(t)\frac{(N+1)!}{\prod_{\substack{j=0}}^N(t-t_j)} = 0 \ => \ R_N(t) = \frac{f^{(N+1)}(\xi)}{(N+1)!}\prod_{\substack{j=0}}^N(t-t_j) \bullet $$

\subsection{Оценка остаточного члена на равномерной сетке.}
$\triangleright$ \textbf{Th:} Пусть $t_n=n\tau, \ \tau=(b-a)/N$ на равномерной сетке. Тогда 
$$ |R_N(t)| \leq \frac{\tau^{N+1}}{N+1}C,\ C=\max_{\substack{t \in [a,b]}} |f^{(N+1)}(t)| $$
	$\circ$ 
		$$t=t_k+\alpha t;\ \alpha \in [0,1]\ => \ t-t_n=k\tau+\alpha\tau-n\tau \ => \ \prod_{\substack{n=0}}^N (t-t_n)=\tau^{N+1}\prod_{\substack{n=0}}^N (k+\alpha-n)$$
		$$ \prod_{\substack{n=0}}^N |k+\alpha-n| \leq N! \ => \ |R_N(t)|\leq \frac{\tau^{N+1}}{N+1} \max_{\substack{\xi \in [a,b]}} |f^{(N+1)}(\xi)| \bullet $$

\section{Билет №5}
\subsection{Полиномы Чебышева, их свойства.}
$$ T_k(x) = cos(k\varphi) = cos(k)arccos(x) \ (cos(\varphi)=x)$$
$\triangleright$ \textbf{Th:} $T_k(x)$ – многочлены степени k=0,1,... При этом $T_0(x) = 1, T_1(x) = x, \ldots$
$$ T_{k+1}(x) = 2x T_k(x) - T_{k-1}(x) $$
	$\circ$ 
	Очевидно: $T_0(x) = cos(0) = 1; \ T_1(x) = cos(arccos(x)) = x$
	$$cos (k+1)\varphi = 2 cos\varphi cos k\varphi - cos(k-1)\varphi$$, что в случае $\varphi=arccosx$ переходит в формулу из теоремы.
	Докажем что многочлен – степени k с помощью индукции по k. k=0, k=1 уже доказано. Фиксируем $k \ge 1$ . Пусть доказано для $T_j(x)$. Тогда обе части рекуррентной формулы есть многочлен степени k+1
	$\bullet$
\subsection{Применение полиномов Чебышева при построении узлов интерполяции.}
$$ Q_n(cos \varphi, sin\varphi, F) = \sum_{\substack{k=0}}^n a_kcos k\varphi \equiv P_n(x,f), \ P_n(x,f) = \sum_{\substack{k=0}}^n a_k T_k(x)$$
$$ a_0 = \frac{1}{n+1} \sum_{\substack{m=0}}^n f_m = \frac{1}{n+1} \sum_{\substack{m=0}}^n f_mT_0(x_m)$$
$$ a_k = \frac{2}{n+1} \sum_{\substack{m=0}}^n f_m cos k\varphi_m = \frac{2}{n+1} \sum_{\substack{m=0}}^n f_mT_k(x_m) $$
Т е $P_n(x,f)$ - алгебраический многочлен степени не выше n, принимающий в узлах интерполяции $x_m = cos\varphi_m$ заданные значения $f(x_m) = f_m$ \\
Отметим, что точки $$\varphi_m = \frac{\pi}{n+1}m + \frac{\pi}{2(n+1)} $$ являются нулями $cos(n+1)\varphi$, а $x_m=cos\varphi_m$ нулями $T_{n+1}(x) = cos(n+1)\varphi$. Т. е. интерп. мн-н $P_n(x,f)$ реализует алгебр. интерп. ф-ции в точках, являющихся нулями многочлена Чебышева


\section{Билет №6}
\subsection{Понятие сплайн-интерполяции}

$\triangleright$ \textbf{Def:} На отрезке [a,b] задана система узловых точек $\{t_n\}, n=0..N$. Сплайн $S_m(t)$ - определенная на [a,b] функция, имеющая l непрерывных проиводных и являющаяся на каждом интервале $[t_{n-1}, t_n]$ многочленом степени m \\
$\triangleright$ \textbf{Def:} Дефект сплайна d=m-l - разность между степенью сплайна и показателем его гладкости \\
$\triangleright$ \textbf{Def:} Кубический сплайн дефекта 1, интерполирующий заданную ф-цию на [a,b] - ф-ция S(t):
\begin{enumerate}
	\item $S(t_n) = f(t_n)$
	\item $S(t) \in C^2[a,b]$
	\item $\forall [t_{n-1},t_n] S(t)$ является кубическим многочленом
	\item Краевые условия \begin{enumerate}
		\item S'(a) = f'(a), S'(b) = f'(b)
		\item S''(a) = f''(a), S''(b) = f''(b)
		\item S(a) = S(b); S'(a) = S'(b)
	\end{enumerate}
\end{enumerate}

\subsection{Процедура построения кубического сплайна показателя гладкости два.}
$\triangleright$ \textbf{Th:} Интерполяционный кубический сплайн, удовлетворяющий условим 1-3 и одному из условий 4 существует и единственен\\
	$\circ$ 
	Пусть S(z) на каждом отрезке представлен как 
	$$ S(z) = f_n(1-z)^2(1+2z) +f_{n+1}z^2(3-2z) + m_n\tau_nz(1-z)^2 -m_{n+1}\tau_nz^2(1-z)$$
	где $\tau_n = t_{n+1}-t_n, \ z = \frac{t-t_n}{\tau_n}, \ m_n = S'(t_n) \rightarrow$
	$$ S''(t) = \frac{(f_{n+1} - f_n)(6-12z)}{\tau_n^2} + m_n \frac{6z-12}{\tau_n} + m_{n+1} \frac{6z-2}{\tau_n}$$
	$$ S''(t_n+0) = 6 \frac{f_{n+1}-f_n}{\tau_n^2} - \frac{4m_n}{\tau_n} - \frac{2m_{n+1}}{\tau_n}$$
	$$ S''(t_n-0) = -6 \frac{f_n-f_{n-1}}{\tau_{n-1}^2} + \frac{2m_{n-1}}{\tau_{n-1}} + m_{n+1}\frac{4m_n}{\tau_{n-1}}$$
	Условие непрерывности второй производной:
	$$r_nm_{n-1}+2m_n+s_nm_{n+1}=c_n$$
	$$ c_n=3 \big(s_n\frac{f_{n+1}-f_n}{\tau_n}+r_n\frac{f_n-f_{n-1}}{\tau_{n-1}}, \ s_n=\frac{\tau_{n-1}}{\tau_{n-1}+\tau_n},\ r_n=1-s_n$$
	После добавления краевых условий получаем систему N+1 уравнений
	\begin{itemize}
		\item Для краевых условий 1-го типа:
		$$ m_0=f_0'$$
		$$ f_nm_{n-1} + 2m_n + s_nm_{n+1} = c_n$$
		$$ m_N=f_N'$$
		\item Для краевых условий 2-го типа (заданы производные)
		$$ 2m_0 + m_1 = 3\frac{f_1-f_0}{\tau_0} - \frac{\tau_0}{2}f_0'' $$
		$$ r_nm_{n-1} + 2m_n + s_nm_{n+1} = c_n $$
		$$ m_{N-1} + 2m_N = 3\frac{f_N-f_{N-1}}{\tau_{N-1}} + \frac{\tau_{N-1}}{2}f_N'' $$
	\end{itemize}
	Аналогично для третьего типа краевых уравнений. Во всех случаях матрицы трехдиагональные, симметричные, положительно определенные => решение СЛАУ существует и единственно
	$\bullet$

\section{Билет №7}
\subsection{Численное интегрирование.}
$$a=x_0<x_1\ldots <x_n=b$$
$$P_k(x)=P_k(x,f,x_0 \ldots x_n)$$ – на каждом отрезке многочлен степени не выше k. Приближенное рав-во для вычисление интеграла
$$ \int_{a}^b f(x)dx \approx \int_{a}^b P_k(x,f,x_0 \ldots x_n) dx = \int_{a}^{x_1} P_k dx + \int_{x_1}^{x_2} P_k dx + \ldots \int_{x_{n-1}}^b P_k dx$$
$\triangleright$ \textbf{Th:} Пусть f(x) имеет ограниченную производную порядка k+1: $\max_{\substack{x\in [a,b]}} |f^{(k+1)}(x)|=M_{k+1}$ и $h=\max_{0 \leq i \leq n-1} |x_{i+1} - x_i| \rightarrow$
$$ \big| \int_{a}^b f(x)dx - \int_{a}^b P_k dx \big| \leq const |b-a|M_{k+1}h^{k+1}$$
	$\circ$ 
		$$\max_{\substack{x \in [a,b]}} |f(x)-P_k| \leq const M_{k+1}h^{k+1} $$
	$\bullet$ 
\subsection{Квадратурные формулы прямоугольников, трапеций, Симпсона}
\begin{itemize}
	\item Формула трапеций: равноотстоящие узлы $x_{i+1}-x_i=\frac{b-a}{n}=h$. В этом случае интеграл на отрезке есть площадь трапеции:
	$$ \int_{x_i}^{x_{i+1}} P_1dx = \frac{b-a}{n} \frac{f_i+f_{i+1}}{2}$$
	$$ \int_{a}^b f(x)dx \approx \int_{a}^b P_1 dx  = \frac{b-a}{n} \big(\frac{f_0}{2} + f_1 + \ldots + f_{n-1} + \frac{f_n}{2} \big)$$
	\item Формула Симпсона: n=2k; $x_{j+1}-x_j=\frac{b-a}{n}=h$ \\
	$\forall [x_{2j};x_{2j+2}]$ заменим f(x) квадратичным интерполяционным многочленом в форме Лагранжа:
	$$ P_2(x,f_{2j},f_{2j+1},f_{2j+2}) = f_{2j} \frac{(x-x_{2j+1})(x-x_{2j+2})}{(x_{2j}-x_{2j+1})(x_{2j}-x_{2j+2})} + \\ + f_{2j+1} \frac{(x-x_{2j})(x-x_{2j+2})}{(x_{2j+1}-x_{2j})(x_{2j+1}-x_{2j+2})} + f_{2j+2} \frac{(x-x_{2j})(x-x_{2j+1})}{(x_{2j+2}-x_{2j})(x_{2j+2}-x_{2j})}$$
	По формуле Ньютона-Лейбница: $$\int_{x_{2j}}^{x_{2j+2}} P_2 dx = \frac{b-a}{n} (f_{2j} + 4f_{2j+1} + f_{2j+2}) \approx  \int_{x_{2j}}^{x_{2j+2}} f(x) dx$$
	Формула Симпсона:
	$$ \int_{a}^b f(x) dx \approx \sum_{\substack{k=0}}^n \int_{x_k}^{x_2k} f(x)dx = S_n(f) = \frac{b-a}{n} (f_0 + 4f_1 + 2f_2 + \ldots + 2f_{n-1} + f_n) $$
\end{itemize}
\subsection{Оценки погрешности квадратных формул.}
$\triangleright$ \textbf{Th:} Пусть ф-ция на отрезке имеет ограниченную третью производную: $ max |f^{(3)}(x)| = M_3$. Тогда погрешность ф-лы Сипсона:
$$ \big|\int_{a}^b f(x)dx - S_n(f) \big| \leq \frac{(b-a)M_3}{12}h^3$$
	$\circ$ 
		Оценим разность $R_2(x) \equiv f(x) - P_2(x) \forall x \in [a,b]$. Каждый из этих $x \in [x_{2j};x_{2j+2}]$, но на этом отрезке R есть погрешность и выражается: 
		$$ R_2(x) = \frac{f^{(3)}(\xi)}{3!} (x-x_{2j})(x-x_{2j+1})(x-x_{2j+2})$$
		$$ |R_2(x)| \leq  \frac{M_3}{3!} \max_{\substack{x \in [x_{2j};x_{2j+2}]}} |(x-x_{2j})(x-x_{2j+1})(x-x_{2j+2})| \leq \frac{M_3}{12}h^3$$
		Из произвольности $x \in [a,b]$
		$$ \max_{\substack{x \in [a,b]}} |R_2(x)| \leq \frac{M_3}{12}h^3$$
	$\bullet$ \\
$\triangleright$ \textbf{Th:} Пусть ф-ция на отрезке имеет ограниченную четвертую производную: $ max |f^{(4)}(x)| = M_4$. Тогда погрешность ф-лы Сипсона:
$$ \big|\int_{a}^b f(x)dx - S_n(f) \big| \leq \frac{(b-a)M_4}{18}h^4$$

\section{Билет №8}
\subsection{Норма матрицы. Согласованные и подчиненные нормы. Примеры подчиненных матричных норм}
Нормы вектора:
\begin{itemize}
	\item Кубическая: $ ||u||_1 = \max_{\substack{1\leq i \leq n}} |u_i| $
	\item Октаэдрическая: $ ||u||_2 = \sum_{\substack{i=0}}^n |u_i| $
	\item Евклидова: $ ||u||_3 = \bigg( \sum_{\substack{i=0}}^n |u_i|^2 \bigg)^{1/2} = (u,u)^{1/2}$
\end{itemize}
$A \in Mat(n \times n)$; нелинейное преобразование $v = Au,\ v,u \in L^n$. Норма матрицы (подчиненная норме вектора): $$ ||A|| = \sup_{||u||\neq 0} \frac{||Au||}{||u||} $$
Свойства: \begin{itemize}
	\item $ ||A+B|| = ||A|| + ||B||$
	\item $ ||\lambda A|| = |\lambda| ||A||$
	\item $ ||AB|| \leq ||A|| ||B||$
	\item $ ||A|| = 0 \iff A=0 $
\end{itemize}
Норма матрицы согласована с нормой вектора, если $ ||Au|| \leq ||A|| ||u||$ \\
Согласованные с введенными выше нормамами векторов нормы матриц:
\begin{itemize}
	\item $ ||A||_1 = \max_{\substack{1 \leq i \leq n}} \sum_{\substack{j=1}}^n |a_{ij}|$
	\item $ ||A||_2 = \max_{\substack{1 \leq j \leq n}} \sum_{\substack{i=1}}^n |a_{ij}|$
	\item $ ||A||_3 = \sqrt{\max_{\substack{1 \leq i \leq n}} \lambda^i (A*A)} $
\end{itemize}
\subsection{Теорема об относительной погрешности решения системы линейных алгебраических уравнений (с доказательством)}
$\triangleright$ \textbf{Th:} Пусть правая часть и невырожденная матрица СЛАУ вида $Au=f,\ u,f \in L^n$ получили приращение $\Delta f, \Delta A$. Пусть существует обратная матрица и выполнены условия $||A|| \neq 0, \mu \frac{||\Delta A||}{||A||} < 1, (\mu=||A|| ||A^{-1}||)$. Тогда оценка погрешности:
$$ \frac{||\Delta u||}{||u||} \leq \frac{\mu}{1-\mu \frac{||\Delta A||}{||A||}} \bigg( \frac{||\Delta f||}{||f||} + \frac{||\Delta A||}{||A||} \bigg)$$
	$\circ$ 
		$$ (A + \Delta A)(u+\Delta u)=f+\Delta f \rightarrow \Delta u = A^{-1}(\Delta f - \Delta Au - \Delta A \Delta u)$$
		$$ ||\Delta u|| \leq ||A^{-1}|| ||\Delta f|| + ||A^{-1}|| ||\Delta A|| ||u|| + ||A^{-1}|| ||\Delta A|| ||\Delta u|| $$
		$$ ||\Delta u|| \leq ||A^{-1}|| \frac{||\Delta f||}{||f||} ||f|| + ||A^{-1}|| \frac{||\Delta A||}{||A||} ||A|| ||u|| + ||A^{-1}|| \frac{||\Delta A||}{||A||} ||A|| ||\Delta u||  $$
		Введя обозначение $\mu (A)=||A|| ||A^{-1}||$:
		$$ ||\Delta u || \big( 1- \mu \frac{||\Delta A||}{||A||} \big) \leq \mu \frac{||\Delta f|| ||f||}{||f|| ||A||} + \mu \frac{||\Delta A||}{||A||} ||u|| \leq $$
		$$ \leq \mu \frac{||\Delta f||}{||f||} ||u|| + \mu \frac{||\Delta A||}{||A||}||u|| = \mu \bigg( \frac{||\Delta f||}{||f||} + \frac{||\Delta A||}{||A||} \bigg) ||\Delta u||$$
	$\bullet$

\subsection{Число обусловленности матрицы}
$\triangleright$ \textbf{Def:} $\mu(A) = ||A|| ||A^{-1}||$ - число обусловленности матрицы. Определяет, насколько погрешность входных данных может повлиять на решение системы. $\mu \geq 1$

\section{Билет №9}
\subsection{Метод Гаусса решения систем линейных алгебраических уравнений}
Рассматривается система:
$$
\begin{cases}
	a_{11}u_1 + \ldots + a_{1n}u_n &= f_1 \\
	\ldots \\
	a_{n1}u_1 + \ldots + a_{nn}u_n &= f_n 
\end{cases} $$
\begin{itemize}
	\item Прямой ход: положим $a_{11} \neq 0$ и исключим $u_1$ из всех ур-ний начиная со второго (прибавив первое, домноженное на $-a_{j1}/a_{11} = \eta_{j1}$). Получаем эквввалентную систему
	$$\begin{cases}
		a_{11}u_1 + \ldots + a_{1n}u_n &= f_1,\\
		\ldots \\
		a_{n2}^1 u_2 + \ldots + a_{nn}^1u_n &= f_n^1
	\end{cases}$$ 
	$$
	a_{ij}^1 = a_{ij} - \eta_{i1}a_{1j} ; \ f_i^1 = f_i - \eta_{i1}f_1
	$$
Продолжая по аналогии приходим к системе с треугольной матрицей:
$$\begin{cases}
		a_{11}u_1 + \ldots + a_{1n}u_n = f_1,\\
		\ldots \\
		a_{nn}^{n-1} u_n = f_n^{n-1}
	\end{cases}$$
	\item Обраный ход: из последнего ур-ния находим $u_n$, подставляя в предпоследнее находим $u_{n-1}$ и т.д.
	$$u_n = \frac{f_n^{n-1}}{a_{nn}^{n-1}} $$
	$$u_k = \frac{1}{a_{kk}^{k-1}} \big( f_k^{k-1} - a_{k,k+1}^{k-1}u_{k+1} - \ldots - a_{kn}^{k-1}u_n \big) $$ 
\end{itemize}
\subsection{Связь с LU-разложением матриц}
A1 - матрица системы после исключения 1-го неизвестного:
$$ A_{11} = \begin{pmatrix}
a_{11} & a_{12} & \ldots & a_{1n} \\
0 & a_{22}^1 & \ldots & a_{2n}^n \\
\ldots \\
0 & a_{n2}^1 & \ldots & a_{nn}^1
\end{pmatrix}$$
Введем матрицу 
$$ N_1 = \begin{pmatrix}
1 & 0 & 0 & \ldots & 0 \\
-\eta_{21} & 1 & 0 & \ldots & 0 \\
-\eta_{31} & 0 & 1 & \ldots & 0 \\
\ldots \\
-\eta_{n1} & 0 & 0 & \ldots & 1
 \end{pmatrix} $$
Очевидно $A_1=N_1A; \ f_1=N_1f$. После n-1 шага:
$$
A_{n-1} = \begin{pmatrix}
a_{11} & a_{12} & \ldots & a_{1n} \\
0 & a_{22}^1 & \ldots & a_{2n}^1 \\
\ldots \\
0 & 0 & \ldots & a_{nn}^{n-1}
\end{pmatrix}
N_{n-1} = \begin{pmatrix}
1 & 0 & \ldots & 0 & 1 \\
\ldots \\
0 & 0 & \ldots & -\eta_{n,n-1} & 1
\end{pmatrix}
$$ 
Введем матрицы:
$$ N_1^{-1} = \begin{pmatrix}
1 & 0 & 0 & \ldots & 0 \\
\eta_{21} & 1 & 0 & \ldots & 0 \\
\eta_{31} & 0 & 1 & \ldots & 0 \\
\ldots \\
\eta_{n1} & 0 & 0 & \ldots & 1
\end{pmatrix} $$
$$
N_2^{-1} = \begin{pmatrix}
1 & 0 & 0 & \ldots & 0 \\
0 & 1 & 0 & \ldots & 0 \\
0 & \eta_{32} & 1 & \ldots & 0 \\
\ldots \\
0 & \eta_{n2} & 0 & \ldots & 1
\end{pmatrix}$$
$$
N_{n-1}^{-1} = \begin{pmatrix}
1 & 0 & \ldots & 0 & 0 \\
0 & 1 & \ldots & 0 & 0 \\
\ldots \\
0 & 0 & \ldots & \eta_{n,n-1} & 1
\end{pmatrix}$$
Введем обозначения $U=A_{n-1}, L=N_1^{-1}\ldots N_{n-1}^{-1}$
$$ L = \begin{pmatrix}
1 & 0 & 0 & \ldots & 0 \\
\eta_{21} & 1 & 0 & \ldots & 0 \\
\eta_{31} & \eta_{32} & 1 & \ldots & 0 \\
\ldots \\
\eta_{n1} & \eta_{n2} & \eta_{n3} & \ldots & 1
\end{pmatrix} $$
=> A=LU - LU-разложение матрицы

\subsection{Выбор ведущего элемента}
Выбор главного элемента о столбцам: перед исключением $u_1$ ищется $\max_{\substack{i}} |a_{i1}|$. Пусть максимум при i=k => меняем местами 1-е и k-е ур-ния. Дальше ищем $\max_{\substack{i}} |a_{i2}^1|$ и т.д.

\section{Билет №10}
\subsection{Итерационные методы решения систем линейных алгебраических уравнений.}
Метод простых итераций: $Au=f => u=Bu+F, B=E- \tau A, F=E-\tau f$. Построим последовательное приближение, $u_0$ - начальное приближение. При подстановке возникает невязка $r_0=f-Au_0$. Вычислив, уточняем решение: $u_1=u_0+\tau r_0 \ldots u_{k+1}=Bu_k+F$

\subsection{Достаточное условие (с доказательством) и критерий (без доказательства) сходимости метода простых итераций.}
$\triangleright$ \textbf{Th: (достаточное условие сходимости)} Итерационный процесс сходится к решению U СЛАУ Au=F со скоростью геометрической прогрессии при условии $||B|| \leq q <1$ \\
	$\circ$ 
	Пусть U точное решение. $ u_k-U=B(u_{k-1}-U)$. Обозначим $\varepsilon_k = u_k-U => \varepsilon_k=B\varepsilon_{k-1}$
	$$ ||u_k-U|| = ||\varepsilon_k|| \leq ||B|| ||\varepsilon_{k-1}|| \leq q||\varepsilon_{k-1}|| \leq \ldots \leq q^k||\varepsilon_0||=q^k||u_0-U||$$
	где $0<q<||B||$
	$\bullet$ \\
$\triangleright$ \textbf{Th: (критерий)} Пусть СЛАУ имет единственное решение. Тогда для сходимости итерационного метода необходимо и достаточно чтобы все с.з. матрицы В по абс. величине были меньше 1

\section{Билет №11}
\subsection{Метод Якоби решения систем линейных алгебраических уравнений: матричная и покомпонентная формулировка}
A=L+D+U, где L,U - нижняя и верхняя треугольные матрицы с нулями на диагонали, D - диагональная матрица. СЛАУ может быть переписана:
$$ Lu + Du + Uu = f$$
$$ Lu_k + Du_{k+1} + Uu_k =f$$ - итерационный метод Якоби
$$ u_{k+1} = -D^{-1}(L+U)u_k + D^{-1}f$$ - описывает итерационный процесс если положить $ B=-D^{-1}(L+U), F=D^{-1}f$
$$ u_1^{k+1}=-(a_{12}u_2^k + a_{13}u_3^k + \ldots + a_{1n}u_n^k - f_1)/a_{11}$$
$$ u_2^{k+1}=-(a_{21}u_1^k + a_{23}u_3^k + \ldots + a_{1n}u_n^k - f_2)/a_{22}$$
$$ u_n^{k+1}=-(a_{n1}u_1^k + \ldots + a_{n,n-1}u_{n-1}^k - f_n)/a_{nn} $$
\subsection{Достаточное условие и критерий сходимости (оба с доказательством)}
$\triangleright$ \textbf{Th:(достаточное условие)} Итер. мтеод сходится к решению соотв. СЛАУ, если выполнено условие диагонального преобладания:
$$ |a_{ii}| > \sum_{\substack{j=1 \\ j \neq i}}^n |a_{ij}|$$
	$\circ$ 
		Условие означает что в любой строке матрицы перехода сумма модулей меньше 1 => хотя бы одна из норм матрицы меньше 1, выполняется условие сходимости метода простых итераций 
	$\bullet$ \\

$\triangleright$ \textbf{Th: (критерий)} необходимо и достаточно чтобы все корни уравнения по модулю не превосходили 1:
$$ \begin{vmatrix} 
\lambda a_{11} & a_{12} & \ldots & a_{1n} \\
a_{21} & \lambda a_{22} & \ldots & a_{2n} \\
\ldots \\
a_{n1} & a_{n2} & \ldots & \lambda & a_{nn}
\end{vmatrix} = 0 $$
	$\circ$ 
		Из диагональности D:
		$$ det(B-\lambda E) = det[-D^{-1}(L+U) - \lambda E] = det(-D^{-1}) det[(L+U) + D\lambda] $$
		С. З. $B=-D^{-1}(L+U)$ - корни $def[(L+U)+D\lambda]=0$ (в соответствии с критерием сходимости они по модулю <1)
	$\bullet$

\section{Билет №12}
\subsection{Метод Зейделя решения систем линейных алгебраических уравнений: матричная и покомпонентная формулировка}
A=L+D+U, где L,U - нижняя и верхняя треугольные матрицы с нулями на диагонали, D - диагональная матрица. СЛАУ может быть переписана:
$Lu_{k+1} + Du_{k+1} + Uu_k = f $
$$ Lu_{k+1} + Du_{k+1} + Uu_k =f$$ - итерационный метод Зейделя
$$ u_{k+1} = -(L+D)^{-1}Uu_k + (L+D)^{-1}f$$ - описывает итерационный процесс если положить $ B=-(L+D)^{-1}U, F=(L+D)^{-1}f$
$$ u_1^{k+1}=-(a_{12}u_2^k + a_{13}u_3^k + \ldots + a_{1n}u_n^k - f_1)/a_{11}$$
$$ u_2^{k+1}=-(a_{21}u_1^{k+1} + a_{23}u_3^k + \ldots + a_{1n}u_n^k - f_2)/a_{22}$$
$$ u_n^{k+1}=-(a_{n1}u_1^{k+1} + \ldots + a_{n,n-1}u_{n-1}^{k+1} - f_n)/a_{nn} $$
\subsection{Достаточное условие и критерий сходимости (оба с доказательством)}
$\triangleright$ \textbf{Th:(достаточное условие)} Итер. метод сходится к решению соотв. СЛАУ, если А вещественная симметричная положительно определенная \\
	$\circ$ 
		Проверка, что выполнение условий $ A = \lambda L + D + \lambda L^{T}$ воечет выполнение условия сходимости итер. метода с матрицей перехода $(\lambda L+D)^{-1}\lambda L^{T}$
	$\bullet$ \\

$\triangleright$ \textbf{Th: (критерий)} необходимо и достаточно чтобы все корни уравнения по модулю не превосходили 1:
$$ \begin{vmatrix} 
\lambda a_{11} & a_{12} & \ldots & a_{1n} \\
\lambda a_{21} & \lambda a_{22} & \ldots & a_{2n} \\
\ldots \\
\lambda a_{n1} & \lambda a_{n2} & \ldots & \lambda & a_{nn}
\end{vmatrix} = 0 $$
	$\circ$ 
		Из диагональности D:
		$$ det(B-\lambda E) = det[-D^{-1}(L+U) - \lambda E] = det(-D^{-1}) det[(L+U) + D\lambda] $$
		С. З. $B=-D^{-1}(L+U)$ - корни $def[(L+U)+D\lambda]=0$ (в соответствии с критерием сходимости они по модулю <1)
	$\bullet$

\section{Билет №13}
\subsection{Теорема об эквивалентности задач минимизации квадратичной функции и решения системы линейных алгебраических уравнений (с доказательством)}
$\triangleright$ \textbf{Th:} Пусть A=A* > 0 => $\exists ! v \in L^n$\\ придающий наименьшее значение квардартичному функционалу \Phi(u) = (Au,u) - (2f,u) + c, являющийся решением СЛАУ Au=f \\
	$\circ$ 
		СЛАУ имеет единственное решение поскольку А является невыроженным оператором в силу положительной определенности. Покажем что в таком случе при Av-f=0 для любого вектора $\Delta$ имеет место \Phi(u+$\Delta$) > \Phi(v), то есть при u=v достигается минимум функционала:
		$$ \Phi(v+\Delta) = (A(v+\Delta), v+\Delta) - 2(f, v+\Delta) + c = (Av+A\Delta, v+\Delta)-2(f,v+\Delta) +c = $$
		$$ = (Av,v)+(Av,\Delta)+(A\Delta,v)+(A\Delta,\Delta)-2(f,v)-2(f,\Delta) +c = ((Av,v)+2(Av,\Delta)+(A\Delta,\Delta)-2(f,v)-2(f,\Delta)+c =$$
		$$= [(Av,v)-2(f,v)+c]+2(Av,\Delta)-2(Av,\Delta-2(f,\Delta)+(A\Delta, \Delta) = \Phi(v) + 2(Av-f,\Delta)+(A\Delta,\Delta)=\Phi(v)+(A\Delta,\Delta)>\Phi(v)$$
		Элемент доставляет минимальное значение функционалу энергии - он является решением СЛАУ Av=f. В точке минимума grad \Phi(u)=2Au-2f=0 => эквивалентность вариац. задачи и задачи решения СЛАУ
	$\bullet$
\subsection{Методы решения систем линейных алгебраических уравнений, основанные на минимизации функции – метод наискорейшего спуска и метод минимальных невязок.}
\begin{itemize}
	\item Метод наискорейшегошего спуска: нахождение следующего приближения смещением в направлении градиента функционала
	$$ \Phi(u)=(Au,u)-2(f,u) $$
	$$ u_{k+1}=u_k - \alpha grad\Phi(u_k) $$
	А - положительно определенная симметричная матрица, $\alpha$ - параметр определяемый из заданных условий, например из условия минимума величины 
	$$ Ф[u_k-\alpha_k grad \Phi(u_k)] $$
	Так как grad \Phi(u)=2(Au-f) => $ u_{k+1} = u_k - \tau_k(Au_k-f) $, где $\tau_k=2\alpha_k$
	$\tau_k$ - итерационный параметр, определяемый из условий минимума $\Phi(\tau_k,u_{k+1})$: 
	$$ 0=2(Au_{k+1}-f, (u_{k+1})\tau_k) = -2(Au_{k+1}-f,Au_k-f)$$
	Подставляя $u_{k+1}: \ (Au_k-f-\tau_kA(Au_k-f),Au_k-f)=0 => (Au_k-f,Au_k-f)-\tau_k(A(Au_k-f),Au_k-f)=0$
	$$\tau_k=\frac{(Au_k-f,Au_k-f)}{(A(Au_k-f),Au_k-f)}=\frac{(r_k,r_k)}{(Ar_k,r_k)} $$ где $r_k=Au_k-f$ - вектор невязки
	\item Метод минимальных невязок: $u_{k+1} = u_k -\tau_k r_k, r_k=Au_k-f$
	$\tau_k$ на каждой итерации выбирается так чтобы минимизировать евклидову норму $r_{k+1}$. Итерационный процесс может быть представлен в терминах невязок: $r_{n+1}=r_n+\tau_n Ar_n$ =>
	$$ (r_{k+1}, r_{k+1}) = (r_k,r_k) - 2\tau_k(Ar_k,r_k) + \tau_k^2(Ar_k,Ar_k) $$
	Для отыскания минимума невязки на след. итерации приравниваем к нулю производную по $\tau_k$ последнего выражения итерации:
	$$-2(Ar_k,r_k)+2\tau_k(Ar_k,Ar_k) = 0 \rightarrow \tau_k = \frac{(Ar_k,r_k)}{(Ar_k,Ar_k)} $$
\end{itemize}

\section{Билет №14}
\subsection{Переопределенные системы линейных алгебраических уравнений}
Каноническая запись:
$$ \begin{cases}
a_{11}x_1 + \ldots + a_{1s}x_s = f1 \\
\ldots \\
a_{n1}x_1 + \ldots + a_{ns}x_s = f_n \end{cases}
$$. 
Введем пространства $R^s, \ R^n$ состоящие из элементов $x=[x_1 \ldots x_s]^T, \ f=[f_1 \ldots f_n]^T$. Обозначим A - матрицу коэффициентов системы. Тогда систему можно записать в виде Ax=f. Введем в $R_n$ скалярное умножение, положив $$ (f,g)^{(n)} = \sum_{\substack{k=1}}^n f_kg_k $$
Также положительно определенной симметричной матрице В сопоставим скалярное умножение $$[f,g]_B=(Bf,g)$$
$\triangleright$ \textbf{Def:} Фиксируем В=В* > 0, B:$R^n \rightarrow R^n$. Введем ф-цию от х: $$ \Phi(х) = [Ax-f,Ax-f]_B $$
Примем за обобщенное решение системы вектор $x_B$, минимизирующий эту квадратичную функцию\\

\subsection{Задачи, приводящие к переопределенным системам. }


\subsection{Определение обобщенного решения переопределенных систем линейных алгебраических уравнений}
$\triangleright$ \textbf{Th:} Пусть столбцы матрицы А ЛНЗ, тогда существует строго одно обощенное решение $x_B$ системы и оно является классическим решением системы уравнений $$ A^*BAx = A^*Bf$$\\
	$\circ$ Введем обозначение $\alpha_k \in R^n$ для k-го столбца матрицы А. Матрица $C=A^*BA \in Mat(s \times s)$
	$$ c_{ij} = (\alpha_i,B\alpha_j)^{(n)}=(B\alpha_i,\alpha_j)^{(n)} = [a_i,a_j]_B; \ \ c_{ij}=c_{ji} => C=C^* $$
	$$ C(\xi, \xi)^{(s)} > 0, \ \xi \in R^s, \xi \neq 0$$
	$$A\xi = \xi_1 \alpha_1 + \ldots + \xi_s \alpha_s \neq 0$$
	$$0<[A\xi,A\xi]_B=(BA\xi,A\xi)^{(n)}=(A^*BA\xi,\xi)=(C\xi,\xi)^{(s)}$$
	Решение единственно в силу невырожденности С. Докажем, что оно является единственным обобщенным решением системы, то есть
	$$ \forall x = x_B + \delta \ (\delta \in R^s) \ => \ \Phi(x_B+\delta)>\Phi(x_B)$$
	Заметим: $[Ax_B-f,A\delta]_B=(B(Ax_b-f),A\delta)^{(n)}=(A^*BAx_B-A^*Bf,\delta)^{(s)}=0$
	$$\Phi(x_b+\delta)=[A(x_B+\delta)-f,A(x_B+\delta)-f]_B=[Ax_B-f,Ax_b-f]_B-2[Ax_b-f,A\delta]_B+[A\delta,A\delta]_B=\Phi(x_b)-2[Ax_b-f,A\delta]_B+(C\delta,\delta)^{(s)}=\Phi(x_B)+(C\delta,\delta)^{(s)} > \Phi(x_B)
	\bullet $$

\section{Билет №15}
\subsection{Решение нелинейных алгебраических уравнений методами простых итераций и релаксации}
\begin{itemize}
	\item Метод простых итераций  \\
	F(x)=0; Пусть знаем, что искомый корень лежит х в интервале [a,b]. Можно положить $$ f(x) = x-\alpha(x)F(x) $$, $\alpha(x)$ - произвольная не обращающаяся в ноль на отрезке. Для отыскания решения из интервала зададим $x_0$ и вычислим $x_1, \ x_2, \ldots$ по формуле $x_p = f(x_{p-1})$ \\
	$\triangleright$ \textbf{Th:} Пусть f(x) непрерывна и при заданном $x_0$ сходится к некоторому $\hat{x}$ из интервала U=\{a<x<b\}. Тогда $\hat{x}$ - корень f(x)\\
	$\circ$ 
		$$ \lim_{\substack{n -> \inf}} x_{n+1}=\lim_{\substack{n -> \inf}} f(x_n); \ Ho \lim_{\substack{n -> \inf}} f(x_n)= f(\lim_{\substack{n -> \inf}}x_n) \ => \ \lim_{\substack{n -> \inf}} x_{n+1}= f\lim_{\substack{n -> \inf}} x_n \iff f(\hat{x})=\hat{x}
	\bullet $$
	\item Метод релаксации: \\
	Без ограничения общности рассмотрим скалярный случай. Положим $F(u) = u + \tau f(u)$ и построим итерационный процесс $u_{k+1} = u_k + \tau f(u_k), \ u_0=a$. Тогда $F'(u)=1+\tau f'(u)$ и $\tau$ берем из условия $|F'(u)|<1$. \\
	В частности, если F'(u)=0 => $\tau=-[f'(u)]^{-1}, \ u_{k+1} = u_k - [f'(u)]^{-1}f(u_k)$
\end{itemize}
\subsection{Критерий сходимости простых итераций (с доказательством).}
$\triangleright$ \textbf{Th:} Пусть уравнение x=f(x) имеет корень из области U и пусть отображение f(x) - сжимающее в U с коэффициентом сжатия q. Тогда решение единственно в области U и $\exists R>0:$ при выборе $x_0$ из условия $|x-x_0|<R$ все члены последовательности будут определены и так что:
$$ |\hat{x}-x_n| \leq q |\hat{x}-x_0| $$
То есть имеет место сходимость $x_n$ к $\hat{x}$ со скоростью геометрической прогресии со знаменателем q\\
	$\circ$ 
	Докажем единственность. Пусть существует еще решение $\hat{x'}$. Тогда в силу сжимаемого отображения 
	$$ |f(\hat{x})-f(\hat{x'})| \leq |q(\hat{x}-\hat{x'})|$$
	Но так как $f(\hat{x})=\hat{x}; \ f(\hat{x'})=\hat{x'} \ => \ |\hat{x'} - \hat{x}| < |\hat{x'} - \hat{x}|$ \\
	Единственность доказана. Далее берем достаточное малое R: $U(\hat{x},R)=\{|\hat{x}-\hat{x'}|<R \} \subset U$
	$$x_0 \in U(\hat{x},R) => |\hat{x} - x_1|=|f(\hat{x}) - f(x_0)| \leq q|\hat{x}-x_0| \leq qR < R
	\bullet $$
\subsection{Метод Ньютона решения нелинейных алгебраических уравнений и систем.}
\begin{itemize}
	\item Случай одного уравнения\\
	Зададим $x_0$. Пусть найдено приближение $x_n$ к корню $\hat{x}$ ур-ния F(x)=0
	$$ F(x) \approx F(x_n) + F'(x_n)(x-x_n) \ => \ F(x_n)+F'(x_n)(x-x_n)=0 $$
	Решение является приближением $x_{n+1}$
	$$ x_{n+1} = x_n - [F'(x_n)]^{-1}F(x_n) $$
	Считая $F'(x) \neq 0 \ => \ x=f(x); \ f(x)=x-[F'(x)]^{-1}F(x)$. Очевидно $\frac{df}{dx}_{x=\hat{x}} = 0$. 
	Пусть f''(x) непрерывна => $$\forall 0<q<1 \exists U_{\hat{x}}: |f'(x)| \leq q \forall x \in U_{\hat{x}}$$
	f(x) - сжимающее отобрадение => последовательность сходится к $\hat{x}$
	\item Случай системы уравнений
	Рассмотрим систему F(x)=0. Пусть в области U есть решение $\hat{x}$ и пусть найдено приближение $x_n$
	$$ F(x) \approx F(x_n) + \frac{dF(x)}{dx}_{x=x_n}(x-x_n) \ => \ F(x_p) + \frac{dF(x)}{dx}_{x=x_p}(x-x_n) = 0 $$
	Решение: $x_{p+1} = x_p - [\frac{dF(x_p)}{dx}]^{-1}F(x_p)$. Можно перейти к равносильной системе:
	$$ x=f(x); \ f(x)=x-[\frac{dF(x)}{dx}]^{-1}F(x) $$
\end{itemize}

\section{Билет №16}
\subsection{Численное решение задачи Коши для обыкновенных дифференциальных уравнений первого порядка}

$$ \frac{du(t)}{dt}=f(t,u), \ t>0, u(0)=u_0 $$
$t \in [0,T]$. Построим сетку ${t_n=n\tau}, \ \tau$ - шаг интегрирования
Дифференциальная задача записывается как L(u)=F, где
$$ L(u) = \begin{cases}
	\frac{du}{dt} - f(t,u), & t>0\\
	u_0, &  t=0 \end{cases} \ \

	F= \begin{cases}
	0, & t>0\\
	u_0, & t=0\end{cases}$$
$L_\tau(u^\tau)=F$ - аппроксимация задачи


$Lu=f$. Решение разностной схемой $L_hu^{(h)}=f^{(h)}$. При подстановке сеточной функции: $$ L_h[u]_h=f^{(h)}+\delta f^{(h)} $$
Задача Коши: $$ \frac{dx}{du}-G(x,u)=0,\ x\in[0,1],u(0)=a $$
Выбираем сетку: $0=x_0<x_1<\ldots<x_{N-1}<x_N=1, \ x_n=nh, h=\frac{1}{N}$ \\
\textbf{Схема Рунге-Кутта}:\\
Задача: $$ \frac{du}{dx}-G(x,u)u=\phi(x) $$
	$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - G(x_n,u_n), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
При данном $u_n$ требуется найти $u_{n+1}$ в точке $x_{n+1}=x_n+h$. Задаем целое l и выписываем:
$$ k_1=G(x_n,u_n)$$
$$ k_2=G(x_n + \alpha h, u_n+\alpha hk_1) $$
$$ \ldots $$
$$ k_l = G(x_n + \gamma h, u_n + \gamma hk_{l-1}) $$

$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - (p_1 k_1 + \ldots + p_l k_l), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
$\alpha, \ldots \gamma, p_1, \ldots p_l$ подбираем так, чтобы при заданном l получить аппроксимацию наиболее высокой точности. \\
При имеющемся $u_n$ можем вычислить $k_1, \ldots, k_l, \ u_{n+1}=u_n+h(p_1k_1 + \ldots + p_l k_l)$
\subsection{Понятие сходимости разностной схемы на примере простейшего линейного уравнения и явной схемы Эйлера.}
$$ L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - G(x_n,u_n), & n=0\ldots N-1\\
	u_0=a, & Nh=1 \end{cases}$$
	-схема Эйлера, аппроксимируящая задачу $$ \frac{du}{dx} - G(x,y)=0, \ x \in [0,1], \ u(0)=a $$
	При известном $u_n: \ u_{n+1}=u_n+hG(x_n,u_n)$
$$ L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - \frac{1}{2}\big[G(x_n,y_n)+G(x_{n+1}, \hat{u}) \big] = 0, & n=0\ldots N-1\\
	u_0=a \end{cases}$$
	где $\hat{u}=u_n+hG(x_n,u_n)$ - схема Эйлера с пересчетом

$$ u(t+\tau) = u(t) + \int_{0}^t u'(t+\tau) d\tau $$
Аппроксимируем интеграл по формуле прямоугольников и заменяем на $\tau u'(t)$:
$$ u(t+\tau)=u(t)+\tau u'(t) = u(t)+\tau f(u,t)$$
$$ t=t_n, \ t+\tau = t_{n+1}, \ u(t)=u_n, \ u(t+\tau) = u_{n+1}$$
$$ \frac{u_{n+1}-u_n}{t} = f(t_n,u_n)$$

\section{Билет №17}
\subsection{Численное решение задачи Коши для обыкновенных дифференциальных уравнений первого порядка.}
$Lu=f$. Решение разностной схемой $L_hu^{(h)}=f^{(h)}$. При подстановке сеточной функции: $$ L_h[u]_h=f^{(h)}+\delta f^{(h)} $$
Задача Коши: $$ \frac{dx}{du}-G(x,u)=0,\ x\in[0,1],u(0)=a $$
Выбираем сетку: $0=x_0<x_1<\ldots<x_{N-1}<x_N=1, \ x_n=nh, h=\frac{1}{N}$ 
\textbf{Схема Рунге-Кутта}:\\
	$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - G(x_n,u_n), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
При данном $u_n$ требуется найти $u_{n+1}$ в точке $x_{n+1}=x_n+h$. Задаем целое l и выписываем:
$$ k_1=G(x_n,u_n)$$
$$ k_2=G(x_n + \alpha h, u_n+\alpha hk_1) $$
$$ \ldots $$
$$ k_l = G(x_n + \gamma h, u_n + \gamma hk_{l-1}) $$

$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - (p_1 k_1 + \ldots + p_l k_l), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
$\alpha, \ldots \gamma, p_1, \ldots p_l$ подбираем так, чтобы при заданном l получить аппроксимацию наиболее высокой точности. \\
При имеющемся $u_n$ можем вычислить $k_1, \ldots, k_l, \ u_{n+1}=u_n+h(p_1k_1 + \ldots + p_l k_l)$
\subsection{Понятие сходимости разностной схемы на примере простейшего линейного уравнения и схемы с центральной разностью.}
$$ \frac{u_{n+1}-u_{n-1}}{2\tau} = f(t_n,u_n)=\frac{1}{2}[f(t_{n-1},u_{n-1}) + f(t_{n+1},u_{n+1})] $$
$$ u'' = f'_t(t,u)+f'_u(t,u)u', \ u'''=f''_{tt}(t,u)+2f''_{tu}(t,u)u' +f''_{uu}(t,u)(u')^2+f'_u(t,u)u'', \ldots $$
$$ => u(t) \approx V_n(t) \equiv \sum_{\substack{i=0}}^I \frac{u^{(i)}(t_n)}{i!}(t-t_n), \ u_{n+1}=V_n(t_{n+1}) $$

\section{Билет №18}
\subsection{Численное решение задачи Коши для обыкновенных дифференциальных уравнений первого порядка}
$Lu=f$. Решение разностной схемой $L_hu^{(h)}=f^{(h)}$. При подстановке сеточной функции: $$ L_h[u]_h=f^{(h)}+\delta f^{(h)} $$
Задача Коши: $$ \frac{dx}{du}-G(x,u)=0,\ x\in[0,1],u(0)=a $$
Выбираем сетку: $0=x_0<x_1<\ldots<x_{N-1}<x_N=1, \ x_n=nh, h=\frac{1}{N}$ 
\textbf{Схема Рунге-Кутта}:\\
	$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - G(x_n,u_n), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
При данном $u_n$ требуется найти $u_{n+1}$ в точке $x_{n+1}=x_n+h$. Задаем целое l и выписываем:
$$ k_1=G(x_n,u_n)$$
$$ k_2=G(x_n + \alpha h, u_n+\alpha hk_1) $$
$$ \ldots $$
$$ k_l = G(x_n + \gamma h, u_n + \gamma hk_{l-1}) $$

$$L_hu^{(h)} = \begin{cases}
	\frac{u_{n+1}-u_n}{h} - (p_1 k_1 + \ldots + p_l k_l), & n=0\ldots N-1\\
	u_0=a, & \end{cases}$$
$\alpha, \ldots \gamma, p_1, \ldots p_l$ подбираем так, чтобы при заданном l получить аппроксимацию наиболее высокой точности. \\
При имеющемся $u_n$ можем вычислить $k_1, \ldots, k_l, \ u_{n+1}=u_n+h(p_1k_1 + \ldots + p_l k_l)$
\subsection{Пример неустойчивой схемы, аппроксимирующей исходную задачу.}

\section{Билет №19}
\subsection{Аппроксимация, устойчивость, сходимость разностных схем решения обыкновенных дифференциальных уравнений}
\begin{itemize}
	\item Сходимость\\
	Задача: $Lu=f$ в области D с границей Г. $D_h$ - сетка, $D_h \subset D \cup \Gamma, \ U_h$ - линейное нормированное пространство функций, $[u]_h \in U_h$ - решение на сетке
	$$ L_hu^{(h)} = f^{(h)}\ : \ ||[u]_h -u^{(h)}||_{U_h} \rightarrow 0 \ (h \rightarrow 0)$$
	$\triangleright$ \textbf{Def:} Сходимость порядка k относительно h: $||[u]_h -u^{(h)}||_{U_h} \leq ch^k, \ c=const$ \\
	\item Аппроксимация \\
	Разностная задача аппроксимирует исходную на решении u, если
	$$ L_hu^{(h)}=f^{(h)}+\delta f^{(h)}: \ ||\delta f^{(h)}||_{F_h} \rightarrow 0 $$
	$\triangleright$ \textbf{Def:} Аппроксимация порядка k относительно h: $||\delta f^{(h)}||_{F_h} \leq ch^k$
	\item Устойчивость \\
	Разностная краевая задача устойчива по определению, если $\exists \delta >0, h_0>0: \forall h<h_0 \forall \varepsilon^{(h)} \in F_h: ||\varepsilon^{(h)}||_{F_h} < \delta =>$
	$$ L_hz^{(h)} = f^{(h)}+\varepsilon^{(h)}$$ имеет ровно одно решение и $||z^{(h)}-u^{(h)}||_{U_h} \leq c||\varepsilon^{(h)}||_{F_h}$
	Разноcтная краевая задача устойчива: $\exists h_0>0: \forall 0<h<h_0 \forall f^{(h)}\in F_h$ она однозначно разрешима, причем $||u^{(h)}||_{U_h} \leq c||f^{(h)}||_{F_h}$
\end{itemize}
\subsection{Теорема Рябенького-Лакса.}
$\triangleright$ \textbf{Th:} Пусть разностная схема $L_hu^{(h)}=f^{(h)}$ апроксимирует задачу Lu=f на решении с порядком $h^k$ с устойчива => решение $u^{(h)}$ сходится к $[u]_h$, причем $$ ||[u]_h - u^{(h)}||_{U_h} \leq cc_1h^k $$
	$\circ$ 
	$$ \varepsilon^{(h)}=\delta f^{(h)},\ [u]_h=z^{(h)} \ => \ ||[u]_h - u^{(h)}||_{U_h} \leq c||\delta f^{(h)}||_{F_h}
	\bullet$$

\end{document}