Bairstowverfahren

Das Bairstow-Verfahren ist ein Iterationsverfahren der numerischen Mathematik und dient dazu, die Nullstellen eines Polynoms zu bestimmen.

Merkmale des Verfahrens

Polynome mit reellen Koeffizienten können auch komplexe Nullstellen haben. Mit Verfahren wie der Regula Falsi und dem Newton-Verfahren, die nur eine Nullstelle finden, ist nicht möglich, komplexe Nullstellen zu finden, ohne dass auch die Berechnung im Komplexen mit komplexer Arithmetik ausgeführt wird. Das Bairstow-Verfahren nutzt die Eigenschaft von Polynomen mit reellen Koeffizienten, die besagt, dass komplexe Nullstellen immer paarweise konjugiert auftreten und sich somit als Lösung einer quadratischen Gleichung mit rein reellen Koeffizienten schreiben läßt.

Die Merkmale des Verfahrens in der Übersicht:

• Bei einem Polynom mit reellen Koeffizienten arbeitet das Bairstow-Verafhren vollständig im Reellen und
• findet auch eventuell auftretende, paarweise konjugiert komplexen Nullstellen (a+bi und a-bi).
• Die Nullstellenberechnung wird auch Programmen zugänglich, die mit komplexer Arithmetik nicht umgehen können
• Eine Iteration in reeller Arithmetik ist erheblich schneller, als die Berechnung in komplexer Arithmetik.

Das Bairstow-Verfahren ist aus dem Newton-Verfahren abgeleitet und konvergiert wie dieses mit 2. Ordnung.

Algorithmus

Gegeben sei ein Polynom n-ten Grades, dessen Nullstellen gesucht werden:

$f(x)=a_{n}\cdot x^{n}+a_{n-1}\cdot x^{n-1}+...+a_{1}\cdot x+a_{0}$.

Grundzüge des Verfahrens

Das Verfahren beruht auf folgenden Schritten:

1. Aus den Startwerten der Iteration für zwei Nullstellen wird ein quadratisches Polynom konstruiert.
2. Das Polynom n-ten Grades wird durch dieses quadratische Polynom dividiert
3. Das bei der Division entstehende Polynom (n-2)-ten Grades wird erneut durch das quadratische Polynom dividiert
4. Bei der Division entstehen Divisionsreste
5. Aus den Divisionsresten wird ein verbessertes quadratisches Polynom bestimmt
6. Wenn bei der Polynomdivision kein Rest mehr bleibt, sind die Nullstellen des quadratischen Polynoms auch Nullstellen des Polynoms n-ten Grades.

Iteration

• Durch Polynomdivision mit dem quadratischen Polynom

$p(x)=x^{2}+p\cdot x+l$

erhält man ein Polynom (n-2)-ten Grades:

$q(x)=q_{n}\cdot x^{n-2}+q_{n-1}\cdot x^{n-3}+...+q_{3}\cdot x+q_{2}$

Die zugehörigen beiden Divisionsreste $q_{0},q_{1}\,$ können mit der folgenden Rekursionsformel zur Bestimmung von $\,q_{s}$ berechnet werden:

$q_{s}=a_{s}+p\cdot q_{s+1}+l\cdot q_{s+2};\qquad q_{n+2}=q_{n+1}=0;\qquad s=n,n-1,...0$

• Erneute Division von q(x) durch p(x) ergibt sich ein neues Polynom und dessen Divisionsreste $t_{1}$ und $t_{0}$

wobei ebenfalls eine Rekursionsformel zum Einsatz kommt

$t_{s}=q_{s+2}+p\cdot t_{s+1}+l\cdot t_{s+2};\qquad t_{n}=t_{n-1}=0;\qquad s=n-2,n-3,...0$

• Mit den Divisionsresten $q_{0},\ q_{1},\ t_{0},\ t_{1}$ verbessert man die Koeffizienten p, l des quadratischen Polynoms:

$M=l\cdot t_{1}+p\cdot t_{0};\qquad D=t_{0}^{2}-M\cdot t_{1}$

$\Delta l={\frac {M\cdot q_{1}-t_{0}\cdot q_{0}}{D}};\qquad \Delta p={\frac {t_{1}\cdot q_{0}-t_{0}\cdot q_{1}}{D}}$

• Die verbesserten Startwerte ergeben sich aus

$p_{neu}=p_{alt}-\Delta p\,$

$l_{neu}=l_{alt}-\Delta l\,$

Anmerkungen zum Ablauf

• Die Bestimmung von $\Delta p,\ \Delta l$ kann als Lösung des folgenden Gleichungssystems aufgefasst werden:

${\begin{pmatrix}t_{0}&t_{1}\\M&t_{0}\end{pmatrix}}\cdot {\begin{pmatrix}\Delta p\\\Delta l\end{pmatrix}}=-{\begin{pmatrix}q_{1}\\q_{0}\end{pmatrix}}$

• Das Verfahren läßt sich numerisch relativ einfach, schnell und speichergünstig umsetzen, wenn man nicht erst q(x) berechnet und speichert, sondern die $q_{s}$ sofort dazu verwendet, auch die Koeffizienten $t_{s}$ zu berechnen.

• Als Startwerte für die Iteration kann man beispielsweise $p={\frac {a_{n-1}}{a_{n}}};\quad l={\frac {a_{n-2}}{a_{n}}}$ wählen.

• Die Iteration kann abgebrochen werden, wenn $\,q_{0}=q_{1}=0$, dann wurden passende Nullstellen gefunden und q(x) ist ein Teiler von f(x). In diesem Fall lohnt es sich, alle Koeffizienten von q(x) bestimmen und dann mit q(x) die nächsten Nullstellen suchen, denn wenn man f(x) die Nullstellen abdividiert, erhält man q(x).

Siehe auch: Regula Falsi, Newton-Verfahren, Polynome