牛顿迭代法求解x 的平方根
牛顿迭代法是一种可以用来快速求解函数零点的方法。
为了叙述方便，我们用 C C C表示待求出平方根的那个整数。显然， C C C的平方根就是函数
f
(
x
)
=
x
c
−
C
f(x)=x^c-C
f(x)=xc−C
的零点。
牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个 x 0 x_0 x0作为初始值，在每一步的迭代中，我们找到函数图像上的点 ( x i , f ( x i ) ) (x_i,f(x_i)) (xi,f(xi)) ，过该点作一条斜率为该点导数 f ′ ( x i ) f'(x_i) f′(xi)的直线，与横轴的交点记为 x i + 1 x_{i+1} xi+1 。 x i + 1 x_{i+1} xi+1 相较于 x i x_{i} xi 而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。下图给出了从 x 0 x_{0} x0 开始迭代两次，得到 x 1 x_{1} x1和 x 1 x_{1} x1的过程。
#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