Bairstowverfahren

Das Bairstow-Verfahren ist ein Iterationsverfahren der numerischen Mathematik und dient der Bestimmung der Nullstellen eines Polynoms. Das Verfahren wurde zuerst 1920 von Leonard Bairstow (1880–1963) im Anhang seines Buches „Applied Aerodynamics“ vorgestellt.^[1]

Jedes Polynom mit reellen Koeffizienten kann in ein Produkt aus linearen und quadratischen irreduziblen Faktoren mit ebenfalls reellen Koeffizienten zerlegt werden (Fundamentalsatz der Algebra nach Gauß, 1799). Die linearen Faktoren entsprechen reellen Nullstellen, die quadratischen konjugierten Paaren echt komplexer Nullstellen. Gibt es mehr als eine reelle Nullstelle, so können die linearen Faktoren leicht zu quadratischen kombiniert werden. Um nun das Rechnen mit komplexen Zahlen zu vermeiden, kann man nach quadratischen reellen Faktoren suchen. Das Bairstow-Verfahren ist, neben der reellen Variante des Jenkins-Traub-Verfahrens, eine Möglichkeit, solche quadratischen Faktoren zu approximieren. 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 bei jedem iterativen Verfahren hängt auch hier der Erfolg und die schnelle Konvergenz von der Wahl eines guten Startpunktes, das heißt eines initialen quadratischen Polynoms, ab, das schon fast ein Faktor des Polynoms sein sollte. Die Güte bestimmt sich dabei aus der Größe des Restes nach Polynomdivision. Im Falle eines zufällig gewählten Startpunktes ergibt sich ein Verhalten, wie es im Newton-Fraktal visualisiert wird. Hat das zu lösende Polynom mehrfache Nullstellen oder dicht beieinanderliegende Cluster von Nullstellen, so kann dieses Verfahren daran scheitern, diese zu finden.

Merkmale des Verfahrens

Polynome mit reellen Koeffizienten wie z. B. $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, aus der ein reelles oder komplex konjugiertes Nullstellenpaar bestimmt werden kann.

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 komplexe 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 eine Iteration in komplexer Arithmetik.

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

Beschreibung des Verfahrens

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

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 $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 ${\bar {z}}=u-i\,v$ . Das quadratische Polynom

a(x)=(x-z)(x-{\bar {z}})=(x-u)^{2}+v^{2}=x^{2}-2ux+(u^{2}+v^{2})

,

welches die Nullstellen $z$ und ${\bar {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)=x^{2}+a_{1}x+a_{0}$ 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

{\begin{matrix}f_{n}&=&b_{n-2}\\f_{n-1}&=&b_{n-3}+a_{1}b_{n-2}\\f_{n-2}&=&b_{n-4}+a_{1}b_{n-3}+a_{0}b_{n-2}\\&\vdots &\\f_{j}&=&b_{j-2}+a_{1}b_{j-1}+a_{0}b_{j}\\&\vdots &\\f_{2}&=&b_{0}+a_{1}b_{1}+a_{0}b_{2}\\f_{1}&=&a_{1}b_{0}+a_{0}b_{1}+r_{1}\\f_{0}&=&a_{0}b_{0}+r_{0}\end{matrix}}

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.

Mathematische Begründung

Es wird eine Faktorisierung $f(x)=a(x)b(x)$ mit einem quadratischen Faktor a(x) und einem verbleibenden Faktor b(x) gesucht. Ist jedoch a(x) nur ein näherungsweiser Faktor, so hinterlässt die Division mit Rest von f(x) durch a(x) mit Ergebnis b(x) einen Rest r(x),

f(x)=a(x)b(x)+r(x)

.

Da a(x) quadratisch ist, ist r(x) linear oder konstant. Es wird nun ein lineares Polynom $\Delta a(x)$ gesucht, sodass $a(x)+\Delta a(x)$ eine bessere Näherung für einen Faktor von f(x) ist. Ist das verbesserte Polynom sogar ein exakter Faktor, so gibt es ein Polynom $\Delta b(x)$ vom Grad n-3 mit

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 das unter Kombination beider Gleichungen

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 $\Delta a(x)$ und $\Delta b(x)$ aufgelöst werden. Die Gleichung kann jedoch mit algebraischen Mitteln weiter vereinfacht werden, so dass das schließlich zu lösende lineare System zwei Variable und genauso viele Gleichungen hat.

Da $\deg \Delta a(x)<\deg a(x)$ gilt, ist das Polynom $\Delta a(x)$ schon selbst der Vertreter kleinsten Grades in seiner Restklasse modulo a(x). Da $a(x)\Delta b(x)$ in der Restklasse der Null liegt, muss

r(x)\equiv \Delta a(x)\,b(x)\mod a(x)

gelten. Nun kann auch das Polynom b(x) modulo a(x) reduziert werden, nach einer weiteren Division mit Rest ergeben sich ein Quotient q(x) und ein linearer Rest p(x) mit $b(x)=q(x)a(x)+p(x)$ . Es ergibt sich

r(x)\equiv \Delta a(x)p(x)\mod a(x)

bzw.

r(x)=\Delta a(x)p(x)-p_{1}\Delta a_{1}\cdot a(x)

.

Als Gleichungssystem ausgeschrieben bedeutet dies

{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}={\begin{pmatrix}p_{0}&-p_{1}a_{0}\\p_{1}&p_{0}-p_{1}a_{1}\end{pmatrix}}\cdot {\begin{pmatrix}\Delta a_{0}\\\Delta a_{1}\end{pmatrix}}

.

Die Determinante der Systemmatrix ist $D=p_{0}^{2}+p_{1}(a_{0}p_{1}-a_{1}p_{0})$ . Ist diese von Null verschieden, so ergibt sich die Lösung des Systems und damit die Änderung des quadratischen Faktors g(x) als

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix}\Delta a_0\\\Delta a_1\end{pmatrix} =\frac1D\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} =\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 a(x) durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)+\Delta a(x)} ersetzt und von vorn begonnen. Man kann abbrechen, wenn die Koeffizienten des Rests r(x) sämtlich eine vorher gesetzte Schranke unterschreiten.

Grundzüge

Das Verfahren beruht auf folgenden Schritten:

Aus den Startwerten der Iteration für zwei Nullstellen wird ein quadratisches Polynom konstruiert.
Das Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Grades wird durch dieses quadratische Polynom dividiert
Das bei der Division entstehende Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n-2)} -ten Grades wird erneut durch das quadratische Polynom dividiert
Bei der Division entstehen Divisionsreste
Aus den Divisionsresten wird ein verbessertes quadratisches Polynom bestimmt
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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x) = x^2 + a_1 \cdot x + a_0 }

erhält man ein Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n-2)} -ten Grades:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Divisionsrests Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)=r_0+r_1x =p-ab} können mit der folgenden Rekursionsformel zur Bestimmung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b_i } berechnet werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n}= b_{n-1} = 0} ;

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j = p_{j+2} - a_1 \cdot b_{j+1} - a_0 \cdot b_{j+2}; \qquad \qquad j=n-2, n-3, \dots, 0,-1,-2 } ;

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_1 = b_{-1}} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_0 = b_{-2}+a_1b_{-1}} ;

Erneute Division von b(x) durch a(x) ergibt ein neues Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} und dessen Divisionsrest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x)=p_1 x+p_0\! } , wobei eine analoge Rekursionsformel zum Einsatz kommt, es gelten wieder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_1=q_{-1}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_0 = q_{-2}+a_1q_{-1}} ;

Mit den Divisionsresten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_0,\ r_1,\ p_0,\ p_1 } verbessert man die Koeffizienten des quadratischen Polynoms a(x):

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M = -a_0 \cdot q_{-1} - a_1 \cdot q_{-2} ; \qquad D = q_{-2}^2 - M \cdot q_{-1} }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta a_1 = \frac{q_{-1} \cdot b_{-2} - q_{-2} \cdot b_{-1}}{D}; \qquad \Delta a_0 = \frac{M \cdot b_{-1} - q_{-2} \cdot b_{-2}}{D}}

Die verbesserten Startwerte ergeben sich aus

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1^{neu} = a_1^{alt} - \Delta a_1 \, }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0^{neu} = a_0^{alt} - \Delta a_0 \, }

Anmerkungen zum Ablauf

Die Bestimmung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta a_0,\ \Delta a_1 } kann als Lösung des folgenden Gleichungssystems aufgefasst werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b(x)} berechnet und speichert, sondern im Schritt j die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b_j,b_{j+1},b_{j+2}} sofort dazu verwendet, auch den Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 aus den führenden drei Koeffizienten das quadratische Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)=\frac1{f_n}(f_nx^2+f_{n-1}+f_{n-2}} bilden, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1 = \frac{f_{n-1}}{f_n}; \quad a_0 = \frac{f_{n-2}}{f_n} } wählen. Wenn Näherungen für zwei Nullstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde x_1, \ \tilde x_2 } vorliegen, kann man auch alternativ nach den Vietaschen Formeln Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1 = - \tilde x_1 - \tilde x_2; \quad a_0 = \tilde x_1 \cdot \tilde x_2 } wählen.

Die Iteration kann abgebrochen werden, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, r_0 = r_1 = 0} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b_{-1}=b_{-2}=0} in der gewünschten Ergebnisgenauigkeit vorliegen, dann wurden passende Nullstellen gefunden und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, a(x)} ist ein Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, f(x)} . In diesem Fall bestimmt man alle Koeffizienten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b(x)} und dann mit dem neuen Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, f(x)=b(x)} reduzierten Grades die nächsten Nullstellen zu suchen. Denn wenn man von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, f(x)} die Linearfaktoren zu den Nullstellen abdividiert, erhält man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b(x)} .

Algorithmus

Das Programmbeispiel in Pseudocode beschreibt einen einzelnen Iterationsschritt, bei dem die Koeffizienten a0 und a1 des quadratischen Polynoms durch zwei Korrekturen da0 und da1 verbessert werden. Das Feld (Array) f() enthält das Polynom, wobei in f(n) der Koeffizient von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^n} steht. Die Bezeichnungen der Variablen wurden sonst wie in den Formeln gewählt.

In der Schleife der doppelten Polynomdivision stehen die Programmvariablen b0, b1, b2 im Schritt j für die Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, b_{j-2},b_{j-1},b_j} und entsprechend q0, q1, q2 für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, q_{j-2},q_{j-1},q_j} . Beim Übergang von Schritt j zu Schritt j−1 müssen die Programmvariablen einen Koeffizientenindex weiter geschoben werden, b2←b1←b0 und q2←q1←q0.

    j=n
    b0 = f(n)
    b1 = 0
    q0 = 0
    q1 = 0

    For j = n - 1 To 0 Step -1
        b2 = b1
        b1 = b0
        b0 = f(j) - a1 * b1 - a0 * b2

        q2 = q1
        q1 = q0
        q0 = b2   - a1 * q1 - a0 * q2
    Next j

    M  =  -a0 * q1 - a1  * q0
    D  =  q0 * q0 - M  * q1
    da1 = (b0 * q1 - b1 * q0) / D
    da0 = (b1 * M  - b0 * q0) / D

    a1  = a1 - da1
    a0  = a0 - da0

Im Ergebnis des Iterationsschritts enthalten die Programmvariablen a0 und a1 verbesserte Werte für die Koeffizienten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, a(x)=x^2+a_1x+a_0}

Beispiel

Es sollen die Nullstellen des folgenden Polynoms bestimmt werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1 = \frac{f_{n-1}}{f_n} = \frac{11}{6} ; \quad a_0 = \frac{f_{n-2}}{f_n} = - \frac{33}{6} }

Die Iteration liefert folgende Werte:

Die Iterationen des Bairstow-Verfahrens
Nr.	a1	a0	Schrittweite	Nullstellen
0	1,833333333333	−5,500000000000	5,579008780071	−0,916666666667±2,517990821623
1	2,979026068546	−0,039896784438	2,048558558641	−1,489513034273±1,502845921479
2	3,635306053091	1,900693009946	1,799922838287	−1,817653026545±1,184554563945
3	3,064938039761	0,193530875538	1,256481376254	−1,532469019881±1,467968126819
4	3,461834191232	1,385679731101	0,428931413521	−1,730917095616±1,269013105052
5	3,326244386565	0,978742927192	0,022431883898	−1,663122193282±1,336874153612
6	3,333340909351	1,000022701147	0,000023931927	−1,666670454676±1,333329555414
7	3,333333333340	1,000000000020	0,000000000021	−1,666666666670±1,333333333330
8	3,333333333333	1,000000000000	0,000000000000	−1,666666666667±1,333333333333

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)=x^2 + \frac{10}{3} \cdot x + 1 = 0 }

Die Lösungen dieser quadratischen Gleichung sind auch Lösungen des Polynoms Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) \,} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_1 = -\frac{1}{3} \qquad x_2 = -3}

Wenn man nun diese beiden Nullstellen dem Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) \,} abdividiert, kann das quadratische Polynom gleich als Startwert für die nächste Iteration verwendet werden.

Visualisierung der Konvergenz des Verfahrens

Analog zum Newton-Fraktal, welches die Konvergenz des Newton-Verfahrens gegen verschiedene Nullstellen visualisiert, kann man auch für dieses Verfahren Bilder erzeugt werden, die einen Überblick über die Konvergenz zu den verschiedenen quadratischen Faktoren ermöglichen. In den nebenstehenden Bildern wurde eine Parametrisierung gewählt, die jedem Punkt (u,v) das quadratische Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)=(x-u)^2+|v|\cdot v=x^2+(-2u)\,x+(u^2+|v|\cdot v)} als Startpunkt des Bairstow-Verfahrens zuordnet. Stellt sich ein solches Polynom als Faktor des gegebenen Polynoms heraus, so ergeben Punkte (u,v) in der oberen Halbebene v>0 das komplex konjugierte Paar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u\pm iv} als Lösungsmenge des quadratischen Faktors, in der unteren Halbebene v<0 das reelle Paar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u\pm v} . Hat das Polynom f(x) k komplexe Lösungen und s=n-2k reelle Lösungen, so gibt es k quadratische Faktoren über der x-Achse und s(s-1)/2 darunter, da jede reelle Lösung kombiniert mit jeder anderen einen möglichen Faktor ergibt.


Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=x^5-1}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=x^6-x}	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align}f(x)=&6x^5+11x^4-33x^3\\&-33x^2+11x+6\end{align}}

In den weiß gefärbten Punkten wird ein guter Faktor schon im ersten Iterationsschritt erreicht, die farbigen Punkte liefern Startwerte, deren Iteration zu dementsprechend gefärbten Bassin um einen der Faktoren führt. Der Farbverlauf entspricht der Anzahl der Iterationen bis zu einer guten Näherung, je dunkler, desto mehr Schritte wurden gebraucht. Für schwarze Startwerte findet die Iteration in den ersten 100 Schritten keinen Faktor hinreichender Genauigkeit, bzw. die Iteration divergiert. Dargestellt sind Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (u,v)\in[-3,3]^2} .

Im Allgemeinen kann man die Konvergenz dieses Verfahrens nicht garantieren, bzw. sie ist teilweise recht langsam, wie sich an den schwarzen und dunklen Flächen des ersten Bildes zum Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=x^5-1} ablesen lässt.

Man kann diese Situation teilweise beheben, indem den ungeraden Grad durch Hinzufügen einer Nullstelle in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = 0} gerade macht, also das erweiterte Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=x(x^5-1)=x^6-x} betrachtet, welches im zweiten Bild dargestellt ist. Im dritten Bild wurde das oben benutzte Beispielpolynom visualisiert.

Praktisch sinnvoller ist aber, mittels Newton-, Sekanten-Verfahren oder Regula falsi bei Polynomen ungeraden Grades zunächst eine reelle Nullstelle zu bestimmen und dann auf das reduzierte Polynom geraden Grades das Bairstow-Verfahren anzuwenden.

Siehe auch

Polynome
Bestimmung der Nullstellen, wenn die Division mit dem quadratischen Näherungspolynom ohne Rest aufgeht: Quadratische Gleichung
Abdividieren des quadratischen Polynoms mit der Polynomdivision
Andere Iterationsverfahren: Regula falsi, Newton-Verfahren, Weierstraß-(Durand-Kerner)-Verfahren

Literatur

Roland W. Freund, Ronald H. W. Hoppe: Stoer/Bulirsch: Numerische Mathematik 1. 10. Auflage. Springer, Berlin 2007, ISBN 978-3-540-45389-5, Abschnitt 5.8.1.

Einzelnachweise

↑ Bairstow, Applied Aerodynamics, Longmans, Green and Co., 1920, Archive

[1] Bairstow, Applied Aerodynamics, Longmans, Green and Co., 1920, Archive

[1]

Anonym

Suche

Bairstowverfahren

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Merkmale des Verfahrens