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 ) , … , z m ( 0 ) ) {\displaystyle 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 ) − P ( z j ( n ) ) ∏ k = 1 , k ≠ j m ( z j ( n ) − z k ( n ) ) {\displaystyle 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 {\displaystyle 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(m2) 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.