Re: Beispiel, bei dem das Newton-verfahren versagt
Detlef Müller
> Hallo,
> ich brauche für ein Referat ein konkretes Beispiel
> (Funktion und Startwert) bei dem das Newton-Verfahren
> zur Nullstellensuche versagt, weil ein Extrempunkt zwischen
> Startwert und Nullstelle liegt.
>
> Kann mir da jemand helfen?
>
Mal sehen.
Als Nullstelle nehmen wir mal 0.
Dann ein Maximum irgendwo >0.
Wenn nach dem Maximum die Funktion stets monoton fällt, haben wir
gewonnen, denn dann führen die Tangenten immer weiter nach rechts und
das Verfahren führt in die Irre ... natürlich nur wenn keine weitere
Nullstelle existiert.
f(x)= x * e^(-x) ist ein Kandidat dafür.
Bei 0 ist offenbar eine Nullstelle.
Für x gegen Unendlich geht f(x) gegen Null,, ist aber stets >0, also
muss ein Maximum existieren.
Konkret: Die Ableitung (x * e^(-x))'=(1-x)e^(-x) wird 0 für x=1 und nur
dann. Nach unserer Vorüberlegung ist dort das Maximum (oder wahlweise
weil (1-x)e^(-x) einen Vorzeichenwechsel von + nach - hat) - denn nur wo
die Ableitung 0 ist, kann ein Maximum sein.
Für alle x>1 ist nun f'(x)<0, aber f(x)>0.
Wählt man also einen Startwert x0>1, so ist f(x0)/f'(x0)<0 und daher
x1=x0-f(x0)/f'(x0)>x0 ... dann ist aber x1 insbesondere auch >1 und das
Newton verfahren führt (wenn der Startwert größer als 1 ist) zu immer
größeren Zahlen, obwohl die einzige Nullstelle bei 0 liegt.
Ich hoffe, so etwas war gesucht.
Man kann auch zu Polynomfunktonen Startwerte konstruieren, so daß das
Verfahren zwischen zwei Werten (um das Extremum) pendelt - aber da ist
mir auf die Schnelle kein so klares Beispiel eingefallen ...
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Markus Steinborn
> Kann mir da jemand helfen?
Ich hätte da noch eine Funktion: f(x) = arcsinh(x). Diese Funktion hat
eine Nullstelle und ist streng monoton wachsend. Startet man das
Newton-Verfahren bei x0 = -20, so divergiert es (und es gibt noch nicht
mal einen uneigentlichen Grenzwert der Folgenglieder).
Grüße
Markus
PS: Liegt der Startpunkt "nahe genug" an der Nullstelle, so konvergiert
das Newton-Verfahren. Die Ursache ist immer, dass der Startpunkt zu weit
entfernt von der Nullstelle gewählt wurde.
Jens Seiler
> Hallo,
> ich brauche für ein Referat ein konkretes Beispiel
> (Funktion und Startwert) bei dem das Newton-Verfahren
> zur Nullstellensuche versagt, weil ein Extrempunkt zwischen
> Startwert und Nullstelle liegt.
f(x) = x^3 - 2x + 2
Bei Startwert x = 0 alterniert das Newton-Verfahren zwischen diesem
Startwert und 1. Die Nullstelle der Funktion liegt bei ca. -1,77, eine
Extremstelle (lokales Maximum) bei ca. -0,82. Somit liegt, wie von Dir
gefordert, zwischen dem Startwert 0 und der Nullstelle -1,77 ein
Extremum bei -0,82.
(Null- und Extremstelle hier nur schnell numerisch ausgerechnet und auf
zwei Stellen hinter dem Komma gerundet)
Das Beispiel stammt von
http://en.wikipedia.org/wiki/Newton%27s_method#Starting_point_enters_a_cycle
Ob das Scheitern ein "Zufall" ist, oder tatsächlich daran liegt, dass
Dein Kriterium mit dem Extrempunkt zwischen Startwert und Nullstelle
greift, das ist nun Dir überlassen :-)
Gruß,
Jens Seiler