Bisection Method

Objectives

	Discussion of bisection algorithm
	Interpretation of relative error

Vocabulary

Zeros of function, Roots of polynomials, Relative error, Absolute error, Significant digits, Stopping criteria, Globally convergence, Error bound, Big O notation

Concepts

	Relative error and number of significant digits
	Bisection algorithm including stopping criteria
	Ratio of error- linear rate of convergence
	One binary digit of the solution is obtained at each iteration
	Method properties:

Method properties:

Strength	Weaknesses
Minimal requirement on function - Only continuity of function is required	Determination of Starting interval may not be trivial
Robust and globally convergent: Always convergent when given an appropriate initial interval	Convergence rate is slow
Rigorous underlying principle: intermediate value theorem	Cannot find roots of functions that do not change sign are complex
Error bound available: |xn -x*|< (b-a)/2n	Cannot be used to discover existence of more than one root for a fixed interval
	Stopping criteria choice not obvious
Easy to implement	Hard to generalize to higher dimension

 

Some External Links:

A web based bisection solver:

http://soli.inav.net/~hqcom/hqcscieng/math/nonlinear/bisection.html

Basic

http://daisy.uwaterloo.ca/~kghare/numeric/bisection.html

http://www.cs.utah.edu/~zachary/computing/classes/Engineering/contents.html

Codes

Maple: http://ftp.math.utah.edu/lab/ms/maple/src/bisection.txt

F90: http://www.warwick.ac.uk/~phrrk/overheads/fortsl11h/

Mathematica: http://e2.tam.uiuc.edu/TAM370/Mathematica/Mappings-1/Mappings-1.html

Practical example 

Where bisection method is used: Space Station Freedom Electrical Performance Model (http://godzilla.lerc.nasa.gov/ppo/tms/tm106395.html)

Correction to Misconceptions

 

Back to Top