5. Root Finding with Bracketing Methods

Bisection Method

Bisection method based on the Intermediate Value Theorem, which states that if the function is continuous on an interval $[a,b]$ and changes sign over that interval, then there exists at least one root in the interval.

Inputs

• The definition of the function: $f(x)$
• The lower bound of the interval: $a$
• The upper bound of the interval: $b$
• The allowed tolerance for the method: $\varepsilon$
• The maximum number of iterations: max_iter

Condition

• The function changes sign over the interval. This condition can be checked by ensuring the following inequality:

$$f(a) \cdot f(b) < 0$$

Iterations

• Find the midpoint of the interval

$$c = \frac{a+b}{2}$$

• Calculate the following values:

$$f(a), f(b), f(c)$$

• Check if the tolerance is satisfied: $$f(c) \le \varepsilon$$

• Check if the convergence is satisfied: $$|b-a| \le \varepsilon$$

• Check if the number of iterations has reached to max_iter.

• If at least one the checks above is not satisfied, specify the new values of the bounds for the next iteration by using the checks below: $$f(a) \cdot f(c) &lt; 0 \rightarrow a^{\prime} = a ~~~~ b^{\prime} = c$$ $$f(b) \cdot f(c) &lt; 0 \rightarrow a^{\prime} = c ~~~~ b^{\prime} = b$$

• Repeat the steps given above until tolerance, convergence, or number of iterations is satisfied.

Estimate the Number of Iterations

One can estimate the number of iterations, which is required to reach the desired tolerance $\varepsilon$, using the equation given below: $$n \ge \log_2 \frac{b-a}{\varepsilon}$$