Inhalt
Bairstow-Verfahren| Beschreibung des Verfahrens | |
\begin{pmatrix}p_0r_0+p_1(a_0r_1-a_1r_0)\\p_0r_1-p_1r_0\end{pmatrix} | |
Bairstow-Verfahren
Beschreibung des Verfahrens
Gegeben sei ein Polynom n-ten Grades, dessen Nullstellen gesucht werden:
.
Die Koeffizienten des Polynoms sind sämtlich reelle Zahlen. Würde man nun in einer direkten Anwendung des Newton-Verfahrens auf die Gleichung f(x) = 0 mit einem reellen Startwert beginnen, so wären alle Glieder der Iterationsfolge wieder reell. Um auch komplexe Nullstellen zu finden, müsste die Rechnung mit komplexen Zahlen durchgeführt werden. Das war bei älteren Programmiersprachen nicht ohne größeren Aufwand möglich.
Jedoch haben Polynome f(x) mit reellen Koeffizienten die Eigenschaft, dass komplexe Nullstellen immer in konjugiert komplexen Paaren auftreten, ist z = u + i v eine Nullstelle, so auch z = u - i v. Das quadratische Polynom
- a(x) = (x - z)(x - z) = (x - u)2 + v2 = x2 - 2ux + (u2 + v2 ),
welches die Nullstellen z und z hat, ist auch ein Faktor des Polynoms f(x) und hat ebenfalls nur reelle Koeffizienten. Statt also direkt Nullstellen zu bestimmen, werden zunächst quadratische Faktoren gesucht.
Ist a(x) = x2 + a1 x + a0 ein quadratischer Faktor von f(x), so gibt es einen weiteren Faktor b(x) vom Grad n-2, der durch Polynomdivision bestimmt werden kann. Ist a(x) kein Faktor, so ergibt die Polynomdivision einen Rest r(x), der ein lineares oder konstantes Polynom ist. Der Rest bestimmt sich dabei aus der Identität f(x)=a(x)b(x)+r(x). Nach einem Koeffizientenvergleich ergibt sich ein System quadratischer Gleichungen in den Koeffizienten
Aus den oberen n-1 Gleichungen lassen sich die Koeffizienten von b(x) aus denen von a(x) und f(x) bestimmen. Aus den letzten zwei Gleichungen ergeben sich die Koeffizienten des Restpolynoms. Das Ziel des Verfahrens ist es, diese durch Anpassen von a(x) möglichst klein zu halten. Aus dem Berechnungsschema ist ersichtlich, dass die Koeffizienten von b(x) und letztlich auch die des Restes r(x) Polynome in den zwei variablen Koeffizienten von a(x) sind. Dieses 2x2-System kann nun mit dem Newtonverfahren angegangen werden.
Die notwendige Bestimmung auch der Ableitungen des Gleichungssystems kann mit algebraischen Mitteln vereinfacht werden.
Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Bairstow-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren