Math 2.0

Numerical analysis Nonlinear equations Theorem

Durand–Kerner method

Builds on Newton's methodRoot of a polynomialMonic polynomialFundamental theorem of algebraRate of convergenceComplex numbers

Statement

Let pp be a monic polynomial of degree n≥2n \ge 2 with complex coefficients, whose roots r1,…,rnr_1, \dots, r_n are pairwise distinct. The Durand–Kerner method, also called the Weierstrass method, updates nn approximations z1(k),…,zn(k)z_1^{(k)}, \dots, z_n^{(k)} simultaneously by zi(k+1)=zi(k)−p(zi(k))∏j≠i(zi(k)−zj(k)),i=1,…,n.z_i^{(k+1)} = z_i^{(k)} - \frac{p\big(z_i^{(k)}\big)}{\prod_{j \ne i} \big(z_i^{(k)} - z_j^{(k)}\big)}, \qquad i = 1, \dots, n. Then there is δ>0\delta > 0 such that, if ∣zi(0)−ri∣<δ\abs{z_i^{(0)} - r_i} < \delta for all ii, the iterates are defined and zi(k)→riz_i^{(k)} \to r_i for each ii, with quadratic convergence.

Remarks

The update is Newton's method applied to the system of nn equations in nn unknowns that says that ∏i(x−zi)=p(x)\prod_i (x - z_i) = p(x) as polynomials. Equivalently, it is Newton's method for the coefficients of the factorization, and the Jacobian of this system is invertible exactly when the ziz_i are distinct. This explains the local quadratic convergence at simple roots. The fundamental theorem of algebra guarantees that pp has nn complex roots counted with multiplicity. A usual start takes zi(0)=wi−1z_i^{(0)} = w^{i-1} for a complex number ww that is neither real nor a root of unity, for example w=0.4+0.9−1w = 0.4 + 0.9 \sqrt{-1}. With such starts the method usually converges in practice, but the theorem above is only local. At multiple roots the convergence is only linear.

Going deeper

For a student

The method avoids deflation, which can lose accuracy when roots are removed one by one. Each step costs O(n2)O(n^2) operations. The Aberth method is a refinement with cubic local convergence.

Reading path

To understand this page from the ground up, read these 40 pages in order. The foundations come first.

Show the path as a graph
Complex numbers, object, no evidence levelComplex numbersobjectGroup, concept, no evidence levelGroupconceptLimit point of a set, definition, no evidence levelLimit point of a setdefinitionRate of convergence, concept, no evidence levelRate of convergenceconceptReal numbers, object, no evidence levelReal numbersobjectRoot of a polynomial, concept, no evidence levelRoot of a polynomialconceptSet bounded above, definition, no evidence levelSet bounded abovedefinitionComplex exponential, definition, no evidence levelComplex exponentialdefinitionContour integral, definition, no evidence levelContour integraldefinitionPower series in the complex plane, definition, no evidence levelPower series in the c…definitionReal and imaginary parts, definition, no evidence levelReal and imaginary pa…definitionRing, definition, no evidence levelRingdefinitionLimit of a function, definition, no evidence levelLimit of a functiondefinitionSupremum, definition, no evidence levelSupremumdefinitionCircle integral, definition, no evidence levelCircle integraldefinitionDisc of convergence, definition, no evidence levelDisc of convergencedefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionDerivative, definition, no evidence levelDerivativedefinitionCompleteness axiom, statement, no evidence levelCompleteness axiomstatementEstimation lemma, statement, no evidence levelEstimation lemmastatementDegree of a polynomial, definition, no evidence levelDegree of a polynomialdefinitionTangent line, concept, no evidence levelTangent lineconceptExistence of square roots of nonnegative reals, statement, no evidence levelExistence of square r…statementLeading coefficient, definition, no evidence levelLeading coefficientdefinitionNewton's method, concept, no evidence levelNewton's methodconceptSquare root, definition, no evidence levelSquare rootdefinitionMonic polynomial, definition, no evidence levelMonic polynomialdefinitionModulus of a complex number, definition, no evidence levelModulus of a complex …definitionComplex differentiability, definition, no evidence levelComplex differentiabi…definitionHolomorphic function, definition, no evidence levelHolomorphic functiondefinitionCauchy's integral formula, statement, no evidence levelCauchy's integral for…statementEntire function, definition, no evidence levelEntire functiondefinitionPower series are holomorphic in the disc of convergence, statement, no evidence levelPower series are holo…statementHolomorphic functions are analytic, statement, no evidence levelHolomorphic functions…statementHolomorphic functions are infinitely differentiable, statement, no evidence levelHolomorphic functions…statementCauchy's integral formula for derivatives, statement, no evidence levelCauchy's integral for…statementCauchy's estimates, statement, no evidence levelCauchy's estimatesstatementLiouville's theorem, statement, no evidence levelLiouville's theoremstatementFundamental theorem of algebra, statement, no evidence levelFundamental theorem o…statementDurand–Kerner method, statement, no evidence levelDurand–Kerner methodstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complex numbers object
  2. Group concept
  3. Limit point of a set definition
  4. Rate of convergence concept
  5. Real numbers object
  6. Root of a polynomial concept
  7. Set bounded above definition
  8. Complex exponential definition
  9. Contour integral definition
  10. Power series in the complex plane definition
  11. Real and imaginary parts definition
  12. Ring definition
  13. Limit of a function definition
  14. Supremum definition
  15. Circle integral definition
  16. Disc of convergence definition
  17. Polynomial ring definition
  18. Derivative definition
  19. Completeness axiom statement
  20. Estimation lemma statement
  21. Degree of a polynomial definition
  22. Tangent line concept
  23. Existence of square roots of nonnegative reals statement
  24. Leading coefficient definition
  25. Newton's method concept
  26. Square root definition
  27. Monic polynomial definition
  28. Modulus of a complex number definition
  29. Complex differentiability definition
  30. Holomorphic function definition
  31. Cauchy's integral formula statement
  32. Entire function definition
  33. Power series are holomorphic in the disc of convergence statement
  34. Holomorphic functions are analytic statement
  35. Holomorphic functions are infinitely differentiable statement
  36. Cauchy's integral formula for derivatives statement
  37. Cauchy's estimates statement
  38. Liouville's theorem statement
  39. Fundamental theorem of algebra statement
  40. Durand–Kerner method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Durand–Kerner_method
About this page
Tag3X6C5SC7AF
URIm2://3X6C5SC7AF
Kindstatement, theorem
WritingW0 stub
MSC65H04
StatusThis copy of the site has no build data. Run m2 status 3X6C5SC7AF.
AboutRoot of a polynomial
UsesNewton's method, Root of a polynomial, Monic polynomial, Fundamental theorem of algebra, Rate of convergence, Complex numbers
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.