SICP - Which functions converge to fixed points?

Question

In chapter 1 on fixed points, the book says we can find fixed points of certain functions using

f(x) = f(f(x)) = f(f(f(x))) ....

What are those functions?

It doesn't work for y = 2y when i rewrite it as y = y/2 it works

Does y need to get smaller everytime? Or are there any general attributes that a function has to have to find fixed points by that method?

What conditions it should satisfy to work?

Answer 1

According to the Banach fixed-point theorem, such a point exists iff the mapping (function) is a contraction. That means that, for example, y=2x doesn't have fixed point and y = 0,999... * x has. In general, if f maps [a,b] to [a,b], then |f(x) - f(y)| should be equal to c * |x - y| for some 0 <= c < 1 (for all x, y from [a, b]).

Answer 2

Say you have:

f(x) = sin(x)

then x = 0 is a fixed point of the function since:

f(0) = sin(0) = 0
f(f(0)) = sin(sin(0)) = sin(0) = 0

Not every point along x is a fixed point of sin, only 0 is.

Different functions have different fixed points, if at all. You can find more on fixed points of functions at Wikidpedia