Q&A: Which is Faster, Bisection or Newton’s Method?

Cross-posted from here.

Want to get notified about new posts? Join the mailing list.

Question

I read that Newton’s method is faster than bisection, but for comparing speed of the bisection method with Newton’s method, I just tried the corresponding Python functions like this:

import numpy as np
from scipy.optimize import bisect, newton
import time

# Define an example function
def f(x):
    return x**3 - 2

# Bisection method
start_time_bisection = time.time()
root_bisection = bisect(f, 1, 2)
end_time_bisection = time.time()
time_bisection = end_time_bisection - start_time_bisection

# Newton's method
start_time_newton = time.time()
root_newton = newton(f, 1.0)
end_time_newton = time.time()
time_newton = end_time_newton - start_time_newton

# Print results
print("Bisection Method Result:", root_bisection)
print("Newton's Method Result:", root_newton)
print("Bisection Method Time:", time_bisection)
print("Newton's Method Time:", time_newton)

The results on my laptop were:

Bisection Method Result: 1.2599210498951834
Newton's Method Result: 1.2599210498947795
Bisection Method Time: 2.0265579223632812e-05
Newton's Method Time: 0.00040721893310546875

In this case, the bisection method was faster.

Answer

The example you gave comparing bisection and Newton’s method is not a fair comparison. Sure, bisection ran faster for you, but Newton’s method produced a more accurate result by at least several orders of magnitude (you’re not holding the level of precision constant, so it’s not an apples-to-apples comparison). Additionally, you didn’t supply any information about the derivative into Newton’s method, so you’re artificially hamstringing it to use a difference approximation (which takes longer).

To find the root of $x^3-2$ a proper comparison would be to compare iterating the function update_newton(x) = 2/3 * (x + 1/x^2) versus update_bisection(bounds) = [bounds[0], m] if m**3 > 2 else [m, bounds[1]] (where m = (bounds[0]+bounds[1])/2) until the desired level of convergence.

Doing this, we see that Newton’s method is in fact faster.

Num Trials:              1000
True Root:               1.259921049894873191
Epsilon:                 0.000000000001000000

Bisection Method Result: 1.259921049895638134
Newton's Method Result:  1.259921049895406320

Bisection Method Time:   0.000012086868286133
Newton's Method Time:    0.000001034021377563

Here’s the script:

import time

def update_bisection(bounds):
    mid = (bounds[0] + bounds[1]) / 2
    if mid**3 > 2:
        return [bounds[0], mid]
    else:
        return [mid, bounds[1]]

def update_newton(x):
    # f(x) = x^3 - 2
    # x - f(x) / f'(x)
    # x - (x^3 - 2) / 3x^2
    # x - 1/3 x + 2/3 x^2
    # 2/3 x + 2/3 x^2
    return 2/3 * (x + 1/x**2)

root = 2**(1/3) # = 1.2599210498948732
epsilon           = 0.000000000001
num_trials = 1000

sum_results_bisection = 0
sum_results_newton = 0

def run_bisection():
    global sum_results_bisection
    guess_bisection = [1, 2]
    while abs((guess_bisection[0] + guess_bisection[1]) / 2 - root) > epsilon:
        guess_bisection = update_bisection(guess_bisection)
    sum_results_bisection += (guess_bisection[0] + guess_bisection[1]) / 2

def run_newton():
    global sum_results_newton
    guess_newton = 1.5
    while abs(guess_newton - root) > epsilon:
        guess_newton = update_newton(guess_newton)
    sum_results_newton += guess_newton

start_time_bisection = time.time()
for _ in range(num_trials):
    run_bisection()
end_time_bisection = time.time()

start_time_newton = time.time()
for _ in range(num_trials):
    run_newton()
end_time_newton = time.time()

time_bisection = (end_time_bisection - start_time_bisection) / num_trials
time_newton = (end_time_newton - start_time_newton) / num_trials
result_bisection = sum_results_bisection / num_trials
result_newton = sum_results_newton / num_trials

num_decimals = len(str(root))
format_str = "{:." + str(num_decimals) + "f}"
def format_decimal(x):
    return format_str.format(x)

print("Num Trials:             ", num_trials)
print("True Root:              ", format_decimal(root))
print("Epsilon:                ", format_decimal(epsilon))
print("")
print("Bisection Method Result:", format_decimal(result_bisection))
print("Newton's Method Result: ", format_decimal(result_newton))
print("")
print("Bisection Method Time:  ", format_decimal(time_bisection))
print("Newton's Method Time:   ", format_decimal(time_newton))

Want to get notified about new posts? Join the mailing list.