BISECTION METHOD

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.

The Bisection Method is a numerical method for estimating the roots of a polynomial f(x).   It is one of the simplest and most reliable but it is not the fastest method.   Assume that f(x) is continuous.

Algorithm for the Bisection Method:   Given a continuous function f(x)

1. Find points a and b such that a < b and f(a) * f(b) < 0.
2. Take the interval [a, b] and find its midpoint x₁.
3. If f(x₁) = 0 then x₁ is an exact root, else if f(x₁) * f(b) < 0 then let a = x₁, else if f(a) * f(x₁) < 0 then let b = x₁.
4. Repeat steps 2 & 3 until f(x_i) = 0 or |f(x_i)| <= DOA, where DOA stands for degree of accuracy.

For the i^th iteration, where i = 1, 2, . . . , n, the interval width is

x_i = 0.5
x_i–1 = ( 0.5 )ⁱ ( b – a )

and the new midpoint is

x_i = a_i–1 + x_i

EXAMPLE:   Consider f(x) = x³ + 3x – 5, where [a = 1, b = 2] and DOA = 0.001.

PROBLEM:   Develop an algorithm, expressed as a NSD, that will find an estimate of the first positive root of a given polynomial f(x) within a certain degree of accuracy DOA using the Bisection Method.   Determine an initial estimate of the first positive root within one unit interval.   Use Horner's Method for evaluating f(x).

Questions:

• What is the best way of determining the values of a and b such that it contains the first positive root of f(x)?
• What is the best way of determining if the interval [a, b], where the first positive root lies, has been found?
• How are f(a), f(b), f(x) evaluated using the Horner's Method of evaluating a polynomial?
• How is the estimate of the root determined if it is not quite possible to determine an exact root?

---

© 1994-07-23 cad rcm cpsm; last update 2010-06-30 20:05

---