Web Lesson 33: Iteration

Iteration

Iteration in an ‘indirect method’ of solving an equation

That means it does not give an exact answer, but it can be used to give an approximate answer to an equation

The level of accuracy is determined by how many iterative steps are used

To use iteration to solve an equation:

You need an iteration algorithm (i.e. an equation with ‘x_n+1’ on the left hand side, given in terms of ‘x_n’)
You need a starting point (called x₀)
You need to refine your answer (this means finding: x₁, x₂, x₃ etc.)
You need to know when to stop iterating (i.e. what level of accuracy you require your answer to).

e.g. In order to solve x³ + 5x – 10 = 0, use the algorithm:

 			x_n+1 =	  10    .
				x_n² + 5

starting with x₀ = 1 to work out x₁, x₂, x₃, x₄ & x₅

If we put ‘n=0’ into the algorithm, we get:

x₁  =	   10   
	x₀² + 5		
 
And, since we know x₀ = 1:  
 
x₁  =	   10   	=	   10   	=	1.66666666 (from calc.)
	x₀² + 5			(1)² + 5
	│			│
	└ ------- x₀ = 1 ------	┘

Next, we put ‘n=1’ into the algorithm, we get:

x₂  =	   10   	=	      10     	=	1.285714286 (from calc.)
	x₁² + 5			(1.66..)² + 5
	│			│
	└ --- x₁ = 1.66.. -----	┘

Next we put n = 2:

x₃  =	   10   	=	      10     	=	1.503067485 (from calc.)
	x₂² + 5			(1.28..)² + 5
	│			│
	└ --- x₂ = 1.28.. -----	┘

Then n = 3:

x₄  =	   10   	=	      10     	=	1.377560015 (from calc.)
	x₃² + 5			(1.50..)² + 5
	│			│
	└ --- x₃ = 1.50.. -----	┘

And, finally, n = 4:

x₅  =	   10   	=	      10     	=	1.449764586 (from calc.)
	x₄² + 5			(1.37..)² + 5
	│			│
	└ --- x₄ = 1.37.. -----	┘

Now, if I tell you that one solution of the equation x³ + 5x – 10 = 0 is x = 1.423318345, then you can see that our answers have been getting closer to this solution. We say that our iterations will "converge" towards this answer (although it will take a few more iterations (repeats) to get there...)

Question 1: Starting with x₀ = 4 and using the algorithm:

			x_n+1 = √(25 - ln x_n)

Find x₁, x₂, x₃, x₄ and x₅

Clue:
 
n=0:			x₁  = √(25 - ln x₀)	= √(25 - ln 4)		=  4.859393546  (from calc.)
 
n=1:			x₂  = √(25 - ln x₁)	= √(25 - ln 4.859...)	=  ......       (from calc.)
 
n=2:			x₃  = √(25 - ln x₂)	= √(25 - ln ......)	=  ......       (from calc.)
 
n=3:			x₄ = ....
 
n=4:			x₅ = 4.83974....
 
Notice that this series converges a lot quicker than the example above
(i.e. the answers are a lot closer together)

Question 2: Starting with x₀ = 2 and using the algorithm:

			x_n+1 = ³√(14 - x_n²)

Find x₁, x₂, x₃, x₄ and x₅

Clue:
 
n=0:			x₁ = ³√(14 - x₀²)	= ³√(14 - 2²)		= 2.15443469  (from calc.)
 
n=1:			x₂ = ³√(14 - x₁²)	= ³√(14 - 2.154...²)	= ....        (from calc.)
 
Etc...

Finding an Algorithm

Like the ones above, most questions will give you algorithm; so this whole stage can be skipped...

But, if the algorithm isn't given, then there are usually four different algorithms that can be produced to solve the equation.

In an exam question, you will be told which one they want you to produce, but here I will show you how to produce all four...

To illustrate to this process, I will try to find four different algorithms to solve: x³ + 5x – 10 = 0:

Pick any one of the ‘x’s in the equation and make that the subject of the equation
(it does not matter that the other ‘x’s are left on the other side)

So, if I pick the ‘x’ next to the ‘5x’: x³ + 5x – 10 = 0
 
(add ‘10’): 				x³ + 5x = 10
 
(subtract ‘x³’):			     5x = 10 – x³
 
(divide by ‘5’):		 	      x = 10 – x³
					             5

Add a subscript of ‘n+1’ to the ‘x’ that is now the subject (so it becomes: x_n+1)
Add a subscript of ‘n’ to the ‘x’s on the other side of the equation (so they become: x_n)
```
					     x = 10 – x³
					            5

So, we get: 				   x_n+1 = 10 – x_n³
					            5    .
 
```

Of course, I had a choice of which x to make the subject...
If I had chosen a different ‘x’ I’d have a different algorithm

If I had chosen the x in the ‘x³’:	x³ + 5x =   10
 
(subtracting ‘5x’):			x³      =   10 – 5x

(cube-rooting):				x       = ³√10 - 5x

(add the subscripts):			x_n+1    = ³√10 - 5x_n

A way of getting two more algorithms is to:

Collect all of the x’s to one side:
```
x³ + 5x = 10
 
```
Factorise:
```
x(x² + 5) = 10
 
```

Make one of these x’s the subject:

Making this x the subject: x(x²+5)=10	  │	Making this x the subject: x(x²+5)=10
					  │
	x(x² + 5) =     10		  │		x(x² + 5) = 10
        ÷(x²+5)     ÷(x²+5)		  │		÷x          ÷x
	-------------------		  │		------------------
	x         =     10  .		  │		  x² + 5  = 10
	              x² + 5		  │		             x
 					  │		      -5         - 5
	x_n+1      =     10   .		  │		-----------------------
	             x_n² + 5		  │		  x²      = 10/x - 5
					  │		  √         √
					  │		-----------------------
					  │		  x       = √(10/x - 5)
					  │
					  │		  x_n+1     = √(10/x_n - 5)

Question 3: Find 4 different algorithms for solving: x³ - 2x - 5 = 0

Clue:
 
1st algorithm: Make this x the subject:		 x³ - 2x - 5 =    0
						 x³          =    2x + ..
						 x           = ³√(2x + ..)
 
Add subscripts:					 x_n+1        = ³ √(2x_n + ..)	. . . . . . alg (1)
 
2nd Algorithm: Make this x the subject:		 x³ - 2x - 5 = 0
						 x³      - 5 = 2x
						 ½(x³ - ..)   = x
 
Add subscripts:					 ½(x_n³ - ..)  = x_n+1  		. . . . . . alg (2)
 
Now, to get any more algorithms, we must first: Collect the x terms to one side and factorise:
						 x³ - 2x     = 5
						 x(x² - 2)   = 5
 
3rd Algorithm: Make this x the subject:		 x(x² - 2)   = 5
						 x           =     5    
						                x² - ..
 
Add subscripts:					 x_n+1        =      5    	. . . . . . alg (3)
						                x_n² - ..
 
4th Algorithm: Make this x the subject: 	 x(x² - 2)   = 5
						   x² - 2    = 5/x
						   x²        = ......
						   x         = √(......)
 
Add subscripts:					   x_n+1      = √(......)  	. . . . . . alg (4)

Note: Exam questions often give us the algorithm and ask us to show that it is correct. This very easy:

Remove the subscripts
Show that this re-arranges to the equation we want to solve

e.g. Show that x_n+1 = √(x_n + 6/x_n) is an algorithm to solve: x³ - x² - 6 = 0

Clue: (remove subscripts): 		          x = √x + 6/x 
 
(re-arrange: square): 			         x² = x + 6/x
 
(re-arrange: multiply by x): 		         x³ = x² + 6
 
(re-arrange: move terms): 		x³ - x² - 6 = 0

Question 4: Show that x_n+1 = 4e^-x_n is an algorithm to solve: xe^x = 4

Clue: (remove subscripts): 			  x = 4e^-x
 
(re-arrange: multiply by e^x): 			... = ..

Question 5: Show that x_n+1 = ³√(14 - x_n²) is an algorithm to solve x³ + x² - 14 = 0

Finding a Starting Point: Called: x₀

Most questions will give you a starting point. i.e. "find the solution near x=1" means that x₀ = 1
However, if no starting point is given, then either one of these methods can be used to find one:
1. Finding a value of x that, when put into the equation, almost makes both sides equal. Call this value, ‘x₀’
2. Use the graphical solutions method (very rough sketch graphs will do) to find an approximate solution. Call this, ‘x₀’
Sometimes a slightly different starting point will make an algorithm work

Refining your Estimate

Now that we have a starting point, we can use the algorithm to improve our estimate:

The algorithm works like this: When we put x₀ (starting guess) into it, the answer is called x₁ (1st improvement)

And then, when we put x₁ back into the algorithm, the answer is called x₂ (2nd improvement)

Etc...

Going back to the first example we did (at the start of this web lesson)

e.g. In order to solve x³ + 5x – 10 = 0, use the algorithm:

 			x_n+1 =	  10    .
				x_n² + 5

starting with x₀ = 1 to work out x₁, x₂, x₃, x₄ & x₅

If we put ‘n=0’ into the algorithm, we get:

x₁  =	   10   	=	   10   	=	1.66666666 (from calc.)
	x₀² + 5			(1)² + 5
	│			│
	└ ------- x₀ = 1 ------	┘

Next, we put ‘n=1’ into the algorithm, we get:

x₂  =	   10   	=	      10     	=	1.285714286 (from calc.)
	x₁² + 5			(1.66..)² + 5
	│			│
	└ --- x₁ = 1.66.. -----	┘

Next we put n = 2:

x₃  =	   10   	=	      10     	=	1.503067485 (from calc.)
	x₂² + 5			(1.28..)² + 5
	│			│
	└ --- x₂ = 1.28.. -----	┘

Then n = 3:

x₄  =	   10   	=	      10     	=	1.377560015 (from calc.)
	x₃² + 5			(1.50..)² + 5
	│			│
	└ --- x₃ = 1.50.. -----	┘

And, finally, n = 4:

x₅  =	   10   	=	      10     	=	1.449764586 (from calc.)
	x₄² + 5			(1.37..)² + 5
	│			│
	└ --- x₄ = 1.37.. -----	┘

Knowing when to Stop

If we require an answer to 2.d.p, then:

As we work out x₁, x₂, x₃ ..., we write a table of the exact values as well as giving them to 2 d.p.
So, for the example above:

x_n	Exact Value	2 d.p.
x₁	1.66666666	1.67
x₂	1.285714286	1.29
x₃	1.503067485	1.50
x₄	1.377560015	1.38
x₅	1.449764586	1.45

You can stop iterating when the answer in the ‘2 d.p.’ column repeats.
So, for the example above, if we carry on with the iterations:

x_n	Exact Value	2 d.p.
x₁	1.66666666	1.67
x₂	1.285714286	1.29
x₃	1.503067485	1.50
x₄	1.377560015	1.38
x₅	1.449764586	1.45
x₆	1.408090282	1.41
x₇	1.432107047	1.43
x₈	1.418252508	1.42
x₉	1.426240508	1.43
x₁₀	1.421633454	1.42
x₁₁	1.424290078	1.42

So, a solution to x³ - 5x + 10 = 0 is: "x = 1.42 (2.d.p.)"

Question 6: Show that x_n+1 = ³√6 + x_n² is an algorithm for solving x³ - x² - 6 = 0
Given that a root exists near x=2, find this root giving your answer to 2 d.p.

Clue: Since we are given the algorithm [x_n+1 = ³√6  + x_n²] for the equation, we can work backwards:
 
(remove the subscripts): 		          x = ³√6 + x²
 
(re-arrange: cube): 			          x³ = .. + ..
 
(re-arrange: swap terms): 		x³ - .. - .. = 0
 
So, now we can use the algorithm, starting with x₀ = 2
 
Putting '2' into the equation:				x₁ = ³√6 + 2² 		= 2.15443469
Putting '2.1544...' into the equation:			x₂ = ³√6 + 2.1544...² 	= 2.199558371
Putting '2.1995...' into the equation:			x₃ = ³√6 + 2.1999...² 	= ...........
Etc....

x_n	Exact Value	2 d.p.
x₁	2.15443469	2.15
x₂	2.199558371	2.20
x₃	2.213012213	2.21
x₄	2.17045488	...
x₅	...	...
x₆	...	...
x₇	...	...

 
 
So, the answer is ...... (2.d.p)

Question 7: An algorithm to solve x⁴ - 5x - 5 = 0 is of the form: x_n+1 = ⁴√B + Ax_n
Find the values of 'A' and 'B'
Given that a root exists near x=2, find the root to 4.d.p.

Clue: Let's just try and find a few algorithms in the normal way and then see if any look like
      the one they want:
 
So, lets make this x the subject: x⁴ - 5x - 5 = 0 ....
[Does the answer look like theirs? Yes! Then what are 'A' and 'B']
 
Now lets start with x₀ = 2
Putting x₀=2 into the algorithm:			x₁ = ⁴√5 + 5(2)  	=  1.96798671
Putting x₁=1.96... back into the algorithm:	x₂ = ⁴√5 + 5(1.96...) 	=  1.962718868
And tabulating our results as we carry on:

x_n	Exact Value	4 d.p.
x₁	1.96798671	1.9680
x₂	1.962718868	1.9627
x₃	...	1.9618
x₄	...	...
x₅	...	...

 
 
So, the answer is 1.961- (4.d.p)

Question 8: An algorithm to solve e^x - 3x = 0 is of the form x_n+1 = ln (Ax_n)
Find 'A'
Sketch the graph of y = e^x and y = 3x on the same grid and find the integer value of x near where they intersect. Using this as your starting value for the iteration, solve the equation e^x - 3x = 0 giving your answer to 2 d.p.

Clue: Make this x the subject: e^x - 3x = 0
 
You should have no problems sketching the graphs and seeing that they meet near x=2
 
Starting with x₀ = 2				x₁ = ln (3×2) 		= 1.7917...
						x₂ = ln (3×1.7917)	= ...
Tabulating the answers as you go...

Question 9: Show that: x_n+1 = 1/(x_n²+2) and x_n+1 = √(1/x_n - 2) are both algorithms for: x³ + 2x - 1 = 0
Starting with x₀ = 0.4, show that one of these algorithms converges to a root whereas the other does not.
Give this root to 3.d.p.

Clue: It is easy to show that: x_n+1 = 1/(x_n²+2) is an algorithm:
(remove subscripts): 				          x = 1/(x²+2) 
(re-arrange: multiply by 'x²+2'): 		 ......     = 1
(re-arrange: expand):				.. + ..     = 1
(re-arrange: shift terms): 			.. + .. - 1 = 0
 
It is similarly easy to show x_n+1 = √(1/x_n - 2) is an algorithm...
 
Using the first algorithm and starting with x₀ = 0.4:
x₁ = 0.462962963
x₂ = 0.451602911
x₃ = ...
 
Using the second algorithm and starting with x₀ = 0.4
x₁ = 0.707
x₂ = ERROR
 
So the second algorithm does not converge!

Note: This is often the case with iteration. One algorithm may converge towards the root, but another may not!

Question 10: Find an algorithm to find the root of x³ - 2x - 5 = 0 Try using your algorithm to find the root of the equation near x=2 If your algorithm doesn't converge to give an answer to 3 d.p. within 10 iterations, then find a different algorithm and try that...

Web Lesson 33: Iteration

Iteration

Iteration in an ‘indirect method’ of solving an equation

That means it does not give an exact answer, but it can be used to give an approximate answer to an equation

The level of accuracy is determined by how many iterative steps are used

To use iteration to solve an equation:

You need an iteration algorithm (i.e. an equation with ‘xn+1’ on the left hand side, given in terms of ‘xn’)

You need a starting point (called x0)

You need to refine your answer (this means finding: x1, x2, x3 etc.)

You need to know when to stop iterating (i.e. what level of accuracy you require your answer to).

e.g. In order to solve x³ + 5x – 10 = 0, use the algorithm:

starting with x0 = 1 to work out x1, x2, x3, x4 & x5

If we put ‘n=0’ into the algorithm, we get:

Next, we put ‘n=1’ into the algorithm, we get:

Next we put n = 2:

Then n = 3:

And, finally, n = 4:

Question 1: Starting with x0 = 4 and using the algorithm:

Find x1, x2, x3, x4 and x5

Question 2: Starting with x0 = 2 and using the algorithm:

Find x1, x2, x3, x4 and x5

Finding an Algorithm

Like the ones above, most questions will give you algorithm; so this whole stage can be skipped...

But, if the algorithm isn't given, then there are usually four different algorithms that can be produced to solve the equation.

In an exam question, you will be told which one they want you to produce, but here I will show you how to produce all four...

To illustrate to this process, I will try to find four different algorithms to solve: x³ + 5x – 10 = 0:

Pick any one of the ‘x’s in the equation and make that the subject of the equation (it does not matter that the other ‘x’s are left on the other side)

Add a subscript of ‘n+1’ to the ‘x’ that is now the subject (so it becomes: xn+1) Add a subscript of ‘n’ to the ‘x’s on the other side of the equation (so they become: xn)

Of course, I had a choice of which x to make the subject... If I had chosen a different ‘x’ I’d have a different algorithm

A way of getting two more algorithms is to:

Collect all of the x’s to one side:

Factorise:

Make one of these x’s the subject:

Question 3: Find 4 different algorithms for solving: x³ - 2x - 5 = 0

Note: Exam questions often give us the algorithm and ask us to show that it is correct. This very easy:

Remove the subscripts

Show that this re-arranges to the equation we want to solve

e.g. Show that xn+1 = √(xn + 6/xn) is an algorithm to solve: x³ - x² - 6 = 0

Question 4: Show that xn+1 = 4e-xn is an algorithm to solve: xex = 4

Question 5: Show that xn+1 = ³√(14 - xn²) is an algorithm to solve x³ + x² - 14 = 0

Finding a Starting Point: Called: x0

Most questions will give you a starting point. i.e. "find the solution near x=1" means that x0 = 1

However, if no starting point is given, then either one of these methods can be used to find one:

Finding a value of x that, when put into the equation, almost makes both sides equal. Call this value, ‘x0’

Use the graphical solutions method (very rough sketch graphs will do) to find an approximate solution. Call this, ‘x0’

Sometimes a slightly different starting point will make an algorithm work

Refining your Estimate

Now that we have a starting point, we can use the algorithm to improve our estimate:

The algorithm works like this: When we put x0 (starting guess) into it, the answer is called x1 (1st improvement)

And then, when we put x1 back into the algorithm, the answer is called x2 (2nd improvement)

Etc...

Going back to the first example we did (at the start of this web lesson)

e.g. In order to solve x³ + 5x – 10 = 0, use the algorithm:

starting with x0 = 1 to work out x1, x2, x3, x4 & x5

If we put ‘n=0’ into the algorithm, we get:

Next, we put ‘n=1’ into the algorithm, we get:

Next we put n = 2:

Then n = 3:

And, finally, n = 4:

Knowing when to Stop

If we require an answer to 2.d.p, then:

As we work out x1, x2, x3 ..., we write a table of the exact values as well as giving them to 2 d.p. So, for the example above:

You can stop iterating when the answer in the ‘2 d.p.’ column repeats. So, for the example above, if we carry on with the iterations:

So, a solution to x³ - 5x + 10 = 0 is: "x = 1.42 (2.d.p.)"

Question 6: Show that xn+1 = ³√6 + xn² is an algorithm for solving x³ - x² - 6 = 0 Given that a root exists near x=2, find this root giving your answer to 2 d.p.

Question 7: An algorithm to solve x4 - 5x - 5 = 0 is of the form: xn+1 = 4√B + Axn Find the values of 'A' and 'B' Given that a root exists near x=2, find the root to 4.d.p.

Question 9: Show that: xn+1 = 1/(xn²+2) and xn+1 = √(1/xn - 2) are both algorithms for: x³ + 2x - 1 = 0 Starting with x0 = 0.4, show that one of these algorithms converges to a root whereas the other does not. Give this root to 3.d.p.

Note: This is often the case with iteration. One algorithm may converge towards the root, but another may not!

Question 10: Find an algorithm to find the root of x³ - 2x - 5 = 0 Try using your algorithm to find the root of the equation near x=2 If your algorithm doesn't converge to give an answer to 3 d.p. within 10 iterations, then find a different algorithm and try that...

Hand in your answers next lesson

You need an iteration algorithm (i.e. an equation with ‘x_n+1’ on the left hand side, given in terms of ‘x_n’)

You need a starting point (called x₀)

You need to refine your answer (this means finding: x₁, x₂, x₃ etc.)

starting with x₀ = 1 to work out x₁, x₂, x₃, x₄ & x₅

Question 1: Starting with x₀ = 4 and using the algorithm:

Find x₁, x₂, x₃, x₄ and x₅

Question 2: Starting with x₀ = 2 and using the algorithm:

Find x₁, x₂, x₃, x₄ and x₅

Pick any one of the ‘x’s in the equation and make that the subject of the equation
(it does not matter that the other ‘x’s are left on the other side)

Add a subscript of ‘n+1’ to the ‘x’ that is now the subject (so it becomes: x_n+1)
Add a subscript of ‘n’ to the ‘x’s on the other side of the equation (so they become: x_n)

Of course, I had a choice of which x to make the subject...
If I had chosen a different ‘x’ I’d have a different algorithm

e.g. Show that x_n+1 = √(x_n + 6/x_n) is an algorithm to solve: x³ - x² - 6 = 0

Question 4: Show that x_n+1 = 4e^-x_n is an algorithm to solve: xe^x = 4

Question 5: Show that x_n+1 = ³√(14 - x_n²) is an algorithm to solve x³ + x² - 14 = 0

Finding a Starting Point: Called: x₀

Most questions will give you a starting point. i.e. "find the solution near x=1" means that x₀ = 1

Finding a value of x that, when put into the equation, almost makes both sides equal. Call this value, ‘x₀’

Use the graphical solutions method (very rough sketch graphs will do) to find an approximate solution. Call this, ‘x₀’

The algorithm works like this: When we put x₀ (starting guess) into it, the answer is called x₁ (1st improvement)

And then, when we put x₁ back into the algorithm, the answer is called x₂ (2nd improvement)

starting with x₀ = 1 to work out x₁, x₂, x₃, x₄ & x₅

As we work out x₁, x₂, x₃ ..., we write a table of the exact values as well as giving them to 2 d.p.
So, for the example above:

You can stop iterating when the answer in the ‘2 d.p.’ column repeats.
So, for the example above, if we carry on with the iterations:

Question 6: Show that x_n+1 = ³√6 + x_n² is an algorithm for solving x³ - x² - 6 = 0
Given that a root exists near x=2, find this root giving your answer to 2 d.p.

Question 7: An algorithm to solve x⁴ - 5x - 5 = 0 is of the form: x_n+1 = ⁴√B + Ax_n
Find the values of 'A' and 'B'
Given that a root exists near x=2, find the root to 4.d.p.

Question 9: Show that: x_n+1 = 1/(x_n²+2) and x_n+1 = √(1/x_n - 2) are both algorithms for: x³ + 2x - 1 = 0
Starting with x₀ = 0.4, show that one of these algorithms converges to a root whereas the other does not.
Give this root to 3.d.p.