Fixed Point Iteration

What is Fixed Point Iteration?

http://en.wikipedia.org/wiki/Fixed_point_iteration

Algorithm

To find a solution to p = g(p) given an initial approximation p₀.

INPUT: Initial approximation p₀; tolerance TOL; maximum number of iterations N₀. OUTPUT: approximate solution p or message of failure.

Step 1: Set i =1

Step 2: While $i\leq No$ Steps 3 - 6

Step 3: Set p = g(p₀)

Step 4: If $|p-po|\leq TOL$ then OUTPUT (p); (The procedure was successful). STOP.

Step 5: Set i = i + 1

Step 6: Set p₀ = p. (Update p₀)

Step 7: OUTPUT ('The method failed after N0 iterations'). STOP.

Examples

1. Find square root of 2 accurate till third decimal (10^-3). The initial point is 2 .

Answer.

We know that,

x0 = 2

x_n+1 = 0.5 * ( x0 + (2/ x0))

x1 = 0.5 * (2 + (2/2)) = 1.5

x2 = 0.5 * (1.5 + (2/1.5)) = 1.416

x3 = 0.5 * (1.416 + (2/1.416)) = 1.4142

We found out the square root of 2 accurate till 4th decimal in 3 steps.

As implemented in python

The following python code implements the functionality of this section.

The two statements under "# Original estimate of square root (initial approximation.)" provide a pretty good estimate of initial approximation of $p_{0}.$ Unfortunately they are computationally intensive and add significant time to completion of function simpleSquareRoot().

The code within the while loop is both very simple and very fast.

Tolerance TOL is determined by the desired precision of the sqRoot, decimal.getcontext().prec, set by the code that invokes this function.

# python code.

import decimal
D = decimal.Decimal

def simpleSquareRoot (N) :
    '''
sqRoot = simpleSquareRoot (N)
Input N must be type Decimal or convertible to type Decimal.
output sqRoot is normally type Decimal.
output may be type None.
'''
    if type(N) != D :
        status = 0
        try : N = D(str(N))
        except: status = 1
        if status :
            print ('simpleSquareRoot (N): Error converting input to type Decimal.')
            return None

    if N in (0,1) : return N
    if N < 0 :
        print ('simpleSquareRoot (N) : input must be >= 0.')
        return None

    originalPrecision = decimal.getcontext().prec
    decimal.getcontext().prec += 2

    # Original estimate of square root (initial approximation.)
    # These next 2 statements are computationally intensive.
    # They add significant computational time to the execution of this function.
    sign, digits, exponent = N.as_tuple()
    n_ = n = D(10) ** ( (len(digits) + exponent) >> 1 )

    last = 0; half = D('0.5')

    if not simpleSquareRootDebug :
        while last != n :
            last = n
            n = half * (n + (N/n))

        decimal.getcontext().prec = originalPrecision
        sqRoot = (n+0).normalize()
        # Normal exit.
        return sqRoot

The following optional code is valid in debugging mode. It provides information about what happens during the while loop and verifies that the calculated square root is in fact within tolerance.

    # Here simpleSquareRootDebug is True.
    print ('simpleSquareRoot (N): N =',N)
    count = 0
    while last != n :
        count += 1
        last = n
        n = half * (n + (N/n))
        print ('n =',n)
    # Function simpleSquareRoot () checks itself.
    # Initial estimate compared with calculated value.
    ratio = decimal.Context(prec=5).create_decimal(n_/n)
    if 10 > ratio > D('0.1') :
        print ('    Original estimate =',n_,', ratio =',  ratio )
    else :
        print ('    Original estimate =',n_,', ratio =',  ratio, '*excessive*.' )
    print ('    count =',count)
    tolerance = D('1e-' + str(originalPrecision + 1))
    N_ = n * n
    v1 = abs(N-N_) ; v2 = abs(N+N_)/2
    status = (v1 > tolerance*v2)
    decimal.getcontext().prec = originalPrecision
    if status :
        print ('    Internal error 1.')
        return None
    sqRoot = (n+0).normalize()
    print ('    sqRoot =',sqRoot)
    return sqRoot

Compared with python's method decimal.Decimal.sqrt(), this code is slow for small values of precision. However, for numbers containing 550 decimal digits or more, this code (without debugging) is a little faster than python's method.

sqrt(2) with precision of 5

simpleSquareRootDebug = 1

precision = decimal.getcontext().prec = 5

sqRoot = simpleSquareRoot(2)

simpleSquareRoot (N): N = 2
n = 1.5
n = 1.416666
n = 1.414216
n = 1.414214
n = 1.414214
    Original estimate = 1 , ratio = 0.70711
    count = 5
    sqRoot = 1.4142

sqrt(2) with 1,000 places of decimals

precision = decimal.getcontext().prec =	1001

sqRoot = simpleSquareRoot(2)

simpleSquareRoot (N): N = 2
n = 1.5
n = 1.41666666666666......66666666
n = 1.41421568627450......92156862
n = 1.41421356237468......91918986
n = 1.41421356237309......93557326
n = 1.41421356237309......39275620
n = 1.41421356237309......87665231
n = 1.41421356237309......76778142
n = 1.41421356237309......02485270
n = 1.41421356237309......23938856
n = 1.41421356237309......48847209
n = 1.41421356237309......48847209
    Original estimate = 1 , ratio = 0.70711
    count = 12
    sqRoot = 
1.414213562373095048801688724209698078569671875376948073176679737990732478462
  107038850387534327641572735013846230912297024924836055850737212644121497099
  935831413222665927505592755799950501152782060571470109559971605970274534596
  862014728517418640889198609552329230484308714321450839762603627995251407989
  687253396546331808829640620615258352395054745750287759961729835575220337531
  857011354374603408498847160386899970699004815030544027790316454247823068492
  936918621580578463111596668713013015618568987237235288509264861249497715421
  833420428568606014682472077143585487415565706967765372022648544701585880162
  075847492265722600208558446652145839889394437092659180031138824646815708263
  010059485870400318648034219489727829064104507263688131373985525611732204024
  509122770022694112757362728049573810896750401836986836845072579936472906076
  299694138047565482372899718032680247442062926912485905218100445984215059112
  024944134172853147810580360337107730918286931471017111168391658172688941975
  8716582152128229518488472

Result was produced with only 12 passes through loop.

2. Consider the iteration p_n+1 = g(p₀) when the function g(x) = 1 + x - x²/4 is used. The fixed points can be found by solving equations x = g(x). The two solutions (fixed points of g) are x = -2 and x = 2. The derivative of the function is g'(x) = 1 - x/2, and there are only two cases to consider

Case 1 (P = -2):

Start with P0 = -2.05

We get

P1 = -2.100625

P2 = -2.20378135

.....

\infty

Therefore, if |g'(x)| > 1 then sequence will not converge to P = -2

Case 2 (P = 2):

Start with P0 = 1.6

We get

P1 = 1.96

P2 = 1.9996

..... 2

Therefore, if |g'(x)| < 1 then sequence will converge to P = 2

Applications

Two methods in which Fixed point technique is used:

1. Newton Raphson Method

Formula

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}

where,

x_n - initial point

f(x_n) is the value of the function at that point

f'(x_n) is the value of the differentiated function at that point.

Plug all these values into the above equation to get x_n+1. It becomes the next initial point. Repeat until you get a point within an acceptable degree of error

2. Secant Method

Used to avoid differentiated form in Newton Raphson's method. Only problem is you need two initial points for this method (x_n and x_n-1)

Formula

x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}

Similar to Newton Raphson's method plug in all values to generate next approximation.

Exercises

If 'f' is continuous and 'x' is a fixed point on 'f' then what is 'f(x)'?

Solution:

f(x) = x

Find the square root of 0.5 using fixed point iteration? Initial point 0.1 and tolerance 10^-3

Calculating x₁ i.e. 1st Iteration

Solution:

x₁ = 2.55

Calculating x₂ i.e. 2nd Iteration

Solution:

x₂ = 1.373

Calculating x₃ i.e. 3rd Iteration

Solution:

x₃ = 0.8685

Calculating x₄ i.e. 4th Iteration

Solution:

x₄ = 0.722

Calculating x₅ i.e. 5th Iteration

Solution:

x₅ = 0.707

In above problem, how many iterations or steps are needed to achieve an accuracy of 10^-8

Solution:

Iteration: 6

Quizzes

<quiz display=simple> {Is there any possibility that the fixed point isn't unique |type="()"} -Yes +No

{ Assuming g ε C[a,b], If the range of the mapping y = g(x) satisfies y ε [a,b], then} +g has a fixed point in [a,b] -g has no fixed point in [a,b] -Depends on some other condition

{ If |g'(x)| > 1, then the iteration x_n+1 = g (x) produces a sequence } +that diverges away from P -that converges towards P -Depends

{The fixed point iteration will diverge unless x₀ = 0. |type="()"} +True -False

{Consider the following fixed point iteration; $f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)$ . Rate (order) of convergence of this iteration is |type="()"} +Quadratic -Linear -Cubic