什么是牛顿迭代法?
今天在刷 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