如何数值求解 ODEñN可证明正确的数字?

计算科学 数值分析 精确
2021-12-22 10:10:46

假设我们有一个形式为 其中是准确已知的(即无限精度),我们可以有效地计算到任何精度。也就是说,我们有一个黑盒子,给定一个向量和一个整数,返回一个保证的近似值是正确的到中的时间多项式中的位数。我想知道是否有任何实用的方法来获得近似值

dxdt=f(x)x(0)=x0
x0Rnf:RnRnxRnMf(x)MMx(tf)(其中是某个给定的最终时间),可证明对个数字是正确的。tfRN

显然,这对于任何函数都是不可能的,因为可能有一些疯狂的行为,它会彻底改变真正的解决方案,但不会在任何合理数量的评估。因此,我也有兴趣知道在上需要什么样的良好行为条件(例如,所有偏导数都存在且有界,小的 Lipschitz 常数等)才能做到这一点。f:RnRnff

2个回答

我想知道是否有任何实用的方法来获得的近似值(其中是某个给定的最终时间),这可证明对 [原文如此] 数字是正确的.x(tf)tfRN

这一切都取决于您对区间算术实用性的看法。有可用的经过验证的集成器,例如 Martin Berz 小组的COZY代码。您可能想查看 Neumaier、Nedialkov、Berz & Makino、Chachuat、Stadtherr 以及其他一些团体的论文。他们的论文倾向于使用“泰勒模型”、“验证积分器”和“区间算术”等短语。

显然,这对于任何函数都是不可能的,因为可能有一些疯狂的行为,会极大地改变真正的解决方案,但不是t 在任何合理数量的评估中都得到了认可。因此,我也有兴趣知道在上需要什么样的良好行为条件(例如,所有偏导数都存在且有界,小的 Lipschitz 常数等)才能做到这一点。f:RnRnff

标准证明(例如,我在想 Dahlquist 的证明)通常使用 Gronwall 类型的不等式作为误差界限,所以理论上,您应该只需要在的域上的有界 Lipschitz 常数你关心的,这说明了 WolfgangBangerth 正在谈论的一些内容,尽管我不知道像 Hairer 和 Wanner 这样的研究生水平的教科书会专门讨论你可以评估准确性; 海厄姆关于数值方法的准确性和稳定性的书可能会讨论这一点。Rnf(x)

在实践中,对于我上面提到的泰勒模型方法,您通常需要结合理论和实践条件。理论部分很简单:如果你想要一个阶泰勒模型,你需要一个中的函数。涉及实用性问题的实施部分更难。kCk

从用户的角度来看,这些集成商归结为两件事:

  • 我有评估的源代码吗?(一个目标文件是不够的。)f
  • 我可以扩充此源代码以与自动微分库以及区间算术库兼容吗?

假设函数可以被解析或运算符重载(取决于所使用的自动微分技术),并假设您可以生成一个函数来计算及其前个导数的区间扩展,那么您可以实现一个经过验证的积分方法阶泰勒模型。fkk

至于典型的 ODE 求解方法,评论 Wolfgang 的回答:

我不认为您可以获得错误低于某个数字的证书,但您会发现估计值低于您的容忍度。

任何具有嵌入式误差估计器的方法都具有 Wolfgang 所引用的信息。通常,这意味着积分方法确实计算了两个(或更多的解决方案;例如,DOP853 计算了 3 个解决方案)的解决方案,并通过一些范数对它们进行比较。假设是更高阶的解决方案更准确,这实际上可能不是真的,这取决于给定的问题、时间步长、初始条件等。实现返回的解决方案可以是计算出的任何候选解决方案。以常见的 Runge-Kutta 4(5) 案例为例,可以返回 4 阶解或 5 阶解;典型的方法使用 Dormand-Prince 公式,它使 5 阶解中的误差最小化,并返回它,而不是 4 阶解,因为五阶解更有可能更准确。除了看稳定性问题,我认为你应该看看错误控制(Hairer 和 Wanner 的第 II.4 节);稳定性是必要的,但不足以保证准确性。

相反,经过验证的积分器将计算包含真实解的区间。如果这个区间的上下界一致M数字,那么那些是第一个M真正解决方案中的数字,这是准确性的证明,听起来像你想要的。

您的第一个问题实际上是您可以从大多数罐装 ODE 积分器那里得到的东西,因为它们都以一种或另一种方式跟踪错误的估计。我不认为您可以获得错误低于某个数字的证书,但您会发现估计值低于您的容忍度。

您的第二个问题更难回答:您可以评估的准确性之间的关系是什么f(x)以及这如何影响您的解决方案的准确性(假设您可以精确地集成 ODE)。这两个精度之比就是您的 ODE 的稳定常数。这将取决于诸如规范之类的事情f, 的范数f,以及您积分的时间段的长度(它通常会以指数方式取决于此间隔长度)。大多数关于数值 ODE 的教科书都会有关于稳定性的部分。