每日一问之初识牛顿迭代法（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

P.S：文中有错欢迎指出，互相学习。以及欢迎关注我的公众号 ????

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

什么是牛顿法

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

参考

相关推荐