当函数几乎 "flat" 时，Newton–Raphson 方法是不可能的

Question

我正在尝试计算 x^x 的值。
我计算了它的导数，我是
使用 Newton–Raphson 方法求 f(x)=x^x-a 对于给定 a.

的根

这是我用来计算下一个近似值的函数：

double xkp1(double xk, double a){
    double lnxp1 = log(xk) +1;
    return xk -( (fx(xk, a))  /  (exp(xk*log(xk)) * (log(xk) + 1)  ));
}

函数 fx 是这样定义的：

double fx(double x, double a){
    return exp(x*log(x))-a;
}

现在，只有当 xk 的起始值已经接近根时，这种方法才能正常工作。
如果它相差 +-0.5，xk 就会爆炸到一个非常高的值并且 f(x) 变为无穷大。
现在我认为这里可能有什么问题 - x^x 的导数与 x^x 的实际值相比非常小，所以整个 (fx(xk, a)) / (exp(xk*log(xk)) * (log(xk) + 1) ) 刚好变成 +infinity - 切线超过根。
这意味着我需要更高的双精度，但这有可能吗？如果不是，是否可以修改方法使其适用于这种情况？

Answer 1

我假设您只对正 x 值感兴趣，对负整数（也有实数值）不感兴趣。

我有两个解决方案可以帮助您解决问题。首先，如果您首先使用对数变换，数值方案可能会更稳定。你的等式就是找到 a 使得 x log(x) = log(a)。 x log(x)的导数是log(x) + 1，可能比你的指数函数更稳定

否则，您可以使用您的知识，因为 f(x) = x^x 在 x>1/e 上单调递增到运行平分搜索。从 x_l = 1/e 和 x_r = 2/e 开始。如果f(x_l) > a，则无解。然后在 f(x_r) < a 时，将 x_l = x_r 和 x_r = c * x_r 设置为 c > 0（或任何其他增加 x_r 的方案）。一旦有了 f(x_l) < a < f(x_r) 之后的一对 x_l, x_r，您就可以开始平分搜索以找到包含 f(x) = a 的解的小区间。一旦这个间隔足够小，您就可以从牛顿法的迭代开始。

你甚至可以结合以上两种方法，进行二等分搜索来求解x log(x) = log(a)。

当函数几乎 "flat" 时，Newton–Raphson 方法是不可能的

Newton–Raphson method impossible when a fuction is almost "flat"

c++

math

double

numeric