Bracketing Method

If $f(x)$ is real and continuous in the interval from $x_l$ to $x_u$ and $f(x_l)$ and $f(x_u)$ have opposite signs, there is at least one real root between $x_l$ and $x_u$.

Opposite Sign Checking

We can check opposite signs using $f(x_l)\cdot f(x_u)<0$.

Bisection Method

Bisection method divides intervals in half.

Steps

1. Choose $x_l$ and $x_u$ such that the function changes signs.
2. Estimate root by $x_r=\frac{x_l+x_u}{2}$.
3. Identify $x_r$ position:
   • If $f(x_l)$ and $f(x_r)$ have the same sign, then $x_l=x_r$
   • If $f(x_u)$ and $f(x_r)$ have the same sign, then $x_u=x_r$
4. Repeat steps 2 and 3.

Example

Our function is:

$$f(x)=x^2-e^{-x}$$

Then we have:

iteration	$x_l$	$x_u$	$x_r$	$f(x_l)$	$f(x_u)$	$f(x_r)$	${ϵ}_a$
1	0	1	0.5	-1	0.632	-0.356	33%
2	0.5	1	0.75	-0.356	0.632	0.901	17%
3	0.5	0.75	0.625	-0.356	0.901	-0.145	9%

• In iteration 2, $f(x_{r_1})$ and $f(x_{l_1})$ have the same sign, so iteration 2 takes $x_{r_1}$ as its lower bound $x_{l_2}$.
• In iteration 2, $f(x_{r_2})$ and $f(x_{u_2})$ have the same sign, so iteration 3 takes $x_{r_2}$ as its upper bound $x_{u_3}$.

Errors

The process above is terminated when a criteria is met, such as relative approximate error ${ϵ}_a<k$ for some $k$, where:

$$\begin{array}{rl}{ϵ}_a& =\left|\frac{x_{r_{new}}-x_{r_{old}}}{x_{r_{new}}}\right|\times 100\%\\ & =\left|\frac{x_u-x_l}{x_u+x_l}\right|\times 100\%\end{array}$$

As an example, for the second iteration we would have:

$${ϵ}_a=\left|\frac{0.75-0.5}{0.5}\right|\times 100\%=33\%$$

We can see that the relative true error, ${ϵ}_t$, has an upper bound of:

$${ϵ}_t<x_{r_{new}}-x_{r_{old}}=\frac{\Delta x}{2}$$

Along these lines, if we are seeking an absolute error level, $E_a=\mid x_{r_{new}}-x_{r_{old}}\mid$, we can actually calculate the number of iterations to reach the desired error level:

$$\begin{array}{rl}\text{Start:}& E_a^0=\Delta x^0=x_u^0-x_l^0\\ \text{1st Iteration:}& E_a^1=\frac{\Delta x^0}{2}\\ \text{2nd Iteration:}& E_a^2=\frac{\Delta x^0}{2\cdot 2}\\ \text{nth iteration:}& E_a^n=\frac{\Delta x^0}{2^n}\end{array}$$

Working from this, we can find the iteration $n$ at which we will be at a certain desired absolute error level $E_{a,d}$:

$$n=\frac{{\log }_{10}(\Delta x^0/E_{a,d})}{{\log }_{10}(2)}$$

Notes

• Robust algorithm – always works
• Slow convergence compared to other methods
• Cannot handle multiple roots (need to first graph to find number of roots and approximate locations)