何为牛顿迭代法
牛顿迭代法的全名叫做牛顿-拉夫森方法(Newton-Raphson method),这是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(y)=0的根。
对于一般的形如f(x)=0的方程,首先任意估算一个解$x1,一般来说此时不能得到方程的正确解,则我们在方程曲线上x=x_1处作f(x)的切线,与x轴相交于点(x_2,0),此时x_2要更加接近于方程f(x)=0的解了。只要以此方式不断地更新x{n+1}$,就能无限接近于方程的精确解。
值得注意的是,该方法在函数不连续或者函数有多个零点的时候会失效。
代码实现
牛顿迭代法多用于以最快速度求一个数字m的方根,仅需几次的迭代就能够得到非常精确的结果,下面举例来介绍牛顿迭代法求平方根的数学公式和实现。
不妨令xm=n,则方程为f(x)=xm−n.
有
f′(x)=mxm−1 假设我们输入一个数字n,我们现在需要求它的平方根x,则
f(x)=x2−n 则我们的迭代方程就是xn+1=xn2+n2xn。
现在要确定的是迭代终止条件,假设我们要求的精度是0.00001,则迭代终止的条件为|x2−n|<0.00001。
由于x=0的时候,n的值就为0,所以我们将迭代的起点设置为x=1,所以我们的程序如下:
1 | #Python3 |
当我们输入的值为2147395599时,输出46339.99998,输出耗时为32ms。而Python自带的n**0.5
耗时60ms。
非典型算法
这里不得不提到神秘数字0x5f3759df,这个数字首次出现在游戏《雷神之锤III》的源代码中。
在一个名为q_math.c
的文件里出现了如下代码
1 | //C |
里面出现了一句让人抓毛的代码:
1 | i = 0x5f3759df - ( i >> 1 ); // what the fuck? |
这句代码和下面的两行一起
1 | i = 0x5f3759df - ( i >> 1 ); // what the fuck? |
就相当于求平方根的操作。
但其中的原理是什么,答案恐怕连写这个代码的人自己也不知道。(what the f*ck?)
参考
【1】维基百科:牛顿法
【2】力扣题目:求平方根