📂Numerical Analysis

Bisection Method

Method ¹

Let’s assume that a continuous function $f$ is defined on the closed interval $[a,b]$ and is equal to $f(a) f(b) < 0$. The tolerance is $\varepsilon$. A $c \in [a,b]$ satisfying $f(c) = 0$ can be found as follows.

---

Step 1.

$$c:= {{a+b} \over {2}}$$

---

Step 2.

If $b-c \le \varepsilon$, return $c$.

---

Step 3.

If $f(b) f(c) < 0$, then $a:=c$, else $b:=c$. Then return to Step 1.

Explanation

As a classic application of the Intermediate Value Theorem, this method continues to halve the interval where a solution exists, finding an approximate solution of the equation $f(x) = 0$. It’s simple enough that if you have an equation to solve immediately and you don’t have any libraries, you could whip this up on the spot.

The charming part is essentially only that it’s defined for continuous functions in a closed interval, and that it finds the solution within a user-specified range, but it has the disadvantage of having a linear convergence rate. Hence, for solving simple equations, usually the Newton-Raphson method is used.

Implementation

Here is an example code written in R.