Bairstow-Verfahren

Beschreibung des Verfahrens

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 gesucht, sodass 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 vom Grad n-3 mit

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

.

Diese Gleichung kann in ein lineares Gleichungssystem für die Koeffizienten von und 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 gilt, ist das Polynom schon selbst der Vertreter kleinsten Grades in seiner Restklasse modulo a(x). Da in der Restklasse der Null liegt, muss

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

bzw. .

Als Gleichungssystem ausgeschrieben bedeutet dies

.

Die Determinante der Systemmatrix ist D = p²₀ + p₁ (a₀ p₁ - a₁ p₀ ). Ist diese von Null verschieden, so ergibt sich die Lösung des Systems und damit die Änderung des quadratischen Faktors g(x) als

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

Anbieterkennzeichnung