Iteration
An iterative sequence is one generated
by the recurrence relation xn+1 = F(xn).
The starting value is x0 and each term is called an iterate.
A fixed point, or convergent, occurs when
xn = F(xn).
Example
Given xn+1 = 4 - 3xn and starting point x0 = 5,
a) calculate the first five iterates.
b) find any fixed points which exist
a)
b) For fixed points, xn = F(xn)
x = 1 is a fixed point
Graphical methods
Consider the function
f(x) = x2 + x - 2
which is graphed below
From the graph, f(x) = 0 at the points (-2,0) and ( 1, 0)
Consider now re-arranging x2 + x – 2 = 0 to x = 2 - x2
x is now in the form x =F(x) , where F(x) = 2 - x2
Plotting y = 2 - x2 gives the graph
but y = 2 - x2 and x = 2 - x2
So y = x = 2 - x2 i.e. y = x = F(x)
The intersection of y = x and y = 2 - x2
gives the points (-2,0) and ( 1, 0)
Which is the same as f(x) = 0
An iterative sequence for x = 2 - x2
would be of the form
For fixed points, xn = F(xn)
So
has fixed points
Which are the intersections found above.
So, if an equation f(x) = 0 can be rearranged to
the form x = F(x), finding any fixed points of the
iterative sequence xn+1 = F(xn) may lead to solutions
for f(x)=0.
Example
Given that x3 - 4x – 5 = 0 can be written
as x = ( 4x +5)1/3 and using a starting value of 2:-
a) Write down a simple iterative formula xn+1 = F(xn)
b) Find, correct to 4dp, a root between 1 and 3
a) x = ( 4x +5) 1/3
so xn+1 = ( 4xn + 5 ) 1/3
b)
x3 - 4x – 5 = 0 has a root 2.4567 (4dp)
Below is a graph showing the same
iterative formula, this time with a starting value of
x0 = -4
Again, the system converges at 2.4567 (4dp)
First order process
If rearranging an equation f(x)=0 to
the form x = F(x) leads to x = a as a solution for the
iterative sequence xn+1 = F(xn), then f(a)=0.
Each iterate differs from a by an error en
so xn = a + en
xn+1 = F(xn) becomes a + en+1 =F(a + en)
Using Taylor’s series
For convergence,
F’(a) is a constant.
This is a first order process.
To find 
from consecutive iterates
Second order process
If F’(a) = 0
F’’(a) is a constant.
This is a second order process.
Rule of false position
Used to find approximate roots of the equation f(x)=0
Take two points on the graph, on either side of the x-axis.
A(a,f(a)) is a fixed point
P0(x0,f(x0)) is a varying point.
An iterative equation can then be formed:-
Example
Use the rule of false position to solve the equation
x4 - 2x = 0 , x > 0 to two decimal places.
f(x) = x4- 2x
f(1) = 1 - 2 = -1 giving ( 1 , -1)
f(2) = 16 - 4 = 12 giving ( 2 , 12)
Taking A (2 , 12) and P0 (1 ,-1)
Starting with x0 = 1 and f(x0) = -1
etc.
x =1.26 2dp
Newton Raphson Iteration
© Alexander Forrest