Fixed Point Iteration

From Wikiversity
Jump to navigation Jump to search

Fixed Point Iteration[edit]

What is Fixed Point Iteration?[edit]

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

Algorithm[edit]

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

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

Step 1: Set i =1

Step 2: While Steps 3 - 6

Step 3: Set p = g(p0)

Step 4: If then OUTPUT (p); (The procedure was successful). STOP.

Step 5: Set i = i + 1

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

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

Examples[edit]

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

Answer.

We know that,
x0 = 2
xn+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.


2. Consider the iteration pn+1 = g(p0) when the function g(x) = 1 + x - x2/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
.....
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[edit]

Two methods in which Fixed point technique is used:

1. Newton Raphson Method

Formula
where,
xn - initial point
f(xn) is the value of the function at that point
f'(xn) is the value of the differentiated function at that point.
Plug all these values into the above equation to get xn+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 (xn and xn-1)
Formula
Similar to Newton Raphson's method plug in all values to generate next approximation.

Exercises[edit]

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


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

Calculating x1 i.e. 1st Iteration

Calculating x2 i.e. 2nd Iteration

Calculating x3 i.e. 3rd Iteration

Calculating x4 i.e. 4th Iteration

Calculating x5 i.e. 5th Iteration

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

Quizzes[edit]

<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 xn+1 = g (x) produces a sequence } +that diverges away from P -that converges towards P -Depends

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

{Consider the following fixed point iteration; . Rate (order) of convergence of this iteration is |type="()"} +Quadratic -Linear -Cubic