4. Alle Nullstellen einer Funktion finden

Alle Nullstellen einer Funktion finden

  • T

    Hier geht es um folgendes:
    Ich habe ein Programm zum newton'schen Näherungsverfahren in C++ geschrieben und möchte nun mittels Horner-Schema und p/q-Formel alle Nullstellen ausfindig machen. Kann mir dabei jemand helfen? Ich komme nämlich bei einer Funktion 5 Grades lediglich auf 3 Nullstellen. Irgendwas fehlt - ich weiß nicht was!
    Ihr müsst in diesem Fall nicht am Programm selber arbeiten, es genügt mir zu erklären wie ich weitere Nullstellen finden kann (auf mathematischer Basis).

    Ich verweise dazu auf eine aktuelle Diskusion bezüglich des jetzigen Standes auf das C++Forum: http://www.c-plusplus.net/forum/viewtopic-var-p-is-1032412.html#1032412

    0
  • C

    Vielleicht hat die Funktion tatsächlich nur drei Nullstellen 😉 (sowas soll's geben)

    Btw berechnet das Horner-Schema afaik nicht die Nullstelle einer Funktion, sondern den Funktionswert an einer bestimmten Stelle - also könntest du mal näher erläutern, WIE du da rechnest?

    0
  • T

    Ich habe doch bewusst auf den Thread im C++Forum verwiesen weil dort meine genauere Problemstellung steht. Habe hier einen Thread eröffnet weil hier die Mathematiker abhängen 😉

    0
  • C

    Dann solltest du dir auch das durchlesen, was andere Leute in deinem Thread geschrieben haben 😉 (Braunsteins letzter Beitrag sollte z.B. weiterhelfen - vorausgesetzt du kannst etwas damit anfangen :D)

    0
  • M

    also wenn du bei einer funktion 5. grades schon drei nullstellen hast, dann sollte es ein leichtes sein die anderen beiden (wenn vorhanden) zu finden:

    Wenn du ein polynom 5. grades hast z.B. x5-15x4+85x^3+274x-120
    und drei Nullstellen (sagen wir 1,2 und 3) dann weißt du, dass das polynom teilbar ist durch (x-1),(x-2) und (x-3), also auch durch (x-1)(x-2)(x-3) = x3-6x2+11x-6.
    Jetzt machst du einfach polinomdivison:

    (x^5-15x^4+85x^3+274x-120):(x^3-6x^2+11x-6) = x^2-9x+6

    damit hast du ein polynom 2. grades und hier kannst du ganz leicht deine nullstellen finden. hier: 4 und 5
    also gilt: x5-15x4+85x^3+274x-120 = (x-1)(x-2)(x-3)(x-4)(x-5)

    0
  • T

    Warum bestimmst Du die übrigen Nullsten nicht auch mit dem Newton-Verfahren in gewünschter Genauigkeit?

    Algebraische und numerische Verfahren zusammenzumixen kann unter Umständen zu bösen Fehlern führen.

    0
  • W

    Wenn ich es richtig verstanden habe, willst du die Nullstellen eines Polynoms n-ten Grades (in deinem Fall setzt du n=5) finden.

    Es gibt in der Tat den bekannten Satz: ein Polynom n-ten Grades besitzt n Nullstellen. Jedoch gilt dieser nur im Körper der komplexen Zahlen und Nullstellen können mehrfach auftreten (zählen dann mehrfach).

    Mit Newton-Verfahren kannst du nur reelle Nullstellen bestimmen (wenn ich mich irre, was ich nicht glaube 😉 , bitte ich um Verzeihung). Es gibt andere Verfahren, mit denen man auch komplexe Nullstellen bestimmen kann. Hier müsste ich jedoch selber mal nachschauen, die kann ich auch nicht im Kopf.

    Außerdem kann man mit Newton in der Standardversion nur Nullstellen der algebraischen Vielfachheit 1 bestimmen. Wenn diese nicht 1 beträgt, kann man das Verfahren jedoch einfach modifizieren (jedoch muss die algebraische Vielfachheit bekannt sein).

    Die Idee von MamboKurt ist durchaus nicht dumm, jedoch ist Turings Einwand berechtigt: die Addition von Gleitkommazahlen mit unterschiedlichen Vorzeichen kann verdammt schlecht konditioniert sein. Da sollte man schon aufpassen.

    Jedoch muss man dazu sagen, dass auch das Finden der Nullstellen von Polynomen ein numerisch hochgradig schlecht konditioniertes Problem ist. Ob da die Auslöschungsprobleme viel machen: weiß nicht.

    0
  • B

    Hallo,

    Ich habe mich mal im Internet etwas umgesehen. Prinzipiell wird da auch immer nur dieser eine Algorithmus verwendet.
    1. Nullstelle suchen (z.Bsp. über Newton)
    2. Polynom vereinfachen durch Abspalten eines Linearfaktors
    3. mit dem vereinfachten Polynom zurück zu 1.

    Für den Punkt 2 kann man auch das Hornerschema verwenden (siehe http://www.mathematik.uni-stuttgart.de/HM/HMD/aufgaben00/node264.html)
    Hier noch was zu Polynomdivision
    http://de.wikipedia.org/wiki/Polynomdivision
    Das von Turing genannte Problem haben wir aber trotzdem. Da beim Newton-Verfahren nur eine Näherungslösung herauskommt, ist das vereinfachte Polynom ebenfalls nur eine Näherung. Somit können im Verlauf des Verfahrens die gefundenen Nullstellen immer ungenauer werden.
    Man könnte auch versuchen im Bereich der Nullstellenschranken (http://de.wikipedia.org/wiki/Polynom) einfach mehrere verschiedenen Startwerte für Newton zu nehmen und so nach dem Zufallsprinzip Nullstellen suchen. Evtl sind beide Verfahren kombinierbar.
    Es wird aber für beide Verfahren kompliziert, wenn zwei Nullstellen dicht nebeneinader liegen.
    Hier auch mal eine Buchempfehlung. Ist zwar für komplexe Nullstellen zeigt aber auch wie komplex das Thema ist. 😉
    Die analytische Theorie der Polynome | ISBN: 3899980433

    Ciao

    0
  • ?

    Hi t1m0n,
    Hast du dein programm fertig geschrieben und funktioniert es?

    Könntest du es vielleicht mal hier rein stellen?

    0
Anmelden zum Antworten