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

令f(x)=x2?n<script id="MathJax-Element-198" type="math/tex"> f(x) = x^2 - n </script>， 也就是相当于求解 f(x)=0<script id="MathJax-Element-199" type="math/tex">f(x) = 0</script> 的解。如上图所看到的。


       首先随便找一个初始值 x0<script id="MathJax-Element-200" type="math/tex"> x_0</script>，假设 x0<script id="MathJax-Element-201" type="math/tex"> x_0</script>不是解，做一个经过 (x0,f(x0))<script id="MathJax-Element-202" type="math/tex">( x_0,f( x_0))</script> 这个点的切线，与x<script id="MathJax-Element-203" type="math/tex">x</script>轴的交点为x1<script id="MathJax-Element-204" type="math/tex">x_1</script>。相同的道理。假设 x1<script id="MathJax-Element-205" type="math/tex">x_1</script>不是解，做一个经过(x1,f(x1))<script id="MathJax-Element-206" type="math/tex">( x_1,f( x_1))</script>这个点的切线，与x<script id="MathJax-Element-207" type="math/tex">x</script>轴的交点为x2<script id="MathJax-Element-208" type="math/tex">x_2</script>。

以此类推。以这种方式得到的xi<script id="MathJax-Element-209" type="math/tex">x_i</script>会无限趋近于 f(x)=0<script id="MathJax-Element-210" type="math/tex">f(x) = 0</script> 的解。


推断xi<script id="MathJax-Element-211" type="math/tex">x_i</script>是否是f(x)=0<script id="MathJax-Element-212" type="math/tex">f(x) = 0</script>的解有两种方法： 一是直接计算f(xi)<script id="MathJax-Element-213" type="math/tex">f(x_i) </script>的值推断是否为0<script id="MathJax-Element-214" type="math/tex">0</script>，二是推断前后两个解xi<script id="MathJax-Element-215" type="math/tex">x_i</script>和xi?1<script id="MathJax-Element-216" type="math/tex">x_{i-1}</script>是否无限接近。


经过(xi,f(xi))<script id="MathJax-Element-217" type="math/tex">(x_i, f(x_i))</script>这个点的切线方程为

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);  
    }
};