Newton-Raphson Method
I am going to solve the equation using the Newton-Raphson method.
Here is a graph of the function:
It has three roots that lie within the integer bounds [-1,0], [1,2] and [2,3]. I will solve the root between [2, 3]
This method begins with a line being drawn up from the highest integer bound of the root (in this case it will be 3) from the x-axis, this x-value is called x0. At the point where this line hits the curve, a tangent to the curve is drawn until it hits the x-axis. The point of interception is the first iterative value (x1). Another line is drawn up from x1 until it hits the curve, and the method is repeated. This is continued until the x value repeats (in this case I will be looking for a repeat to 10 d.p).
This is an iterative process; it uses the iterative formula:
e.g.
(starting value)
(accuracy given by scientific calculator)
(accuracy given by scientific calculator)
The method continues.
Therefore the root is 2.53209 to 5 d.p
I will now work out the error bounds by finding the y values for the root and for the x-values either side of it so I can look for the change of sign and have a better idea where the root lies
The change of sign is highlighted in the table; the root must lie between [2.53209, 2.53208], these are my error bounds.
The root between [1,2]:
So the root is 1.34730 to 5 d.p
The root between [-1,0]:
So the root to 5 d.p would be -0.87939.
Failure of Newton-Rhapson Method:
This method may fail if it is used with a curve with some portions that are close to horizontal, as this will mean that the tangents drawn will take a long time to cross the x-axis and find the root.
I will attempt to solve the equation
Here is a graph of the function
There are roots between the integer bounds [-1,0] and [1,2]. I will try to find the root between [-1,0].
Here is the table of iterative values where x0 =1 (accurate to 10 s.f)
The 6th iterative value is not calculated, as it is so far away from the previous iterative value it is obvious that the values are not converging towards the root, but diverging away from it. So the method has failed.
Rearrangement Method
I am going to solve the equation
Here is a graph of the function
As shown by the graph, the roots lie between the integer values [-1,0], [0,1] and [1,2].
In this method, roots are solved by rearranging the equation so that it is in the form, this function is called. This is then drawn on the graph along with the line. At the points of intersection between y=x and y=g(x), the value ofis the same as the-value of the root.
So the function I draw is
As shown by the graph the points of intersection have the same- values as the roots.
It is solved by using the following iterative formula
The start value is on the, a line is drawn vertically from this toand then back toto give an -value
I shall attempt to solve the root that lies between the integer bounds [0,1].
This is also an iterative method; so it can also be found by using the iterative formula
e.g.
The method continues – as shown on this graph – and the line gets closer to the root.
So the root to 5 d.p. is 0.35542
In this case the method works; this is affected by the gradient of , whereis the root. So for it to not be a failure case the rule is: .
This graph shows that the line has a gradient that is above 0 as it is not horizontal. It also has a gradient that is smaller than that of the line which has a gradient of -1. So in this case gradient of g(x) follows the rule which means the method will work.
Failure of Rearrangement Method
There are many case where the rearrangement will fail; at any time where the gradient of is not between 1 and -1.
I will show this by attempting to find the root that lies between [-1,0] of the equation (for which the function is ) used above with the same rearrangement.
My start value will be -1. Again, a line is drawn from to, but this time the line is drawn downwards, away from the root I am trying to find.
After only four readings the iterative value (and the gap between the iterative values) has gotten so big that there is no point in continuing. This is a failure case.
As is clearly visible on the graph, the curve has a larger gradient than which has gradient of 1, so, so the method will not work.
Comparison Of Methods
I am going to use all three methods to find the same root of an equation. I will use the curve which was used for the rearrangement method above. I solved the root between [0,1] (using 0 as the start value).
My table for rearrangement can be seen above; I found the root to be 0.35542 to 5 d.p.
Using the Newton-Raphson method, my table of iterative values (using 0 as the start value) is:
So the root to 5 d.p. would be 0.35542
I will now find the root using decimal search, starting between the integer bounds [0,1].
The change of sign is highlighted, so I shall search between [0.3, 0.4].
I will now find the midpoint value so I know which of the bounds the root is closer to.
The change of sign is between [0.355415, 0.355415], so the root to 5 d.p. is 0.35542.
All of my methods give the same root (x=0.35542 to 5 d.p). The rearrangement took 29 iterations (or calculations) to 5 d.p, the Newton-Raphson took 4 iterations (or calculations) until it settled to 5 d.p, and the decimal search took 25 calculations to find the root to 5 d.p.
The rearrangement and decimal search took the longest (i.e. took the greatest number of iterations), and Newton-Raphson was by far the fastest (and it does not fail as much as rearrangement). In rearrangement when the gradient of the curve g(x) is closer to 0, the difference in gradient between g(x) and y=x (or a line with the gradient -1) is greater, so the distance between the two graphs will also be greater, and the speed the speed of convergence will be faster as less steps will be needed to reach the root. With Newton-Raphson (which uses a tangent of the curve), if the gradient of the curve does not vary as much, then the speed of convergence will be greater as it will stay closer to the tangent.
I calculated all of these roots using the computer program Autograph 3, which obviously made all methods much easier and faster as I did not have to work out each individual value myself. However, it is also possible to use these methods with only a calculator. I have shown above how to find Newton-Raphson and rearrangement using their iterative formulas, this would take much longer and mistakes are more likely (especially as they are iterative values so one mistake or rounding too much could affect all the rest). Decimal search by hand would simply be putting x-values into the formula, so the tables produced would be exactly the same as those above (these tables can also be immediately produced by graphical calculators); the further down the tables the changes of sign are, the longer the method will take; this method by hand is fairly accurate, as the values do not rely on each other and rounding does not affect the results (as you just need to look for whether the value is positive or negative). Decimal search is the most reliable to do by hand as you will find out immediately if it will fail and mistakes are immediately apparent (the next table will not have a change of sign in it), whereas rearrangement or Newton-Raphson may take many iterations before you realise it is diverging, overflowing or moving towards the wrong root. If using Newton Raphson, I would have to differentiate the function myself. Also, without Autograph, I would just have to start with an equation and would have no graph to look at; so I would not know how many roots there were or where the start values were (this would mean it would take up much more time); when using rearrangement I would not be able to see the gradient of g(x) so I would have no idea if the roots would fail, and I could waste a lot of time.
