1. Introduction
The root-finding problem
Given a continuous , find such that
is a root (or zero) of . It can also be read as where two graphs intersect, or as the extremum of a function (solve ).
Three questions must be answered:
- Existence: is there a solution?
- Number: how many roots are there?
- Approximation: how do we get close enough to the one we want?
Methods in this chapter:
| # | Method | Interval type |
|---|---|---|
| 1 | Bisection (dichotomy) | closed (bracketing) |
| 2 | Fixed point | open |
| 3 | Newton–Raphson | open |
| 4 | Secant | open |
2. Intermediate Value Theorem (Recall)
Theorem – IVT
If is continuous on and is any number between and , then there is with . (There may be several such .)
Corollary – Existence and uniqueness of a root
- Existence: if (a) is continuous on and (b) , then has at least one root in .
- Uniqueness: if in addition is strictly monotone on , the root is unique.
Example (extra)
on : , → at least one root. → strictly increasing → exactly one root ().
⚠️ guarantees an odd number of roots (counted with multiplicity), not one. Without monotonicity there may be 3, 5, … roots. Also does not prove there is no root (there could be 2).
3. Bisection Method (Dichotomy)
Idea
Start with a bracket where changes sign. Halve it, keep the half where the sign change remains, and repeat. Each midpoint approximates .
Algorithm
Set , . At iteration :
- If : root in → ,
- If : root in → ,
- If : is the root, stop.
Stop when (then take ) or when .
⚠️ The slides’ “generalized algorithm” tests instead of . Both work, but the branches flip: . Choose one convention and stick with it.
flowchart TD S["a₀=a, b₀=b with f(a)f(b) < 0"] --> C["cₙ = (aₙ+bₙ)/2"] C --> Z{"f(cₙ) = 0 ?"} Z -->|yes| R["root = cₙ"] Z -->|no| T{"f(aₙ)·f(cₙ) < 0 ?"} T -->|yes| L["bₙ₊₁ = cₙ, aₙ₊₁ = aₙ"] T -->|no| U["aₙ₊₁ = cₙ, bₙ₊₁ = bₙ"] L --> E{"|bₙ₊₁ − aₙ₊₁| < ε ?"} U --> E E -->|no| C E -->|yes| F["x* ≈ (aₙ₊₁+bₙ₊₁)/2"]
Example (extra) – on
| sign → keep | bound | true | |||||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0.5 | −0.3750 | 0.5 | 0.1823 | |
| 1 | 0.5 | 1 | 0.75 | +0.1719 | 0.25 | 0.0677 | |
| 2 | 0.5 | 0.75 | 0.625 | −0.1309 | 0.125 | 0.0573 | |
| 3 | 0.625 | 0.75 | 0.6875 | +0.0125 | 0.0625 | 0.0052 | |
| 4 | 0.625 | 0.6875 | 0.65625 | −0.0611 | 0.03125 | 0.0261 | |
| 5 | 0.65625 | 0.6875 | 0.671875 | −0.0248 | 0.0156 | 0.0105 |
⚠️ Look at : the true error grows from to . Bisection guarantees the bound halves each step, not the actual error.
Strengths and weaknesses
- ✅ Convergence is guaranteed (if is continuous and )
- ✅ The number of iterations needed for a given precision is known in advance
- ❌ Slow (linear convergence)
- ❌ The error doesn’t necessarily decrease every iteration
4. Error Bound
Theorem – Maximum error
Each iteration halves the interval, and the root lies inside it, so the error is at most half the current width:
Corollary – Number of iterations
To guarantee :
Example (extra)
On with : (i.e. compute , which is 10 midpoints).
⚠️ Watch the index: the bound for is in the denominator, because already has error .
Convergent vs divergent behaviour
- Convergent: as , and (regardless of sign)
- Divergent: drifts away from and moves away from
- If is given and a target precision is required, compute at each step and stop as soon as it is below the tolerance.
5. Convergence Study
Theorem
Let be continuous on with and a unique root in . With , and for all :
- is increasing, is decreasing, and for all
- for all
6. Order of Convergence (any method)
Definition
Let be the error at iteration . The method has order if
| Name | |
|---|---|
| (with ) | linear |
| superlinear | |
| quadratic | |
| cubic |
A higher order means the method reaches the root faster and gives smaller errors for the same number of iterations.
Example (slides) – order of bisection
⚠️ Linear with means you gain about one binary digit per iteration, or one decimal digit every iterations.