When a fixed-point iteration silently fails
A student writes one routine to solve nonlinear equations: read g(x), start at x0 = 0.5, iterate x_{k+1} = g(x_k), stop when |x_{k+1} − x_k| < 10^−8 or after 50 iterations, and report whichever comes first. The routine is then applied to three problems: (A) x = e^−x, (B) x = 3e^−x, and (C) x = 2e^−x. On (A) it converges in a few dozen steps and prints the root; on (B) it returns a number and the student reports it as the root; on (C) it needs more than the allowed 50 iterations. The student concludes that (B) is "solved" and that (C) is a numerical bug. No error or convergence test on |g′| is coded.
1. For problem (A), estimate the convergence rate and the number of iterations needed to reach an error of 10^−8.
Read the worked answer
Root of x = e^−x is the omega constant, x* = 0.5671. Here g′(x) = −e^−x, so |g′(x*)| = e^−0.5671 = 0.5671.
Fixed-point error behaves as e_k ≈ (g′(x*))^k e_0: |e_0| = |0.5 − 0.5671| = 0.0671.
Require 0.0671 × 0.5671^k < 1e−8: 0.5671^k < 1.49e−7 k ln 0.5671 < ln(1.49e−7) = −15.72 k > 15.72 / 0.5677 = 27.7 → k ≈ 28 iterations
So the routine's 50-iteration cap comfortably covers (A). Note this is a conservative linear estimate: quadratic terms and the fact that |g′| < 1 near but not at the root make the actual count within a few iterations of 28. Convergence is linear (first order), roughly 0.57 digits per iteration - contrast Newton's method, which would need about 4–5 iterations from the same start.
2. For problem (B), show that the returned value cannot be trusted. What is the true root and what is |g′| there?
Read the worked answer
For (B), g(x) = 3e^−x and g′(x) = −3e^−x = −g(x). At any fixed point g(x*) = x*, hence g′(x*) = −x*.
Root: x* = 3e^−x* → x* = W(3) ≈ 1.0499 (check: 3e^−1.0499 = 3 × 0.3499 = 1.0497 ✓). Then |g′(x*)| = 1.05 > 1: the fixed point is repelling, so the iteration cannot converge to it from a generic start. Indeed g maps 0.5 to 1.819, then to 0.486, and it wanders; it cannot settle.
Why the code lies: the stopping rule |x_{k+1} − x_k| < 1e−8 tests step size, not residual |g(x) − x|. For a repelling fixed point the step size can become small while the iterate is far from x* (near-tangency of g to the diagonal), so the loop exits with a plausible-looking but wrong number. The 50-iteration cap then produces a second failure mode: it exits with the last iterate, unlabelled, which the student reads as a root.
Diagnosis: always compute |g′(x)| on the interval and reject the method if it is ≥ 1 somewhere in the enclosing interval. A root of 1.05 is the true answer; the returned value is not.
3. What single check would have caught both (B) and (C) before running, and how many iterations would (C) need at tolerance 10^−12?
Read the worked answer
The diagnostic is a pre-flight contraction check: evaluate max|g′(x)| on a bracket containing the root (or verify that g maps the interval into itself - an invariant-interval test). If the maximum exceeds 1, refuse the fixed-point method and switch to Newton or bisection.
For (C), x = 2e^−x: x* = W(2) = 0.8526 and g′(x*) = −x* = −0.8526 (since g′ = −g and g(x*) = x*). It does converge, but slowly: |e_0| = 0.8526 − 0.5 = 0.3526. At tol 1e−8: 0.3526 × 0.8526^k < 1e−8 → 0.8526^k < 2.84e−8 → k > 17.38/0.1595 = 109 iterations - so a 50-step cap is genuinely insufficient and the student's "bug" is really a badly chosen cap. At tol 1e−12: k > (17.38 + 9.21)/0.1595 = 167 iterations.
General lesson: the iteration count scales as ln(1/tol)/|ln|g′||. A cap of 50 is arbitrary and must be justified from the contraction constant; and the exit condition should report which criterion fired (convergence vs. iteration limit) rather than silently returning the last iterate.