Home » maths » A binary view on bisection method

A binary view on bisection method

We could argue that the bisection method is like binary search, but in a continuous space. To demonstrate that, let’s see an example where instead of limiting ourselves in decimal representation of the numbers, we also write down their binary representation. It is easy to see the pattern that in each step, one more binary digit of the root is revealed.

As a side note, the binary representation that we use is the naive one, where each digit has weight according to how many positions after the decimal point is. For instance 0.1 in our binary representation stands for 0.5 in decimal and similarly 0.01 in binary stands for 0.25 in decimal.

With that in mind, we proceed to the example.

Given the function f(x) = -x^3 + 3x^2 - 5x + 1, we find a real root. It is also given that f(0) = 1 and f(1) = -2.

We apply some steps of the bisection method as demonstrated on the table below.

x_n in binary (decimal) Interval in binary f(x_n) in decimal Interval length in binary
x1 = 0.1 (0.5) [0, 1] -0.875 1
x2 = 0.01 (0.25) [0, 0.1] -0.078125 0.1
x3 = 0.001 (0.125) [0, 0.01] 0.4199218 0.01
x4 = 0.0011 (0.1875) [0.001, 0.01] 0.161377 0.001
x5 = 0.00111 (0.21875) [0.011, 0.01] 0.039337 0.0001
x6 = 0.001111 (0.234375) [0.00111, 0.01] -0.019955 0.00001

To check the numbers above, we can use the following Python code.

Two only slightly related notes:

  • Because the bisection method is linear on the interval length, how fast we reach the desired precision depends on the initial precision (interval length).
  • Newton–Raphson is faster. Why? What kind of extra information does it use compared to the bisection method? Could we extend it somehow? (Hint: derivatives) Answer
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: