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:
“With two sons born eighteen months apart, I operated mainly on automatic pilot through the ceaseless activity of their early childhood. I remember opening the refrigerator late one night and finding a roll of aluminum foil next to a pair of small red tennies. Certain that I was responsible for the refrigerated shoes, I quickly closed the door and ran upstairs to make sure I had put the babies in their cribs instead of the linen closet.”
—Mary Kay Blakely (20th century)
“I will go root away
The noisome weeds which without profit suck
The soil’s fertility from wholesome flowers.”
—William Shakespeare (1564–1616)