Bisection Method - Example: Finding The Root of A Polynomial

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:

    “when man determined to destroy
    himself he picked the was
    of shall and finding only why
    smashed it into because”
    —E.E. (Edward Estlin)

    “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)