与最先进的 ODE 求解器相比,显式 Runge-Kutta “tableau”方法的效果如何?它们何时会失败?

计算科学 龙格库塔
2021-11-29 08:56:19

与最先进的 ODE 求解器相比,显式 Runge-Kutta “tableau”方法的效果如何?它们何时会失败?我一直在阅读 Butcher 的 ODE 书,他在介绍表示不同 Runge-Kutta 方法的画面方面做得很好。这包括具有自适应步长大小的内置误差估计的方法,例如 Fehlberg、Vergner 或 Dorman-Prince。

我不明白这些方法与 ODE 求解器中当前最先进的方法相比如何。这些方法是否真的被使用过,或者只是出于历史原因而讨论过?如果使用它们,它们的一般限制或使用范围是什么?

顺便说一句,我注意到DifferentialEquations.jl似乎实现了几乎所有已知的tableau 方法。也就是说,它们似乎不是使用的默认方法,这也让我怀疑它们是否仍然具有现代用途。

3个回答

我认为这里的混淆是什么是“画面方法”,因为它在我们的文档中以一种非常具体的方式使用。DifferentialEquations.jl 用语中的“表格方法”是一种通过显式构建表格数组并在所述数组上执行循环来实现的方法。表格以发布的最高精度存储在 DiffEqDevTools.jl 中,并在编译时转换为正确的精度,然后再求解。这是 Tsitouras 的 5 阶方法:

https://github.com/JuliaDiffEq/DiffEqDevTools.jl/blob/master/src/ode_tableaus.jl#L866-L920

您可以直接将它们与 ExplicitRK 方法一起使用。这是它的内部perform_step功能:

https://github.com/JuliaDiffEq/OrdinaryDiffEq.jl/blob/master/src/perform_step/explicit_rk_perform_step.jl#L72-L119

然而,正如另一篇文章所提到的,当我们第一次这样做时,我们对我们可以找到的所有表格进行了文献回顾,实施了它们,测试了它们,查看了稳定性等(表格的 8000 行页面:))然后专门化了一些算法。例如,对于 Tsitoras 的方法,我们将其拆分为堆栈分配的画面

https://github.com/JuliaDiffEq/OrdinaryDiffEq.jl/blob/master/src/tableaus/low_order_rk_tableaus.jl#L497-L601

将方程专门化为常数的形式

https://github.com/JuliaDiffEq/OrdinaryDiffEq.jl/blob/master/src/perform_step/low_order_rk_perform_step.jl#L609-L656

为其添加了一个特殊的插值,修改了一些默认的自适应幻数等,以专门优化该算法。我们还有一个特征系统,例如硬编码有关执行刚度检测和自动切换到隐式方法所需的稳定区域的特定常数。我们为其他一些 RK 方法做到了这一点。许多这些优化只有在以下情况下才真正重要f很便宜,但是因为这在很多情况下都会出现(参数估计和搜索,混沌系统的分析),我们花时间来做这个,测试它,并且性能方面会推荐这些实现而不是纯基于表格的形式. 请注意,它在数学上是相同的方法,但此公式不需要对常量进行循环,而是采用 LLVM 优化得非常好的形式。当方程很小时,Julia 实际上会符合用户的f导数函数,求解器将构建完全不同且高效的东西。

但这只是优化,只是一个DifferentialEquations.jl 的事情。显式 RK 方法、隐式 RK 方法、Rosenbrock 方法等都可以作为表格形式的方法来讨论,这些都是相当不错的方法。上面显示的 Tsitorious 方法实际上是生态系统的核心默认值之一,类似的方法是您可能知道的 Dormand-Prince 方法ode45. 这些仍然是最先进的(至少对于非刚性方程,以及与 PI 自适应及其特殊插值配对时)。这些是随处可见的推荐方法,以及一些非画面方法,如多步 Adams 和 BDF。由于我们拥有的基准,我们推荐手动调整的版本,但它的步进行为在数学上与您循环遍历常量数组相同(没有常量和插值的专业化)。

另外,我们的测试表明,并非每一个画面都值得。有些只是效率不高。随着时间的推移,人们在选择减少主要截断误差项同时保持稳定区域大小相同的系数方面变得更好。然后,较旧的方法会采取类似的步骤,但会导致解决方案出现更多错误。我们将它们放在那里用于研究目的,而且它也是一个很好的文献档案,因为其中一些很难找到。

Runge-Kutta 方法可以说是用于初始值 ODE(也包括 PDE 半离散化)的最广泛使用的方法。有一些特定类型的 Runge-Kutta 方法几乎适用于每一类初始值问题。它们当然不仅仅是历史文物。

DifferentialEquations.jl 对当前求解器进行了最好的调查。它遍历每个选项并对其进行基准测试。现代 RK 画面在大多数非僵硬情况下都是最先进的。多步方法适用于昂贵的非刚性函数。对于僵硬的问题,它会有所不同。看:

http://diffeq.sciml.ai/latest/solvers/ode_solve.html

http://devdocs.juliadiffeq.org/latest/internals/notes_on_algorithms.html

这两个文档有时会相互矛盾,例如在 7 和 8 顺序推荐不同的算法,因此您必须向 Chris Rackauckas 询问(原因请参阅下面 Chris 的评论)。在第二个链接上,有一个隐含的理解,即高阶方法在所需的公差缩小时很有用,但在更宽松的公差下也会出现速度缺陷。

您还需要了解步长控制,因为许多最好的算法都依赖于它,并将其作为一个单独的问题。DiffEq 有这个简短的描述,但我认为原始论文更容易理解