Newton-Verfahren bei Mehrfacher Nullstelle

23.08.2007, 20:32	tigerbine	Auf diesen Beitrag antworten »
Newton-Verfahren bei Mehrfacher Nullstelle In vielen Skripten bin ich auf den Kommentar gestoßen: "Bei mehrfachen Nullstellen konvergiert das Newton-Verfahren linear" Schön, aber wie sieht es mit einem Beweis aus? Eine Möglich Aufgabenstellung wäre diese angehängte. Aber wie geht man da vor? Erst einmal die klassischen Notationen. Newton-Iteration $\begin{eqnarray} x_{k+1}:= x_k - \frac{f(x_k)}{f'(x_k)} \end{eqnarray}$ zugehörige Fixpunktfunktion $\begin{eqnarray} h(x):=x - \frac{f(x)}{f'(x)} \end{eqnarray}$ Nun lautet die Funktion f wie folgt, m > 1 $\begin{eqnarray} f(x):=(x-x^)^m \cdot g(x) \end{eqnarray}$ $\begin{eqnarray} f'(x) &&= m \cdot (x-x^)^{m-1}\cdot g(x) + (x-x^)^{m}\cdot g'(x) \\&& = (x-x^)^{m-1} \cdot [m \cdot g(x) + (x-x^) \cdot g'(x)] \end{eqnarray}$ $\begin{eqnarray} f''(x) &&= m \cdot (m-1) \cdot (x-x^)^{m-2} \cdot g(x) + m \cdot (x-x^)^{m-1}\cdot g' (x) + m \cdot (x-x^)^{m-1} \cdot g'(x) + (x-x^)^{m}\cdot g''(x) \\&& = (x-x^)^{m-2}\cdot [m\cdot (m-1) \cdot g(x) + m \cdot (x-x^) \cdot g'(x) + m \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot g''(x)] \end{eqnarray}$ Es liegt bei dem Quotienten eine hebbare Definitionslücke vor. $\begin{eqnarray} \frac{f(x)}{f'(x)} = \frac{(x-x^)^m \cdot g(x)}{m \cdot (x-x^)^{m-1}\cdot g(x) + (x-x^)^{m}\cdot g'(x)} =\frac{(x-x^)\cdot g(x)}{m \cdot g(x) + (x-x^) \cdot g'(x)} \end{eqnarray}$ So dass gilt: $\begin{eqnarray} \lim_{x \to x^} ~\frac{f(x)}{f'(x)} = 0 \end{eqnarray}$ $\begin{eqnarray} \lim_{x \to x^}~h(x) =x^ \end{eqnarray}$ Weiter ist nun: $\begin{eqnarray} h'(x) && = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{[f'(x)]^2} \\&&= \frac{f(x)f''(x)}{[f'(x)]^2} \\\\ && = \frac{\Bigl((x-x^)^m \cdot g(x) \Bigr) \cdot \Bigl( (x-x^)^{m-2}\cdot [m\cdot (m-1) \cdot g(x) + m \cdot (x-x^) \cdot g'(x) + m \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot g''(x)]\Bigr)}{\Bigl( (x-x^)^{m-1} \cdot [m \cdot g(x) + (x-x^) \cdot g'(x)]\Bigr)^2} \\&& = \frac{\Bigl((x-x^)^m \cdot g(x) \Bigr) \cdot \Bigl( (x-x^)^{m-2}\cdot [m\cdot (m-1) \cdot g(x) + m \cdot (x-x^) \cdot g'(x) + m \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot g''(x)]\Bigr)}{ (x-x^)^{2m-2} \Bigl([m \cdot g(x) + (x-x^) \cdot g'(x)]\Bigr)^2}\\&& = \frac{g(x) \cdot \Bigl( (x-x^)^{m-2}\cdot [m\cdot (m-1) \cdot g(x) + m \cdot (x-x^) \cdot g'(x) + m \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot g''(x)]\Bigr)}{ (x-x^)^{m-2} \Bigl([m \cdot g(x) + (x-x^) \cdot g'(x)]\Bigr)^2} \\&& = \frac{g(x) \cdot [m\cdot (m-1) \cdot g(x) + m \cdot (x-x^) \cdot g'(x) + m \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot g''(x)]}{ [m \cdot g(x) + (x-x^) \cdot g'(x)]^2} \\\\&& = \frac{m\cdot (m-1) \cdot [g(x)]^2 + m \cdot (x-x^) \cdot g(x) \cdot g'(x) + m \cdot (x-x^) \cdot g(x) \cdot g'(x) + (x-x^)^2 \cdot g(x) \cdot g''(x)]}{ m^2 \cdot [g(x)]^2 +2 \cdot m \cdot g(x) \cdot (x-x^) \cdot g'(x) + (x-x^)^2 \cdot [g'(x)]^2} \\\\&& = \frac{(m-1) \cdot [g(x)]^2 + (x-x^) \cdot g(x) \cdot g'(x) + (x-x^) \cdot g(x) \cdot g'(x) + \frac{1}{m}\cdot(x-x^)^2 \cdot g(x) \cdot g''(x)]}{ m \cdot [g(x)]^2 +2 \cdot g(x) \cdot (x-x^) \cdot g'(x) + \frac{1}{m}\cdot (x-x^)^2 \cdot [g'(x)]^2} \end{eqnarray}$ Somit gilt: $\begin{eqnarray} \lim_{x \to x}~h'(x) = \frac{m-1}{m} < 1 \end{eqnarray}$ Was kann man nun daraus folgern? Die Hebbarkeit der "Division durch 0" sicher, dass das Verfahren in einer Umgebung $\begin{eqnarray} K_r(x) \setminus \{x^\} \end{eqnarray}$ wohl definiert ist. Nun muss noch die Konvergenz nachgewiesen werden. Diese müsste doch analog zum Newton verfahren einer C^1-Funktion gehen? $\begin{eqnarray} \|x_{k+1}-x^\| && = \|x_k - \frac{f(x_k)}{f'(x_k)} - x^\| \\&& = \|x_k - x^- \frac{f(x_k)}{f'(x_k)} \| \\&& = \|(x_k-x^)-(x_k-x^) \cdot \frac{f(x_k)-f(x^)}{(x_k-x^)f'(x_k)} \| \\&& \stackrel{\text{MWS}}\leq \|x_k-x^\| \cdot \|1-\frac{f'(\zeta)}{f'(x_k)}\| \end{eqnarray}$ Da f' stetig ist und $\begin{eqnarray} \zeta \in (x_n,x^) \end{eqnarray}$ oder $\begin{eqnarray} \zeta \in (x^,x_n) \end{eqnarray}$ gilt, kann man den Radius r ggf. soweit verkleinern, dass gilt: $\begin{eqnarray} \|1-\frac{f'(\zeta)}{f'(x_k)}\| \leq q < 1 \end{eqnarray}$ Mit Induktion folgt dann, dass für $\begin{eqnarray} x_0 \in K_r(x^) \end{eqnarray}$ alle Iterierten in $\begin{eqnarray} K_r(x^) \end{eqnarray}$ . Damit folgt aus $\begin{eqnarray} \|x_{k+1}-x^\| \leq q \cdot \|x_k-x^\| \end{eqnarray}$ die "lineare Konvergenz" (und damit die Konvergenz!) der Folge gegen x. Die lineare Konvergenzrate beträgt $\begin{eqnarray} \frac{m-1}{m} \end{eqnarray*}$
23.08.2007, 22:43	tigerbine	Auf diesen Beitrag antworten »
Edit, vielleicht kann ja jemand eine Stellungnahme zu der Lösung abgeben.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »