Polynomial roots (Durand–Kerner)
Self‑contained complex root solver with an “explain & check” harness. Enter coefficients; get roots, residuals, Vieta checks, and a rebuild test.
What this is?
This tool finds all complex roots of a polynomial using the Durand–Kerner (Weierstrass) method.
How it works: normalize to monic; choose distinct complex seeds; iterate
x_k ← x_k − P(x_k) / ∏_{j≠k}(x_k − x_j) simultaneously. For simple roots and generic starting points,
all roots converge quickly.
Why it’s correct (sketch): roots are fixed points of this map; locally it behaves like a simultaneous Newton step.
We stop when all updates are < 1e‑14 or after a hard iteration cap.
Proof harness: after solving we compute tiny residuals |P(r)|, check Vieta’s identities on the monic form,
and rebuild the polynomial from the roots to compare coefficients.
Answer
Reason why
Sorting & formatting. Roots are shown in a deterministic order (by rounded real, then imag parts).
Near‑integers snap to integers; we hide ±0i and print i or −i for ±1·i.
Limits. Multiple roots converge slower; here, the two included test polynomials have simple roots, so quadratic convergence is typical. Complexity per iteration is O(n²) (each update divides by a product).