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=(z_1^{(0)},z_2^{(0)},\dots ,z_m^{(0)})$

består Durand-Kerner av iterationen

$z_j^{(n+1)}=z_j^{(n)}-\frac{P\left(z_j^{(n)}\right)}{\prod _{k=1,k\ne j}^m(z_j^{(n)}-z_k^{(n)})}$

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.