*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 6
Donnerstag, 21.09.2000, 16.00–16.20 Uhr, WIL C 229

Der Potenzsummen-Algorithmus für Polynomnullstellen

Herbert Möller, Universität Münster

In dem unten angegebenen Lehrbuch wurde eine neue Version des Approximationsverfahrens von D. Bernoulli entwickelt. Die Verwendung der Newtonschen Formeln für den Zusammenhang zwischen den Polynomkoeffizienten und den Potenzsummen der Nullstellen hat zu der Bezeichnung “Potenzsummen-Algorithmus” (PSA) geführt. Die Sicherheit und die Effizienz des PSA beruhen auf zwei vorher nicht bekannten theoretischen Ergebnissen, nämlich auf einer Rekursionsformel für die approximierenden Quotienten aufeinanderfolgender Potenzsummen und im Falle eines ungünstigen Ausgangs auf einer Näherungsdarstellung für den kleinsten Nullstellenbetrag mit Hilfe der schon berechneten Quotienten.

Der inzwischen ausgereifte Algorithmus zeichnet sich durch eine Reihe von weiteren Besonderheiten aus: Das Konvergenzverhalten wird nicht durch mehrfache oder gehäufte Nullstellen beeinflusst; auch im ungünstigsten Fall liegt gute Komplexität vor; in einer zweiten Phase können alle Nullstellen in “Laguerre-Kreisen” separiert werden; eine optionale dritte Phase führt zu quadratischer Konvergenz; es sind keine Schwachpunkte bekannt; die Herleitung ist elementar. Für den Vortrag wird außerdem die gute Visualisierbarkeit des PSA genutzt.

Literatur: H. Möller, Algorithmische Lineare Algebra. Verlag Vieweg, Wiesbaden 1997.