c - 尝试为 hermite 多项式暴力求根

Question

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

代码已删除

Answer 1

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

有一点很清楚，您非常过度使用了递归。只是用 n=37 计算你的 hermite 是一个复杂的递归，有点像求和 37 个斐波那契数，大约是 4000 万。

现在，认为您的 newton 方法应该重复调用 hermite，以及 h_deriv(具有相同的数量级递归)，直到收敛到 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 算法中的每一步我们都需要同一点的值和导数 - 这可以有效地完成。

附言但是到目前为止，我无法找到解决方案。 Newton-Raphson 只是不收敛于我尝试开始的点。

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