牛顿迭代法与一道经典编程有关问题

牛顿迭代法与一道经典编程问题

牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

既然牛顿迭代法可以用来求解方程的根，那么不妨以方程

x2=n $x^2=n$ 为例，来试着求解它的根。为此。令

f(x)=x2−n $f(x) = x^2 - n$ ，也就是相当于求解

f(x)=0 $f(x) = 0$ 的解，如上图所示。

首先随便找一个初始值

x0 $x_0$ ，如果

x0 $x_0$ 不是解，做一个经过

(x0,f(x0)) $( x_0,f( x_0))$ 这个点的切线，与

x $x$ 轴的交点为

x1 $x_1$ 。同样的道理，如果

x1 $x_1$ 不是解，做一个经过

(x1,f(x1)) $( x_1,f( x_1))$ 这个点的切线，与

x $x$ 轴的交点为

x2 $x_2$ 。以此类推。以这样的方式得到的

xi $x_i$ 会无限趋近于

f(x)=0 $f(x) = 0$ 的解。

判断

xi $x_i$ 是否是

f(x)=0 $f(x) = 0$ 的解有两种方法：一是直接计算

f(xi) $f(x_i)$ 的值判断是否为

0 $0$ ，二是判断前后两个解

xi $x_i$ 和

xi−1 $x_{i-1}$ 是否无限接近。

经过

(xi,f(xi)) $(x_i, f(x_i))$ 这个点的切线方程为

f (x) = f (x i) + f' (x i) (x - x i)

$f(x) = f(x_i) + f'(x_i)(x - x_i)$ 其中，

f′(x) $f'(x)$ 为

f(x) $f(x)$ 的导数，本题中为

2x $2x$ 。令切线方程等于

0 $0$ ，即可求出

x i + 1 = x i - f ( x i ) f ' ( x i )

$x_{i+1}=x_i - \frac{f(x_i)}{f'(x_i)}$

继续化简

x i + 1 = x i - x 2 i - n 2 x i = x i - x i 2 + n 2 x i = x i 2 + n 2 x i

$x_{i+1}=x_i -\frac{x_i^2 - n}{2x_i} = x_i - \frac{x_i}{2} + \frac{n}{2x_i} = \frac{x_i}{2} + \frac{n}{2x_i}$

基于上述迭代公式，我们其实给出了一个求平方根的算法。事实上，这也的确是很多语言中内置的开平方函数的实现方法。

Leetcode上也有一道经典面试题目涉及到开平方函数的实现，如下

牛顿迭代法与一道经典编程有关问题

基于我们已经给出的牛顿迭代法，下面就可来编程解决该问题了，示例代码如下

class Solution {
public:
    int mySqrt(int x) {
        if (x ==0)  
        return 0;  
        double pre;  
        double cur = 1;  
        do  
        {  
        pre = cur;  
        cur = x / (2 * pre) + pre / 2.0;  
        } while (abs(cur - pre) > 0.00001);  
        return int(cur);  
    }
};

牛顿迭代法与一道经典编程有关问题

相关推荐