1.3. Bracketing Methods

Bracketing methods start with an interval that contains the root and a procedure is used to obtain a smaller interval containing the root.

Examples of Bracketing methods:

• Bisection Method
• False position method (Regula-Falsi)

# These are helper types that are declared to document the code.
from typing import Callable, Tuple 

# A non-linear function is simply a function that takes
# a float and returns a float.
NonLinearFunction = Callable[[float], float]

# Helper Functions
def sign_of(number) -> int:
    if number == 0:
        return 0
    elif number < 0:
        return -1
    elif number > 0:
        return 1

1.3.1 Bisection Method (or Interval Halving)

In the bisection method you are given the two numbers that represent an interval on the x-axis of the number line that contains the root.

           interval_midpoint
                   |
  interval_start   ↓   interval_end 
          ⬤-----------------⬤
-∞       -3 -2  -1   0   1   2   3       +∞
 └┴┴┴┴┴─┴─┴──┴───┴───┴───┴───┴───┴─┴─┴┴┴┴┘ 

Assumptions of the Bisection Method

Given a function \(f(x)\) and an interval \([interval\_start, interval\_end]\):

• \(f(x)\) is continuous on the interval.
• The sign of \(f(interval\_start)\) and \(f(interval\_end)\) are different (i.e \(f(interval\_start) \times f(interval\_end)\))

Algorithm of the Bisection Method

1. At each iteration you evaluate the value of the function at:
   • The start of the interval, \(interval\_start\)
   • The end of the interval, \(interval\_end\)
   • And, the midpoint of the interval, \(interval\_midpoint\)
2. Adjust the values of \(interval\_start\) and \(interval_end\) using the following rule:

   • If the value of the function at \(interval\_midpoint\) has the same sign as \(interval\_start\), then the new interval is: \([interval\_midpoint, interval\_end]\).

   • If the value of the function at \(interval\_midpoint\) has the same sign as \(interval\_end\), then the new interval is: \([interval\_start, interval\_midpoint]\)

Best Estimate and Error Level

The best estimate of the root of the equation is the mid point of the interval.

\(Estimate \space of \space the \space zero: r = \frac{b + a}{2}\)

Using the midpoint of the interval as an estimate the error is given by:

\(Error \leq \frac{b - a}{2}\)

Convergence Analysis of Bisection Method

\(n \leq \frac{log(b-a) - log(\epsilon)}{log(2)}\)

Where:

• \(n\): The number of iterations.
• \([a, b]\): The interval of the containing the root.
• \(\epsilon\): The acceptable error (specified as an absolute error).

# This is a verbose example to explain the concepts

def bisection_method(
    function: NonLinearFunction,
    interval: Tuple[float, float],
    iteration_limit: int,
    error_level: float,
) -> float:

    (start, end) = interval
    # Check that the interval has two different signs at
    # both sides
    if sign_of(function(start)) == sign_of(function(end)):
        raise "The start and end of the interval must have different signs"

    for _ in range(iteration_limit):
        midpoint = (start + end) / 2

        # Get the value of the function at the interval's
        # start, end and midpoint.
        start_value: float = function(start)
        end_value: float = function(end)
        midpoint_value: float = function(end)

        error = abs(midpoint_value - 0)
        if error <= error_level:
            # If the error is within the error level we return.
            return midpoint

        if midpoint_value == 0:
            # If we found the exact root return early.
            return midpoint_value
        elif sign_of(start_value) == sign_of(midpoint_value):
            # If the sign of the midpoint is the same as the sign at the 
            # start of the interval, the midpoint becomes the new interval start
            start = midpoint
        elif sign_of(end_value) == sign_of(midpoint_value):
            # If the sign of the midpoint is the same as the sign at the
            # end of the interval, the midpoint becomes the new interval end. 
            end = midpoint 

    # Once we've exceeded the iteration limit return whatever is the
    # midpoint of the interval
    midpoint = (start + end) / 2
    return midpoint 

Testing out our code:

func_1 = lambda x: (x**2) - x - 2

root = bisection_method(
    function = func_1,
    interval = (0, 3),
    iteration_limit = 20,
    error_level = 0.05,
)

import matplotlib.pyplot as plt

plt.grid()
plt.plot(
    list(map(func_1, range(-3, 6)))
)
plt.scatter(2, 0, color="red")
plt.scatter(5, 0, color="red")

<matplotlib.collections.PathCollection at 0x21cf67413d0>

# Simple version

def bisection_method_simple(
    f: NonLinearFunction,
    interval: Tuple[float, float],
    iteration_limit: int,
    error_limit: float
) -> float:
    (a, b) = interval
    for _ in range(iteration_limit):
        c = (a+b) / 2
        f_a = f(a)
        f_b = f(b)
        f_c = f(c)

        if sign_of(f_c) == sign_of(f_a):
            a = c
        elif sign_of(f_c) == sign_of(f_b):
            b = c
        elif f_c == 0:
            return c

    return (a+b) / 2