Suche einen Algorithmus zur Nullstellenberechnung

[Sliver21]

Kennt jemand von einen Algorithmus, der alle Nullstellen einer ganzrationalen Funktion n. Grades (wenn es nicht geht, dann reicht es auch bis zum 5. Grad) in einem vorgegebenen Intervall berechnet?
Ich habe es schon mal mit dem Halbierungsverfahren versucht, dieser geht bei mir nur dann, wenn in dem betrachteten Intervall nur eine Nullstelle ist. Kennt ihr einen Trick, um alle Nullstellen berechnen zu können?

[Senior Sanchez]

Das dürfte eigentlich per Newton-Verfahren gehen, wenn mich nicht alles täuscht, das zu implementieren ist aber nicht gerade einfach. Irgendwann habe ich auch das schon mal gemacht, aber ich weiß es nicht mehr genau, müsste mich da auch erst wieder reinfuchsen und im mom hab ich dafür keine zeit (Montag Info-Klausur: Theoretische Informatik)

Im grunde sollte es aber folgendermaßen gehen. Das Programm muss schrittweise die X-Werte ablaufen und schauen ob ein Vorzeichenwechsel der Funktionswerte stattfindet, wenn ja, so ist hier eine Nullstelle. Nun kann man über den Ansatz Newton-Verfahren (musste aber die Funktion auch ableiten lassen, aber sollte schnell und einfach gehen, sofern da keine aufwendigen Differenzierungsregeln zum einsatz kommen sollten) eine Tangente an den Grafen legen und dann per Näherung die Nullstellen bestimmen.


mfg Senior Sanchez

[Gangstaslida]

Der beste Weg die Nullstelle herauszufinden ist imo das Newtonverfahren (http://de.wikipedia.org/wiki/Newton-Verfahren). Das Problem ist, dass du die Funktion ableiten musst. Man kann jedoch die Tangente (->Ableitung) auch näherungsweise berechnen (wie es z.B. auch mein TR macht).

Besonders die geometrische Interpretation bei Wikipedia sollte selbsterklärend sein.

Ich hoffe, ich konnte helfen.

Eluskio

[Sliver21]

Danke schon mal für eure Tipps. Das Newton'sche Näherungsverfahren kenne ich, jedoch ist es damit noch lange nicht getan. Das Problem besteht ja schon mal darin, einen günstigen Anfangswert für die Näherung zu finden, denn zwischen dem Anfangswert und der tatsächlichen Nullstelle darf sich weder ein Extrempunkt, noch ein Sattelpunkt befinden. Das macht das alles nicht einfach.
Auch das schrittweise Ablaufen von x-Werten ist problematisch. Welche Differenz müssen dann benachbarte x-Werte haben, damit man keine Nullstellen überspringt. Es kann zum Beispiel sein, dass die Funktion im Intervall [5,444/5,445] 2 Nullstellen hat, was dazu führt, dass man kein Vorzeichenwechsel bemerkt.

[Jojo]

Such mal im Netz nach 'Regula Falsi' - das Verfahren liefert meiner Erfahrung nach auch mit relativ schlechten Anfangswerten gute Ergebnisse.
Zum Thema dicht beieinander liegende Nullstellen: Ist knifflig, man kann z.B. (bei Regula Falsi) die Nullstelle als nächsten linken Rand des Suchintervalls nehmen.

[ethrandil]

(x-a)*(x-b)*(x-c) = (x*x-(a+b)x+a*b)*(x-c) =

x^3-(a+b+c)x^2+(ab+ac+bc)*x-abc

Behauptung:
Sei q der konstante Term und f eine Funktion, die sich wie oben gezeigt durch beliebig viele (x-r)-Terme darstellen lässt. Dann liegen alle Nullstellen im Bereich [-|r|;|r|].


Ja, ich weiß dass das nicht viel hilft, aber ich wollts nur mal so sagen *gg*.

- Eth

[pajofego]

Danke schon mal für eure Tipps. Das Newton'sche Näherungsverfahren kenne ich, jedoch ist es damit noch lange nicht getan. Das Problem besteht ja schon mal darin, einen günstigen Anfangswert für die Näherung zu finden, denn zwischen dem Anfangswert und der tatsächlichen Nullstelle darf sich weder ein Extrempunkt, noch ein Sattelpunkt befinden. Das macht das alles nicht einfach.
Auch das schrittweise Ablaufen von x-Werten ist problematisch. Welche Differenz müssen dann benachbarte x-Werte haben, damit man keine Nullstellen überspringt. Es kann zum Beispiel sein, dass die Funktion im Intervall [5,444/5,445] 2 Nullstellen hat, was dazu führt, dass man kein Vorzeichenwechsel bemerkt.

In diesem Zusammenhang fällt mir die Picard Iteration ein. Sie macht weniger Schwierigkeiten, konvergiert aber schlechter als das Newton Verfahren (linear). Deswegen kombiniert man beide. Sprich zuerst ein bischen Picard, um das Problem zu umgehen einen "guten" Startwert zu finden, um dann nach ein paar interationsschritten mit dem Newtonverfahren weiterzumachen. Schau dich mal ein bischen im www um. Ich denke da wird es schon ein paar Skripte dazu geben.

Gruss pajofego

[Sliver21]

Danke, ich schau mich mal im Internet um.