(Decrease & conquer, basically Binary Search)

It is fundamental technique in numerical analysis used for finding roots of continuous functions.

image.png

It works by repeatedly dividing an interval in half and then selecting the subinterval in which the root lies. The process is continued until the root is approximated to a desired level of accuracy.

The method is based on the Intermediate Value Theorem, which states that if a continuous function changes sign over an interval, then there is at least one root within that interval. The Bisection Method is particularly notable for its simplicity and guaranteed convergence, making it a reliable choice for solving equations where other methods might fail.

Example:

For the given function $f(x)=x^3-x-2$ over the interval $[1,2]$, approximate the root using 4 iterations.

Check:

  1. $f(x) \in C[1,2]$ since $f(x)$ is a polynomial.
  2. $f(1)=1-1-2=-2$
  3. $f(2)=8-2-2=4$
  4. $f(1)f(2) <0$ this ensures a root for the function $f$ in the interval $[1,2]$

First Iteration:

$$ c_1=\frac{1+2} 2=1.5 \quad f(c_1) = (1.5)^3-1.5-2 = -0.125 $$

Untitled Diagram.drawio.png

Second Iteration:

$$ c_2=\frac{1.5+2} 2=1.75 \quad f(c_2) = (1.75)^3-1.75-2 = 1.609375 $$

Untitled Diagram.drawio (1).png

Third Iteration:

$$ c_3=\frac{1.5+1.75} 2=1.625 \quad f(c_3) = (1.625)^3-1.625-2 = 0.666015625 $$

Untitled Diagram.drawio (2).png

Fourth & Final Iteration:

$$ c_4=\frac{1.5+1.625} 2=1.5625 \quad \text{is the root of the function} \quad f(x) $$

Sometimes the number of iterations is not specified. However we would have an Error value we have to reach for an acceptable root, given by the formula where $n$ is the number of iterations: