牛顿迭代法求解x 的平方根

牛顿迭代法是一种可以用来快速求解函数零点的方法。

为了叙述方便，我们用$C$表示待求出平方根的那个整数。显然，$C$的平方根就是函数

$$f(x)=x^c-C$$
的零点。

牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个$x_0$作为初始值，在每一步的迭代中，我们找到函数图像上的点 $(x_i,f(x_i))$ ，过该点作一条斜率为该点导数$f^{\prime }(x_i)$的直线，与横轴的交点记为$x_{i+1}$ 。$x_{i+1}$ 相较于$x_i$ 而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。下图给出了从$x_0$ 开始迭代两次，得到$x_1$和$x_1$的过程。

#include <iostream>
#include <math.h>
int main(int argc, char *argv[]) {
  const int C = 5;
  const double y_eps = 1e-10;
  const double x_eps = 1e-8;
  double x_n = double(C);             // last iteration value x(n)
  double x_n_1 = (x_n + C / x_n) / 2; // iteration value x(n+1)
  int iter_num = 1e5;                 // a protect value
  while (std::abs(x_n * x_n - C) > y_eps && (std::abs(x_n_1 - x_n) > x_eps) &&
         (iter_num--)) {
    x_n = x_n_1;
    x_n_1 = (x_n + C / x_n) / 2;
    std::cout<<C<<"的平方根为："<<x_n_1<<std::endl;
  }
  std::cout<<C<<"的平方根最终迭代计算结果为："<<x_n_1<<std::endl;
  std::cout<<C<<"的平方根库函数计算结果为："<<std::sqrt(C)<<std::endl;
  return 0;
}

计算log：

5的平方根为：2.33333
5的平方根为：2.2381
5的平方根为：2.23607
5的平方根为：2.23607
5的平方根为：2.23607
5的平方根最终迭代计算结果为：2.23607
5的平方根库函数计算结果为：2.23607

参考
youtube
leetcode