Transcript 17 Iteration using x=g(x)

“Teach A Level Maths”
Vol. 2: A2 Core Modules
17: Iteration using
x  g( x )
© Christine Crisp
Iteration
Module C3
"Certain images and/or photos on this presentation are the copyrighted property of JupiterImages and are being used with
permission under license. These images and/or photos may not be copied or downloaded without permission from JupiterImages"
Iteration
There are some equations that we can’t solve.
e.g.
x  1 x
3
However, we can find an approximate solution to some
of these equations.
The approximation can be very accurate, say to 6 or
more decimal places.
There are several methods of finding approximate
solutions and in this presentation we will study one of
them.
Iteration
There are 2 stages to getting a solution:
Stage 1. Find a 1st estimate
Stage 2. Find a formula to improve the estimate.
Sometimes we can just spot an approximate solution
to an equation.
Can you spot the approximate value of the solution to
x  2x  1 ?
3
Ans: It’s quite close to 0 as the l.h.s. is then 0 and
the r.h.s. is 1.
If we can’t quickly spot an approximation, we can use
a method involving finding bounds for the solution.
Iteration
Bounds are numbers which lie on either side of the
solution.
If these are integers we call them integer bounds.
e.g. To find integer bounds for x  1  x 3 we
can sketch y  x and y  1  x 3
y  1 x
3
y
x
This is the point . . . where y  x and y  1  x 3
so the x coordinate gives the solution to x  1  x 3
Iteration
Bounds are numbers which lie on either side of the
solution.
If these are integers we call them integer bounds.
e.g. To find integer bounds for x  1  x 3 we
can sketch y  x and y  1  x 3
y  1 x
3
y
a
x
The solution
lies between
0 and 1.
0 and 1 are
the integer
bounds.
We usually call the solution a, so 0  a  1 .
Iteration
Bounds are numbers which lie on either side of the
solution.
If these are integers we call them integer bounds.
e.g. To find integer bounds for x  1  x 3 we
can sketch y  x and y  1  x 3
y  1 x
3
y
a
x
The solution
lies between
0 and 1.
0 and 1 are
the integer
bounds.
We usually call the solution a, so 0  a  1 .
Our first approximation to a, is any number between
the bounds, say 0  5.
Iteration
If we can use Autograph or a graphical calculator,
sketching is a good method of finding the integer
bounds.
Even without a graph plotter you may have been
able to sketch these 2 graphs.
However, if we can spot likely bounds, or if we are
given values and want to show they are bounds, we
can use the algebraic method that follows and avoid
sketching.
Iteration
Rearrange the equation to get zero on one side.
e.g. For x  1  x 3 , get x 3  1  x  0
 Call this
f ( x)  0 
To show how the method works I’m going to sketch
y  f ( x ) ( but you won’t usually have to do this ).
3
The solution, a, is
f ( x)  x  1  x
now where
f ( x)  0
a
At a, f ( x )  0
To the left of a, e.g. at x = 0, f ( x )  1  0
To the right of a, e.g. at x = 1, f ( x )  1  0
Iteration
Rearrange the equation to get zero on one side.
e.g. For x  1  x 3 , get x 3  1  x  0
 Call this
f ( x)  0 
To show how the method works I’m going to sketch
y  f ( x ) ( but you won’t usually have to do this ).
f ( x)  x  1 
3
a
x
f ( x ) has opposite
signs on the left
and right of a.
To the left of a, e.g. at x = 0, f ( x )  1  0
To the right of a, e.g. at x = 1, f ( x )  1  0
Iteration
The Algebraic Method:
 If we want to show that 0 and 1 are integer
bounds, we show that f ( x ) has different signs
at 0 and 1.
• Rearrange the equation to the form f ( x )  0
x  1 x  x 1 x  0
Define f ( x ): Let f ( x )  x 3  1  x
Find f ( 0) :
e.g.
•
•
3
3
Iteration
The Algebraic Method:
 If we want to show that 0 and 1 are integer
bounds, we show that f ( x ) has different signs
at 0 and 1.
• Rearrange the equation to the form f ( x )  0
x  1 x  x 1 x  0
Define f ( x ): Let f ( x )  x 3  1  x
Find f ( 0) : f (0 )  0 3  1  0  1
Change of sign
3
Find f ( 1 ) : f (1 )  1  1  1  1
e.g.
•
•
•
•
3
The change of sign 
3
Iteration
The Algebraic Method:
 If we want to show that 0 and 1 are integer
bounds, we show that f ( x ) has different signs
at 0 and 1.
• Rearrange the equation to the form f ( x )  0
x  1 x  x 1 x  0
Define f ( x ): Let f ( x )  x 3  1  x
Find f ( 0) : f (0 )  0 3  1  0  1
Change of sign
3
Find f ( 1 ) : f (1 )  1  1  1  1
e.g.
•
•
•
•
3
3
The change of sign  0  a  1
You must of
always
line.
Our 1st estimate
a is include
betweenthis
these
values, say 0  5
Iteration
It is possible to find bounds that are closer than
the nearest integers.
For example, to find bounds accurate to 1 decimal
place, we could use a decimal search.
So if we had 0  a  1 , a decimal search would
calculate
f ( 0  1 ), f ( 0  2 ), f ( 0  3 ) . . .
looking for a change of sign.
However, integer bounds are good enough for the
method of iteration we are studying.
Iteration
e.g. 1 (a) Using a graphical calculator, or
otherwise, sketch, on the same axes, the graphs of
3
y  x  2 and y  5 x
(b) From the sketch, find integer bounds for the
3
solution, a, of the equation x  2  5 x
(c) Use an algebraic method to confirm these are
correct and give a 1st approximate solution.
Solution:
y  5x
(a)
(b) a is the x-value
at the point of
3
intersection, so 0
yx 2
and 1 are integer
bounds.
a
Iteration
e.g. 1 (a) Using a graphical calculator, or
otherwise, sketch, on the same axes, the graphs of
3
y  x  2 and y  5 x
(b) From the sketch, find integer bounds for the
3
solution, a, of the equation x  2  5 x
(c) Use an algebraic method to confirm these are
correct and give a 1st approximate solution.
(c) ( Confirm bounds are 0 and 1 )
• Rearrange equation to f ( x )  0 : x 3  5 x  2  0
•
•
•
Define f ( x ) :
So,
f ( x)  x  5 x  2
f ( 0)   2  0
f (1)  1  5  2  2  0
The change of sign  0  a  1
3
A 1st approximation is any number between 0 and 1.
Iteration
Not all functions f ( x ) that have a sign change
between 2 numbers have a solution to f ( x )  0
between the numbers.
Look at this function:
f ( 0 )  2 ,
y  f ( x)
x
1
2
f (1)  2
There is a change of
sign . . . but no
solution between 0
and 1.
Do you notice
anything that
explains this?
Ans: The function has an asymptote between 0 and 1.
We couldn’t draw the curve without lifting the pencil
off the paper. We say it is discontinuous.
Iteration
Not all functions f ( x ) that have a sign change
between 2 numbers have a solution to f ( x )  0
between the numbers.
Look at this function:
f ( 0 )  2 ,
y  f ( x)
x
1
2
f (1)  2
There is a change of
sign . . . but no
solution between 0
and 1.
Do you notice
anything that
explains this?
You are unlikely to meet discontinuous functions in this
work so just remember the effect on solutions.
Iteration
Exercise
1. Using a graphical calculator or otherwise, sketch
suitable graphs to find integer bounds for the
solution to
x 1  e
2
x
.
Give a 1st approximation to the solution.
2. Use the algebraic method to show that
ln x  4  x
has a root between 2 and 3.
Give an approximation to this root.
An equation has a solution which may consist of one
or more roots.
Iteration
1. x 2  1  e  x
Solution:
Sketch y  x 2  1 and y  e  x
y  x 1
2
ye
x
a
The integer bounds for a are 1 and 2. So,
1a  2
Any number between 1 and 2 could be used as the
1st approximation.
Iteration
2. Use the algebraic method to show that
ln x  4  x
has a root between 2 and 3.
Solution:
• Rearrange to
•
ln x  4  x
f ( x)  0:
ln x  x  4  0
Define f ( x ) :
f ( x )  ln x  x  4
f ( 2)  ln 2  2  4   1  3
f ( 3)  ln 3  3  4   0  1
•
Change of sign (continuous function)  2  a  3
Any number between 2 and 3 could be used as the
1st approximation.
Iteration
The 1st approximate solution lies anywhere between
the bounds. The next stage is to improve this
estimate.
• Rearrange the equation to the form x  g( x ) .
You may spot lots of ways of doing this. e.g.
e.g. For the equation
3
x  1 x :
Iteration
The 1st approximate solution lies anywhere between
the bounds. The next stage is to improve this
estimate.
• Rearrange the equation to the form x  g( x ) .
You may spot lots of ways of doing this. e.g.
e.g. For the equation
(i) Square:
3
x  1 x :
3 2
3
x  1  x  x  (1  x )
or (ii) Rearrange:
x  1 x
Cube root:
3
 x  1
3

x

x  1
x
or (iii) Rearrange: x  1  x 3  x 3  1 
x
1
x
Divide by x :
2

x 
x
2

1
3
Iteration

Let’s take the 2nd arrangement: x  1 
x

1
3
Our 1st estimate of a we will call x0.
We
substitute
into the
of is
the
formula
and )
( Some
peoplex0start
withr.h.s.
x1 which
just
as good.
the result gives the new estimate x1.

We now have x1  1 
x0

1
3
We will then keep repeating the process so we write
the formula as
1
x n 1  1  x n 3


This is called an iterative formula.
to iterate means to repeat
Iteration
So,

x n 1  1 
xn

Starting with x 0  0  5

x1  1 
x0

1
3
1
3
we get

 x1  1 
05

1
3
 x1  0  664105 ( 6 d.p. )
Because we are going to repeat the calculation,
we use the ANS function on the calculator.
• Type 0  5 and press ENTER
• Type the r.h.s. of the equation, replacing x
with ANS, using the ANS button, giving 1  ANS
•
•

Press ENTER and you get 0  664105 ( 6 d.p. )
Pressing ENTER again replaces 0  5 with 0  664105
and gives the next estimate and so on.

1
3
We get
Iteration
x0  0  5
x1  0  664105
x 2  0  569878
Although I’ve only written down 6 decimal places, the
calculator is using the greatest possible accuracy.
If we continue to iterate we eventually get
a  0  605423 ( to 6 d.p. )
Error Bounds
Since the answer is correct to 6 decimal places, the
exact value of a must be within
6
of our answer.
 0  0000005 or  0  5  10
Tip: The index equals the number of d.ps. in the answer.
Iteration
SUMMARY
To find an approximation to a solution ( or root ) of
an equation:
 Find a 1st approximation, often by finding integer
bounds for the solution. Let this be x0 .
 Rearrange the equation into the form x  g ( x )
 Write the arrangement as an iterative formula:
x n1  g( x n )
 Key x0 into a calculator and ENTER.
 Key the r.h.s. of the formula into the calculator,
replacing x with ANS.
 Press ENTER as many times as required to get
the solution to the specified accuracy.
Iteration
e.g. 1(a) Show that the equation 2 x  x 3 has a root
a in the interval 1  3  a  1  4 .
(b) Using the arrangement x  3 2 x write down
an iterative formula and use it to find the
root correct to 4 decimal places.
Solution: (a) Let f ( x )  2 x  x 3  0
Then,
f (1  3)  2
f (1  4)  2
1.3
 1  3  0  27
1.4
 1  4  0  10
3
3
Change of sign  1  3  a  1  4
Iteration
e.g. 1(a) Show that the equation 2 x  x 3 has a root
a in the interval 1  a  2.
(b) Using the arrangement x  3 2 x write down
an iterative formula and use it to find the
root correct to 4 decimal places.
Solution: (b)
Let
x
3
2
gives
x
x 0  1  5  x1  2 0 
 1  414
3
x
x n1 
3
2
3
2
xn
15
x 2  1  3865
x 3  1  3776
It takes about 7 iterations to reach a  1 3735 (4 d.p.)
Iteration
Exercise
1. (a) Show that the equation x 3  x 2  25 has a
solution a between 2 and 3.
2
(b) Use the iterative formula x n1  3 25  x n
with x 0  2  5 to find the solution, giving
your answer correct to 4 d.p.
2. (a) Show that the equation ln x  2 x  3 has
a solution between 1 and 2.
(b) Use the iterative formula x n1  ln x n  x n  3
with x 0  1  5 to find the solution, giving your
answer correct to 4 d.p.
Iteration
Solutions
1. (a) Show that the equation x 3  x 2  25 has a
solution between 2 and 3.
Solution: (a) Let f ( x )  x 3  x 2  25  0
f ( 2)  2  2  25  13  0
3
2
f ( 3)  3  3  25  11  0
3
2
Change of sign  2  a  3
(b) Use the iterative formula x n1  3 25  x n
with x 0  2  5 to find the solution, giving
your answer correct to 4 d.p.
2
x 0  2  5, x1  2  6566 , . . . a  2  6258 ( 4 d.p. )
Iteration
Solutions
2. (a) Show that the equation ln x  2 x  3 has
a solution between 1 and 2.
Solution: Let f ( x )  ln x  2 x  3
f (1)  ln 1  2  3  1  0
f ( 2)  ln 2  4  3   0  3  0
Change of sign  1  α  2
(b) Use the iterative formula x n1  ln x n  x n  3
with x 0  1  5 to find the solution, giving your
answer correct to 4 d.p.
Solution: We need ln( ANS)  ANS  3
x 0  1  5, x1  1  9055 , . . . a  1  7915 ( 4 d.p. )
Iteration
Some arrangements of an equation give formulae
which do not give a solution.
We earlier met 3 arrangements of x  1  x 3
1
1 x
(i) x  (1  x 3 ) 2 (ii) x  1  x 3
(iii) x 
2
x
We used (ii) with x 0  0  5 to find the solution


a  0  605423 ( to 6 d.p. )
Now try (i) with x 0  0  5
We get x1  0  77 , x 2  0  30 , x 3  0  94 , . . .
and after a while the sequence just oscillates between
1 and 0.
This iterative sequence does not converge.
Iteration
Now try the formula x n1 
1
We get x1  1  17 , x 2  0  06 ,
xn
xn
2
with x 0  0  5 .
The iteration then fails because we are trying to
square root a negative number.
Some arrangements of an equation give an iterative
sequence which converges to a solution; others do
not converge.
The next presentation investigates convergence of
iterative sequences.
Iteration
Iteration
The following slides contain repeats of
information on earlier slides, shown without
colour, so that they can be printed and
photocopied.
For most purposes the slides can be printed
as “Handouts” with up to 6 slides per sheet.
Iteration
There are some equations that we can’t solve.
e.g.
x  1 x
3
However, we can find an approximate solution to some
of these equations.
The approximation can be very accurate, say to 6 or
more decimal places.
There are several methods of finding approximate
solutions and in this presentation we will study one of
them.
Iteration
There are 2 stages to getting a solution:
Stage 1. Find a 1st estimate
Stage 2. Find a formula to improve the estimate.
Sometimes we can just spot an approximate solution
to an equation.
The solution to
x  2x  1
3
is quite close to 0 as the l.h.s. is then 0 and the
r.h.s. is 1.
If we can’t quickly spot an approximation, we can use
a method involving finding bounds for the solution.
Iteration
We often start by finding numbers ( bounds ) that lie
on either side of the solution. If these are integers
we call them integer bounds.
e.g. To find integer bounds for x  1  x 3 we
can sketch y  x and y  1  x 3
y  1 x
3
y
a
x
The solution
lies between
0 and 1.
0 and 1 are
the integer
bounds.
We usually call the solution a, so 0  a  1 .
Our first approximation to a, is any number between
the bounds, say 0  5.
Iteration
The Algebraic Method:
 If we want to show that 0 and 1 are integer
bounds, we show that f ( x ) has different signs
at 0 and 1.
• Rearrange the equation to the form f ( x )  0
x  1 x  x 1 x  0
Define f ( x ): Let f ( x )  x 3  1  x
Find f ( 0) : f (0 )  0 3  1  0  1
Change of sign
Find f ( 1 ) : f (1 )  13  1  1  1
e.g.
•
•
•
•
3
3
The change of sign  0  a  1
Our 1st estimate of a is between these values, say 0  5
Iteration
e.g. 1 (a) Using a graphical calculator, or
otherwise, sketch, on the same axes, the graphs of
3
y  x  2 and y  5 x
(b) From the sketch, find integer bounds for the
3
solution, a, of the equation x  2  5 x
(c) Use an algebraic method to confirm these are
correct and give a 1st approximate solution.
Solution: (c) ( Confirm bounds are 0 and 1 )
• Rearrange equation to f ( x )  0 : x 3  5 x  2  0
•
•
•
Define f ( x ) :
So,
f ( x)  x  5 x  2
f ( 0)   2  0
f (1)  1  5  2  2  0
The change of sign  0  a  1
3
A 1st approximation is any number between 0 and 1.
Iteration
The 1st approximate solution lies anywhere between
the bounds. The next stage is to improve this
estimate.
• Rearrange the equation to the form x  g( x ) .
You may spot lots of ways of doing this. e.g.
e.g. For the equation
(i) Square:
x  1 x :
3 2
3
x  1  x  x  (1  x )
(ii) Rearrange:
x  1 x
3
3
Cube root:
(iii) Rearrange:
Divide by x 2:
 x  1
3

x  1 x
3
x

x 1
x
 x3  1 
x
1
x

x 
x
2

1
3
Iteration

Let’s take the 2nd arrangement: x  1 
x

1
3
Our 1st estimate of a we will call x0.
( Some people start with x1 which is just as good. )
We substitute x0 into the r.h.s. of the formula and
the result gives the new estimate x1.

We now have x1  1 
x0

1
3
We will then keep repeating the process so we write
the formula as
1
x n 1  1  x n 3


This is called an iterative formula.
to iterate means to repeat
Iteration
SUMMARY
To find an approximation to a solution ( or root ) of
an equation:
 Find a 1st approximation, often by finding integer
bounds for the solution. Let this be x0 .
 Rearrange the equation into the form x  g ( x )
 Write the arrangement as an iterative formula:
x n1  g( x n )
 Key x0 into a calculator and ENTER.
 Key the r.h.s. of the formula into the calculator,
replacing x with ANS.
 Press ENTER as many times as required to get
the solution to the specified accuracy.
Iteration
e.g. 1(a) Show that the equation 2 x  x 3 has a root
a in the interval 1  3  a  1  4 .
(b) Using the arrangement x  3 2 x write down
an iterative formula and use it to find the
root correct to 4 decimal places.
Solution: (a) Let
f ( x)  2  x  0
x
f (1  3)  2
f (1  4)  2
3
1.3
 1  3  0  27
1.4
 1  4  0  10
3
3
Change of sign  1  3  a  1  4
Iteration
Solution: (b)
Let
x
3
2
gives
x
x 0  1  5  x1  2 0 
 1  414
3
x
x n1 
3
2
3
2
xn
15
x 2  1  3865
x 3  1  3776
It takes about 7 iterations to reach a  1 3735 (4 d.p.)
Iteration
Some arrangements of an equation give formulae
which do not give a solution.
We earlier met 3 arrangements of x  1  x 3
x  1 x
(i) x  (1  x )
1
1 x
3
 x
 x  1 x
2
x
We used (ii) with x 0  0  5 to find the solution
3 2
(ii)
x  1
3

(iii)
x
3

a  0  605423 ( to 6 d.p. )
Trying (i) with x 0  0  5
gives x1  0  77 , x 2  0  30 , x 3  0  94 , . . .
and after a while the sequence just oscillates between
1 and 0.
The iterative sequence does not converge.
Iteration
Trying the arrangement
x
1
x
x
2
with x 0  0  5
gives x1  1  17 , x 2  0  06 ,
The iteration then fails because we are trying to
square root a negative number.
Some arrangements of an equation give an iterative
sequence which converges to a solution; others do
not converge.