python - 牛顿法 : building higher order procedure using python

Question

我正在研究计算机程序的结构和解释。

在页。 73，它以牛顿法为例说明如何构造高阶程序。

这是我的代码:

def deriv(g):
    dx = 0.00001
    return lambda x: (g(x + dx) - g(x)) / dx


def newton_transform(g):
    return lambda x: x - g(x) / deriv(g)(x)


def fixed_point(f, guess):
    def close_enough(a, b):
        tolerance = 0.00001
        return abs(a - b) < tolerance

    def a_try(guess):
        next = f(guess)
        if close_enough(guess, next):
            return next
        else:
            return a_try(next)

    return a_try(guess)


def newton_method(g, guess):
    return fixed_point(newton_transform(g), guess)


def sqrt(x):
    return newton_method(lambda y: x / y, 1.0)

print sqrt(2)

代码会崩溃并给我 ZeroDivisionError。我知道它是如何崩溃的，但我不明白它为什么会这样。

在我的“a_try”函数中，每个“next”都是“guess”的两倍值。当我打印出每次迭代的“猜测”和“下一个”时，我的下一个猜测只会加倍。所以最后整数溢出。

为什么？我的代码有什么问题？我的逻辑有什么问题？谢谢你的时间。请帮忙。

Answer 1

要使用牛顿法求 sqrt(2)——即 y**2 == 2——你首先要写 g( y) = y**2 - 2，然后使用 newton_transform 对其进行迭代，直到收敛。

您的 deriv 和 newton_transform 很好，您的 fixed_point 实际上会迭代 newton_transform 直到它收敛——或者直到达到递归限制，或者直到浮点运算下溢。在您的情况下，它是最后一个。

为什么？好吧，看看你的 g(y):它是 2/y。我不知道你从哪里得到的，但是 g/g' 只是 -y，所以牛顿变换是 y - -y，这显然不会收敛。

但如果您插入 y**2 - 2，则 g/g' 上的变换将收敛(至少对于大多数值)。

所以:

def sqrt(x):
    return newton_method(lambda y: y**2-x, 1.0)