Analyse the use of three methods which are called the: change of sign, Newton-Raphson and the rearrangement method and use them to find roots of different equations.
MATHS P2 COURSEWORK
There are many different kind of methods which can be used to find the roots of equations which can not be sold algebraically. In this coursework we are going to analyse the use of three of these methods which are called the: change of sign, Newton-Raphson and the rearrangement method and are going to use them to find roots of different equations.
Change of sign method
A root of an equation (where the graph crosses the x-axis) can be detected by finding where the solution of a formula changes sign from positive to negative. Where we find a change of sign on a graph using omnigraph we take the range of the numbers it is in and divide it by ten to find where it now changes sign. This procedure is then repeated to the required level of accuracy.
Here is a graphical representation of the systematic decimal search:
X 1
X 10-1
X10-2
Using change of sign method on excel
First you look up between 2 values (e.g. 1 and 2, or 4 and 5) where the graph crosses the x-axis. Then you take that as your range and divide it up into 10 equal segments. For example, if between 1 and 2.. you use 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, etc. you work out the formula for each of these and where the change of sign occurs you repeat the process between that range.
A
B
C
D
E
E
X1
f(A1)
A2+0.01
f(C1)
C1+0.001
f(C1)
2
A1+0.1
f(A2)
C1+0.01
f(C2)
E1+0.001
f(C2)
3
A2+0.1
f(A3)
C2+0.01
f(C3)
E2+0.001
f(C3)
4
A3+0.1
f(A4)
C3+0.01
f(C4)
E3+0.001
f(C4)
5
This process carries on to the required accuracy and this is how we try to find the root of an equation, using omnigraph and excel.
Example
I'm going to use the change of sign method to investigate when the method works and when it doesn't.
The equation I am going to find the root of is f(X)= x5+4x4-6x which looks like this.
As shown above there are 3 roots one which is at 0 and the others between -5 and -4, 1 and 2.
I'm going to find the root which lies between 1 and 2.
To find this root I'm going to use excel to see where the solution of the equation changes sign.
This shows the first few columns to how we came to find the root between 1 and 2.
FOR F(X)= x5+4x4-6x
x
f(x)
x
f(x)
x
f(x)
x
f(x)
x
f(x)
-4
24
-1
-1
.05
-0.16169
.058
-0.01045
-3
99
.1
0.86691
.01
-0.84657
.051
-0.14306
.0581
-0.00853
-2
44
.2
3.58272
.02
-0.68619
.052
-0.12434
.0582
-0.0066
-1
9
.3
7.33733
.03
-0.51869
.053
-0.10555
.0583
-0.00468
0
0
.4
2.34464
.04
-0.34391
.054
-0.08668
.0584
-0.00276
-1
.5
8.84375
.05
-0.16169
.055
-0.06774
.0585
-0.00083
2
84
.6
27.10016
.06
0.028133
.056
-0.04872
.0586
0.001093
3
549
.7
37.40697
.07
0.225736
.057
-0.02962
.0587
0.00302
4
2024
.8
50.08608
.08
0.431284
.058
-0.01045
.0588
0.004947
5
5595
.9
65.48939
.09
0.64495
.059
0.008804
.0589
0.006875
6
2924
2
84
.1
0.86691
.06
0.028133
.059
0.008804
The highlighted cells show where the solution to the function has a change of sign. The actual figure if we carry on this method comes to 1.0585432205 ± 0.0000000005. However, if we use 4.d.p as a sensible level of accuracy, we wud say the root is= 1.0585 < x < 1.0586
Where the change of sign method fails
However this method may not always be able to find the root of an equation. Here is an example of an equation that cannot be found using the systematic decimal search:
f(x)=x3+5.283x2-0.2144x-22.56371908
As shown there is a definite root between 1 and 2 and a possible root between -3 and
-4. Using systematic decimal search it is not clear whether a root lies between -3 and
-4. Here are the tables for f(x) =x3+5.283x2-0.2144x-22.56371908 produced on excel.
For: f(x)=x3+5.283x2-0.2144x-22.56371908
-5
-14.4167
-4
-1.17812
-3
-1.37352
-2
-9.00292
-1
-18.0663
0
-22.5637
-16.4951
2
6.139481
3
51.34008
4
25.1067
5
233.4393
This table shows that a change of sign doesn't occur between -4 and -3 meaning there are no roots between these values. However, the graph shows that a change of sign does occur and has roots.
This proves that the change of sign method does not work for all equations, as the above shows there are two roots between -3.7 and -3.6 and -3.5 and -3.4 . The roots are very close together and this is why the roots don't show up, as a change of sign, in the ...
This is a preview of the whole essay
4
25.1067
5
233.4393
This table shows that a change of sign doesn't occur between -4 and -3 meaning there are no roots between these values. However, the graph shows that a change of sign does occur and has roots.
This proves that the change of sign method does not work for all equations, as the above shows there are two roots between -3.7 and -3.6 and -3.5 and -3.4 . The roots are very close together and this is why the roots don't show up, as a change of sign, in the table
Rearrangement method
The roots of an equation can be found be rearranging the equation "f(x)=0" in terms of "x" (i.e. in the form "x = g(x)"). An initial value for x is entered producing a value for g(x). This value of g(x) is then used as the new value of x2. This process is repeated and after appropriate iteration a very accurate value of a root can be found.
Here is a graphical form of the process I am going to use which is the Spiral method. This method is used where the curve bisects the curve y=x with a negative gradient.
Using Y=x and y=g(x)
The above shows how the rearrangement method is used to converge to the root.
How to use the rearrangement method on excel
First a value for x is put into cell A1. Then the function f(x)=0 is rearranged into the form x=g(x), and the function g(x) is input in cell A2 with reference to cell A1. This procedure is repeated until an accurate value for x is obtained.
A
x
2
=g(A1)
3
=g(A2)
4
=g(A3)
5
=g(A4)
6
Fill down until 2 adjacent values are identical
Example
I am now going to use the above method for the equation:
5x3-6.5x2-4x+3.15=0
Y=f(x) can be rearranged into:
x=g(x)= 5x36.5x2+3.15
4
Shows y=x and y=g(x)
Using '1' as my initial value I'm going to try to attain the value 0.37494227 (accurate to 8.dp) as shown below.
However, we can say that 0.37494226 < x < 0.37494227.
FOR g(x)=5x3-6.5x2+2.15/4
x
g(x)
x
g(x)
x
g(x)
x16
0.37394395
x1
.00000000
x17
0.37563226
x32
0.37493954
x2
0.16250000
x18
0.37446511
x33
0.37494414
x3
0.49995361
x19
0.37527211
x34
0.37494096
x4
0.28753189
x20
0.37471419
x35
0.37494316
x5
0.43286827
x21
0.37509994
x36
0.37494164
x6
0.33440156
x22
0.37483324
x37
0.37494269
x7
0.40252817
x23
0.37501763
x38
0.37494197
x8
0.35572951
x24
0.37489015
x39
0.37494247
x9
0.38813591
x25
0.37497829
x40
0.37494212
x10
0.36578518
x26
0.37491735
x43
0.37494231
x11
0.38125397
x27
0.37495948
x44
0.37494223
x12
0.37057006
x28
0.37493036
x45
0.37494229
x13
0.37796083
x29
0.37495049
x46
0.37494225
x14
0.37285332
x30
0.37493657
x47
0.37494227
x15
0.37638555
X31
0.37494620
x48
0.37494226
The convergence of the iteration to this root can be demonstrated graphically. Below are the graphs of y=x and g(x) = 5x3-6.5x2+2.15 displayed on the same axes. 4
However, this method does not work for all graphs in the form of x=g(x). The roots of the graph above can be found using this method because the gradient of the curve at the interception is near the region of -1 to 1.
The actual gradient is:
g'(x) = 15x2-13x
4
And near the region of the root which is close to 0.4, the gradient= -0.7
This gradient is between -1 and 1. This feature allows the value of x to converge to the root after several iterations.
* Failure
However, 'x' may not always be able to converge to the required root.
By rearranging the same equation the result is:
The table below shows the results we get if we try to find the root between 1.5 and 2.
X1 is the starting point of the attempted convergence method.
x1
2
.9
.8
.7
x2
3
2.335627530
2.060683761
.802262443
x3
5
3.722508199
2.811604741
2.066722245
x4
7
0.132754463
5.583122148
2.830307506
x5
230
78.396268951
23.421746740
5.663513488
x6
40704
4727.061900274
421.381984107
24.116392026
x7
.27E+09
.72E+07
.37E+05
4.47E+02
x8
.25E+18
2.27E+14
.44E+10
.54E+05
x9
.20E+36
3.97E+28
.58E+20
.81E+10
x10
.11E+72
.21E+57
.93E+40
2.53E+20
x11
9.46E+143
.13E+114
2.87E+80
4.92E+40
x12
#NUM!
#NUM!
6.32E+160
.87E+81
x13
#NUM!
#NUM!
#NUM!
2.68E+162
x14
#NUM!
#NUM!
#NUM!
#NUM!
x15
#NUM!
#NUM!
#NUM!
#NUM!
As shown in the table, the iteration fails after a number of convergences to any roots and actually diverges away from the root.
Graphical demonstrations of the failing iterations are shown below:
At the required root:
g'(x) = 15x2 - 4
6.5x
The approximate root is = 1.6
Using x=1.6, g'(x) = (15 x 1.62-4) / (6.5 x 1.6) = 3.308 (3dp)
The gradient at this root is not between -1 and 1, but quite steep positively. Due to this the value of x diverges from the root after several iterations.
From this failure it is apparent that in order for the iteration to converge to a root, the gradient at the root generally needs to be between -1 and 1.
Newton raphson
A root of an equation can also be found by the following method:
A (Xn,f(Xn))
B Xn
y=f(X)
* Take tangent at point (A) on y=f(x)
* Find out when this tangent cuts the x axis (i.e. y=0) (B)
* Use that value as the next x value
* Repeat this procedure
Equation of AB slope of AB = f'(xn)
y=f'(xn)x + c
f(xn)=f'(xn)xn + c
c=f(xn) - f'(xn)xn
y=f'(xn)x + f(xn) - f'(xn)xn
At B, y=0 0=f'(xn)x + f(xn) - f'(xn)xn
x=f'(xn)xn -f(xn)
f'(xn)
xn+1 = xn f(xn)
f'(xn)
* Method on Microsoft Excel
First a value of x is typed into A1. Then in the cell below (B1), the
A
X
2
A1-f(A1)/f'(A1)
3
A2-f(A2)/f'(A2)
4
A3-f(A3)/f'(A3)
5
A4-f(A4)/f'(A4)
6
A5-f(A5)/f'(A5)
7
A6-f(A6)/f'(A6)
8
A7-f(A7)/f'(A7)
9
A8-f(A8)/f'(A8)
Drag down until two
Consecutive values are identical
This method will find different roots depending on the nature of the slope, and the original value of x that you start with.
I am going to use the above method to find the root of f(x)= 0.5x3-2.5x+0.06
As we can see, the graph has 3 roots. To get to these roots, we need different starting points for each root. These starting points are going to be -2, -0.5 and 3. All of the roots found below are (to 8or9 D.P).
f(x)= 0.5x3-2.5x+0.06
f'(x)=1.5x2-2.5
A
B
C
x1
-2.00000000
-0.5
3.000000000
x2
-2.30285714
0.087058824
2.449090909
x3
-2.24986517
0.023844498
2.251747622
x4
-2.24797511
0.024002765
2.224478330
x5
-2.24797274
0.024002766
2.223970147
x6
-2.24797274
0.024002766
2.223969972
x7
-2.24797274
0.024002766
2.223969972
Therefore, we can see that the roots of the equation f(x)= 0.5x3-2.5x+0.06 are
-2.24797, 0.02400 and 2.22397 (to 5DP).
Below is the graphical demonstration of how the root between 2 and 3 was found.
As evident in the graph, it only takes a few iterations to find the root.
Error bounds:
Comparing the values of x, to see how similar they are, can determine the accuracy of the roots. Here is a comparison of the values of x obtained by iteration, between 2 and 3.
Initial x value
3
.
0
st iteration
2
.
4
4
9
0
9
0
9
0
9
2nd iteration
2
.
2
5
7
4
7
6
2
2
3rd iteration
2
.
2
2
4
4
7
8
3
3
0
4th iteration
2
.
2
2
3
9
7
0
4
7
5th iteration
2
.
2
2
3
9
6
9
9
7
2
6th iteration
2
.
2
2
3
9
6
9
9
7
2
After 1 iteration, we cannot say how accurate the root is, as the values of x aren't similar to any significant figures or decimal places.
After 2 iterations we can say the root is 2.4 (to 1 d.p.)
After 3 iterations we can say the root is 2.25 (to 2 d.p.)
After 4 iterations we can say the root is 2.2244 (to 4 d.p)
After 5 iterations we can say the root is 2.22397 (to 5 d.p.)
After 6 iterations we can say the root is 2.223969972 (to at least 9 d.p.)
Therefore, we can say, the more times we use this method the closer and more accurate we can get to the actual root of the equation. Therefore, this method is good at getting an accurate answer. This is an example of 'quadratic convergence'.
Where the Newton raphson method fails
However, the Newton raphson method does not always find a root of an equation.
For example:
y=ln(4x3+5)+e-x
As shown in the graph there is only one solution to this graph at around -1. To apply the Newton-Raphson method the derivative of the equation is required:
dy 12x2 e-x
dx 4x3+5
However, when the Newton-Raphson formula is applied on a spreadsheet it only takes a few iterations before there is an error in the calculation. Here are a few examples:
0
0.1
-0.5
-1
-0.1
2.609437912
-1.65689
2.9552604
2.71041076
-1.29286
2.410109
-1.79347836
#NUM!
-2.214477
-1.91031344
#NUM!
-1.57941
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
#NUM!
Every starting value that I have used did not find the root required, as we can see instead, we obtained errors. The reason for this is that at the root the gradient of the curve is extremely high. Therefore the formula cannot be used to gradually get closer and closer to the root. 'Another problem is that it is a natural logarithmic function and so there is only a small range of x values for which the function has real values. This is because the natural logarithm of a negative number is undefined.' (Source: P2 textbook). Therefore when the tangent to the curve is found at particular points, there is no corresponding x value, meaning that the formula breaks down. As shown below:
Comparison of all the methods
Here we are going to use all three methods to find the root of one of the equations above and analyse how good it is as a tool. The equation we are going to use is the
equation I used for the Newton raphson method which is f(x)= 0.5x3-2.5x+0.06
These are the results obtained by the Newton raphson method again:
f(x)= 0.5x3-2.5x+0.06
f'(x)=1.5x2-2.5
A
B
C
x1
-2.00000000
-0.5
3.000000000
x2
-2.30285714
0.087058824
2.449090909
x3
-2.24986517
0.023844498
2.251747622
x4
-2.24797511
0.024002765
2.224478330
x5
-2.24797274
0.024002766
2.223970147
x6
-2.24797274
0.024002766
2.223969972
x7
-2.24797274
0.024002766
2.223969972
If we use the change of sign method with this equation, we get the following results for finding the root at 0.024002766 but I've stopped at 0.0240<x<0.0241:
0.0000
0.0600
0.0000
0.0600
0.0200
0.0100
0.0240
0.0000
0.1000
-0.1895
0.0100
0.0350
0.0210
0.0075
0.0241
-0.0002
0.2000
-0.4360
0.0200
0.0100
0.0220
0.0050
0.0242
-0.0005
0.3000
-0.6765
0.0300
-0.0150
0.0230
0.0025
0.0243
-0.0007
0.4000
-0.9080
0.0400
-0.0400
0.0240
0.0000
0.0244
-0.0010
0.5000
-1.1275
0.0500
-0.0649
0.0250
-0.0025
0.0245
-0.0012
0.6000
-1.3320
0.0600
-0.0899
0.0260
-0.0050
0.0246
-0.0015
0.7000
-1.5185
0.0700
-0.1148
0.0270
-0.0075
0.0247
-0.0017
0.8000
-1.6840
0.0800
-0.1397
0.0280
-0.0100
0.0248
-0.0020
0.9000
-1.8255
0.0900
-0.1646
0.0290
-0.0125
0.0249
-0.0022
.0000
-1.9400
0.1000
-0.1895
0.0300
-0.0150
0.0250
-0.0025
If we use the rearrangement method this is what happens, using the rearrangement of x=0.5x3+0.06
2.5
x1
.0000
x2
0.2240000000000
x3
0.0262478848000
x4
0.0240036167037
x5
0.0240027660501
x6
0.0240027657561
x7
0.0240027657560
x8
0.0240027657560
*when accurate to 9d.p.
* Speed of Convergence
Change of Sign method
The speed of convergence using this method is relatively slow. It has the lowest speed of convergence out of all the methods used. The procedure needed to be done 9 times to obtain the required root accurate to 9 decimal places because we knew the region of the root, otherwise it would have taken 10 repetitions. Every time the method is repeated the root becomes accurate to another decimal place. Therefore the convergence is linear, of magnitude 10. After n iterations the root can be said to be:
a ± 5x10-n
(where a is the average of values between which the root lies.)
Newton-Raphson method
This method is as fast as the convergence of the rearrangement method but much faster than the change of sign method. Using -0.5 as the starting value, it took just 6 iterations to have a value for the required root accurate to 9 decimal places. The Newton-Raphson method has quadratic convergence. For example, the error of a particular term is roughly equal to the square of the previous error.
i.e. Error n+1 (Error n )2
This is why the root is found accurately, to many decimal places, so quickly.
(source: P2 textbook).
Rearrangement method
The speed of convergence for this method is as quick in comparison to the Newton-Raphson method, but much faster than the change of sign method. To obtain the required root accurate to 9 decimal places, it required 6 iterations, using 1 as the starting value. However, this starting value is further away from the required root than the starting value used in the Newton-Raphson method so we could assume that this method converged faster than the Newton-Rapshon method.
Ease of Use
All three methods use Microsoft Excel, and so computer literacy is required for each procedure. However, some of the methods required greater mathematical and computer skill than others.
Change of sign method
The systematic search is the most functional out of all three methods. It requires the least mathematical knowledge to be able to apply it, and the accuracy of the root can be easily calculated. You only need to use the formula provided, and locate where a change of sign occurs which is very easy on excel.
Newton-Raphson method
This method requires the most mathematical ability to perform, as you need to differentiate the equation provided, divide the formula by its differential, and minus this from the previous value. This is a greater number of calculations to perform than the other two methods, and the calculations are much more complex. Also, this method doesn't always converge to the required root. Different starting values of x may have to be used to obtain the required root.
Rearrangement method
This method isn't as mathematically advanced as the Newton-Raphson method, but it requires more mathematical ability than the change of sign method. The only calculation that you need to do is to rearrange the formula f(x)=0 into the form x=g(x), which can be done in a variety of ways. However, not all of the rearrangements work, and so many different rearrangements and starting values often have to be used. For the rearrangement to work, the gradient of g'(x) at the root needs to be between -1 and 1.
CONCLUSION
I think that the rearrangement method is the best method to use, because even though the convergence of the rearrangement and Newton-raphson methods are the same, the ease of use of the rearrangement method is much better. However, when I used the rearrangement before, I did not converge to a value until I repeated the process 32 times, this shows even thought the method can be fast, it can also be unreliable.
However, when using this method you must be carefull in choosing the right rearrangement of f(x) because not all rearrangments work. In this sense the Newton raphson method is better because it is more likely to find a root, and only fails when there is a break in the magnitude of the graph.
The slowest, but easiest method is the change of sign method. However, this method can take a very long time to do as it requires many repetitions of the same process.
Due to the unreliability of the rearrangement method I think the Newton raphson method is the best method to use, because it shows reliability, accuracy and has fast convergences.