The table is shown again below.
I will investigate this further: A table is produced of values between 0.4 and 0.5.
Although there is no change of sign there is an evident way of getting nearer to the root. As the table shows the numbers are getting nearer to 0 up to x = 0.44, but x = 0.45 is now starting to move away from 0.
One more table of values between 0.44 and 0.45 should prove this further.
This also was the case with f(x) getting nearer to 0 up until x = 0.444 and then moves away from 0 for x = 0.445.
So even though I have done three sets of iterations, there is no change of sign.
Newton-Raphson Method
Now I will be using the Newton-Raphson method to find the roots of the equation:
y=ex-x3-1.4
The Graph is shown below and shows there are three roots for the equation.
The table of values is shown below.
The Newton-Raphson formula is: X1=X0 - f(X0)
f’(X0)
Here, X0 is the current known x-value, f(X0) represents the value of the function at X0, and f'(X0) is the derivative (slope) at X0. X1 represents the next x-value that I am trying to find.
I will now find the function equations for f(X0) and f’(X0).
F(X0) = ex-x3-1.4
F’(X0) = ex -3x2
So my formula is: X1=X0 - ex0-x03-1.4
ex0 -3x02
To find root A.
X0 = -2
X1 = -2-(e-2-(-2)3-1.4) = -1.43232
(e-2 -3-22)
X2 = -1.13190
X3 = -1.02608
X4 = -1.01226
X5 (root) = -1.01203 Answer (5.d.p.)
Answer Root A: -1.01203 (5 .d.p)
Error: -1.01203 + 0.000005
Error bounds: [-1.012025, -1.012035]
F(x) = ex-x3-1.4
F(-1.012025) = -0.0000073
F(-1.012035) = 0.0000198
A change of sign occurs and so confirms there is a root.
Finding Root B
X0 = 0.8
X1 = -0.22618
X2 = 0.69116
X3 = 0.21887
X6 = 0.37282 ( 5.d.p.)
Answer Root B: 0.37282 (5.d.p.)
Finding Root C
X0 = 1
X1 = 2.12979
X2 = 1.62013
X3 = 1.40784
X6 = 1.34816
Answer Root C: 1.34846(5.dp.)
Newton-Raphson Failure
For the Newton-Raphson method to fail the X0 starting position must be between a turning point and the root. This will therefore not find the required root.
For example with the equation:
F(x) = 43x3-60x2-250x-115
The graph for this function is shown below.
The table of values is given below:
Using the Newton-Raphson formula of: X1=X0 - f(X0)
f’(X0)
F(x) = 43x3-60x2-250x-115
F’(x) = 129x2–120x-250
So my formula is: X1=X0 - 43x03-60x02-250x0-115
129x02–120x0-250
Finding Root A
X0 = -1
X1 = -1 – 43(-1)3-60(-1)2-250(-1)-115 = 31
129(-1)2–120(-1)-250
X2 = 20.87085
X3 = 14.14418
X11(root)= 3.36156 This is actually ROOT C.
The graph 1 shows the iteration process. It shows the first iteration more clearly than my graph 2: Only the first 7 or 8 iterations are shown clearly here
The graph 2 below is showing the same iteration process but the y-axis goes up to a million.
Graph 3 shows the iteration process from X7 between the x values of 3.3 and 4
This is an example of the Newton-Raphson failing. I started near to root A but the method went and found the root of C. It failed as I started too near to the turning point. Therefore, f’(x) was very close to value 0. it is illustrated on the next page.
Using autograph I found the turning point to be -1.003 ( 3 d.p.)
The graph below shows that the X0 starting point starting point is very near to the turning point.
Answer Root C: 3.36156 (5 d.p.)
Error: 3.36156 + 0.000005
Error Bounds: [3.361555, 3.361565]
For these error bounds to be valid there must be a change of sign when the values are input into the equation:
f(x) = 43x3-60x2-250x-115
f(3.361555) = -0.00478
f(3.361565) = 0.00327
There is a change of sign in the two answers so I can say the error bounds are valid.
ROOT C ANSWER = 3.36156 (5 d.p.)
This concludes that there is a root but the answer is root C not root A which I was initially trying to find.
Rearrangement
This method uses an estimate for the value of x using an iterative process. By rearranging f(x) = 0 into the form x = g(x) provides an iterative formula which will converge to a required root by picking an appropriate starting value. On a graph the roots will be equal to the values of x where the curve y = f(x) intersects the line y = x. The equation I will use is:
y= x3-5x+2.6
The graph is shown below with 3 roots to the equation.
dy = 3x2-5 =0
dx
= 3x2 = 5 => 2 turning points
The table of values is given below:
Rearrangement into x= g(x)
x3-5x+2.6
x= 3√(5x-2.6) x = (x3+2.6)
5
Putting these equations onto the graph along with the graph y=x I get the following graphs.
Pink line – y=x
Blue Line – g1 equation
Green Line – g2 equation
Finding Root A
Using g1
x0 = -1
x1 = -1.9661
x2 = -2.3164
x3 = -2.42057
X11(root) = -2.46099
Finding Root B
Using g2
x0 = -1
x1 = 0.32
x2 = 0.52655
x3 = 0.54920
x8(root) = 0.55401
Finding Root C
Using g1
x0 = 1
x1 = 1.33887
x2 = 1.59978
x3 = 1.75429
x17 (root) = 1.90698
All three roots have been found to five decimal places. They are:
Root A = -2.46099 Root B = 0.55401 Root C = 1.90698
All three roots have been found, but why does it depend on which rearrangement is used? It depends on the gradient of each rearrangement. For the iteration to work the gradient of the rearrangement must be between -1 and 1.
For example:
g1(x) = 3√(5x-2.6) g2(x) = (x3+2.6)
5
= (5x-2.6)⅓ dg2 = 3x2
dx 5
dg1= ⅓(5x-2.6)-⅔ ×5
dx
= 5/3
3√(5x-2.6)2
Root A ≈ -2.5
dg1 = 5/3 = 0.27 -1<x<1
dx 3√(5×(-2.5)-2.6)2
Iteration of g1 converges to find root A.
Root B ≈ 0.5
dg2 = (0.53+2.6) = 0.545 -1<x<1
dx 5
Iteration of g2 converges to find Root B.
Root C ≈ 1.9
dg1 = 5/3 = 0.46 -1<x<1
dx 3√(5×(1.9)-2.6)2
Iteration converges to find Root C.
An example of the iteration failing.
For the iteration to fail the gradient of the rearrangement must not be between -1<x<1.
Root A ≈ -2.5
x0 = -1
x1 = -0.52655
x2 = 0.54920
x3 = 0.55313
x (root) = 0.55401 = Root B
dg2 = ((-2.5)3+2.6) = -2.605 -1<x<1
dx 5
Therefore, the iteration does not converge to the root of A but to the root of B as the gradient of g2 is below -1. Below it is shown graphically.
Comparison of Methods
Now that I have applied all three methods successfully to my equations I will use the same equation of y= x3-5x+2.6 to find the same root. This will help me to comment on the relative success of: the ease of mathematics/General understanding, Use of calculator/software, speed of convergence and problems with starting points.
The graph of y= x3-5x+2.6 is shown below with 3 roots to the equation.
The table of values is given below:
The 3 roots of the equation found from the rearrangement method are shown below:
Root A = -2.46099 Root B = 0.55401 Root C = 1.90698
For this comparison I will be searching for Root A in every case.
Decimal Search Method.
Finding Root A
I know that root A of the equation y= x3-5x+2.6 lies somewhere between: x = -2.460993 and x =-2.460992. So taking the answer as the midpoint of the two I get: x = -2.4609925 (7 d.p.). But seeing as I only need the answer to 5 decimal places I get x = -2.46099 (5 d.p.). This corresponds with the same answer I got originally.
Answer Root A: -2.46099 (5 d.p.)
Error: -2.46099 + 0.000005
Error Bounds: [-2.460995, -2.460985]
For these error bounds to be valid there must be a change of sign when the values are input into the equation:
f(x) = x3-5x+2.6
f(-2.460995) = -0.00003
f(-2.460985) = 0.00141
There is a change of sign in the two answers so I can say the error bounds are valid.
Newton-Raphson
The Newton-Raphson formula is: X1=X0 - f(X0)
f’(X0)
f(X0) = x3-5x+2.6
f’(X0) = 3x2-5
X0 = -2
X1 = -2 - x3-5x+2.6 = -2.65714
3x2-5
X2 = -2.47948
X4 (Root) = -2.46099
As you can see this is the exact root and has found it in four iterations.
Conclusions
Ease of Mathematics
The mathematics required for the decimal search method is fairly basic. All that is required is to put values into the formula (substitution) and read of the values and find the change in sign. It is fairly simple to use and quite easy to understand.
The mathematics used in the Newton-Raphson method on the whole is more complicated than the decimal search method as basic concepts of differentiation is required. Difficulties occur with this method when more complex formulas are involved. For example, if I was required to differentiate sin, cos and tan I would have to start to question the method for people that find these difficult to differentiate. Therefore, the ease of this method is based around the complexity of the original equation and the ability to differentiate. The rearrangement method is quite simple as all that is involved is the ability to rearrange an equation. Also, a general understanding of which rearrangement is required so that the iteration converges to the required root.
Use of Hardware/software
When carrying out the decimal search method, I was reliant on a graphical calculator as it showed the suitability of an equation and gave me all the information for unit tables. The table and graph function was simple to use and very straightforward.
The Newton-Raphson method required me to use my graphical calculator to work out the value of the iterations from the formula. What made it easier was the memory function. Where I could store equations using “ANS” in place of X. I also used Autograph to demonstrate the Newton Raphson method. This was fairly simple to use and did not involve a large amount of time learning to use.
For the rearrangement method I used the calculator and the memory function. I stored the two different arrangements into my calculator and that allowed me to access the two equations quickly to find the roots. I also used autograph to demonstrate graphically the convergences.
Speed of convergence
Out of all three methods Newton-Raphson appears to converge to the root with the least number of iterations. Where it took four iterations for the Newton-Raphson method it took 11 iterations using the rearrangement method and took 5 iterations using the decimal search method. For decimal search method I classed one unit table from my calculator as 11 iterations as there are 11 calculations being worked out in one unit table. Therefore, there are many more iterations involved with decimal search which correlates with the length of time it takes to converge to the root. For the Newton-Raphson method I classed one iteration to be one calculation using the Newton-Raphson formula. I used my calculator to repeatedly press the execute button and this was used to calculate how many iterations there was. For the rearrangement method I classed one iteration to be one calculation using the iteration formula, whether it is g1 or g2. This was also a repeated process where I pressed execute has many times as required until I found the root to the degree of accuracy I required.
Problems with Starting Points
There were no problems with starting points in the decimal search method. In the failure of decimal search I had to recognise the f(x) lowering and then raising. For the rearrangement method the starting point mattered depending also on which g(x) to use. I had to view my graph to see which derivative of g(x) was near 1 or -1. I noticed if I selected the other g(x) then I would find another root. When using the Newton-Raphson method the starting value mattered greatly because I noticed if I started with a different value then a different root could have been found. Also with the Newton-Raphson method I could never use the starting value of “0” as the solution of the formula would be trivial as in we would be dividing by zeros. Autograph helped me solve problems with starting points as it showed where about the solutions were, without autograph I would have to try more than one value.
