Example AEF.NEB Numerical Estimation Bisection
In many cases representing the exact value of a solution to an
equation as a decimal can be very difficult or even
impossible. In such cases techniques that provide a numerical estimate
of the solution to some precision is very useful. Mapping diagrams can
be used often to visualize these techniques.
Since many examples involve elementary functions that are continuous for an interval of the form $[a,b]$, one basis for
estimating solutions is the result:
Theorem: CCD.IVT.0: If $f$ is a continuous function on the interval
$[a,b]$ and $0$ is between $f(a)$ and $f(b)$, then there is a number $c \in [a,b]$
where $f(c) = 0$.
An immediate consequence of the IVT is that if $f(a)\cdot f(b) < 0$, then there is a number $c \in [a,b] $ where $f(c) = 0$.
The Bisection Method
The bisection method repeatedly applies the IVT to estimate a solution to an equation with an elementary function,
$f$, of the form $f(x)=0$ as long as $f(a)\cdot f(b) < 0$ for the initial numbers $a$ and $b$ .
The procedure is as follows:Start with $a_1=a$ and $b_1=b$.
Suppose $a_n < b_n$ and $f(a_n)\cdot f(b_n) < 0$. Let $m_n = \frac {a_n+b_n}2$ and compute $f(m_n)$.
If $f(m_n) = 0$ then $m_n$ is the solution to the equation.
Otherwise either $f(a_n)\cdot f(m_n) < 0$ or $f(m_n)\cdot f(b_n) <
0$.
If $f(a_n)\cdot f(m_n) < 0$, let $a_{n+1} = a_n$ and $b_{n+1}=m_n $.
Otherwise let $b_{n+1} = b_n$ and $a_{n+1}=m_n $.
Then $a_{n+1} < b_{n+1}$ and $f(a_{n+1})\cdot f(b_{n+1}) < 0$, so the procedure can be repeated.
At each step the interval $[a_n,b_n]$ is bisected, so the solution
guaranteed by the IVT to exist in this interval is approximated more
accurately by either end numbers of the next interval.
The mapping diagram below illustrates the example where $f(x) = x^2-2, a=0,$ and $b=2$.
The Bisection Method
Notice how the arrows on the mapping diagram are paired with the
point on the graph of the function $f$.
You can move the point for $x$ on the mapping diagram to see how
the function value changes both on the diagram and on the graph.
Sliders: The sliders labeled $a$ and $b$ control the end values of the interval $[a,b]$.
The slider labeled $n$ controls which the number of times the bisection of the interval is executed.
Checking the box to "Show/Hide Midpont & Data" will display $a_n, b_n, m_n$ and the values of $f$ for each of these nmbers.
It will also display a scond box to "Show/Hide Smallest Exact
Root". Checking this box will display this root on both the graph and
the mapping iagram.
The function $f$ can be changed by making an entry in the appropriately labeled input box.
Martin Flashman, August. 10, 2017.
Created with GeoGebra