The root therefore lies in the interval [1.879385,1.879386]. Therefore the root of the equation f(x)=0, in the interval [1,2] is:
x=1.87939 to five decimal places.
I have confirmed that this root is correct to five decimal places because I have confirmed that it lies in the interval [1.879385,1.879386]. This means that
1.879385<x<1.879386;
This directly tells us that x>1.879385, therefore x is not less than 1.87939 to five decimal places because it is equal to at least 1.87939 to five decimal places.
It also implies that x<1.879395, confirming that x is not greater than or equal to 1.87940 to five decimal places. If x≥1.879395, then x would be at least 1.87940 to five decimal places.
Thus the root has been proven to be 1.87939 to five decimal places as a result of doing the decimal search method for values of x to six decimal places.
If I was trying to find all the roots of the equation 3x3+2x2-x-2.5=0, then the change of sign method would fail. Take f(x)=3x3+2x2-x-2.5
The table shows values of f(x) at integer values of x from -5 to 5.
Using the change of sign method, there is only one change of sign and it lies in the interval [1,2]. Therefore, using this method, only the root between x=1 and x=2 will be found. It is however evident from the following graph of y=f(x) that there are three roots to the equation f(x)=0, because the graph crosses the x-axis three times.
This occurs because although the graph crosses three times, two of those crossings are in the same interval on the table. A change of sign occurs when the graph crosses the x-axis. This graph crosses the x-axis twice in the interval [-2,-2]. This results in the change of sign occurring twice in that interval, resulting in no change of sign detected in the table, because the interval gap is wider than the gap between the roots. This can be illustrated graphically.
The red lines indicate from the x-axis what the y values, which are equal to f(x) values, would be, for integer values of x from -2 to 2. This would therefore represent what values for f(x) would be in the table displayed earlier for integer values of x from -2 to 2. As one can see, only the red line from x=2 goes up, implying that all f(x values resulting from integer values of x lower than -2 are negative. In the interval [1,2] there is an evident change of sign, shown by the opposite direction of red lines from the x-axis. In the interval [-2,-1], although the graph crosses the x-axis here, because it crosses twice, both x=-2 and x=-1 result in negative f(x) values. Therefore two roots here are undetected. This is an example of where the change of sign method can fail.
Newton-Raphson Method
I want to find the roots of the equation x3-7x-4=0 to seven decimal places.
Consider the function f(x)=x3-7x-4; hence I want to find the roots of the equation f(x)=0.
If x1 is an approximate root of the equation f(x)=0, the Newton-Raphson formula for finding a second approximation x2 from x1 is
x2 = x1 – (f(x1)/(f /( x1))
In the case f(x)=x3-7x-4, the Newton-Raphson formula simplifies to:
x2 = (2x13+4)/(3x12-7)
The graph y=f(x) is shown:
There are three visible roots to the equation. I will take an approximate root for the root in interval [2,3] to be 3. As I shall explain later, the Newton-Raphson iteration will hopefully converge to the root in interval [2,3].
Therefore taking x1=3, the following iteration is constructed:
Each value is done to eight decimal places by Microsoft Excel. As one can see, the iteration has appeared to converge to 2.89510652 in three steps.
Therefore using the Newton-Raphson method, the root to the equation x3-7x-4=0 in the interval [2,3] is 2.8951065 to seven decimal places.
Looking at the graph, I will apply the same method and obtain the other two roots, using the approximate roots, -3 and -1 to begin with.
Therefore the roots to the equation x3-7x-4=0 are:
x= 2.8951065, -0.6027049, -2.2924016 (all to seven decimal places)
This method can be illustrated graphically. In order to find the root in the interval [-3,-2], I have chosen an approximate root to be -3, because it is roughly close to the real root in the interval [-3,-2] and is closer to this root than the other ones. Following is part of the graph y=x3-7x-4; I have taken y to be equal to f(x). The pink line represents the Newton-Iteration.
The next approximation is given by
x2 = x1 – (f(x1)/(f /( x1))
This works because the gradient of the line drawn is f /( x1).
The gradient equals the change in y over the change in x, i.e. y/x.
Since the change in y = f(x), as defined earlier:
f /( x1)= f(x)/x
therefore
f(x)/ f /( x1)=x
The x given by this equation is the change in x from x1 and x2. To get the x-co-ordinate of x2 one has to subtract this change in x from x1.
i.e. x2 = x1 – (f(x1)/(f /( x1))
This method can also ‘tangent’ sliding, because for an approximation of the root xn, the next approximation is obtained by making a tangent at (xn, f(xn)) and taking it to be the value where the tangent crosses the x-axis (i.e. ‘sliding’ down the tangent).
The reason the next iteration in the example above is used more accurate is because the tangent does not ‘cut across' the curve, but it is in the direction the curve is curving towards.
The next approximation in the general case may not be more accurate than the last. This is shown below.
As one can see, x1 which equals 2, is more accurate than x2 which equals four. The root the iteration converges to is 2.8951065. This occurs because the absolute value of the gradient formed at the curve is very small, i.e. it is very shallow, therefore the tangent touches the x-axis further away. However, this method still works because the tangent formed at (2,-10) leads the iteration to (4,0), allowing tangent sliding from the right side of the curve, which brings us back to a similar situation.
I can confirm earlier that I had found the roots using this method to seven decimal places. I had claimed that the roots to the equation x3-7x-4=0 are:
x= 2.8951065, -0.6027049, -2.2924016 (all to seven decimal places)
Primarily Excel gave 8 figures after the decimal point, so I could confirm that there would not be a rounding error when giving the roots to seven decimal places. I therefore rounded the values of x to seven decimal places. I can confirm that these are correct to seven decimal places using the decimal search method.
I therefore wish to confirm that x=2.8951065 to seven decimal places is a root of the equation x3-7x-4=0.
Therefore using the decimal search method, the root lies in the interval [2.89510651,2.89510652], therefore to 7 decimal places, it is equal to 2.8951065. Therefore I have confirmed the accuracy to one of the roots the Newton-Raphson method produced.
An example of a failure of this method is as follows:
Suppose I want to find a particular root of the equation x3-4x+1=0. Let f(x)= x3-4x+1 and a graph of y=f(x) is drawn below.
I want to find the root of the equation in the interval [0,1]. 1 is a decent first approximation, as it is closer to the root near 0, than the root at 2.
However if one uses 1 in the iteration the following occurs:
i.e. it does not converge at the required root.
To illustrate this graphically (the pink line represents the iteration):
This happens because the gradient of the curve at x=1 is very shallow, therefore the tangent touches the x-axis ‘too far’ to the left. The gradient is shallow at this value for x as well, therefore the new tangent touches the x-axis ‘too far’ to the right, causing convergence at the root furthest to the right (the root with the biggest value), 2.8951065. Therefore the method fails to find the particular root I wanted it to find despite taking a starting value close to it.
Rearranging f(x)=0 in the form x=g(x)
I want to find the roots of the equation x3-3x+1=0 to seven decimal places.
Consider the function f(x)=x3-3x+1; hence I want to find the roots of the equation f(x)=0.
One way to rearrange this equation is:
x3+1=3x
therefore x=(x3+1)/3
Therefore one possible iteration that emerges from the original equation is:
xn+1=(xn3+1)/3
Let g(x)=(x3+1)/3
A graph of the curves y=g(x) and y=x is shown:
The points at which these two curves meet have the same x-values as the roots to the equation x3-3x+1=0.
This is because:
At the intersection points, y=g(x) equals y=x
therefore, (x3+1)/3 = x
therefore, x3+1 = 3x
therefore, x3-3x+1 = 0, which is the equation to which the roots we are trying to find.
Therefore the roots of the equation have the same x-values as these intersection points.
Using the formula generated at the beginning,
xn+1=(xn3+1)/3
one can obtain values for the roots. I want to find the root in the interval [0,1]. The table below shows the iteration being generated, using an initial approximation of the root. e.g. x2 was generated using (x13+1)/3, x3 was generated using (x23+1)/3, and so on.
Therefore, for x3-3x+1=0, the root in the interval [0,1] is:
x=0.3472964 (to seven decimal places)
The convergence of this rearrangement can be demonstrated graphically. Part of the graph of the curves y=x and y=g(x) is shown. Using x1=1, the iteration is represented by the red line:
The approximations get better as the iteration progresses. This is because the iteration converges to the intersection, which has the same x-value as the root.
If g(x)=(x3+1)/3
then, g/(x)=d/dx (x3/3 – 1/3)=3x2/3= x2
The root we have already found is x=0.3472964 (to seven decimal places). If we apply function g(x) to this root, (i.e. square it,) we obtain 0.1206148 (to seven decimal places). The absolute value of g/(x)<1, therefore convergence to the root, x=0.3472964, will occur provided that a suitable initial value is chosen.
It converges rather than diverges at the point shown because from one approximation to the next, the change in y is less than the change in x, i.e. the gradient is less than 1. For example, in the graph above, AC is smaller than AB.
Taking the equation x3-3x+1=0, another rearrangement would be as follows:
x3-3x+1=0
therefore, x3= 3x-1
therefore, x= (3x-1)/x2
Therefore the iteration that emerges is:
xn+1= (3xn-1)/xn2
Let h(x)= (3x-1)/x2
I wish to find the same root using this rearrangement. The iteration is carried out as follows, using 0.5 as x1; this is a sensible first approximation as it is closer to the required root than the other roots. x2 was generated using (x13+1)/3, x3 was generated using (x23+1)/3, and so on.
Instead, the iteration has converged on another root, in the interval [1,2]. The iteration has failed to converge to the required root. If instead I choose an initial approximation less than the required root, I get the following result. I choose x1 to be -1.
#NUM! means that the number is too large to display. Clearly, divergence occurs. The iteration fails to converge to the required root, whatever the initial approximation.
h(x)= (3x-1)/x2
h/(x)= (2-3x)/x3
The reason that the iteration fails to converge to the required root is because:
The required root=0.3472964 (7d.p.)
h/(0.3472964)= 22.8725661 (7d.p.)
h/(x)>1, therefore the iteration will never converge to this root, whatever the initial approximation.
Graphically the second failure can be represented (with the red line representing the iteration) as such:
Although the starting value is 0.3, the iteration leads to divergence in the negative region of the graph. This is due to the gradient at 0.3 of the curve being too large, which does not allow convergence at the intersection in the interval [0,1]. Thus, divergence occurs, spiralling outwards, with half the x-values tending to zero and the other half tending to negative infinity.
Comparison of methods
I want to find the roots of the equation x3-3x+1=0 to seven decimal places.
Consider the function f(x)=x3-3x+1; hence I want to find the roots of the equation f(x)=0.
As shown in the last section, if we rearranged the equation in the form xn+1=(xn3+1)/3, then the following table can be constructed:
Therefore, for x3-3x+1=0, the root in the interval [0,1] is:
x=0.3472964 (to seven decimal places)
Using the Newton-Raphson method, the iteration is xn+1=xn-((f(xn))/f/(xn)) and the following table is constructed:
The same root, x=0.3472964 (7dp) is found. A different starting value had to be used for convergence to the required root.
Using the decimal search method, the following tables were constructed:
Therefore the root lies in the interval [1.34729635,1.34729636], therefore the root is:
x=0.3472964 (to 7 decimal places).
In terms of speed of convergence, the rearrangement method took 11 steps to converge to the root to 7 decimal places, the Newton-Raphson method took 3 steps to do this and the decimal search method took 8 sets to achieve this. It would seem that the Newton-Raphson method is the fastest, followed by the decimal search method and then followed by the rearrangement method. This may not always be the case since the speed of convergence for both Newton-Raphson and the rearrangement method is subject to the initial starting value chosen. The decimal search method always takes one more table than the number of decimal places required (as explained before). In many cases, the speed of convergence for the rearrangement method has been faster than the decimal search method, but the Newton-Raphson method is always quickest to converge (given that it does converge).
I used Microsoft Excel to do all of these tables and graphs. In terms of ease of use, the rearrangement method required the least steps as all I had to do was fill the formula in one cell, using cell above as the xn value, and ‘drag down’. This was the quickest and easiest method to produce a table for. The Newton-Raphson method was much the same, however it required the input of a much longer formula, and therefore was slightly more tedious. The decimal search method required the input of a lot of data, even after entering the formula into one of the cells. It requires n+1 tables if I want to find a root to n decimal places. Therefore this was by far the slowest method to use.
In terms of failure, the rearrangement method only gives one root for one rearrangement. In this respect the Newton-Raphson method is better, since it converges to all roots given a suitable starting value. However it has the potential to diverge which is unhelpful. In this respect, the decimal search method is the best, given small enough intervals, as it hardly ever fails once a root is identified in a particular interval.
