Root Finding Summary

Numerical Analysis · Axiom Academy

Key concepts and takeaways from this unit Idea: Repeatedly halve the interval containing the root Requires: Bracket [a, b] where f(a)·f(b) < 0 Convergence: Linear (one bit per iteration) Strength: Always converges — no failures! Weakness: Slow compared to other methods Idea: Follow the tangent line to find the next guess Formula: xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ) Convergence: Quadratic (digits double) Strength: Very fast near the root Weakness: Needs derivative; can diverge Idea: Approximate derivative with secant line Requires: Two initial points x₀, x₁ Convergence: Superlinear (order ≈ 1.618) Strength: No derivative needed Weakness: Can fail like Newton Idea: Convert f(x) = 0 to x = g(x) Convergence: Linear if |g'(p)| < 1 Key Insight: Newton is a special case! Choice of g matters: Same equation, different convergence Speed Comparison (Iterations to 10-Digit Accuracy) Linear (p = 1): Error multiplied by constant < 1 each step (Bisection, Fixed-Point) Superlinear (1 Faster than linear, slower than quadratic (Secant: p ≈ 1.618) Quadratic (p = 2): Error is squared — digits double! (Newton near simple roots) Rule of thumb: Quadratic ≈ 2× as many digits per iteration as linear Trade-off: Speed vs reliability — faster methods can fail Hybrid approach: Start with bisection to get close, then use Newton/secant Newton is special: It's fixed-point iteration with g(x) = x - f(x)/f'(x) Watch for pitfalls: f'(x) = 0, poor initial guesses, multiple roots

This is the written version of the interactive lesson above. See the full Numerical Analysis course.