%Лекция 21 by wictor
\section{Понятие устойчивости разностных методов}
	
	Рассмотрим задачу Коши:
	
	\begin{equation}
	\label{eq_5_4_1}
		\begin{cases}
        	\frac{du}{dt} = f(t, u(t)), \quad t>0, \\
        	u(0) = u_0.
        \end{cases}
	\end{equation}
	
	Рассмотрим для примера такую схему:
	$$ y_n = qy_{n-1},\quad q \in \mathbb{C}, \quad q = const, $$
	$$ n = 0, 1, \ldots;\quad y_0 \text{ задан.} $$
	
	Придадим $y_n$ возмущение $\delta_n$:
	$$ \tilde{y}_n = y_n + \delta_n. $$
	
	Тогда $ \tilde{y}_{n+1} = q\tilde{y}_n = q y_n + q \delta_n = y_{n+1} +
	\delta_{n+1},$ где $ \delta_{n+1} = q \delta_{n}. $
	
	Если $|q|>1,$ то $\delta_n$ нарастает, следовательно, об устойчивости говорить
	нельзя.
	
	Рассмотрим модельную задачу:
	\begin{equation}
	\label{eq_5_4_2}
		\begin{cases}
        	\frac{du}{dt} + \lambda u(t) = 0, \quad t>0, \\
        	u(0) = u_0.
        \end{cases}
	\end{equation}
	
	Ее решение имеет вид $ u(t) = u_0 e^{-\lambda t}.$ Если $\lambda > 0$, то
	|$u(t)| \leq |u_0|,$ т.е. имеет место устойчивость по начальному условию.
	
	Устойчивость --- внутреннее свойство разностной схемы. Разностная схема не
	обязательно сохраняет устойчивость исходной задачи.
	
	Рассмотрим явную схему Эйлера:
	\begin{equation}
	\label{eq_5_4_3}
		\begin{cases}
        	\frac{y_{n+1} - y_n}{\tau}  = f(t_n, y_n),  \\
        	y_0 = u_0.
        \end{cases}
	\end{equation}
	
	Запишем ее для модельной задачи:
	$$ \frac{y_{n+1} - y_n}{\tau} + \lambda y_n = 0. $$
	Выразим $y_{n+1}:$
	$$ y_{n+1} = y_n - \tau \lambda y_n = (1-\tau \lambda) y_n. $$
	Обозначим $ q = 1 - \tau \lambda.$ Тогда $y_{n+1} = q y_n.$
	Таким образом, для устойчивость необходимо, чтобы выполнялось $|q| \leq 1 $,
	т.е. $$ 1 - \tau \lambda \geq -1, $$
	$$ 0 < \tau \lambda \leq 2. $$
	Таким образом, для того, чтобы явная схема Эйлера была устойчивой (для
	модельной задачи), необходимо выполнение условия 
	\begin{equation}
	\label{eq_5_4_4}
		0 < \tau \leq \frac{2}{\lambda}.
	\end{equation}
	
	Это означает, что явная схема Эйлера является условно устойчивой (для
	модельной задачи).
	
	Рассмотрим неявную схему Эйлера:
	$$ \frac{y_{n+1} - y_n}{\tau}  = f(t_{n+1}, y_{n+1}). $$
	Перепишем ее:
	\begin{equation}
	\label{eq_5_4_5}
		y_{n+1} + \tau f(t_{n+1}, y_{n+1}) = y_n.
	\end{equation}

	Для решения нелинейного уравнения \eqref{eq_5_4_5} обычно применяется метод
	Ньютона, в качестве начального приближения для нахождения $y_{n+1}$ используют
	$y_n$. 
	
	Перепишем \eqref{eq_5_4_5} для модельной задачи:
	$$ y_{n+1} + \tau \lambda y_{n+1} = y_n, $$
	$$ (1 + \tau \lambda)y_n = t_{n+1}, $$
	$$ y_{n+1} = q y_n, \quad q = \frac{1}{1 + \tau \lambda}. $$
	Заметим, что $|q| < 1$ при $\tau > 0, \lambda > 0.$ Это значит, что
	неявная схема Эйлера является абсолютно устойчивой (для модельной задачи).
	
	Таким образом, для устойчивой дифференциальной задачи существуют как
	устойчивые, так и неустойчивые схемы.
	
	Рассмотрим произвольный $m$-шаговый разностный метод:
	\begin{equation}
	\label{eq_5_4_6}
		\sum \limits_{k=0}^m \frac{a_k}{\tau}y_{n-k} = \sum \limits_{k=0}^m b_k
	f_{n-k}, \quad y_0, \ldots, y_{m-1} \text{ заданы.}
	\end{equation}

	Запишем его для модельной задачи:
	\begin{equation}
	\label{eq_5_4_7}
		\sum \limits_{k=0}^m \frac{a_k}{\tau}y_{n-k} + \lambda \sum
	\limits_{k=0}^m b_k y_{n-k} = 0,
	\end{equation}
	
	$$ \sum \limits_{k=0}^m (a_k + \tau \lambda b_k)y_{n-k} = 0. $$
	
	Будем искать решение этого уравнения в виде $ y_j = q^j $.
	
	Подставим это \eqref{eq_5_4_7}:
	$$ \sum \limits_{k=0}^m (a_k + \tau \lambda b_k)q^{n-k} = 0. $$
	Разделим обе части этого уравнения на $q^{m-n}$, получим
	\begin{equation}
	\label{eq_5_4_8}
		F_m(\tau, q) = \sum \limits_{k=0}^m (a_k + \tau \lambda b_k)q^{m-k} = 0.
	\end{equation}
	
	Уравнение \eqref{eq_5_4_8} называется характеристическим уравнением. Для
	устойчивости необходимо, чтобы его корни по модулю не превосходили 1 (иначе решение
	будет неограниченно нарастать). Однако, нахождение корней уравнения
	\eqref{eq_5_4_8} -- трудная задача, и обычно рассматривают более простое
	уравнение:
	\begin{equation}
	\label{eq_5_4_9}
		F_m(0, q) = \sum \limits_{k=0}^m a_kq^{m-k} = 0.
	\end{equation}
	
	Уравнение \eqref{eq_5_4_9}, также как и уравнение \eqref{eq_5_4_8}, называют
	характеристическим уравнением.
	
	\begin{myUnnumberedDefinition}
    	Говорят, что разностная схема \eqref{eq_5_4_6} удовлетворяет условию
    	\aCond, если все корни характеристического уравнения \eqref{eq_5_4_9}
    	лежат внутри или на границе единичного круга комплексной плоскости, причем
    	на границе нет кратных корней.
    \end{myUnnumberedDefinition} 
	
	\begin{myUnnumberedTheorem}
    	Пусть разностная схема \eqref{eq_5_4_6} удовлетворяет условию \aCond~и
    	$|f'_n| \leq L$ при $ 0 \leq t_n = \tau n \leq T$. Тогда для любого
    	достаточно малого $\tau$ справедливо
		\begin{equation}
		\label{eq_5_4_10}
			|y_n - u_n| \leq M \left(  \sum \limits_{j=m}^n \tau |\psi_j| + \max_{0 \leq
			i \leq m-1}|y_i - u(t_i)| \right),
		\end{equation}
    	где $M$ не зависит от $\tau,\, \psi_j$ -- погрешность аппроксимации
    	разностного метода \eqref{eq_5_4_6} на решение задачи \eqref{eq_5_4_1}.
    \end{myUnnumberedTheorem}
	
	\begin{myUnnumberedNote}
    	Метод Адамса удовлетворяет условию \aCond:
    	$$ a_0 = - a_1 = 1, $$
    	$$ \frac{y_n -y_{n-1}}{\tau} = \sum \limits_{k-0}^m b_k f_{n-k}. $$
    	Характеристическое уравнение имеет вид:
    	$$ q^n - q^{n-1} = 0, $$
    	оно имеет корни $ q = 0 $ и $q = 1,$ причем $q = 1$ -- некратный корень.  
    \end{myUnnumberedNote}
	
	\begin{myUnnumberedNote}
    	Для неявных схем наивысший порядок погрешности аппроксимации $p \leq 2m$.
    	Для явных схем $p \leq 2m-1$.
    	
    	Однако, схемы высокого порядка не удовлетворяют условию \aCond, т.е. не
    	являются устойчивыми. Наивысший порядок погрешности аппроксимации для
    	схем, удовлетворяющих условию \aCond, следующий:
    	\begin{enumerate}
          \item Для неявных схем:
          \begin{enumerate}
            \item Если m -- четно, то $ p \leq m + 2$.
            \item  Если m -- нечетно, то $ p \leq m + 1$.
          \end{enumerate}
          \item Для явных схем  $ p \leq m $.
        \end{enumerate}
    	
    \end{myUnnumberedNote}
	
	\begin{myUnnumberedNote}
    	Говорить об условной или безусловной устойчивости не имеет смысла. Она
    	всегда условная, т.к. рассматриваются малые $ \tau $.
    \end{myUnnumberedNote}
	
	\begin{myUnnumberedTask}
    	Доказать, что для схемы 
    	$$ \frac{y_n + 4y_{n-1} - 5y_{n-2}}{6\tau} = \frac{2f_{n-1}+ f_{n-2}}{3} $$
    	имеет место $\psi_n = O(\tau ^3).$
    \end{myUnnumberedTask}
	\begin{proof}[Решение]
    	$$ \psi_n = - \frac{u_n + 4u_{n-1} - 5u_{n-2}}{6\tau} + \frac{2f_{n-1}+
    	f_{n-2}}{3}. $$
    	
    	Запишем условия, налагаемые на многошаговый разностный метод для
    	того, чтобы погрешность аппроксимации имела порядок 3:
    	
    	$$ \begin{cases}
           		b_0 = 1 - \sum \limits_{k=1}^m b_k, \\
           		a_0 = - \sum \limits_{k=1}^m a_k, \\
           		\sum \limits_{k=1}^m a_k k = -1, \\
           		\sum \limits_{k=0}^m k^{l-1}(a_k k + b_k) = 0, \: l = 2,3.
           \end{cases}
    	$$
    	
    	В нашем случае, $m = 2,\, a_0 = \frac{1}{6},\, a_1= \frac{2}{3},\, a_2 = -
    	\frac{5}{6},\, b_0 = 0, \, b_1 = \frac{2}{3},\, b_2 = \frac{1}{3}.$
    	Выписанные условия, как легко проверить, выполняются. Таким образом,
    	$\psi_n = O(\tau ^3).$
    \end{proof}

	Рассмотренная в предыдущей задаче схема неустойчива. Действительно, для нее
	характеристическое уравнение имеет вид:
	$$ q^2 + 4q - 5 = 0. $$
	Это уравнение имеет корни $q_1 = 1, q_2 = -5.$ Т.к. $|q_2| >1,$ то данный
	разностный метод не удовлетворяет условию \aCond.
	
	\section{Жесткие системы ОДУ}
	Рассмотрим систему ОДУ
	\begin{equation}
	\label{eq_5_5_1}
			\begin{cases}
            	\frac{du_1}{dt} + a_1 u_1 (t) = 0, \quad t > 0, \\
            	\frac{du_2}{dt} + a_2 u_2 (t) = 0, \quad t > 0, \\
            	u_1 (0) = u_{10},\: u_2(0) = u_{20}, \quad a_1>0, \: a_2 > 0.
            \end{cases}
	\end{equation}
	
	Решение имеет вид:
	$$ u_1 (t) = u_{10}e^{-a_1 t}, $$
	$$ u_2 (t) = u_{20}e^{-a_2 t}. $$
	
	Пусть $a_1 >> a_2.$ Тогда такая система ОДУ называется жесткой. С некоторого
	момента $t^*$ решение $ u_2 (t)$ мало отличается от $0$. Однако, если мы
	решаем эту систему при помощи явной схемы Эйлера, то нам нужно использовать
	шаг $\tau \leq \min\{ \frac{2}{a_1}, \frac{2}{a_2} \} = \frac{2}{a_2}.$ Это будет
	весьма маленький шаг, ибо $a_1 >> a_2$. Но с некоторого момента $t^*$ $u_2$
	можно ``не считать'', т.е. использование маленького шага излишне. Таким
	образом, явные схемы для жестких систем ОДУ не годятся. Если использовать неявную схему, то можно взять
	более крупный шаг.
	
	
	