A root of a polynomial P(x) is a number c for which P(c) = O.
The bisection method is one scheme that can be used to find an approximate root of P(x) in some given interval [a, b], where pea) and P(b) have opposite signs (thus guaranteeing that P(x) has a root in [a, bbl.
In this method, we begin by bisecting the interval [a, b] and determining in which half P(x) changes sign, because P must have a root in that half of the interval. Now bisect this subinterval and determine in which half of this subinterval P(x) changes sign.
Repeating this process gives a sequence of smaller and smaller subintervals, each of which contains a root of P(x), as pictured in the following diagram.
The process can be terminated when a small subinterval-say, of length less than O.OOO1-is obtained or when P(x) has the value 0 at one of the endpoints:
Add and test a member function root 0 to the Polynomial class template so that, for a Polynomial object p, p. root (a,b) returns an approximate root of the polynomial in the interval [a, b] (if there is one), using the bisection method.