Chapter 3 – Solving ODEs: Root-Finding Methods

Lesson and interactive activities on locating roots graphically or numerically, implementing the bisection (dichotomy) method, and applying Newton’s (Newton–Raphson) method.

Locating a root of an equation

Lesson: use graphical and simple numerical scans to find intervals containing roots.

Lesson. To solve an equation f(x) = 0 numerically, the first step is to locate intervals where roots can lie. Graphically, one plots y = f(x) and looks for x-intercepts; numerically, one evaluates f on a grid of points and detects sign changes between consecutive values. If f is continuous and f(a) and f(b) have opposite signs on [a, b], then by the intermediate value property there exists at least one root in (a, b), so [a, b] is said to bracket a root.

Exercise 1 – Locate a root by sign changes

Work with the preset function f(x) = x³ − x − 2. Scan an interval and automatically detect subintervals where f changes sign, indicating at least one root.

Discussion

The scan does not give the root directly but identifies where to start more precise methods such as bisection or Newton’s method.

Bisection (dichotomy) method

Lesson: systematically shrink an interval that brackets a root.

Lesson. The bisection method assumes an initial bracket [a, b] such that f(a) and f(b) have opposite signs and f is continuous. At each step, one computes the midpoint c = (a + b) / 2 and evaluates f(c); depending on the sign of f(c), the new bracket is [a, c] or [c, b]. This procedure halves the interval length at every iteration, converging linearly to a root and guaranteeing success as long as the assumptions hold.

Exercise 2 – Bisection on x³ − x − 2

Use the bisection method to approximate a root of f(x) = x³ − x − 2, starting from the default bracket [1, 2], which is known to contain a root. Choose the maximum number of iterations and a tolerance for the interval length.

Algorithm 
Given a continuous f and [a, b] with f(a) * f(b) < 0:

for k = 0, 1, 2, ...
  c = (a + b) / 2
  if f(c) = 0 or (b - a)/2 < tolerance: stop
  else if f(a) * f(c) < 0:
       b = c
       // root in [a, c]
  else:
       a = c
       // root in [c, b]

Newton’s method (Newton–Raphson)

Lesson: use tangent lines to converge rapidly to a root.

Lesson. Newton’s method improves a guess xₙ to a root of f(x) = 0 by following the tangent line at (xₙ, f(xₙ)) to where it crosses the x-axis. The update formula is xₙ₊₁ = xₙ − f(xₙ) / f′(xₙ), which can converge quadratically when f is smooth and the initial guess is close to a simple root. However, if f′(xₙ) is small or the starting point is poorly chosen, the method may diverge or converge to an unintended root, so bracketing or prior analysis is important.

Exercise 3 – Newton’s method on cos(x) − x

Consider f(x) = cos(x) − x, which has a root near x ≈ 0.739. Choose an initial guess x₀ and iterate Newton’s method up to a given number of steps, observing the convergence.

Iteration formula 
For f(x) = cos(x) − x:

f'(x) = −sin(x) − 1

Newton iteration:
x_{n+1} = x_n − f(x_n) / f'(x_n).

Stop when |x_{n+1} − x_n| is below the chosen tolerance or
when the maximum number of iterations is reached.