c++ - Newton-Raphson 在 C++ 中使用递归

Question

我已经编写了以下代码来使用牛顿法计算平方根，但每次运行它都会溢出。我试过自己检查，但没有发现任何错误。你们能帮帮我吗？

double root(double n,double init){
    if(fabs(init*init-n)<=0.00001){
        return init;
    }else{
        init=(init*init-n)/2*init;
        return root(n,init);
   }
}
int main()
{
    double a;
    cout<<"Enter any number to get its square root: ";
    cin>>a;
    cout<<"Square Root of "<<a<<" is: "<<root(a,2);
    return 0;
}

Answer 1

所以你的问题有两个方面。首先，您的牛顿法略有偏差(这是一个更大的问题)。其次，您实现它的方式会导致溢出。

问题 1(更大的问题):

其他答案似乎忽略了这一点，即使这是更大的问题。计算机可以处理小数平方的溢出，例如计算 9 的平方根时，但您的方法甚至对它们不起作用。这是因为，正如我在评论中提到的，您的牛顿法略有偏差。

您应该在此行中使用加号而不是减号(尝试重新推导以查看原因):

init=(init*init+n)/(2*init);

推导:

x_{k+1} = x_k - f(x_k)/f'(x_k)
        = x_k - ((x_k)^2 - n)/(2x_k)
        = x_k - 1/2*x_k + n/(2x_k)  // note the + here
        = 0.5*x_k + 0.5*n/x_k
        = 0.5*(x_k + n/x_k)

x_k 是您的 init 变量。

问题 2:

执行init*init 会导致数字增长过快而溢出(数字越大错误越大)。您可以用代数方式将其重写为:

init=0.5*(init + n/init);

综合起来:

#include <iostream>
#include <cmath>
using namespace std;
double root(double n,double init){
    if(fabs(init*init-n)<=0.00001){
        return init;
    }else{
        init=0.5*(init + n/init);
        return root(n,init);
   }
}
int main()
{
    double a;
    cout<<"Enter any number to get its square root: ";
    cin>>a;
    cout<<"Square Root of "<<a<<" is: "<<root(a,2);
    return 0;
}