shidenggui commented 6 years ago

编程与数学(3): Newton‘s Method

缘起

前几天看到一道题目，是关于“对整数 n 开平方，求其整数部分”，解法用到了 Newton's Method，因为之前刚刚学过，就顺便复习下什么是 Newton's Method，为什么可以用于求解这道题?

Newton's Method

本身是用于逼近函数零点的一种技巧。因为对没有求根公式的函数，求解它的零点是非常困难的，因此就发明了 Newton‘s Method 来逼近该函数的零点。具体方法如下图所示:

应用

至于为什么用于逼近函数零点的 Newton's Method 会跟 “对整数 n 开平方” 有关代码实现如下:

def int_sqrt(n):
    """
    >>> int_sqrt(0)
    0
    >>> int_sqrt(1)
    1
    >>> int_sqrt(80)
    8
    >>> int_sqrt(81)
    9
    >>> int_sqrt(82)
    9
    """
    x_n = 1 
    x_n_plus_1 = (1 + n) / 2
    #while int(x_n_plus_1) != int(x_n): 原来的错误做法，具体见评论
    while abs(x_n_plus_1) != int(x_n):
        x_n = x_n_plus_1
        x_n_plus_1 = (x_n + n / x_n) / 2
    return int(x_n_plus_1)

如果是开 k 次方呢？

代码实现如下：

def int_sqrt_of(n, k=3):
    """
    >>> int_sqrt_of(26, 3)
    2
    >>> int_sqrt_of(27, 3)
    3
    >>> int_sqrt_of(28, 3)
    3
    """
    x_n = 1
    x_n_plus_1 = (k - 1 + n) / k
    while abs(x_n_plus_1 - x_n) > 0.01:
        x_n = x_n_plus_1
        x_n_plus_1 = ((k - 1) * x_n + n / x_n ** (k - 1)) / k
    return int(x_n_plus_1)

shidenggui commented 6 years ago

昨天写的时候太迟了，有时间加下开 K 次方的推导

shidenggui commented 6 years ago

在推导 K 次方的时候发现一个 bug，Newton's Method 本身只是逼近零点，并没有保证是从左边还是右边逼近。假设对 26 开 3 次方的整数部分应该是 2，但是按如上方式会得到 3。逼近过程:

Failed example:
    int_sqrt_of(26, 3)
Expected:
    2
Got:
    x_n:  1                  x_n_plus_1:  9.333333333333332
    x_n:  9.333333333333332  x_n_plus_1:  6.321712018140589
    x_n:  6.321712018140589  x_n_plus_1:  4.431336288615502
    x_n:  4.431336288615502  x_n_plus_1:  3.3955737286203282
    x_n:  3.3955737286203282 x_n_plus_1:  3.015383302914971
    3

看了下其他人的写法终止条件是

while abs(x_n_plus_1 - x_n) > 0.01

而不是

while int(x_n_plus_1) != int(x_n):

此时的逼近过程:

int_sqrt_of(26, 3)
Expected:
    2
Got:
    x_n:  1                  x_n_plus_1:  9.333333333333332
    x_n:  9.333333333333332  x_n_plus_1:  6.321712018140589
    x_n:  6.321712018140589  x_n_plus_1:  4.431336288615502
    x_n:  4.431336288615502  x_n_plus_1:  3.3955737286203282
    x_n:  3.3955737286203282 x_n_plus_1:  3.015383302914971
    x_n:  3.015383302914971  x_n_plus_1:  2.96341824201515
    x_n:  2.96341824201515   x_n_plus_1:  2.9624963553449146
    2

经过测试，我原本的写法开 2 次方的时候，在 1 到 1e9 上都正常，但是 3 次方很快就出现了错误。

while abs(x_n_plus_1 - x_n) > 0.01

测试是对的，但是对应的作者都没有给出严格的证明，这估计需要等我后面学到 Newton's Method 的收敛性质的时候才能判断，到时候再来补完。有空会将 K 次方的推导补充上去。

shidenggui commented 6 years ago

完结，已补充求 k 次方的推导。

shidenggui / blog