Root Finding by Interval Halving: computing $\sqrt{2}$¶

Last revised on August 23, 2024

Seek $\sqrt{2}$ starting with the fact that it is between zero and 2.

In [1]:
import numpy as np
import matplotlib.pyplot as plt
In [2]:
def f(x):
    return x**2 - 2.0
a = 0
b = 2
In [3]:
c = (a+b)/2
print(f"{a=}, {b=}, with midpoint {c=}")
x = np.linspace(a, b)
plt.figure(figsize=(8,4))
plt.plot(x, f(x))
plt.plot([a, b], [0, 0], 'g')  # Mark the x-axis in green
acb = np.array([a, c, b])
plt.plot(acb, f(acb), 'b*')
plt.grid(True);  # Add a graph paper background

a=0, b=2, with midpoint c=1.0

The above graph shows that the zero is in the right-hand half, between 1 and 2, so zoom in:

In [4]:
a = c
In [5]:
c = (a+b)/2
print(f"{a=}, {b=}, with midpoint {c=}")
x = np.linspace(a, b)
plt.figure(figsize=(8,4))
plt.plot(x, f(x))
plt.plot([a, b], [0, 0], 'g')  # Mark the x-axis in green
acb = np.array([a, c, b])
plt.plot(acb, f(acb), 'b*')
plt.grid(True);  # Add a graph paper background

a=1.0, b=2, with midpoint c=1.5

Now the root is in the left-hand half, $[1, 1.5]$, so

In [6]:
b = c
In [7]:
c = (a+b)/2
print(f"{a=}, {b=}, with midpoint {c=}")
x = np.linspace(a, b)
plt.figure(figsize=(8,4))
plt.plot(x, f(x))
plt.plot([a, b], [0, 0], 'g')  # Mark the x-axis in green
acb = np.array([a, c, b])
plt.plot(acb, f(acb), 'b*')
plt.grid(True);  # Add a graph paper background

a=1.0, b=1.5, with midpoint c=1.25

One more time: the root is in the right-hand half $[1.25, 1.5]$, so

In [8]:
a = c
In [9]:
c = (a+b)/2
print(f"{a=}, {b=}, with midpoint {c=}")
x = np.linspace(a, b)
plt.figure(figsize=(8,4))
plt.plot(x, f(x))
plt.plot([a, b], [0, 0], 'g')  # Mark the x-axis in green
acb = np.array([a, c, b])
plt.plot(acb, f(acb), 'b*')
plt.grid(True);  # Add a graph paper background

a=1.25, b=1.5, with midpoint c=1.375