WS08: Bisection and Newton’s method

These exercises are indented to give you practice at using the material on numerical approximation and are intended to reinforce the material that was covered in lectures.

Please attempt the worksheet before your tutorial. Support is available in your tutorial or in the Class Team.

Partial solutions are available to check your understanding. Please create Issues and Pull requests with your solutions or share your answers for peer feedback in the class team Worksheet solutions channel

Part a (pen and paper warm up)

1. Bisection method

We first check that the solution of \(f(x) = x^3 - 2 = 0\) must sit in [0,2] because \(f(0)f(2) = -2 \times 6 <0\). Can you then apply three iterations of the Bisection method to this equation and narrow down this initial solution interval?

2. Newton’s method

Apply three iterations of Newton’s method to \(f(x) = x^3 - 2 = 0\) starting from an initial guess \(x_0 = 2\).

Part b (code implementations and testing)

2. Implement Bisection and Newton’s methods

def newton(f, df, x0, tol):
    x = x0
    y = f(x)
    it = 0
    while abs(y) > tol:  # iterate until less than or eq tol
        """
        TODO: Newton's method
        """
        it = it + 1
        x = x - y / df(x)
        y = f(x)

    return x, it


def bisection(f, x0, x1, tol):
    it = 0
    x = (x0 + x1) / 2.0
    xL = x0
    xR = x1

    y = f(x)
    yL = f(xL)
    yR = f(xR)
    while abs(y) > tol:
        """
        TODO: Bisection method
        """
        if y * yL < 0:
            xR = x
            yR = y
        elif y * yR < 0:
            xL = x
            yL = y
        x = (xL + xR) / 2
        y = f(x)
        it += 1

    return x, it

3. Test your implementation

def f(t):
    return t * t * t - 2.0


def df(t):
    return 3.0 * t * t


x, it = newton(f, df, 2.0, 1.0e-6)
print(f"Newton's method: {x} after {it} iterations")

x, it = bisection(f, 0.0, 2.0, 1.0e-6)
print(f"Bisection method: {x} after {it} iterations")

Part c: Extension

In which cases, Newton’s method could fail, and what’s your corresponding strategies to save it?