Matroids Matheplanet Forum Index
Moderiert von Curufin epsilonkugel
Analysis » Funktionen » Algorithmus, um Nullstellen von Polynomen zu berechnen
Autor
Kein bestimmter Bereich Algorithmus, um Nullstellen von Polynomen zu berechnen
thomasH
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 03.07.2022
Mitteilungen: 2
  Themenstart: 2022-07-03

Hallo, ich schreibe gerade einen neuen Algorithmus um die Nullstellen Von Polynomen beliebigen Grades zu berechnen. Der Algorithmus basiert auf dem Newtonverfahren. Mittels der Formel x=x-f(x)/f'(x) nähert sich das Newtonverfahren schrittweise einer Nullstelle. Das Problem bei dem Verfahren ist, dass es scheitert, wenn f'(x) null ist, da man nicht durch null teilen kann. Meine Idee zur Verbesserung des Verfahrens ist simpel: Man teilt die Funktion in Intervalle auf, in denen f'(x) != null ist, führt das Verfahren separat für jedes Intervall aus und fügt die Ergebnisse zusammen. Man braucht um die Nullstellen zu berechnen also zuerst die Nullstellen der Ableitung, weshalb zuerst die Nullstellen aller Ableitungen in aufsteigender Reihenfolge berechnet werden. In jedem Intervall gibt es maximal 1 Nullstelle, da das Vorzeichen der Ableitung konstant ist. Wenn die Funktion innerhalb eines Intervalls die X-Achse kreuzt, kann es keine zweite Nullstelle geben, da das Vorzeichen der Ableitung sich dafür umdrehen müsste. Ich glaube man kann sogar sagen, dass wenn das Vorzeichen von f(linke Seite des Intervalls) und f(rechte Seite des Intervalls) unterschiedlich ist, dass es genau 1 Nullstelle gibt, wenn das Vorzeichen gleich ist gibt es keine Nullstelle. Mich würde Eure Meinung zum Algorithmus interessieren. Ich bin kein Mathematiker und habe keine Ahnung, ob meine Argumentation mathematisch schlüssig ist. Am interessantesten wäre für mich, ob der Algorithmus alle Nullstellen findet oder nur eine wenige. Hier ist etwas Beispielcode: \sourceon typescript export function superacid(polynom:Decimal[],accuracy:Decimal=new Decimal(0.01), newtonIterations:number=32):Decimal[] { /* Simplify polynomial by dividing through the first coefficient. Smaller coefficients mean less chance of overflowing. */ polynom=simplyfyPolynom(polynom); var degree = polynom.length-1; if (degree<=0) return null; var polynoms=calculateDerivates(polynom); //calculate all derivatives /* Add polynomial to the list of polynomials, whose roots need to be calculated */ polynoms.unshift(polynom); var c= degree; var firstDegreeDerivation=polynoms[polynoms.length-2]; var derivateZeros:Decimal[]=[firstDegreeDerivation[1].neg().div(firstDegreeDerivation[0])]; var roots = derivateZeros; /* Calculate roots of polynomial and all its derivates, starting with lowest degree. Roots are needed for calculating the roots of the polynom with the next degree. */ while (--c) { var fx= polynoms[c-1]; var fxx= polynoms[c]; roots=[]; /* Intervals are located from -infinity to the first stationary point, in between neigbouring stationary points, and from the last stationary point to +infinity. Because of that, the zeros of the derivate are needed, calculated in the last loop iteration. In each interval there is at most one zero, because the sign of the derivative is constant. */ var intervals= getIntervalsInPolynom(...derivateZeros); for( var interval of intervals) { //Do Newton iterations seperately for each interval var root=newtonIterate(fx,fxx,interval.left,interval.right,interval.start,newtonIterations,accuracy); if (root==null) continue; //skip next interval, because root will be the same as in the current interval if (interval.right.minus(root).abs().lessThan(accuracy)) intervals.next(); roots.push(root); //Add root to the list of found roots } derivateZeros=roots; //Roots are needed for calculating the next intervals } return roots; // return found roots } \sourceoff Den kompletten Source (MIT Open Source Lizenz) inkl. einer GUI zum Testen findet Ihr hier: https://github.com/P3N9U1N/superacid Viele Grüße, Thomas


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2262
Wohnort: Thüringen
  Beitrag No.1, eingetragen 2022-07-03

Hallo, willkommen auf dem MP ! Beim lesen fiel mir ein, ein Polynom n.ten Grades hat ja n Nullstellen. Dabei wird auch der komplexe Zahlenbereich einbezogen. Arbeitet für z. Bsp. 0=x^4+81 Dein Programm korrekt ? LG


   Profil
thomasH
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 03.07.2022
Mitteilungen: 2
  Beitrag No.2, vom Themenstarter, eingetragen 2022-07-04

Hallo pzktupel, \quoteon(2022-07-03 17:16 - pzktupel in Beitrag No. 1) Hallo, willkommen auf dem MP ! Beim lesen fiel mir ein, ein Polynom n.ten Grades hat ja n Nullstellen. Dabei wird auch der komplexe Zahlenbereich einbezogen. Arbeitet für z. Bsp. 0=x^4+81 Dein Programm korrekt ? LG \quoteoff Das Programm findet nur Näherungslösungen für reelle Zahlen. 0=x^4-81 würde gehen. Die GUI ist unter folgendem Link zu finden: https://p3n9u1n.github.io/superacid/gui/index.html Viele Grüße, Thomas


   Profil
thomasH hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]