%Лекция 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$ можно ``не считать'', т.е. использование маленького шага излишне. Таким образом, явные схемы для жестких систем ОДУ не годятся. Если использовать неявную схему, то можно взять более крупный шаг.