The Intermediate Value Theorem

I. Cnop
Vrije Universiteit Brussel
icnop@vub.ac.be

Continuous functions

In  the age of technology, a continuous dependance (function) means that we can obtain its values with any (finite) precision if we know the value of the independant variable with sufficient (finite) precision.This is exactly what Augustin Cauchy meant when he gave his first definition od continuity, and since computers work with finite precision this definition is the one we will use. If a dependence is continuous, we can obtain values with arbitrary precision.
The same is true for the definition of a limit.
We will now show how we can approximate in the same way the zeroes of a continuous function when we know its graph crosses the axis of the independant variables. The existence of a zero in this case is shown by a construction, on which the classical proof is based. It is an example of a constructive proof. Many constructive proofs use repeated computations called algorithms, and they also are the basis of algorithms themselves.
We are going to locate the zero with any precision by the following algorithmic construction.

The bisection method

Set f the name of any function on an interval

f[x_] := (x^3) + (Sqrt[x + 2]) - 4

Here we have chosen a function for which there is no algebraic way to locate a zero. We will first check that it has negative and positive values on a certain interval by taking a product of values:

Control

f[0. ]  f[2]//N

This will be our initial interval where we look for a zero. Recall that in  Mathematica  , an interval  [a,b]  is denoted by the listing of both endpoints  {a,b}

Divide the interval

If the value of the function in the middle of an interval  [a,b]  has a different sign of the value in the left endpoint we keep the left half of the interval, otherwise we keep the right half of the interval.

newHalf[{a_, b_}] := 
      If[f[a] f[(a + b)/2] <= 0, {a, (a + b)/2}, {(a + b)/2, 
          b}]

Repeat this division:

intervals = NestList[newHalf, {0. , 2. }, 10]

intervals // TableForm

More steps will give more precision

intervals = NestList[newHalf, {0. , 2. }, 30]

intervals // TableForm

The value of f in the endpoints of the last interval obtained is indeed close to zero

f[Last[%%]]

Plotting our results

Left endpoints

ListPlot[
      Transpose[{First[Transpose[intervals]], 
          Range[Length[intervals]]}]]

Right endpoints

ListPlot[
      Transpose[{Last[Transpose[intervals]], 
          Range[Length[intervals]]}]]

All endpoints

Show[%, %%]

Showing all intervals

segments = 
        Map[Line, 
          Transpose[{Transpose[{Last[Transpose[intervals]], 
                  Range[Length[intervals]]}], 
              Transpose[{First[Transpose[intervals]], 
                  Range[Length[intervals]]}]}]];

Show[Graphics[segments
], 
      AspectRatio ->  .2]

Efficiency of this algorithm

\(Since\ each\ time\ the\ length\ of\ the\ interval\ is\ divided\ by\ \ 2\ \ this\ algorithm\ is\ very\ efficient . \ 
        We\ will\ obtain\ a\ location\ within\ \ \ 1/
        10\^20\ \ in\ \ about\)

N[(Subscript[log, 2])((10^20))]

steps.

Proof the intermediate value theorem

The proof is easy if we know the precise definition of continuity. 
Continuity means that values are arbitrarily close (to the value at a point) on sufficiently small intervals (around this point). 
This means that on small intervals the function can only have a small spread of its values. 

If  on each interval in the construction above  some of the values are negative and some positive, they must lie around zero and closer to it as the size of the interval decreases. We obtain a zero value with arbitrary precision.

Exercise

Repeat this algorithm for other functions on selected intervals

Make shure  each time that the function has values with different signs at both endpoints of the initial interval.