WS08: Bisection and Newton’s method

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.

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?

Contents