Newton-Raphson
Finding a root
The graph of y=f(x):
Roots of f(x)=0 exist in the intervals [-2,-1] and [0,1].
f(x)=(x2+0.9x-2.52)-1+1
f’(x)=-(2x+0.9)(x2+0.9x-2.52)-2
We shall find a root by taking x1=1
f(0.862435)=0.000014
f(0.862445)=-0.000012
The change of sign indicates that the root is 0.86244±0.000005.
Graphical illustration
The following is a graphical illustration of the process for finding this root with x1=1:
Finding the remaining root
The other root can be found using x1=-2.
x=2.62488 (5d.p.)
Failure of the Newton-Raphson method
The method fails for the same function if x1=0
The value diverges, despite the starting value being close to the root. This is because the tangent crosses the asymptote, as shown below:
Fixed point iteration with x=g(x)
Finding a root
f(x)=x5-4x+3
The graph of y=f(x):
We shall rearrange the equation into the form x=g(x) to find roots of f(x)=0.
0= x5-4x+3
x5=4x-3
x=(4x-3)1/5
xn+1=(4xn-3)(1/5)
We shall take a starting value of x1=-1.
x=-1.56004 (5d.p.)
Graphical illustration
The graph below shows the lines y=x and y=g(x). The lines intersect at the roots of f(x)=0.
The importance of the magnitude of g’(x)
For a root of f(x)=0 to be found by fixed point iteration, g'(x) must be between -1 and 1 near the root. The diagram above shows that the gradient of g(x) is within this range at the root which is found.
Failure using a different rearrangement
0= x5-4x+3
x=(x5+3)/4
xn+1=(xn5+3)/4
Take a starting value of x1=-2
The reason for the failure is demonstrated below. The value of g'(x) at this point is far greater than 1, so the iterations do not converge.
Comparison of methods
I will compare the methods with the equation f(x)=x5-4x+3. One root of f(x)=0 was found using fixed point iteration
-1.56004 (5d.p.)
Finding the root with a change of sign method
The desired root exists in the interval [-2,-1], as shown by the first graph in the fixed point iteration section.
Change of sign indicates root exists in interval [-1.6,-1.5]
x=-1.55±0.05
x=-2 (0d.p.)
Change of sign indicates root exists in interval [-1.57,-1.56]
x=-1.565±0.005
x=-1.6 (1d.p.)
Change of sign indicates root exists in interval [-1.561,-1.560]
x=-1.5605±0.0005
x=-1.56 (2d.p.)
Change of sign indicates root exists in interval [-1.5601,-1.5600]
x=-1.56005±0.00005
x=-1.560 (3d.p.)
Change of sign indicates root exists in interval [-1.56005,-1.56004]
x=-1.560045±0.000005
x=-1.560 (3d.p.)
Change of sign indicates root exists in interval [-1.560041,-1.560040]
x=-1.5600405±0.0000005
x=-1.56004 (5d.p.)
Finding the root using Newton-Raphson
f’(x)=5x4-4
-1.56004 (5d.p.) is therefore a root of f(x)=0.
Speed of convergence
This shows that Newton-Raphson converges the quickest. In this case fixed point iteration using x=g(x) was the next fastest method, though in some cases its rate of convergence can be very slow: e.g., using the rearrangement x=(4x-3)1/5, it takes 19 iterations to find the root 1.002 of f(x)=0 to three decimal places.
Unlike the other two methods, the change of sign method takes a similar length of time for any equation. This means that it may be faster or slower than using the rearrangement x=g(x).
Ease of use
The decimal search is the easiest method to automate, either using a spreadsheet or when programming. Newton-Raphson requires the function to be differentiated, while x=g(x) requires it to be rearranged. A decimal search, in contrast, just requires calculations, which can easily be done using a computer. It does, however, experience problems when the curve of y=f(x) just touches the x axis, there are multiple roots in a small interval, or there is a discontinuity in f(x).
The Newton-Raphson method is more difficult to automate because f'(x) must be found. Some computer programs, such as Autograph, can carry out the iterations for you, which, if they are available to you, can make it easier to use than a decimal search. Care must be taken when choosing a starting value and asymptotes can cause the method to fail. In some cases you may not be able to differentiate f(x).
Fixed point iteration with x=g(x) can be carried using programs like Autograph. It must still be rearranged manually though, and a large proportion of rearrangements fail. Because of this it is the most difficult method to use, especially if you do not have software to automate the iterations.
Overall the change of sign method is the easiest as it is purely numerical calculation. Newton-Raphson is the second simplest because it fails far less often than x=g(x).