ISSN:
1436-5057
Keywords:
AMS(MOS)
;
65H05
;
Polynomial zeros
;
Eulidean division of Chebyshev expansions
;
Sturm sequences
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir stellen einen global konvergenten Algorithmus zur Berechnung aller Nullstellen eines Polynomsp n ,p n (z) = ∑ v = 0 n a v z v, mit reellen Koeffizienten vor. Durch Aufspalten vonp n (exp(it)) in seinen Real-und Imaginärteil können wir mittels Euklidischer Division von Čebyševentwicklungen und durch Argumentation mit Sturmschen Ketten entscheiden, obp n Nullstellen im Einheitskreis hat und wie viele Nullstellen auf dem Rand und im Inneren davon liegen. Somit erhalten wir mittels einer Bisektionsstrategie die Beträge aller Nullstellen bis auf eine vorgegebene Genauigkeit, und zusätzlich finden wir die Argumente als reelle Nullstellen eines Polynoms niedrigen Grades. Auf diese Weise erzeugen wir Startnäherungen für alle Nullstellen, die in einem letzten Schritt mittels eines iterativen Prozesses höherer Konvergenzordnung verbessert werden (z.B. Newton- oder Bairstowverfahren).
Notes:
Abstract We present a globally convergent algorithm for calculating all zeros of a polynomialp n ,p n (z) = ∑ v = 0 n a v z v, with real coefficients. Splittingp n (exp(it)) into its real and imaginary part we can decide via Euclidean division of Chebyshev expansions and Sturm sequence argumentations whetherp n has some zeros on the unit circle and how many zeros lie on the boundary and in the interior of it. Hence, by a bisection strategy we get the moduli of all zeros to a prescribed accuracy, and additionally we find the arguments as real zeros of a low degree polynomial. In this way we generate starting approximations for all zeros which in a final step are refined by an iterative process of higher order of convergence (e.g. Newton's or Bairstow's method).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238233
Permalink
