4. Nullstellenberechnung von Ganzrationalen Funktionen

Nullstellenberechnung von Ganzrationalen Funktionen

  • S

    Hallo!

    Ich schreibe gerade ein Programm für ganzrationale Funktionen, also Funktionen in der Art:
    f(x) = ax^n + bx^(n-1) + cx^(n-2) + ... + dx^2 + ex + k
    z.B.
    f(x) = 2x^4 - x³ + 4x² - 9x + 2

    Das ganze Programm soll diese Funktionen ableiten, Extremwerte bestimmen und Nullstellen berechnen.
    Das Problem ist die Nullstellenberechnung. Ich brauche ein universelles Verfahren, um die erste Nullstelle zu finden; die restlichen kann ich ja dann per Horner-Schema ermitteln. Ich habe auch schon zwei Verfahren gefunden, allerdings haben beide so ihre Tücken:

    • Newtonverfahren: geht bei f'(x1) = 0 nicht, genausowenig wie bei f(x1) * f''(x1) <= 0 und wenn ein Vorzeichenwechsel von f''(x) während der Iteration auftritt. Wie kann ich diese Probleme umgehen und passende Startwerte für x1 finden, für die bei f''(x) kein Vorzeichenwechsel auftritt.
    • Bisektionsverfahren: Wenn f(x) > 0 für alle x, aber die x-Achse berührt, gibt es auch hier Schwierigkeiten. Außerdem habe ich keine Ahnung, wie ich die Startwerte ermittle, dass immer einer negativ und der andere positiv ist (Brute Force wäre eine langsame und unzuverlässige Möglichkeit).

    Irgendjemand von euch Mathe-Profis kann mir da doch sicher helfen... 🕶

    0
  • G

    Hallo,
    die falls die polynomiale Gleichung ganzzahlige Koeffizienten hat sind die ganzzahligen Lösungen Teiler des konstanten Terms k

    Grüße

    0
  • F

    Steven schrieb:

    Hallo!
    [*]Newtonverfahren: geht bei f'(x1) = 0 nicht

    Du kannst beispielsweise erst die Nullstellen der ersten Ableitung ausrechnen.
    Damit kannst du dann überprüfen ob dies auch Nullstellen der ursprünglichen Funktion sind.
    (Man beachte, dass man für diese Vorgehensweise bei der Bestimmung der Nullstellen für die erste Ableitung, genau dasselbe Problem hat wie vorher schon, du musst dasselbe also für 2-te,3-te...n-te Ableitung ebenfalls tun und dann von hinten aufdrösseln)

    Noch ein Ansatz (keine Ahnung ob das rechnerisch zu lange dauert):

    Berechne doch die n-2 te Ableitung, dass ist ein quadratischen Polynom.
    Von dem kannst du ALLE Nullstellen leicht bestimmen.
    Damit kannst leicht für die n-3 -te Ableitung Punkte angeben, an der sie positive bzw. negative Funktionswerte hat. Mit diesen kannst du dann das Bisektionsverfahren starten. Somit erhältst du eine Nullstelle der n-3 Ableitung. --> n-3-te Ableitung faktorisieren erhältst quadratischen Polynom -->
    alle Nullstellen ausrechnen. --> ALLE Nullstellen n-3 Ableitung bekannt -->
    mit diesem Wissen Startwert für Bisektionsverfahren von n-4-te Ableitung bestimmen usw....
    (hierbei merkt man auch, wenn nicht alle Nullstellen reell sind)

    Ansonsten gibts da noch das QD - Verfahren(Quotienten/Differenzen Algorithmus), oder den Horner - Algorithmus
    http://mathworld.wolfram.com/HornersMethod.html

    und noch eine ganze Reihe weitere Algorithmen von denen ich aber nicht weiß ob sie deine Probleme lösen:
    http://mathworld.wolfram.com/topics/Root-Finding.html

    Viele Grüße
    Fischi

    0
  • B

    das problem bei f'(x)=0 ist ja eigentlich das man nur nicht weiss in welche richtung man das Extrema suchen soll.
    man kann zB sagen
    ich beginne mit x=0
    mögliche werte
    f'(x)=0
    -> f(x) und f((x+1)^2) testen auf Vorzeichenwechsel
    solange sign(f(x))==sign f((x+1)^2)
    -> x=(x+1)^2
    ansonsten hat man ne Nullstelle eingekreist.
    hat die gleichen nachteile wie Bisektion, da mann Berührungspunkte übersieht.
    also sollte man die 1.Ableitung mitberechnen und auf steigungsänderungen achten.
    Wiederum der Vorzeichenwechsel zwischen f'(x) und f'((x+1)^2)
    sign f'(x))!=sign f'((x+1)^2)) -> finde Extrema im Interval, teste Extrema auf Null in f(x_e)

    0
  • S

    Danke erstmal. Ihr habt mir schon weitergeholfen. 🕶

    0
  • V

    Steven schrieb:

    Newtonverfahren: geht bei f'(x1) = 0 nicht, genausowenig wie bei f(x1) * f''(x1) <= 0 und wenn ein Vorzeichenwechsel von f''(x) während der Iteration auftritt. Wie kann ich diese Probleme umgehen und passende Startwerte für x1 finden, für die bei f''(x) kein Vorzeichenwechsel auftritt.

    Newton geht eigentlich. Das einzige, was passieren kann, ist ne Division durch 0 oder ein Auftauchen von NAN während der Rechnung. Dann würfelt man halt nen neuen Startwert und macht weiter. Fast alle Startwerte sind lieb.
    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.

    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.

    0
  • Z

    lass dein programm eine nullstelle raten 🤡

    0
  • S

    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... 😞

    0
  • V

    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).

    0
  • S

    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?

    0
  • V

    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

    0
  • S

    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.

    0
  • V

    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.

    0
  • S

    Also gut, werde es so machen. Danke!

    0
  • S

    Noch ne Frage: Wie komme ich nochmal mit dem Hornerschema an die restlichen Nullstellen? Stehe grad etwas auf dem Schlauch... 😞

    0
  • V

    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.

    0
  • S

    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!

    0
Anmelden zum Antworten