Examining, analysing and comparing three different ways in which to find the roots to an equation.
Advanced Mathematics (C3) Coursework
Introduction:
For my investigation, I will be examining, analysing and comparing three different ways in which to find the roots to an equation. It will include the "Change of Sign Method", the "Newton-Raphson Method" and finally the method of rearranging "f(x) = 0" into the form "x = g(x)". I will be finding roots of equations using the methods, and hence compare the merits and flaws of the methods with each other. I will analyse which is the best in terms of factors such as a speed of convergence and ease of use with available software and hardware.
Change of Sign Method:
This method finds a root to an equation by looking at when values of f(x) change sign from positive to negative or vice versa. This works because when the value of f(x) changes its sign, it must have passed through the x axis, and thus the root is somewhere between the two values that changed. The technique of the method can be done in many ways such as by interval bisection or linear interpolation. However, I will be using the decimal search method.
With decimal search, you first draw the graph of the curve that is to be investigated, and look for where the curve passes through the x axis, as these points are where the roots are. But as you cannot guess exactly where the roots are, you take intervals: the two points surrounding where the curve passes through the x axis. These points are taken as whole numbers. The next step is then to investigate where exactly between this interval, the value of f(x) changes to positive, or negative. To do this you go one decimal point further between these values. For example if the root was between 3 and 4, you would now investigate every 0.1 value, such as 3.1, 3.2, 3.3 and so on.
To investigate these values you put them into the formula to receive a value of f(x), and you can thus see where the change of sign occurs. When this has been found, it will be again between two values, so again you adjust the decimal places by one, and you are now investigating to 2 decimal places, such as 3.22 and 3.23. You keep going further into more decimal places, in order to increase the accuracy of root. For my investigation I will be going to 3 decimal places.
To investigate this method I will be using this equation:
f(x) = x³-15x-11
I used Autograph in order to plot the graph, and this is shown on the following page.
As the graph shows, there are several roots. I have chosen to investigate the root in the interval of [4, 5]. I will then begin by using 1 decimal place, and I put the values back into the equation in order to get the values of f(x).
I calculated each of the f(x) values in order to see where the change in sign was, as shown in the results below:
4
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
5
-7.00
-3.58
0.09
4.01
8.18
2.63
7.34
22.32
27.59
33.15
39.00
As the graph and the table show, there is a change of sign between 4.1 and 4.2, and thus the new interval was [4.1, 4.2]. I then took this a stage further, and did the decimal search to 2 decimal places. The results were:
4.1
4.11
4.12
4.13
4.14
4.15
4.16
4.17
4.18
4.19
4.2
-3.58
-3.22
-2.87
-2.51
-2.14
-1.78
-1.41
-1.04
-0.67
-0.29
0.09
The result here was an interval between [4.19, 4.2], and so I then went further, to 3 decimal places.
4.19
4.191
4.192
4.193
4.194
4.195
4.196
4.197
4.198
4.199
4.2
-0.29
-0.25
-0.21
-0.18
-0.14
-0.10
-0.06
-0.03
0.01
0.05
0.09
Here the interval was between [4.197, 4.198] but in order to decide on a root with a 3 decimal place accuracy, I must go to 4 decimals and see towards which value the root lies closest to:
4.197
4.1971
4.1972
4.1973
4.1974
4.1975
4.1976
4.1977
4.1978
4.1979
4.198
-0.0256
-0.0219
-0.0181
-0.0143
-0.0105
-0.0067
-0.0029
0.0009
0.0046
0.0084
0.012
As this shows, the root lies between the interval [4.1976, 4.1977] and this means that the root is closer towards 4.198 than 4.197, and so the solution of the answer is:
4.198 to 3 decimal places with an error bound of + or - 0.005
Failure Case for Change of Sign Method:
...
This is a preview of the whole essay
4.197
4.1971
4.1972
4.1973
4.1974
4.1975
4.1976
4.1977
4.1978
4.1979
4.198
-0.0256
-0.0219
-0.0181
-0.0143
-0.0105
-0.0067
-0.0029
0.0009
0.0046
0.0084
0.012
As this shows, the root lies between the interval [4.1976, 4.1977] and this means that the root is closer towards 4.198 than 4.197, and so the solution of the answer is:
4.198 to 3 decimal places with an error bound of + or - 0.005
Failure Case for Change of Sign Method:
The change of sign method can fail in many circumstances for example when the curve touches the x axis, but does not cross it. There is still a root but the curve only touches the x axis, and thus as the change of sign method requires a change of sign in order to spot the root, this method cannot be used.
The equation I used was:
y=1/4x³+3x²
As the graph shows the curve does not touch the x axis. The table below shows how the method does not change sign when at the root, and thus by using this method alone, no estimations for roots can be made, as it never changes sign, and thus we do not know where the root is.
-2
-1
0
2
0
2.75
0
3.25
4
Rearranging "f(x) = 0" into the form "x = g(x)":
This method uses the "Iteration Process" in order to find the roots to an equation. Instead of finding the points where y = f(x) crosses the x axis, this method finds the points of intersection of the curve y = g(x) and the line y=x.
With the iteration process, you start off by rearranging the equation from the form f(x) = 0, to x = g(x). A rearrangement of the equation f(x) = 0 into the form x = g(x) will allow convergence to a root "a" of the equation, but only if the gradient of "a", g`(x), is between -1 and 1, otherwise the iteration will diverge away from the root.
The equation I have chosen is:
f(x) = x³-4x+1
This can be rearranged in an infinite number of ways, but I have chosen to use the following the iterative method:
And thus my rearranged equation is:
x= (x³+1)/4
Once rearranged, the next step is to plot the graph, in order to see where the roots lie. Plotted on top of the curve of y=g(x), is the line y=x, in order to find the points of intersection between the line and the curve. The graph is shown below:
From the graph I could see that there are 3 intersections of the curve with the line, and thus there are 3 roots to the equation. The next stage is to use the method of successive approximations, in order to find the root of the equation.
Successive approximation works by first selecting a rough estimate to where the root may be. This is known as a "fixed-point estimation". Once this has been done, the next step is to take this value and put it into the rearranged equation of g(x) = x. The resulting value is "x1". This is the first approximation of the root of the equation. In order to get closer to the actual root, more approximations need to be done, so the next step is to put the value of "x1" back into the equation, g(x) = x, in order to get "x2". Then the value of "x2" is put into the equation in order to get "x3" and so on. What is happening is that the approximations are getting closer and closer to the root, known as the interation process. The iteration process is complete when the following value coming out from the equation g(x) = x, is the same as that which was put in. This is when a root has been found. This happens seldom, and in most cases the process will keep going, but will get more and more accurate. In this case, the amount of decimal places must be decided, and then a rounded answer can be chosen.
On the graph on the previous page, there are 3 roots that can be found, and I will be investigating the root between the interval, [0, 1]. Thus to start the iteration process I will put the value of 0.5 into the equation, as it is roughly near that value.
This was the result:
When x = 0.5, "x1" = (0.5³ + 1)/4 = 0.28125
So with "x1", "x2" = (0.28125³ +1)/4 = 0.255561828613
And so I decided to go closer to the root, and investigate "x2" and so on until I reached the accuracy of 12 decimal places, which is what I want.
These were the results:
x1
0.281250000000
x2
0.255561828613
x3
0.254172803842
x4
0.254105133149
x5
0.254101855184
x6
0.254101696443
x7
0.254101688756
x8
0.254101688384
x9
0.254101688366
x10
0.254101688365
x11
0.254101688365
As shown, the values converge to a single point, 0.254101688365, which is the root to the degree of accuracy of 12 decimal places.
The convergence of these values is shown on the graph on the following page, which illustrates each of the approximations that were taken, showing how they got closer and closer to the root, and finally reached it:
The magnitude of g`(x) could be calculated by first finding g`(x) of the equation which was done by differentiation:
g`(x) = 3x/4
So with a starting point of 1, the gradient of the line at that point would be:
(3 x 1)/4 = 0.75
As the value was less than 1, but still higher than -1, the iteration converged towards the root, and didn't diverge.
Failure of Rearranging Method:
This method can fail when the gradient, g`(x), of "a" is above 1 or less than -1, as then the iteration does not converge towards the root, and instead diverges away from it.
This can be shown in the example below.
By taking the same equation, I rearranged it in a different way, giving the resulting equation:
x = x³ - 3x + 1
I then drew the graph to see where the roots were:
I then chose to try and investigate one of the roots. I picked the root at the interval, [1, 2] and chose the starting value of 2. The results of the iteration were as follows:
x1
2.0000000000
x2
3.097656250000
x3
7.680870190263
x4
13.534706794433
x5
365869.522500695000
x6
2243869989713700.000000000000
As the results showed, the iteration was not converging towards a root, but instead was diverging, and eventually the program failed as it was "overflowing". This happened as the gradient of "a" was larger than 1, and thus the iteration will not converge towards the root.
The actual value of g`(x) could be found by putting the starting value of 2 into the differentiation of the equation, which I worked out to be: g`(x) = 3x² - 3
I put 3 back into the equation and the result was 9, much larger than 1, and thus the convergence didn't work.
As the graph shows, the iterations are diverging away from the root, instead of converging towards. As can be seen also, the magnitude of the gradient at "a" is much larger than 1 at that point, and thus it diverges away from the root.
Newton-Raphson Method:
The Newton-Raphson method is also a "fixed-point estimation" as with the previous rearranging method. You again start with an estimate for a root of f(x) = 0, called "x1", but instead, you draw a tangent to the curve at that point, (x1, f(x1)). The point at which the tangent cuts the x axis gives the next approximation for the root, and as with the previous method, the process is repeated until it converges to the root, to the required degree of accuracy.
The Newton-Raphson method uses its own iteration formula:
The equation that I will investigate is:
f(x) = x³ - 7x + 5
To start with I drew the graph to see where the roots were located:
I saw that the roots were located between the intervals, [-3, -2], [0, 1] and [2, 3]. After finding this I had to start rearranging my equation to fit the Newton-Raphson iteration formula. To do this I had to find the differentiation of the equation, which resulted in:
f `(x) = 3x² - 7
I then put the equations back into the iteration formula, the new rearranged equation to use is:
x n+1 = x(3x² - 7) - (x³ - 7x + 5)
(3x² - 7)
However this can be simplified to:
x n+1 = 2x³ - 5
(3x² - 7)
So thus after finding the equation to use, I then set about investigating the roots. The first root I chose to investigate was between the interval [-3, -2]. To converge towards the root, I must put an estimate value, which I chose to be --4, into the interation formula that I simplified, and thus this will generate x1. Once x1 has been found, I will repeat the process but insert the value of x1, in order to get x2. This is similar to the previous Rearranging method that I investigated, and equally for this I will stop the iteration once the root has been found to the degree of accuracy that I want.
Here are the results for the iteration of the first root.
x1
-3.224000000000
x2
-2.978251357674
x3
-2.949221498471
x4
-2.948828429739
x5
-2.948828358122
x6
-2.948828358122
The iteration process worked, and the convergence was towards the value of "-2.948828358122".
I put the value back into the formula to get = 1.74438E-12
However, if I selected the next value, -2.948828358123, the result I got was -1.73408E-11. From what I learnt in the Change of Sign method, this meant the root was in the interval: [-2.948828358122, -2.948828358123].
Thus I investigated the mid value between the two, -2.9488283581225, and put it back into the original equation to get the result: -7.80176E-12. As this integer was negative, it suggested that the root must lie closer to -2.948828358122 than it is to -2.948828358123. And so I can give my answer of -2.948828358122 correct to 12 decimal places, but with an error bounds of:
+ or - 0.0000000000005
The graph below shows the iteration process, and that the approximations converge very quickly:
After finding the first root, I went on to investigate the next root, between the interval of [0, 1]. I used the same technique and this time my starting point was 1. These were the iteration results:
x1
.000000000000
x2
0.750000000000
x3
0.782352941176
x4
0.782815581320
x5
0.782815678664
x6
0.782815678664
Again the convergence worked and this time the root was 0.782815678664
Finally I investigated the final root, at the interval of [2, 3] and my starting point this time was 3. These were the iteration results:
x1
3.000000000000
x2
2.450000000000
x3
2.217783329548
x4
2.168294044149
x5
2.166017443144
x6
2.166012679479
x7
2.166012679458
x8
2.166012679458
The final root was found to be 2.166012679458
Failure of Newton-Raphson Method:
Failure can happen when the iteration does not converge towards the root, even though if the starting point was within reason. Using the graph as before, I tried finding the root between the interval of [-3, -2] but instead used a staring point of -1. As shown on the graph below, the iteration converges towards another root, and not the root that I was investigating:
This is often a problem with the Newton-Raphson method, as if a starting point is chosen and it is near the turning point of the curve, it often converges towards the wrong value. Therefore when selecting the starting point you have to pick a very good guess, otherwise it may end up converging towards the wrong root, or even diverging away altogether.
Comparison Of Methods:
For the comparison, I will be comparing each of the methods against the Rearranging Method. With the rearranging method, I used the equation:
f(x) = x³-4x+1
One of the roots that I found was between the interval of [0, 1] and the method found the root to be 0.254101688365, and was found in 11 steps of the iteration process. I will now use the other methods to find the same root, in order to compare the merits and flaws.
Using Change of Sign Method:
I used the same technique as before, but used the new equation, and plugged in values of x, in order to see when f(x) changes sign from positive to negative. The results were very large as I was doing it to 12 decimal place accuracy, and so are shown separately on the next page.
Using Newton-Raphson Method:
In order to do this, I first must differentiate the equation, and plug the values into the Newton-Raphson version of the iteration formula. The simplified result was:
x n+1 = 2x³ - 1
(3x² - 4)
I then used the iteration process, and plugged the starting point of 0.5 into the equation. I chose 0.5 in order to make the comparison fair, as I had used 0.5 as the starting point for the Rearranging Method. I then carried on the iteration process till I reached the desired result. These were the results:
x1
0.230769230769
x2
0.254000237051
x3
0.254101686304
x4
0.254101688365
x5
0.254101688365
As the results show, it only took 5 steps in order to find the root.
Comparison of Speed of Convergence:
The speed of convergence for the Newton-Raphson was much faster than that of the Rearranging Method. This is because by finding the tangent to the curve each time, it is getting closer to the root of the equation faster, rather than finding the points of intersection between the curve y = g(x) and y =x, as that takes more iterations in order to reach the root. For the equation, it took the Newton-Raphson method only 5 steps to reach the answer, whereas it took the Rearranging Method 11 steps, thus over twice as slow.
However, both of these methods are faster than that of the Change of Sign method, as for that you must examine a huge amount of values of x in order to find where the sign changes, and it takes a very long time to find the root to the same amount of accuracy as the rest. The actual number of calculations needed was 132, compared to that of 5 and 11 steps for the other methods, makes it a very tedious method.
Comparison of Ease of Use with Available Software and Hardware:
The Rearranging Method and Newton-Raphson Method are relatively similar in their demands for software and hardware, as they both require a machine and software that is able to plot graphs, so that the roots can be spotted and fixed point estimations can be made. The Change of Sign Method however, does not require this as it can simply see when the sign changes and thus discover the roots. The iterations of the Newton Raphson Method and Rearranging Method can be calculated via easy formulas in a spreadsheet program such as Excel, though they require no more hardware or software than that of the Change of Sign method, which also uses simple spreadsheet formulas to calculate the value of f(x). However, the Change of Sign method does require more hard disk space as the calculations can be very large at times in comparison with the other methods.
Daniel Hoij 13.6 DCGS Centre No. 52205 Candidate No. 8670