Newton-Verfahren

27.06.2019, 21:01	Annanas	Auf diesen Beitrag antworten »
Newton-Verfahren Meine Frage: Hey liebes Forum, ich habe eine Frage... Kann man der Iteration $\begin{eqnarray} x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} \end{eqnarray}$ irgendwie "ansehen", dass sie u.u. zum Ziel führt, also die Folge zu einer Nullstelle Funktion $\begin{eqnarray} f\in C^1(I) \end{eqnarray}$ konvergiert? Was wäre ein starkes Argument? Also wenn man diese Rekursionsvorschrift hat, inwiefern liefert diese Grund zur Annahme, dass sie gegen eine Nullstelle der Funktion konvergieren könnte? Meine Ideen: Beim Newton-Verfahren wird eine Funktion im Startwert $\begin{eqnarray} x_0 \end{eqnarray}$ in Form der Tangente von $\begin{eqnarray} f \end{eqnarray}$ in $\begin{eqnarray} x_0 \end{eqnarray}$ linearisiert und $\begin{eqnarray} x_1 \end{eqnarray}$ ist dann die Schnittstelle der Tangente mit der x-Achse.
28.06.2019, 00:22	mYthos	Auf diesen Beitrag antworten »
Es gibt einige Gründe, weshalb das Newton-Verfahren nicht konvergieren kann. 1. Der Startwert ist zu weit von der Nullstelle entfernt. 2. In unmittelbarer Nähe der Nullstelle befindet sich ein Wendepunkt, 3. Zwischen Startwert und Nullstelle befindet sich eine Polstelle oder sonstige Unstetigkeitsstelle. Daher ist es essentiell, sich vor Berechnung der Nullstelle ein Bild vom Graphen der Funktion zu machen. Idealerweise wählt man den Startwert so, dass er sich in einem Intervall befindet, an dessen Enden ein VZW (Vorzeichenwechsel) stattfindet. Damit ist man sicher, dass sich die vermutetet Nullstelle darin befindet. Anstatt der Ableitung kann auch der Differenzenquotient verwendet werden, wenn $\begin{eqnarray} \Delta x \end{eqnarray}$ hinreichen klein (konstant und im Bereich $\begin{eqnarray} 10^{-4} \end{eqnarray}$ ) ist. Dies ist besonders bei automatengestützten Rechenmethoden von Vorteil, diese finden die Nullstelle dann ebenso schnell (ohne mehr Itererationsschritte) und brauchen dazu keine Ableitung. Im Falle das Newton-Verfahren fehlschlägt, kann man auf die Regula Falsi (Sekantenverfahren) oder Bisektion (Intervallhalbierung) übergehen. mY+
28.06.2019, 00:29	Finn_	Auf diesen Beitrag antworten »
Sei $\begin{eqnarray} \varphi: [a,b]\to\mathbb R \end{eqnarray}$ differenzierbar. Hat die Gleichung $\begin{eqnarray} x=\varphi(x) \end{eqnarray}$ eine Lösung und gibt es ein $\begin{eqnarray} r \end{eqnarray}$ mit $\begin{eqnarray} \|\varphi'(x)\|<r<1 \end{eqnarray}$ für alle $\begin{eqnarray} x \end{eqnarray}$ , dann konvergiert die Fixpunktiteration $\begin{eqnarray} x_{n+1}=\varphi(x_n) \end{eqnarray}$ für jeden Startwert $\begin{eqnarray} x_0 \end{eqnarray}$ . Nun haben wir $\begin{eqnarray} \varphi(x) = x-\frac{f(x)}{f'(x)}. \end{eqnarray}$ Angenommen, $\begin{eqnarray} f\in C^2([a,b]) \end{eqnarray}$ und $\begin{eqnarray} f'(x)\ne 0 \end{eqnarray}$ , dann ist auch $\begin{eqnarray} \varphi \end{eqnarray}$ differenzierbar und es gilt $\begin{eqnarray} \varphi'(x) = 1-\frac{f'(x)f'(x)-f(x)f''(x)}{f'(x)^2} = \frac{f(x)f''(x)}{f'(x)^2}. \end{eqnarray}$ Da $\begin{eqnarray} f(x) \end{eqnarray}$ , $\begin{eqnarray} f'(x) \end{eqnarray}$ und $\begin{eqnarray} f''(x) \end{eqnarray}$ stetig sind, ist auch $\begin{eqnarray} \varphi'(x) \end{eqnarray}$ stetig. Nach dem Satz vom Minimum und Maximum muss $\begin{eqnarray} \|\varphi'(x)\| \end{eqnarray}$ somit auf dem Intervall $\begin{eqnarray} [a,b] \end{eqnarray}$ ein Maximum annehmen. Daher genügt es bereits, wenn $\begin{eqnarray} \|\varphi'(x)\|<1 \end{eqnarray}$ ist, denn wenn $\begin{eqnarray} M<1 \end{eqnarray}$ das Maximum ist, dann kann man $\begin{eqnarray} r:=(M+1)/2 \end{eqnarray}$ halbe setzen. Bei einer Nullstelle $\begin{eqnarray} x_0 \end{eqnarray}$ ist $\begin{eqnarray} f(x_0)=0 \end{eqnarray}$ . Wegen $\begin{eqnarray} f'(x_0)\ne 0 \end{eqnarray}$ muss auch $\begin{eqnarray} \|\varphi'(x_0)\|=0 \end{eqnarray}$ sein. Da $\begin{eqnarray} \|\varphi'(x)\| \end{eqnarray}$ stetig ist, muss $\begin{eqnarray} \|\varphi'(x)\|<1 \end{eqnarray}$ in einer hinreichend kleinen Umgebung der Nullstelle erfüllt sein. Liegt der Anfangswert in dieser Umgebung, dann konvergiert das Verfahren sicher.
29.06.2019, 16:21	Annanas	Auf diesen Beitrag antworten »
Ich habe nicht ganz alles verstanden... Aber vielen herzlichen Dank für eure Hilfe!
29.06.2019, 20:30	mYthos	Auf diesen Beitrag antworten »
Der Beitrag von Finn ist Hochschulwissen, meiner eher im Schulbereich angesiedelt. Nimm dir einfach, was du brauchst. Im Übrigen gibt es sehr viele einschlägige Themen in diesem Board, suche bitte nach Newton bzw. Newton-Verfahren. mY+

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »