不动点理论和 isGoodEnough 函数

Question

在 Coursera 课程 Functional Programming Principles in Scala 中，讲师谈到 Fixed Point 并写了一些简单的实现。

def isCloseEnough(x: Double, y: Double) = 
    math.abs((x - y) / x) / x < tolerance

def fixedPoint(f: Double => Double)(guess: Double) = {

    def iterate(guess: Double): Double = {
        val next = f(guess)
        if (isCloseEnough(guess, next)) next
        else iterate(next)
    }
    iterate(guess)
}

这样的实现将允许以下函数 f(x) = 1 + x 有一个固定点。

然而，这不应该永远发生。如这个函数图中所示：

这就是维基百科所说的：

Not all functions have fixed points: for example, if f is a function defined on the real numbers as f(x) = x + 1, then it has no fixed points, since x is never equal to x + 1 for any real number.

这里的重点是 isCloseEnough 我不明白为什么要这样写。

我来这里是为了了解 isCloseEnough 以及为什么要这样实施这就是全部。

Answer 1

该算法并不完美，它显然应该取决于您选择的容差。如果我们检查 isCloseEnough:

def isCloseEnough(x: Double, y: Double) = 
    math.abs((x - y) / x) / x < tolerance

真的很像：

| x - y | / x^2 < tolerance

只是因为某些原因没有取x外除的绝对值，当x为负数时完全破坏了算法。

不过，我们的想法是，我们通过找到 任意接近 到 f(x) 的 x 来找到不动点，即 f(x) 之间的差异 x 和 f(x) 和我们想要的一样小（低于一些公差）。如果我们可以快速找到固定点，这就可以正常工作：

scala> fixedPoint(math.sqrt)(2)
res2: Double = 1.0000846162726942

这里，固定点是x = 1，其中math.sqrt(1) = 1。我用了tolerance = 0.0001。如果我使用更小的东西，我显然会更接近不动点 1.

但现在说我有：

def f(x: Double): Double = x + 1

scala> fixedPoint(f)(1)
res4: Double = 102.0

它找到了一个大约102.0的不动点。显然，这是错误的，但它会发生，因为 x 和 f(x) 之间的差异对于此函数是 always 1，并且作为 x 变大，1 / x^2 越来越小，直到低于 tolerance。如果我把 tolerance 变小，我会找到一个更大的不动点。

val tolerance = 0.000000001

scala> fixedPoint(f)(1)
res5: Double = 31624.0

这显然也是错误的。但关键是，对于一个固定点，我应该能够使 tolerance 任意小 ，并且仍然得到一致的结果。有了这个函数，显然对于任何固定的tolerance，最终1 / x^2都会比它小。但是，对于任何x，我总是可以选择一个足够小的tolerance使得1 / x^2总是落在它之外，所以没有定点.

这算不上是数学证明，但重点是该算法在某些标准上存在缺陷。

不动点理论和 isGoodEnough 函数

Fixed point theory and the isGoodEnough function

computer-science

scala

fixed-point-iteration