理解牛顿迭代法求开方

  牛顿迭代法(Newton’s method)又称为牛顿-拉弗森方法(Newton-Raphson method),它是牛顿在 17 世纪提出的一种在实数域和复数域上近似求解方程的方法。这个概念比较抽象,我们只看看在算法中的实际应用,牛顿迭代法是求方程根的重要方法之一,比如给定一个 x,求 $\sqrt{x}$。

  牛顿迭代法常用于两个方面,我们主要看牛顿迭代法在方程求根中的应用:

  1. 方程求根,五次及以上多项式方程没有根式解(就是没有像二次方程那样的万能公式),没有根式解不意味着方程解不出来,数学家也提供了很多方法,牛顿迭代法就是其中一种。
  2. 最优化问题,最优化其实就是搜索函数 f(x) 的最小值或最大值问题。

牛顿迭代法求根过程

  求开方的问题可以转化成函数求解的问题,比如求 $\sqrt{4}$ ,其实就是求 $x^2 - 4 = 0$ 的解,求 4 的平方根就转化为求函数 $f(x) = x^2 - 4$ 与 $x$ 轴的交点,如下图:
sqrt4

  $\sqrt{4}$ 的解显而易见,我们知道 $\sqrt{4} = \pm2$,但如果是求 $\sqrt{5}$ 呢?用计算器可以算出 $\sqrt{5} \approx \pm2.236067…$,那我们来看下牛顿迭代法的过程,首先求 $\sqrt{5}$ 的问题可以转化为如下:
已知:

  1. 函数 $f(x) = x^2 - 5$ ;
  2. $f\prime(x) = 2x$ ;
  3. 牛顿迭代法公式是 $x_{n+1} = x_n - \frac{f(x_n)}{f\prime(x_n)}$ 。

求:

$x_{n+1}$,这个值是无限逼近 $2.236067…$ 的,我们这里只求几次看看效果。

过程:

  1. 先取一个 $x_1$ = 5 ;
  2. 带入公式可得 $x_2 = x_1 - \frac{f(x_1)}{f\prime(x_1)} = 5 - \frac{5^2 - 5}{2\times5} = 5 - \frac{20}{10} = 5 - 2 = 3$
  3. 带入公式可得 $x_3 = x_2 - \frac{f(x_2)}{f\prime(x_2)} = 3 - \frac{3^2 - 5}{2\times3} = 3 - \frac{4}{6} = 3- \frac{2}{3} = \frac{7}{3}$
  4. 带入公式可得 $x_4 = x_3 - \frac{f(x_3)}{f\prime(x_3)} = \frac{7}{3} - \frac{(\frac{7}{3})^2 - 5}{2\times\frac{7}{3}} = \frac{7}{3} - \frac{2}{21} \approx 2.23809$

  计算三次误差已经在 $0.002$ 级别,其实我们可以估算其值的范围是大于 2 小于 3 ,直接用 $x_1$ = 2 开始,逼近速率更快:

  1. 先取一个 $x_1$ = 2 ;
  2. 带入公式可得 $x_2 = x_1 - \frac{f(x_1)}{f\prime(x_1)} = 2 - \frac{2^2 - 5}{2\times2} = \frac{9}{4} = 2.25$ ;
  3. 带入公式可得 $x_3 = x_2 - \frac{f(x_2)}{f\prime(x_2)} = 2.25 - \frac{2.25^2 - 5}{2\times2.25} = \frac{9}{4} = 2.236111$ 。

  计算两次误差已经在 $0.0001$ 级别,牛顿迭代法求开方其实就是无限逼近真实值的过程,至于什么时候结束就看具体精度要求了。

  接下来通过图形更直观的感受一下。如下 f(x) 是一个曲线函数,我们要求 f(x) 与 $x$ 轴的交点 $x_0$,$x_1$、$x_2$、$x_3$、$x_4$、$x_5$ 就是逐渐逼近 $x_0$ 的过程,通过牛顿法多次迭代后获取的 $x_5$ 已经非常接近 $x_0$ :
NewtonIteration_Ani0

一步一步来看:
  先随机取一个点 $x_1$,求函数 $f(x)$ 上点 $(x_1, f(x_1))$ 处的切线与 $x$ 轴交点,得到 $x_2$,具体怎么算出来的我们稍后看:
NewtonIteration_Ani1

  再求函数 $f(x)$ 上点 $(x_2, f(x_2))$ 处的切线与 $x$ 轴交点,得到 $x_3$:
NewtonIteration_Ani2

  再求函数 $f(x)$ 上点 $(x_3, f(x_3))$ 处的切线与 $x$ 轴交点,得到 $x_4$:
NewtonIteration_Ani3

  再求函数 $f(x)$ 上点 $(x_4, f(x_4))$ 处的切线与 $x$ 轴交点,得到 $x_5$:
NewtonIteration_Ani4

  整个过程的核心就是牛顿迭代法公式: $x_{n+1} = x_n - \frac{f(x_n)}{f\prime(x_n)}$ 。

牛顿-拉弗森方法的推导

线性近似

  先了解下线性近似的概念,所谓线性近似主要作用是把一个复杂的非线性函数用一个简单的线性函数来表示。假设一个曲线函数 $f(x)$ 上存在点 $(A, f(A))$,当 $x$ 接近 $A$ 时,可以使用函数在 $A$ 点的切线作为函数的近似线,切线是一条直线,可以用 $y = kx + b$ 表示。也就是说在某一点处切线是曲线的线性逼近,可以说在 $A$ 点附近,$y = kx + b \approx f(x)$。

牛顿-拉弗森方法的几何直觉

  牛顿-拉弗森方法提出来的思路就是利用切线是曲线的线性逼近这个思想。牛顿、拉弗森们想啊,切线多简单啊,研究起来多容易啊,既然切线可以近似于曲线,我直接研究切线的根不就成了,于是对曲线 $f(x)$ 的研究转换成了对切线 $y = kx + b$ 的研究。

  然后他们观察到一个事实,随便找一个曲线上的 $A$ 点(为什么随便找,根据切线是切点附近的曲线的近似,应该在根点附近找,但是很显然我们现在还不知道根点在哪里),以 $A$ 为切点做一个切线,切线的根 $x_1$ (就是和 $x$ 轴的交点)与曲线的根 $x_0$ 还有一定的距离。
  牛顿、拉弗森们想,没关系,我们从这个切线的根出发,做一根垂线,和曲线 $f(x)$ 相交于 $B$ 点,再以 $B$ 为切点做切线,发现 $B$ 点切线的根 $x_2$ 比之前 $x_1$ 更接近 $x_0$ 。
  牛顿、拉弗森们很兴奋,继续重复刚才的工作,最后发现经过多次迭代后切线的根会越来越接近曲线的根(哪怕经过无数次迭代也只会更接近曲线的根,用数学术语来说就是,迭代收敛了)。第四次得到的 $x_4$ 就已经很接近 $x_0$ 了,如下图:
NewtonIteration

牛顿-拉弗森方法的代数解法

  现在把求曲线 $f(x)$ 的根转化成了不断求切线的根(就是切线和 $x$ 轴的交点),切线的根简单,与 $x$ 轴的交点嘛,令切线方程等于 0 就行,现在的问题就是不断求曲线 $f(x)$ 的切线方程,先求第一个点 $x_1$ 的切线方程,具体就是:
已知:

切点 $(x_1, f(x_1))$

求:

  1. 曲线 $f(x)$ 的切线方程
  2. 切线方程的根(就是切线和 $x$ 轴的交点)

  只须求出曲线的导数 $f\prime(x_1)$ 并代入点斜式方程即可。因为切线方程可以用点斜式方程 $y - y_1 = k(x - x_1)$ 来求,其中 $k$ 是斜率,斜率又可以用该点处的导数 $k = f\prime(x_1)$ 求得(切线、斜率和导数的关系可以看下面章节),切线方程如下:

$y - y_1 = k(x - x_1)$
$\Rightarrow f(x) - f(x_1) = f\prime(x_1)(x - x_1)$

  求根既然是求切线和 $x$ 轴的交点,那就令 $f(x) = 0$,做一下变形:

$0 - f(x_1) = f\prime(x_1)(x - x_1)$
$\Rightarrow - f(x_1) = f\prime(x_1)(x - x_1)$
$\Rightarrow f\prime(x_1)(x - x_1) + f(x_1) = 0$
$\Rightarrow x\cdot f\prime(x_1) = x_n\cdot f\prime(x_1) - f(x_1)$
$\Rightarrow x = x_1 - \frac{f(x_1)}{f\prime(x_1)}$

  现在求出的 $x$ 其实就是 $x_2$ ,下一次迭代以 $(x_2, f(x_2))$ 为切点求切线方程,得到 $x_3$,也就是 $x_3= x_2 - \frac{f(x_2)}{f\prime(x_2)}$,如此反复逐渐逼近真实值,这就是 牛顿迭代法的公式:$x_{n+1} = x_n - \frac{f(x_n)}{f\prime(x_n)}$

  有的函数越迭代越远,也就是发散的,无法收敛到我们想要的结果;有的函数是来回震荡,不收敛,所以牛顿迭代法也是有条件的,充分条件如下:
设 $f(x)$ 在 $[a, b]$ 满足

  1. $f(a) \cdot f(a) < 0$。
  2. $f(x) \in [a, b]$,$f\prime(x)$ 和 $f\prime\prime(x)$ 均存在,且 $f\prime(x)$ 和 $f\prime\prime(x)$ 的符号均保持不变。
  3. $f(x) \cdot f\prime\prime(x) > 0$,$x \in [a, b]$ 则方程 $f(x) = 0$ 在 $[a, b]$ 上有且只有一个实根。

  则牛顿迭代序列 ${x_n}$ ,单调地收敛于方程 $f(x) = 0$ 的根 $x^*$ 。

切线、斜率与导数

  复习一下切线、斜率和导数的基本概念:

  切线,几何上 切线指的是一条刚好触碰到曲线上某一点的直线。更准确地说,当切线经过曲线上的某点(即切点)时,切线的方向与曲线上该点的方向是相同的。在高等数学中,对于一个函数,如果函数某处有导数,那么此处的导数就是过此处的切线的斜率,该点和斜率所构成的直线就为该函数的一个切线。

  斜率,亦称“角系数”,表示一条直线相对于横轴的倾斜程度。一条直线与某平面直角坐标系横轴正半轴方向的夹角的正切值即该直线相对于该坐标系的斜率。如果直线与 x 轴垂直,直角的正切值无穷大,故此直线不存在斜率。当直线 L 的斜率存在时,对于一次函数 $y=kx+b$ (斜截式),k 即该函数图像(直线)的斜率。

  导数,导数是函数的局部性质。一个函数在某一点的导数描述了这个函数在这一点附近的变化率。如果函数的自变量和取值都是实数的话,函数在某一点的导数就是该函数所代表的曲线在这一点上的切线斜率。导数的本质是通过极限的概念对函数进行局部的线性逼近。例如在运动学中,物体的位移对于时间的导数就是物体的瞬时速度。在高等数学中,对于一个函数,如果函数某处有导数,那么此处的导数就是过此处的切线的斜率,该点和斜率所构成的直线就为该函数的一个切线。

  直线方程常用的表达形式主要有点斜式、斜截式、两点式和截距式:

  1. 当已知斜率 k 和一点坐标 $(x_1, y_1)$ 时,常用点斜式:$y-y_1 = k(x - x_1)$
  2. 当已知斜率 k 和 y 轴截距 b 时,常用斜截式:$y = kx + b$
  3. 当已知两点坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 时,常用两点式:$\frac{x - x_1}{x_2 - x_1} = \frac{y - y_1}{y_2 - y_1}$
  4. 当已知所有截距 a 和 b 时,常用截距式:$\frac{x}{b} + \frac{y}{b} = 1$

代码实现

  比如求 5 的平方根,可以看成求 $f(x) = x^2 - 5$ 与 $x$ 轴的交点:

已知:

$f(x) = x^2 - 5$
$f\prime(x) = 2x$

我们用 $r$ 表示最终的结果,根据牛顿迭代法:

$x_{n+1} = x_n - \frac{f(x_n)}{f\prime(x_n)}$
$\Rightarrow r = r - \frac{f(r)}{f\prime(r)}$
$\Rightarrow r = r - \frac{r^2 - 5}{2\times r}$

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def mySqrt(self, n):
r = n
while r * r > n:
r = int((r + n/r) / 2) # 不用 int()的话,n = 5 时死循环
#r = int(r - (r*r - n)/2/r)
return r

if __name__ == '__main__':
S = Solution()
num = 5
print(S.mySqrt(num))

对比二分查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def mySqrt(self, x):
if x == 0 or x == 1:
return x
if x == 2 or x == 3:
return 1
left, right = 0, x//2
while left <= right:
mid = left + (right - left)//2
if mid * mid <= x < (mid+1)*(mid+1):
return mid
elif mid < x // mid:
left = mid + 1
else:
right = mid - 1

if __name__ == '__main__':
S = Solution()
num = 5
print(S.mySqrt(num))

参考

如何通俗易懂地讲解牛顿迭代法?
「珂学原理」No.96「牛顿如何迭代」
牛顿法
线性近似
切线
斜率
导数
用导数求切线方程的四种类型

文章目录
  1. 1. 牛顿迭代法求根过程
  2. 2. 牛顿-拉弗森方法的推导
    1. 2.1. 线性近似
    2. 2.2. 牛顿-拉弗森方法的几何直觉
    3. 2.3. 牛顿-拉弗森方法的代数解法
    4. 2.4. 切线、斜率与导数
  3. 3. 代码实现
  4. 4. 参考