Dichotomy method
4 min read

Dichotomy method

Introduction

In engineering, finding a value analytically is not always easy or feasible, and in this case, you might want to use a way to approximate a value. The dichotomy method is a way to find the approximate value where a function equals zero, it is doable by hand and with the computer.

Explanation

What is this method all about and how to implement it? The idea behind this method is that we have an interval and we know that in this interval, the function equals zero at some value, we don't know what that value is but we'll try to get as close as possible to this value.
Let's call our lower and upper boundaries a and b, the next step is to get the value halfway through a and b, let's call it c. If the value at which the function goes through zero is between a and c then (if we consider that the function is strictly increasing or decreasing in the given interval),f(a)f(c)<0, otherwise, f(a)f(c)>0. Same for b and c. Then, we keep c and the boundary (either a or b) that gives us a new interval containing the value at which the function equals zero as our new boundaries and we start all over again until our interval is small enough.

This is probably somewhat confusing without an example so let's see what it would look like in an example.

Example

We'll use this method to find, for what value the exponential function equals 10. This is the same thing as asking:
For what x, does f(x)=10 with f(x)=ex ?
However, the dichotomy method is used to find a value of a function where the function equals zero, not ten. To work around that we can rewrite the question as: For what x, does f(x)=0 with f(x)=ex-10 ?
And just like that, we can go ahead and use our method to find,
for what x, does ex-10=0 ?

First of all, let's graph f(x)=ex-10

graph of f(x)=exp(x)-10

Secondly, let's choose our interval: let's say that our lower interval is a=0 and our higher interval is b=10.
The next step is to calculate the middle point: c=(a+b)/2=5
Now, let's calculate:
f(0)=-9
f(5)≅138.41
f(10)≅22016.47
Evidently, the value we search is between x=0 and x=5, but we can show that by showing that f(0)*f(5)<0 (this means that one boundary is below zero and the other is above zero).

Let's start this process all over again, with our new boundaries being 0 and 5, and our new midpoint being therefore 2.5:
f(0)=-9
f(2.5)≅2.18
f(5)≅138.41

And again, we start over with our new boundaries being 0 and 2.5 (midpoint=1.25)
f(0)=-9
f(1.25)≅-6.51
f(2.5)≅2.18
Here, we'll take 1.25 and 2.5 as our new boundaries (midpoint=1.875). If we keep going until there is a distance of 0.05 between our two boundaries, we get this graph:

In this case, our final boundaries are a≅2.27 and b≅2.30. Let's check that this is a coherent result by calculating: c=(a+b)/2=2.285 and then:
f(c)=-0.17
Which is somewhat close to 0, if we wanted to have a better value, we could have continued until we had a smaller interval. Anyway, now that we know that ex-10=-0.17, then, we know that ex=9.83, with x=2.85.

Implementation

This is the implementation I used to get those neat graphs (you can also download it below):

import math
import matplotlib.pyplot as plt
import numpy as np

def f(x): #Change this to whatever function
    return math.exp(x)-10

precision=0.01

a = 0
b = 4
c=(a+b)/2

x = np.linspace(a,b, 10000)
y = list(map(f, x))

plt.plot(x,y) #plotting the graph
plt.axvline(x=a, color='red') #these are the red lines showing the changing boundaries
plt.axvline(x=b, color='red')


while abs(a-b)>precision: #this is where everything interesting happens
    plt.axvline(x=c, color='red')
    if f(a)*f(c)<0:
        b=c
    else:
        a=c
    c=(a+b)/2

    
print(a,b) #showing the final interval
plt.show()

Just for the fun of it, let's change the function to f(x)=x3-1 and the boundaries to a=-5 and b=5. This is the graph we'd get:

Thanks a lot for reading my article, and please consider subscribing to my newsletter, it's free and keeps me motivated!