\myAddDate{27}{04}{09}
\section{Оценка точности на примере 2-х этапного метода Рунге-Кутта}

\begin{equation}
	\label{eq_5_2_3_1}
	\begin{cases}
		\frac{du}{dt} = f(t, u(t)), \quad t > 0 \\
		u(0) = u_0
	\end{cases}
\end{equation}

\[
\frac{y_{n+1} - y_n}{\tau} = (1-\sigma)f(t_n,y_n) + \sigma f(t_n + at, y_n + a\tau f(t_n,y_n))\]
\[ y_0 = u_0 \] \[ t_n \in \omega_{\tau} \]

\(\sigma\) - параметр, в качестве которого можно выбирать любое число, лишь бы выполнялось условие второй погрешности аппроксимации. Обычно выбирают \( \sigma \in [0,1] \).

 а  - некоторая константа. Будем рассматривать \( a \geq 0 \), но, вообще говоря, это необязательно. 

Введем функцию погрешности \( z_n \):

\begin{equation}
  \label{eq_5_2_3_2}	  
  z_n = y_n - u(t_n) = y_n - u_n \Rightarrow
\end{equation}

\begin{equation}
  \label{eq_5_2_3_3}
  \frac{z_{n+1} - z_n}{\tau} = - \frac{u_{n+1} - u_n}{\tau} + (1-\sigma)f(t_n, y_n) + \sigma f(t_n + a \tau, y_n + atf(t_n, y_n))
\end{equation}

Для сходимости нужно показать, что:

\[ |z_n| \rightarrow 0, \quad n \rightarrow \infty \]

Покажем, что \( |z_n| \leq M \tau^2, \quad \mbox{где M не зависит от $\tau$} \)

\[ \frac{z_{n+1} - z_n }{\tau} = - \frac{ u_{n+1} - u_n }{\tau} + (1-\sigma)f(t_n, u_n) + \] 
\[ \sigma f (t_n + a \tau, u_n + a \tau f(t_n, u_n)) - (1-\sigma)f(t_n, u_n) + \]
\[ (1-\sigma)f(t_n, y_n) - \sigma f(t_n + a \tau, u_n + a \tau f(t_n, u_n)) + \]
\[  \sigma f(t_n + a\tau, y_n + a\tau f(t_n, y_n)) = \psi_n + \phi_n^{(1)} + \phi_n^{(2)} \]

где \( \psi_n,  \phi_n^{(1)}, \phi_n^{(2)} \) обозначены слагаемые:

\[
\psi_n =  - \frac{ u_{n+1} - u_n }{\tau} + (1-\sigma)f(t_n, u_n) + \sigma f (t_n + a \tau, u_n + a \tau f(t_n, u_n)), \]

\begin{equation}
  \label{eq_5_2_3_4}
   \phi_n^{(1)} = (1-\sigma)( f(t_n, y_n) - f(t_n, u_n) ), \quad  \quad \quad \quad
\end{equation}
   

\[ \phi_n^{(2)} = \sigma \Bigl[ f(t_n + a \tau, y_n+a \tau f(t_n, y_n)) - f(t_n + a\tau, u_n + a \tau f(t_n, u_n)) \Bigr]. \] 


Введем допущение: функция f по второму аргументу удовлетворяет условию Липшица с константой L.
Оценим, исходя из этого допущения, \( \phi_n^{(1)} \) и \( \phi_n^{(2)} \):

\[ |\phi_n^{(1)}| \, \leq \, (1-\sigma)|f(t_n,y_n) - f(t_n, u_n)| \, \leq \, (1-\sigma)L|y_n-u_n| = (1 - \sigma)L|z_n|, \]
\[ |\phi_n^{(2)}| \, \leq \, \sigma L|y_n + a\tau f(t_n, y_n) - u_n + a\tau f(t_n, u_n)| \, \leq \, \]
\[ \leq \, \sigma L(|y_n - u_n| + \underbrace{a}_{\geq 0} \tau L|y_n - u_n|) = \sigma L (1+a\tau L) |\underbrace{y_n - u_n}_{z_n}| \]

Из \eqref{eq_5_2_3_3} \( \Rightarrow \)

\[ z_{n+1} = z_n + \tau \psi_n + \tau \phi_n^{(1)} + \tau \phi_n^{(2)} \]
\[ |z_{n+1}| \leq |z_n| + \tau |\psi_n| + \tau \bigl[ (1-\sigma)L|z_n| + \sigma L |z_n| + \sigma a \tau L^2|z_n| \bigr] =
\]
\[ \tau |\psi_n| + (1+\tau L + \tau^2 a \sigma L^2)|z_n| \]

Рассмотрим \( \sigma a \leq 0,5 \), заметив, что \( 1+\tau L + 0,5 \tau^2 L^2 \) являются первыми членами разложения по Тейлору функции \( e^{\tau L} \):

\begin{equation}
	\label{eq_5_2_3_4_no2}
 |z_{n+1}| \leq \tau|\psi_n| + (1+\tau L + 0,5 \tau^2 L^2)|z_n| \leq e^{\tau L}|z_n| + \tau|\psi_n| 
\end{equation}

Обозначим \( e^{\tau L}  = \rho \). Получим оценку:

\begin{equation}
	\label{eq_5_2_3_5}
|z_{n+1}| \leq \rho |z_n| + \tau |\psi_n|
\end{equation}

Соотношение \eqref{eq_5_2_3_5} можно рассмотреть как рекуррентную формулу. Легко видеть, что:

\[ z_{n+1} \leq \rho^{n+1}|z_0| + \sum_{j=0}^{n} \rho^{n-j} \tau |\psi_j| \]
\[ |z_{n+1}| \leq \max_{0 \leq j \leq n}|\psi_j|\sum_{j=0}^{n} \rho^{n-j} \tau  \,\leq\, t_{n+1}e^{Lt_{n+1}}\max_{0 \leq j \leq n}|\psi_j| \]

Окончательно, получаем:

\begin{equation}
	\label{eq_5_2_3_6}
   |z_{n+1}| \leq  M \max_{0 \leq j \leq n}|\psi_j|, \quad \mbox{M не зависит от } \tau
\end{equation}

Видно, что точность будет совпадать с порядком погрешности аппроксимации, а именно:
\begin{enumerate}
	\item \( \sigma a = 0,5  \Rightarrow \psi = O(\tau^2) \Rightarrow |z_n| = O(\tau^2)\), т.е. имеем второй порядок погрешности.
	\item \( \sigma = 0, \forall a \Rightarrow \psi = O(\tau), \quad\ |z_n| \leq M_1\tau, \quad M_1 \) не зависит от \( \tau \), получаем первый порядок точности.  
\end{enumerate}

\section{Многошаговые разностные методы}
\begin{equation}
	\label{eq_5_2_4_1}
	\begin{cases}
		\frac{du}{dt} = f(t, u(t)), \quad t>0\\
		u(0) = u_0
	\end{cases}
\end{equation}

Введем сетку \( \omega_{\tau} = \bigl\{ t_n = n\tau, \, \tau > 0, n=0,1,\ldots  \bigr\} \).

Обозначим \( y_k = y(t_k), \, f_k= f(t, y_k) \).

\begin{myUnnumberedDefinition}
Линейным m-шаговым разностным методом решения задачи \eqref{eq_5_2_4_1} называется метод, записанный уравнением:
\begin{equation}
	\label{eq_5_2_4_2}
    \sum_{k=0}^{m}\frac{a_k}{\tau}y_{n-k} = \sum_{k=0}^{m}b_kf_{n-k},
\end{equation}

где \(a_k, b_k\) - числа, \( \tau >0 \). При этом \( a_0 \neq 0, \, b_m \neq 0, \, n=m, m+1, \ldots \)
\end{myUnnumberedDefinition}

Если \( b_0 = 0 \), то \eqref{eq_5_2_4_2} - явный метод. Если \( b_0 \neq 0 \), то \eqref{eq_5_2_4_2} - неявный метод.

Для начала вычислений по формуле \eqref{eq_5_2_4_2} необходимы значения \( y_0, \ldots, y_{m-1}\) - т.н. ``Разгонный этап''. Так как формула \eqref{eq_5_2_4_2} однородна по \(a_k\) и \(b_k\), то полагают \( \sum_{k=0}^{m}b_k = 1 \)(условие нормировки).

Неявный \(m\)-шаговый разностный метод записывается в виде

\begin{equation}
 \label{eq_5_2_4_3}
 \frac{a_0}{\tau}y_n - b_0 f(t_n, y_k) = F(y_{n-1}, y_{n-2}, \ldots, y_{n-m})
\end{equation}
\[ F = \sum_{k=1}^{m}b_k f_{n-k} - \sum_{k=1}^{m}\frac{a_k}{\tau}y_{n-k} \]

Уравнение \eqref{eq_5_2_4_3} решается чаще всего методом Ньютона, 
причем в качестве \( y_n^{(0)} \) берется \( y_{n-1}\). В явном
разностном методе значения \( y_n \) находятся по явной формуле

\[ y_n = \frac{\tau}{a_0}\Bigl( \sum_{k=1}^{m} b_k f_{n-k} - \sum_{k=1}^{m}\frac{a_k}{\tau}y_{n-k} \Bigr) \]

Оценим погрешность аппроксимации на решении

\begin{equation} 
  \label{eq_5_2_4_4}
  \psi_n = - \sum_{k=0}^{m}\frac{a_k}{\tau}u_{n-k} + \sum_{k=0}^{m}b_k f(t_{n-k}, u_{n-k})
\end{equation}

\[ u_{n-k} = u(t_n - k\tau) = \sum_{l=0}^{p}\frac{ (-k\tau)^l }{l!}u^{(l)}(t_n) + O(\tau^{p+1}) \]
\[ f(t_{n-k}, u_{n-k}) = u_{n-k}' = \sum_{l=0}^{p-1} \frac{ (-k\tau)^l }{l!}u^{(l+1)}(t_n) + O(\tau^p) \]

\[ \psi_n = - \sum_{k=0}^{m}\frac{a_k}{\tau}\sum_{l=0}^{p} \frac{ (-k\tau)^l }{l!}u^{(l)}(t_n) + \sum_{k=0}^{m}b_k \sum_{l=0}^{p-1}u^{(l+1)}(t_n) + O(\tau^p) = \]
\[= \Bigl\{ \mbox{сдвиг индексов} \Bigr\} = - \sum_{l=0}^{p}\sum_{k=0}^{m} \frac{a_k}{\tau} \frac{ (-k\tau)^l }{l!}u^{(l)}_n + \]
\[ \sum_{l=1}^{p}\sum_{k=0}^{m}b_k \frac{ (-k\tau)^{l-1} }{(l-1)!}u_n^{(l)} + O(\tau^p) = \]
\[ -\sum_{k=0}^{m}\frac{a_k}{\tau}u_n + \sum_{k=0}^{m}\Bigl[  \sum_{l=1}^{p}(-k\tau)^{l-1}(a_kk + lb_k)\frac{u_n^{(l)}}{l(l-1)!} \Bigr] + O(\tau^p)\]

Условие аппроксимации: \[ \sum_{k=0}^{m}a_k = 0 \]

Для достижения аппроксимации порядка p должно быть выполнено соотношение:

\[ \sum_{k=0}^{m}k^{l-1}(a_kk+lb_k) = 0, \quad l=1,2,\ldots,p \]

В многошаговом методе 2m+2 неизвестных - \( a_0, a_1, \ldots, a_m, b_0, \ldots, b_m \), и p+2 уравнений. Чтобы система не была переопределенной, должно выполняться \( p \leq 2m \Rightarrow \) наивысший порядок аппроксимации равен 2m.

Таким образом, для достижения порядка погрешности аппроксимации \(p\) должны выполняться следующие соотношения:
\[ a_0 = - \sum_{k=1}^{m}a_k \]
\[ b_0 = 1 - \sum_{k=1}^{m}b_k\]
\[ \sum_{k=0}^{m}k^{l-1}(a_kk+lb_k) = 0, \quad l=1,2,\ldots,p \]
