\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 \]