Bisection Method

Given that $f$ has a root $p$ in some interval, successively halve the interval and choose as your new interval the half containing $p$.

Enclosure methods

The bisection method is a basic example of an enclosure method: we produce successively better root approximations by enclosing or “trapping” a root in smaller and smaller intervals at each step.

Implementation

Given a function $f$ and an interval $[a, b]$, how can I decide if $f$ has a root in $[a, b]$?

Let's consider an example.

Let's consider an example.

Let $f(x)=x^3+2x^2-3x-1$ and note that \begin{alignat*}{3} f(-3) &= {\color{var(--emphColor)} -}1, &\quad f(-1) &= {\color{var(--emphColor)} + }3, &\quad f(1) &= {\color{var(--emphColor)} -}1 \\ f(-2) &= {\color{var(--emphColor)} + }5, &\quad f(0) &= {\color{var(--emphColor)} -}1, &\quad f(2) &= {\color{var(--emphColor)} + }9. \end{alignat*}
What can you say about the roots of $f$?
Let $f(x)=x^3+2x^2-3x-1$ and note that \begin{alignat*}{3} f(-3) &= {\color{var(--emphColor)} -}1, &\quad f(-1) &= {\color{var(--emphColor)} + }3, &\quad f(1) &= {\color{var(--emphColor)} -}1 \\ f(-2) &= {\color{var(--emphColor)} + }5, &\quad f(0) &= {\color{var(--emphColor)} -}1, &\quad f(2) &= {\color{var(--emphColor)} + }9. \end{alignat*}

Intermediate Value Theorem

Let $f$ be a continuous function on $[a,b]$ and let $k$ be any number between $f(a)$ and $f(b)$. Then there exists $c$ in $(a,b)$ such that $f(c)=k$.
What does the intermediate value theorem tell me about root finding?
Consider $\mathrm{sgn} (f(a) f (b))$. If $f$ is continuous on $[a, b]$ and the product $f(a) f(b)$ is negative, what can you say?