I tabulated this one more time.
The other root of the equation can be found using this method. It is, to 5 significant figures, 1.1144.
Failure of the Change of Sign Method
The Change of Sign method only works for certain equations, e.g. where there is a change of sign or where a change of sign is shown in the first table of values. One equation where the Change of Sign method does not find the roots is y = 4x4-4x+1.
Newton Raphson Method
x3 – 10x + 6 = 0
The Newton Raphson Iteration works as follows:
It is based on the formula
F’(Xn) is F(Xn) differentiatied, so if F(Xn) = x3 – 10x + 6, than F’(xn) = 3x2 - 10. Iterations work by repeating a formula that eventually converges toward a root.
Xo is the original estimation of a root. Therefore we replace Xn with Xo.
My original estimate for the middle root is 3, so substitute 3 for Xo.
Therefore: f(Xn) = 33 – 10x3 + 6 = 3
And f’(Xn) = 3*32 – 10 = 17
X1 = 3 – (3/17) = 2.823529412 or 48/17
X2 = 2.803785064
X3 = 2.803542459
X4 = 2.803542496
X5 = 2.803542496
The other two roots of this equation are:
0.62434 & -3.4279, each to 5 significant figures.
This method can be illustrated graphically:
Failure of the Newton-Raphson Method
However, the Newton-Raphson method does not work for all roots. One example of an equation where the Newton Raphson method does not work is y = 2/X3+6.
Above shows that the graph cuts the x axis in the interval -1 < x < 0. It does not, however, cut at 0 as there is an asymptote there that the computer does not recognise. This is because at the origin the x value is 0, and in the equation 3 is divided by x. No number can be divided by 0 and therefore there is no point there and nothing can cross the y axis.
F(x) = 2/X5+6
F’(x) = 10/X4
Xo = -1
X1 = -1 – (((2/-15)+6)/(10/-14)) = -1.4
X2 = -3.5621
X3 = -100.105
X4 = -60254771.11
And so on, until it reaches -ve infinity.
This can be shown graphically.
Here you can see the tangent of Xo becoming steeper (veering towards –ve infinity).
Fixed Point Iteration
2x -x -3 = 0 is written in the form f(x) = 0
2x -x -3 = 0 can be rearranged in the form g(x) = x.
Eg. 2x – 3 = x
We can plot y = 2x – 3 against y = x, and where these lines intersect will give us the roots of the original equation.
From this graph we can estimate the root, and put it into the equation g(x) = x. In the same way as Newton-Raphson, the formula will converge to the root.
Xo, my original estimation for the lower root, is -3.
X1 = 2Xo – 3 = 2-3 – 3 = -2.875
X2 = 2-2.875 – 3 = -2.863686533
X3 = 2ans – 3 = -2.862613375
X4 = 2ans – 3 = -2.862511141
X5 = 2ans – 3 = -2.862500371
X6 = 2ans – 3 = -2.862500371
The root, to 5 s.f. is -2.8265.
Failure of the Fixed Point Iteration
This method only works on certain equations. When the method fails to converge to a root, it is because of the gradient of the curve when in the form x = g(x). The gradient must be <1 or >-1 at the root for the formula to converge.
One example of a failure of this method is using the equation used to demonstrate Newton Raphson.
x3 +10x -6 = 0 can be arranged to (x3-6)/10 = x.
However, when this is iterated to find the upper root, using 3 as Xo, the root converges to positive infinity.
X1 = (33+6)/10 = 3.3
X2 = (3.33+6)/10 = 4.1937
X3 = (X23+6)/10 = 7.9755
X4 = (X33+6)/10 = 51.33123
Etc…
This is because the gradient around the desired root is greater than 1. This is obvious when compared to the yellow line y = x, where the gradient is 1 exactly.
Comparing Methods
x3 – 10x + 6 = 0
Using Newton-Raphson Method, the upper root was found in 4 steps:
I will use the other two methods to see which method is quicker to converge to the root.
Using the Change Of Sign method:
Using Fixed Point Iteration Method
X3 – 10x +6 = 0
x = (10x-6)
Plotted against the graph of y = x.
Xo = 3
X1 = (10*Xo -6)^(1/3) = 2.884499141
X2 = (10*X1 -6)^(1/3) = 2.837463822
X3 = (10*X2 -6)^(1/3) = 2.81785521
X4 = (10*X3 -6)^(1/3) = 2.80959937
X5 = (10*X4 -6)^(1/3) = 2.806108843
X6 = (10*X5 -6)^(1/3) = 2.804630452
X7 = (10*X6 -6)^(1/3) = 2.804003818
X8 = (10*X7 -6)^(1/3) = 2.803738127
X9 = (10*X8 -6)^(1/3) = 2.80362546
X10 = (10*X9 -6)^(1/3) = 2.80357768
X11 = (10*X10 -6)^(1/3) = 2.803557417
X12 = (10*X11 -6)^(1/3) = 2.803548824
The quickest way this root was found was through Newton-Raphson, where it converged after 4 steps. The Change of Sign method found the root to 5 s.f. after 6 steps while the Fixed Point iteration took 12 steps. Therefore it seems the Newton–Raphson method is the most efficient.
However, the time it takes to set up and apply a method also affects it’s efficiency.
The Newton Raphson method took the least amount of steps to find the root, but also took the most time to substitute into the formula as the function had to be differentiated. Although this took a while, once the formula was in the calculator, it could easily be repeated for each Xn.
The Change of Sign method took 6 steps to converge to the root (up to 5 s.f.) but took by far the most time to work out. This was because the table on excel for each step had to be changed, while using the other methods a calculator could just re-iterate the chosen formula.
The Fixed Point iteration took more steps to converge to the root, twice that of Change of Sign and three times that of the Newton Raphson method. However, it was the quickest to find using hardware and software as the formula was easily re-arranged and could then be quickly written into and then re-iterated on a graphical calculator for each Xn.