python - python中的逐次逼近

Question

逐次逼近是一种通用方法，在这种方法中，在算法的每次迭代中，我们都会找到对我们正在寻找的答案的更接近估计。一类逐次逼近算法使用不动点的思想。如果 f(x) 是一个数学函数，那么找到满足 f(x) = x 的 x 就可以得到 f 的不动点。

找到不动点的一种方法是从一些猜测开始(例如 guess = 1.0)，如果这不够好，则使用 f(guess) 的值作为下一个猜测。我们可以不断重复这个过程，直到我们得到一个在 f(guess) 的 epsilon 范围内的猜测。

这是我的代码:

def fixedPoint(f, epsilon):
    """
    f: a function of one argument that returns a float
    epsilon: a small float

    returns the best guess when that guess is less than epsilon 
    away from f(guess) or after 100 trials, whichever comes first.
    """
    guess = 1.0
    for i in range(100):
        if abs(f(guess) - guess) < epsilon:
            return guess
        else:
            guess = f(guess)
    return guess

现在进一步...

def sqrt(a):
    def tryit(x):
        return 0.5 * (a/x + x)
    return fixedPoint(tryit, 0.0001)

我想计算数字“a”的平方根，它是函数 f(x) = 0.5 * (a/x + x) 的不动点。并完成。

(以上解法正确)

Answer 1

逐次逼近是一种通用方法，在这种方法中，在算法的每次迭代中，我们都会找到对我们正在寻找的答案的更接近估计。一类逐次逼近算法使用不动点的思想。如果 f(x) 是一个数学函数，那么找到满足 f(x) = x 的 x 就可以得到 f 的不动点。

找到不动点的一种方法是从一些猜测开始(例如 guess = 1.0)，如果这不够好，则使用 f(guess) 的值作为下一个猜测。我们可以不断重复这个过程，直到我们得到一个在 f(guess) 的 epsilon 范围内的猜测。

Python 示例:

def fixedPoint(f, epsilon):
"""
f: a function of one argument that returns a float
epsilon: a small float

returns the best guess when that guess is less than epsilon 
away from f(guess) or after 100 trials, whichever comes first.
"""
     guess = 1.0   
     for i in range(100):
           if -epsilon < f(guess) - guess < epsilon:
                  return guess
           else:
                  guess = f(guess)

      return guess

进一步令函数 f 用于使用巴比伦法求平方根:

def sqrt(a):
     def babylon(x):
           def test(x):
                return 0.5 * ((a / x) + x)
           return test(x)

     return fixedPoint(babylon, 0.0001)