2

我有一个程序应该使用牛顿法找到第 ** 次埃尔米特多项式的根，但运行该程序需要很长时间。我对 C 很陌生，所以我不知道我的错误在哪里，或者这是否只是暴力破解这个问题的本质。我也遇到了获取准确根的问题，但到目前为止，很难找到那个错误，因为我只能每 5-10 分钟运行一次测试用例

代码已删除

4

1 回答 1

1

我 100% 确定 Newton-Raphson 没有充分的理由花这么多时间。在某些情况下，它可能会出现问题，因为这种方法不能保证收敛。但在您的具体情况下 - 应该没有问题。

一件很清楚的事情是你过度使用递归。仅用 n=37计算你hermite的递归是一个复杂的递归，它有点像 37 个斐波那契数的总和，大约是40 百万。

现在，认为您的newton方法应该重复调用hermite以及h_deriv（具有相同数量级的递归），直到 in 收敛到10^-12. 听起来像几十次互动。

而且，这还不够，您还可以newton 递归地实现！世界上真的没有理由这样做。（lisp/scheme 是你的第一门编程语言吗？）

这是您应该做的以提高性能：

  1. 修复你的hermite. 您应该计算 37 个系数，这可以递归完成。一旦完成 - 您应该使用它们在正常时间内计算多项式的值。

  2. 导数也一样。只需计算 36 个系数。

  3. 可选择修复您的newton. 据我所知 - 你不会获得太多的性能：你的“递归”是一个尴尬的循环。但是它看起来会更好，并且消耗更少的堆栈。

编辑：

阅读评论后，我花时间尝试构建和运行它。而且，我必须承认，我低估了问题的复杂性。

事实证明，由递归关系计算的系数增长迅速，并且舍入误差似乎占主导地位。因此，通过蛮力解决这个问题具有不可避免的影响，并且使用预先计算的系数（并将它们按直接顺序求和）产生相同的结果并不明显。

尽管如此，还是有一种方法可以在不改变计算逻辑的情况下摆脱荒谬的递归：

const int N = 37;

double g_pHermiteValues[N+1];

void CalcHermiteAt(double x)
{
    double x2 = x*2;

    g_pHermiteValues[0] = 1.;
    g_pHermiteValues[1] = x2;

    for (int n = 2; n <= N; n++)
        g_pHermiteValues[n] =
            g_pHermiteValues[n - 1] * x2 - 
            g_pHermiteValues[n - 2] * 2*(n - 1);
}

double CalcHermiteDerivAt()
{
    return g_pHermiteValues[N - 1] * 2*N;
}

double newton(double x_0)
{
    const double tolerance = 1E-12;

    while (true)
    {
        CalcHermiteAt(x_0);

        if (abs(g_pHermiteValues[N]) < tolerance)
            return x_0;

        x_0 -= g_pHermiteValues[N] / CalcHermiteDerivAt();
    }
}

也就是说，我们使用相同的递归关系。只是为了计算 Hermite 多项式在给定点的值，我们对直到 n=37 的所有多项式进行迭代计算，并将结果存储在全局数组中。然后它的顶部元素保存所需的结果，并且导数也从末尾的第二个数组元素推导出来。

因为在 Newton-Raphson 算法的每一步中，我们都需要在同一点上的值和导数——这是有效的。

PS但是到目前为止，我无法找到解决方案。Newton-Raphson 对于我试图开始的点并没有收敛。

我相信对于这样的问题，可以使用更稳健的方法，例如中值搜索。

于 2012-04-22T17:10:36.067 回答