Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений

Найти функцию для $y(t)$ удовлетворяющую уравнению

Задача Коши для ОДУ

${\begin{cases}y'=f(t,y(t)),&t>t_{0}\\y(t_{0})=y_{0}\end{cases}}$

Ищем интегральную кривую, проходящую через $(t_{0},y_{0})$

Применяя формулу численного дифференцирования

${\frac {y(t_{i+1})-y(t_{i})}{h}}=f(t_{i},y(t_{i}))\quad \Rightarrow \quad y_{i+1}=y_{i}+h\cdot f(t_{i},y_{i})$

Формула Тейлора

Пусть $y(t)$ - найдено. Найдем $t+h$:

$y(t+h)=y(t)+hy'(t)+{\frac {h^{2}}{2}}y''(t)+...+{\frac {h^{p}}{p!}}y^{(p)}(t)+{\frac {h^{p+1}y^{(p+1)}(\xi )}{(p+1)!}}$

Первая производная - это правая часть.

II-я: $y''=f'_{t}+f'_{y}y'_{t}=f'_{t}+f'_{y}f$

III-я: $y'''=f''_{tt}+f''_{ty}f+(f'_{yt}+f'_{yy})+f'_{y}(f'_{t}+f'_{y}f)$

• Формула Тейлора I-го порядка точности по $h$ (Метод Эйлера)

$y(t+h)=y(t)+hf(t,y(t))$

• Формула Тейлора II-го порядка точности по $h$:

$y(t+h)=y(t)+hf(t,y(t))+{\frac {1}{2}}h^{2}(f'_{t}+f'_{y}f)$

Метод Эйлера

${\begin{cases}y'=f(t,y(t)),&\quad t_{i}=t_{0}+ih,i={\overline {1,n}}\\y(t_{0})=y_{0}\end{cases}}$

Дискретизация задачи (переход от непрерывной функции к дискретной)

$y(t_{i})$ - точное решение. $y_{i}$ - приближенное. $y'(t_{i})\approx h^{-1}(y_{i+1}-y_{i})$, ${\frac {y_{i+1}-y_{i}}{h}}=f(t_{i},y_{i})$

$y^{n}={\begin{pmatrix}y_{0}\\\vdots \\y_{N}\end{pmatrix}}$ - в ответе получаем вектор.

${\begin{cases}y_{i+1}=y_{i}+hf(t_{i},y_{i})&\\y_{0}{\text{ - задано}}\end{cases}}\qquad$ шаг обычно берут h = 0.1}

Геометрическая интерпретация.

Геометрическая интерпретация метода Эйлера

$l(t)=y(t_{i})+y'(t_{i})(t-t_{i})$ - уравнение касательной.

Погрешности:

Определение. Погрешность на шаге определяется по формуле $r_{i}=y(t_{i+1})-y_{i+1}$, где $y(t_{i})$ - точное решение, а $y_{i}$ - приближенное.

Определение. Локальная погрешность: $l_{i}=y(t_{i})-y_{i}$, если $y_{i-1}\equiv y(t_{i-1})$ - точное.

Определение. Глобальная погрешность: $E(h)=\max {0\leq i\leq N-1}\|r_{i}\|$

Определение. Будем называть метод $p$-го порядка точности по $h$, если $E(h)\leq ch^{p}$, где $c$ - константа.

Модификации метода Эйлера

$y_{i+1}=y_{i}+hk_{i}$. изменяя $k_{i}$ можно легко получить меньшую погрешность.

• $k_{i}=f(t_{i+{\frac {1}{2}}},y_{i+{\frac {1}{2}}}$) - усовершенствованный метод Эйлера.

${\begin{cases}y_{i+{\frac {1}{2}}}=y_{i}+{\frac {h}{2}}f(t_{i},y_{i})\\y_{i+1}=y_{i}+hf(t_{i+{\frac {1}{2}}},y_{i+{\frac {1}{2}}})\end{cases}}\Leftrightarrow y_{i+1}=y_{i}+hk_{i},k_{i}=f(t_{i+{\frac {1}{2}}},y_{i}+{\frac {h}{2}}f(t_{i},y_{i}))$ (за угол наклона берется наклон касательной в средней точке).

$E(h)=ch^{2}$

• Метод Эйлера-Коши:

$y_{i+1}+hk_{i},\quad k_{i}={\frac {k_{i}^{1}+k_{i}^{2}}{2}},\quad k_{i}^{1}=f(t_{i},y_{i}),k_{i}^{2}=f(t_{i}+h,y_{i}+hk_{i}^{2})$. $E(h)=ch^{2}$.

Методы Рунге-Кутты

Метод Эйлера - это метод Рунге-Кутты I-го порядка точности. $y_{i+1}=y_{i}+hk_{i},\quad k_{i}$ - угловой коэффициент секущей.

$m$-этапный метод Рунге-Кутты

$y_{i}=y(t_{i})$

Метод Рунге-Кутты

$t_{i}^{(1)}=t_{i}$ $t_{i}^{(2)}=t_{i}^{(1)}+\alpha _{2}h\quad 0<\alpha _{2}<1\quad t_{i}^{(m)}=t_{i}^{(1)}+\alpha _{m}h\quad 0<\alpha _{m}<1$

$k_{i}^{(1)}=f(t_{i}^{(1)},y_{i}^{(1)})=f(t_{i},y_{i})$

$k_{i}^{(2)}=f(t_{i}^{(1)}+\alpha _{2}h,y_{i}+h\beta _{21}k_{i}^{(1)})$

$k_{i}^{(3)}=f(t_{i}^{(1)}+\alpha _{3}h,y_{i}+h(\beta _{31}k_{i}^{(1)}+\beta _{32}k_{i}^{(2)}))$

$\dots$

$k_{i}^{(m)}=f(t_{i}^{(1)}+\alpha _{m}h,y_{i}+h(\beta _{m1}k_{i}^{(1)}+...+\beta _{m,m-1}k_{i}^{(m-1)}))$

Все коэффициенты ($\alpha$ и $\beta$) подлежат определению: $k_{i}=c_{1}k_{i}^{(1)}+c_{2}k_{i}^{(2)}+...+c_{m}k_{i}^{(m)}$ коэффициенты $c_{i}$ также неизвестны.

$y(t+h)=y(t)+hy'(t)+{\frac {h^{2}}{2}}y''(t)+...+{\frac {h^{p}}{p!}}y^{(p)}(t)+{\overline {\overline {O}}}(h^{p+1})$

Если хотим построить метод $p$-го порядка точности по $h$, $y_{i+1}=y_{i}+hk_{i}$. Возьмем разложение для точного решения. Правую часть раскладываем в $t_{i}$. Коэффициенты $\alpha ,\beta$ и $c$ подбираем так, чтобы разложение совпало до $p$-го порядка включительно. Построим параметрическое семейство двухэтапных методов Рунге-Кутты (2-го порядка точности по $h$)

$t_{i}^{(1)}=t_{i},\quad t_{i}^{(2)}=i_{i}+\alpha h$

$k_{i}^{(1)}=f(t_{i},y_{i}),\quad k_{i}^{(2)}=f(t_{i}+\alpha h,y_{i}+h\beta k_{i}^{(1)},\quad k_{i}=c_{1}k_{i}^{(1)}+c_{2}k_{i}^{(2)}$

$y_{i+1}=y_{i}+hk_{i}=y_{i}+h\left[c_{1}f(t_{i},y_{i})+c_{2}f(t_{i}+\alpha h,y_{i}+h\beta k_{i}^{(1)})\right]$

$f(t_{i}+\alpha h,y_{i}+h\beta k_{i}^{(1)})=f(t_{i},y_{i})+f'_{t}(t_{i},y_{i})\alpha hf'_{y}(t_{i},y_{i})h\beta k_{i}^{(1)}+{\overline {\overline {O}}}(h^{2})$

$y_{i+1}=y_{i}+h\left[c_{1}f(t_{i},y_{i})+c_{2}(f(t_{i},y_{i})+f'_{t}(t_{i},y_{i})\alpha h+h\beta f'_{y}(t_{i},y_{i})k_{i}^{(1)})\right]+{\overline {\overline {O}}}(h^{3})$ - разложение приблзительного решения.

В полученное разложение будем подставлять точное решение, будем считать $\alpha =\beta$

$y''(t_{i})=f'_{t}(t_{i},y(t_{i}))+f'_{y}(t-i,y(t_{i}))f(t_{i},y_{i}(t_{i}))$

$y(t_{i+1})=y(t_{i})+h(c_{1}+c_{2})f(t_{i},y(t_{i}))+c_{2}\alpha h^{2}\left[f'_{t}(t_{i},y(t_{i}))+f'_{y}(t_{i},y(t_{i}))f(t_{i},y(t_{i}))\right]\Rightarrow y(t_{i+1})=y(t_{i})+h(c_{1}+c_{2})y'+\alpha c_{2}h^{2}y''(t_{i})+{\overline {\overline {O}}}(h^{3})$

${\begin{cases}c_{1}+c_{2}=1\\c_{2}\alpha ={\frac {1}{2}}\end{cases}}\Rightarrow {\begin{cases}c_{2}={\frac {1}{2\alpha }}\\c_{1}=1-{\frac {1}{2\alpha }}\end{cases}},\quad \alpha$ - параметр

Имеем:

${\begin{cases}y_{i+1}=y_{+}hk_{i}\\k_{i}^{(1)}=f(t_{i},y_{i})\\k_{i}^{(2)}=f(t_{i}+\alpha h,y_{i}+\alpha hk_{i}^{(1)})\\k_{i}=(1-{\frac {1}{2\alpha }})k_{i}^{(1)}+{\frac {1}{2\alpha }}k_{i}^{(2)}\end{cases}}$

При $\alpha =1$ получаем метод Эйлера-Коши, $\alpha ={\frac {1}{2}}$ - усовершенствованный метод Эйлера.

По построению: локальная погрешность этих методов для $p$-го порядка точности $l=ch^{p+1}$

Каноническая форма записи методов численного интегрирования

$y_{i+1}=y_{i}+hf(t_{i},y_{i})\to {\frac {y_{i+1}-y_{i}}{h}}=f(t_{i},y_{i})$ - явный одношаговый метод. ${\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{i+1-j}=\Phi (t_{i},y_{i+1-k},...,y_{i},y_{i+1},h),\alpha _{0}\neq 0$ - канонический вид формулы численного интегрирования. (неявный $k$-шаговый метод)

Если правая часть этой формулы не содержит $y_{i+1}$, тогда это явный $k$-шаговый метод. Все методы Рунге-Кутты - явные, одношаговые.

${\frac {y_{i+1}-y_{i}}{f}}=\Phi (t_{i},y_{i},h)$ - общая формула методов Р-К (каноническая формула явных одношаговых методов).

Определение. Аппроксимацией будем называть сеточную функцию $\Psi _{i}^{h}$, определенную так: \\$\Psi _{i}^{h}={\frac {1}{h}}\sum _{j=0}^{k}\alpha _{i}y(t_{i+1-j})-\Phi (t_{i},y(t_{i+1-k}),...,y(t_{i}),y(t_{i+1}),h)$

Определение. Будем говорить, что метод сходится с порядком $p$, если величина $E(h)=\max {0\leq 1\leq N}|y_{i}-y(t_{i})|\leq ch^{p}$

Погрешность аппроксимации метода Эйлера: $\Psi _{i}^{h}={\frac {h^{2}}{2}}y''(t)$

Устойчивость ЗК

${\begin{cases}y'=f(t,y)\\y(t_{0})=y_{0}\end{cases}}\quad {\begin{cases}{\tilde {y}}'=f(t,{\tilde {y}})-\phi \\{\tilde {y}}(t_{0})={\tilde {y}}_{0}\end{cases}}\quad$ - возмущенная задача

$\varepsilon (t)=y(t)-{\tilde {y}}(t)\Rightarrow {\begin{cases}\varepsilon '=f(t,y)-f(t,{\tilde {y}})+\phi \\\varepsilon (t_{0})=y_{0}-{\tilde {y}}_{0}=\varepsilon _{0}\end{cases}}$

$f(t,y)-f(t,{\tilde {y}})=f'_{y}(t,{\tilde {\tilde {y}}})(y-{\tilde {y}})\Rightarrow {\begin{cases}\varepsilon '=\lambda \varepsilon +\phi ,\lambda =f'_{y}(t,{\tilde {\tilde {y}}}),{\tilde {\tilde {y}}}=\left[y,{\tilde {y}}\right]\\\varepsilon (t_{0})=\varepsilon _{0}\end{cases}}$

Получим линейное неоднородное уравнение

${\begin{cases}\varepsilon '_{1}=\phi \\\varepsilon (t_{0})=0\end{cases}}$ и ${\begin{cases}\varepsilon '_{2}=\lambda \varepsilon _{2}\\\varepsilon _{2}(t_{0})=\varepsilon _{0}\end{cases}}\Rightarrow \varepsilon _{1}=\int _{t_{0}}^{t}\phi (\tau )d\tau ,\varepsilon _{2}=\varepsilon _{0}\exp\{\int _{t_{0}}^{t}\lambda (\tau )d\tau \}$

Если $\lambda (t)>0\Rightarrow$ первое слагаемое $\varepsilon _{2}\rightarrow [t\to \infty ]{}\infty$. Если $\lambda (t)<0\Rightarrow \varepsilon _{2}\rightarrow [t\to \infty ]{}0$

Оценка устойчивости ЗК

$|\varepsilon (t)|\leq k(\tau )(|\varepsilon _{0}|+\int _{t_{0}}^{\tau }|\phi (t)|dt),k(\tau )={\begin{cases}\exp\{\int _{t_{0}}^{\tau }\lambda (t)dt\},&\lambda (t)\geq 0\\1,&\lambda (t)<0\end{cases}}$

Из этого неравенства вытекает устойчивость ЗК.

Рассмотрим возмущенную дискретную ЗК:

${\frac {1}{h}}\sum _{j=0}^{k}{\tilde {y}}_{i+1-j}\lambda _{j}=\Phi (t_{i},{\tilde {y}}_{i+1-k},...,{\tilde {y}}_{i},{\tilde {y}}_{i+1},h)-\phi$

$\varepsilon _{0},\varepsilon _{1},...,\varepsilon _{k-1}$ - погрешности вычисления стартовых точек метода.

Определение. Будем называть метод (1) устойчивым, если:

$\max {0\leq i\leq n}|y_{i}-{\tilde {y}}_{i}|\leq k(\tau )\max {0\leq i\leq k-1}(|\varepsilon _{i}|+\sum _{i+k}^{N-1}h|\phi |)$

Многошаговые методы. Методы Адамса

Приближение правой части и интегрирование в многошаговых методах

$\int _{t_{i}}^{t_{i+1}}y'dt=\int _{t_{i}}^{t_{i+1}}f(t,y(t))dt$. $y(t)$ приближаем полиномом по известным значениям.

Метод Адамса

Формулы Адамса-Башфорта

Метод Адамса-Башфорта

$p_{1}(t)=f_{i-1}+{\frac {f_{i}-f_{i-1}}{h}}(t-t_{i-1})$ - интерполяционный многочлен Ньютона. Интегрируемые функции $f(t,y)$: $\int _{t_{i}}^{t_{i+1}}p_{1}(t)dt=\int _{t_{i}}^{t_{i+1}}(f_{i-1}+{\frac {f_{i}-f_{i-1}}{h}}(t-t_{i-1}))dt=f_{i-1}h+{\frac {f_{i}-f_{i-1}}{h}}\left.{\frac {(t-t_{i-1})^{2}}{2}}\right|_{t_{1}}^{t_{i+1}}={\frac {h}{2}}(3f_{i}-f_{i-1})\Rightarrow y_{i+1}=y_{i}+{\frac {h}{2}}(2f_{i}-f_{i-1})$ - формула А-Б (двухшаговый метод, II порядка точности по $h$) Формулы Адамаса-Мултона

Метод Адамса-Моултона

$Q_{1}(t)=f_{i}+{\frac {f_{i+1}-f_{i}}{h}}(t-t_{i})$

$\int _{t_{i}}^{t_{i+1}}Q_{1}(t)dt=f_{i}h+\left.{\frac {(f_{i+1}-f_{i})(t-t_{i})^{2}}{2h}}\right|_{t_{1}}^{t_{i+1}}={\frac {h}{2}}(f_{i}+f_{i+1})$

$y_{i+1}=y_{i}+{\frac {h}{2}}(f_{i}+f_{i+1})$ - II порядка точности, более устойчив.

Порядок аппроксимации в построенных методах

$\Psi _{i}$ - дискретная функция. Канонический вид: ${\frac {y_{i+1}-y_{i}}{h}}={\frac {1}{2}}f_{i}+{\frac {1}{2}}f_{i+1}$

$y'=f(t,y(t))\quad f_{i}=y'(t_{i})\quad f_{i+1}=y'(t_{i+1})$

$\Psi _{i}={\frac {y(t_{i+1})-y(t_{i})}{h}}-{\frac {1}{2}}y'(t_{i})-{\frac {1}{2}}y'(t_{i+1})={\frac {y(t_{i})+hy'(t_{i}){\frac {h^{2}}{2}}y''(t_{i})+{\frac {h^{3}}{6}}y'''(t_{i})+{\underline {\underline {O}}}(h^{4})-y(t_{1})}{h}}-{\frac {1}{2}}y'(t_{i})-{\frac {1}{2}}(y'(t_{i})+hy''(t_{i})+{\frac {h^{2}}{2}}y'''(t_{i})+{\underline {\underline {O}}}(h^{3}))={\frac {h}{2}}y''(t_{i})+{\frac {h}{6}}y'''(t_{i})+{\underline {\underline {O}}}(h^{3})-{\frac {h}{2}}y''(t_{i})-{\frac {h^{2}}{4}}y'''(t_{i})+{\underline {\underline {O}}}(h^{3})=-{\frac {h^{2}}{12}}y'''(t_{i})+{\underline {\underline {O}}}(h^{3})$

$\Psi _{i}=-{\frac {h^{2}}{12}}y'''(t_{i}),\Psi =\max {0\leq i\leq N}|\Psi _{i}|\leq {\frac {M_{3}h^{2}}{12}}\Rightarrow$ II аппроксимационный порядок

Если функция $y(t)$ - аналитична и $k$ раз дифференцируема, то $k$ - шаговый метод А-Б и $k-1$ шаговый метод А-М имеют $k$-й порядок аппроксимации по $h$.

Каноническая формула метода:

$(A):{\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{i+1-j}=\Phi (t_{i},y_{i+1-k},...,y_{i},y_{i+1})$ - дискретная ЗК. Стартовые точки $y_{0},y_{1},...,y_{k-1}$

$(B):{\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{i+1-j}^{*}=\Phi (t_{i},y_{i+1-k}^{*},...,y_{i}^{*},y_{i+1}^{*})$ - дискретная ЗК с возмущенными данными. Стартовые точки $y_{0},y_{1},...,y_{k-1}$

Определение. (Устойчивость $k$-шагового метода)

$\max {k\leq i\leq N}|y_{i}-y_{i}^{*}|\leq c\{\max {0\leq i\leq k-1}|y_{i}-y_{i}^{*}|+\max |\sum _{i=k}^{N}h\Psi _{i}|\}$

Теорема. Если численный метод устойчив и имеет порядок аппроксимации $p$, то он сходится с $p$-м порядком точности по $h$.

Доказательство. Подставим в численный метод точное решение $(A)$:

$y(t_{i}):(A)\to (B),\Psi _{i}$ - погрешность аппроксимации $\Psi _{i}=ch^{p}$

$\max {k\leq i\leq N}|y_{i}-y_{i}^{h}|\leq c\{\max {0\leq i\leq k-1}|y_{i}-y(t_{i})|+\max |\sum _{i=k}^{N}hc_{1}h^{p}|\}=c\{\max |y_{i}-y(t_{i})|+c(T-t_{0})h^{p}\}$

Предположим: $\max {k\leq i\leq N}|y_{i}-y_{i}^{h}|\leq c_{3}h^{p}$, где $c_{3}=c(c_{2}+c_{1}(T-t_{0}))$

Если $|y_{i}-y(t_{i})|\leq c^{(i)}h^{0}$, то $c_{2}=\max c^{(i)}$

Уравнения высокого порядка и системы ДУ

${\begin{cases}y'_{1}=f_{1}(t,y,...,y_{m})\\y'_{2}=f_{2}(t,y,...,y_{m})\\\vdots \\y'_{m}=f_{m}(t,y,...,y_{m})\\y'_{1}(t_{0})=y_{1}^{0}\\\vdots \\y'_{m}(t_{0})=y_{m}^{0}\end{cases}}$ - нелинейная система ОДУ 1-го

$y={\begin{pmatrix}y_{1}\\\vdots \\y_{m}\end{pmatrix}}\quad y^{0}={\begin{pmatrix}y_{1}^{0}\\\vdots \\y_{m}^{0}\end{pmatrix}}\quad F={\begin{pmatrix}f_{1}(t,y_{1},...,t_{m})\\\vdots \\f_{1}(t,y_{1},...,t_{m})\end{pmatrix}}$

метод Эйлера:

${\begin{cases}y'=F(t,y)\\y(t_{0})=y_{0}\end{cases}}$

$y_{i+1}=y_{i}+hF(t_{i},y_{i})$

${\begin{cases}a_{m}y^{(m)}(t)+a_{m-1}y^{(m-1)}+...+a_{1}y'(t)+a_{0}y(t)=f(t)\\y(t_{0})=y_{0}\\\vdots \\y^{(m-1)}(t_{0})=y_{0}^{(m-1)}\end{cases}}$

$y_{1}(t)=y(t);y_{2}(t)=y'(t)=;...;y_{m}(t)=y^{(m-1)}(t)$ - замены

${\begin{cases}y'_{1}=y_{2}\\y'_{2}=y_{3}\\\vdots \\y'_{m-1}=y_{m}\\y'_{m}={\frac {f(t)-a_{m-1}y_{m}-...-a_{0}y_{1}}{a_{m}}}\end{cases}}y={\begin{pmatrix}y_{1}\\\vdots \\y_{m}\end{pmatrix}}F={\begin{pmatrix}y_{2}\\\vdots \\y_{m}\\{\frac {f(t)-a_{m-1}y_{m}-...-a_{0}y_{1}}{a_{m}}}\end{pmatrix}}$

Устойчивость численных методов

${\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{n+1-j}=\Phi (t_{n},y_{n+1-k},...,y_{n},y_{n+1},h)\quad (1)$

$\quad \alpha _{0},\alpha _{1},...,\alpha _{k-1}\quad \alpha _{0}\neq 0$

Чтобы облегчить задачу будем исследовать устойчивость по начальным данным (без правой части) $y_{0},y_{1},...,y_{k-1}$

Определение. Метод устойчив по начальным данным, если

$\max _{0\leq n\leq N}|y_{n}^{*}-y_{n}|\leq k(\tau )\max _{0\leq i\leq k-1}|\varepsilon _{i}|$, где $y^{*}$ - решение $(1)$ при возмущенных входных данных $y_{0}^{*}...y_{k}^{*}$. $\varepsilon _{i}=y_{i}^{*}-y_{i}$, $i={\overline {0,k-1}}$

Рассмотрим модельную задачу $y'=0$ на нуль-устойчивость

${\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{n+1-j}=0$

$(2)\quad \alpha _{0}y_{n+1}+\alpha _{1}y_{n}+...+y_{k}\alpha _{n+1-k}=0$ - конечно-разностное уравнение. Стартовые точки $y_{n+1-k}...y_{n+1}$

Затем мы находим $y_{0},y_{1},...,y_{k-1},y_{k},y_{k+1},...,y_{N}$

Возмущенная задача: $y_{0}^{*}...y_{k-1}^{*}$

$\alpha _{0}y_{n+1}^{*}+\alpha _{1}y_{n}^{*}+...+\alpha _{k}y_{n+1-k}^{*}=0$

$y_{i}^{*}\quad i={\overline {0,N}}$ - проверим на устойчивость

$\alpha _{0}\varepsilon _{n+1}+\alpha _{1}\varepsilon _{n}+...+\alpha _{k}\varepsilon _{n+1-k}=0$

$\varepsilon _{n}={\overline {\varepsilon }}q^{n}$, $q$ некоторое число. ${\overline {\varepsilon }}$ - некоторая первоначальная погрешность. Получим характеристическое уравнения $k$ - шагового метода:

$\alpha _{0}q^{k}+\alpha _{1}q^{k-1}+...+\alpha _{k}=0$

$P(q)=\sum _{j=0}^{k}\alpha _{k}q^{k-j}$ - характеристический полном Уравнение $P(q)=0$ имеет ровно $k$ корней (кратных и простых). Пусть $q_{1}$ - кратный корень кратности $r$, остальные простые:

$q=c_{1}^{(1)}q_{1}^{n}+c_{1}^{(2)}nq^{n}+...+c_{1}^{(r-1)}n^{r-1}q_{1}^{n}+c_{2}q_{2}^{n}+...+c_{m}q_{m}^{n}\quad (3)$

Общее решение уравнения: $|q_{i}|<1,n\to \infty ,|q|\to 0$

Определение. Будем говорить, что выполнено корневое условие, если все корни полнинома устойчивости по модулю меньше 1, или на гранирце круга $|q_{i}|=1$ кратных корней нет

Теорема. Если выполнено корневое условие, то метод является устойчивым (называется $O$-устойчивым)

Доказательство. из $(3)$: $|q_{i}|<1\quad \varepsilon _{n}={\overline {\varepsilon }}a^{n}\quad \varepsilon _{n}\to 0$ при $n\to \infty$

$|q_{i}|=1$, но корень не кратен. $\varepsilon _{n}={\overline {\varepsilon }}$ - погрешность не растет.

Утверждение. Все методы Рунге-Кутты и методы Адамаса являются нуль устойчивыми методами.

Р-К: $P(q)=q-1$

А: $\alpha _{0}q^{k}+\alpha _{1}q^{k-1}+0q^{k-2}+...+0=0\quad \alpha _{0}=1,\alpha _{1}=-1\quad P(q)=q^{k}-q^{k-1}$

Наличие $O$-устойчивости означает, что метод устойчив на конечном отрезке $\left[t_{0},T\right]$. Если $T\to \infty$ следует применять абсолютно устойчивые методы.

Модельная задача:

$\left.{\begin{cases}y'=\lambda y&\lambda \in C\\y(t_{0})=y_{0}&Re\lambda <0\end{cases}}\right\}\Rightarrow$ Ассимптотическая устойчивость

${\frac {1}{h}}\sum _{j=0}^{k}\alpha _{j}y_{n+1-j}=\lambda \sum _{j=0}^{k}\beta _{j}(\lambda h)y_{n+1-j}\qquad z=\lambda h$

$\sum _{j=0}^{k}(\alpha _{j}-z\beta _{j}(z))y_{n+1-j}=0\qquad \gamma =\alpha _{j}-z\beta _{j}(z)$

Для невозмущенной задачи: $\sum _{j=0}^{k}\gamma _{j}y_{n+1-j}=0\qquad y_{0},...,y_{k-1}$ - стартовые точки

$P(q,z)=\gamma _{0}q^{k}+\gamma _{1}q^{k-1}+...+\gamma _{k}=0$. Ищем $q_{1},q_{2},...,q_{n}$ (зависят от $z$)

Для явного метода Эйлера: ${\frac {y_{n+1}-y_{n}}{h}}=\lambda y_{n}$

$\varepsilon _{n+1}-(1+\lambda h)\varepsilon _{n}=0\quad q-(1+z)=0\quad \Rightarrow \quad q_{1}=1+z\quad |1+z|<1$

$-1<1+z<1\quad \Rightarrow \quad z\in (-2,0)\quad z=\lambda h;\lambda <0\Rightarrow 0<h<{\frac {2}{-\lambda }}$

Метод называется устойчивым при ограничении на шаг $h<{\frac {2}{|\lambda |}}$

Для неявного:

${\frac {y_{n+1}-y_{n}}{h}}=\lambda y_{n+1}\Rightarrow {\frac {1}{1-\lambda h}}=q\Rightarrow |1-\lambda h|<1$ - верно т.к. $\lambda <0$

Ограничений на $h$ нет. Область устойчивости: $|1-z|<1$

Определение. Метод называется абсолютно устойчивым при конкретном значении $z=\lambda h$ если все его корни полинома устойчивости лежат внутри единичного круга, а на границе нет кратных корней. Множество точек $z$ комплексной плоскости в которых выполнено корневое условие называется областью абсолютной устойчивости метода.

Определение. Численный метод называется $A$-устойчивым, если область абсолютой устойчивости включает в себя полу плоскость $Rez<0$

Неявный метод Эйлера $A$-устойчив

Понятие о жестких задачах

$S={\frac {\max |Re\lambda _{i}(A)|}{\min |Re\lambda _{i}(A)|}},\quad S$ - число жесткости системы

$s\gg 10$ - система жесткая. Для таких задач надо применять $A$-жесткие методы.