TOPICS
Search

Durand-Kerner Method


The Durand-Kerner method, also called the Weierstrass method, is a simultaneous root-finding algorithm for all the roots of a monic polynomial p of polynomial degree n. From pairwise distinct approximations z_1, ..., z_n, it updates every approximation using the old values:

 z_i^(new)=z_i-(p(z_i))/(product_(j!=i)(z_i-z_j)).

The update is Newton's method applied to the coefficient equations obtained by matching product_(j=1)^(n)(x-z_j) to p(x). To see this, write the correction to z_j as Delta_j and expand product_(j=1)^(n)(x-z_j-Delta_j) to first order in the corrections. At x=z_i, all first-order terms except -Delta_iproduct_(j!=i)(z_i-z_j) vanish. Equating that term to p(z_i) gives the update.

For simple roots and sufficiently close initial approximations, the method converges quadratically (Aberth 1973). For general initial values, it can fail to converge to the roots (Reinke et al. 2023).


See also

Ehrlich-Aberth Method, Newton's Method, Root-Finding Algorithm

Explore with Wolfram|Alpha

References

Aberth, O. "Iteration Methods for Finding All Zeros of a Polynomial Simultaneously." Math. Comput. 27, 339-344, 1973. https://doi.org/10.1090/S0025-5718-1973-0329236-7.McNamee, J. M. "Simultaneous Methods." In Numerical Methods for Roots of Polynomials, Part I. Amsterdam, Netherlands: Elsevier, pp. 67-130, 2007. https://doi.org/10.1016/S1570-579X(07)80007-3.Reinke, B.; Schleicher, D.; and Stoll, M. "The Weierstrass-Durand-Kerner Root Finder Is Not Generally Convergent." Math. Comput. 92, 839-866, 2023. https://doi.org/10.1090/mcom/3783.

Cite this as:

Weisstein, Eric W. "Durand-Kerner Method." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Durand-KernerMethod.html

Subject classifications