Nullstellenberechnung von Ganzrationalen Funktionen
-
lass dein programm eine nullstelle raten
-
volkard schrieb:
Dann würfelt man halt nen neuen Startwert und macht weiter. Fast alle Startwerte sind lieb.
Per Zufallsgenerator?
Damit man alle Nullstellen erwischt, sollte man gleich komplexe Zahlen nehmen. Newton bleibt im Komplexen immernoch lieb. Sonst isses immer so unpraktisch, raten zu müssen, ob man alle reellen erwischt hat.
Nur von komplexen Zahlen hab ich überhaupt keinen Plan... Die bleiben lieber draußen.
Newton für Rechner ist anders als Newton im Mathebuch. Die beschreiben da wohl, was gegeben sein mus, damit Newton schnurstracks ankommt. Das tut aber nicht not. Wrnn er mal abhaut, was soll schon passieren? Er rennt mit nem ganz unglücklichen Schritt mal ganz dich an ein lokales Minimum und haut dann ab. Weit weg. Und dann (weil weit weit weg bei polynomen immer krasses gefälle in richtung Ursprung heißt) kommt er in schnellen Schritten wieder angerast.
...dann rennt er wieder auf den Extrempunkt zu, was erneut eine Division durch eine sehr kleine Zahl bedeutet und das ganze Spiel beginnt von vorne -> Endlosschleife...
-
Steven schrieb:
volkard schrieb:
Dann würfelt man halt nen neuen Startwert und macht weiter. Fast alle Startwerte sind lieb.
Per Zufallsgenerator?
jo.
Damit man alle Nullstellen erwischt, sollte man gleich komplexe Zahlen nehmen. Newton bleibt im Komplexen immernoch lieb. Sonst isses immer so unpraktisch, raten zu müssen, ob man alle reellen erwischt hat.
Nur von komplexen Zahlen hab ich überhaupt keinen Plan... Die bleiben lieber draußen.
das macht doch nix. musst nur wissen, daß es komplexe zahlen gibt, daß die auch +, -, * und / kennen, daß newton, polynomdivision und hornerschema im komplexen genau gleich funktionieren und daß ein polynom vom grad n genau n nullstellen hat, wenn man komplex rechnet.
nimm also einfach dein programm und ersetze double durch complex<double> und du findest alle nullstellen. und dann kannste ja, um den user nicht mit komplexem zu verwirren einfach nur die reellen nullstellen anzeigen. also alle komplexen nullstellen (bestehend aus struct complex{double reellerteil;double imaginärerteil;}), wo der imaginäre teiöl gleich 0 ist.Newton für Rechner ist anders als Newton im Mathebuch. Die beschreiben da wohl, was gegeben sein mus, damit Newton schnurstracks ankommt. Das tut aber nicht not. Wrnn er mal abhaut, was soll schon passieren? Er rennt mit nem ganz unglücklichen Schritt mal ganz dich an ein lokales Minimum und haut dann ab. Weit weg. Und dann (weil weit weit weg bei polynomen immer krasses gefälle in richtung Ursprung heißt) kommt er in schnellen Schritten wieder angerast.
...dann rennt er wieder auf den Extrempunkt zu, was erneut eine Division durch eine sehr kleine Zahl bedeutet und das ganze Spiel beginnt von vorne -> Endlosschleife...
stimmt ja gar nicht. teste es doch einfach. das prog zu schreiben ist nicht so arg schwer, wirste schon schaffen. und ich sage dir, daß es klappt, denn ich hatte jahrelang so nen polynomlöser im einsatz (damals auf nem sharp pc-1403 in basic). die kombination von newton, hornerschema (einmal zum berechnen der funktionswerte/ableitungswerte und später zur polynomdivision), komplexen zahlen und zufälligen startwerten (aber klein, sagen wie mal zwischen -10 und 10) klappt einfach und ist schnell und ist einfach.
der löser in basic hatte nichmal die möglichkeit, divisionen durch 0 und NAN gescheit abzufangen!!! dennoch war das prog gut, denn die fehler passieren so selten, daß es einfach irrelevant ist.
warum glaubt mir eigentlich keiner was? denkt ihr, ich benutze hier nen würfel, um schlau klingende sätze für meine postings zu basteln?zum tapsen auf extrempunkte:
er rennt in ne richtung, wo er annimmt, daß 0/0 wäre. um genau zu sein, legt newton einfach am messpunkt x/f(x) ne tangente an und guckt, wo die die x-achse schneidet. weit weg ist die tangente immer recht steil und schneidet die x-achse an nem punkt, der näher anb 0 ist als der messpunkt.
ganz dich bei nem lokalen extremum ist sie aber recht flach. deswegen schneidet die tangente erst recht weit weg wieder die x-achse.
beim heranrennen kann folgendes passieren:a) alles geht glatt
b) in richtung 0/0 ist auf dem weg datzischen in lokales ectremum und newton tappt ganz dicht daneben. dann haut er mal ab und...
b1) zwar in die richtung, aus der er kam. er kommt wieder, aber diesmal, da er ja recht große schritte macht, tappt er nicht mehr dicht ans extremum und er rennt weiter richtung 0/0
b2) zwar in die richtung, wo er eh hinwollte. dann ist er evtl über die nullstelle hinaus? macht nix, von der anderen seite findet er die auch.c) er ging gerade so schön bergab, und auf einmal geht er bergauf (kann nur kommen, wenn extremum übertappt wurde). macht nix, er dreht um und probiert es von neuem. dabei kann er ruhig auch 10mal die richtung wechseln. irgendwann trifft er das extremum auch mal dicht genug, um weit genug zu springen, daß er dicht genug an ne echte nullstelle kommt.
die endlosschleife passiert nur, wenn gar keine nullstellle da ist!
also bei y=x^2+1 tanzt newton im rellen endlos umher.
und bei nem schlechten startwert (nem reellen startwert) im komplexen auch.
aber ich habe noch keinen startwert gewürfelt, wo er im komplexen endlos tanzen würde. und selbst wenn man die würfeln könnte, dann brich einfach die schleife nach 1000 schritten ab und fang neu an. (1000 schritte ist sauviel).
-
volkard schrieb:
die endlosschleife passiert nur, wenn gar keine nullstellle da ist!
also bei y=x^2+1 tanzt newton im rellen endlos umher.
und bei nem schlechten startwert (nem reellen startwert) im komplexen auch.
aber ich habe noch keinen startwert gewürfelt, wo er im komplexen endlos tanzen würde. und selbst wenn man die würfeln könnte, dann brich einfach die schleife nach 1000 schritten ab und fang neu an. (1000 schritte ist sauviel).Das heißt, wenn ich komplexe Zahlen während der Berechnung verwende und einen Startwert wie z.B. 1+i nehme, gibt es keine Probleme?
-
Steven schrieb:
Das heißt, wenn ich komplexe Zahlen während der Berechnung verwende und einen Startwert wie z.B. 1+i nehme, gibt es keine Probleme?
fast. aber 1+i ist zu glatt. bei ganzzahligen kleinen koeffizienten des polynoms ist es zu leicht, sowas zu treffen. gerade in schule oder studium wird gerne in den aufgaben versucht, sowas wie i+1 als lösung zu konstruieren.
nimm besser 1.01+0.99*i. oder geh auch nommer sicher und nimm rand()/double(RANDMAX)+rand()/double(RANDMAX)*i
-
Ein Problem noch: Wie erkenne ich zuverlässig, ob ich jetzt eine Lösung ohne Imaginäranteil habe? Da das Newtonverfahren ja nur eine Näherung liefert, weiß ich ja nicht, was ich z.B. mit 2+0,00000001i anfangen soll, also ob es sich dabei um Ungenauigkeit handelt, oder ob der Imaginäranteil tatsächlich stimmt.
-
Steven schrieb:
Ein Problem noch: Wie erkenne ich zuverlässig, ob ich jetzt eine Lösung ohne Imaginäranteil habe? Da das Newtonverfahren ja nur eine Näherung liefert, weiß ich ja nicht, was ich z.B. mit 2+0,00000001i anfangen soll, also ob es sich dabei um Ungenauigkeit handelt, oder ob der Imaginäranteil tatsächlich stimmt.
geht nicht. ich würde bei 2+0,00000001i von rechenungenauigkeit ausgehen.
wer noch mehr genauigkeit haben mag, kann seltsame wege gehen:
nach dem finden einer lösung nochmal mit wenig verfälschten daten nachnähern. also die losung, die aus dem polynom kam, das evtl schon 5mal durch die polynomdivision ging, nochmal in das ursprungspolynom stecken und ganz genau machen. evtl sogar mit bisektion (heißt das quatrosektion im komplexen?).aber das tut normalerweise echt nicht not. so ein double hat ja 17 stellen, da werden hoffentlich schon 10 genaue stellen rauskommen.
-
Also gut, werde es so machen. Danke!
-
Noch ne Frage: Wie komme ich nochmal mit dem Hornerschema an die restlichen Nullstellen? Stehe grad etwas auf dem Schlauch...
-
Steven schrieb:
Noch ne Frage: Wie komme ich nochmal mit dem Hornerschema an die restlichen Nullstellen? Stehe grad etwas auf dem Schlauch...
haste eine nullstelle und benutzt das hornerschema, dann kriegste ja ganz rechts ne 0 raus. links von der 0 stehen die koeffizienten des restpolynoms nach der polynomdivision.
hornerschame macht also außer dem berechnen des funktionswertes auch noch nebenher polynomdivision.
das restpolynom nimmsta dann und suchst darin ganz normal mit newton die nächste nullstelle.
-
volkard schrieb:
Steven schrieb:
Noch ne Frage: Wie komme ich nochmal mit dem Hornerschema an die restlichen Nullstellen? Stehe grad etwas auf dem Schlauch...
haste eine nullstelle und benutzt das hornerschema, dann kriegste ja ganz rechts ne 0 raus. links von der 0 stehen die koeffizienten des restpolynoms nach der polynomdivision.
hornerschame macht also außer dem berechnen des funktionswertes auch noch nebenher polynomdivision.
das restpolynom nimmsta dann und suchst darin ganz normal mit newton die nächste nullstelle.Na Ok, bleibt mir wohl nix anderes übrig...
Trotzdem danke!EDIT: Funktioniert!