Project 28: Numerical Polynomial Root Finder

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 1-2 weeks
  • Language: Python
  • Prerequisites: Projects 3, 5, and 26-27
  • Source: ML-Math P03

What You Will Build

Build a root-finding workbench for polynomial and user-selected smooth functions. Implement bisection as the dependable bracketed baseline and Newton’s method as the fast derivative-based method, with an optional secant fallback. Every solver returns a structured history containing iterates, function values, interval widths or step sizes, residual, stop reason, and iteration count. Plot the function, current bracket, tangent steps, and convergence curve. Detect invalid brackets, flat derivatives, cycles, divergence, non-finite values, and roots of even multiplicity that do not change sign. Compare methods on simple roots, repeated roots, closely spaced roots, and functions whose starting points send Newton in the wrong direction.

Real World Outcome

For a polynomial such as x^3-2x-5, the CLI prints side-by-side iteration tables and highlights the converged root on a plot. For a poor Newton starting point, it reports why the method failed or switches to a maintained bracket. Final output includes both |f(x)| and an uncertainty/step measure rather than only rounded x.

Core Question

How can an algorithm know that an approximate root is trustworthy, and what tradeoff separates guaranteed bracketing from fast local iteration?

Concepts You Must Understand First

  1. Continuity and the intermediate value theorem: opposite endpoint signs bracket at least one root.
  2. Bisection: halving a valid bracket gives predictable error reduction.
  3. Newton iteration: tangent-line intersection gives x_next=x-f/f'; convergence is local, not guaranteed.
  4. Multiplicity: repeated roots flatten the curve and may not create a sign change.
  5. Residual versus location error: small |f(x)| does not always imply small x error for ill-conditioned roots. See Sedgewick and Wayne, Algorithms, numerical methods discussions.

Build Milestones

  1. Represent polynomials robustly and evaluate values and derivatives, including edge cases.
  2. Implement bisection with bracket invariants and a formal interval-width bound.
  3. Implement Newton and secant iterations with derivative and non-finite guards.
  4. Add a hybrid mode that uses Newton only when its proposal stays safely inside a bracket.
  5. Visualize histories and build a failure-case test catalog.

Hints in Layers

  1. Make solver output a record rather than a bare float; termination evidence is part of the result.
  2. Use both residual and step/bracket tolerance, plus a maximum iteration count.
  3. In hybrid mode, preserve the sign-changing bracket after every accepted step.

Common Pitfalls and Debugging

  • Symptom: bisection “converges” without a root. Cause: endpoints never bracketed a sign change. Fix: validate before iteration and report even-multiplicity limitations.
  • Symptom: Newton jumps to infinity. Cause: derivative is nearly zero or start is outside the attraction basin. Fix: guard slope size and fall back to bisection.
  • Symptom: solver loops despite stable printed digits. Cause: exact equality was used. Fix: define residual, step, and iteration tolerances.

Definition of Done

  • Bisection preserves its bracket invariant and reports an error bound.
  • Newton converges rapidly on well-behaved simple roots.
  • Hybrid mode recovers from unsafe Newton proposals.
  • Repeated-root, no-real-root, invalid-bracket, and flat-derivative cases are documented.
  • Iteration plots and tables expose convergence behavior.
  • Final answers include residual, uncertainty measure, and stop reason.

Previous: Project 27 · Complete learning path · Next: Project 29