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:

  1. Existence: is there a solution?
  2. Number: how many roots are there?
  3. Approximation: how do we get close enough to the one we want?

Methods in this chapter:

#MethodInterval type
1Bisection (dichotomy)closed (bracketing)
2Fixed pointopen
3Newton–Raphsonopen
4Secantopen

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 :

  1. If : root in → ,
  2. If : root in → ,
  3. 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 → keepbound true
0010.5−0.37500.50.1823
10.510.75+0.17190.250.0677
20.50.750.625−0.13090.1250.0573
30.6250.750.6875+0.01250.06250.0052
40.6250.68750.65625−0.06110.031250.0261
50.656250.68750.671875−0.02480.01560.0105

Bisection on f(x)=x³+x−1, [0,1]00.20.40.60.81-1-0.500.51[a0,b0][a1,b1][a2,b2][a3,b3][a4,b4]xf(x)f(x)root ≈ 0.6823

⚠️ 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 :

  1. is increasing, is decreasing, and for all
  2. 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.