# Bisection Algorithm

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

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: . 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;

Iteration a b m=(a+b/2) f(m) Discussion
1 1 2 (1+2)/2 = 1.5 f(1.5) = 0.25 Since 0.25 > 0, substitute 1.5 for 2. The new interval is [1,1.5].
2 1 1.5 (1+1.5)/2 = 1.25 f(1.25) = -0.4375 Since -0.4375 < 0, substitute 1.25 for 1. The new interval is [1.25,1.5].
3 1.25 1.5 (1.25+1.5)/2 = 1.375 f(1.375) = -0.109375 Since -0.109375 < 0, substitute 1.375 for 1.25. The new interval is [1.375,1.5].
4 1.375 1.5 (1.375+1.5)/2 = 1.4375 f(1.4375) = 0.06640625 Since 0.06640625 > 0, substitute 1.4375 for 1.5. The new interval is [1.375,1.4375].
5 1.375 1.4375 (1.375+1.4375)/2 = 1.40625 f(1.40625) = -0.0224609375 Since -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

1. McAdams, David E.. All Math Words Dictionary, bisection algorithm. 2nd Classroom edition 20150108-4799968. pg 27. Life is a Story Problem LLC. January 8, 2015. Buy the book

McAdams, David E. Bisection Algorithm. 4/12/2019. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/b/bisectionalgorithm.html.

### Revision History

4/12/2019: Changed equations and expressions to new format. (McAdams, David E.)
1/29/2019: Fixed page formatting issues. (McAdams, David E.)
12/21/2018: Reviewed and corrected IPA pronunication. (McAdams, David E.)