BDF против скрытого времени Рунге Кутты

Есть ли причины, по которым следует выбирать неявную Рунге Кутту высокого порядка (IMRK), а не BDF? BDF кажется мне намного проще, так как для ступени IMRK требуется q линейных решений за шаг по времени. Стабильность для BDF и IMRK выглядит спорным вопросом. Я не могу найти никаких ресурсов, сравнивающих / противопоставляющих неявные степперы времени.$q$$q$

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

Да, по этой причине не так много ресурсов. В течение очень долгого времени стандартным goto было «просто использовать методы BDF». Эта мантра была заложена в камне по нескольким историческим причинам: для одного кода Gear был первый широко доступный жесткий решатель, а для другого комплект MATLAB не включал / не включает неявный метод RK. Однако эта эвристика не всегда верна, и я бы сказал, что при тестировании она обычно ошибочна. Позвольте мне объяснить подробно.

Методы BDF имеют высокую фиксированную стоимость

Адаптивный временной шаг и адаптивный порядок в методах BDF имеет очень высокую стоимость. Коэффициенты должны быть пересчитаны, или значения должны быть интерполированы в разное время. Было проделано много работы, чтобы сделать текущие коды BDF более эффективными (есть две хорошо известные «формы» для реализации, пытающиеся по-разному решить эту проблему), но на самом деле это просто очень сложная проблема разработки программного обеспечения. Из-за этого фактически большинство кодов BDF являются потомками оригинального кода Gear: Gears, vode, lsoda, CVODE Sundial, даже решатели DAE DASKR и DASSL являются потомками одного и того же кода.

Это означает, что если ваша проблема «слишком мала», высокая фиксированная стоимость действительно имеет значение, и методы Implicit RK будут работать лучше.

Методы BDF высокого порядка очень нестабильны для сложных собственных значений

Методы BDF позволяют контролировать максимальный порядок и делают его более консервативным по причине: методы BDF более высокого порядка не могут очень хорошо обрабатывать даже сложные собственные значения среднего размера. Таким образом, в этих случаях, чтобы быть стабильными, они должны отказаться от своего заказа. По этой причине метод BDF 6-го порядка, хотя и технически стабилен, часто игнорируется, поскольку даже у 5-го порядка здесь есть проблемы (а 6-й порядок еще менее стабилен). Только до 2-го порядка является A-стабильным, поэтому он всегда может отступить к нему, но тогда в шаге преобладает ошибка.

Таким образом, при использовании кодов BDF для нетривиальных задач вы не получаете 5-й заказ все время. Колебания вызывают падение его порядка.

Методы BDF имеют высокую стартовую стоимость

$i\tau$$\tau$

BDF-методы, будучи многошаговыми, имеют лучшее масштабирование

$f$radau

Какие тесты доступны?

Книга Хайрера и DiffEqBenchmarks (объясненные ниже), вероятно, являются лучшими с точки зрения легко доступных диаграмм точности работы. Решение обыкновенных дифференциальных уравнений Хайрера II содержит ряд диаграмм точности работы на страницах 154 и 155. Результаты по выбранным им задачам совпадают с указанными выше по причинам, изложенным выше: неявный РК будет более эффективным, если проблема не решена. «достаточно большой». Еще одна интересная вещь, которую стоит отметить, - это то, что методы Розенброка высокого порядка оказываются наиболее эффективными во многих его тестах (например Rodas) в режиме, где ошибка выше, а неявный RK radau5наиболее эффективен при меньших ошибках. Но его проблемы с тестами в основном не связаны с дискретизацией больших PDE, поэтому примите во внимание приведенные выше пункты.

Как вы тестируете / тестируете?

Мне нравится проверять это с diffrentialEquations.jl в Julia (заявление об отказе: я один из разработчиков). Это у Юлии. Язык программирования действительно должен получить примечание здесь. Помните, что при увеличении стоимости вызова функции методы BDF справляются лучше. В R / MATLAB / Python пользовательская функция является единственным кодом R / MATLAB / Python, который на самом деле должны использовать оптимизированные решатели: если вы используете обертки SciPy или Sundials, это весь код C / Fortran, за исключением передаваемой вами функции , Это означает, что в динамических языках (которые не являются Julia) методы BDF работают лучше, чем обычно, потому что вызовы функций очень неоптимизированы (это, вероятно, причина, по которой Shampine включен ode15sв набор MATLAB, но не содержит неявный метод RK) ,

$f$ODEProblem

@time sol = solve(prob,CVODE_BDF())
@time sol = solve(prob,radau())

где первый использует Sundials ' CVODE(метод BDF), а второй использует Hairer radau(неявный RK).

Для любого ODEProblemвы можете использовать инструменты тестирования, чтобы увидеть, как разные алгоритмы масштабируются для разных адаптивных допусков. Некоторые результаты размещены на DiffEqBenchmarks.jl . Например, в задаче ROBER (система из 3 жестких ODE) вы можете видеть, что солнечные часы на самом деле нестабильны и расходятся с достаточно высоким допуском (тогда как другие методы сходятся очень хорошо), показывая примечание выше о проблемах стабильности. Что касается проблемы Ван Дер Пола , вы можете видеть, что это скорее промывка. У меня есть намного больше, чем я не опубликовал, но, вероятно, не доберусь до него, пока я не закончу некоторые методы Розенброка более высокого порядка (Родас - это версия на Фортране).

(Примечание: эти жесткие тесты нуждаются в обновлении. Во-первых, текст нуждается в обновлении, поскольку по некоторым причинам методы ODE.jl расходятся ...)

Методы экстраполяции и RKC

Существуют также методы экстраполяции, подобные тем, seulexкоторые предназначены для сложных задач. Это «бесконечный адаптивный порядок», но это означает только то, что они асимптотически хороши, когда вы ищете очень низкую ошибку (т. Е. Пытаетесь решить жесткие задачи на уровне ниже 1e-10или около того, и в этом случае вы, вероятно, можете использовать явный метод) , Однако в большинстве случаев они не так эффективны и их следует избегать.

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

Другие методы для рассмотрения: специализированные методы для жестких PDE

Вероятно, следует отметить, что методы Розенброка высокого порядка действительно хороши, во много раз даже лучше, для жестких задач малого и среднего размера, когда можно легко вычислить якобиан. Тем не менее, для некоторых PDE, я считаю, что проблемы адвекции-диффузии попадают в эту категорию, Розенброк может потерять некоторые порядки точности. Кроме того, они нуждаются в очень точных якобианах, чтобы сохранить их точность. В Юлии это легко, потому что решатели идут с символической и авто-дифференциацией, которая может быть правильной для машинного эпсилона. Тем не менее, такие вещи, как MATLABode23sмогут иметь проблемы, потому что эти реализации используют конечное различие. Для BDF и неявных методов RK ошибки в якобиане приводят к более медленной сходимости, в то время как для Розенброка, поскольку они не являются неявными уравнениями и являются скорее методами RK с инверсиями Якоби, они просто теряют порядок точности.

Другие методы, на которые стоит обратить внимание, - это экспоненциальные методы RK, экспоненциальная разность во времени (ETD), неявный фактор интегрирования (IIF) и экспоненциальные методы Розенброка. Первые три используют тот факт, что во многих случаях PDE

$A$$Au$$e^A$$A$

$A$$Ju + g(u)$$J$$f = Ju + g$

Еще другие методы: последние творения

Методы, которые являются полностью неявными, очевидно, хороши для жестких уравнений. Если PDE недостаточно велик, вы не сможете эффективно «распараллелить в пространстве», чтобы использовать HPC. Вместо этого вы можете создавать параллельные по времени дискретизации, которые полностью неявны и, следовательно, хороши для жестких уравнений, но в то же время параллельны для полного использования аппаратного обеспечения. XBraid - это решатель, который использует такую ​​технику, а основными являются методы PFFAST и parareal. DiffrentialEquations.jl разрабатывает метод нейронной сети, который работает аналогично.

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

Вывод: принять асимптотические соображения с крошкой соли

$\Delta t$

Методы BDF асимптотически лучшие, но в большинстве случаев вы, вероятно, не работаете в этом режиме. Но если пространственная дискретизация имеет достаточно точек, методы BDF могут эффективно распараллеливать в пространстве (путем распараллеливания линейного решения) и будут иметь наименьшее количество вызовов функций, и, следовательно, будут делать все возможное. Но если ваша дискретизация PDE недостаточно велика, обратите внимание на неявные методы RK, Rosenbrock, RK и т. Д. Использование пакета программного обеспечения, такого как DifferentialEquations.jl, который позволяет легко переключаться между различными методами, может быть очень полезным для вас, чтобы понять, какой метод лучше всего подходит для вашей проблемной области, поскольку во многих случаях он не может быть известен заранее.

[Если у вас есть примеры проблем, которые вы хотите добавить в комплект тестирования, пожалуйста, не стесняйтесь, чтобы помочь что-то там. Я хочу сохранить очень полный ресурс по этому вопросу. Я надеюсь, что в скором времени все тесты Hairer будут представлены в готовых формах записных книжек, и я хотел бы получить другие проблемы, характерные для научных областей. Любая помощь приветствуется!]