1
Investigating numerical methods
The aim of this investigation is to analyze three methods of numerically finding the solutions to equations, the potential limitations and strengths of the methods below will also be discussed. The methods to be deployed are Change of Sign, Newton Raphson, and iterations. To allow later comparison, all methods will be deployed to find solutions to 5 d.p.
Change of sign method
y = x4 – 3x3 + x -1
In this method two boundaries within which the solution lies are chosen. Values are investigated at 1 d.p to find two more boundaries, shown when a change of sign in solution occurs. Then the process is then repeated for further decimal places.
Solution of root
Step Num / X Value / Y Value1 / 2 / -7 / Change of sign experienced
2 / 3 / 2 / Answer between 2 and 3
3 / 2 / -7
4 / 2.1 / -7.2349
5 / 2.2 / -7.3184
6 / 2.3 / -7.2169
7 / 2.4 / -6.8944
8 / 2.5 / -6.3125
9 / 2.6 / -5.4304
10 / 2.7 / -4.2049
11 / 2.8 / -2.5904
12 / 2.9 / -0.5389 / Change of sign experienced
13 / 3 / 2 / Answer between 2.9 and 3
14 / 2.9 / -0.5389
15 / 2.91 / -0.3077954
16 / 2.92 / -0.071767 / Change of sign experienced
17 / 2.93 / 0.169237 / Answer between 2.92 and 2.93
18 / 2.92 / -0.071767
19 / 2.921 / -0.0478914
20 / 2.922 / -0.023966 / Change of sign experienced
21 / 2.923 / 9.356E-06 / Answer between 2.922 and 2.923
22 / 2.922 / -0.023966
23 / 2.9221 / -0.0215707
24 / 2.9222 / -0.0191749
25 / 2.9223 / -0.0167786
26 / 2.9224 / -0.0143818
27 / 2.9225 / -0.0119845
28 / 2.9226 / -0.0095868
29 / 2.9227 / -0.0071885
30 / 2.9228 / -0.0047897
31 / 2.9229 / -0.0023904 / Change of sign experienced
32 / 2.923 / 9.356E-06 / Answer between 2.9229 and 2.923
33 / 2.9229 / -0.0023904
34 / 2.92291 / -0.0021505
35 / 2.92292 / -0.0019105
36 / 2.92293 / -0.0016705
37 / 2.92294 / -0.0014306
38 / 2.92295 / -0.0011906
39 / 2.92296 / -0.0009506
40 / 2.92297 / -0.0007106
41 / 2.92298 / -0.0004706
42 / 2.92299 / -0.0002306 / Change of sign experienced
43 / 2.923 / 9.356E-06 / Answer between 2.92299 and 2.923
Error bounds
The solution was found to lie between 2.92299 and 2.92300, an assumed approximate answer is therefore 2.922995 with an error of .
The solution is displayed graphically below;
From this graph we can see that when the value of x = 2.92299 the function returns a negative value (i.e. the result is below the x-axis). Also we can see that when x = 2.923 the function returns a positive value (one above the x-axis).
An example where the method fails
By definition the methods requires a change of sign to occur. However roots of some equations exist where the function will merely ‘touch’ the x-axis, with a solution occurring twice at the same value yet no change of sign occurs. A good example is shown below.
y = x2
The solution lies between -1 and 1.
Solution to root
Step Num / X Value / Y Value1 / -1 / 1
2 / -0.9 / 0.81
3 / -0.8 / 0.64
4 / -0.7 / 0.49
5 / -0.6 / 0.36
6 / -0.5 / 0.25
7 / -0.4 / 0.16
8 / -0.3 / 0.09
9 / -0.2 / 0.04
10 / -0.1 / 0.01
11 / 0 / 0
12 / 0.1 / 0.01
13 / 0.2 / 0.04
14 / 0.3 / 0.09
15 / 0.4 / 0.16
16 / 0.5 / 0.25
17 / 0.6 / 0.36
18 / 0.7 / 0.49
19 / 0.8 / 0.64
20 / 0.9 / 0.81
21 / 1 / 1
Clearly a solution exists when x = 0. However, using this method that is not apparent. This would be most crucial if the process were used automatically in computer software to find solutions, the computer programme would need a set rule to search for a change of sign, when no change occurs no result would be given.
Newton Raphson method
In Newton Raphson the following iterative formula is used, with each iteration being progressively closer to the solution.
Solution to a second equation
*Shown below – note – graph is a representation for visual purposes and does not display all turning points since the coursework focuses on intersections with the x-axis.
In this example equation a value has to be selected as the starting value, known as .
This value is one close to the solution which is desired to be solved. In this particular equation when finding an accurate answer for the right hand root (-ve X, +ve Y quadrant) a close approximation is -4, let this be .
Solution of point near x = -4
First f’(x) is found and the iterative formula set-up;
Value of n / Iteration answer0 / -4
1 / -4.708333333
2 / -4.500295635
3 / -4.470421752
4 / -4.469838841
5 / -4.469838622
Solution found to 5 d.p (when two iterations returned the same value to 5 d.p).
Answer to 5 d.p = -4.46984
Solution found for the second root
Second root lies near 1, using the same method let = 1
Value of n / Iteration answer0 / 1
1 / 0.916666667
2 / 0.90545028
3 / 0.905259139
4 / 0.905259084
Answer to 5 d.p = 0.90526
The graph above shows the true power of this iteration based numerical method. The method managed to converge to the required root within 4 iterations. Above we can see that a line labelled X0 is drawn equal to the first value, a tangent is then made where the line intersects with the curve. This tangent then intersects with the x-axis and that intersect is the new value of Xn, in this case X!. This process is repeated and the iterations converge closer and closer to the solution. At this current magnification the root is converged to so quickly that after just 2 iterations further iterations are not visible.
Error bounds for root 0.90526
An example where the method fails
The equation has two roots both near a turning point. This method relies on the ability for a tangent to intersect with the x-axis, yet at a turning point the gradient is 0, and a tangent will therefore be horizontal.
This is reinforced algebraically;
when x = 2
One cannot divided by 0, showing that no solution is found using this starting value to find either roots, the tangent produced by the starting value is shown below to be horizontal.
Iteration method
The iteration method is exactly that, a rearrangement of an equation into the form.
The resultant then produces the iterative formula;
Solution to a third equation
Formula rearranged into the form .
The root to be found is the second root close to the origin where . Therefore let =0.
Iterative formula is therefore;
Value of n / Iteration answer0 / 0
1 / 0.25
2 / 0.262026612
3 / 0.26326017
4 / 0.263390536
5 / 0.263404356
6 / 0.263405822
7 / 0.263405977
Answer to 5 d.p = 0.26341
Graphical representation
The intersection with the y=x line in the graph above near 0 has a gradient where. This is why the iterative formula converges so successfully, x=g(x) iterations require the gradient to be within these thresholds.
The Graph above shows the graph of the rearrangement with the y=x line drawn in, which the iterative procedure converges using, shown below.
Firstly a line x=X0 was drawn and the intersection with the function was used as the value to find the next value of n, (on graph labelled X1). This process is repeated and the resultant n values converge ever closer to the root.
An example where the method fails
We can see from the graph of the rearrangement that the intersection providing a root near -1 has a very large value of g’(x). With equal aspect scales one can see quite clearly that is unlikely to be true. Therefore the root will not converge, or will converge to a different root.
Value of n / Iteration answer0 / -1
1 / 1.333333333
2 / -1.35
3 / -0.480170461
4 / 0.30481936
5 / 0.268216167
6 / 0.263921592
7 / 0.263460735
8 / 0.263411801
9 / 0.263406611
10 / 0.263406061
In this case the iterative formula does provide an answer but it is not the intended root, showing that the method fails when is not true.
Comparison of the three methods
Resolving a common root for comparison
A common root of a common equation shall be found to fairly compare the three methods.
will be used, the root close to 0 is to be found using Newton Raphson and The change of Sign method, the root has already been found using the iteration method.
Change of sign method
Boundaries for the root are between 0 and 1
Step Num / X Value / Y Value1 / 0 / -1
2 / 0.1 / -0.602975
3 / 0.2 / -0.2236 / Change of sign experienced
4 / 0.3 / 0.121025 / Answer between 0.2 and 0.3
5 / 0.2 / -0.2236
6 / 0.21 / -0.1872968
7 / 0.22 / -0.1513584
8 / 0.23 / -0.1158014
9 / 0.24 / -0.0806426
10 / 0.25 / -0.0458984
11 / 0.26 / -0.0115856 / Change of sign experienced
12 / 0.27 / 0.0222796 / Answer between 0.26 and 0.27
13 / 0.26 / -0.0115856
14 / 0.261 / -0.0081786
15 / 0.262 / -0.0047762
16 / 0.263 / -0.0013783 / Change of sign experienced
17 / 0.264 / 0.0020152 / Answer between 0.263 and 0.264
18 / 0.263 / -0.0013783
19 / 0.2631 / -0.0010387
20 / 0.2632 / -0.0006992
21 / 0.2633 / -0.0003598
22 / 0.2634 / -2.035E-05 / Change of sign experienced
23 / 0.2635 / 0.000319 / Answer between 0.2634 and 0.2635
24 / 0.2634 / -2.035E-05 / Change of sign experienced
25 / 0.26341 / 1.359E-05 / Answer between 0.26340 and 0.26341
To 5 d.p.
Newton Raphson Method
0 / 0
1 / 0.25
2 / 0.263291855
3 / 0.263405987
4 / 0.263405995
Answer to 5 d.p = 0.26341
Comparison of the methods – speed of convergence
Now that a common root of a common function has been resolved, one can compare the speed of convergence by analyzing the number of steps taken to find the correct answer to 5 d.p.
Method / StepsNewton Raphson / 4
x=g(x) iteration / 7
Change of sign / 25
The number of steps is considered from a mechanical point of view. One could program a piece of spreadsheet software or a graphical calculator to display the answer from 0 to 1 of all x value in 0.1 steps, for the change of sign method, and a human could spot the change of sign positions by eye, but a computer would need to continue until a change of sign was experienced one by one. Hence the method used to count the steps in the change of sign method.
To summarize it is clear that the most powerful method when considering the number of steps before the root is resolved must be the Newton Raphson method. The x=g(x) is similarly fast a finding a solution and only slightly slower, yet the speed of convergence of the change of sign method is far to slower due to the amount of steps involved in resolving the root.
Comparison of methods – Ease of use
Method / Time consumed (s)Newton Raphson / 90
x=g(x) iteration / 240
Change of sign / 130
The results of ease of use are quite surprising, however once considered, understandable. The x=g(x) method took far longer than the other methods to provide an answer despite its iterative nature and small amount of iterations to find the root.
The reason for this was simply that technology in the form of powerfully software aided greatly in the change of sign and Newton Raphson method. The x=g(x) method is restricted to the degree to which software and/or hardware can speed its process; the iteration itself only took 30 seconds. It was the preparation in setting up a rearrangement that works, and provides a value for g’(x) which is acceptable. Clearly this is trial and error and software advances can do little to solve this problem.
All methods, whether iteration or change of sign were done using spreadsheet software where a relationship using the formula or iterative relationship and the computer automatically assumes the next ‘n’ values and calculates the result. In all methods this proved very powerful and easy to use. In conclusion, it would seem that with the use of a computer both Newton Raphson and change of sign are very easy methods, as too for the x=g(x) iteration IF a suitable rearrangement is found quickly. Despite this if a computer was not available I feel that the manual style of change of sign may take an extensive period of time , and the order of ease of use would match more the close the order of steps required. Clearly the issue of ‘ease of use’ is solely dependant on the available hardware and software.