There is a root in the range (2.5615, 2.5616)
Now use decimal search and Excel within the interval [2.5615, 2.5616]
There is a root in the range (2.56155, 2.56156)
Error bounds
I saw from my last table in Excel that the root lies in range (2.56155, 2.56156)
So the solution bounds are 2.56155 and 2.56156
I can also write the solution bounds as 2.561555 ± 0.000005. These are the error bounds.
Approximate value of root
The root is 2.5615 to 4 decimal places.
Illustrate the method graphically
The fact that f(2) is negative and f(3) is positive tells us the graph must cross the x axis between 2 and 3. Hence there is a root in the range (2, 3)
This graph shows us how the root is finally trapped in the range (2.56155, 2.56156)
What can cause failure?
One reason that the decimal search can fail is that there are several roots very close together in the same integer range.
For example, the equation y=54x³−225x²+309x−140
There appears to be only one root in the interval (1, 2) but there are three.
After finding the first root we might miss the other two.
There are three roots close together.
We only get one change of sign when we do the integer search.
The search will find the first root 1.6666 in this interval
Unless we have drawn a graph there is a big danger we may miss the other two roots.
Newton Raphson
An example is given: y=x³−2x²+1
We can see there are roots in the intervals [-1, 0] and [1, 2]
We will find the root in the interval [-1, 0]
Xn+1= Xn–f(Xn)/f’(Xn)
If f(X)= x³−2x²+1 then f’(x)= 3x²-4x
Xn+1= Xn–( Xn ³−2 Xn ²+1)/ (3 Xn ²-4 Xn)
Using our example : y=x³−2x²+1
To find the root in the interval [-1, 0] we can take x1 =-1 or x1 = 0
I will use x1 = -1
Can see that root is near to -0.6180 to 4 sf
Using Newton Raphson and Autograph Solver to find the root in the interval [-1, 0] Solution: x=-0.61803399, y=0
Then find the root in the interval [1, 2]
To find the root in the interval [-1, 0] we can take x1 =1 or x1 = 2
I will use x1 = 2
Can see that root is near to 1.6180 to 5 sf
Then 1 is one of the roots of the equation.
Newton Raphson converges to a value near to -0.6180
The Newton Raphson does NOT automatically trap the root between two values
In our example it looks like the root is just below 1.618034. We proposed it was 1.6180 to 5sf
We need to use the change of sign method to trap the root between two solution bounds
We evaluate f(1.61805) and f(1.61795)
We can also write the solution bounds as the error bounds 1.6180± 0.00005
The example below shows that NR fails to find the root.
y=x³−5x²+4.67x−0.418
The turning point near to x1 caused the divergence
Xn+1= Xn–f(Xn)/f’(Xn)
If f(X)= x³−5x²+4.67x−0.418 then f’(x)= 3 x²-10x+4.67
Xn+1= Xn– (Xn ³−5 Xn ²+4.67 Xn −0.418) / (3 Xn ²-10 Xn +4.67
X=g(x) method
Example: y=−3x³−x²+x+2
The solution is near to 1
Take x1 = 1
Roots are given by −3x³−x²+x+2=0
Rearranges to:
3x³= −x²+x+2
x³ = 1/3(−x²+x+2)
x= [1/3(−x²+x+2)]1/3
Iteration is Xn +1 = [1/3(−Xn ²+ Xn +2)]1/3
Using our example and finding the root in the interval [0, 1] , using X1=1
Can see that root is near to 0.8736 to 4 sf
Since g(x) = [1/3(−x²+x+2)]1/3
g‘(x) =1/9*((-x^2+x+2)^(-2/3))*(-2*x+1)
The root was x= 0.8878
Hence g‘(root) = -0.0.03618
Since -1< g'(x) <0 then we would expect the iteration to converge as a Cobweb
y=−3x³−x²+x+2
Rearrange to x=3x³+x²-2 leads to failure.
x1=1
x’=9x^2+2x
g’(0.8878)= 8.86929956
Since g‘(root) >1 then we would expect the iteration to diverge away from the root as a staircase.
Comparison
I am going to compare advantages and disadvantages of all three methods.
y=−3x³−x²+x+2
There are three intervals containing roots:
(-0, 1)
To find the root in the interval (0, 1)
Decimal search
The root is0.8878 to 4 s.f.
Newton-Raphson
- To find the root in the interval [0, 1] we can take x1 =0 or x1 =1
I will use x1 = 1
xn+1= xn - (3xn^3+xn^2-xn-2)/(9xn^2+2xn-1)
Can see that root is near to 0.8878 to 4 sf
x = g(x)
Take x1 = 1
Roots are given by −3x³−x²+x+2=0
Rearranges to:
3x³= −x²+x+2
x³ = 1/3(−x²+x+2)
x= [1/3(−x²+x+2)]1/3
-
Iteration is Xn +1 = [1/3(−Xn ²+ Xn +2)]1/3
Using our example and finding the root in the interval [0, 1] , using X1=1
Can see that root is near to 0.8736 to 4 sf
Each method achieved the same accuracy in:
16 calculations for change of sign
4 calculations for Newton Raphson
1 calculation for x = g(x)
The x=g(x) method was the fast one in this particular example
Change of sign was much slower than NR and x=g(x)
If I only had a scientific calculator – the change of sign method is easier to operate.
If I also have Excel - the x=g(x) method is easier because there was only one calculation.
If I also have Autograph – the x=g(x) method is easier because there was only one calculation..