每日一问之初识牛顿迭代法（Newton's method）

什么是牛顿迭代法？

今天在刷 LeetCode 的 sqrt(x) 这道题的时候，看到别人的解法中有使用牛顿迭代法。之前也看到这个方法很多次，但都没有去了解。今天正好就这个问题来稍微整理一下：

• 什么是牛顿法？
• 为什么可以用它来求解开方问题？

什么是牛顿法

在维基百科中的定义如下：

In numerical analysis, Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. It is one example of a root-finding algorithm.

牛顿法是一种用于找到实数函数的根的近似值的方法，是求根算法中的一个代表。下面以一个例子来具体说明用牛顿法求根的过程。

一个变量中的 Newton-Raphson 方法实现如下，主要的想法来自这个视频，这个教授讲解的挺明白的，一共有 7 个视频，想了解更多的可以查看视频。

假设我们有一个连续的函数，其在 轴上存在很多根（零点）。现在在 轴上取一初始点 ，该点对应的函数值为 。然后在该点的函数值附近画切线，切线与 轴的交点为 。假设 ，在由切线，x 轴及函数值 形成的三角形中，可以求得斜率 ，化解可得 。slope 即为函数在 处的导数，所以有 ，最后代入得 。后面在 对应的函数值处取切线，然后开始新一轮的迭代。之后再循环这个过程，直到达到足够准确的值，这就是牛顿法求根的过程。过程中迭代的公式可以写成：

为什么可以用它来求解开方问题？

根据上面的基本介绍，牛顿法是用于求解一个实数函数的根的近似值的方法。然而开方问题可以看成是对方程 求根的问题，所以就可以用牛顿法来求解：首先可以得知 ，所以迭代公式为

依据该迭代公式，对应 LeetCode 的 sqrt(x) 这道题写成 Python 代码就会很简洁，比二分法要简洁多了，且运行时间也快一些。

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """       
        
        """
        # 采用二分法
        low, high = 0, x
        while(low <= high):
            mid = int((low + high) / 2)
            if mid*mid > x :
                high = mid - 1
            elif mid*mid < x:
                low = mid + 1
            else:
                return mid

        
        return low - 1
        """
        # 采用牛顿迭代法
        r = x
        while r*r > x:
            r = int((r + x/r) / 2)
        
        return r 

参考

[1]. Newton's method - wikipedia
[2]. Calculus: Newton's Method (1 of 7) Basics Continued: Roots of Functions

*P.S：文中有错欢迎指出，互相学习。