Tuesday, January 3, 2012

Fixed point iteration

A fixed point for a function is a point at which the value of the function does not change when the function is applied. More formally, x is a fixed point for a given function f if
and the fixed point iteration
converges to the a fixed point if f is continuous.
The following function implements the fixed point iteration algorithm:
from pylab import plot,show
from numpy import array,linspace,sqrt,sin
from numpy.linalg import norm

def fixedp(f,x0,tol=10e-5,maxiter=100):
 """ Fixed point algorithm """
 e = 1
 itr = 0
 xp = []
 while(e > tol and itr < maxiter):
  x = f(x0)      # fixed point equation
  e = norm(x0-x) # error at the current step
  x0 = x
  xp.append(x0)  # save the solution of the current step
  itr = itr + 1
 return x,xp
Let's find the fixed point of the square root funtion starting from x = 0.5 and plot the result
f = lambda x : sqrt(x)

x_start = .5
xf,xp = fixedp(f,x_start)

x = linspace(0,2,100)
y = f(x)
The result of the program would appear as follows:
The red dot is the starting point, the blue ones are the sequence x_1,x_2,x_3,... and the green is the fixed point found.
In a similar way, we can compute the fixed point of function of multiple variables:
# 2 variables function
def g(x):
 x[0] = 1/4*(x[0]*x[0] + x[1]*x[1])
 x[1] = sin(x[0]+1)
 return array(x)

x,xf = fixedp(g,[0, 1])
print '   x =',x
print 'f(x) =',g(xf[len(xf)-1])
In this case g is a function of two variables and x is a vector, so the fixed point is a vector and the output is as follows:
   x = [ 0.          0.84147098]
f(x) = [ 0.          0.84147098]


  1. This comment has been removed by a blog administrator.

  2. I have used a function almost the same as fixedp and it returns complex values for some values of x while I am sure the answer should be real number. Do you know how I can solve it?

  3. wait what function is this finding the fixed points of?

    1. In the first example the square root. In the second, you can have a look at the function g.

  4. Hi everybody
    Thanks for the author for these examples. One should note that the fixed point method is used to find the zeros or roots of functions. In the first example, the author solved the equation f(x)=x-sqrt(x)=0 and the solution is at x=1. Similarliry the second example solved a multi-variate equation to find the root of f(x,y)=[1/4*(x*x + y*y)-x, sin(x+1)-y]=[0,0].
    Keep the good job :-)