2

逐次逼近是一种通用方法，在该方法中，在算法的每次迭代中，我们都会找到对我们正在寻找的答案的更接近的估计。一类逐次逼近算法使用固定点的思想。如果 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) 的不动点。并做了。

（以上解法均正确）

4

2 回答 2

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)
于 2014-09-29T19:25:01.940 回答
0

您可能想看看scipy中的优化和寻根功能。

特别是scipy.optimize.fixed_point。实际的源代码在这里。

于 2013-11-10T13:41:51.587 回答