Bisection Algorithm

Pronunciation: /baɪˈsɛkt ʃən ˈæl gəˌrɪð əm/ ?

The bisection algorithm is a method for approximating the root of an equation by successively bisecting an interval that contains the root. The root of a function f(x) is where the function equals zero: f(x) = 0. If two values of f(x) are known, and one is positive and the other negative, the Intermediate Value Theorem guarantees that a root exists between those two values if f(x) is continuous on the interval. The bisection algorithm approximates that root to as many significant digits as one wants.

The basic algorithm starts with a closed interval [a..b] where the sign of f(a) is the opposite of the sign of f(b) (if f(a)>0 then f(b)<0, and if f(a)<0 then f(b)>0). The middle value of the interval is found by averaging the endpoints: m=(a+b)/2. The value of f(m) is calculated. If it is negative, replace the endpoint of the interval for which f(x) is negative with m. If it is positive, replace the endpoint of the interval for which f(x) is positive with m. Then repeat the algorithm until sufficient significant digits have been found.

Example 1

Calculate the root of f(x) = x2 - 2 that lies between 1 and 2 to two significant digits. Since f(1)=-1 and f(2) = 2, let a=1 and b=2;

Iterationabm=(a+b)/2f(m)Discussion
112(1+2)/2 = 1.5f(1.5) = 0.25Since 0.25 > 0, substitute 1.5 for 2. The new interval is [1,1.5].
211.5(1+1.5)/2 = 1.25f(1.25) = -0.4375Since -0.4375 < 0, substitute 1.25 for 1. The new interval is [1.25,1.5].
31.251.5(1.25+1.5)/2 = 1.375f(1.375) = -0.109375Since -0.109375 < 0, substitute 1.375 for 1.25. The new interval is [1.375,1.5].
41.3751.5(1.375+1.5)/2 = 1.4375f(1.4375) = 0.06640625Since 0.06640625 > 0, substitute 1.4375 for 1.5. The new interval is [1.375,1.4375].
51.3751.4375(1.375+1.4375)/2 = 1.40625f(1.40625) = -0.0224609375Since -0.0224609375 < 0, substitute 1.40625 for 1.375. The new interval is [1.40625,1.4375]. Since the endpoints of the interval round to the same two digit number, the answer is 1.4.
Table 1: Example 1 of the bisection algorithm

Cite this article as:


Bisection Algorithm. 2010-10-15. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/b/bisectionalgorithm.html.

Image Credits

Revision History


2010-10-15: Initial version (McAdams, David.)

All Math Words Encyclopedia is a service of Life is a Story Problem LLC.
Copyright © 2005-2011 Life is a Story Problem LLC. All rights reserved.
Creative Commons License This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License