牛頓法：使用Python構建高階程序

in pg。 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」的兩倍。當我打印每個迭代的「猜測」和「下一個」時，我的下一個猜測就是保持加倍。所以最後整數溢出。

爲什麼？我的代碼有什麼問題？我的邏輯有什麼問題？謝謝你的時間。請幫忙。

來源

2014-11-14 Lucas Shen

整數不會溢出Python編寫的。他們只是在不斷增長。（好吧，最終你會得到一個'MemoryError'，但它們不會回滾到0.）所以，你對這個問題的描述是不正確的。然而，你顯然正在轉換到某個地方（希望足夠早），或者'sqrt（2）'必須是'1'，所以這並不重要。 – abarnert

也許在頂部工作中加入'from __future__ import division'？ – Wilbeibi

我很困惑這應該如何工作。沒有平方發生在任何地方，所以，即使這樣做會聚，它如何會聚到平方根？（你的'deriv'和'newton_transform'函數看起來很好，我只是沒有得到你想要在這裏轉換的東西。）沒有看到Scheme代碼，你正在移植它很難猜測什麼是丟失 – abarnert

要使用牛頓的方法來查找，說，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)

來源

2014-11-14 01:30:48 abarnert

是的。這是答案。我明白牛頓的方法是錯誤的。非常感謝你！！！！！！邏輯錯誤比編程錯誤更難以識別... –

@LucasShen：我很高興你能理解，因爲我很難解釋數學，我會建議如果你沒有沒有辦法，你應該去別的地方（也許[Math.sx]（http://mathematics.stackexchange.com）），在那裏有人可以把它變得更好。 :) – abarnert

哈哈哈，這也是很好的資源。但是，從我以前的錯誤中，我的g（y）= x/y，所以我的牛頓變換會給我一個lambda y：2 * y。這就是我猜測不能收斂的原因......並且保持每次迭代翻倍。 –

牛頓法：使用Python構建高階程序

回答

相關問題