Fixed-Point Iteration

Fixed-Point Iteration, FPI for short, is another equation solving method. But! Unlike The Bisection Method you have to exercise more caution.

First we need to rewrite the initial problem from f(x)=0 to g(x)=x and iterate until the solution stabilizes. Here is the code for FPI:

fpi :: (F -> F) -> F -> Integer -> [F]
fpi _ _ 0 = []
fpi g x0 k = xc : fpi g xc (k-1)
 where xc = g(x0)

The code is simple and the method returns a list with the intermediate approximated solutions. The best solution is in the end of the list.

Let us try to solve the same equation as the one presented in The Bisection Method, f(x)=x^3+x-1. Re-writing it we would get the equation: x=1-x^3 thus g(x)=1-x^3 (remember it should be of the form g(x)=x). But FPI will fail and the list returned would look like:

[0.0,1.0,0.0,1.0,0.0,1.0,0.0,1.0,0.0,1.0,0.0,...]

That is no good! But if we happen to add 2x^3 to both sides of the equation, and rearrange things we get: x = (1+2x^3)/(1+3x^2). So using g(x)=(1+2x^3)/(1+3x^2) we will have a good approximation in just 6 steps!

[0.75,0.68604654,0.68233955,0.68232775,0.6823278,
0.6823278]

Why? Well because there is a theorem that says: Assume g(x) is continuously differentiable, and g(r)=r, and |g'(r)|<1. Then FPI converges to the fixed point r for sufficiently close initial guess to r.

Checking |g'(r)| (r≃0.68) for the first attempt we can see that it is larger than 1, but not the second attempt.

FPI can converge to a solution faster than The Bisection Method, but we need to re-write the original solution. Because we dont now the solution r beforehand we can test re-writing it differently until FPI succeeds.