JScience: Polynom in Normalform aus Nst???

[babuschka]

Hallo Leute,

häng schon seit einigen Tagen dran, aber komm einfach ned weiter. Ich hoffe es kann mir jemand helfen.

Problem:
Ich brauch die Ableitung eines Polynoms g. Zuerst muss ich mir aber das Polynom g erstellen. Was ich dazu habe, sind die Nst. des Polynoms g. Die Ableitung eines Polynoms ist ja mit JScience ganz einfach.....nur wie kann ich mittels JScience ein Polynom in Normalform aus den Nst erstellen???

Von (x-x0)*(x-x1)*....*(x-xn) ---- mittels JScience auf ---> a_n*x^n+....+a_1*x+a_0

Hier mein Code aber seh den Fehler ned....

[HIGHLIGHT="Java"]//cmplArr_Approx ist ein Complex-Array und enthält die Nst

Polynomial<Complex> g = null;
Polynomial<Complex> polynom_x = Polynomial.valueOf(Complex.ONE,cmpl_varX);
Polynomial<Complex> polynom_nan = Polynomial.valueOf(Complex.ZERO,cmpl_varX);

Polynomial<Complex> polynom_tmp = polynom_nan.plus(cmplArr_Approx[0]);
Polynomial<Complex> polynom_g = polynom_x.minus(polynom_tmp);

for (int i = 1; i < cmplArr_Approx.length; i++)
{
polynom_tmp = polynom_nan.plus(cmplArr_Approx);
polynom_tmp = polynom_x.minus(polynom_tmp);

polynom_g = polynom_g.times(polynom_tmp);
}[/HIGHLIGHT]


Als Beispiel:
1.Nst (2+0*i)
2.Nst (-2+0*i)

(x-(2+0*i))*(x-(-2+0*i)) -------> (1.0 + 0.0i)x² + (-4.0 + 0.0i)

Aber es kommt bei mir raus: (1.0 + 0.0i)x² + (2.0 + 0.0i)x + (-4.0 + 0.0i)

Sieht jemand nen Denk- oder Programmfehler??

 

[0x7F800000]

Naja, ausgerechnet hast du das schon richtig^^
Wahrscheinlich ist das einfach irgendein Tippfehler. Jag's doch durch den Debugger, oder gib an paar Stellen mit System.out.println() die Zwischenergebnisse aus.

 

[babuschka]

tippfehler hät ich gesehen, so oft wie ichs überprüft hab

daran hab ich schon gedacht @ Ausgaben mit System.out.println()
nur hab ichs zur besseren übersicht im post rausgelöscht.....

um an obiges bsp anzuknüpfen...hier ne ausgabe in der for schleife für die zeile: polynom_g.times(polynom_tmp)
--polynom_g ist [1.0 + 0.0i]x + [-2.0 + 0.0i]
--polynom_tmp ist [1.0 + 0.0i]x + [2.0 + 0.0i]

die beiden multipliziert er....aber bekomm ned den term (1.0 + 0.0i)x² + (-4.0 + 0.0i) (Ergebnis bei Maple)
sondern (1.0 + 0.0i)x² + (2.0 + 0.0i)x + (-4.0 + 0.0i)

hab ich evtl. bei komplexen zahlen irgendwas übersehen? gibts da noch ne besonderheit?

 

[0x7F800000]

omfg, ich verstehe überhaupt nicht was dieses ganze Herugewurschtel mit fünfzig Milliarden hilfsvariablen soll

Kannst du mir bitte sagen, was rauskommt, wenn du sowas eintippst? :

[HIGHLIGHT="Java"]Polynomial<Complex> g = Polynomial.valueOf(Complex.ONE,Term.ONE);
Polynomial<Complex> x = Polynomial.valueOf(Complex.ONE,cmpl_varX);

for (int i = 0; i < cmplArr_Approx.length; i++){
g=g.times(x.minus(cmplArr_Approx,Term.ONE));
}

System.out.println(g);[/HIGHLIGHT]

Ich hab momentan dieses Paket nicht, und will es auch nicht runterladen, deshalb kann ich nichts kompilieren => bei Bedarf Klammern & fehlende Buchstaben einfügen.
Was kommt da raus?

 

[babuschka]

omfg, ich verstehe überhaupt nicht was dieses ganze Herugewurschtel mit fünfzig Milliarden hilfsvariablen soll

Kannst du mir bitte sagen, was rauskommt, wenn du sowas eintippst? :

[HIGHLIGHT="Java"]Polynomial<Complex> g = Polynomial.valueOf(Complex.ONE,Term.ONE);
Polynomial<Complex> x = Polynomial.valueOf(Complex.ONE,cmpl_varX);

for (int i = 0; i < cmplArr_Approx.length; i++){
g=g.times(x.minus(cmplArr_Approx,Term.ONE));
}

System.out.println(g);[/HIGHLIGHT]

Ich hab momentan dieses Paket nicht, und will es auch nicht runterladen, deshalb kann ich nichts kompilieren => bei Bedarf Klammern & fehlende Buchstaben einfügen.
Was kommt da raus?

Hallo Andrey,

danke für den beitrag. Das Herugewurschtel (...meintest wohl herumgewurschtel...) dient zum Debuggen ^^
In deinem ersten Post meintest du, dass man Ausgaben machen soll....das hat ich ja auch und dazu die "vielen vielen" Hilfsvariablen....nur ich Post die ganzen System.out.println() ned mit, da so die Übersichtlichkeit ned wirklich gefördert wird...

Leider hilft mir dein Post ned weiter...du musst dir ja das Package ned installieren, aber sieh dir bitte die API an ...an einem Polynom-Objekt kann ich in der Methode minus kein Term-Objekt übergeben....

Durch einige Versuche hab ich herausgefunden, dass das Package bei der Multiplikation von Polynomen höheren Grades nicht wirklich die Rechenregeln befolgt => JScience kannste in den Müll werfen.....

Hab auch schon oft mit JEP gearbeitet, aber das langt mir ned aus.....würd die ganze Rechnerei jetzt gern auslagern...

Hab hier im Forum mal was von "R" gehört....kann mir dazu jemand mehr sagen? Welche Alternativen gibt es dazu?
Am schönsten wär was mit Maple

Grüße

 

[0x7F800000]

Oooh Mensch, deshalb hab ich ja gesagt "ein paar fehlende buchstaben ergänzen"...

[HIGHLIGHT="Java"]Polynomial<Complex> g = Polynomial.valueOf(Complex.ONE,Term.ONE);
Polynomial<Complex> x = Polynomial.valueOf(Complex.ONE,cmpl_varX);

for (int i = 0; i < cmplArr_Approx.length; i++){
g=g.times(x.minus(Polynomial.valueOf(cmplArr_Approx,Term.ONE)));
}

System.out.println(g);
[/HIGHLIGHT]
geht's so?

Ansonsten, wenn JScience wirklich "in den Müll" gehört, dann löst das bei mir so eine Art Schadensfreude aus weil ich vor kurzem angefangen habe, ein paket zu basteln, das in direkter Konkurrenz zu diesem JScience-Polynompaket steht.

Ob JScience wirklich "falsch rechnet" bezweifle ich eher: die JScience-Leute haben sich dabei doch definitiv irgendwas gedacht. Aber beim Blick auf die Dokumentation ist bei mir irgendwie der Eindruck entstanden, dass die selbst nicht genau wussten, was sie mit dem Paket eigentlich machen wollten.

<werbung>
Bei meiner Variante sind immerhin schon die ganzen nützlichen hilfsfunktiönchen zum zurückgeben von leittermen, leitkoeffizienten, tail's usw. implementiert, außerdem sind addition usw. doppelt und dreifach für alle arten von termen und einzelnen Koeffizienten überladen, aber das ist alles langweilig.

Interessanter: bei JScience haben sie Polynome oder Terme einfach "Comparable" gemacht. Das ist echt seltsam. Bei meiner Version gibt es nämlich drei oft verwendete eingebaute Monomordnungen, und ein paar Factory-methoden zum erstellen von weiteren Matrixordnungen und speziellen Eliminationsordnungen, die aus mehreren Unterring-Ordnungen zusammengesetzt werden können.

Ferner habe ich schon die ganzen methoden zum berechnen des größten gemeinsamen Teilers, für Polynomdivision / Divisionsalgorithmus, ich habe einige lahme funktionen zum Faktorisieren von Polynomen, und mein größter stolz: ich kann damit Gröbnerbasen ausrechnen.

Ein kleines beispiel gibt's als Vorgeschmack schonmal hier zu bewundern.
</werbung>
<antiwerbung>
Mein Projekt hat gegenüber JScience bisher aber einen wesentlichen Nachteil:
1) es deckt bisher wirklich nur Polynome / bisschen Lineare Algebra ab
2) es ist ein Prototyp. Ich werde weder den Quellcode noch ein .jar veröffentlichen, bis ich das vollständig neugeschrieben habe, das dauert noch mindestens ein Monat.
</antiwerbung>

Okay, wenn du willst, kannst du dich mit mir kurz freuen, aber dein Problem löst es wohl nicht wirklich^^

Also: probier's noch ein wenig mit JScience (so wie ich das jetzt korrigiert habe, zum Beispiel)
Wenn nix geht, schmeißt du es tatsächlich in den müll, und nimmst
JAS, welches diesem JScience-Paket wirklich 100 Lichtjahre voraus zu sein scheint (ich bin mir sicher, dass es auch mit komplexen zahlen sauber rechnen kann)

Aber bevor du alles das tust: sag mir bitte, wozu brauchst du das?

edit: achso, was R angeht: viele Leute mögen es, ich persönlich fand's dagegen in jeder Hinsicht gruselig, also zumindest nach Java schmeckt einem sowas gar nicht... Und imho ist das auch nicht so toll dazu geeignet, mit Polynomen rumzurechnen, das ist eher "numerisch" ausgerichtet.

 

[babuschka]

dann bin ich ja mal auf dein paket gespannt!

was ich vorhab: Weierstraß-Verfahren zur Berechnung aller Nullstellen (auch die komplexen) eines polynoms beliebiger ordnung.
http://de.wikipedia.org/wiki/Weierstraß-(Durand-Kerner)-Verfahren

as verfahren an sich is ja recht leicht zu verstehen....eher ein passendes paket in java zur bildung von g und dessen ableitung g' ist schwer zu finden

danke für den tipp mit JAS...werd ich mir mal genauer anschaun obs damit geht

 

[0x7F800000]

Ooochje... genau auf solche monsterstunts zielte meine Frage "wozu brauchst du das?" ab...

Das was du machen willst ist Numerik.
Dieses Paket das du anwenden wolltest, das was ich in meinem Paket implementiere, und das was JAS sehr effizient macht sind algebraische Manipulationen von Polynomen. Das ist nicht dazu da, um da irgendwelche schlecht gerundete Ziffern einzusetzen, diese ganze Polynom-Rechnerei arbeitet 100% exakt ohne Rundungsfehler, dafür aber mit einem (für numerische Anwendungen) ziemlich hohen Overhead, was aber auch egal ist, da diese Pakete einfach für was anderes gedacht sind, etwa Polynomielle Gleichungssysteme exakt Umformen.

Für das was du willst braucht man das alles doch gar nicht.
Dieses variablenbehaftete ausrechnen von irgendwelchen polynomen, und dann Ableiten und Teufel weiß was noch... Nee. Das ist alles extremst lahm. Außerdem hast du den Wikipedia Artikel nicht so genau gelesen. Wenn da

g'

steht, heißt es doch noch lange nicht, dass du da irgendwelche Polynome ableiten musst??? Da steht nur was es ist. Und wie man es schnell berechnet steht da auch, das ist dieses kleine Produkt, da braucht man definitiv keine Symbolische rumrechnerei und solchen Krempel.

Hier, hb da eben schnell was hingehackt:
[HIGHLIGHT="Java"]
package fastnumerics;

import java.util.Arrays;

public class WeierstrassIteration {
//bisschen was zum rechnen mit komplexen zahlen
private static class Complex{
private double im,re;
public Complex(double r, double i) { re=r; im=i; }
public Complex(double r) { this(r,0); }
public Complex() { this(0,0); }
public Complex add(Complex other){
return new Complex(this.re+other.re,this.im+other.im);
}
public Complex subtract(Complex other){
return new Complex(this.re-other.re,this.im-other.im);
}
public Complex multiply(Complex other){
return new Complex(this.re*other.re-this.im*other.im,this.re*other.im+this.im*other.re);
}
public double squareAbs(){
return re*re+im*im;
}
public double abs(){
return Math.sqrt(squareAbs());
}
public Complex getInverse(){
double squareAbsInv=1/squareAbs();
return new Complex(re*squareAbsInv,-im*squareAbsInv);
}
public Complex getNegative(){
return new Complex(-re,-im);
}
public Complex divide(Complex other){
return this.multiply(other.getInverse());
}
public static Complex random(){
return new Complex(Math.random(),Math.random());
}
@Override
public String toString(){ return re+"+"+im+"i"; }
}

//hornerschema zum auswerten von polynomen
private static Complex hornerScheme(Complex[] polyCoeffs, Complex x){
Complex result=polyCoeffs[polyCoeffs.length-1];
for(int i=polyCoeffs.length-2;i>=0;i--)
result=result.multiply(x).add(polyCoeffs);
return result;
}

//dieses komische g'(z[k]) im nenner aus der wikipedia
private static Complex g(Complex[] approx, int k){
Complex result=new Complex(1);
for(int i=0; i<k; i++) result=result.multiply(approx[k].subtract(approx));
for(int i=k+1; i<approx.length; i++) result=result.multiply(approx[k].subtract(approx));
return result;
}

//die eigentliche iteration
private static Complex[] weierstrassIteration(Complex[] polyCoeffs, int iters){
//approx sind die approximationen der nullstellen
Complex[] approx=new Complex[polyCoeffs.length-1];
//erstmal alles zufällig
for(int i=0; i<approx.length; i++) approx=Complex.random();

//iteration
Complex[] correcture=new Complex[approx.length];
for(int i=0; i<iters; i++){
//korrekturterme ausrechnen
for(int k=0; k<correcture.length; k++){
correcture[k]=hornerScheme(polyCoeffs,approx[k]).divide(g(approx,k));
}
//auf die approximation die korrekturterme draufaddieren (bzw subtrahieren)
for(int k=0; k<correcture.length; k++){
approx[k]=approx[k].subtract(correcture[k]);
}
}

//fertig...
return approx;
}

//TEST
public static void main(String..._){
// (23+i)+(-10+i)x+x^2 = (3+i-x)(7-2i-x)
Complex[] polyCoeffs={new Complex(23,1),new Complex(-10,1),new Complex(1)};
Complex[] variety=weierstrassIteration(polyCoeffs,15); //nullstellen (approximiert)
System.out.println("polynom koeffizienten: "+Arrays.toString(polyCoeffs));
System.out.println("nullstellen approximiert: "+Arrays.toString(variety));

System.out.println();
for(Complex x:variety){
System.out.println("polynom ausgewertet in "+x+":\t"+hornerScheme(polyCoeffs,x));
}
}
}
[/HIGHLIGHT]
Da das Forum grad nicht voll funktionstüchtig ist, musst du erst auf "zitieren" drücken, und von da den code rauskopieren, sonst kriegst du da zeilennumerrierungen mitkopiert oder sowas. Lass es mal laufen, das ding ist an einem Stück kompilierbar und sofort ausführbar, und braucht auch keinerlei externe jars oder sowas. Wozu schwer wenn's auch einfach geht?

 

[babuschka]

vielen dank für die hilfe andrey!
respekt@hingehackt

hab wohl den wald vor lauter bäumen nicht mehr gesehen...
schande über mich, dass ich die produktsumme zur berechnung von g' übersehen habe....
die fertige lib von jscience hat mich vielleicht auch dazu verführt und dachte es wär der schnellste weg ans ziel zu kommen, da ja schon sooo viel vorimplementiert ist ^^

was besseres bzgl. der laufzeit als das horner-schema zur berechnung gibt es ja ned...das ist wirklich optimal.

habs nun getestet und findet sehr oft alle nstl.....gibt ein paar ausnahmefälle....beispiel:

p(x) = (1+1i)*x^2 + (0+2i)*x  +  (2-1i)

selbst bei 30.000 iterationen findet er nur eine nstl....liegt wohl daran, dass es ein iteratives verfahren ist...
es werden anscheinend noch mehr iterationen benötigt....aber konvergieren muss es ja irgendwann mal ^^

 

[0x7F800000]

>> "konvergieren muss es ja irgendwann mal"
Nnaja... weiß der Teufel... Ich hab's jetzt nur abgetippt, nicht nachgerechnet und bewiesen dass es wirklich was sinnvolles liefert. Ich hab's an deinem beispiel jetzt ein paar mal ausprobiert, es sieht eher so aus, als ob es divergieren würde
Da kommen auch nach ein paar schritten NaN, NaN NaN überall raus, bei bestimmten Startwerten zumindest.
Ich weiß nicht voran das liegt. Vielleicht hab ich was überlesen, vielleicht habe ich da irgendwo einen Tippfehler. Ich werd's mir bei der nächsten Gelegenheit etwas genauer anschauen, aber leider geht in den nächsten paar tagen nichts.