Bairstow-Verfahren

Das Bairstow-Verfahren ist ein Iterationsverfahren der numerischen Mathematik und dient dazu, die Nullstellen eines Polynoms zu bestimmen. Genauer bestimmt dieses Verfahren einen reellen quadratischen Faktor eines Polynoms mit reellen Koeffizienten. Die reellen oder komplexen Nullstellen dieses quadratischen Faktors können dann mit der bekannten Formel zum Lösen quadratischer Gleichungen bestimmt werden. Weitere Nullstellen können aus dem verbleibenden Polynom nach Abspalten des quadratischen Faktors gewonnen werden.
Wie jedes iterative Verfahren hängt der Erfolg und die schnelle Konvergenz von der Wahl eines guten Startpunktes, d.h. initialen quadratischen Faktors ab, der schon fast ein Faktor des Polynoms ist. Im Falle eines zufällige gewählten Startpunktes ergibt sich ein Verhalten, wie es im Newton-Fraktal visualisiert wird. Hat das zu lösende Polynom mehrfache Nullstellen oder [!dicht] beeinanderliegende Cluster von Nullstellen, so kann dieses Verfahren daran scheitern, diese zu finden.
 
 

Merkmale des Verfahrens

Polynome mit reellen Koeffizienten wie z.B. \(\displaystyle x^2+1\) können auch komplexe Nullstellen haben. Mit Verfahren wie der Regula Falsi und dem Newton-Verfahren, die nur eine Nullstelle finden, ist es 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. Das Verfahren findet die Nullstellen als Paar und liefert eine quadratische Gleichung mit reellen Koeffizienten, die das Nullstellenpaar liefert.
Die Merkmale des Verfahrens in der Zusammenfassung:
  • Bei einem Polynom mit reellen Koeffizienten arbeitet das Bairstow-Verfahren vollständig im Reellen und
  • findet auch eventuell auftretende, paarweise konjugiert komplexen Nullstellen (\(\displaystyle a+bi\) und \(\displaystyle 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 eine Iteration in komplexer Arithmetik.
Das Bairstow-Verfahren ist aus dem Newton-Verfahren abgeleitet und konvergiert wie dieses mit 2. Ordnung.

Beschreibung des Verfahrens

Gegeben sei ein Polynom n-ten Grades, dessen Nullstellen gesucht werden:
\(\displaystyle f(x) = f_n \cdot x^n + f_{n-1} \cdot x^{n-1} + \dots + f_1 \cdot x + f_0\).
Die Koeffizienten des Polynoms sind sämtlich reelle Zahlen. Würde man nun in einer direkten Anwendung des Newton-Verfahrens auf die Gleichung \(\displaystyle 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. Jedoch haben Polynome \(\displaystyle f(x)\) mit reellen Koeffizienten die Eigenschaft, dass komplexe Nullstellen immer in konjugiert komplexen Paaren auftreten, ist \(\displaystyle z=u+i\,v\) eine Nullstelle, so auch \(\displaystyle \bar z=u-i\,v\). Das quadratische Polynom
\(\displaystyle a(x)=(x-z)(x-\bar z)\)\(\displaystyle =(x-u)^2+v^2\)\(\displaystyle =x^2-2ux+(u^2+v^2)\),
welches die Nullstellen \(\displaystyle z,\bar z\) hat, ist auch ein Faktor des Polynoms \(\displaystyle f(x)\) und hat ebenfalls nur reelle Koeffizienten. Statt also direkt Nullstellen zu bestimmen, werden zunächst quadratische Faktoren gesucht.
Ist \(\displaystyle a(x)=x^2+a_1x+a_0\) ein quadratischer Faktor von \(\displaystyle f(x)\), so gibt es einen weiteren Faktor \(\displaystyle b(x)\) vom Grad \(\displaystyle n-2\). Betrachtet man die Koeffizienten von \(\displaystyle a\) und \(\displaystyle b\) als Unbestimmte, so ist die Gleichung \(\displaystyle f(x)=a(x)b(x)\) zu lösen. Nach einem Koeffizientenvergleich ergibt sich ein System quadratischer Gleichungen in den Koeffizienten
\(\displaystyle \begin{matrix} f_n&=&b_{n-2}\\ f_{n-1}&=&b_{n-3}+a_1b_{n-2}\\ f_{n-2}&=&b_{n-4}+a_1b_{n-3}+a_0b_{n-2}\\ &\vdots&\\ f_j&=&b_{j-2}+a_1b_{j-1}+a_0b_j\\ &\vdots&\\ f_2&=&b_0+a_1b_1+a_0b_2\\ f_1&=&a_1b_0+a_0b_1\\ f_0&=&a_0b_0 \end{matrix}\)
Aus den oberen Gleichungen lassen sich die Koeffizienten von \(\displaystyle b(x)\) aus denen von \(\displaystyle a(x)\) und \(\displaystyle f(x)\) bestimmen, aus den letzten zwei Gleichungen ergibt sich dann das System, welches mittels des Newton-Verfahrens gelöst werden soll.
Die notwendige Bestimmung auch der Ableitungen des Gleichungssystems kann mit algebraischen Mitteln vereinfacht werden.

Mathematische Begründung

Es wird eine Faktorisierung \(\displaystyle f(x)=a(x)b(x)\) mit einem quadratischen Faktor \(\displaystyle a(x)\) und einem verbleibenden Faktor \(\displaystyle b(x)\) gesucht. Ist jedoch \(\displaystyle a(x)\) nur ein näherungsweiser Faktor, so hinterlässt die Division mit Rest von \(\displaystyle f(x)\) durch \(\displaystyle a(x)\) mit Ergebnis \(\displaystyle b(x)\) einen Rest \(\displaystyle r(x)\),
\(\displaystyle f(x)=a(x)b(x)+r(x)\).
Da \(\displaystyle a(x)\) quadratisch ist, ist \(\displaystyle r(x)\) linear oder konstant. Es wird nun ein lineares Polynom \(\displaystyle \Delta a(x)\) gesucht, so dass \(\displaystyle a(x)+\Delta a(x)\) eine bessere Näherung für einen Faktor von \(\displaystyle f(x)\) ist. Ist das verbesserte Polynom sogar ein exakter Faktor, so gibt es ein Polynom \(\displaystyle \Delta b(x)\) vom Grad \(\displaystyle n-3\) mit
\(\displaystyle f(x)=\left(a(x)+\Delta a(x)\right)\cdot\left(b(x)+\Delta b(x)\right)\).
Im Newton-Verfahren werden nur Terme erster Ordnung in den Koordinaten des Änderungsvektors betrachtet, alle höhergradigen Ausdrücke werden vernachlässigt. In erster Ordnung ergibt unter Kombination beider Gleichungen
\(\displaystyle r(x)=f(x)-a(x)b(x)=a(x)\cdot\Delta b(x)+\Delta a(x)\cdot b(x)\).
Diese Gleichung kann in ein lineares Gleichungssystem für die Koeffizienten von \(\displaystyle \Delta a(x)\) und \(\displaystyle \Delta b(x)\) umgewandelt werden. Sie kann jedoch mit algebraischen Mitteln weiter vereinfacht werden, sodass das schließlich zu lösende lineare System zwei Variable und genausoviele Gleichungen hat.
Da \(\displaystyle \deg \Delta a(x)<\deg a(x)\) gilt, ist das Polynom \(\displaystyle \Delta a(x)\) der Vertreter kleinsten Grades in seiner Restklasse modulo \(\displaystyle a(x)\). Da \(\displaystyle a(x)\Delta b(x)\) in der Restklasse der Null liegt, muss
\(\displaystyle r(x)\equiv \Delta a(x)\,b(x)\mod a(x)\)
gelten. Nun kann auch das Polynom \(\displaystyle b(x)\) modulo \(\displaystyle a(x)\) reduziert werden, nach einer weiteren Division mit Rest ergeben sich ein Quotient \(\displaystyle q(x)\) und ein linearer Rest \(\displaystyle p(x)\) mit \(\displaystyle b(x)=q(x)a(x)+p(x)\). Es ergibt sich
\(\displaystyle r(x)\equiv \Delta a(x)p(x)\mod a(x)\) bzw. \(\displaystyle r(x)=\Delta a(x)p(x)-p_1\Delta a_1\cdot a(x)\).
Als Gleichungssystem ausgeschrieben bedeutet dies
\(\displaystyle \begin{pmatrix}r_0\\r_1\end{pmatrix} =\begin{pmatrix}p_0 & -p_1a_0\\ p_1 & p_0-p_1a_1\end{pmatrix} \cdot\begin{pmatrix}\Delta a_0\\\Delta a_1\end{pmatrix} \).
Die Determinante der Systemmatrix ist \(\displaystyle D=p_0^2+p_1(a_0p_1-a_1p_0)\). Ist diese von Null verschieden, so ergibt sich die Lösung des Systems und damit die Änderung des quadratischen Faktors \(\displaystyle g(x)\) als
\(\displaystyle \begin{pmatrix}\Delta a_0\\\Delta a_1\end{pmatrix} \)\(\displaystyle =\dfrac1D\begin{pmatrix}p_0-p_1a_1 & p_1a_0\\ -p_1 & p_0\end{pmatrix} \cdot\begin{pmatrix}r_0\\r_1\end{pmatrix} \)\(\displaystyle =\begin{pmatrix}p_0r_0+p_1(a_0r_1-a_1r_0)\\p_0r_1-p_1r_0\end{pmatrix} \).
Für den nächsten Schritt wird \(\displaystyle a(x)\) durch \(\displaystyle a(x)+\Delta a(x)\) ersetzt und von vorn begonnen. Man kann abbrechen, wenn die Koeffizienten des Rests \(\displaystyle r(x)\) sämtlich eine vorher gesetzte Schranke unterschreiten.

Grundzüge

Das Verfahren beruht auf folgenden Schritten:
  1. Aus den Startwerten der Iteration für zwei Nullstellen wird ein quadratisches Polynom konstruiert.
  2. Das Polynom \(\displaystyle n\)-ten Grades wird durch dieses quadratische Polynom dividiert
  3. Das bei der Division entstehende Polynom \(\displaystyle (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

\(\displaystyle a(x) = x^2 + a_1 \cdot x + a_0 \)
erhält man ein Polynom (n-2)-ten Grades:
\(\displaystyle b(x) = b_{n-2} \cdot x^{n-2} + b_{n-3} \cdot x^{n-3} + \dots + b_1 \cdot x + b_0\)
Die Koeffizienten des zugehörigen beiden Divisionsrests \(\displaystyle r(x)=r_0+r_1x =p-ab\) können mit der folgenden Rekursionsformel zur Bestimmung von \(\displaystyle \, b_i \) berechnet werden:
\(\displaystyle b_{n}= b_{n-1} = 0\);
\(\displaystyle b_j = p_{i+2} - a_1 \cdot b_{j+1} - a_0 \cdot b_{j+2}; \qquad \qquad j=n-2, n-3, \dots, 0,-1,-2 \);
\(\displaystyle r_1 = b_{-1}\) und
\(\displaystyle r_0 = b_{-2}+a_1b_{-1}\);
  • Erneute Division von \(\displaystyle b(x)\) durch \(\displaystyle a(x)\) ergibt ein neues Polynom \(\displaystyle q(x)\) und dessen Divisionsrest \(\displaystyle p(x)=p_1 x+p_0\! \), wobei eine analoge Rekursionsformel zum Einsatz kommt, es gelten wieder \(\displaystyle p_1=q_{-1}\) und \(\displaystyle p_0 = q_{-2}+a_1q_{-1}\);
  • Mit den Divisionsresten \(\displaystyle r_0,\ r_1,\ p_0,\ p_1 \) verbessert man die Koeffizienten des quadratischen Polynoms \(\displaystyle a(x)\):
\(\displaystyle M = -a_0 \cdot q_{-1} - a_1 \cdot q_{-2} ; \qquad D = q_{-2}^2 - M \cdot q_{-1} \)
\(\displaystyle \Delta a_1 = \dfrac{q_{-1} \cdot b_{-2} - q_{-2} \cdot b_{-1}}{D}; \qquad \Delta a_0 = \dfrac{M \cdot b_{-1} - q_{-2} \cdot b_{-2}}{D}\)
  • Die verbesserten Startwerte ergeben sich aus
\(\displaystyle a_1^{neu} = a_1^{alt} - \Delta a_1 \, \)
\(\displaystyle a_0^{neu} = a_0^{alt} - \Delta a_0 \, \)

Anmerkungen zum Ablauf

  • Die Bestimmung von \(\displaystyle \Delta a_0,\ \Delta a_1 \) kann als Lösung des folgenden Gleichungssystems aufgefasst werden:
\(\displaystyle \begin{pmatrix} q_{-2} & q_{-1} \\ M & q_{-2} \end{pmatrix} \cdot \begin{pmatrix} \Delta a_1 \\ \Delta a_0 \end{pmatrix} = \begin{pmatrix} - b_{-1} \\ - b_{-2} \end{pmatrix} \)
  • Das Verfahren lässt sich numerisch relativ einfach, schnell und speichergünstig umsetzen, wenn man nicht erst \(\displaystyle \, b(x)\) berechnet und speichert, sondern im Schritt \(\displaystyle j\) die \(\displaystyle \, b_j,b_{j+1},b_{j+2}\) sofort dazu verwendet, auch den Koeffizienten \(\displaystyle \, q_j=b_{j+2}-a_1q_{j+1}-a_0q_{j+2}\) zu berechnen.
  • Als Startwerte für die Iteration kann man beispielsweise \(\displaystyle p = \dfrac{a_{n-1}}{a_n}; \quad q = \dfrac{a_{n-2}}{a_n} \) wählen. Wenn Näherungen für zwei Nullstellen \(\displaystyle \tilde x_1, \ \tilde x_2 \) vorliegen, kann auch alternativ \(\displaystyle p = - \tilde x_1 - \tilde x_2\); \(\displaystyle q = \tilde x_1 \cdot \tilde x_2 \) wählen.
  • Die Iteration kann abgebrochen werden, wenn \(\displaystyle \, r_0 = r_1 = 0\) bzw. \(\displaystyle \, b_{-1}=b_{-2}=0\) in der gewünschten Ergebnisgenauigkeit, dann wurden passende Nullstellen gefunden und \(\displaystyle \, a(x)\) ist ein Teiler von \(\displaystyle \, f(x)\). In diesem Fall lohnt es sich, alle Koeffizienten von \(\displaystyle \, b(x)\) zu bestimmen und dann mit \(\displaystyle \, b(x)\) die nächsten Nullstellen zu suchen. Denn wenn man von \(\displaystyle \, f(x)\) die Linearfaktoren zu den Nullstellen abdividiert, erhält man \(\displaystyle \, b(x)\).

Beispiel

Es sollen die Nullstellen des folgenden Polynoms bestimmt werden:
\(\displaystyle f(x) = 6 \cdot x^5 + 11 \cdot x^4 - 33 \cdot x^3 - 33 \cdot x^2 + 11 \cdot x + 6\).
Die Startwerte der Iteration bestimmt man beispielsweise aus der Empfehlung
\(\displaystyle a1 = \dfrac{f_{n-1}}{f_n} = \dfrac{11}{6} ; \quad a0 = \dfrac{f_{n-2}}{f_n} = - \dfrac{33}{6} \)
Die Iteration liefert folgende Werte: Nr a1 a0 0 1,83333333333333 -5,50000000000000 1 2,97902606854572 -0,03989678443826 2 3,63530605309108 1,90069300994740 3 3,06493803975823 0,19353087552890 4 3,46183419123714 1,38567973111800 5 3,32624438656387 0,97874292718913 6 3,33334090935105 1,00002270114662 7 3,33333333333992 1,00000000001968 8 3,33333333333333 1,00000000000000
Nach der 8. Iteration wurden a1 und a0 des Näherungspolynoms im Rahmen der Rechengenauigkeit exakt bestimmt. Die Lösung ergibt sich dann aus dem Polynom
\(\displaystyle a(x)=x^2 + \dfrac{10}{3} \cdot x + 1 = 0 \)
Die Lösungen dieser quadratischen Gleichung sind auch Lösungen des Polynoms \(\displaystyle f(x) \,\):
\(\displaystyle x_1 = -\dfrac{1}{3} \qquad x_2 = -3\)
Wenn man nun diese beiden Nullstellen dem Polynom \(\displaystyle f(x) \,\) abdividiert, kann das quadratische Polynom gleich als Startwert für die nächste Iteration verwendet werden.
Bairstow-fractal_6_11_m33_m33_11_6_scale_03.png
\(\displaystyle a(x)=(Z-x)^2+\vert y\vert \cdot y\) für \(\displaystyle {(x,y)\in[-3,3]^2}\)
Im allgemeinen kann man die Konvergenz dieses Verfahrens jedoch nicht garantieren, wie sich an den schwarzen Flächen des nebenstehenden Bildes ablesen lässt. Für diese findet die Iteration in den ersten 100 Schritten keinen Faktor hinreichender Genauigkeit. In den weißen Gebieten wird ein guter Faktor schon im ersten Iterationsschritt erreicht, die farbigen Punkte liefern Startwerte, deren Iteration zu dem entsprechend gefärbten Bassin um einen der Faktoren führt.

Siehe auch

Die Mathematik ist eine Art Spielzeug, welches die Natur uns zuwarf zum Troste und zur Unterhaltung in der Finsternis.

Jean-Baptist le Rond d'Alembert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Bairstow-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе