Bairstow-Methode erste quadratische Approximationen

9

Bairstows Wurzelfindungsmethode benötigt sehr gute Anfangsnäherungen für die quadratischen Faktoren, um zu konvergieren.

>

Ich habe verschiedene Konstanten, Zufallszahlen, Brüche aus dem Schleppkoeffizienten (-a1 / a2, -a0 / a2; nach Lin?) vergeblich versucht.

Bitte, kennt jemand eine gute Methode zur Auswahl der Faktoren?

Zum Beispiel:

%Vor%

Es braucht 3x so viel Zeit, um die Wurzel mit den anfänglichen Annäherungen 0,1, 0,2 zu finden als mit 0,2, 2,0.

Oder:

%Vor%

dauert etwas länger (~ 50%) mit 0,1, 1,2 als mit 0,1, 0,1

Versuche, Cauchys Schranke für die anfängliche quadratische Approximation zu verwenden:

%Vor%

Leider beschleunigt dies die Konvergenz nicht wirklich.

    
Ecir Hana 25.08.2015, 10:03
quelle

1 Antwort

3

Da ich an dem Artikel gearbeitet und die Bilder geliefert habe, kann ich sagen, dass Sie diese guten Annäherungen wirklich nicht brauchen.

Der wichtigste erste Schritt besteht darin, das Polynom, wie im Artikel beschrieben, auf ein gradzahliges Maß zu reduzieren. Danach kann man nichts falsch machen, es sollte fast globale Konvergenz geben. Allerdings gilt das gleiche wie bei Newtons Methode: Wenn nach 10 Schritten kein merkliches Konvergenzzeichen auftritt, starten Sie mit einem anderen Anfangspunkt neu.

Es ist natürlich sinnvoll, einen äußeren Wurzelradius zu berechnen und den anfänglichen quadratischen Faktor zu wählen, um Wurzeln innerhalb dieses Radius zu haben.

Siehe die Javascript-Implementierung im Quelltext von Ссылка für eine "naive" oder "Vanille" aber scheinbar robuste Implementierung. Keine Reduktion auf Grad, keine Sorge für Koeffizienten / Wurzelgrößen, ...

Das Beispiel ist effizient ein ungeradzahliges Polynom innerhalb der Einheitsscheibe mit einer Wurzel -117.9917 bei virtueller Unendlichkeit. Für die Initialisierung in jedem Schritt sollte man den äußeren Wurzelradius berechnen, der R=119 in der Version "1 + max der Koeffizienten abs" (führender Koeffizient 1) ist. Dann initialisiere mit x^2-R^2 oder phi=2*pi*random(); und x^2+R^2*cos(phi)*x+R^2*sin(phi) oder etwas ähnliches.

    
LutzL 25.08.2015 11:08
quelle