Newton-Verfahren

Hallo, warum konvergiert das Newton-Verfahren für $f(x) = x^n - a, a > 0, n > 0$ für jeden Startwert?

Taurin

Mach dir doch mal ne Skizze für zwei, drei Werte von n bzw. a.
Achte dabei darauf, dass du für n sowohl ungerade als auch gerade Werte nimmst.

PeterTheMaster

versuche, den banachschen fixpunktsatz anzuwenden.

Man kann ruhig n > 1 wählen, da x~k + 1~ = a nicht wirklich spannend ist.

Für n > 1 ergibt sich folgendes:
f(x) = xⁿ - a <=> x = a^1/n

Newton: x~k + 1~ = x_k - f(x_k) / f'(x_k)
=> x~k + 1~ = x_k - (x_kⁿ - a) / (n * x_k^n - 1^)
= x_k - 1/n * x_k + a / (n * x_k^n - 1^)
= (1 - 1/n) * x_k + a / (n * x_k^n - 1^)
= 1/n * ((n - 1) * x_k + a / x_k^n - 1^)

Die Konvergenz kann man wie folgt einsehen:
N(x) = (n - 1) / n * x_k + a / (n * x_k^n - 1^) ist für x > 0 strikt konvex, da N''(x) > 0. Weiterhin gilt N(x) → ∞ für x → 0 und für x → ∞. N(x) besitzt also genau ein Minimum, welches an der Stelle x = a^1/n wegen N'(a^1/n) = 0 angenommen wird. Da N(a^1/n) gerade a^1/n ist, ist N(x) > a^1/n für alle x > 0 und x ≠ a^1/n.

Für die Fehlerabschätzung gilt: a / x_k^n - 1^ ≤ a^1/n ≤ x~k + 1~ ≤ x_k für k = 1, 2, ...
Mit x_k ≥ a / x_k^n - 1^ folgt a / x_k^n - 1^ ≤ x~k + 1~ ≤ x_k, da x~k + 1~ ja gerade das (gewogene) arithmetische Mittel von x_k und a / x_k^n - 1^ ist. Der Rest ergibt sich mit 1 / x_k ≤ 1 / a^1/n.