bisection method

intro

Bisection method pops up quite often when we talk about root finding methods due its very easy and simple algorithm to implement (Luna, 2020). This method uses the intermediate value theorem iteratively to find roots (Kong et al., 2020). It is also known as the interval halving method, where it provides a systematic approach to finding the root of a function within a given interval (Collimator, 2023). A brief about this method and JavaScript code are given here.

root

• Root $x = r_n$ of a function $f(x)$ is when it makes $$\tag{1} f(r_n) = 0. $$
• It can also be a root when $$\tag{2} g(r_n) = h(r_n), $$ since it can be defined that $$\tag{3} f(x) = g(x) - h(x). $$

range

• A single root $x = r_n$ exists for $x \in [x_1, x_2]$ if $$\tag{4} f(x_1) f(x_2) < 0. $$
• It also holds for odd number of roots.
• If the requirement is not satisfied there might be even number of roots or there is not any root.
• From now on only case with one root is considered here.
• Even that $x_1 < r_n < x_2$, but the value of $r_n$ is still unknown.

method

• Find the midpoint between $x_1$ and $x_2$ is a way to approach the $r_n$ $$\tag{5} x_3 = \tfrac12 (x_1 + x_2), $$ where the name comes from, bisection, divide the range into two equal parts.
• Next step is to find where the root exists with two possibilities, which are $x_1 < r_n < x_3$ or $x_3 < r_n < x_2$ by calculating which one from $f(x_1)f(x_3)$ and $f(x_2)f(x_3)$ is negative.
• If $x_1 < r_n < x_3$ then swap $x_2$ and $x_1$.
• Then calculate next midpoint using equation similar to the last one $$\tag{6} x_4 = \tfrac12 (x_2 + x_3). $$
• Repeat the step until $|f(x_n)| > \varepsilon$, where $\varepsilon$ is small value regarding as zero.

flowchart

• The method can be represented in a flowchart as follow.
• The symbol a ↔ b means swapping a and b values.

  // define a and b
  let a = 2;
  let b = 10;
  
  // swap a and b via c
  let c = a;
  a = b;
  b = c;
  

example

• Suppose that there is a function $$\tag{7} f(x) = x - 3.45, $$ whose root is to be find with $\varepsilon = 10^{-5}$, and initial values are $0$ and $20$.

• Following code is in JavaScript

  function f(x) {
    let y = x - 3.45;
    return y
  }
  
  let eps = 1E-5;
  let fxn = 100;
  let x = [];
  let y = [];
  
  console.log('n', 'xn', 'f(xn)');
  
  let n = 0;
  x[n] = 0;
  y[n] = f(x[n]);
  console.log(n, x[n], y[n]);
  
  n++;
  x[n] = 20;
  y[n] = f(x[n]);
  console.log(n, x[n], y[n]);
  n++;
  
  while(Math.abs(fxn) > eps) {
    x[n] = 0.5 * (x[n-1] + x[n-2]);
    y[n] = f(x[n]) 
    fxn = y[n];
  
    if(f(x[n]) * f(x[n-2]) < 0) {
      [x[n-1], x[n-2]] = [x[n-2], x[n-1]];
      [y[n-1], y[n-2]] = [y[n-2], y[n-1]];
    }
  
    console.log(n, x[n], y[n]);
  
    n++;
  }
  

  url https://onecompiler.com/javascript/3zw6fwzav

• Result

• Discussion

  • It finds $r_1 \approx 3.44999$ where $f(r_1) \approx -6.866\times10^{-6}$, whose absolute value is already smaller than $\varepsilon$.
  • Further exploration with $\varepsilon = 10^{-20}$ requires more steps, $n = 56$, to obtain $r_1 = 3.45$.

graphics

• Previous data can be visualized for $r_1$ as follow.
• It can also visualized for $f(r_1)$ as follow.
• You may hover your mouse on a point to see its pair values.
• JS code to produce the data for Chart.js embeded here is available https://onecompiler.com/javascript/3zw6zv4x9 .

challenges

• Modify above given code to find the root with $\varepsilon = 10^{-20}$, display the last three lines, and show that it requires $n = 56$.
• Modify the code to calculate a root of $$\tag{8} f(x) = (x - 3.45)(x + 1). $$ Explain whether the initial values $0$ and $20$ can be used or they must be changed.
• What if the function is $$\tag{9} f(x) = (x - 3.45)(x - 1), $$ can the initial values still be used? If they must be changed, what are your suggestion?

refs

• Collimator (2023) “Understanding the Basics of the Bisection Method”, url https://www.collimator.ai/reference-guides/what-is-the-bisection-method .
• Kong Q, Siauw T, Bayen A (2020) “Python Programming and Numerical Methods”, Academic Press, 1st edition, isbn 9780128195499 , ch 19.03 .
• Luna C M (2020) “Bisection Method”, Medium, @cmluna2913/32c8fb2e76a0 .