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

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

Definition

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

Scope

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

Core questions

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

Key theories

Нулевая устойчивость и корневое условие

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

Барьеры Дальквиста

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

Mechanisms

Методы Адамса интегрируют интерполирующий полином через прошлые значения производных: Адамс-Башфорт использует только известные значения (явный), Адамс-Моултон включает неизвестное новое значение (неявный) для большей точности и устойчивости. На практике эти два метода объединяются в пару предиктор-корректор: явная формула предсказывает, неявная корректирует, обычно за одну или две итерации. Формулы обратного дифференцирования вместо этого используют разности прошлых значений решения для аппроксимации производной в новой точке, что дает жестко-устойчивые методы, лежащие в основе кодов для жестких ОДУ. Поскольку многошаговым методам требуется несколько начальных значений, они запускаются с помощью одношагового метода.

Clinical relevance

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

History

Адамс и Башфорт представили многошаговые формулы в девятнадцатом веке, а Моултон добавил неявные варианты; анализ Дальквиста в 1950-х–1960-х годах установил теорию устойчивости и барьеры порядка, которые управляют этой областью, а работа К. Уильяма Гира в 1970-х годах сделала коды формул обратного дифференцирования стандартом для жестких задач.

Key figures

• John Couch Adams
• Francis Bashforth
• Forest Ray Moulton
• Germund Dahlquist
• C. William Gear

Seminal works

• hairer1993
• iserles2008

Frequently asked questions

Чем многошаговые методы отличаются от методов Рунге-Кутты?

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

Что такое корневое условие?

Это требование, чтобы корни первого характеристического полинома метода лежали внутри или на единичной окружности, причем граничные корни должны быть простыми. Оно гарантирует, что малые ошибки не усиливаются по мере накопления шагов, обеспечивая нулевую устойчивость метода и, следовательно, его сходимость.