每日一问之初识牛顿迭代法（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 个视频，想了解更多的可以查看视频。

假设我们有一个连续的函数

f(x)

，其在

x

轴上存在很多根（零点）。现在在

x

轴上取一初始点

x_1

，该点对应的函数值为

f(x_1)

。然后在该点的函数值附近画切线，切线与

x

轴的交点为

x_2

。假设

x_2 = x_1 - △x

，在由切线，x 轴及函数值

f(x_1)

形成的三角形中，可以求得斜率

slope =\frac{f(x_1)}{△x}

，化解可得

△x = \frac{f(x_1)}{slope}

。slope 即为函数在

x_1

处的导数，所以有

△x = \frac{f(x_1)}{f'(x_1)}

，最后代入得

x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}

。后面在

x_2

对应的函数值处取切线，然后开始新一轮的迭代。之后再循环这个过程，直到达到足够准确的值，这就是牛顿法求根的过程。过程中迭代的公式可以写成：

x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)}

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

根据上面的基本介绍，牛顿法是用于求解一个实数函数的根的近似值的方法。然而开方问题可以看成是对方程

x^2 - n =0

求根的问题，所以就可以用牛顿法来求解：首先可以得知

f(x) = x^2 - n ，f'(x) = 2x

，所以迭代公式为

x_{n+1}=x_{n} - \frac{ x_{n}^2 - n}{2x_{n}} = \frac{x_n + \frac{n}{x_n}}{2}。

依据该迭代公式，对应 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