Solving nonlinear equations · Lecture 6

Root Finding and the Bisection Method

Trap the root between two points where f changes sign, then halve the interval again and again. Slow, but it never fails, and it tells you exactly how accurate it is.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: when does the ball land?

A game engine throws a ball upward at 20 m/s from a 10 m roof, with air drag. When must it play the "bounce" sound?

With drag, the height is $h(t) = 10 + 79.24\,(1 - e^{-0.5t}) - 19.62\,t$ (metres, seconds)
We need $t$ with $h(t) = 0$ . Try to solve it with algebra: $t$ is trapped both inside and outside the exponential
No school formula works. Without drag, the quadratic formula gives 4.528 s; with drag the answer is different, and the game needs it every frame
Today: a method that finds it to any accuracy, using only the sign of $h(t)$

$t$ (s)	$h(t)$ (m)	sign
0	10.000	+
1	21.559	+
2	20.849	+
3	12.699	+
4	0.036	+
5	−15.364	−

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

2 / 20

Today's goals

State the root-finding problem and rewrite any equation as $f(x) = 0$
Use the intermediate value theorem to locate a bracket $[a, b]$
Perform bisection by hand and present it as a clear iteration table
Compute the error bound and the number of iterations needed
Write bisection in Python and C
Explain its limitations and which later methods remove them

Last time

Conditioning and stability: accuracy needs a well-posed problem and a careful algorithm.

Today

The first of five root-finding methods. Bisection is the safest, the slowest, and the benchmark for all the others.

Solving nonlinear equations · you are here

L6 · Root Finding and the Bisection Method→L7 · False Position Method→L8 · Fixed-Point Iteration→L9 · Newton–Raphson Method→L10 · Secant Method and Nonlinear Systems

Builds on: L1, L4

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

3 / 20

Start here

The idea in one picture

The curve crosses the axis somewhere: that x is the root.f is negative at a and positive at b, so the root is between them.Look at the middle point c. Which sign does f have there?Negative, like a. So the root is in the right half: keep it.Halve again: now f(c) is positive.Keep the left part. The bracket is 4 times smaller than at the start.Each step halves the bracket. The root can never escape.

In plain words

If f is below the axis at a and above it at b, it must cross in between
Test the middle; keep the half where the sign still changes
Repeat: the trap gets half as wide every time

New words today

root: an x with f(x) = 0
bracket [a, b]: an interval known to contain the root
midpoint: c = (a + b)/2
tolerance ε: the accuracy at which we stop

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

4 / 20

The root-finding problem

Find $x$ with $f(x) = 0$ : a root of $f$ , or a zero; graphically, where the curve crosses the $x$ -axis
Any equation can be rewritten: $e^{x} = 3x \;\Rightarrow\; f(x) = e^{x} - 3x = 0$
Polynomials of degree ≥ 5 and most transcendental equations ( $\sin$ , $e^x$ , $\ln$ mixed with powers) have no formula for their roots
Two families of methods: bracketing (bisection, false position) and open (fixed point, Newton, secant)

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

5 / 20

Trapping a root: the intermediate value theorem

Intermediate value theorem: f continuous on [a, b]

f(a)\,f(b) < 0 \;\Longrightarrow\; \exists\, r \in (a,b) : f(r) = 0

A sign change guarantees at least one root (an odd number of roots)
Tabulate $f$ at a few points and look for a sign change: here $f(1) < 0 < f(2)$ , so a root lies in $[1, 2]$
Continuity matters: $f(x) = 1/(x-1)$ changes sign on $[0, 2]$ but has no root
No sign change does not mean no root: $(x-1)^2$ touches zero without crossing

$x$	0	1	2	3
$f(x) = x^3 - x - 2$	−2	−2	+4	+22

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

6 / 20

The bisection algorithm

Start with $[a, b]$ where $f(a)\,f(b) < 0$
Midpoint $c = \dfrac{a + b}{2}$ ; compute $f(c)$
If $f(a)\,f(c) < 0$ , the root is in $[a, c]$ : set $b = c$
Otherwise the root is in $[c, b]$ : set $a = c$ (if $f(c) = 0$ , stop: $c$ is the root)
Repeat until $\dfrac{b - a}{2} < \varepsilon$ ; the answer is the last midpoint

Pseudocode

input f, a, b, tol
if f(a)·f(b) > 0: stop (no bracket)
repeat up to N times:
    c ← (a + b) / 2
    if f(c) = 0 or (b − a)/2 < tol:
        return c
    if f(a)·f(c) < 0:  b ← c
    else:              a ← c

Each pass keeps the half of the bracket where the sign changes, so the root stays trapped while the bracket halves.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

7 / 20

Explore: bisection step by step

Press Next step; the shaded band is the current bracket
The table grows exactly as you would write it in a written solution
The error bound $(b-a)/2$ halves every step
Type your own $f(x)$ , $a$ and $b$

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

8 / 20

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$

$n$	$a$	$b$	$c = \tfrac{a+b}{2}$	$f(c)$	new bracket	$(b-a)/2$
1	1	2	1.5	−0.125	[1.5, 2]	0.5
2	1.5	2	1.75	+1.609375	[1.5, 1.75]	0.25
3	1.5	1.75	1.625	+0.666016	[1.5, 1.625]	0.125
4	1.5	1.625	1.5625	+0.252197	[1.5, 1.5625]	0.0625
5	1.5	1.5625	1.53125	+0.059113	[1.5, 1.53125]	0.03125
6	1.5	1.53125	1.515625	−0.034054	[1.515625, 1.53125]	0.015625

$f(1) = -2 < 0$ and $f(2) = 4 > 0$ . Each row keeps the half where $f$ changes sign. After 6 steps: root ≈ 1.5156 with error ≤ 0.0156. True root: 1.5213797.

After 6 iterations

r \approx 1.515625

,

|r - c_6| \le 0.015625

. For 4 decimal places we need

(b-a)/2^n < 0.00005

, i.e. 15 iterations.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

9 / 20

Classical vs numerical

Same problem, two approaches: $x^2 - 2 = 0$

Algebra

Classical (exact formula)

Rearrange: $x^2 = 2 \Rightarrow x = \sqrt{2}$
Exact answer, one line of algebra
But to get digits you still need a square-root algorithm (inside the calculator)

vs

Algorithm

Numerical (bisection)

$f(1) < 0 < f(2)$ : bracket $[1, 2]$
20 halvings for $10^{-6}$ : $x \approx 1.414214$
Matches $\sqrt2 = 1.4142136$ : the method is validated on a problem we can check

When the classical approach cannot work

Landing time with drag: $10 + 79.24(1 - e^{-0.5t}) - 19.62t = 0$

$t$ appears inside and outside the exponential: no algebraic rearrangement isolates it (its exact form needs the Lambert W function, not an elementary function). Bisection: $t = 4.002526$ s.

Good practice: validate a numerical method on a problem with a known answer before trusting it on one without.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

10 / 20

How accurate after $n$ steps? How many steps?

Error bound after n bisections

|r - c_n| \le \frac{b - a}{2^{n}}

Steps needed for tolerance ε

\frac{b-a}{2^n} < \varepsilon \;\Longleftrightarrow\; n > \log_2\frac{b - a}{\varepsilon} = \frac{\ln\big((b-a)/\varepsilon\big)}{\ln 2}

Example: $[1, 2]$ , $\varepsilon = 10^{-4}$ : $n > \log_2 10^4 = 13.29$ , so 14 iterations
Known in advance, independent of $f$ : a rare luxury
Each step gains one binary digit; about 3.3 steps per decimal digit ( $\log_2 10$ )
Convergence is linear with rate ½: $e_{n+1} \approx \tfrac12 e_n$

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

11 / 20

Bisection in Python and C

The loop stops when the error bound is below tol, or after 100 steps as a safety net
It checks the sign condition first and refuses a bad bracket
In C, #define f(x) is the classic textbook style; a function works too
Change f, a, b and tol, then run

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

12 / 20

Problem 2: $x^3 + x - 1 = 0$ with $a = 0.6$ , $b = 0.8$

Problem 2"Write down the code for finding a real root of the equation

x^3 + x - 1 = 0

using bisection method with initial value 0.6 and 0.8." Below: what the program prints, which you should also be able to produce by hand.

$n$	$a$	$b$	$c$	$f(c)$	$(b-a)/2$
1	0.6	0.8	0.7	+0.043000	0.1
2	0.6	0.7	0.65	−0.075375	0.05
3	0.65	0.7	0.675	−0.017453	0.025
4	0.675	0.7	0.6875	+0.012451	0.0125
5	0.675	0.6875	0.68125	−0.002581	0.00625

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

13 / 20

When bisection is fooled

Pole: $1/(x-1)$ changes sign at $x = 1$ without a root; bisection "converges" to the pole, and $f(c)$ blows up
Double root: $(x-1)^2 \ge 0$ , no sign change, bisection cannot start
Several roots: it finds one of them, not necessarily the one you want
Defence: plot or tabulate $f$ first, and check that $|f(c)|$ really becomes small

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

14 / 20

When to use it

Bisection: method profile

Best case

Any continuous $f$ with one sign change in $[a, b]$ : success is guaranteed
Cost is the same for every $f$ : $\lceil\log_2((b-a)/\varepsilon)\rceil$ steps (20 for $10^{-6}$ on a unit interval); only a lucky exact hit $f(c) = 0$ ends earlier
Noisy, step-like or black-box $f$ : only the sign is used

Worst case

Even an easy, almost straight $f$ still takes 20 steps; false position needs 1 on a straight line
No sign change (double root $(x-1)^2$ , both ends same sign): cannot start
A pole such as $1/(x-1)$ : converges to the pole, not to a root

Best suited for

Monotone functions from data: thresholds, rates, calibration
Hard real-time code that needs a fixed, known running time
The first, safe phase of a hybrid solver that hands over to Newton or secant

Avoid when

$f'$ is cheap and you need many digits many times (use Newton, L9)
You need all roots of a polynomial, or roots of a system (L10)
$f$ is discontinuous or you have not plotted it

Rule of thumb: use bisection when failure is not allowed, and to get a safe starting bracket for a faster method.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

15 / 20

Comparison

Comparative analysis: bisection vs brute-force search

Method	Idea	Evaluations for $10^{-6}$ on $[0, 1]$	Guaranteed?	Finds all roots in range?
Graph / guess	read the crossing off a plot	—	no; about 2 digits	yes, roughly
Incremental search	step $h = 10^{-6}$ from $a$ , stop at the first sign change	up to 1,000,000	yes	yes (if $h$ is small enough)
Bisection	halve the bracket	20	yes	no: one root per bracket

Best practice combines them: a coarse incremental search ( $h = 0.1$ , 10 evaluations) finds every sign change, then bisection refines each bracket in 20 more steps. Lectures 7–10 add faster refinement methods to this table.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

16 / 20

Roadmap

Limitations, and where we fix them

Bisection is the benchmark: safe and predictable. Every later root-finding method keeps one of its strengths and removes one of its weaknesses.

What it does well (keep this)

Always converges once a sign change is found
Guaranteed error bound $(b-a)/2^n$ at every step
Iteration count known in advance
Needs only the sign of $f$ : works on noisy or black-box functions

LimitationHow it is overcomeWhere

Slow: one binary digit per step (20 steps for

10^{-6}

)

→

Use the values

f(a), f(b)

, not just their signs: the chord method

Lecture 7 →

Still linear; we want digits to multiply

→

Use the slope: tangent line (Newton), or a line through two recent points (secant, L10)

Lecture 9 →

Needs a bracket with a sign change; cannot find double roots like

(x-1)^2

→

Open methods need only a starting guess: fixed point, Newton, secant

Lecture 8 →

Solves one equation in one unknown

→

Newton for systems with the Jacobian matrix

Lecture 10 →

Fooled by poles; finds only one of several roots

→

Tabulate or plot

f

first; always check

|f(c)|

(stopping rules, Lecture 1)

this lecture

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

17 / 20

Applications

Where this method runs in the real world

Click a card to see the exact step where bisection runs, with a small worked example.

Commits to search	Tests needed
1,000	10
100,000	17
1,000,000	20

$\beta$	0	0.5	1	2	5
Perp( $\beta$ )	4.000	2.715	2.046	1.462	1.041

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

18 / 20

Checkpoint

Checkpoint · think, then discuss with your neighbourBisection starts on

[0, 1]

. How many iterations guarantee an error below

10^{-6}

?

A6

B10

C20

D1,000,000

C.

n > \log_2(1/10^{-6}) = 6\log_2 10 = 19.93

, so

n = 20

. (Each decimal digit costs about 3.3 halvings.)

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

19 / 20

Summary

Key points

Rewrite as $f(x) = 0$ ; a sign change of a continuous $f$ on $[a, b]$ traps a root (IVT)
Bisection: $c = (a+b)/2$ , keep the half where the sign changes
Error bound $|r - c_n| \le (b-a)/2^n$ ; iterations $n > \log_2((b-a)/\varepsilon)$
Robust but slow (linear, rate ½); fails for double roots and is fooled by poles
Code: sign check + halving + stopping rule + iteration cap

Opening problem: solved

The ball lands at $t = 4.002526$ s: bisection on $[4, 5]$ , 20 halvings for $10^{-6}$ (the drag-free formula would say 4.528 s).

Homework

Find the root of $e^{x} - 3x = 0$ in $[0, 1]$ by bisection, 6 iterations, as a table.
How many iterations are needed to find $\sqrt{3}$ (root of $x^2 - 3$ ) in $[1, 2]$ to 6 decimal places?
Modify the C program to read $a$ , $b$ and the tolerance with scanf and to print "no sign change" when needed.
Lab: use the solver tab to check your answer to Q1.

Next lecture

The false position method. Replace the midpoint by the point where the chord crosses the axis: usually much faster, but with a surprising weakness.

Md Mahbub E Noor

Lecture 6: Root Finding and Bisection

University of Barishal

20 / 20

Root Finding and the Bisection Method

The problem: when does the ball land?

Today's goals

The idea in one picture

The root-finding problem

Trapping a root: the intermediate value theorem

The bisection algorithm

Explore: bisection step by step

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$

Same problem, two approaches: $x^2 - 2 = 0$

Classical (exact formula)

Numerical (bisection)

Landing time with drag: $10 + 79.24(1 - e^{-0.5t}) - 19.62t = 0$

How accurate after $n$ steps? How many steps?

Bisection in Python and C

Problem 2: $x^3 + x - 1 = 0$ with $a = 0.6$ , $b = 0.8$

When bisection is fooled

Bisection: method profile

Comparative analysis: bisection vs brute-force search

Limitations, and where we fix them

Where this method runs in the real world

🎮 Game physics: landing time

🔍 git bisect

🧠 t-SNE in machine learning

🎚️ Classifier threshold

🔊 Speech: filter cut-off frequency

📈 Finance: internal rate of return

Checkpoint

Summary

Root Finding and the Bisection Method

The problem: when does the ball land?

Today's goals

The idea in one picture

The root-finding problem

Trapping a root: the intermediate value theorem

The bisection algorithm

Explore: bisection step by step

Problem 1: x3−x−2=0x^3 - x - 2 = 0x3−x−2=0 on [1,2][1, 2][1,2]

Same problem, two approaches: x2−2=0x^2 - 2 = 0x2−2=0

Classical (exact formula)

Numerical (bisection)

Landing time with drag: 10+79.24(1−e−0.5t)−19.62t=010 + 79.24(1 - e^{-0.5t}) - 19.62t = 010+79.24(1−e−0.5t)−19.62t=0

How accurate after nnn steps? How many steps?

Bisection in Python and C

Problem 2: x3+x−1=0x^3 + x - 1 = 0x3+x−1=0 with a=0.6a = 0.6a=0.6, b=0.8b = 0.8b=0.8

When bisection is fooled

Bisection: method profile

Comparative analysis: bisection vs brute-force search

Limitations, and where we fix them

Where this method runs in the real world

🎮 Game physics: landing time

🔍 git bisect

🧠 t-SNE in machine learning

🎚️ Classifier threshold

🔊 Speech: filter cut-off frequency

📈 Finance: internal rate of return

Checkpoint

Summary

Problem 1: $x^3 - x - 2 = 0$ on $[1, 2]$

Same problem, two approaches: $x^2 - 2 = 0$

Landing time with drag: $10 + 79.24(1 - e^{-0.5t}) - 19.62t = 0$

How accurate after $n$ steps? How many steps?

Problem 2: $x^3 + x - 1 = 0$ with $a = 0.6$ , $b = 0.8$