Previous Topic

Next Topic

Bisection Iteration Method

Component

Utility

 

Definition

The bisection method is based on the principle that a function will change sign when it passed through zero. By evaluating the function at the middle of an interval and replacing whatever limit has the same sign, the bisection method halves the size of the interval in each iteration.

Assuming that the interval contains the root, the bisection method is guaranteed to find it, although it can be slow. When an interval contains more than one root, the bisection method will find one of them, and when an interval contains a singularity, the bisection method will converge to that singularity.

 

 

Algorithm

The following algorithm finds a root of f(x) = 0 in the interval of (ao, bo) with which f(a0)f(b0) < 0, assuming an accuracy of e:

Equation Template

 

 

Convergence Criteria

The bisection method halves the size of the interval in each iteration. If the interval is wide, the bisection method may take many iterations before the root is found. However, if a root exists between the given bounds, the bisection method is guaranteed to find it. This contrasts the Newton-Raphson and Secant methods which are superior in speed however are not guaranteed to converge on the root.

Reasonable upper (b) and lower (a) bounds are preset for each procedure. If the root is not within these bounds, the bounds are adjusted until they contain the root.

The number of iterations required depends considerably upon how close the root is to either of the bounds as well as the desired accuracy level (e). The desired accuracy level varies depending on the scale of x0. Base line accuracy is set at six decimal places for x0 = 1, and decreases as the order of magnitude of x0 increases. For example, if x0 = 10 then the accuracy is set to five decimal places; if x0 = 100 then the iteration procedure will converge to four decimal places; and so on.

If after 40 iterations the value is not within the desired accuracy level, then the entire process will start again with another estimate of x0. This will occur up to five times, and if the procedure still fails to converge then an error message will be displayed.

 

 

Return to www.derivativepricing.com website

Copyright 2013 Hedgebook Ltd.