The intermediate value theorem and the bisection method

On pages 42 and 43 in section 1.5 of our textbook, we meet the intermediate value theorem and the bisection method, which can be used to show that certain equations have solutions and to estimate them fairly accurately. In this little demo, we'll see how to use these tools on the computer and how the theory leads to the algorithms working in the background.

The theory

The intermediate value theorem (or IVT) looks something like so:

The intermediate value theorem
Suppose that the function $f$ defined on the closed interval $[a,b]$ has the following three properties:
  1. $f(a) < 0$,
  2. $f(b) > 0$, and
  3. $f$ is continuous on $[a,b]$.
Then, there is a number $c$ in the open interval $(a,b)$ such that $f(c)=0$.

This theorem is extremely important from an applied perspective because it often allows us to know if equations that we want to solve have solutions. We can also use it in an iterative fashion to zoom in on a root once we've isolated it. The formal statement of this technique is called the bisection method.

The bisection method
  1. Suppose that $f(a)<0$, $f(b)>0$, and that $f$ is continuous on $[a,b]$.
  2. Choose a tolerance level $\varepsilon>0$. Our estimate will be within $\varepsilon$ of the actual root.
  3. Set $c=(a+b)/2$.
    1. If $f(c) = 0$, then we've found our root! Return $c$
    2. If $f(c)<0$, reset $a=c$.
    3. If $f(c)>0$, reset $b=c$.
  4. If $b-a<\varepsilon$, then we've met our tolerance level. Return $c$.
  5. Note that, if we haven't found our root to the desired tolerance level yet, then $f$ still satisfies the assumptions of IVT on the new interval $[a,b]$. Go back to step 2.

Practice

Let's take a look at a typical situation that we might explore on a computer. In the code blocks below, we're using a mathematical tool called Sage. The specific example we'll explore is $f(x) = x^4 - x - 1$ over the interval $[0,2]$. It's not hard to show that there is a root by looking at a graph.

We'd like to know the value of the root more precisely, though. Sage does have an algebraic solve command that can (sometimes) compute roots exactly. The solve command works for this example, but the result is not particularly palatable. Here's how to use it, nonetheless:

In computational mathematics, there is an important distinction between symbolic computation and numeric computation. The previous computation was symbolic. A numeric computation should produce a decimal approximation, which is often more palatable. Sage has a numeric findroot which works great here.

Implementation

Later this semester, we'll learn a technique called Newton's method that forms the basis for the findroot command. For the time being, we'll happily implement the simpler bisection method that can be used in this situation.