Content deleted Content added
m →Variations: fmt. |
|||
| (24 intermediate revisions by 20 users not shown) | |||
Line 1:
{{Short description|Root-finding algorithm for polynomials}}
In [[numerical analysis]], the '''Durand–Kerner method''', discovered by [[Karl Weierstrass]] in 1891 and rediscovered independently by Durand in 1960 and Kerner in 1966, is a [[root-finding algorithm]] for solving [[polynomial]] [[equation (mathematics)|equations]].<ref name="Petković">{{cite book |last1=Petković |first1=Miodrag |title=Iterative methods for simultaneous inclusion of polynomial zeros |date=1989 |publisher=Springer |___location=Berlin [u.a.] |isbn=978-3-540-51485-5 |pages=31–32}}</ref> In other words, the method can be used to solve numerically the equation▼
{{refstyle|date=November 2020}}
▲In [[numerical analysis]], the '''Weierstrass method''' or '''Durand–Kerner method''', discovered by [[Karl Weierstrass]] in 1891 and rediscovered independently by Durand in 1960 and Kerner in 1966, is a [[root-finding algorithm]] for solving [[polynomial]] [[equation (mathematics)|equations]].<ref name="Petković">{{cite book |last1=Petković |first1=Miodrag |title=Iterative methods for simultaneous inclusion of polynomial zeros |date=1989 |publisher=Springer |___location=Berlin [u.a.] |isbn=978-3-540-51485-5 |pages=31–32}}</ref> In other words, the method can be used to solve numerically the equation ''f''(''x''){{=}}0, where ''f'' is a given polynomial, which can be taken to be scaled so that the leading coefficient is 1.
==Explanation==
Line 12 ⟶ 10:
: <math>f(x) = x^4 + ax^3 + bx^2 + cx + d</math>
for all ''x''. The known numbers ''a'', ''b'', ''c'', ''d'' are the [[coefficient]]s.
: <math>f(x) = (x - P)(x - Q)(x - R)(x - S)</math>
Line 28 ⟶ 22:
So if used as a [[fixed point (mathematics)|fixed-point]] [[iteration]]
: <math>x_1 := x_0 - \frac{f(x_0)}{(x_0 - Q)(x_0 - R)(x_0 - S)},</math>
it is strongly stable in that every initial point ''x''<sub>0</sub> ≠ ''Q'', ''R'', ''S'' delivers after one iteration the root ''P'' = ''x''<sub>1</sub>. Furthermore, if one replaces the zeros ''Q'', ''R'' and ''S'' by approximations ''q'' ≈ ''Q'', ''r'' ≈ ''R'', ''s'' ≈ ''S'', such that ''q'', ''r'', ''s'' are not equal to ''P'', then ''P'' is still a fixed point of the perturbed fixed-point iteration
: <math>x_{k+1} := x_k - \frac{f(x_k)}{(x_k - q)(x_k - r)(x_k - s)},</math>
Line 41 ⟶ 29:
: <math>P - \frac{f(P)}{(P - q)(P - r)(P - s)} = P - 0 = P.</math>
Note that the denominator is still different from zero. This fixed-point iteration is a [[contraction mapping]] for ''x'' around ''P''.
The clue to the method now is to combine the fixed-point iteration for ''P'' with similar iterations for ''Q'', ''R'', ''S'' into a simultaneous iteration for all roots.
Initialize ''p'', ''q'', ''r'', ''s'':
Line 64 ⟶ 48:
: <math>s_n = s_{n-1} - \frac{f(s_{n-1})}{(s_{n-1} - p_n)(s_{n-1} - q_n)(s_{n-1} - r_n)}.</math>
Re-iterate until the numbers ''p'', ''q'', ''r'', ''s'' essentially stop changing relative to the desired precision. They then have the values ''P'', ''Q'', ''R'', ''S'' in some order and in the chosen precision. So the problem is solved.
Note that [[complex number]] arithmetic must be used, and that the roots are found simultaneously rather than one at a time.
== Variations ==
This iteration procedure, like the [[Gauss–Seidel method]] for linear equations, computes one number at a time based on the already computed numbers. A variant of this procedure, like the [[Jacobi method]], computes a vector of root approximations at a time. Both variants are effective root-finding algorithms.
Both variant are effective root-finding algorithms.▼
One could also choose the initial values for ''p'', ''q'', ''r'', ''s'' by some other procedure, even randomly, but in a way that
* they are inside some not-too-large circle containing also the roots of ''f''(''x''), e.g. the circle around the origin with radius <math>1 + \max\big(|a|, |b|, |c|, |d|\big)</math>, (where 1, ''a'', ''b'', ''c'', ''d'' are the coefficients of ''f''(''x''))
and that
* they are not too close to each other,
which may increasingly become a concern as the degree of the polynomial increases.
If the coefficients are real and the polynomial has odd degree, then it must have at least one real root. To find this, use a real value of ''p''<sub>0</sub> as the initial guess and make ''q''<sub>0</sub> and ''r''<sub>0</sub>, etc., [[complex conjugate]] pairs. Then the iteration will preserve these properties; that is, ''p''<sub>''n''</sub> will always be real, and ''q''<sub>''n''</sub> and ''r''<sub>''n''</sub>, etc., will always be conjugate. In this way, the ''p''<sub>''n''</sub> will converge to a real root ''P''. Alternatively, make all of the initial guesses real; they will remain so.
== Example ==
This example is from the reference Jacoby (1992). The equation solved is {{nowrap|1=''x''<sup>3</sup> − 3''x''<sup>2</sup> + 3''x'' − 5 = 0}}. The first 4 iterations move ''p'', ''q'', ''r'' seemingly chaotically, but then the roots are located to 1 decimal. After iteration number 5 we have 4 correct decimals, and the subsequent iteration number 6 confirms that the computed roots are fixed. This general behaviour is characteristic for the method. Also notice that, in this example, the roots are used as soon as they are computed in each iteration. In other words, the computation of each second column uses the value of the previous computed columns.
::{|class="wikitable"
Line 151 ⟶ 125:
Those coefficients are, up to a sign, the [[elementary symmetric polynomial]]s <math>\alpha_1(\vec z),\dots,\alpha_n(\vec z)</math> of degrees ''1,...,n''.
To find all the roots of a given polynomial <math>f(X)=X^n+c_{n-1}X^{n-1}+\cdots+c_0</math> with coefficient vector <math>(c_{n-1},\dots,c_0)</math> simultaneously is now the same as to find a solution vector to the [[Vieta's_formulas|Vieta's system]]
:<math>\begin{matrix}
Line 181 ⟶ 155:
In the [[quotient ring]] (algebra) of [[residue class]]es modulo ƒ(''X''), the multiplication by ''X'' defines an [[endomorphism]] that has the zeros of ƒ(''X'') as [[eigenvalue]]s with the corresponding multiplicities. Choosing a basis, the multiplication operator is represented by its coefficient matrix ''A'', the [[companion matrix]] of ƒ(''X'') for this basis.
Since every polynomial can be reduced modulo ƒ(''X'') to a polynomial of degree ''n'' − 1 or lower, the space of residue classes can be identified with the space of polynomials of degree bounded by ''n'' − 1. A problem-specific basis can be taken from [[Lagrange interpolation]] as the set of ''n'' polynomials
:<math>b_k(X)=\prod_{1\le j\le n,\;j\ne k}(X-z_j),\quad k=1,\dots,n,</math>
Line 212 ⟶ 185:
==Convergence results==
The connection between the Taylor series expansion and Newton's method suggests that the distance from <math>z_k + w_k</math> to the corresponding root is of the order <math>O\big(|w_k|^2\big)</math>, if the root is well isolated from nearby roots and the approximation is sufficiently close to the root. So after the approximation is close, Newton's method converges ''quadratically''; that is
For the conclusion of linear convergence there is a more specific result (see ref. Petkovic et al. 1995). If the initial vector <math>\vec z</math> and its vector of Weierstrass updates <math>\vec w = (w_1, \dots, w_n)</math> satisfies the inequality
: <math>\max_{1 \le k \le n}
then this inequality also holds for all iterates, all inclusion disks <math>
: <math>
each containing exactly one zero of
==Failing general convergence==
The Weierstrass / Durand-Kerner method is not generally convergent: in other words, it is not true that for every polynomial, the set of initial vectors that eventually converges to roots is open and dense. In fact, there are open sets of polynomials that have open sets of initial vectors that converge to periodic cycles other than roots (see Reinke et al.)
==References==
{{Reflist}}
* {{cite conference|last=Weierstraß|first=
* {{cite conference|last=Durand|first=E.|
* {{cite journal|last= Kerner|first= Immo O.|title=Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen|journal=Numerische Mathematik|volume=8|year= 1966|issue= 3|pages= 290–294|doi=10.1007/BF02162564 |s2cid= 115307022}}
* {{cite journal|author=Prešić, Marica|title=A convergence theorem for a method for simultaneous determination of all zeros of a polynomial |url=http://elib.mi.sanu.ac.rs/files/journals/publ/48/n042p159.pdf|journal=Publications de l'Institut Mathématique |series=Nouvelle Série|volume=28|pages=158–168 |year=1980 | issue=42}}
* {{cite journal|author=Petkovic, M.S., Carstensen, C. and Trajkovic, M.|title=Weierstrass formula and zero-finding methods|journal=Numerische Mathematik|volume=69|year=1995|issue=3|pages=353–372|
* Bo Jacoby, ''Nulpunkter for polynomier'', CAE-nyt (a periodical for Dansk CAE Gruppe [Danish CAE Group]), 1988.
* Agnethe Knudsen, ''Numeriske Metoder'' (lecture notes), Københavns Teknikum.
* Bo Jacoby, ''Numerisk løsning af ligninger'', Bygningsstatiske meddelelser (Published by Danish Society for Structural Science and Engineering) volume 63 no.
* {{cite book|last=Gourdon|first=Xavier|title=Combinatoire, Algorithmique et Geometrie des Polynomes|publisher=École Polytechnique|___location=Paris|year=1996|url=http://algo.inria.fr/gourdon/thesis.html|access-date=2006-08-22|archive-url=https://web.archive.org/web/20061028060132/http://algo.inria.fr/gourdon/thesis.html|archive-date=2006-10-28|url-status=dead}}
* [[Victor Pan]] (May 2002): [https://web.archive.org/web/20060907205721/http://www.cs.gc.cuny.edu/tr/techreport.php?id=26 ''Univariate Polynomial Root-Finding with Lower Computational Precision and Higher Convergence Rates'']. Tech-Report, City University of New York
* {{cite journal|first= Arnold|last= Neumaier|title= Enclosing clusters of zeros of polynomials|journal= Journal of Computational and Applied Mathematics|volume= 156 |year=2003|issue= 2|url=https://www.mat.univie.ac.at/~neum/papers.html#polzer|doi= 10.1016/S0377-0427(03)00380-7|pages=
* Jan Verschelde, ''[
* Bernhard Reinke, Dierk Schleicher, and Michael Stoll, "[https://arxiv.org/abs/2004.04777 The Weierstrass root finder is not generally convergent]", 2020
** Bernhard Reinke, Dierk Schleicher and Michael Stoll: "The Weierstrass-Durand-Kerner root finder is not generally convergent", Math. Comp. vol.92 (2023), pp.839-866. DOI: https://doi.org/10.1090/mcom/3783 .
==External links==
* ''[https://sites.google.com/site/drjohnbmatthews/groots?authuser=0 Ada Generic_Roots using the Durand–Kerner Method] [https://web.archive.org/web/20090701041632/http://home.roadrunner.com/~jbmatthews/misc/groots.html
* ''[http://sites.google.com/site/drjohnbmatthews/polyroots Polynomial Roots]'' — an
* ''[https://web.archive.org/web/20060505043302/http://www.cpc.wmin.ac.uk/~spiesf/Solve/solve.html Roots Extraction from Polynomials : The Durand–Kerner Method]'' — contains a [[Java applet]] demonstration
[[Category:
| |||