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 x1.
  3. If f(x1) = 0 then x1 is an exact root, else if f(x1) * f(b) < 0 then let a = x1, else if f(a) * f(x1) < 0 then let b = x1.
  4. Repeat steps 2 & 3 until f(xi) = 0 or |f(xi)| <= DOA, where DOA stands for degree of accuracy.

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

xi = 0.5
xi–1 = ( 0.5 )i ( b – a )

and the new midpoint is

xi = ai–1 + xi

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

i a x b f(a) f(x) f(b)
1 1 1.5 2 –1  2.875  9
2 1 1.25 1.5 –1  0.703125  2.875
3 1 1.125 1.25 –1 –0.201171875  0.703125
4 1.125 1.1875 1.25 –0.201171875  0.237060546875  0.703125
5 1.125 1.15625 1.1875 –0.201171875  0.014556884765625  0.237060546875
6 1.125 1.140625 1.15625 –0.201171875 –0.0941429138183594   0.014556884765625
7 1.140625 1.1484375 1.15625 –0.0941429138183594 –0.0400032997131348  0.014556884765625
8 1.1484375 1.15234375 1.15625 –0.0400032997131348 –0.0127759575843811  0.014556884765625
9 1.15234375 1.154296875 1.15625 –0.0127759575843811  0.000877253711223602  0.014556884765625

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:


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