I will start with the integer immediately below the root (0) and this will be the lower bound. I will find the values of f(x) for this and consecutive increments of 0.1 until a change of sign is found. Here is my table of values.
When looking at this table of values, no change of sign occurs. This means that I can’t continue with this method as I do not know which two numbers look between for the next stage. I cannot use this method to find this root with this equation. The reason that the decimal search method has failed for this equation is that there are two roots too close together. They must be within 0.1 of each other as the table of values has not found a change of sign. I will now show the two roots on the graph to see how close they are together.
This graph shows that the two roots are between 0.2 and 0.3, this is why the decimal search method has failed as there was no change of sign when using increments of 0.1.
Newton-Raphson Method
This method is a ‘Fixed Point Estimation Method’. This means that you find a single value as your estimate for the root, rather than an interval in which the root lies. This method is an iterative process which is generating a sequence of numbers by continuous repetition of the same formula. To begin the sequence we need a starting point, x, and this will be our first estimate of the root of the equation. Once we have the first estimate for a root of f(x) = 0, we draw the tangent to the curve at this point. Then the point at which the tangent cuts the x-axis gives the next approximation to the root. Then the process is repeated until the root is found.
The Newton-Raphson formula is written as:
To find the roots of an equation using this method, I need to differentiate the equation. I will then replace X with my estimate into the differentiated equation and the number outputted will be the place on the x-axis that the tangent is drawn. This number will then be inputted into the differentiated equation and the process will continue until the number put into the equation equals the number outputted.
I will now solve an equation using the Newton-Raphson method. The equation I will be using is y=x³-3x+0.5. I will find all roots, starting with this one.
f(x) = x³-3x+0.5
f’(x) = 3x2 -3
My first estimate will be -2.
This is the tangent that is
drawn when using this
method. It has found the first
root to be -1.81.
I will now use the same method to find the remaining two roots for this equation.
My first estimate will be 0.
This is the tangent that is
drawn when using this method.
It has found the 2nd root to be 0.1683
3rd Root – My first estimate will be 2.
This is the tangent that is drawn when using this method. The last number inputted was the same as the last number outputted which means that this is a root.
F(x) = x3 -3x+0.5 The change of sign here confirms
F(1.6415) = -0.00144 the accuracy of the root.
F(1.6425) = 0.00365
The root is 1.6425 (to 3dp)
Although I have successfully found all three roots using the Newton-Raphson method, sometimes this method fails to find the roots. I will now show an example of the Newton-Raphson method failing and find out why it fails. I will use the equation y=3x³-9x+2.
I will try to find either the 2nd root or the 3rd root using the Newton-Raphson method. My starting value will be 1 as it is near both roots so I expect to get one of them. When I use the method, a tangent gets drawn to the curve but then the gradient is 0 and the next tangent is a horizontal line. As this is the case, it can’t find the next root as the horizontal line continues forever and an overflow is created meaning that it will never reach the x-axis so it won’t create a tangent back to the curve.
This shows that an overflow is created as a tangent can’t be drawn back to the x-axis as the previous tangent is a horizontal line and therefore will never reach the x-axis, continuing forever and causing an overflow.
Graphical Convergence
The Graphical Convergence is, like Newton-Raphson, is a ‘Fixed Point’ estimation method as you chose a single value as your estimate for the root, rather than an interval in which the root lies. The Graphical Convergence method is an iterative process as it generates a sequence of numbers by continuous repetition of the rearranged formula. The formula is found by rearranging the starting equation that you wish to solve. The rearranged formula is plotted on a graph along with the line x=y. Where the curve and the line cross is the root of the original equation. The estimate at the start of the process will be used to draw a tangent from the x=y line to the curve and then continues drawing tangents until the root is found.
I will now solve an equation using the Graphical Convergence method. The equation I will be using is y=x³-4x+0.5. (shown below)
I will now rearrange my equation so I can use it as an iterative formula. The rearrangement is . From the graph below, you can see that the roots of the original equation (shown in red) are the same as where the formula and the line x=y cross.
I will now try and find the middle root. My starting estimate will be 0. The computer draws a tangent between the line y=x and y=(x³+0.5)/4. The first tangent is between the two lines at 1 that was the starting number that I chose. It then draws a horizontal line to the y=x line and then continues to draw vertical and horizontal lines until finding the root to the required level of accuracy. I will know when a root has been found as the number outputted from the formula will be the same as the last number inputted. Here is the table of results and the graph with the tangents.
This type of diagram is called a staircase diagram as the values of x approach the root from one side, in this case the right. From this graph and mainly using the table of iterates we can see that the root is at 0.1255. To confirm this, I will look for a change is sign.
F(x) = y=x3-4x+0.5
F(0.126) = -0.001996
F(0.125) = 0.001953
As a change of sign has happened, this confirms that there is a root at 0.1255. The reason why finding this root using the Graphical convergence method is that the gradient of the curve at the root is between 1 and -1. If it wasn’t, it would both increase and cause an overflow or to converge to the wrong root. As the gradient of the curve was between 1 and -1, this method is successful.
Although I have successfully found a root using the Graphical Convergence method, sometimes this method fails to find the roots. I will now show an example of the Graphical Convergence method failing and find out why it fails. I will use the same equation as the previous success but try to find either of the remaining two roots.
My estimate and starting value will be -2 as it is near the first root (shown on the graph)
Although I started at -2, the graph used the rearranged formula and converged to the second root which I already found previously. This could possibly a failure or it could just be that I started too close to the middle root. I will now try starting slightly further away from the middle root to see if I can get the graph to converge to the first root. My estimate and starting value will be -2.1.
This graph shows that when I used -2.1 as my starting point, the graph went in the other direction and missed the root, the number increased and caused an overflow. As it has failed to find the root with starting points -2 and -2.1 going in different directions each time, the Graphical Convergence method has failed to find this root. The actual reason that this method failed to find the first root is that the gradient of the curve near the root is greater than one. This means that no matter what starting point you chose, it will either increase and cause an overflow or converge to the wrong root. The gradient at a root must be between 1 and -1. If it isn’t, it will not find the correct root and fail.
Comparisons
To compare the three different methods of solving equations, I will use the same equation and root for all three to make it a fair test and to make it easy to make comparisons. The equation I will use will be the equation that I used for the Graphical Convergence method which is y=x³-4x+0.5
I will now find the 2nd root of the above equation using the Decimal Search method. I will start with increments of 0.1 between values 0 and 1. Here is my table of results.
From this I can see that the change of sign occurs between 0.1 and 0.2. I will now use increments of 0.01 between 0.1 and 0.2.
Here is my table of values. From this, I can see that the change of sign occurs between 0.12 and 0.13. I will now use increments of 0.001 between 0.12 and 0.13.
From this table I can see that the change of sign occurs between 0.125 and 0.126. As I only intend to find the root to 3 decimal places I don’t need to continue the method. To be certain that the root is between 0.125 and 0.126, I will calculate f(x) in each case to make sure that a change of sign occurs.
F(x) = y=x³-4x+0.5
F(0.125) = 0.0019531
F(0.126) = -0.0019996
As a change of sign has been found and confirmed here, this is where the root lies.
I will now find the same root using the Newton-Raphson method. My starting value (estimate) will be 0 to match my Graphical Convergence method..
This graph shows the tangents that have been drawn to find the root. Using the table of iterates we can see that the root is at 0.1255. To confirm this, I will look for a change is sign.
F(x) = y=x3-4x+0.5
F(0.126) = -0.001996
F(0.125) = 0.001953
As a change of sign has been found and confirmed here, this is where the root lies.
When using these three different methods I was able to use a computer program that helped me greatly in drawing the graphs and tangents and working out the iterates from the equations that I gave it. If I had not been able to use this program, there would only be one method that I would have been able to have used. The Decimal Search method was the easiest to understand and to produce and without any programs as it only needed some small calculations that were easy enough to do on a calculator in not much time and no tangents were needed to be drawn which would have taken a while without a program. Even if this method had needed the maximum number of calculations, it would have been significantly faster than the other two methods. Both the Newton-Raphson method and the Graphical Convergence method used difficult formulas and rearrangements. This would have taken a long time when finding out tangents and then putting the value that was outputted back into the equation, especially if it had many iterations.
The Decimal Search method had 14 iterations, whereas Newton-Raphson and Graphical Convergence only had 4 but without a computer they all would have taken similar time to work out. In general, I think that the Decimal Search method would be faster as Newton-Raphson and Graphical Convergence methods usually have more iterations that they did have with the previous equation. So I think Decimal Search is the best method to use when a computer program is not available due to the number of calculations that are needed and the difficulty of them.
When using a computer program, I think that the best method is Newton-Raphson. This is because you do not need to rearrange any equations yourself as the program will do it all for you. The only thing you need to do is to enter a starting value and the program will draw the tangents and give you a final root to the required accuracy. No calculations are needed so this proves a very fast method. The Graphical Convergence method is also quicker when using a computer as it also draws all your tangents and gives you the overall root. The reason that I think Newton-Raphson is better is that for Graphical Convergence you need to rearrange your own equation which can take some time if it is a difficult one. You then need to draw three equations onto a graph whereas Newton-Raphson only requires one curve on the graph. The Decimal Search method is speeded up when using a computer but it doesn’t have that much of an impact compared to the other two methods as only the calculations are done for you and these can be done with ease anyway.
Overall I think that the best method to use is Newton-Raphson as it rarely fails and this is mainly due to a poor starting value. It is very fast when using a computer and it is more reliable than Graphical convergence. Although Graphical Convergence can converge rapidly to a high degree of accuracy, it has a high failure rare and extra calculations are needed to find the error bounds. If a computer is available, you should use the Newton-Raphson method and if not the Decimal Search should be used.