%\documentstyle{report}
%\documentclass{report }

%\usepackage[cp866]{inputenc}
%\usepackage[cp1251]{inputenc}

%\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\documentclass[12pt,a4paper]{article}
%\usepackage[cp866]{inputenc}
\usepackage[cp1251]{inputenc}

\usepackage[russian]{babel}
%\usepackage[LCY]{fontenc}
%\usepackage{graphicx,mybib,russian}
%\newcommand{\<<}{\lfq}
\twocolumn
\oddsidemargin =-2cm
\topmargin -3cm
\textheight=27cm
\textwidth=17cm
\pagestyle{empty}
\begin{document}

{ \footnotesize

 {\bf Лекция 13.}

 {\bf Порядок точности явной схемы Эйлера }

$$
\begin{array}{l}
\frac{du}{dt}=f(t,u)\\
u(0)=u^0,\qquad f(t,u)\in G=\{ 0\le t\le T, |u-u^0|\le U\}\\
\end{array}
$$

$$
\begin{array}{l}
[0,T]\to \omega_\tau=\{t_i:0\le t_0<t_1<\cdots<t_n\le T,\\
 \tau=t/n, t_i=\tau (i-1),i=\overline{0,n} \},\\
u_{i+1}=u_i+\tau f(t_i,u_i),\\
u_0=u^0,\i=\overline{0,n-1}\\
\end{array}
$$

Здесь $u_i$ -приближенное решение задачи.

 Пусть $u(t_i)$- точное решение. Интерес представляет мера близости
между точным решением приближенным, а также накопление возможных ошибок в приближенном алгоритме.
Меру близости будем оценивать с помощью $||\{ u(t_i) \}_{i=0}^n-\{ u_i\}_{i=0}^n||_{R_n}$.

Предварительно докажем лемму

{\bf Лемма Гронуолла} Пусть $\alpha,\beta>0$, $\gamma_0=0$. Тогда из неравенства

$ \gamma_{i+1}\le \gamma_i(1+\alpha)+\beta$ следует, что

$\gamma_i\le \beta \frac{\exp(i\alpha)-1}{ \alpha}.$

Док-во: для $i=0$ утверждение леммы очевидно. Предположим, что лемма справедлива для любого
$i$ и докажем справедливость леммы для $i+1$.

$\gamma_{i+1}\le \gamma_i(1+\alpha)+\beta\le (1+\alpha)\beta \frac{\exp(i\alpha)-1}{\alpha}+\beta=$

$\beta\frac{\exp(i\alpha)(1+\alpha)-1}{\alpha}\le \beta\frac{\exp(i\alpha)(\exp(\alpha)-1}{\alpha}=
\beta\frac{\exp((i+1)\alpha)-1}{\alpha}$

Порядок точности явной схемы Эйлера.
Пусть $M_0=\max_G|f|,\qquad M_1=\max_G|f'_t|,\qquad M_2=\max_G|f'_u|$


$||\{u(t_i)\}_{i=0}^n-\{u_i\}_{i=0}^n||_{R_n}=?$
 Для точного решения имеем
$u(t_{i+1})=\mbox{ используем разложение в ряд Тейлора } =u(t_i)+\tau u'(t_i)
+\frac{\tau^2}{2}u''(\zeta_i),\qquad \zeta_i\in [t_i,t_{i+1}]$

$u'=f \to u(t_{i+1}=u(t_i)+\tau f(t_i,u(t_i))+\frac{\tau^2}{2}u''(\zeta_i)$

Приближенное решение в методе Эйлера задается равенством

$u_{i+1}=u_i+\tau f(t_i,u_i)$.

Вычитая из первого равенства второе будем иметь

$|u(t_{i+1})-u_{i+1}|=|u(t_i)-u_i+\tau f(t_{i},u(t_{i})) -\tau f(t_i,u_i)+
\frac{\tau^2}{2} u''(\zeta_i)|=
$

$\mbox{$u''=(u')'=(f)'_t=f'_t+f'_uf$}$


$
 \le
|u(t_i)-u_i|+\tau |f(t_{i},u(t_{i})) -\ f(t_i,u_i)|+\frac{\tau^2}{2}(|f'_t|+f'_u||f|)=$

{используя  формулу конечных приращений Лагранжа}

$f(x)-f(y)=\int_0^1 f_\omega'(x+\omega(x-y))d\omega (x-y)$
$|u(t_{i+1})-u_{i+1}|\le   |u(t_i)-u_i|+\tau |f_u||u(t_i)-u_i|+\frac{\tau^2}{2}(|f'_t|+f'_u||f|)
\le   |u(t_i)-u_i|+\tau M_2|u(t_i)-u_i|+\frac{\tau^2}{2}(M_1+M_2M_0)$

Применяя к полученному неравенству лемму Гронуолла, будем иметь

$|u(t_{i})-u_{i}|\le \frac{\tau^2}{2}(M_1+M_2M_0)\frac{M_1+M_2M_0}{\tau M_2}(\exp(i\tau M_2)-1) $


$||\{u(t_i)\}_{i=0}^n-\{u_i\}_{i=0}^n||_{R_n}=\max_{0\le i\le n}|u(t_i)-u_i|=
\tau\frac{M_1+M_2M_0}{M_2}(\exp(TM_2)-1)\sim O(\tau)$

 {\bf Аппроксимация, устойчивость, сходимость для линейных разностных схем}

Пусть на отрезке $[0,T]$ Линейное уравнение $Lu=f$
имеет решение $u(t)$. Пусть далее задан приближенный алгоритм(разностная схема) решения
на равномерной сетке $\omega_\tau$

$
L_\tau u_\tau=f_\tau, \qquad \tau$- параметр \qquad  схемы


Пример:

$$
\begin{array}{l}
\frac{du}{dt}+\lambda u=f(t)\\
u(0)=u^0,
\end{array}
$$
$$
Lu=
\left\{
\begin{array}{l}
 \frac{du}{dx}+\lambda u \qquad t\in (0,T]\\
u(0),\qquad t=0
\end{array}
\right.
$$


$$
f=
\left\{
\begin{array}{l}
 f(t) t\in (0,T]\\
u^0,\qquad t=0
\end{array}
\right.
$$



$$
\begin{array}{l}
u_{i+1}=u_i-\tau \lambda u_i+\tau f_i,\\
u_0=u^0,\i=\overline{0,n-1}\\
\end{array}
$$

$$
L_\tau u_\tau=
\left\{
\begin{array}{l}
 \frac{u_{i+1}-u_i}{\tau}+\lambda u_i  \qquad i=\overline{1,n}\\
u_0,\qquad i=0
\end{array}
\right.
$$

$$
f_\tau =
\left\{
\begin{array}{l}
 f_i=f(t_i)  \qquad i=\overline{1,n}\\
u^0,\qquad i=0\\
\end{array}
\right.
$$


{\bf Опр.} Погрешностью аппроксимации оператора $L$ оператором $L_\tau$
на решении $u(t)$ уравнения $Lu=f$ назовем функцию

$
\Psi(t)=Lu(t)-L_\tau u(t)
$

В нашем примере
$\Psi(t)=\frac{du}{dt}|_{t=t_i}+\lambda u(t_i)-\frac{u(t_{i+1})-u(t_i)}{\tau}-\lambda u(t_i)=
f(t_i)-\frac{u(t_{i+1})-u(t_i)}{\tau}-\lambda u(t_i)
$

{\bf Опр.} Будем говорить, что оператор $L_\tau$ имеет $m-$порядок аппроксимации
на сетке $\omega_\tau$, если

$||\Psi||_\tau=||L_\tau u- Lu||_\tau\sim O(\tau^m), \qquad ||\Psi||_\tau=M\tau^m
$
Здесь и далее  под символом $||.||_\tau$ понимается норма в $R_n$ для сеточной
функции заданной на сетке $\omega_\tau$

Пример: $\Psi=f(t_i)-\frac{u(t_{i+1})-u(t_i)}{\tau}-\lambda u(t_i)=
f(t_i)-\frac{u(t_i)+\tau u'(t_i)+\tau^2/2 -u(t_i)}{\tau}-\lambda u(t_i)=
f(t_i)-u'(t_i)-\lambda u(t_i)-\frac{\tau}{2}u''(t_i)$

$||\Psi||\sim O(\tau)$

{\bf Опр.} Будем говорить, что разностная схема $L_\tau u_\tau=f_\tau$ устойчива,
если существует постоянная $M>0$, независящая от выбора $f_{\tau}$ такая, что
имеет место оценка

$||u_\tau||\le M ||f_\tau||$.

{\bf Опр.} Будем говорить, что разностная схема  $L_\tau u_\tau=f_\tau$ корректна,
если существует единственное решение разностной схемы при любых входных данных
$f_\tau$ и выполнены условия устойчивости.

Пример: $ \frac{du}{dt}+\lambda u=0$

$u(0)=u^0$

Разностная схема

$u_{i+1}=u_i-\lambda \tau u_i, \quad u_0=u^0, i=\overline{0,n-1} $

$u_{i+1}\le (1-\tau \lambda)u_i, \mbox{если} |1-\tau\lambda|<1\to
|u_{i+1}|\le|u_i|\le\cdots\le |u_0|$

$|1-\tau\lambda|<1\to \lambda\tau<2$

Следствие:
 1. Устойчивость означает непрерывную зависимость решения разностной схемы
$L_\tau u_\tau=f_\tau$ от входных данных равномерную относительно $\tau.$

Пусть $ L_\tau \overline{u_\tau}=\overline{f_\tau}$

$L_\tau u_\tau=f_\tau$

Вычитая из второго первое равенство, имеем

$L_\tau (u_\tau-\overline{u_\tau}) =(f_\tau-\overline{f_\tau})$ из условий устойчивости
следует, что

$||\overline{u_\tau}-u_\tau||\le M ||_\tau\overline{f_\tau}-f_\tau||_\tau$

2. Если разностная схема $L_\tau u_\tau=f_\tau$ корректна, то существует
обратный оператор $L_\tau^{-1}\to u_\tau=L_\tau^{-1}f_\tau\to
||u_\tau||\le ||L_\tau^{-1}||||f_\tau||\to$ из условий устойчивости, что

$$||L_\tau^{-1}||\le M $$

т.е. имеет место равномерная ограниченность обратного оператора при выполнении условий
устойчивости.

Связь устойчивости, аппроксимации разностной схемы с порядком точности приближенного
решения.

Задача $|| {u(t_i)}_{i=0}^n-u_\tau||=?$

Обозначим $z_\tau=u_\tau-u\to u_\tau=z_\tau+u \to L_\tau u_\tau=f_\tau\to
L_\tau z_\tau=f_\tau-L_\tau u= f_\tau-f+f-L_\tau u=$

$f_\tau-f+Lu-L_\tau u =\Psi_\tau $- погрешность аппроксимации оператора $L$ оператором
$L_\tau$

{\bf Опр. } Будем говорить, что решение разностной схемы сходится к точному
решению, если

$$||z_\tau||\to 0 \quad \tau\to 0$$

$L_\tau z_\tau=\Psi_\tau$  из условий устойчивости следует, что
$||z_\tau||_\tau \le M||\Psi_\tau||_\tau$ следовательно, если
выполнено условие аппроксимации т.е. $||\Psi_\tau||_\tau\sim O(\tau^m)$
тогда $||z_\tau||_\tau\to 0 \quad  \tau \to 0$

В этом смысле и говорят, что из аппроксимации и устойчивости решения разностной схемы
следует сходимость приближенного решения к точному и для сходимости достаточно исследовать
аппроксимацию и устойчивость.

{\bf Устойчивость разностных схем для решения задачи Коши.}
Рассмотрим задачу
$$
\begin{array}{l}
\frac{du}{dt}=f(t,u)\\
u(0)=u^0,\qquad f(t,u)\in G=\{ 0\le t\le T, |u-u^0|\le U\}\\
\end{array}
$$

и возмущенную
$$
\begin{array}{l}
\frac{d\overline{u}}{dt}=\overline{f}(t,\overline{u})\\
\overline{u}(0)=\overline{u}^0,\qquad \overline{f}(t,u)\in G=\{ 0\le t\le T, |u-u^0|\le U\}\\
\end{array}
$$
Вычитая из второй задачи первую, будем иметь для $z=\overline{u}-u$

$$
\begin{array}{l}
\frac{d{z}}{dt}=\overline{f}(t,z+{u})-f(t,u)\\
{z}(0)=\overline{u}^0-u^0=\delta u\\
\end{array}
$$

Применяя к последнему равенству формулу конечных приращений, для нахождения
$z$, будем иметь уравнение

$$
\begin{array}{l}
\frac{d{z}}{dt}+\lambda u=0\\
{z}(0)=\delta u, \quad \lambda=-f'_u(t,\zeta)\\
\end{array}
$$

Если $f_u<0 \to \lambda>0 \to z=\delta u\exp(-\lambda t) \to $ решение задaчи
Коши устойчиво (локально) по отношению к возмущению правой части и начальных данных.
Аналогично поступим и для исследования устойчивости разностных схем

1. Схема Эйлера

$$
\begin{array}{l}
 u_{i+1}=u_i+\tau f(t_i,u_i), \\
u_0=u^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
Рассмотрим возмущенную разностную схему
$$
\begin{array}{l}
 \overline{u}_{i+1}=\overline{u}_i+\tau \overline{f}(t_i,\overline{u}_i), \\
\overline{u}_0=\overline{u}^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
Вычитая из второй задачи первую для $z=\overline{u}_i-u_i$, будем иметь
$$
\begin{array}{l}
 {z}_{i+1}={z}_i+\tau \overline{f}(t_i,z_i+{u}_i)-f(t_i,u_i), \\
{z}_0=\overline{u}^0-u_0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
Используя формулу конечных приращений, получим

$$
\begin{array}{l}
 {z}_{i+1}={z}_i+\tau f'(...)z_i=(1-\lambda\tau)z_i, \lambda=-f'_u \\
{z}_0=\overline{u}^0-u_0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
Видим, что устойчивость разностной схема сводится к локальной устойчивости,
т.е. устойчивости  линейной разностной Эйлера в окрестности некоторой точки

Очевидно, что для устойчивости в этом случае достаточно, чтобы
$|1-\lambda \tau|<1\to \tau\lambda<2,\lambda>0$

 Для исследования устойчивости остальных схем, будем рассматривать линеаризованное
уравнение

2. Неявная схема Эйлера
$$
\begin{array}{l}
 u_{i+1}=u_i-\tau \lambda u_{i+1}, \\
u_0=u^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$

$u_{i+1}=\frac{1}{1+\tau\lambda } u_i \to |\frac{1}{1+\tau\lambda }|<1 \to$
устойчивость для любых $\tau,\lambda>0$

 3. Схема Роте с весами

$$
\begin{array}{l}
 u_{i+1}=u_i- \lambda \tau [\alpha u_{i+1}+(1-\alpha)u_i], 0\le \alpha\le 1 \\
u_0=u^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$


$u_{i+1}=\frac{1-\tau\lambda(1-\alpha)}{1+\tau\lambda\alpha}u_i\to$

$|\frac{1-\tau\lambda(1-\alpha)}{1+\tau\lambda\alpha}|<1 $
откуда следует, что схема безусловно устойчива(для всех$\tau$) для $\alpha\ge 0.5$
и устойчива при $\tau=\frac{1}{(0.5-\alpha)\lambda} $ ,$\lambda>0$

4. Схема предиктор-корректор
$$
\begin{array}{l}
 u_{i+1}^*=u_i-\tau \lambda u_{i}, \\
 u_{i+1}=u_i-\frac{\tau \lambda}{2} [u_{i}+u_{i+1}], \\
u_0=u^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
$ u_{i+1}=u_i[1-\tau\lambda +\frac{\tau^2\lambda^2}{2}]\to$

$|(1-\tau\lambda +\frac{\tau^2\lambda^2}{2})|<1$
$\to$ $\tau\lambda<2, \lambda>0$




5. Схема Рунге-Кутты 4-го порядка

$$
\begin{array}{l}
 u_{i+1}=u_i-\frac{\tau}{6} (k_1+2k_2+2k_3+k_4), \\
u_0=u^0, \quad  i=\overline{0,n-1}\\
\end{array}
$$
$k_1=f(t_i,u_i)=-\lambda u_i$,

$k_2=f(t_i,0.5\tau,u_i+0.6\tau k_1)=
-\lambda[u_i+0.5\tau k_1]=[0.5\tau\lambda^2=\lambda]u_i$

$k_3=f(t_i,u_i+0.5\tau k_2)=u_i[\lambda+\frac{\tau}{2}\lambda^2-\frac{\tau^2}{4}\lambda^2]$

$k_4=f(t_i,u_i+\tau k_3)=u_i[\lambda+\tau\lambda^2-\frac{\tau^2}{2}\lambda^3+\frac{\tau^3}{8}\lambda^4]$

$u_{i+1}=u_i[1-\tau\lambda +\frac{\tau^2\lambda^2}{2}-\frac{\tau^3\lambda^3}{6}+\frac{\tau^4\lambda^4}{24} ]$

$|1-\tau\lambda +\frac{\tau^2\lambda^2}{2}-\frac{\tau^3\lambda^3}{6}
+\frac{\tau^4\lambda^4}{24} |<1$ $\to$

$\tau\lambda<278, \lambda>0$


}
\end{document}
