§ 1.6. Многошаговые методы

В этом параграфе описывается класс многошаговых методов.

1.6.1. Одношаговые и многошаговые методы.

Как уже говорилось, все рассмотренные выше методы являлись одношаговыми: для нахождения значения (j_t)_i приближенного решения j_t в точке t_i использовалось только значение (j_t)_i-1 приближенного решения в предыдущей точке t_i-1. Представляется вероятным, что использование дополнительной (уже имеющейся) информации, а именно, значений (j_t)_i-2, (j_t)_i-3, ..., позволит улучшить точность метода. Методы, использующие при вычислении (j_t)_i значения (j_t)_i-1, ..., (j_t)_i-p называются p-шаговыми методами. Подчеркнем, что пока не будет оговорено противное, мы предполагаем (это существенно), что сетка G_t равномерная.

1.6.2. Явные методы Адамса.

Итак, допустим к настоящему моменту мы вычислили значения x_i-1, ..., x_i-p приближенного решения в узлах сетки t_i-1, ..., t_i-p. Уравнение (E) эквивалентно (см. п. 1.1.4) интегральному уравнению

x(t) = x(ti-1) +  т t ti–1 f[s, x(s)] ds.

В частности, при t = t_i

x(ti) = x(ti-1) +  т ti ti–1 f[s, x(s)] ds.

(1)

Не известную нам подынтегральную функцию s ® f[s, x(s)] можно приблизить интерполяционным полиномом P, построенным по узлам t_i-1, ..., t_i-p, но поскольку нам неизвестны и значения f[t_j, x(t_j)] этой функции в узлах, при построении полинома P мы воспользуемся приближенными значениями, считая, что f[t_j, x(t_j)] » f(t_j, x_j) (j = i - p, ..., i - 1). Тогда

x(ti) » xi-1 +  т ti ti–1 P(s) ds.

Таким образом, мы приходим к так называемому явному p-шаговому методу Адамса

xi = xi-1 +  т ti ti–1 P(s)ds.

(2)

в котором P — интерполяционный полином, построенный по узлам t_i-1, ..., t_i-p и значениям f(t_i-1, x_i-1), ..., f(t_i-p, x_i-p).

Разумеется, (2) представляет собой лишь "заготовку" для метода. Конкретные методы получаются после вычисления коэффициентов интерполяционного полинома и интеграла.

Задача 1.6.1. Покажите, что явный одношаговый метод Адамса есть явный метод Эйлера

1.6.3. Пример: явный двухшаговый метод Адамса.

Интерполяционный полином P (в форме Лагранжа) в случае p = 2, очевидно, имеет вид

P(s) =  s - ti-2 ti-1 - ti-2 f(ti-1, xi-1) +  s - ti-1 ti-2 - ti-1 f(ti-2, xi-2).

Тогда, после несложных вычислений, учитывая, что t_i - t_i-1 = t_i-1 - t_i-2 = t, получаем

т ti ti–1 P(s)ds =  t 2 [3f(ti-1, xi-1) - f(ti-2, xi-2)].

Таким образом, явный двухшаговый метод Адамса имеет вид

xi = xi-1 +  t 2 [3f(ti-1, xi-1) - f(ti-2, xi-2)].

(3)

Задача 1.6.2. Выведите явный трехшаговый метод Адамса

Обратим внимание на новое обстоятельство. Формула (3) неприменима при i = 1: для нахождения x₁ необходимо знать x_-1. Проблему "начального запуска" многошаговых методов мы обсудим чуть позднее.

1.6.4. Неявные методы Адамса.

Заметим, что при выводе явных методов Адамса мы использовали значения интерполяционного полинома P на отрезке [t_i-1, t_i]. Узлы же интерполяции лежат вне и, более того, по одну сторону от этого отрезка. Известно, что в таких случаях интерполяционный полином является плохим приближением. Чтобы избежать такой ситуации, добавим к нашим узлам интерполяции узел t_i и (неизвестное) значение f(t_i, x_i), обозначив получившийся полином через Q. В результате мы получим неявный p-шаговый метод Адамса

xi = xi-1 +  т ti ti–1 Q(s)ds.

(4)

где Q — интерполяционный полином, построенный по узлам t_i-p, ..., t_i и значениям f(t_i-p, x_i-p), ..., f(t_i, x_i). Подчеркнем (ср. с явными и неявными методами Рунге — Кутты), что метод (4), в отличие от метода (3), не дает явной формулы для вычисления x_i, но представляет собой уравнение, которое должно быть разрешено относительно x_i.

Задача 1.6.3. Покажите, что в случае p = 0 получается неявный метод Эйлера.

Задача 1.6.4. Выведите неявные двух- и трехшаговые методы Адамса.

Явные методы Адамса часто называют методами Адамса — Бэшфорта, а неявные — методами Адамса — Мултона.

1.6.5. Линейные многошаговые методы.

Описанные выше методы укладываются в следующую общую конструкцию. Метод

p е s = 0 asxi-s = t p е s = 0 bs f(ti-s, xi-s)

(5)

называется линейным p-шаговым методом. Например, при p = 2, a₀ = 1, a₁ = -1, a₂ = 0, b₀ = 0, b₁ = 3/2, b₂ = -1/2 метод (5) представляет собой явный двухшаговый метод Адамса.

Методы (5) называются линейными, потому что в левой части стоит линейный оператор. Если b₀ = 0, то они называются (являются) явными, в противном случае — неявными. Мы всегда предполагаем, что a₀ № 0 (чтобы x_i всегда фигурировал в уравнении (5)). Более того, не ограничивая общности, можно предполагать, что a₀ = 1. Коэффициенты a_s, b_s в (5) можно находить из разных соображений. Выше мы рассмотрели два таких приема.

1.6.6. Проблема "запуска" многошаговых методов.

Как уже отмечалось, формулы (2) так же, как и (4), (5), не являются разностными схемами (вернее, являются неполными разностными схемами), поскольку в них не заданы формулы (уравнения) для вычисления p начальных значений. Здесь нельзя просто положить, например, x_i = x⁰ при i = 0, ..., p - 1, поскольку эти значения будут аппроксимировать j(t₀) только с точностью O(t); если же сами методы являются методами высокого порядка точности, то перенесенная начальная погрешность сведет на нет все преимущества метода. Обычно поступают так. Либо насчитывают первые p значений с помощью одношагового метода того же порядка точности, либо используют методы более низкого порядка, но при этом используют более мелкий шаг, чтобы получить через соответствующее число шагов начальные значения с нужной точностью. Помимо всего прочего, необходимость в начальном запуске очевидно приводит в увеличению объема работы по программированию метода.

1.6.7. Сходимость многошаговых методов.

Без описания процесса запуска многошагового метода мы не можем воспользоваться определениями п. 1.2.6, поскольку в них фигурируют неопределенные начальные значения. Чтобы выделить свойства самогó многошагового метода безотносительно к выбору процедуры запуска, модифицируем определение сходимости многошаговых методов. Будем говорить, что метод (5) сходится с k-м порядком, если найдутся константы C₀ и C такие, что для любых решений j задачи (E) – (C) и любых начальных значений (j_t)₀, ..., (j_t)_p-1, удовлетворяющих условию

||(jt)i - (Ptj)i|| Ј C0tk,   i = 0, ..., p - 1,

выполнено неравенство

||jt - Ptj|| t Ј Ctk.

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

1.6.8. Аппроксимация многошаговых методов.

При определении порядка аппроксимации многошаговых методов можно, как в п. 1.2.7, воспользоваться неравенством ||F_tP_tj||_t Ј C_at^k, но для этого нужно будет определить разностный оператор F_t на начальных значениях, т. е. опять привязаться к конкретной процедуре запуска. Здесь мы определим порядок аппроксимации в терминах локальной погрешности (ср. с п. 1.5.3). Локальной погрешностью линейного p-шагового метода (5) (в точке (t, x)) назовем величину

e(t, x, t) = j(t + pt) - (jt)p,

где j — решение уравнения (E), проходящее через точку (t, x), а j_t — приближенное решение, полученное методом (5) с точными начальными условиями

(jt)0 = j(t),   (jt)1 = j(t + t),  ...,  (jt)p-1 = j[t + (p - 1)t]

(6)

(рис. 8).

Рис. 8.

Говорят, что метод (5) является методом k-го порядка аппроксимации, если ||e(t, x, t)|| Ј Ct^k+1 с некоторой не зависящей от t, x и достаточно малых t константой C; другими словами, если e(t, x, t) = O(t^k+1) (ср.с (1.5.4)).

Локальная погрешность многошаговых методов выражается (также, как и для одношаговых) через f и коэффициенты метода. Для этого обозначим для любой дифференцируемой функции x: R ® R^m агрегат

p е s = 1 as y(t - st) - t p е s = 1 bs yў(t - st)

через D(t, y, t). Оказывается тогда, что в случае скалярного уравнения

e(t, x, t) =  D(tp, j, t) a0 -tb0 fx(tp, J) ,

(7)

где J О (j(t +t_p), (j_t)_p), а j — как и выше, решение уравнения (E), проходящее через точку (t, x).

Действительно, в силу (5) и (6) (j_t)_p удовлетворяет уравнению

p е s = 1 asj(tp-s) + a0(jt)p = t p е s = 1 bs f [ti-s, j(ti-s)] + tb0 f [tp, (jt)p],

откуда, добавив и отняв a₀j(t_p) - tb₀ f [t_p, j(t_p)] (= a₀j(t_p) - tb₀jў(t_p)) и использовав введенное обозначение D, после несложных преобразований получим

D(tp, j, t) = a0[j(tp) - (jt)p] - tb0(f[tp, j(tp)] - f[tp, (jt)p]) .

Применив к последнему слагаемому теорему Лагранжа, получим эквивалентное равенству (7) равенство

D(tp, j, t) = a0[j(tp) - (jt)p] - tb0 fx(tp, J)[j(tp) - (jt)p] = = [a0 - tb0 fx(tp, J)]e(t, x, t).

Задача 1.6.5. Выпишите D для явного и неявного двухшаговых методов Адамса.

Задача 1.6.6. Выведите аналог формулы (7) в многомерном случае.

Если отображение f ограничено, то поскольку a₀ = 1, знаменатель в (7) при достаточно малых t равномерно отделен от нуля и поэтому e(t, x, t) и D(t_p, j, t) по t являются бесконечно малыми одного порядка. Таким образом, метод (5) обладает k-м порядком аппроксимации, если и только если

D(t, y, t) = O(tk+1)

(8)

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

В следующем пункте мы приводим выраженный в терминах коэффициентов a_s и b_s признак выполнения равенства (8).

1.6.9. Теорема о порядке аппроксимации линейных многошаговых методов.

Для того, чтобы линейный p-шаговый метод имел k-й порядок аппроксимации для любой задачи Коши с k раз непрерывно дифференцируемой правой частью необходимо и достаточно выполнения следующих условий

p е s = 0 as = 0,    p е s = 0 as(p - s)j = j p е s = 0 bs(p - s)j-1   (j = 1, ..., k)

(9)

(мы считаем здесь, что 0⁰ = 1).

Д о к а з а т е л ь с т в о.  Сохраним обозначение t_s = t + ts. Докажем (8) для всех k + 1 раз непрерывно дифференцируемых функций x. Подставим разложения

x(tp-s) =  k е j = 0 (p - s)jt j j! x(j)(t) + O(tk+1),

xў(tp-s) =  k–1 е j = 0 (p - s)jt j j! x(j+1)(t) + O(tk),

в определение D и преобразуем, используя очевидные свойства бесконечно малых O(t^k+1) + O(t^k+1) = O(t^k+1),  lO(t^k+1) = O(t^k+1),  tO(t^k) = O(t^k+1):

D(tp, x, t) =  p е s = 0  as ж и k е j = 0 (p - s)jt j j! x(j)(t) + O(tk+1) ц ш  –

–t p е s = 0  bs ж и k–1 е j = 0 (p - s)jt j j! x(j+1)(t) + O(tk) ц ш  =

=  p е s = 0 asx(t) +  p е s = 0 as  k е j = 0 (p - s)jt j j! x(j)(t) –

–  p е s = 0 bs  k–1 е j = 0 (j + 1) (p - s)jt j+1 (j + 1)! x(j+1)(t) + O(tk+1) =

=  ж и p е s = 0 as  ц ш x(t) + k е j = 1 t j j! x(j)(t)  ж и p е s = 0 as(p - s)j - j p е s = 0 bs(p - s)j–1 ц ш  + O(tk+1).

Теперь эквивалентность соотношений (8) и (9) очевидна.

Например, для явного двухшагового метода Адамса, для которого (см. п. 1.6.5) a₀ = 1, a₁ = -1, a₂ = 0, b₀ = 0, b₁ = 3/2, b₂ = -1/2, соотношения (9) выполнены при j = 1, 2 и не выполнены при j = 3. Поэтому этот метод является методом второго порядка аппроксимации.

Задача 1.6.7. Покажите, что порядок аппроксимации явных p-шаговых методов Адамса равен p, а неявных — (p + 1).

1.6.10. Замечание о постоянном шаге.

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

Задача 1.6.8. Постройте явный двухшаговый метод Адамса на неравномерной сетке.

Такие методы требуют пересчета коэффициентов на каждом шаге.

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

Разумеется, все эти способы увеличивают объем вычислительной, а также программистской работы, усложняют логику программ и т. п.

File based on translation from T_EX by T_TH, version 3.05.
Created On 28 May 2002, 18: 26.
Last modified 8 May 2002.