Nullstellen "erraten"

Neue Frage »

Schlomo199 Auf diesen Beitrag antworten »
Nullstellen "erraten"
Hallo zusammen,

ich versuche gerade ein Programm zu schreiben, welches die Nullstellen beliebiger Polynomfunktionen berechnet.

Gar nicht so leicht wie ich es mir vorgestellt habe...

Ab Funktionen dritten Grades wird es da ja etwas komplizierter.
Wenn die Nullstelle eine ganze Zahl ist, kann man sie mit etwas Glück gezielt durch die ganzzahligen Teiler des letzten Faktors erraten. Top.
Gleiches gilt ähnlich für die Kehrwerte der ganzen Zahlen - 1/7, 1/10 usw. können also auch ganz gut gefunden werden.
(Ausnahmen erstmal außen vor)

Das Näherungsverfahren nach Newton erledigt scheinbar den Rest. Doch irgendwie komme ich hier nicht auf einen grünen Zweig.

Leitet man eine Funktion mit Nullstellen wie 13/7 in der Linearfaktorendarstellung her, so nähert man sich mit dem Newtonverfahren doch lediglich diesem Wert, was nun wenn ich ihn exakt wissen möchte?

Zweites Problem: Was ist wenn die Nullstellen 10^-6 Einheiten aneinander liegen. Dann laufe ich ja Gefahr die Nullstelle zu übersehen.

Welche Verfahren gibt es die mich weiter bringen können?
mYthos Auf diesen Beitrag antworten »

Mittels Newton- und anderen Verfahren wird eine Nullstelle wie 13/7 niemals exakt zu bestimmen sein, das liegt schon im Wesen dieser iterativen Verfahren, welche immer nach endlich vielen Schritten zu beenden sind, wenn die Differenz zweier aufeinanderfolgender Näherungswerte eine gegebene Fehlertoleranz unterschreitet.
Deshalb heissen diese Verfahren ja auch "Näherungsverfahren".

Es gibt zahlreiche Gründe, weshalb Näherungsverfahren keine Lösungen finden, obwohl welche existieren. Sie konvergieren in einer Umgebung der Nullstelle einfach nicht (--> lokale/globale Konvergenz).
Neben Newton gibt es natürlich andere Verfahren, die gegebenenfalls dieses Manko ausgleichen.
Fast immer funktioniert die "Regula Falsi" (Sekantenverfahren), das Intervallhalbierungsverfahren (Bisektion) oder das aus Newton mittels Differenzenquotient abgewandelte Sekantensteigungsverfahren (ohne Ableitung!).
Die ersten beiden erfordern zwar weit mehr Rechenschritte, dies spielt jedoch angesicht der zur Verfügung stehenden CAS mit entsprechender Rechenpower keine so große Rolle mehr.

Bei sehr nahe beieinander liegenden Nullstellen können zur ersten Eingrenzung graphische Verfahren (Plotter mit extremer Dehnung der x-Achse) helfen. Allerdings steht fest, dass diese dennoch sehr schwierig zu behandeln sind.

Siehe dazu --> http://docplayer.org/20827416-2-nullstellenbestimmung.html

mY+
Dopap Auf diesen Beitrag antworten »

meine Frage ist, ob rein rationale Nullstellen gesucht werden. Sind die Koeffizienten rational wird mit dem HN multipliziert und anschließend substituiert derart, dass der führende Koeffizient 1 ist. Jetzt greift der Satz von vieta...
Bei Erfolg noch rücksubstituieren.

code:
1:
[latex]p(x)=a_nx^n+a_{n-1}x^{n-1}+ \cdots +a_0 \quad \big |a_n^{n-1}[/latex]


code:
1:
[mathjax]x=\frac {z}{a_n}[/mathjax]


jetzt wird bei mir gar nichts mehr angezeigt verwirrt
Schlomo199 Auf diesen Beitrag antworten »

Ich stelle mir gerade im Prinzip eine Frage:

Wenn ich eine Funktion mittels beliebiger Linearfaktoren bestimmen kann, so muss ich doch auch irgendwie auf diese Linearfaktoren zurückkommen.
Ich habe überlegt den letzten Faktor einer Funktion n-ten Grades in n-Produkte zu zerlegen und anschließend alle Möglichkeiten in die Funktion einzusetzen.

Gibt es hier noch andere Verfahren die genau auf die Linearfaktoren zurückführen?



Bei Polynomfunktionen kann ich mich natürlich immer den Nullstellen der Ableitungen nähern um zu sehen wo die Funktion steigt oder fällt (zumindest näherungsweise).
So müsste ich eine Funktion zehnten Grades so lange ableiten bis ich eine Funktion zweiten Grades habe und könnte immer die steigenden, bzw. fallenden Intervalle der jeweiligen Stammfunktion bestimmen.
Stellt sich natürlich die Frage nach der Effizienz - außerdem habe ich ja am Ende "nur" eine Näherung ...
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Schlomo199
Wenn ich eine Funktion mittels beliebiger Linearfaktoren bestimmen kann, so muss ich doch auch irgendwie auf diese Linearfaktoren zurückkommen.

Das gilt nur sehr eingeschränkt.
Wenn eine Polynomgleichung nur rationale Koeffizienten hat, dann lassen sich alle rationalen Nullstellen exakt durch einen endlichen Algorithmus bestimmen. Nicht rationale Nullstellen lassen sich unabhängig von der Art der Koeffizienten nur für Polynome bis zum Grad 4 durch endliche geschachtelte Wurzelausdrücke bestimmen.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Schlomo199
Zweites Problem: Was ist wenn die Nullstellen 10^-6 Einheiten aneinander liegen. Dann laufe ich ja Gefahr die Nullstelle zu übersehen.

Hat man eine Nullstelle gefunden (sei es durch Numerisches Verfahren, sei es anderweitig), dann nimmt man gewöhnlich eine Polynomdivision vor und sucht die restlichen Nullstellen von nicht durch Betrachtung von , sondern von . Dadurch kann einem keine Nullstelle entgehen, auch nicht bei Einsatz von Verfahren wie Newton, wo man bei Einsatz "wilder" Startwerte nie so genau weiß, bei welcher Nullstelle man dann landet...
 
 
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von mYthos
Mittels Newton- und anderen Verfahren wird eine Nullstelle wie 13/7 niemals exakt zu bestimmen sein, das liegt schon im Wesen dieser iterativen Verfahren, welche immer nach endlich vielen Schritten zu beenden sind, wenn die Differenz zweier aufeinanderfolgender Näherungswerte eine gegebene Fehlertoleranz unterschreitet.


Da muss ich widersprechen. Bei mit findet Netwon bei jedem beliebigen Startwert nach einem Schritt die exakte Lösung. Nur weil es im Allgemeinen nur eine Nährung liefert, heißt es nicht, dass es immer nur eine Nährung liefert.
HAL 9000 Auf diesen Beitrag antworten »

Davon abgesehen: Bei einfachen Nullstellen sowie hinreichend nahem Startwert hat das Newtonverfahren quadratische Konvergenzordnung. Was salopp gesagt bedeutet, dass sich mit jedem Schritt die Anzahl der gültigen Ziffern der Nullstelle etwa verdoppelt ... was natürlich nur im Rahmen der Maschinengenauigkeit (bei 64Bit-Floatingpoint etwa 16 Dezimalstellen) gültig ist. D.h., mit einer Handvoll Iterationsschritten hat man bereits die Genauigkeit rausgeholt, die die Maschine nur leisten kann - was will man mehr. Augenzwinkern

Kritischer ist also, erstmal dieses "hinreichend nahe" zu bewerkstelligen.
mYthos Auf diesen Beitrag antworten »

Zitat:
Original von IfindU
....
Da muss ich widersprechen. Bei mit findet Netwon bei jedem beliebigen Startwert nach einem Schritt die exakte Lösung.
...

Natürlich. Wenn die Tangente mit der Kurve=Gerade zusammenfällt ...

Immer diese Erbsenzähler! Augenzwinkern Big Laugh Big Laugh

mY+
IfindU Auf diesen Beitrag antworten »

Es gibt ja auch nicht-triviale Beispiele.
In jeder Umgebung der 0 gibt es unendlich viele Startwerte, so dass Netwon angewendet auf sofort eine Nullstelle findet. Und das wirklich nach einem Schritt.
Dopap Auf diesen Beitrag antworten »

Nullstellen von Polynomen liegen in der Nähe von 0. Doch was heißt schon nahe? Ein vernünftiger Suchraum ist

zur Annäherung an die Linearfaktoren kann auch das Bairstow Verfahren
https://de.wikipedia.org/wiki/Bairstow-Verfahren
dienen, das einem Polynom einen irreduziblen quadratischen Faktor abspaltet. Konvergiert ebenfalls quadratisch.
HAL 9000 Auf diesen Beitrag antworten »

Man kann das Newtonverfahren übrigens auch "komplex" durchführen, d.h., mit komplexen Startwert - auch bei Polynomen mit rein reellen Koeffizienten. Wenn man nicht gerade das Pech hat, mit dem Startwert in der Nullmenge zu liegen, für die das Verfahren nicht konvergiert (z.B. weil irgendeine Iterierte Ableitungswert Null hat), dann konvergiert Newton gegen irgendeine (reelle oder echt komplexe) Nullstelle von . Ist es "echt komplex", d.h., mit , dann ist bei einem rein reellen Polynom auch das konjugiert komplexe eine Nullstelle. Damit ist dann eine Polynomdivision möglich - siehe meine Anmerkung 15.01.2018 14:17 .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »