Ein wurzelfindender Algorithmus ist eine numerische Methode oder Algorithmus, für einen Wert x solch dass f (x) = 0, für eine gegebene Funktion f zu finden. Solch ein x wird eine Wurzel der Funktion f genannt.

Dieser Artikel ist mit Entdeckung des Skalars, der echten oder komplizierten Wurzeln, näher gekommen als schwimmen lassend Punkt-Zahlen beschäftigt. Entdeckung von Wurzeln der ganzen Zahl oder genauen algebraischen Wurzeln ist getrennte Probleme, deren Algorithmen wenig genau wie diejenigen haben, die hier besprochen sind. (Sieh: Gleichung von Diophantine bezüglich Wurzeln der ganzen Zahl)

Die Entdeckung einer Wurzel von f (x) − g (x) = 0 ist dasselbe als das Lösen der Gleichung f (x) = g (x). Hier wird x das unbekannte in der Gleichung genannt. Umgekehrt kann jede Gleichung die kanonische Form f (x) = 0 annehmen, so ist das Gleichungslösen dasselbe Ding wie rechnend (oder findend) eine Wurzel einer Funktion.

Numerische wurzelfindende Methoden verwenden Wiederholung, eine Folge von Zahlen erzeugend, die hoffentlich zu einer Grenze zusammenlaufen (der so genannte "feste Punkt"), der eine Wurzel ist. Die ersten Werte dieser Reihe sind anfängliche Annahmen. Die Methode schätzt nachfolgende Werte, die auf den alten und der Funktion f gestützt sind.

Das Verhalten von wurzelfindenden Algorithmen wird in der numerischen Analyse studiert. Algorithmen leisten am besten, wenn sie bekannte Eigenschaften der gegebenen Funktion ausnutzen. So kann ein Algorithmus, um isolierte echte Wurzeln eines Polynoms des niedrigen Grads in einer Variable zu finden, wenig Ähnlichkeit mit einem Algorithmus für komplizierte Wurzeln einer Funktion "des schwarzen Kastens" haben, die, wie man sogar bekannt, differentiable nicht ist. Fragen schließen Fähigkeit ein, nahe Wurzeln, Robustheit im Erzielen zuverlässiger Antworten trotz unvermeidlicher numerischer Fehler und Rate der Konvergenz zu trennen.

Spezifische Algorithmen

Bisektionsverfahren

Der einfachste wurzelfindende Algorithmus ist das Bisektionsverfahren. Es arbeitet, wenn f eine dauernde Funktion ist und es vorherige Kenntnisse von zwei anfänglichen Annahmen, a und b, solch verlangt, dass f (a) und f (b) entgegengesetzte Zeichen haben. Obwohl es zuverlässig ist, läuft es langsam zusammen, ein Bit der Genauigkeit mit jeder Wiederholung gewinnend.

Die Methode des Newtons (und ähnliche Ableitungsbasierte Methoden)

Die Methode von Newton nimmt die Funktion f an, eine dauernde Ableitung zu haben. Die Methode von Newton, kann wenn angefangen, zu weit weg von einer Wurzel nicht zusammenlaufen. Jedoch, wenn es wirklich zusammenläuft, ist es schneller als das Bisektionsverfahren, und ist gewöhnlich quadratisch. Die Methode von Newton ist auch wichtig, weil sie sogleich zu hoch-dimensionalen Problemen verallgemeinert. Einem Newton ähnliche Methoden mit der höheren Ordnung der Konvergenz sind die Methoden des Wohnungsinhabers. Der erste nach der Methode von Newton ist die Methode von Halley mit der Kubikordnung der Konvergenz.

Sekantenverfahren

Die Ableitung in der Methode von Newton mit einem begrenzten Unterschied ersetzend, bekommen wir das Sekantenverfahren. Diese Methode verlangt die Berechnung (noch die Existenz) einer Ableitung nicht, aber der Preis ist langsamere Konvergenz (die Ordnung ist etwa 1.6). Eine Generalisation des Sekantenverfahrens in höheren Dimensionen ist die Methode von Broyden.

Falsche Position (Regula Falsi)

Die falsche Positionsmethode, auch genannt den regula falsi Methode, ist dem Sekantenverfahren ähnlich. Jedoch, anstatt die letzten zwei Punkte zu behalten, überzeugt es sich, um einen Punkt auf beiden Seiten der Wurzel zu behalten. Die falsche Positionsmethode ist schneller als das Bisektionsverfahren und robuster als das Sekantenverfahren, aber verlangt, dass die zwei Startpunkte die Wurzel einklammern. Die Methode von Ridders ist eine Variante auf der Methode der falschen Position, die auch die Funktion am Mittelpunkt des Zwischenraums bewertet, schnellere Konvergenz mit der ähnlichen Robustheit gebend.

Interpolation

Das Sekantenverfahren entsteht auch, wenn man der unbekannten Funktion f durch die geradlinige Interpolation näher kommt. Wenn quadratische Interpolation statt dessen verwendet wird, kommt man in die Methode von Muller an. Es läuft schneller zusammen als das Sekantenverfahren. Eine besondere Eigenschaft dieser Methode ist, dass das Wiederholen x kompliziert werden kann.

Umgekehrte Interpolation

Das kann durch das Interpolieren des Gegenteils von f vermieden werden, auf die umgekehrte quadratische Interpolationsmethode hinauslaufend. Wieder ist Konvergenz asymptotisch schneller als das Sekantenverfahren, aber umgekehrte quadratische Interpolation benimmt sich häufig schlecht, wenn das Wiederholen der Wurzel nicht nah ist.

Kombinationen von Methoden

Die Methode von Brent

Die Methode von Brent ist eine Kombination des Bisektionsverfahrens, des Sekantenverfahrens und der umgekehrten quadratischen Interpolation. Bei jeder Wiederholung entscheidet die Methode von Brent, welche Methode aus diesen drei wahrscheinlich Bestes tun wird, und durch das Tun eines Schritts gemäß dieser Methode weitergeht. Das gibt eine robuste und schnelle Methode, die deshalb beträchtliche Beliebtheit genießt.

Die Entdeckung von Wurzeln von Polynomen

Viel Aufmerksamkeit ist auf den speziellen Fall gelenkt worden, dass die Funktion f ein Polynom ist; dort bestehen Sie wurzelfindende Algorithmen, die die polynomische Natur von f ausnutzen. Für ein univariate Polynom des Grads weniger als fünf, dort werden Form-Lösungen wie die quadratische Formel geschlossen, die alle Wurzeln erzeugen. Jedoch sollte sogar dieser Grad zwei Lösung mit der Sorge verwendet werden, um numerische Stabilität zu sichern. Noch mehr Sorge muss mit dem Grad drei und Grad vier Lösungen wegen ihrer Kompliziertheit genommen werden. Polynome des höheren Grads haben keine solche allgemeine Lösung, gemäß dem Lehrsatz von Abel-Ruffini (1824, 1799).

Die Methode von Birge-Vieta verbindet die Methode von Horner der polynomischen Einschätzung mit dem Newton-Raphson, um eine rechenbetonte Beschleunigung zur Verfügung zu stellen.

Für echte Wurzeln stellen der Lehrsatz von Sturm und die Regierung von Descartes von Zeichen Handbüchern zum Auffinden und Trennen von Wurzeln zur Verfügung. Das plus die mit der Methode von Newton verbundene Zwischenraum-Arithmetik gibt robuste und schnelle Algorithmen nach.

Der Algorithmus, für die Wurzeln, mit der Regierung von Descartes von Zeichen und dem Lehrsatz von Vincent zu isolieren, war den Algorithmus von modifiziertem Uspensky von seinen Erfindern Collins und Akritas ursprünglich genannt worden. Nach dem Durchgehen von Namen wie "Methode von Collins-Akritas" und "die Methode von Descartes" (zu verwirrend, wenn den Artikel von Fourier denkt) war es schließlich François Boulier der Lille Universität, die ihm den Namen Methode von Vincent-Collins-Akritas (VCA), p gegeben hat. 24 gestützt auf der Tatsache, dass "die Methode von Uspensky" nicht besteht und tut keiner "die Methode von Descartes". Dieser Algorithmus ist von Rouillier und Zimmerman verbessert worden, und die resultierende Durchführung, ist zum Datum, dem schnellsten Bisektionsverfahren. Es hat dieselbe Grenzfall-Kompliziertheit wie Algorithmus von Sturm, aber ist fast immer viel schneller. Es ist der Verzug-Algorithmus der Ahorn-Wurzelentdeckungsfunktion fsolve. Eine andere auf dem Lehrsatz von Vincent gestützte Methode ist die Methode von Vincent-Akritas-Strzeboński (VAS); es ist gezeigt worden, dass der VAS (fortlaufende Bruchteile) Methode schneller ist als die schnellste Durchführung des VCA (Halbierung) Methode, eine Tatsache, die anderswohin unabhängig bestätigt wurde; genauer für die Polynome von Mignotte des hohen Grads ist VAS ungefähr 50,000mal schneller als die schnellste Durchführung von VCA. VAS ist der Verzug-Algorithmus für die Wurzelisolierung in Mathematica, Weisem, SymPy, Xcas. Sieh den Lehrsatz von Budan für eine Beschreibung des historischen Hintergrunds dieser Methoden. Weil ein Vergleich zwischen der Methode und VAS von Sturm die Funktionen realroot (poly) und Zeit (realroot (poly)) Xcas verwendet. Standardmäßig, um die echten Wurzeln von poly zu isolieren, verwendet realroot die VAS Methode; um die Methode von Sturm zu verwenden, schreiben realroot (sturm, poly). Siehe auch die Außenverbindungen für einen Zeigestock zu einer iPhone/iPod/iPad Anwendung, die dasselbe macht.

Eine Möglichkeit ist, die dazugehörige Matrix des Polynoms zu bilden. Da die eigenvalues dieser Matrix mit den Wurzeln des Polynoms zusammenfallen, kann man jeden eigenvalue Algorithmus verwenden, um die Wurzeln des Polynoms zu finden. Zum Beispiel erweist sich die Methode des klassischen Bernoullis, die Wurzel größer im Modul zu finden, wenn es besteht, die auf die dazugehörige Matrix angewandte Macht-Methode zu sein. Die umgekehrte Macht-Methode, die eine kleinste Wurzel zuerst findet, ist, was die Methode von Jenkins-Traub steuert und ihr seine numerische Stabilität und schnelle Konvergenz sogar in Gegenwart von vielfachen oder gruppierten Wurzeln gibt.

Die Methode von Laguerre, sowie die Methode von Halley, verwendet die zweiten Ordnungsableitungen und den Komplex arithmetics einschließlich der komplizierten Quadratwurzel, um Kubikkonvergenz für einfache Wurzeln auszustellen, die quadratische durch die Methode von Newton gezeigte Konvergenz beherrschend.

Die Methode von Bairstow verwendet die Methode von Newton, quadratische Faktoren eines Polynoms mit echten Koeffizienten zu finden. Es kann sowohl echte als auch komplizierte Wurzeln eines echten Polynoms mit nur die echte Arithmetik bestimmen.

Der einfache Durand-Kerner und die ein bisschen mehr komplizierte Methode von Aberth finden gleichzeitig alle Wurzeln mit nur die einfache Arithmetik der komplexen Zahl.

Die zerreißende Kreismethode ist nützlich, für die Wurzeln von Polynomen des hohen Grads zur willkürlichen Präzision zu finden; es hat fast optimale Kompliziertheit in dieser Einstellung. Eine andere Methode mit diesem Stil ist die Dandelin-Gräffe Methode (wirklich wegen Lobachevsky) der Faktoren das Polynom.

Das Polynom von Wilkinson illustriert, dass hohe Präzision notwendig sein kann, wenn sie die Wurzeln eines Polynoms gegeben seine Koeffizienten schätzt: Das Problem, die Wurzeln von den Koeffizienten zu finden, wird im Allgemeinen schlecht-bedingt.

Die Entdeckung vielfacher Wurzeln von Polynomen

Wenn p (x) ein Polynom mit einer vielfachen Wurzel an r ist, dann kann die Entdeckung des Werts von r (ineffizient oder unmöglich) für viele der wurzelfindenden Standardalgorithmen schwierig sein. Glücklich gibt es eine Technik besonders für diesen Fall, vorausgesetzt, dass p ausführlich als ein Polynom in einer Variable mit genauen Koeffizienten gegeben wird.

Algorithmus

1. Erstens müssen wir bestimmen, ob p (x) eine vielfache Wurzel hat. Wenn p (x) eine vielfache Wurzel an r hat, dann wird seine Ableitung p  (x) auch eine Wurzel an r haben (ein weniger, als p (x) dort hat). So berechnen wir den größten allgemeinen Teiler der Polynome p (x) und p  (x); passen Sie den Hauptkoeffizienten an, um ein es g (x) zu sein und ihn zu nennen. (Sieh den Lehrsatz von Sturm.), Wenn g (x) = 1, dann hat p (x) keine vielfachen Wurzeln und wir jene anderen wurzelfindenden Algorithmen sicher verwenden können, die am besten arbeiten, wenn es keine vielfachen Wurzeln gibt, und dann abgeht.
2. Nehmen Sie jetzt an, dass es eine vielfache Wurzel gibt. Bemerken Sie, dass g (x) eine Wurzel derselben Vielfältigkeit an r haben wird, den p  (x) hat und der Grad des Polynoms g (x) allgemein viel weniger sein wird als dieser von p (x). Nennen Sie rekursiv diese Routine, d. h. gehen Sie zurück, um #1 oben, mit g (x) im Platz von p (x) zu gehen. Nehmen Sie jetzt an, dass wir die Wurzeln von g (x) gefunden haben, d. h. wir factored er haben.
3. Seitdem r gefunden worden ist, können wir Faktor (xr) aus p (x) wiederholt, bis wir alle Wurzeln an r entfernt haben. Wiederholen Sie das für irgendwelche anderen vielfachen Wurzeln, bis es keine vielfache Wurzeln mehr gibt. Dann kann der Quotient, d. h. der restliche Teil von p (x), factored auf die übliche Weise mit einem der anderen wurzelfindenden Algorithmen sein. Ausgang.

Beispiel

Nehmen Sie p (x) = x+x5x+3 an

ist die Funktion, deren Wurzeln wir finden wollen.

Wir berechnen p  (x) = 3x+2x5.

Teilen Sie jetzt p  (x) in p (x), um p (x) = p  (x) zu bekommen · ((1/3) x + (1/9)) + ((32/9) x + (32/9)).

Teilen Sie den Rest durch 32/9, um x1 zu bekommen, der monic ist.

Teilen Sie x1 in p  (x), um p  (x) = (x1) zu bekommen · (3x+5) +0.

Da der Rest Null, g (x) = x1 ist. So ist die vielfache Wurzel von p (x) r = 1.

Sich p (x) durch (x1) teilend, bekommen wir p (x) = (x+3) (x1), so ist die andere Wurzel 3, eine einzelne Wurzel.

Direkter Algorithmus für die vielfache Wurzelbeseitigung

Es gibt eine direkte Methode, vielfach (oder wiederholt) Wurzeln von Polynomen mit genauen Koeffizienten (ganze Zahlen, rationale Zahlen, ganze Zahlen von Gaussian oder vernünftige komplexe Zahlen) zu beseitigen.

Nehmen Sie an einer Wurzel des Polynoms P, mit der Vielfältigkeit m> 1 zu sein.

Dann ein Wille, eine Wurzel der formellen Ableitung P', mit der Vielfältigkeit m−1. sein

Jedoch, P 'kann zusätzliche Wurzeln haben, die nicht Wurzeln von P sind.

Zum Beispiel, wenn P (x) = (x−1) (x−3), dann P' (x) =6 (x−1) (x−2) (x−3). So 2 ist eine Wurzel von P', aber nicht P.

Definieren Sie G, um der größte allgemeine Teiler von P und P zu sein, '. (Sagen Sie G (x) = (x−1) (x−3)).

Schließlich teilt G P genau, so bilden Sie den Quotienten Q =P/G. (Sagen Sie Q (x) = (x−1) (x−3)). Die Wurzeln von Q sind die Wurzeln von P, mit vielfachen Wurzeln reduziert unten auf einzelne Wurzeln.

Da P ein Polynom mit genauen Koeffizienten dann ist, wenn der Algorithmus mit der genauen Arithmetik durchgeführt wird, wird Q auch ein Polynom mit genauen Koeffizienten sein.

Offensichtlich Grad (Q)

• Der n-te Wurzelalgorithmus
• Vielfältigkeit (Mathematik)
• Größter allgemeiner Teiler
• Polynom
• Die Methode von Graeffe
• Kryptografisch sicherer Pseudozufallszahlengenerator — eine Klasse von Funktionen hat spezifisch vorgehabt, durch wurzelfindende Algorithmen unlösbar zu sein.
• Systeme von polynomischen Gleichungen — wurzelfindende Algorithmen im multivariate Fall
• MPSolve
• GNU wissenschaftliche Bibliothek

Links

• Wurzelfindende Algorithmen javanischer Code Durch Behzad Torkian
• Zeichentrickfilme für die feste Punkt-Wiederholung
• GAMS: Wurzeln von Polynomen mit echten Koeffizienten
• Gratis online lässt Polynom Finder sowohl für echte als auch für komplizierte Koeffizienten einwurzeln
• Kehagias, Spyros: RealRoots, freier App für das iPhone, den iPod touch und das iPad, um die Methode und VAS von Sturm http://itunes.apple.com/gr/app/realroots/id483609988?mt=8 zu vergleichen