As can be seen, there are two roots in this interval, 2.1 and 2.2, therefore the initial table did not pick up any change in sign, as overall the two changes cancelled out.
Newton-Raphson Method
The Newton-Raphson method is a process whereby a rough approximation of the root is made (called x1) and the tangent to the curve at x1 is drawn. The point on the x-axis where this tangent hits is made x2 (see diagram) and again a tangent to the curve is drawn at x2. The process continues until the root is found.
In order to set up a table of values on order to quickly find the root, a calculation must be created to find x2 quickly from x1. This is done using the following equations.
The gradient of y=f(x) at a certain point P on the graph whose x-coordinate is x1 is equal to both f1(x1) and also f(x1)-0
x1-x2
Therefore, f1(x1)=f(x1)
x1-x2
and x2= x1-f(x1)
f1(x1)
So, in order to calculate the next estimate of x, called xn+1, place the value for xn into this equation:
xn+1= xn- f(xn)
f1(xn)
This method was used to find all three roots for the function
f(x)=2x3-13x2+7x+11
The following tables of data could be obtained by the use of the formula:
The root is therefore found to be -0.66529 ± 0.000005, as the calculations are only accurate to 5 decimal places.
The finding of this root is illustrated in the diagram on the following page.
Further roots can no be found, using the same process but with a different initial xn.
This table shows that the function has a root of 1.44528 ± 0.000005
This table shows that the function has a root of 5.72001 ± 0.000005
Failure of Newton-Raphson Method
The Newton-Raphson method can fail to find the root of a function, as in the following example. The function is f(x)=20-((x-3)2+0.05)-1
It is clear from simply looking at the function that one root is going to be x=3. However, if the Newton-Raphson method is used, the following data is obtained
As can be seen on the diagram below, these figures are clearly divergent, which means that xn+1 is further from the root than xn, and so are no use in finding the root of the function.
Fixed Point Iteration
This method to find the roots of a function is done by rearranging the function f(x) into the form x=g(x). This can be explained with an example. If the expression xn+1=0.8+2.6/xn is used to create a large table of values for xn+1, it is found that after x50 and x51 are both 2.061324773. This means that xn+1 converges on this figure. If we let the limit L=2.061324773, then L satisfies the equation L=0.8+2.6/L and therefore L2-0.8L-2.6=0 and therefore L is a root of f(x). The function that I will be finding the roots of is f(x)=x3-4x2-7x+11. In order to find the roots, the equation f(x)=0 must be rearranged into the form x=g(x). Therefore, g(x) = (x3-4x2+11)/7
Now, xn+1=xn3-4xn2+11 is used to generate a table of values for xn, the results
7
are as follows:
As can be seen, the value for xn+1 slowly converges on 1.082809. Therefore, one of the roots of the function f(x)=x3-4x2-7x+11is 1.082809 ± 0.0000005. This is illustrated on the graph on the following page, where a spiral convergence is clearly displayed.
The function g(x) has a gradient of g1(x), which is
g1(x) = (1/7)(3x2-8x)
If the root 1.082809=d,
g1(d)= -0.735
Therefore, |g1(d)|<1 and the sequence converges
Failure of Fixed Point Iteration
There are certain functions where the sequence does not converge on a root. An example of this is the function f(x)=x3-4x2-3x+11. When rearranged,
g(x) = (1/3)(x3-4x2+11)
The following data can then be obtained using the aforementioned formula.
It would appear that the sequence does not converge upon any one root. A diagram shows that this is indeed the case.
After 400 calculations, the sequence has not got close to converging on the root. The closest x value to the root appears to be x1 and so it can reasonably be assumed that it will never converge.
Looking again at g1(x), in this case
g1(x) = (1/3)(3x2-8x)
and as the root is approximately 1.6, d=1.6 and
g1(d) = -1.707 (to 3 decimal places)
Therefore |g1(d)|>1 and the sequence does not converge.
Comparison of Methods
The function whose roots will be found by every method was chosen to be f(x)=2x3-13x2+7x+11, whose three roots have already been found using the Newton-Raphson method. Using the decimal search method,
It is clear that there is a root in the interval [1, 2]
The root is in the interval [1.4, 1.5]
The root is in the interval [1.44, 1.45]
The root is in the interval [1.445, 1.446]
As the root is in the interval [1.445, 1.4455] and all the numbers within that range, when rounded to 3 decimal places, equals 1.445, then one of the roots of that function is 1.445 correct to 3 decimal places. This result agrees with the Newton Raphson method which gave the root to 5 decimal places as 1.44528 which, when rounded to 3 decimal places, gives 1.445
Using the fixed point iteration by rearrangement method, the function can be rearranged to give
xn+1 = √((2xn3+7xn+11)/13)
When data is obtained from this calculation, the following sequence is observed
As can be seen, the sequence clearly converges on 1.445281, and thus agrees with both of the other methods as to the location of this root for this function, as when rounded to 3 decimal places, this becomes 1.445.
Of the three methods, it is clear that the method that is the slowest to converge on the root is the decimal search method. The quickest to converge is the Newton-Raphson method, closely followed by the fixed point iteration. However, although both iteration methods can find the root correct to several decimal places very quickly, there is more initial work in order to start using these methods than there is for the decimal search. Formulae must be rearranged or new formulae constructed in order to begin the search. Also, a lot of the speed of the two iteration methods is due to the ability of a computer to quickly do repeat calculations many times over. They are well suited to the use of computers whereas the decimal search method is relatively slow even with the use of computers, as it would take a human to spot the change in sign that determines the next set of calculations.
Finally, there is no reason why the decimal search method could fail when used in conjunction with an graph plotted accurately by calculator or computer to determine the rough approximations of the roots, whereas with the other two methods there are functions where it is impossible to obtain an estimate of the roots.
