| |
| Autor |
 Algorithmus, um Nullstellen von Polynomen zu berechnen |
|
thomasH
Neu 
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 
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
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. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
