Durand-Kerner method


Durand-Kerner method

In numerical analysis, the Durand–Kerner method (established 1960–66) or method of Weierstrass (established 1859–91) is a root-finding algorithm for solving polynomial equations. In other words, the method can be used to solve numerically the equation

: ƒ("x") = 0

where ƒ is a given polynomial, which can be taken to be scaled so that the leading coefficient is 1.

Explanation

The explanation is for equations of degree four. It is easily generalized to other degrees.

Let the polynomial ƒ be defined by

:ƒ("x") = "x"4 + "ax"3 + "bx"2 + "cx" + "d"

for all "x".

The known numbers "a, b, c, d" are the coefficients.

Let the (complex) numbers "P,Q,R,S" be the roots of this polynomial ƒ.

Then

:ƒ("x") = ("x" − "P")("x" − "Q")("x" − "R")("x" − "S")

for all "x". One can isolate the value "P" from this equation,

:P=x-frac{f(x)}{(x-Q)(x-R)(x-S)}.

The substitution :x:=x-frac{f(x)}{(x-Q)(x-R)(x-S)}is a strongly stable fixed point iteration in that every initial point "x" ≠ "Q,R,S" delivers after one iteration the root "P".

If one replaces the zeros "Q", "R" and "S" by approximations qapprox Q, rapprox R, sapprox S, such that "q,r,s" are not equal to "P", then "P"is still a fixed point of the perturbed fixed point iteration since

:P-frac{f(P)}{(P-q)(P-r)(P-s)} = P - 0 = P.

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":

:"p"0 := (0.4 + 0.9 i)0 ;:"q"0 := (0.4 + 0.9 i)1 ; :"r"0 := (0.4 + 0.9 i)2 ; :"s"0 := (0.4 + 0.9 i)3 ;

There is nothing special about choosing 0.4 + 0.9 i except that it is neither a real number nor a root of unity.

Make the substitutions for "n" = 1,2,3,··· :where w_j=-frac{f(z_j)}{b_j(z_j)} are again the Weierstrass updates.

The companion matrix of ƒ("X") is therefore: A = mathrm{diag}(z_1,dots,z_n) +egin{pmatrix}1\vdots\1end{pmatrix}cdotleft(w_1,dots,w_n ight).

From the transposed matrix case of the Gershgorin circle theorem it follows that all eigenvalues of "A", that is, all roots of ƒ("X"), are contained in the union of the disks D(a_{k,k},r_k) with a radius r_k=sum_{j e k}ig|a_{j,k}ig|.

Here one has a_{k,k}=z_k+w_k, so the centers are the next iterates of the Weierstrass iteration, and radii r_k=(n-1)left|w_k ight| that are multiples of the Weierstrass updates. If the roots of ƒ("X") are all well isolated (relative to the computational precision) and the points z_1,dots,z_ninmathbb C are sufficidently close approximations to these roots, then all the disks will become disjoint, so each one contains exactly one zero. The midpoints of the circles will be better approximations of the zeros.

Every conjugate matrix TAT^{-1} of "A" is as well a companion matrix of ƒ("X"). Choosing "T" as diagonal matrix leaves the structure of "A" invariant. The root close to z_k is contained in any isolated circle with center z_k regardless of "T". Choosing the optimal diagonal matrix "T" for every index results in better estimates (see ref. Petkovic et al 1995).

Convergence results

The connection between the Taylor series expansion and Newton's method suggests that the distance from z_k+w_k to the corresponding root is of the order O(|w_k|^2), 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: the error is squared with every step (which will greatly reduce the error once it is less than 1). In the case of the Durand-Kerner method, convergence is quadratic if the vector vec z=(z_1,dots,z_n) is close to some permutation of the vector of the roots of ƒ.

For the conclusion of linear convergence there is a more specific result (see ref. Petkovic et al 1995). If the initial vector vec z and its vector of Weierstrass updates vec w=(w_1,dots,w_n) satisfies the inequality

:max_{1le kle n}ig|w_kig| le frac1{5n} min_{1le j

then this inequality also holds for all iterates, all inclusion disks extstyle Dleft(z_k+w_k,(n-1)|w_k| ight)are disjoint and linear convergence with a contraction factor of "1/2" holds. Further, the inclusion disks can in this case be chosen as

: extstyle Dleft(z_k+w_k,frac14 |w_k| ight)qquad k = 1,dots, n,

each containing exactly one zero of ƒ.

References

*
*
*
*
*
* 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. 3-4, 1992, pp. 83-105.
*
* Victor Pan (May 2002): [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
*
* Jan Verschelde, " [http://www2.math.uic.edu/~jan/mcs471f03/Project_Two/proj2/node2.html The method of Weierstrass (also known as the Durand-Kerner method)] ", 2003.

External links

* " [http://www.cpc.wmin.ac.uk/~spiesf/Solve/solve.html Roots Extraction from Polynomials : The Durand-Kerner Method] " — contains a Java applet demonstration


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Durand–Kerner method — In numerical analysis, the Durand–Kerner method established 1960–66 and named after E. Durand and Immo Kerner, also called the method of Weierstrass, established 1859–91 and named after Karl Weierstrass, is a root finding algorithm for… …   Wikipedia

  • Durand-Kerner method — noun An algorithm for finding the roots of polynomial equations. Syn: method of Weierstrass …   Wiktionary

  • Durand-Kerner-Methode — Das Weierstraß (Durand Kerner) Verfahren (W (D K) Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum… …   Deutsch Wikipedia

  • Durand-Kerner-Verfahren — Das Weierstraß (Durand Kerner) Verfahren (W (D K) Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum… …   Deutsch Wikipedia

  • Weierstraß-(Durand-Kerner)-Verfahren — Das Weierstraß (Durand Kerner) Verfahren (W (D K) Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum… …   Deutsch Wikipedia

  • Kerner — may refer to:In literature:* Elizabeth Kerner, fantasy author * Justinus Kerner (1786 ndash;1862), a German lyric poet of the Swabian schoolIn politics:* Kerner Commission, 11 member commission assembled to investigate causes of the 1967 race… …   Wikipedia

  • Kerner — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Kerner est un patronyme d’origine germanique. Pour consulter un article plus général, voir : Nom de famille germanique. Patronyme Anton Kerner von… …   Wikipédia en Français

  • method of Weierstrass — noun Durand Kerner method …   Wiktionary

  • Aberth method — The Aberth method, sometimes named Aberth Ehrlich method is a root finding algorithm for simultaneous approximation of all the roots of a univariate polynomial. The fundamental theorem of algebra states that for each polynomial with complex… …   Wikipedia

  • Weierstraß-Iteration für Polynomnullstellen — Das Weierstraß (Durand Kerner) Verfahren (W (D K) Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum… …   Deutsch Wikipedia