Home » maths » A binary view on bisection method

# A binary view on bisection method

Advertisements

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