Num Methods: Fixed Point Iteration

30 days ago by solin

Fixed-Point Iteration Method

The Fixed-Point Iteration method is an iterative technique that solves approximately equations of the form g(x) = x where g(x) is an arbitrary function which is Lipschitz-continuous with the constant 0 ≤ K < 1. (Lipschitz-continuous means continuous and piecewise-differentiable, with |g'(x)| < 1). Differentiable functions such that |g'(x)| < 1 satisfy this condition. If this basic assumption is satisfied, then the method converges for any initial guess x0. 

The following active input text box contains the main code. You need to click on it to see an "Evaluate" link appear at its bottom. Click on this link to have the code sent to our computer and interpreted. Then you can evaluate/modify/evaluate the examples in the other text boxes in the same way. Have fun and let us know at femhub@googlegroups.com with any problems or questions.

The Code:
# importing symbolics and plotting functions from sympy import (var, pi, factorial, sin, cos, log, exp, tan, atan, asin, acos, sinh, cosh, tanh, asinh, acosh, sqrt, lambdify) import pylab # we will be using the symbol 'x' for independent variable var("x") # performing the fixed point iteration method with function # g(x), initial guess x0, and error tolerance epsilon. def fixed_point(g, x, x0, epsilon): if epsilon <= 0: print "Epsilon must be greater than zero!" print "Stopping." return g = lambdify(x, g, modules=["math"]) x_old = float(x0) count = 1 while 1: x_new = g(x_old) residual = abs(g(x_new) - x_new) print "step:", count, "approximation:", x_new, "residual:", residual # in order to stop, both x_new and x_old must be close enough AND # the residuum abs(g(x_new) - x_new) must be sufficiently small if abs(x_new - x_old) < epsilon and abs(g(x_new) - x_new) < epsilon: break x_old = x_new count += 1 print "Done." 
       

Input: function g(x), x symbol for the independent variable, initial guess x0, and a tolerance epsilon > 0.
fixed_point(1/(1+x**2), x, 5, 1e-8) 
        
step: 1 approximation: 0.0384615384615 residual: 0.960061356664
step: 2 approximation: 0.998522895126 residual: 0.497783797229
step: 3 approximation: 0.500739097896 residual: 0.298787809776
step: 4 approximation: 0.799526907672 residual: 0.189489328391
step: 5 approximation: 0.610037579281 residual: 0.118747922172
step: 6 approximation: 0.728785501453 residual: 0.0756723721716
step: 7 approximation: 0.653113129281 residual: 0.0478754526607
step: 8 approximation: 0.700988581942 residual: 0.0304709051819
step: 9 approximation: 0.67051767676 residual: 0.0193306746732
step: 10 approximation: 0.689848351434 residual: 0.0122914242886
step: 11 approximation: 0.677556927145 residual: 0.0078048603863
step: 12 approximation: 0.685361787531 residual: 0.00496043937133
step: 13 approximation: 0.68040134816 residual: 0.00315088391588
step: 14 approximation: 0.683552232076 residual: 0.00200217234965
step: 15 approximation: 0.681550059726 residual: 0.0012719555375
step: 16 approximation: 0.682822015264 residual: 0.000808175080785
step: 17 approximation: 0.682013840183 residual: 0.000513451099407
step: 18 approximation: 0.682527291282 residual: 0.000326225671936
step: 19 approximation: 0.68220106561 residual: 0.000207262657243
step: 20 approximation: 0.682408328268 residual: 0.000131684373328
step: 21 approximation: 0.682276643894 residual: 8.36644406271e-05
step: 22 approximation: 0.682360308335 residual: 5.31559298369e-05
step: 23 approximation: 0.682307152405 residual: 3.37722425245e-05
step: 24 approximation: 0.682340924648 residual: 2.14570369528e-05
step: 25 approximation: 0.682319467611 residual: 1.36325951653e-05
step: 26 approximation: 0.682333100206 residual: 8.66139811373e-06
step: 27 approximation: 0.682324438808 residual: 5.50296861312e-06
step: 28 approximation: 0.682329941776 residual: 3.49628110052e-06
step: 29 approximation: 0.682326445495 residual: 2.2213422477e-06
step: 30 approximation: 0.682328666837 residual: 1.41131747911e-06
step: 31 approximation: 0.68232725552 residual: 8.96672590178e-07
step: 32 approximation: 0.682328152193 residual: 5.69695924546e-07
step: 33 approximation: 0.682327582497 residual: 3.61953101824e-07
step: 34 approximation: 0.68232794445 residual: 2.29964877252e-07
step: 35 approximation: 0.682327714485 residual: 1.46106893806e-07
step: 36 approximation: 0.682327860592 residual: 9.28281963519e-08
step: 37 approximation: 0.682327767764 residual: 5.89778738069e-08
step: 38 approximation: 0.682327826741 residual: 3.74712615381e-08
step: 39 approximation: 0.68232778927 residual: 2.38071559133e-08
step: 40 approximation: 0.682327813077 residual: 1.51257431025e-08
step: 41 approximation: 0.682327797952 residual: 9.61005619526e-09
step: 42 approximation: 0.682327807562 residual: 6.10569539372e-09
Done.
fixed_point(sqrt(x), x, 0.5, 1e-8) 
       
fixed_point(exp(x-2), x, 4.0, 1e-8)