Introduction

This method finds a root of a one-variable function. By root, we mean x | f(x) = 0.

Method

Bisection method works on an interval given as input. Iteratively, it divides the interval into two equal intervals, and chooses one based on the following principle: the root will be found where the first value of the interval is negative/positive (evaluated on the function) and the second value is the opposite, since this implies the function goes through the X axis and the root is in that interval.

In order to work, this method requires a function to solve, an interval (two real numbers, the first one smaller than the second one) and either a number for iterations, a maximum absolute error value or a maximum iterative error value (the most common is the second one).

Examples

All of these testings were done with a maximal absolute error of 1e-12:

  • f(x) = x³ – 3x² – 4x + 2 ([-2, 0], x = -1.2924, 42 iterations, 7 ms)
  • f(x) = sin(x) + x – 2 ([1, 2], x = 1.10606, 39 iterations, 5 ms)
  • f(x) = e^x + x² – 2 ([0, 1], x = 0.537274, 41 iterations, 5 ms)

Singularities

This method can only find one root in each interval, meaning that one must know how many roots the function has and where are they found.

It has trouble in the following cases:

  • The function is non continuous in the interval given
  • The function contains multiple roots in the interval given

Some examples of functions that fail are:

  • f(x) = 1 / x – 1 (if we pass [-2, 2], the method has trouble since f(x) is discontinuous on x = 0)
  • f(x) = x⁴ – 14x³ + 71x² – 154x + 120 (if we pass [3, 4], the method can’t find anything, since the roots are on the first interval)

* In the code, there is a condition to detect roots on the beginning.

Flowchart

bisection

Code

Conclusions

In general, bisection method is not that good for solving problems. It works when one knows where the roots are and one only needs to get a good approximation of it. And, one must be careful to give an interval containing one and only one root, and the function must be continuous on that interval.

Advertisements