2

In Coursera course Functional Programming Principles in Scala, the Lecturer talks about the Fixed Point and wrote some simple implementation of it.

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)
}

Such implementation will allow the following function f(x) = 1 + x to have a Fixed Point.

However this should not never happen. As in this function graph:

enter image description here

And this is what stated by Wikipedai:

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.

The point here is in the isCloseEnough that I couldn't why it is written that way.

I am here to understand the isCloseEnough and why it was implemented that way That is All.

4

1 回答 1

3

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

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

它真的类似于：

| x - y | / x^2 < tolerance

除了由于某种原因它没有取 的外除的绝对值，这在为负x时完全破坏了算法。x

然而，我们的想法是，我们通过找到一个任意接近 的 来找到一个固定点x，即和之间f(x)的差异尽可能小（低于某个容差）。如果我们可以快速找到固定点，这很好用：xf(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)函数，并且随着变大，变得越来越小，直到它低于. 如果我做的更小，我会找到一个更大的固定点。 1x1 / x^2tolerancetolerance

val tolerance = 0.000000001

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

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

这几乎不是数学证明，但关键是该算法在某些标准上存在缺陷。

于 2015-07-05T15:39:48.903 回答