Адаптивные методы интегрирования ОДУ: алгоритмы Рунге-Кутты-Фельберга

Компромисс между скоростью и точностью: проблема постоянного шага

Решение обыкновенных дифференциальных уравнений (ОДУ) методами Рунге-Кутты, которые мы рассматривали ранее, часто проводится с постоянным шагом интегрирования. Однако в реальных физических системах характер процессов может резко меняться с течением времени. Представьте космический аппарат, который летит к Луне. Большую часть пути гравитационные поля меняются очень плавно, и траекторию можно рассчитывать с огромным шагом (например, раз в час). Но при подлете к орбите Луны и выполнении маневров гравитационные силы начинают меняться стремительно. Если оставить прежний большой шаг, расчетная траектория грубо отклонится от реальной. Если же с самого начала установить микроскопический шаг «с запасом» для прохождения сложных участков, то расчет простого участка пути займет неоправданно много времени процессора.

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

Вложенные методы и оценка локальной погрешности

Блестящее решение этой проблемы предложил немецкий математик Эрвин Фельберг в 1969 году. Он разработал концепцию вложенных методов Рунге-Кутты. Идея заключается в том, чтобы на каждом шаге вычислять новое приближение функции сразу двумя методами разного порядка точности (например, четвертого и пятого порядка).

Если бы мы делали это «в лоб», объем вычислений возрос бы в два раза. Гениальность идеи Фельберга (и последующих авторов, таких как Дорман и Принс) состоит в том, что коэффициенты для методов 4-го и 5-го порядков подбираются специальным образом. Они используют одни и те же промежуточные вычисления (те самые коэффициенты наклона касательных внутри шага). То есть, вычислив набор наклонов для метода 5-го порядка, мы можем путем простого перемножения с другими весами получить и результат для 4-го порядка практически бесплатно! Разность между результатами 5-го и 4-го порядка служит превосходной оценкой локальной ошибки (погрешности усечения) на данном шаге.

Алгоритм управления шагом (Step Size Control)

Имея оценку локальной ошибки, программа-решатель включает встроенный ПИД-регулятор шага. Пользователь заранее задает желаемую допустимую погрешность (tolerance). Алгоритм сравнивает вычисленную оценку ошибки с заданным допуском.

Если ошибка оказалась больше допуска, это означает, что шаг был слишком велик. Алгоритм отбрасывает вычисленное значение, уменьшает шаг по специальной формуле (обычно умножая на коэффициент около 0.8 от расчетного оптимального, чтобы иметь запас надежности) и пересчитывает этот участок заново. Если же ошибка оказалась значительно меньше допуска, алгоритм принимает шаг как успешный, но для следующего шага автоматически увеличивает размер интервала, ускоряя симуляцию. Метод Рунге-Кутты-Фельберга (RKF45) и его более современная модификация, метод Дормана-Принса (DOPRI5), стали мировым стандартом адаптивного интегрирования и используются по умолчанию во встроенных функциях MATLAB (ode45) и библиотеках SciPy в Python.