Iteration

Contents

Summary

• Iteration is a method of finding an approximate solution of a given equation.
• Remember the 3 steps below to carry out iteration:
1. Find the interval in which the root lies.
2. Select a suitable value in that interval then substitute again and again in the given iterative formula to give a better approximation.
3. When we find an approximation which is outside the interval where the actual root lies. We say that the iteration has failed due to either the iteration formula itself or the incorrect value of the input.

There are many equations which can not be solved by using algebraic formulae for exact solutions. However we can use different techniques to find their approximate solutions to any degree of accuracy. Iteration is one of the techniques that can be used.

What is iteration?

An iterative process is one which is repeated several times following exactly the same procedure each time. It provides a method of obtaining the solution to an equation f(x) = 0 in which we rearrange the equation to create an iterative formula of the form  ${ x }_{ n\quad +\quad 1 }\quad =\quad f\left( { x }_{ n } \right)$.

Where  ${ x }_{ n\quad +\quad 1 }\quad =\quad f\left( { x }_{ n } \right)$  is a better approximation than  ${ x }_{ n }$  to the solution of .

The steps we follow to do iteration are:

1.     Initially we find the interval in which the root lies. For this we calculate f(a) and f(b). If they are of opposite sign and f(x) is continuous in that interval then the equation f(x) = 0 has a root in the interval a < x < b.

2.     To find the approximate value of the root, we select a suitable value in that interval. It is then used as an input to a given iterative formula and it gives a better approximation. This is then substituted again to give an even better approximation. The procedure is repeated until the required degree of accuracy is obtained.

3.     Sometimes an interaction gives an approximation which is outside the interval where the actual root lies. We say that the iteration has failed and the failure is due to the iteration formula itself or the incorrect value of the input.

Generally, an iterative formula converges to the actual root if  $\left| f^{ ' }\left( x \right) \right| \quad <\quad 1$  near the root and diverges if  $\left| f^{ ' }\left( x \right) \right| \quad >\quad 1$  near the root.
We will move onto an example which will show how the above steps are carried out in order to solve an equation through iteration.

Example

Q.

i) The equation  ${ x }^{ 3 }\quad +\quad x\quad +\quad 1\quad =\quad 0$ has one real root. Show by calculation this root lies between -1 and 0.

ii) Show that if a sequence of values given by the iterative formula  ${ x }_{ n\quad +\quad 1 }\quad =\quad \frac { 2{ x }_{ n }^{ 3 }\quad -\quad 1 }{ 3{ x }_{ n }^{ 2 }\quad +\quad 1 }$  converges, then it converges to the root of the equation given in part (1).

iii) Use this iterative formula with initial value  ${ x }_{ 1 }\quad =\quad 0.5$  to determine the root correct to a 2 decimal places.

Solution:

i) Let:

$f\left( x \right) \quad =\quad { x }^{ 3 }\quad +\quad x\quad +\quad 1$

$f\left( -1 \right) \quad =\quad { (-1) }^{ 3 }\quad +\quad (-1)\quad +\quad 1\quad =\quad -1\quad \quad \quad \quad <\quad 0$

$\left( 0 \right) \quad =\quad { (0) }^{ 3 }\quad +\quad (0)\quad +\quad 1\quad =\quad 1\quad \quad \quad \quad >\quad 0$

Now since there is change of sign, therefore there is a root between -1 and 0.

ii) Given that  ${ x }_{ n\quad +\quad 1 }\quad =\quad \frac { 2{ x }_{ n }^{ 3 }\quad -\quad 1 }{ 3{ x }_{ n }^{ 2 }\quad +\quad 1 }$,  removing n, we have  ${ x }\quad =\quad \frac { 2{ x }^{ 3 }\quad -\quad 1 }{ 3{ x }^{ 2 }\quad +\quad 1 }$ .

So,

${ x }\quad =\quad \frac { 2{ x }^{ 3 }\quad -\quad 1 }{ 3{ x }^{ 2 }\quad +\quad 1 }$

${ 3{ x }^{ 3 }\quad +\quad x }\quad =\quad 2{ x }^{ 3 }\quad -\quad 1$

${ { x }^{ 3 }\quad +\quad x }\quad +\quad 1\quad =\quad 0$       which is the same as giving in part (1)

iii) Substituting  ${ x }_{ 1 }\quad =\quad -0.5$ in the given iterative formula:

${ x }_{ 2 }\quad =\quad \frac { 2{ (-0.5) }^{ 3 }\quad -\quad 1 }{ 3{ (-0.5) }^{ 2 }\quad +\quad 1 }$

$=\quad \frac { -1.25 }{ 1.75 } \quad =\quad -0.714286$

${ x }_{ 3 }\quad =\quad \frac { 2{ (-0.714286) }^{ 3 }\quad -\quad 1 }{ 3{ (-0.714286) }^{ 2 }\quad +\quad 1 }$

$=\quad \frac { -1.728864}{ 2.530613 } \quad =\quad -0.683180$

${ x }_{ 4 }\quad =\quad \frac { 2{ (-0.683180) }^{ 3 }\quad -\quad 1 }{ 3{ (-0.683180) }^{ 2 }\quad +\quad 1 }$

$=\quad \frac { -1.637728 }{ 2.400205 } \quad =\quad -0.682328$

Ans:          The required root is  $\alpha \quad =\quad -0.68$  correct to 2 decimal places