Адаптивный размер шага - Adaptive step size

В числовой анализ, адаптивный размер шага используется в некоторых методах для численное решение обыкновенных дифференциальных уравнений (включая особый случай численное интегрирование ) для контроля ошибок метода и обеспечения свойства устойчивости Такие как А-стабильность. Использование адаптивного размера шага особенно важно, когда существует большой разброс в размере производной. Например, при моделировании движения спутника вокруг Земли в качестве эталона. Орбита Кеплера, фиксированный метод временного шага, такой как Метод Эйлера может быть достаточно. Однако все сложнее, если кто-то хочет смоделировать движение космического корабля с учетом как Земли, так и Луны, как в Проблема трех тел. Там возникают сценарии, в которых можно делать большие временные шаги, когда космический корабль находится далеко от Земли и Луны, но если космический корабль приближается к столкновению с одним из планетных тел, тогда требуются небольшие временные шаги. Метод Ромберга и Рунге – Кутта – Фельберг являются примерами методов численного интегрирования, в которых используется адаптивный размер шага.

Пример

Для простоты в следующем примере используется простейший метод интеграции: Метод Эйлера; на практике методы высшего порядка, такие как Рунге-Кутта методы предпочтительнее из-за их превосходных свойств сходимости и стабильности.

Рассмотрим задачу начального значения

${\displaystyle y'(t)=f(t,y(t)),\qquad y(a)=y_{a}}$

куда у и ж может обозначать векторы (в этом случае это уравнение представляет собой систему связанных ОДУ с несколькими переменными).

Нам дана функция ж(т,у) и начальные условия (а, у_а), и нас интересует решение на т = б. Позволять у(б) обозначим точное решение в точке б, и разреши у_б обозначают решение, которое мы вычисляем. Мы пишем ${\displaystyle y_{b}+\varepsilon =y(b)}$, куда ${\displaystyle \varepsilon }$ - ошибка численного решения.

Для последовательности (т_п) значений т, с т_п = а + нэметод Эйлера дает приближения к соответствующим значениям у(т_п) в качестве

${\displaystyle y_{n+1}^{(0)}=y_{n}+hf(t_{n},y_{n})}$

Локальная ошибка усечения этого приближения определяется как

${\displaystyle \tau _{n+1}^{(0)}=y(t_{n+1})-y_{n+1}^{(0)}}$

и по Теорема Тейлора, можно показать, что (при условии ж достаточно гладкая) локальная ошибка усечения пропорциональна квадрату размера шага:

${\displaystyle \tau _{n+1}^{(0)}=ch^{2}}$

куда c - некоторая константа пропорциональности.

Мы отметили это решение и его ошибку значком ${\displaystyle (0)}$.

Значение c нам не известно. Давайте теперь снова применим метод Эйлера с другим размером шага, чтобы получить второе приближение к у(т_п+1). Мы получаем второе решение, которое мы помечаем ${\displaystyle (1)}$. Возьмите новый размер шага, равный половине исходного размера шага, и примените два шага метода Эйлера. Это второе решение, по-видимому, более точное. Поскольку нам приходится применять метод Эйлера дважды, локальная ошибка (в худшем случае) вдвое превышает исходную ошибку.

${\displaystyle y_{n+{\frac {1}{2}}}=y_{n}+{\frac {h}{2}}f(t_{n},y_{n})}$

${\displaystyle y_{n+1}^{(1)}=y_{n+{\frac {1}{2}}}+{\frac {h}{2}}f(t_{n+{\frac {1}{2}}},y_{n+{\frac {1}{2}}})}$

${\displaystyle \tau _{n+1}^{(1)}=c\left({\frac {h}{2}}\right)^{2}+c\left({\frac {h}{2}}\right)^{2}=2c\left({\frac {h}{2}}\right)^{2}={\frac {1}{2}}ch^{2}={\frac {1}{2}}\tau _{n+1}^{(0)}}$

${\displaystyle y_{n+1}^{(1)}+\tau _{n+1}^{(1)}=y(t+h)}$

Здесь мы предполагаем коэффициент ошибки ${\displaystyle c}$ постоянно на интервале ${\displaystyle [t,t+h]}$. В действительности скорость его изменения пропорциональна ${\displaystyle y^{(3)}(t)}$. Вычитание решений дает оценку ошибки:

${\displaystyle y_{n+1}^{(1)}-y_{n+1}^{(0)}=\tau _{n+1}^{(1)}}$

Эта оценка локальной ошибки имеет третий порядок точности.

Оценка локальной ошибки может использоваться для определения размера шага ${\displaystyle h}$ должны быть изменены для достижения желаемой точности. Например, если местная толерантность ${\displaystyle {\text{tol}}}$ разрешено, мы могли бы позволить час развиваться как:

${\displaystyle h\rightarrow 0.9\times h\times \min \left(\max \left(\left({\frac {\text{tol}}{2\left|\tau _{n+1}^{(1)}\right|}}\right)^{1/2},0.3\right),2\right)}$

В ${\displaystyle 0.9}$ является фактором безопасности для обеспечения успеха при следующей попытке. Минимум и максимум предназначены для предотвращения резких изменений предыдущего размера шага. Это должно, в принципе, давать ошибку около ${\displaystyle 0.9\times {\text{tol}}}$ в следующую попытку. Если ${\displaystyle |\tau _{n+1}^{(1)}|<{\text{tol}}}$, мы считаем шаг успешным, и оценка ошибки используется для улучшения решения:

${\displaystyle y_{n+1}^{(2)}=y_{n+1}^{(1)}+\tau _{n+1}^{(1)}}$

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

Начиная с начального размера шага ${\displaystyle h=b-a}$, эта теория облегчает нашу управляемую интеграцию ОДУ с точки ${\displaystyle a}$ к ${\displaystyle b}$, используя оптимальное количество шагов с учетом локальной устойчивости к ошибкам. Недостатком является то, что размер шага может стать слишком маленьким, особенно при использовании младшего порядка. Метод Эйлера.

Подобные методы могут быть разработаны для методов более высокого порядка, таких как метод Рунге – Кутта 4-го порядка. Кроме того, устойчивость к глобальной ошибке может быть достигнута путем масштабирования локальной ошибки до глобальной области.

Встроенные оценки ошибок

Адаптивные методы размера шага, которые используют так называемую «встроенную» оценку ошибки, включают Рунге – Кутта – Фельберг, Кэш – Карп и Дорман – Принс методы. Эти методы считаются более эффективными с точки зрения вычислений, но имеют более низкую точность оценок ошибок.

Смотрите также

• Адаптивная квадратура
• Адаптивное численное дифференцирование

Рекомендации

дальнейшее чтение

• Уильям Х. Пресс, Сол А. Теукольски, Уильям Т. Веттерлинг, Брайан П. Фланнери, Числовые рецепты на C, Второе издание, ПРЕСС КЕМБРИДЖСКОГО УНИВЕРСИТЕТА, 1992. ISBN  0-521-43108-5
• Кендалл Э. Аткинсон, Числовой анализ, Второе издание, John Wiley & Sons, 1989. ISBN  0-471-62489-6