Example: Finding The Root of A Polynomial
Suppose that the bisection method is used to find a root of the polynomial
First, two numbers and have to be found such that and have opposite signs. For the above function, and satisfy this criterion, as
and
Because the function is continuous, there must be a root within the interval .
In the first iteration, the end points of the interval which brackets the root are and, so the midpoint is
The function value at the midpoint is . Because is negative, is replaced with for the next iteration to ensure that and have opposite signs. As this continues, the interval between and will become increasingly smaller, converging on the root of the function. See this happen in the table below.
| Iteration | ||||
|---|---|---|---|---|
| 1 | 1 | 2 | 1.5 | −0.125 |
| 2 | 1.5 | 2 | 1.75 | 1.6093750 |
| 3 | 1.5 | 1.75 | 1.625 | 0.6660156 |
| 4 | 1.5 | 1.625 | 1.5625 | 0.2521973 |
| 5 | 1.5 | 1.5625 | 1.5312500 | 0.0591125 |
| 6 | 1.5 | 1.5312500 | 1.5156250 | −0.0340538 |
| 7 | 1.5156250 | 1.5312500 | 1.5234375 | 0.0122504 |
| 8 | 1.5156250 | 1.5234375 | 1.5195313 | −0.0109712 |
| 9 | 1.5195313 | 1.5234375 | 1.5214844 | 0.0006222 |
| 10 | 1.5195313 | 1.5214844 | 1.5205078 | −0.0051789 |
| 11 | 1.5205078 | 1.5214844 | 1.5209961 | −0.0022794 |
| 12 | 1.5209961 | 1.5214844 | 1.5212402 | −0.0008289 |
| 13 | 1.5212402 | 1.5214844 | 1.5213623 | −0.0001034 |
| 14 | 1.5213623 | 1.5214844 | 1.5214233 | 0.0002594 |
| 15 | 1.5213623 | 1.5214233 | 1.5213928 | 0.0000780 |
After 15 iterations, it becomes apparent that there is a convergence to about 1.521: a root for the polynomial.
Read more about this topic: Bisection Method
Famous quotes containing the words finding and/or root:
“A submissive spirit might be patient, a strong understanding would supply resolution, but here was something more; here was that elasticity of mind, that disposition to be comforted, that power of turning readily from evil to good, and of finding employment which carried her out of herself, which was from Nature alone. It was the choicest gift of heaven.”
—Jane Austen (1775–1817)
“A radical generally meant a man who thought he could somehow pull up the root without affecting the flower. A conservative generally meant a man who wanted to conserve everything except his own reason for conserving anything.”
—Gilbert Keith Chesterton (1874–1936)