I want the root that the arrow is pointing ,the root lies between x=0 and x=1.
x f(x)
0 0.1
0.1 0.0715
0.2 0.016
0.3 -0.0425
The root is between x=0.2 and x=0.3, and I am going to zoom the graph in to see I am correct or not.
If my prediction is correct, my calculations above have found a wrong root (the blue arrow), which is not the root I want (the green arrow). The Decimal Search method has failed to find the root that I want from 5x^4+x³−2x²−0.1x+0.1=0. This is because the roots are so near, there are two roots in one interval, no matter where we set the starting value of x is, we will always miss the other root. Also, as the g'(x) there is diverging, the root found will usually the wrong root. Therefore, to avoid this, we should try both starting value at both end of the interval, but it really consume time to do it.
In conclusion, the less steep the grdient, the faster the coverging is. If the gradient is steep, the root can also be found but not as efficient as a less steep g'(x).
Solving 3x^5+5x²-1=0 using the “Rearrangement Method” of fixed point iteration
The graph of the equation is shown below:
I will rearrange f(x)=0 in the form of x=g(x). As my equation is 3x^5+5x²-1=0 , there are many possible rearrangements of this. Here is two of them (A&B).
Rearrangement A: 3x^5+5x²-1=0
x^5= (1- 5x²)/3
x= [(1- 5x²)/3]^(1/5)
I will draw the graph of the equation y=g(x)=[(1- 5x²)/3]^(1/5) on the Autograph software and the line y=x. This is shown below:
And I am going to show how this method work and it is shown below:
The blue line is approaching to the root, and that is the answer of f(x)=0
Rearrangement B: 3x^5+5x²-1=0
x²=(1-3x^5)/5
x=√[(1-3x^5)/5]
On Autograph software, I can draw the equation y=g(x)= √[(1-3x^5)/5]and also the line y=x. The graph is shown below:
I want to find the intersection of the arrow
After all, both seems can work out the root and I have chosen Rearrangement B, which is
x=√[(1-3x^5)/5]. So my iterative formula for this rearrangement is xn+1=√[(1-3xn^5)/5]
I can see from my graph above that the point of intersections of the two lines is between x=0 and x=0.8(approximately). So my starting value for x(x0) would be 0.
x0 = 0 ( I substitute x0 = 0 into iterative formula to work out x1 )
x1 = √[(1-3(x0)^5)/5] = 0.4472136
x2 = √[(1-3(x1)^5)/5] = 0.4350481
x3 = √[(1-3(x2)^5)/5] = 0.4366342
x4 = √[(1-3(x3)^5)/5] = 0.4364376
x5 = √[(1-3(x4)^5)/5] = 0.4364621
x6 = √[(1-3(x5)^5)/5] = 0.4364590
x7 = √[(1-3(x6)^5)/5] = 0.4364594
x8 = √[(1-3(x7)^5)/5] = 0.4364594
I can see convergence from x4 , and there is no change between x7 and x8 for this number of decimal places. I know that this method has worked successfully to find a root. This is shown graphically below:
Therefore, my root is x=0.43646( 5d.p.)
I know that using Rearrangement B can help me find a root of 3x^5+5x²-1=0. However, Rearrangement A of this function would not find the same root as I have found. This is explained with a diagram with of Rearrangement A and its iterative formula below. This failure is shown graphically below:
From the graph above, I can see that there is no convergence to that particular root I am looking for, but I want to test it again by substitution into the iterative formula of Rearrangement A, which is
y= [(1- 5x²)/3]^(1/5) and the starting value for x(x0) is 0, the same as before.
Zx0 = 0
x1 = √[(1-3(x0)^5)/5] = 0.8027416
x2 = √[(1-3(x1)^5)/5] = -0.9417235
x3 = √[(1-3(x2)^5)/5] = -1.0274040
x4 = √[(1-3(x3)^5)/5] = -1.0735437
Immediately, I can see that I can see that there is really no convergence to that particular root I am looking for(the one in Rearrangement B and my observation from the graph is correct. Therefore, I have found a rearrangement of the same equation where the iteration has failed to converge to the required root as the gradient ( g'(x)) there is diverging. In conclusion, the less steep the gradient, the more efficient it is. If the gradient is steep, it will still work but not as efficient as having a less steep gradient. It will not work only if g'(x) >1 or g'(x) <-1
Solving x^4+x³-1=0 by using the “Newton-Raphson” method
As I will solve the above equation by “Newton-Raphson” method, first of all I need to draw the graph of the equation out and it is shown below:
I can see that there is two roots in this equation and the iterative formula for the “Newton-Raphson” method is:
xn+1=xn-f(xn)/f’(xn)
For my equation, f’(xn) = 4x³+3x² when my function is differentiated to find the gradient function. The iterative formula I will use to find the roots of this function is:
xn+1=xn - [(xn ^4+xn ³-1=0)/( 4xn ³+3xn ²)]
I will start by finding out the negative root first. By the graph above, I can see that the root is between -1 and -2, therefore, I will set x0 = -1 as my starting value of x.
x0 = -1
x1 = x0 - [(x0 ^4+x0 ³-1=0)/( 4x0 ³+3x0 ²)] = -2
x2 = x1 - [(x1^4+ x1 ³-1=0)/( 4x1 ³+3x1 ²)] = -1.65
x3 = x2 - [(x2^4+x2 ³-1=0)/( 4x2 ³+3x2 ²)] = -1.454113738
x4 = x3 - [(x3 ^4+x ³-1=0)/( 4x3 ³+3x3 ²)] = -1.387577585
x5 = x4 - [(x4 ^4+x4 ³-1=0)/( 4x4 ³+3x4 ²)] = -1.380357406
x6 = x5 - [(x5 ^4+x5 ³-1=0)/( 4x5 ³+3x5 ²)] = -1.380277579
x7 = x6 - [(x6 ^4+x6 ³-1=0)/( 4x6 ³+3x6 ²)] = -1.380277569
x8 = x7 - [(x7 ^4+x7 ³-1=0)/( 4x7 ³+3x7 ²)] = -1.380277569
I can see some convergence from x6. There has been no change in the x-values between x7 and x8 for this number of decimal place. I know that this method for finding the root has worked and I am going to show how it works graphically in this root. It is shown as below:
Now I am going to find the positive root of this function. The starting value (x0) is 1 as it lies between x=0 and x=1 when f(x)=0.
x0 = 1
x1 = x0 - [(x0 ^4+x0 ³-1=0)/( 4x0 ³+3x0 ²)] = 0.857142857
x2 = x1 - [(x1^4+ x1 ³-1=0)/( 4x1 ³+3x1 ²)] = 0.821252204
x3 = x2 - [(x2^4+x2 ³-1=0)/( 4x2 ³+3x2 ²)] = 0.819179147
x4 = x3 - [(x3 ^4+x ³-1=0)/( 4x3 ³+3x3 ²)] = 0.819172513
x5 = x4 - [(x4 ^4+x4 ³-1=0)/( 4x4 ³+3x4 ²)] = 0.819172513
I can see some convergence from x3. There has been no change in the x-values between x4 and x5 for this number of decimal place. I know that this method for finding the root has worked and I am going to show how it works graphically in this root. It is shown as below:
As the method I have used to find the roots, the roots are x=-1.380277569 and x=0.819172513, both are in 9 decimal places accuracy. Therefore, the maximum error is 0.000000005
However, sometimes the Newton-Raphson method would not work, and examples are shown below:
Example
I want to solve the equation of x³+3x²−1=0 and find the first negative root of that which graph is shown below:
The f '(x) = 3x²+6x, so the iterative formula is
xn+1=xn - [(xn³-+3xn²−1)/ (3xn²+6xn)]
As the graph shown above, the root is between x=0 and x=-1, so I take x0 = 0 as the starting value and it is worked as below:
x0 = 0
x1 = undefined
The Newton-Raphson method does not work because when I substitute x=0 into the iterative formula, f '(x)=0 which f(x)/f '(x) is undefined. Therefore, the Newton-Raphson method would not work whenever f '(x)=0.
In spite of the example above, there are still situations in which Newton-Raphson method will not work, they are:
- the function is discontinuous
- a bad starting value of x
- the function is not defined over the whole real number(a point outside the domain of the function)
Comparison of methods
To compare which method work the best, I am going to solve the same equation with 3 different methods. The equation is x³-3x-1=0, the graph is shown below:
I want to find the negative root of the equation by Decimal Search method and the root lies between x=0 and x=-1
x f(x)
-0.1 -1.299
-0.2 -0.408
-0.3 -0.127
-0.4 0.136
I can see change of sign is between x= -0.3 and x= -0.4
x f(x)
-0.31 -0.09979
-0.32 -0.07277
-0.33 -0.04594
-0.34 -0.01930
-0.35 0.00713
The change of sign is between x=-0.34 and x=-0.35
x f(x)
-0.349 4.491451 x 10^-3
-0.348 1.855808 x 10^-3
-0.347 -7.81923 x 10^-4
The change of sign is between x=-0.347 and x=-0.348
x f(x)
-0.3471 -3.18056 x 10^-4
-0.3472 -2.54210 x 10^-4
-0.3473 9.61518 x 10^-6
There is a change of sign between x=-0.3472 and x=-0.3473
x f(x)
-0.34730 9.61518 x 10^-6
-0.34729 -1.67664 x 10^-5
There is change of sign between x=-0.34729 and x=-0.34730. I can stop it now as only want a root of 5 decimal places and the root is -0.347295. The maximum error is 0.000005.
Now, I use the Rearrangement method trying to find the same root.
Rearrangement 1: x= (x^3 -1)/3
I set my starting value for x is 0
x0 = 0
x1 = (x0^3-1)/3= -0.333333
x2 = (x1^3-1)/3= -0.345679
x3 = (x2^3-1)/3= -0.347102
x4 = (x3^3-1)/3= -0.347273
x5 = (x4^3-1)/3= -0.347294
x6 = (x5^3-1)/3= -0.347296
x7 = (x6^3-1)/3= -0.347296
I can see there is no difference in x6 and x7 and the root found out is the same as that in Decimal Search. The root is -0.34730 (5d.p.) and the error is 0.000005.
I am going to use Newton-Raphson method to try to find the same root as well:
The iterative formula of the equation:
xn+1=xn - [(xn^3-3xn-1)/ (3xn^2-3)]
I think that a good starting value for x0 would be 0
x0 = 0
x1 = xn0- [(x0^3-3x0+1)/ (3x0^2-3)] = -0.333333
x2 = x1 - [(x1^3-3x1+1)/ (3x1^2-3)] = -0.347222
x3 = x2 - [(x2^3-3x2+1)/ (3x2^2-3)] = -0.347296
x4 = x3 - [(x3^3-3x3+1)/ (3x3^2-3)] = -0.347296
For the Newton-Raphson method, I find the same root as the other methods had found. Therefore, the root for all methods is -0.34730 (6d.p.) and the error is 0.000005.
Now, I can compare the efficiency of each methods.
After a lot of examples, I found that the Decimal Search method was the simplest out of the three, as it does not involve any iteration, so mistakes with iterative formulas and rearrangements are not applicable as with the other two methods used. However, the efficiency is not that good, though it is
simple, it has to work many steps if an accurate root is needed (e.g. 5 decimal place), it really consume time to have an accurate root.
Both the Newton-Raphson method and the Rearrangement method were fixed point estimates and involved an iterative process. Therefore, these methods were very similar. However, these two methods differ because there is a specific formula for the Newton-Raphson method. Although the Newton-Raphson method gave the much more rapid rate of convergence. In fact, the Newton-Raphson method gave the most rapid rate of convergence to 6d.p. , whereas, for the Decimal Search method, it took me very many calculations to converge to 5d.p. . So the Decimal Search method is not as efficient as the iterative methods( Rearrangement method and Newton-Raphson method). However, it was really easy to make mistakes on the calculator due the order of the terms in the iterative formulae.