# Fixed Point Iteration

### 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 p_{0}.

INPUT: Initial approximation p_{0}; tolerance TOL; maximum number of iterations N_{0}.
OUTPUT: approximate solution p or message of failure.

Step 1: Set i =1

Step 2: While Steps 3 - 6

Step 3: Set p = g(p_{0})

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

Step 5: Set i = i + 1

Step 6: Set p_{0} = p. (Update p_{0})

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

- x
_{n+1}= 0.5 * ( x0 + (2/ x0))

- x

- 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 p_{n+1} = g(p_{0}) when the function g(x) = 1 + x - x^{2}/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,
- 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

- Plug all these values into the above equation to get x

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})

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

- 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)'?

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_{1} i.e. 1st Iteration

Solution:

x_{1} = 2.55

Calculating x_{2} i.e. 2nd Iteration

Solution:

x_{2} = 1.373

Calculating x_{3} i.e. 3rd Iteration

Solution:

x_{3} = 0.8685

Calculating x_{4} i.e. 4th Iteration

Solution:

x_{4} = 0.722

Calculating x_{5} i.e. 5th Iteration

Solution:

x_{5} = 0.707

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

Solution:

Iteration: 6

#### 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 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} = 0.
|type="()"}
+True
-False

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