Явные методы Адамса-Башфорта
Адамс-Башфорт — самое известное семейство явных многошаговых методов. Их идея красива: вместо того чтобы прощупывать промежуточные точки, мы проводим многочлен через прошлые наклоны и аккуратно его интегрируем.
Метод Адамса-Башфорта — явный многошаговый метод, в котором приращение решения за шаг получают интегрированием интерполяционного многочлена, построенного по нескольким предыдущим значениям правой части f.
Запишем точное соотношение, из которого всё выводится. Решение в новой точке отличается от старого на интеграл от правой части: y(t_{n+1}) = y(t_n) + интеграл от t_n до t_{n+1} от f(t, y(t)) dt. Проблема в том, что подынтегральная функция f(t, y(t)) нам по-настоящему неизвестна — мы знаем её значения только в узлах сетки, где уже посчитали наклоны. Идея Адамса: заменить неизвестную f на интерполяционный многочлен, проходящий через несколько последних известных наклонов f_n, f_{n-1}, ..., а затем честно проинтегрировать этот многочлен от t_n до t_{n+1}. Многочлен интегрируется аналитически, и получается готовая формула с фиксированными коэффициентами.
Формула AB2
Возьмём два последних наклона: f_n в точке t_n и f_{n-1} в точке t_{n-1}. Через две точки проходит ровно одна прямая (многочлен первой степени). Если провести эту прямую через (t_{n-1}, f_{n-1}) и (t_n, f_n) и проинтегрировать её от t_n до t_{n+1}, после упрощения получится формула двухшагового метода Адамса-Башфорта порядка 2:
AB2 (порядок 2):
y_{n+1} = y_n + (h/2) * (3*f_n - f_{n-1})Прочитаем её содержательно. Мы берём текущий наклон f_n с весом 3 и вычитаем прошлый наклон f_{n-1} с весом 1, всё это умножаем на h/2. Комбинация 3*f_n - f_{n-1} — это, по сути, экстраполяция наклона вперёд: прямая, проведённая через два прошлых наклона, продлевается в будущее. Метод как бы говорит: «наклон рос вот так, продолжим тенденцию». Никаких новых вызовов f внутри шага не нужно — оба числа уже есть в истории, поэтому AB2 явный и очень дешёвый: один новый вызов f на шаг (только чтобы посчитать f в свежей точке для будущих шагов).
Коэффициенты AB3 и AB4
Если взять больше прошлых точек, многочлен будет выше степенью, а метод — выше порядком. Через три точки проходит парабола (даёт AB3, порядок 3), через четыре — кубика (даёт AB4, порядок 4). Выводить коэффициенты вручную утомительно, но они давно посчитаны и табулированы. Их полезно держать под рукой:
AB2 (порядок 2):
y_{n+1} = y_n + (h/2) * (3*f_n - f_{n-1})
AB3 (порядок 3):
y_{n+1} = y_n + (h/12) * (23*f_n - 16*f_{n-1} + 5*f_{n-2})
AB4 (порядок 4):
y_{n+1} = y_n + (h/24) * (55*f_n - 59*f_{n-1} + 37*f_{n-2} - 9*f_{n-3})Заметьте закономерность: коэффициент при самом свежем наклоне f_n всегда самый большой и положительный, а у более старых наклонов знаки чередуются. Сумма всех коэффициентов в скобках равна знаменателю — это свойство гарантирует, что метод точно воспроизводит постоянную правую часть. AB4 при том же порядке 4, что и RK4, требует только один вызов f на шаг против четырёх — в этом и состоит обещанная экономия.
Зачем экономить вызовы f
Может показаться, что разница между «один вызов f на шаг» и «четыре вызова» — мелочь, ведь арифметика всё равно быстрая. Но правая часть f — это не всегда дешёвая формула вроде y' = y. В настоящих задачах вычисление f на одном шаге может означать решение системы из тысяч уравнений, обращение к большой физической модели, интерполяцию табличных данных или даже отдельный расчёт на суперкомпьютере. Когда один вызов f стоит секунды или минуты машинного времени, сокращение их числа в четыре раза напрямую сокращает счёт вчетверо. Именно поэтому многошаговые методы любят в задачах с дорогой правой частью: они не прощупывают промежуточные точки заново, как методы Рунге-Кутты, а переиспользуют уже посчитанные наклоны из истории — те наклоны, что были честно вычислены на прошлых шагах и теперь просто хранятся в памяти. История наклонов работает как накопленный капитал: один раз посчитал f, и потом этот результат участвует в нескольких последующих шагах.
За эту экономию приходится платить двумя неудобствами, о которых стоит знать заранее. Первое — проблема старта: на самом первом шаге истории ещё нет, у нас есть только начальная точка, и формуле AB просто нечего подставить вместо f_{n-1}. Поэтому первые шаги приходится делать «разгоном» — одношаговым методом (например, RK4), который не нуждается в истории и сам её создаёт. Второе — проблема смены шага: коэффициенты AB выведены в предположении, что узлы лежат на равномерной сетке с постоянным шагом h. Если посреди счёта захочется уменьшить или увеличить шаг (а адаптивные алгоритмы делают это постоянно), вся накопленная история перестаёт соответствовать новому шагу, и её приходится либо пересчитывать, либо заново разгоняться. Методы Рунге-Кутты от этого свободны — они на каждом шаге начинают с чистого листа, и в этом их гибкость. Выбор между семействами — это всегда обмен: дешевизна шага у Адамса против простоты управления шагом у Рунге-Кутты.
Как работает под капотом
Реализуем AB2 честно. Сложность ровно одна — разгон: для первого шага AB2 нужны два наклона, f_0 и f_1, но в начале у нас есть только точка t_0. Поэтому первый шаг (получение y_1) делаем одношаговым методом порядка не ниже 2 — возьмём RK4, он заведомо точен. После этого у нас в истории два наклона, и дальше крутим дешёвую формулу AB2. Решим эталонную задачу y' = y с y_0 = 1 на отрезке [0, 1] с шагом h = 0.1; точное решение — math.exp(t).
import math
h = 0.1
f = lambda t, y: y # правая часть, y' = y
def rk4_step(t, y, h): # одношаговый разгон
k1 = f(t, y)
k2 = f(t + h/2, y + h/2*k1)
k3 = f(t + h/2, y + h/2*k2)
k4 = f(t + h, y + h*k3)
return y + h/6*(k1 + 2*k2 + 2*k3 + k4)
ts = [0.0]
ys = [1.0]
# --- разгон: первый шаг через RK4 ---
y1 = rk4_step(0.0, 1.0, h)
ts.append(0.1)
ys.append(y1)
fs = [f(0.0, 1.0), f(0.1, y1)] # история двух наклонов
# --- основной цикл AB2 ---
for n in range(1, 10):
yn, fn, fn1 = ys[n], fs[n], fs[n-1]
ynew = yn + h/2 * (3*fn - fn1) # AB2
tnew = ts[n] + h
ts.append(tnew)
ys.append(ynew)
fs.append(f(tnew, ynew)) # 1 новый вызов f
print(' t AB2 точное ошибка')
for i in range(len(ts)):
exact = math.exp(ts[i])
err = abs(ys[i] - exact)
print(f'{ts[i]:.1f} {ys[i]:.6f} {exact:.6f} {err:.2e}')Вывод:
t AB2 точное ошибка 0.0 1.000000 1.000000 0.00e+00 0.1 1.105171 1.105171 8.47e-08 0.2 1.220946 1.221403 4.56e-04 0.3 1.348830 1.349859 1.03e-03 0.4 1.490107 1.491825 1.72e-03 0.5 1.646182 1.648721 2.54e-03 0.6 1.818603 1.822119 3.52e-03 0.7 2.009085 2.013753 4.67e-03 0.8 2.219518 2.225541 6.02e-03 0.9 2.451991 2.459603 7.61e-03 1.0 2.708814 2.718282 9.47e-03
Точка t = 0.1 почти идеальна — её посчитал RK4, у которого ошибка крошечная. Дальше работает AB2, и ошибка растёт плавно, оставаясь порядка тысячных при h = 0.1. Это поведение метода второго порядка: уменьшив h вдвое, мы ожидали бы падения ошибки примерно вчетверо. Главное — мы получили результат, потратив всего один вызов f на каждый шаг после разгона.
Частые ошибки
- Разгон методом низкого порядка. Если первый шаг сделать обычным Эйлером (порядок 1), его ошибка попадёт в историю наклонов и испортит точность всего последующего AB2. Стартовый метод должен быть не ниже порядка основного.
- Знак в формуле. Правильно 3*f_n - f_{n-1}, а не 3*f_n + f_{n-1}. Минус перед старым наклоном — часть экстраполяции; перепутанный знак ломает порядок метода.
- Не добавить новый наклон в историю. После вычисления y_{n+1} обязательно нужно посчитать f в этой точке и положить в историю — иначе на следующем шаге метод возьмёт устаревшие наклоны.
- Считать AB методом «вообще без вызовов f». Один свежий вызов на шаг всё же нужен — чтобы пополнить историю для будущих шагов. Экономия в том, что их один, а не четыре.
Итоги
- Адамс-Башфорт интегрирует интерполяционный многочлен, проведённый через прошлые наклоны f.
- AB2: y_{n+1} = y_n + (h/2)(3*f_n - f_{n-1}) — экстраполяция наклона вперёд, порядок 2.
- AB3 и AB4 берут больше прошлых точек и дают порядок 3 и 4; коэффициенты табулированы, знаки у старых наклонов чередуются.
- Все AB-методы явные: один новый вызов f на шаг, против четырёх у RK4 того же порядка.
- Первый(е) шаг(и) требуют разгона одношаговым методом не ниже того же порядка.