Bairstow-Verfahren

Merkmale des Verfahrens

• Bei einem Polynom mit reellen Koeffizienten arbeitet das Bairstow-Verfahren 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 eine Iteration in komplexer Arithmetik.

Beschreibung des Verfahrens

$f(x) = f_n \cdot x^n + f_{n-1} \cdot x^{n-1} + \dots + f_1 \cdot x + f_0$.

$a(x)=(x-z)(x-\bar z)$$=(x-u)^2+v^2$$=x^2-2ux+(u^2+v^2)$,

$\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}$

Mathematische Begründung

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

$f(x)=\left(a(x)+\Delta a(x)\right)\cdot\left(b(x)+\Delta b(x)\right)$.

$r(x)=f(x)-a(x)b(x)=a(x)\cdot\Delta b(x)+\Delta a(x)\cdot b(x)$.

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

$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)$.

$\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}$.

$\begin{pmatrix}\Delta a_0\\\Delta a_1\end{pmatrix}$$=\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}$$=\begin{pmatrix}p_0r_0+p_1(a_0r_1-a_1r_0)\\p_0r_1-p_1r_0\end{pmatrix}$.

Grundzüge

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

$a(x) = x^2 + a_1 \cdot x + a_0$

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

$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 $r(x)=r_0+r_1x =p-ab$ können mit der folgenden Rekursionsformel zur Bestimmung von $\, b_i$ berechnet werden:

$b_{n}= b_{n-1} = 0$;

$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$;

$r_1 = b_{-1}$ und

$r_0 = b_{-2}+a_1b_{-1}$;

• Erneute Division von $b(x)$ durch $a(x)$ ergibt ein neues Polynom $q(x)$ und dessen Divisionsrest $p(x)=p_1 x+p_0\!$, wobei eine analoge Rekursionsformel zum Einsatz kommt, es gelten wieder $p_1=q_{-1}$ und $p_0 = q_{-2}+a_1q_{-1}$;
• Mit den Divisionsresten $r_0,\ r_1,\ p_0,\ p_1$ verbessert man die Koeffizienten des quadratischen Polynoms $a(x)$:

$M = -a_0 \cdot q_{-1} - a_1 \cdot q_{-2} ; \qquad D = q_{-2}^2 - M \cdot q_{-1}$

$\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

$a_1^{neu} = a_1^{alt} - \Delta a_1 \,$

$a_0^{neu} = a_0^{alt} - \Delta a_0 \,$

Anmerkungen zum Ablauf

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

$\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 $\, b(x)$ berechnet und speichert, sondern im Schritt $j$ die $\, b_j,b_{j+1},b_{j+2}$ sofort dazu verwendet, auch den Koeffizienten $\, q_j=b_{j+2}-a_1q_{j+1}-a_0q_{j+2}$ zu berechnen.
• Als Startwerte für die Iteration kann man beispielsweise $p = \dfrac{a_{n-1}}{a_n}; \quad q = \dfrac{a_{n-2}}{a_n}$ wählen. Wenn Näherungen für zwei Nullstellen $\tilde x_1, \ \tilde x_2$ vorliegen, kann auch alternativ $p = - \tilde x_1 - \tilde x_2$; $q = \tilde x_1 \cdot \tilde x_2$ wählen.
• Die Iteration kann abgebrochen werden, wenn $\, r_0 = r_1 = 0$ bzw. $\, b_{-1}=b_{-2}=0$ in der gewünschten Ergebnisgenauigkeit, dann wurden passende Nullstellen gefunden und $\, a(x)$ ist ein Teiler von $\, f(x)$. In diesem Fall lohnt es sich, alle Koeffizienten von $\, b(x)$ zu bestimmen und dann mit $\, b(x)$ die nächsten Nullstellen zu suchen. Denn wenn man von $\, f(x)$ die Linearfaktoren zu den Nullstellen abdividiert, erhält man $\, b(x)$.

Beispiel

$f(x) = 6 \cdot x^5 + 11 \cdot x^4 - 33 \cdot x^3 - 33 \cdot x^2 + 11 \cdot x + 6$.

$a1 = \dfrac{f_{n-1}}{f_n} = \dfrac{11}{6} ; \quad a0 = \dfrac{f_{n-2}}{f_n} = - \dfrac{33}{6}$

$a(x)=x^2 + \dfrac{10}{3} \cdot x + 1 = 0$

$x_1 = -\dfrac{1}{3} \qquad x_2 = -3$

$a(x)=(Z-x)^2+\vert y\vert \cdot y$ für ${(x,y)\in[-3,3]^2}$

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ß-Iteration bzw. Durand-Kerner Verfahren

Ein Mathematiker, der nicht irgendwie ein Dichter ist, wird nie ein vollkommener Mathematiker sein.

Karl Weierstraß

Numerische Verfahren

• Kondition
• Stabilität
• Konsistenz
• Lineare Gleichungssysteme
• Nichtlineare Gleichungssysteme
  • Sekantenverfahren
  • Regula Falsi
  • Fixpunktiteration
  • Newton-Verfahren
  • Halley-Verfahren
  • Euler-Tschebyschow-Verfahren
  • Bairstow-Verfahren
  • Weierstraß-Iteration
  • Trennkreisverfahren
• Interpolation
• Approximation
• Numerische Integration