计算科学 - 使用 ODE 求解器求解非线性方程组比使用牛顿法更快？ - 吾爱随笔录

计算科学数值分析颂非线性方程牛顿法

2021-11-30 23:21:52

这在某种程度上是出乎意料的，但我最近求解非线性方程组的经验是，将它们视为常方程组的右手边，然后使用 ODE 求解器对系统进行演化可能比使用通常的牛顿法快得多-拉夫森迭代。

当然，这只适用于某些特定类型的非线性方程。我正在处理的方程式来自化学平衡问题。化学演化方程看起来像

\frac{d}{d t} x_{i} = f_{i} (x) = - k_{1} x_{i} - k_{2} x_{i} x_{j} - k_{3} x_{i} x_{k} - \dots + k_{4} x_{j} + k_{5} x_{k} x_{h} + \dots,

$\frac{d}{dt}x_i = f_i(\mathbf{x}) = -k_1x_i-k_2x_ix_j -k_3x_ix_k -\cdots + k_4x_j + k_5x_kx_h + \cdots,$

\dots

$\cdots$ 在哪里

k_{i}

$k_i$ s 都是常数。

目标是解方程

f_{i} (x) = 0, for i = 1, \dots, n .

$f_i(\mathbf{x}) = 0,\ \text{for }i=1,\ldots,n.$ 我所说的方法是从最初的猜测开始

x_{0}

$x_0$ ，并让它进化直到

f_{i}

$f_i$ s 非常接近

0

$0$ ; 基于物理直觉保证存在平衡解决方案（尽管不一定是唯一的）。

我不明白的是，ODE 求解器还内置了 Newton-Raphson 迭代，这是隐式方案（我正在使用的方案）中需要的；ODE 方法如何更快？

编辑：非线性方程有一个平凡的解决方案 $\mathbf{x}=0$ ，但这很少是我们想要的。我的理解是，不能保证牛顿迭代将从初始估计开始收敛到“物理”解决方案 $\mathbf{x}_0$ ，而 ODE 方法似乎具有此属性。

更新：我用守恒方程替换了一个非线性方程，现在牛顿法运行得更快（相似大约比 ODE 方法快 4 倍），并且很可能不这样做会产生错误的结果，因为非线性方程组不是完全独立的（这让牛顿求解器抱怨）。

1个回答

这在某种程度上是出乎意料的，但我最近求解非线性方程组的经验是，将它们视为常方程组的右手边，然后使用 ODE 求解器对系统进行演化可能比使用通常的牛顿法快得多-拉夫森迭代。

听起来您正在做某种伪瞬态延续（PtC）。（请参阅是否众所周知，某些优化问题等同于时间步长？）

我不明白的是，ODE 求解器还内置了 Newton-Raphson 迭代，这是隐式方案（我正在使用的方案）中需要的；ODE 方法如何更快？

可能是 PtC 方法所经历的初始猜测序列比用于求解您希望求解的代数方程的 Newton-Raphson 方法需要更少的迭代。举一个您看到的迭代历史的例子会很有帮助。

我的理解是，不能保证牛顿迭代将从初始估计 x0 开始收敛到“物理”解，而 ODE 方法似乎具有此属性。

是的，不能保证牛顿迭代会收敛到“物理”解决方案。如果 ODE 方法收敛，它应该收敛到动态系统的稳定平衡点，在您的情况下，这就是您正在谈论的物理解决方案。

我用守恒方程替换了其中一个非线性方程，现在牛顿方法运行得更快（类似于 ODE 方法），不这样做很可能会产生错误的结果，因为非线性方程组不是完全独立（这让牛顿求解器抱怨）。

如果雅可比矩阵是秩不足的，则线性求解可能会或可能不会返回解。例如，Krylov 子空间求解器通常会计算 Drazin 逆，这会产生最小二乘解。由于零枢轴或类似情况，高斯消除可能会引发错误；也可以使用 QR 或 SVD 计算最小二乘解。

PtC 方法中时间步长的雅可比矩阵通常是满秩的；它们将具有以下形式 $(I - \Delta{t}J)$ ，在哪里 $J$ 是左侧的雅可比行列式 $f(x) = 0$ . 秩不足可能是您使用的原始 Newton-Raphson 方法的收敛性不太好的另一个原因。

守恒方程将产生一个 DAE，如果您愿意，您也可以在 PtC 方法中使用它。参见Coffey、Kelley 和 Keyes (2003)，将 PtC 用于 DAE 与 ODE 公式的比较分析。

其它你可能感兴趣的问题