牛顿法:用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”值都是“猜测”的两倍。当我打印出每一次迭代的“猜测”和“下一步”时，我的下一个猜测就会加倍。所以整数在结尾溢出。

为什么？我的密码怎么了？我的逻辑怎么了？耽误您时间，实在对不起。请帮帮忙。

Answer 1

要用牛顿的方法找到，比方说，sqrt(2)-that is，y**2 == 2-you首先写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)