Using the bisection method, I am going to find one root for the equation , the graph of which is shown below, where one division on the x-axis represents 1, and one division on the y-axis represents 14. From the graph it can be seen that there is a root between 1 and 2, it is this root that I will try to find using the bisection method: In the spreadsheet above, n is the iteration number. an is the lower bound, bn is the upper bound, and xn the bisection of the interval [1,2] and f(xn) is the value of y, for that particular value for x. If y > 0 then an remains the same, and the last value of xn becomes bn.
If however, y < 0 then bn remains the same, and an becomes the value of xn in the previous iteration. f(an) and f(bn) are included to give an idea of how close to the root an and bn are. The diagram below shows how the bisection method works. The blue and green lines represent the original lower and upper bounds. The purple lines represent the average value of the lower and upper bounds. These get closer to the root, as the diagram shows. (This is actually the graph of , on a different scale)
The root of the equation in the interval [1, 2] is , and the error bounds are 1. 175537 and 1.175781. However, when solving the equation , the change of sign method does not work. As the graph of above shows, there is a root between 1 and 2, but when x is 1, y is positive, however when x is 2, y is positive again. So because there is no change of sign, the change of sign method does not work for equations which have a minimum when y = 0. Using the Newton- Raphson method to find all the roots of an equation The Newton- Raphson method can be summarized by an equation: Where is a point on the x-axis, fairly close to the root. is a point on the x-axis that is closer to the root.
By repeating this equation and allowing to become for the next iteration. is the value of the function of x for the value. is the value of for the derivative of . I am going the use this method to solve the equation . The graph of is shown below, where one division on the x-axis represents 1, and one division on the y-axis represents 14: It can be seen that there are roots in the intervals [-1, 0], and [1, 2] (twice, therefore, the lower value will be found by coming from , and the upper value from ). The derivative of is . In the spreadsheet above, the first root for is found, to 4 significant figures, so.
I will now try to find the second root for My initial value of was 3, to avoid confusion. The second root in the interval [1, 2] is 1. 9805 ? 0. 0005. I will now find the third root, which is in the interval [-1, 0]. This third and final root can be expressed as . The graph above is the third root, zoomed in upon, to show the method. The green lines represents x0, the initial value, in this case -1. The purple line is the tangent to the curve at x0. Where the tangents meets the x-axis, this is x1. This happens again, from the blue line, to the pink line, and so on, until the root is reached.
The graph shown above is . It can be seen that there is a root in the interval [2, 3]. However, if , the Newton- Raphson method fails, to find the root in [2, 3] as shown in the diagram below. (The green line is on , each division represents 0. 2) By starting at x =2, the method finds the root in the interval [1, 2] and not in [2, 3], even though the starting value was close to the root in [2, 3]. This is because the turning point in [2, 3] means that the gradient at is negative, as is the value of , so the method finds a root the left of .
Using fixed point iteration to find a root of an equation I am going to use this method to solve the equation . The graph of is shown below. The function can be arranged to , and if a graph of is drawn on the same set of axis as , then the root of is where the two graphs cross. As shown below graphically, if, then . Which is why the method works. The spreadsheet below finds the root: To four figures, the root is . In the spreadsheet above, r is the iteration number, and . The diagram below, shows how the method works. is the starting value, in this case -1.
The corresponding y-value of is then calculated- this value is then used to find the y-value of , and hence the value of is found. By repeating this procedure, the method reaches the root. The green line is , and the purple lines represent as the method converges on the root of . However, if the equation is rearranged to , then the graph of and the graph of do not cross, as shown below. Therefore this rearrangement of would fail to find the root, which the spreadsheet below shows. The conditions in which fixed point iteration would fail to find the root of an equation are when , and .
Comparison of Methods To compare the methods, I am going to use the equation that I used for the fixed point iteration method, . To find the root (to 4 figures) using the fixed point iteration method 25 iterations were required. Below are the spreadsheets of the bisection method and the Newton-Raphson method respectively, each finding the same root. Out of these methods, the Newton- Raphson method converged on the root the fastest, with only 3 iterations required. The second fastest was the bisection method, with 14 iterations, and the slowest was fixed point iteration, which required 25 iterations.
With a computer spreadsheet, all of the methods are easy to apply, but they all have failings, that there are some equations that can not be solved with that particular method. All of the methods require a starting value that is close to the root, so a graph is required for each method, again with appropriate software this is easy. Without a computer, the bisection method generally takes the most time, due to the calculations involved. The fixed point iteration may be slow, and the Newton- Raphson method requires the ability to differentiate.