Polynomial Root Finding

Numerical Analysis · Axiom Academy

Specialized techniques for finding all roots of polynomials Given a polynomial of degree n, find all n roots (counting multiplicity). A degree-n polynomial has exactly n roots (complex, counting multiplicity) Complex roots of real polynomials come in conjugate pairs No general formula exists for n ≥ 5 (Abel-Ruffini theorem) Numerical methods are essential! Example: x⁴ - 5x² + 4 has roots at x = ±1, ±2 Once we find a root r, we can factor it out and work with a lower-degree polynomial! Deflation Algorithm (Synthetic Division) Find a root r of p(x) using Newton, Muller, etc. Compute q(x) = p(x) / (x - r) using synthetic division Continue until polynomial is fully factored For p(x) = aₙxⁿ + ... + a₁x + a₀ and root r: This gives q(x) = bₙ₋₁xⁿ⁻¹ + ... + b₁x + b₀ An efficient way to evaluate polynomials and their derivatives. Instead of computing each power of x separately: Only n multiplications (vs. ~n² naive) Gives both p(x) and synthetic division Horner can compute p(x) and p'(x) simultaneously in one pass! This is essential for efficient polynomial root-finding. Enter polynomial coefficients to find all roots using deflation. A robust method specifically designed for polynomials. Cubic convergence for simple roots Very robust - almost always converges Works for complex roots from real starts NumPy/SciPy polynomial solvers Summary: Polynomial Root-Finding Strategy Use Laguerre's method or Muller's method to find roots Apply deflation to reduce degree after each root

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