Durand-Kerners metod

Durand-Kerners metod är en numerisk metod för beräkning av nollställen till polynom. Den beskrevs 1960-1966 av E. Durand och I. Kerner men bygger på resultat av Karl Weierstrass och kallas därför ibland även Weierstrass metod eller W(D-K)-metoden.

Durand-Kerner går ut på att finna alla komplexa nollställen samtidigt. Givet ett moniskt polynom P(z) av grad m och en vektor av icke-reella begynnelsevärden

$Z^{0}=\left(z_{1}^{(0)},z_{2}^{(0)},\ldots ,z_{m}^{(0)}\right)$

består Durand-Kerner av iterationen

$z_{j}^{(n+1)}=z_{j}^{(n)}-{\frac {P\left(z_{j}^{(n)}\right)}{\prod _{k=1,k\neq j}^{m}\;\left(z_{j}^{(n)}-z_{k}^{(n)}\right)}}$

för j = 1, 2, ..., m. $Z$ konvergerar då i praktiken nästan alltid mot polynomets samtliga nollställen, med kvadratisk konvergensordning om rötterna är enkelrötter. Varje iteration kräver O(m²) beräkningar.

Algoritmen kan härledas från Newtons metod.

Källor

• V. Y. Pan, Univariate Polynomial Root-Finding with a Lower Computational Precision and Higher Convergence Rates, 2002.