Fixed point theory and the isGoodEnough function

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:

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.

The algorithm isn't perfect, and it should obviously depend upon your choice of tolerance. If we examine isCloseEnough:

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

It is really similar to:

| x - y | / x^2 < tolerance

Except that for some reason it is not taking the absolute value of the outer division of x, which completely breaks the algorithm when x is negative.

The idea though, is that we find a fixed point by finding an x that is arbitrarily close to f(x), i.e. the difference between x and f(x) is as small as we want (below some tolerance). This works fine if we can find fixed points quickly:

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

Here, the fixed point is x = 1, where math.sqrt(1) = 1. I used tolerance = 0.0001. Had I used something smaller, I would obviously gain a closer approximation of the fixed point 1.

But now say I have:

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

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

It finds a fixed point of approximately 102.0. Obviously, this is wrong, but it happens because the difference between x and f(x) is always 1 for this function, and as x gets larger, 1 / x^2 gets smaller and smaller until it falls below the tolerance. If I make the tolerance smaller, I will find a larger fixed point.

val tolerance = 0.000000001

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

This is obviously also wrong. But the point is, for something to be a fixed point, I should be able to make tolerance arbitrarily small, and still get a consistent result. With this function, it is clear that for any fixed tolerance, eventually 1 / x^2 will be smaller than it. But, for any x, I can always choose a small enough tolerance such that 1 / x^2 will always fall outside of it, so there are no fixed points.

This is hardly a mathematical proof, but the point is that the algorithm is flawed for some criteria.