In this chapter, we’ll focus on ways to solve all continuous functions.

Bisection Method

1. Initial Condition

Start with x_L and x_R such that:

f(x_L) \times f(x_R) < 0

Why?: We want two points that enclose a zero (opposite signs)

2. Calculate midpoint

x_M = \frac{x_L + x_R}{2} \qquad \text{error} = x_R - x_L

3. Evaluate function at midpoint and shrink window

Stopping Criteria: Stop here and return x_M if:

• f(x_M)=0, or
• |\text{error}| < \epsilon

If f(x_L) f(x_M) < 0, root is in left half. Update x_R \leftarrow x_M

• Else, x_L \leftarrow x_M

Return to step 2.

Note — The speed is good at the start (halving repeatedly), but then it takes ages to converge.

Pseudocode

function Bisection (f : float \rightarrow float, a : float, b : float, maxIter : int, eps : float)
    fa := call f(a)
    fb := call f(b)

    if fa \large{*} fb \ge 0 then
        // Inadequate values for a and b.
        return -1.0
    end if

    error := b \text{$-$} a

    for it \leftarrow to maxIter
        error := error / 2
        c := a \text{$+$} error
        fc := call f(c)

        if |error| \lt eps or fc = 0 then
            // Algorithm has converged after #{it} iterations!
            return c
        end if

        if fa \large{*} fc \lt 0 then
            b := c
            fb := fc
        else
            a := c
            fa := fc
        end if
    end for

    // Max Iterations reached without convergence...
    return c
end function

Notice in the code we calculate the midpoint a little oddly. Mathematically, we’re just doing:

x_M = \frac{x_R - x_L}{2} + x_L

This modified form uses the error as the numerator, which lets us kill two birds with one stone.

Newton’s Method

1. Initialization

Start with initial value x_0, f, and f'.

2. Evaluate f and f' at x_0

Calculate f(x_0) and f'(x_0).

3. Compute the next iteration value

\boxed{ x_{i+1} = x - \frac{f(x_{i})}{f'(x_{i})} }

4. Check if complete

Stopping Criteria: Stop here and return x_i if |f(x_i) / f'(x_i)| < \epsilon, otherwise:

Return to step 2.

Note — This method is a lot faster than bisection, but getting the derivative isn’t trivial, especially with real-world data.

• The next method (Secant), will solve this by approximating the derivative
• Future chapters will give us ways to make functions that describe given data.

Pseudocode

function Newton (f : float \rightarrow float, derF : float \rightarrow float, x : float, maxIter : int, eps : float, delta : float)
    fx := call f(x)
    for it \leftarrow to maxIter
        fd := call derF(x)

        if |fd| \lt delta then
            // Small slope!
            return x
        end if

        d := fx / fd
        x := x \text{$-$} d
        fx := call f(x)

        if |d| \lt eps then
            // Algorithm has converged after #{it} iterations!
            return x
        end if
    end for

    // Max iterations reached without convergence...
    return x
end function

Secant Method

Like Newton’s but you use this to compute next iteration value.

\boxed{ x_i = x_{i-1} - \frac{ (x_{i-1} - x_{i-2}) f(x_{i-1}) }{ f(x_{i-1}) - f(x_{i-2}) } }

Note — We approximate the derivative using the two previous points, which also means we need two initial guesses instead of one.

The error term is \Delta, which is just \text{new point} - \text{old point}

• (e.g., error of x_3: \Delta_3 = x_3 - x_2)

f(x) := 3x^2 - 4x + 1
i(x, y) := x - ( x - y )( f(x) )/( f(x) - f(y) )
s(x, y) := [ i(x, y) , f(i(x, y)) ]

Pseudocode

function Secant(f : float \rightarrow float, a : float, b : float, maxIter : int, eps : float)
    fa := call f(a)
    fb := call f(b)

    if |fa| \gt |fb| then
        swap(a,b)
        swap(fa,fb)
    end if
    for it \leftarrow to maxIter
        if |fa| \gt |fb| then
            swap(a,b)
            swap(fa,fb)
        end if
        d := (b-a)/(fb-fa)
        b := a
        fb := fa
        d := d \large{*} fa

        if |d| \lt eps then
            // Algorithm has converged after ${it} iterations!
            return a
        end if

        a := a \text{$-$} d
        fa := call f(a)
    end for

    // Maximum number of iterations reached!
    return a
end function

Analysis

Addendum: Hybrid Method

Recall — Newton’s and Secant method can get stuck in dips (local extrema) in the graph. Secant method is technically less likely to get stuck by not strictly hugging the line, allowing the possibility to shoot past the dip.

Also, the bisection method is actually pretty fast at the start thanks to its halving behavior, which is then its downfall as it takes forever to converge.

Therefore — The hybrid method is where you do bisection method some amount of times (Professor recommends 5 iterations), before switching to Secant or Newton.

In other words, you quickly reduce the problem size by 96.875%, and then switch to a faster method to do the last ~3%.