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 ${\displaystyle i\leq No}$ Steps 3 - 6

Step 3: Set p = g(p₀)

Step 4: If ${\displaystyle |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.

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

..... ${\displaystyle \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

${\displaystyle 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

${\displaystyle 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)'?

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

Calculating x₂ i.e. 2nd Iteration

Calculating x₃ i.e. 3rd Iteration

Calculating x₄ i.e. 4th Iteration

Calculating x₅ i.e. 5th Iteration

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

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; ${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$. Rate (order) of convergence of this iteration is |type="()"} +Quadratic -Linear -Cubic