Root Finding — Bracketing

Bisection Method

The bisection method finds a root of f(x) by halving an interval [a,b] where f(a) and f(b) have opposite signs. Apply to f(x)=x²-2 on [1,2]: after 3 steps the root lies in [1.375,1.5], interval width 0.1250.

Example

Add one bisection row per iteration until the bracket is narrow enough.

highlighted = computed this step

Step 1 — Set up

Start with the bracket from 1 to 2.

f(x)=x2−2[1,2]f(x)= x^{2}-2 \quad [ 1 , 2 ]

Step 2 — Iteration 1

Add bisection iteration 1 to the table.

nabmf(m)update11.00002.00001.5000+0.2500b=m\begin{array}{cccccc}\text{n} & \text{a} & \text{b} & \text{m} & \text{f(m)} & \text{update} \\ \hlmath{1} & \hlmath{1.0000} & \hlmath{2.0000} & \hlmath{1.5000} & \hlmath{+0.2500} & \hlmath{\text{b=m}}\end{array}

Step 3 — Iteration 2

Add bisection iteration 2 to the table.

nabmf(m)update11.00002.00001.5000+0.2500b=m21.00001.50001.2500−0.4375a=m\begin{array}{cccccc}\text{n} & \text{a} & \text{b} & \text{m} & \text{f(m)} & \text{update} \\ 1 & 1.0000 & 2.0000 & 1.5000 & +0.2500 & \text{b=m} \\ \hlmath{2} & \hlmath{1.0000} & \hlmath{1.5000} & \hlmath{1.2500} & \hlmath{-0.4375} & \hlmath{\text{a=m}}\end{array}

Step 4 — Iteration 3

Add bisection iteration 3 to the table.

nabmf(m)update11.00002.00001.5000+0.2500b=m21.00001.50001.2500−0.4375a=m31.25001.50001.3750−0.1094a=m\begin{array}{cccccc}\text{n} & \text{a} & \text{b} & \text{m} & \text{f(m)} & \text{update} \\ 1 & 1.0000 & 2.0000 & 1.5000 & +0.2500 & \text{b=m} \\ 2 & 1.0000 & 1.5000 & 1.2500 & -0.4375 & \text{a=m} \\ \hlmath{3} & \hlmath{1.2500} & \hlmath{1.5000} & \hlmath{1.3750} & \hlmath{-0.1094} & \hlmath{\text{a=m}}\end{array}

Step 5 — Bracketed root

The final bracket is 1.3750 to 1.5000 with width 0.1250.

[1.3750,1.5000]w=0.1250[ \hlmath{1.3750} , \hlmath{1.5000} ]\quad w= \hlmath{0.1250}
bisection-method If f(a)<0 and f(b)>0, a root exists in [a,b]. Compute midpoint m=(a+b)/2. If f(m) has the same sign as f(a), replace a with m; otherwise replace b with m. Repeat.