The Newton Method as Efficient Root Finder of Polynomials

点击翻译按钮获取中文摘要

Im Rahmen dieses Forschungsprojekts soll das klassische Newton- Verfahren zum Finden von Nullstellen komplexer Polynome von einer Heuristik zu einem effizienten Algorithmus aufgewertet werden. Dieses Verfahren hat gut bekannte lokale Eigenschaften und wird praktisch-heuristisch viel verwendet, aber die globale Dynamik ist bislang nicht gut verstanden. Die Theorie der Numerischen Analysis untersucht daher andere effiziente Nullstellen-Algorithmen (z.B. basierend auf Matrix-Operationen). Ist p ein komplexes Polynom vom Grad d, dann ist das zugehörige Newton-Verfahren eine rationale Abbildung vom Grade höchstens d, und die Newton-Dynamik fügt sich daher ein in die Theorie iterierter rationaler Abbildungen. In diesem Forschungsprojekt liegt der Fokus darauf, ein besseres Verständnis der globalen Eigenschaften des Newton-Verfahrens zu finden. Konkret besteht das Ziel dieses Forschungsprojekts darin, einen Algorithmus basierend auf dem Newton-Verfahren zu entwickeln, der zu einem gegebenen komplexen Polynom p und einer Genauigkeit eine approximative Liste der Nullstellen von p mit gegebener Genauigkeit liefert. Zum Projekt gehört die explizite Bestimmung der Effizienz dieses Algorithmus mit dem Ziel, die Laufzeit polynominal quadratisch in der Genauigkeit und polynominal in d zu erreichen.