WS08: Bisection and Newton’s method - partial solutions

WS08: Bisection and Newton’s method - partial solutions#

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.

These are partial solutions. 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#

import numpy as np

def newton(f, df, x0, tol):
    x = x0
    y = f(x)
    it = 0
    while abs(y) > tol:  # iterate until less than or eq tol
        x = x - y / df(x)  # apply one Newton iteration
        y = f(x)  # reevaluate f at new estimate
        it = it + 1

    return x, it


def bisection(f, x0, x1, tol):
    it = 0
    x = (x0 + x1) / 2.0
    while abs(f(x)) > tol:
        it = it + 1
        x = (x0 + x1) / 2.0
        if abs(x) < 1.0e-6:
            return x
        if f(x) * f(x0) < 0:
            x1 = x
        else:
            x0 = x

    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 method: {x} after {it} iterations")
np.testing.assert_allclose(abs(f(x)), 0.0, atol=1.0e-6)

x, it = bisection(f, 0.0, 2.0, 1.0e-6)
print(f"Bisection method: {x} after {it} iterations")
np.testing.assert_allclose(abs(f(x)), 0.0, atol=1.0e-6)

Part c: Extension#

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

Contents