Chapter 2 — Solutions of Equations in One Variable

This chapter is about solving \(f(x)=0\) for a single unknown. Almost no equation of interest can be solved in closed form, so instead we build a sequence \(p_0, p_1, p_2, \ldots\) that converges to a root and stop when we are close enough. The three methods here — bisection, fixed-point iteration and Newton’s method — trade robustness against speed, and §2.4 makes that trade-off precise.

2.1 The Bisection Method

The method needs only one thing: a sign change. If \(f\) is continuous on \([a,b]\) and \(f(a)\) and \(f(b)\) have opposite signs, the intermediate value theorem (Theorem 1.8) guarantees a root somewhere between them. Evaluate \(f\) at the midpoint, keep whichever half still shows a sign change, and repeat.

Because the root always stays inside the current bracket, \(a_n \le p \le b_n\), and taking \(p_n\) to be the midpoint gives \[ |p_n - p| \le \tfrac{1}{2}(b_n - a_n). \] The interval is halved each step, so \[ b_n - a_n = \frac{b-a}{2^{\,n-1}}, \qquad\text{hence}\qquad |p_n - p| \le \frac{1}{2}\cdot\frac{b-a}{2^{\,n-1}} = \frac{b-a}{2^{\,n}} \] for \(n \ge 1\). This is a genuine error bound, known in advance, which is what makes bisection so dependable — and it is unusual: none of the faster methods in this chapter come with anything like it.

function p = bisection(f, a, b, tol)
% Solve f(p) = 0 using the bisection method.

for n = 1:100
    p = (a + b) / 2;
    if p - a < tol
        break
    end
    if f(a) * f(p) > 0
        a = p;
    else
        b = p;
    end
end

2.2 Fixed-Point Iteration

A fixed point of \(g\) is a value \(p\) with \(g(p) = p\). Root-finding and fixed-point problems are interchangeable: given \(f\), we can rearrange \(f(x) = 0\) into the form \(x = g(x)\) and then look for a fixed point instead.

Existence and uniqueness

The two hypotheses do different jobs. That \(g\) maps \([a,b]\) into itself gives existence; the derivative bound \(|g'(x)| \le k < 1\) gives uniqueness.

Without the derivative bound, existence still holds but uniqueness can fail.

The iteration

function p = fixedpoint(g, p0, tol)
% Solve g(p) = p using fixed-point iteration.

for n = 1:100
    p = g(p0);
    if abs(p - p0) < tol
        break
    end
    p0 = p;
end

Given a starting value \(p_0\), simply feed each output back in: \[ p_n = g(p_{n-1}), \qquad n = 1, 2, \ldots \] If the sequence converges, its limit must be a fixed point — provided \(g\) is continuous, which is what lets the limit pass through \(g\): \[ p = \lim_{n\to\infty} p_n = \lim_{n\to\infty} g(p_{n-1}) = g\Bigl(\lim_{n\to\infty} p_{n-1}\Bigr) = g(p). \]

The iteration has a memorable picture. From \(p_n\) on the horizontal axis, move vertically to the curve to get \(g(p_n) = p_{n+1}\), then horizontally to the diagonal \(y=x\) to bring that value back onto the axis, and repeat.

Here the iterates alternate around \(p\) — \(p_1 < p_3 < p < p_2 < p_0\) — which is what a negative \(g'\) near the fixed point produces. A positive \(g'\) gives a staircase approaching from one side instead.

2.3 Newton’s Method and Its Extensions

Graphical derivation

Newton’s method replaces \(f\) by its tangent line at the current iterate and takes the next iterate to be where that tangent meets the axis. The tangent at \((p_0, f(p_0))\) has slope \(f'(p_0)\), and it crosses \(y=0\) at \(p_1\), so \[ f'(p_0) = \frac{0 - f(p_0)}{p_1 - p_0}, \qquad\text{which rearranges to}\qquad p_1 = p_0 - \frac{f(p_0)}{f'(p_0)} . \]

Taylor polynomial derivation

The same formula falls out of Taylor’s theorem, which also shows what is being neglected. Suppose \(f \in C^2[a,b]\), that \(p_0 \in [a,b]\), and that \(f'(p_0) \ne 0\). Expanding about \(p_0\) and evaluating at the root \(p\), \[ f(p) = f(p_0) + (p - p_0)f'(p_0) + \frac{(p-p_0)^2}{2}f''(\xi(p)) . \] Now set \(f(p) = 0\) and drop the quadratic term, which is small when \(p_0\) is close to \(p\): \[ 0 \approx f(p_0) + (p-p_0)f'(p_0) \qquad\Longrightarrow\qquad p \approx p_0 - \frac{f(p_0)}{f'(p_0)} \equiv p_1 . \]

Iterating gives Newton’s method: \[ p_n = p_{n-1} - \frac{f(p_{n-1})}{f'(p_{n-1})} . \]

This is fixed-point iteration in disguise, \(p_n = g(p_{n-1})\), with \[ g(x) = x - \frac{f(x)}{f'(x)} . \] Everything we proved in §2.2 therefore applies — and the discarded quadratic term is exactly why Newton converges so much faster than a generic fixed-point iteration.

function p = newton(f, df, p0, tol)
% Solve f(p) = 0 using Newton's method.

for n = 1:100
    p = p0 - f(p0) / df(p0);
    if abs(p - p0) < tol
        break
    end
    p0 = p;
end

Convergence

Proof of Newton convergence.

The plan is to find an interval \([p-\delta, p+\delta]\) on which \(g\) satisfies the fixed-point theorem: \(g\) maps it into itself, and \(|g'(x)| \le k < 1\).

(1) Since \(f'(p) \ne 0\) and \(f'\) is continuous, there is a \(\delta_1 > 0\) with \(f'(x) \ne 0\) on \([p - \delta_1, p + \delta_1]\), so \(g\) is defined there.

(2) On that interval, differentiating \(g\) with the quotient rule, \[ g'(x) = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{[f'(x)]^2} = \frac{f(x)f''(x)}{[f'(x)]^2}, \] so \(g \in C^1[p-\delta_1, p+\delta_1]\).

(3) Evaluating at the root, where \(f(p) = 0\), \[ g'(p) = \frac{f(p)f''(p)}{[f'(p)]^2} = 0 . \] Since \(g'\) is continuous and vanishes at \(p\), there is a \(\delta\) with \(0 < \delta < \delta_1\) and a constant \(0 < k < 1\) such that \[ |g'(x)| \le k \qquad\text{for } x \in [p-\delta, p+\delta]. \]

(4) It remains to check that \(g\) maps the interval into itself. By the mean value theorem, for \(x \in [p-\delta, p+\delta]\), \[ |g(x) - p| = |g(x) - g(p)| = |g'(\xi)|\,|x-p| \le k\,|x-p| < |x-p| , \] using \(g(p) = p\). Since \(|x - p| < \delta\), this gives \(|g(x) - p| < \delta\): that is, \(g\) maps \([p-\delta, p+\delta]\) into itself.

(5) Both hypotheses hold, so the fixed-point theorem applies and \(\{p_n\}_{n=0}^\infty\) converges to \(p\) for any \(p_0 \in [p-\delta, p+\delta]\). ■

Notice what the theorem does not say. Convergence is guaranteed only for \(p_0\) close enough to \(p\), and the proof gives no way to find \(\delta\) in practice. This is the price of Newton’s speed: unlike bisection, it can fail outright from a bad starting point.

Variations without derivatives

Newton’s method needs \(f'\), which may be unavailable or expensive. The secant method replaces it with a difference quotient over the two most recent iterates: if \(p_0\) is close to \(p_1\), then \[ f'(p_1) \approx \frac{f(p_1) - f(p_0)}{p_1 - p_0}. \] Substituting into Newton’s formula gives the secant method, which needs two starting values but no derivatives.

Comparing with Figure 2.5, the secant method takes more steps for the same accuracy: its order of convergence is about \(1.618\) rather than \(2\). But each step costs one function evaluation instead of two, which often makes it the better bargain in practice.

2.4 Error Analysis for Iterative Methods

To compare methods we need to say precisely how fast an error shrinks. If \[ \lim_{n\to\infty} \frac{|p_{n+1} - p|}{|p_n - p|^{\alpha}} = \lambda \] for constants \(\alpha > 0\) and \(\lambda > 0\), then \(\{p_n\}\) converges to \(p\) with order \(\alpha\) and asymptotic error constant \(\lambda\). The cases \(\alpha = 1\) and \(\alpha = 2\) are common enough to have names: linear and quadratic convergence.

Convergence of fixed-point iteration

So a generic fixed-point iteration is linearly convergent, and the only way to do better is to arrange \(g'(p) = 0\).

Newton’s method as a quadratic fixed-point iteration

The two results above suggest how to derive Newton’s method rather than guess it: look for a fixed-point iteration with \(g'(p) = 0\). Try \[ g(x) = x - \phi(x)f(x) \] for some function \(\phi\) to be determined. Any such \(g\) has the right fixed point, since \(f(p) = 0\) gives \[ g(p) = p - \phi(p)f(p) = p . \] Now impose the condition for quadratic convergence. Differentiating and using \(f(p)=0\) again, \[ g'(p) = 1 - f'(p)\phi(p) = 0 \qquad\Longrightarrow\qquad \phi(p) = \frac{1}{f'(p)} . \] Choosing \(\phi(x) = 1/f'(x)\) throughout gives \[ g(x) = x - \frac{f(x)}{f'(x)}, \] which is exactly Newton’s method. So if \(f(p) = 0\) and \(f'(p) \ne 0\), Newton’s method converges (at least) quadratically — and this derivation shows the quadratic rate was designed in, not a lucky accident.

Multiplicity of zeros

The caveat \(f'(p) \ne 0\) matters. A root where \(f'(p) = 0\) as well is a multiple root, and Newton’s method degrades to linear convergence there.

Variants for multiple roots

The fix is to apply Newton’s method not to \(f\) but to \[ \mu(x) = \frac{f(x)}{f'(x)}, \] which has a simple root wherever \(f\) has a multiple one. Differentiating, \[ \mu'(x) = \frac{f'(x)f'(x) - f(x)f''(x)}{[f'(x)]^2} = 1 - \frac{f(x)f''(x)}{[f'(x)]^2}, \] and substituting both into Newton’s formula, \[ p_{n+1} = p_n - \frac{\mu(p_n)}{\mu'(p_n)} = p_n - \frac{f(p_n)/f'(p_n)} {1 - f(p_n)f''(p_n)/[f'(p_n)]^2} . \] Clearing the compound fraction gives the modified Newton’s method: \[ p_{n+1} = p_n - \frac{f(p_n)\,f'(p_n)} {[f'(p_n)]^2 - f(p_n)\,f''(p_n)} . \]

The cost is that \(f''\) is now needed, and the denominator involves a cancellation that can lose accuracy near the root.