In order to make sure there are always sign changes between the 2 values of interval [a, b], two columns showing f (a) < 0 and f (b) > 0 will be added on the spreadsheet.
Spreadsheet 1.6
By using Excel spreadsheet 1.6, I discovered that in the 20th term, the root 1.21293 of 5 decimal places with error bounds ±is got. This gives the solution bounds as 1.212929046< x < 1.212930954. To ensure the root is correct, it is essential to check the presence of the sign change.
f (1.212929046) =
f (1.212930954) =
Since sign change can be shown, the Interval Bisection method succeeds in finding the root.
Failure of the method
The method fails when several roots are very close to each other. This can be proved by solving the following non-trivial equation.
To show the failure when using this method, another equation
y = (x+0.3) (x+0.5) (x+0.1)-0.0008 is chosen for illustrating the process.
Graph 1.7--- y = (x+0.3) (x+0.5) (x+0.1)-0.0008
Spreadsheet 1.8
Graph1.9--- bisection of y = (x+0.3) (x+0.5) (x+0.1)-0.0008
Consequently, we have got a root of -0.32021 (to five decimal places) between the interval [-1, 0]. The answer obtained in fact is one of the right roots. However, from the graph above, the graph intersects the x-axis three times, thereby giving 3 different roots. They all lie in the same interval [-1, 0]. Bisectional method has failed to find all the roots when several roots are too close with each other.
Fixed point iteration ---the Newton-Raphson method
An estimate of the root as a starting point has to be set. First of all, for one root of f(x) = 0. We then can draw a tangent to the curve y=f(x) at the point (x1, f(x1)). The point which the tangent cuts the x axis gives the next approximation for the root. Then the process is repeated, as shown in graph 2
The gradient of the tangent at (x1, f(x1)) is f’(x1). Since the equation of a straight line can be written
y-y1 = m(x-x1),
The equation of the tangent is
y-f (x1) = f(x1) [x-x1]
This tangent cuts the x-axis at (x2, 0), so
0- f(x1) = f(x1) [x2-x1]
Rearranging this gives
The Newton-Raphson iterative formula is then formed
On viewing the graph 2.1, the intervals in which the roots lie are [-3,-2], [-1, 0], [0, 1] respectively.
Graph 2.1---
In this case, I choose [0, 1] as the root presented graphically as follows.
First of all, I am going to show the way to find the root in the interval [0, 1]
Graph 2.2---Newton-Raphson for
By using the help of autograph, in interval [0, 1], I get a root of 3 decimal places 0.908.
Spreadsheet 2.3
From spreadsheet 2.3 above, rounding up the solution to 5 decimal places, I get the solution of 0.90762. The error bounds for this is ±0.000005. Hence, the solution is between 0.907615< x < 0.907625
f(0.907625) =
f(0.907615) =
After having checked for the existence of sign change, the method is proved to be successful.
By applying the same method, and choosing 2 other iteration as -2 and 0. I get the following 2 other roots.
Spreadsheet 2.4
Spreadsheet 2.5
Therefore the solution for the 2 other roots are -2.06292 and -0.17803.
(both to FIVE DECIMAL PLACES).
Failure of method
Even though this method worked really well with this graph, and is usually reliable and also very quick, sometimes the Newton-Raphson method is not working. Reasons for that are:
- the graph is not continuous
- the function is not defined for all real numbers
- the first guess is not good
A bad starting point (first guess) is when the f’(x) =0, then the tangent will never cross the x-axis.
To demonstrate how the method fails, a new equation:is chosen.
Graph 2.6---failure of Newton-Raphson on
There is an asymptote at X=0, the tangent diverges and so no root can be obtained.. it is because when X=0, there is a turning point, as. Therefore the tangent is horizontal to the x-axis and will never cut them. The gradient at a turning point is always 0, that implies horizontal.
If y=0,
There we can see if we start with 0, we will have to draw a tangent at a turning point, which has a gradient horizontal to the x-axis and so we will never find X2 because the tangent will never cut the x-axis.
Fixed point iteration- Rearranging the equation f(x) = 0 into the form x = g(x)
In this method, an equation of f (x) =0 is rearranged into the form x= g (x). In this case, I am going to use a non-trivial and cubic equation---
y = (x-3) (x-1) (x+4) - 4, which can be expressed as f(x) = x³-13x+8=0
From the graph shown above, the intervals lie in the [-4,-3], [0, 1], [3, 4]
Graph 3.1
For example, f(x) = 0 can be arranged into:
A. B.
Here the b) equation is chosen to solve the equation.
Graph 3.2
From the Graph 3.2, y = x and intersect at the 3 roots which are around 3.5, 0.5 and -4.
Graph 3.3
Spreadsheet 3.4 Spreadsheet 3.5
Therefore we get the solution of 0.63509 with error bounds ±0.000005,
giving solution bounds of 0.635085 < x < 0.635095. By checking sign change:
f (0.635085) = +4.57111 x 10-5, which is positive
f (0.635095) = -7.72189 x 10-5 , which is negative
This tells that my answer is correct and it is in the bounds.
Differentiating the formula of
→ I would get
Inserting the solution x = of 0.63509 into g’(x), I would get 0.093078. This tell us the magnitude of the gradient of g(x) at the point of x = 0.093078 is less than 1, (<1) that means that the slope of it is less than that of the line y = x.
Failure of the method
In spite of the effectiveness of this method, it fails occasionally. Besides the root we have worked out, there is two other interception points. To test it, I use 4 as an approximation in applying the method by using the same rearranged equation:
and x= g (x) → by differentiation,
Have a look on spreadsheet 3.6; the values of x are diverging. It then becomes further from the actual root. This can be shown graphically on the Graph 3.7. Not knowing the magnitude of the gradient, the value of x taken is near to the approximation---2. The slope of the graph at x = 4 is g’ (4) which is 3.692307692…, which is larger than 1.
Spreadsheet 3.6
The magnitude of the rearrangement is quite good as you have to apply this method only 9 times until you have an answer which is correct to 6 decimal places. Furthermore the rearrangement was really quick and easy.
Let’s look at the rate of convergence:
Considering the different values of g’(x), for the values close to 0 and less than one---rapid rate, for the values close to 1 and less than one---slow rate and for the values bigger than one---divergence which implies the presence of failure.
In sum, the method will eventually converge to a root k, given that the absolute value of the slope of k------ is less than 1. In other words, the gradient of the root must not be steeper than y = x.
Graph 3.7
Comparison of method
In order to compare the 3 methods in a fair manner, the same equation should be applied in each method.
Here I am going to use the equation: f(x) = x³-13x+8, which has been just demonstrated to apply on the rearranged equation method. After using the rearranged equation method, the root 0.63509 has been found already.
Differentiating f (x), which gives f ’(x) = 3x2-13
Graph 4.1
Bisectional Method
Looking on the spreadsheet 4.2 shown below, I now apply the bisectional method in finding the roots and the way of proceeding the answers is as following:
Spreadsheet 4.2
The bisection method turns out to achieve the root 0.63509 with error bounds of
Again, by applying these into the spreadsheet 4.3, the Newton-Raphson method gives us the following result:
Spreadsheet 4.3
Newton-Raphson has found the root 0.63509 as well.
Comparing those three methods
Speed of convergence
After applying those three methods, I then know that the Bisectional method takes 18 steps, shown on spreadsheet 4.2, which is the longest procedure, to get the answer. On the other hand, Newton-Raphson method proceeds more quickly than that of bisection, which takes only 6 steps, shown on spreadsheet 4.3. Besides, the rearranging method takes two more steps---eight steps, shown on spreadsheet 3.4, to get the answer.
By comparing the number of iterations need to find the root in the interval of [1 ,2] in 5 decimal places, it is clear that Newton-Raphson Method has the fastest speed of convergence.
To conclude the results I have found, Newton-Raphson Method is the one has the fastest speed of convergence, which can be explained as in this method, finding a root by the intercepts of tangents to the curve with x-axis seems to be more efficient, by comparing to the Interval Bisection Method and the method of Rearranging the equation f(x) = 0 into the form x = g(x), as both of them are more likely to take more steps to achieve finding a root in a given level of accuracy.
Ease of use with available hardware and software
It is obvious that the Newton-Raphson method is the fastest to find the root in this case. Nevertheless, considering the use of software Autograph and Excel, it is not the easiest way to deal with.
First of all, when using bisection method, I need to type five formulae into Excel, including to define the value of x, f(x), Maximum Possible Errors and the assumptions of value a and b. Still, no algebraic calculation is needed. And in this case, basically, one calculator can help me find the roots.
Secondly, Newton-Raphson method is relatively trickier, including inserting four formulae into Excel to define Xn, f(Xn), f'(Xn) and f(Xn)/f'(Xn). At the same time, the equation of f(Xn) is needed to be calculated by differentiation algebraically. Further, the calculator is not the only thing needed. It can only work with the aid of autograph programme. The reason is that this can give us a clue of what approximation value of the roots should be taken, thereby avoiding taking any approximation value which is near the turning point and converse to a false root.
Thirdly, when applying rearranging equations, the equation f(x) has to be converted into the form of g(x) algebraically. After that, I use Autograph to draw the curve y = x and g(x) to find where the intersection points lie. I can then use Excel spreadsheet to insert one approximation value of the starting point and the accuracy of the method can be found. In the whole process, one formula is going to be put in. However, the gradient of the graph at the root have to be less than on, otherwise it will fail to find the root. All in all, the less complex the f (x) is, the more convenient we can use this method by rearranging the f(x) = 0 into the form x = g(x).
To conclude, it is most convenient, just typing one formula, to use Excel spreadsheet when using the method of rearranging equations. But, the bisection method is considered to be the easiest one when considering the whole process. It is because all we need to do is just use Excel and even a calculator only, whilst algebraic works is involved in the other two methods which may take longer time and increase the possibility to make mistake. Though I need to type more formulae than the others in Excel, it is still the easiest to deal with.