Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wurzel-Algorithmus

Wurzel-Algorithmus

Universität / Fachhochschule

Tags: Algorithmus, Wurzel

Sukomaki aktiv_icon

12:00 Uhr, 19.09.2025

Guten Morgen,

ich möchte zeigen, dass mein Wurzel-Algorithmus immer zur Wurzel konvergiert.

Ich beginne mit der Gleichung

x^{2} = a

Newton auf

x^{2} - a

angewendet ergibt

x_{n + 1} = x_{n} - \frac{x_{n}^{2} - a}{2 x_{n}}

.

Das ist dann

x_{n + 1} = \frac{1}{2} (x_{n} + \frac{a}{x_{n}})

.

Sei

T (x) = \frac{1}{2} (x + \frac{a}{x})

.

Ableiten von

T (x)

zeigt, dass

T (x)

bei

x = \sqrt{a}

ein Minimum hat.

Injektiv ist die Funktion auf

(0, \infty)

allerdings noch nicht.

Betrachte ich nun die Abbildung auf dem Intervall

[\sqrt{a}, \infty)

, so
stellt der Teil der Funktion eine Kontraktion dar, die laut dem Banachschen
Fixpunktsatz gegen

\sqrt{a}

(Lösung von

T (x) = x

) konvergiert.

Fallunterscheidung :

Wenn

a \geq 1

und

x_{0} = a

, so geht

(x)_{n}

von oben gegen

\sqrt{a}

.

Wenn

0 < a < 1

und

x_{0} = 1

, so geht

(x)_{n}

von oben gegen

\sqrt{a}

.

Das ist jetzt ein Spezialfall betreffs des Startwertes.

Die Definition von Konvergenz einer Folge

(x)_{n}

nach

c

in einem vollständig metrischen Raum ist ja :

\forall ε > 0 : \exists n_{0} \in ℕ : \forall n > n_{0} : ∣ x_{n} - c ∣ < ε

Wie kann ich jetzt ganz allgemein, also unabhängig vom Startwert, zeigen, dass

(x)_{n}

immer zur Wurzel von

a

konvergiert?

Ich habe es schon versucht mit

∣ x_{n + 1} - \sqrt{a} ∣ \leq τ \cdot ∣ x_{n} - \sqrt{a} ∣

mit

τ < 1

Also

∣ \frac{1}{2} (x_{n} + \frac{a}{x_{n}}) - \sqrt{a} ∣ \leq τ \cdot ∣ x_{n} - \sqrt{a} ∣

.

Aber leider vergebens.

Hat jemand eine Idee zu einem alternativen Beweis?

G
Sukomaki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
n-te Wurzel
Wurzel (Mathematischer Grundbegriff)

mathadvisor aktiv_icon

13:27 Uhr, 19.09.2025

Du könntest einfach den Beweis der Konvergenz des NV abschreiben, angepasst für Dein Beispiel.

calc007

18:51 Uhr, 19.09.2025

Hallo
"ich möchte zeigen, dass mein Wurzel-Algorithmus immer zur Wurzel konvergiert."
Dieses 'immer' wird wohl kaum funktionieren.
Denn, es lässt sich zeigen, dass der Algorithmus Probleme (Singularitäten)

>

bei

x_{n} = 0

>

bei

x_{n} = - \sqrt{a}

hat.

Ich will vermuten, dass du eigentlich nur den positiven Ast der Wurzelfunktion betrachtest,
und dazu nur positive Startwerte

x_{n}

zugrundelegst.
Wenn du das noch einschränkend dazu erklärst, dann sehe ich gute Chancen für dich...

Sukomaki aktiv_icon

10:26 Uhr, 20.09.2025

Mit "immer" meine ich, dass der Algorithmus unabhängig vom Startwert bei

\sqrt{a}

landet.

Dabei beachte ich die von Dir genannten Beschränkungen.

Also, dass der Startwert positiv ist und ich mich dadurch automatisch nur auf dem positiven Ast bewege.

(Es ist ja hier so, dass diejenige Nullstelle (

\sqrt{a}

oder

- \sqrt{a}

) erreicht wird, die näher am Startwert liegt.
Wenn der Startwert

0

ist, ist

f ʹ (0) = 0

und das Verfahren divergiert)

Allerdings habe ich Schwierigkeiten zu zeigen, dass der Abstand zu

\sqrt{a}

beim Iterieren kleiner wird.

Tatsächlich gibt es Beispiele, wo der Abstand zu

\sqrt{a}

erst einmal größer wird :

a = 5, x_{0} = 0.01 \Rightarrow x_{1} = 250.005

∣ 250.005 - \sqrt{5} ∣ > ∣ 0.01 - \sqrt{5} ∣

calc007

11:18 Uhr, 20.09.2025

Du bist widersprüchlich.
Die Aussage
"Mit 'immer' meine ich, dass der Algorithmus unabhängig vom Startwert bei

\sqrt{a}

landet."
ist doch widersprüchlich zur Einschränkung auf

\to

positive Startwerte.

Aber wie gesagt, wenn es dir denn gelingt, eindeutigere Erklärungen zu geben,
ahne ich guten Mutes, dass wir auf positive Äste und Startwerte beschränkt eigentlich das gleiche meinen und aussichtsreich Konvergenz zeigen können.
:-)

mathadvisor aktiv_icon

11:23 Uhr, 20.09.2025

Ja, Du hast zwar "immer" geschrieben, und die Voraussetzungen nicht sauber am Anfang formuliert (damit spätere Verwirrung riskiert), aber das ist nicht das Problem.
Generell muss der Abstand zur Nullstelle auch nicht immer kleiner werden - Konvergenz ist was anderes. Also, fang mal geordnet an: Was ist vorausgesetzt, was genau willst Du zeigen?
Nochmal: Warum schreibst Du nicht einen bekannten Beweis einfach um (wenn es um Konvergenz geht)?

Sukomaki aktiv_icon

16:01 Uhr, 20.09.2025

Konvergenz heisst :

\forall ε > 0 : \exists n_{0} \in ℕ : \forall n \geq n_{0} : ∣ a_{n} - c ∣ < ε

Notwendige Bedingung dazu ist, dass die Differenzen der Folgeglieder eine Nullfolge bilden.

Beispiel :

(a)_{n} = 2 + \frac{1}{n}

(a)_{n}

konvergiert gegen

c = 2

.

Dabei ist

n_{0} = ⌊ \frac{1}{ε} + 1 ⌋

Die Differenz der Folgeglieder ist

(2 + \frac{1}{n + 1}) - (2 + \frac{1}{n}) = - \frac{1}{n (n + 1)}

Das ist eine Nullfolge.

Also, es ist gegeben :

* die rekursiv definierte Folge

a_{n + 1} = \frac{1}{2} \cdot (a_{n} + \frac{a}{a_{n}})

* ein Startwert

a_{0} > 0

und ich möchte zeigen, dass

*

lim_{n \to \infty} a_{n} = \sqrt{a}

Es gelingt mir noch nicht zu zeigen, dass

∣ a_{n + 1} - a_{n} ∣

eine Nullfolge darstellt :

Es ist ja

∣ a_{n + 1} - a_{n} ∣ = ∣ - \frac{1}{2} a_{n} + \frac{a}{a_{n}} ∣ = ∣ \frac{1}{2} \frac{- a_{n}^{2} + a}{a_{n}} ∣

Mit

a_{n} = \sqrt{a} + ε_{n}

ist das

∣ \frac{1}{2} \frac{- (\sqrt{a} + ε_{n})^{2} + a}{\sqrt{a} + ε_{n}} ∣ = ∣ - \frac{1}{2} \frac{ε_{n} (2 \sqrt{a} + ε_{n})}{\sqrt{a} + ε_{n}} ∣

Und hier hänge ich. Ich sehe nicht, warum das eine Nullfolge ist.

Hilft es,

\sqrt{a} + ε

∣ \frac{1}{2} \frac{- (\sqrt{a} + ε_{n})^{2} + a}{\sqrt{a} + ε_{n}} ∣

abzuspalten, also

(\sqrt{a} + ε_{n}) (\frac{1}{2} (- 1 + \frac{a}{(\sqrt{a} + ε_{n})^{2}}))

?

Auf de.wikipedia.org/wiki/Newtonverfahren#Erstes_Beispiel wird nämlich so vorgegangen.

Das bringt mich zu der Frage von mathadvisor :

> Warum schreibst Du nicht einen bekannten Beweis einfach um?

Das ist leichter gesagt als getan. Zum einen sind wohl mein Fall und derjenige auf Wikipedia
nicht vergleichbar. Und zum anderen verstehe ich leider die Umformungen noch nicht wirklich.
Ich denke aber, dass ich sie verstehen werde, wenn ich noch ein wenig darüber nachdenke.

Anmerkung : Ich habe diese Aufgabe an der Uni nicht gelöst bekommen. Sie sollte aber
eigentlich nicht all zu schwer sein. Und ich bin guten Mutes, dass ich das Zeigen der
Konvergenz noch in einem vertretbarem Zeitraum hinbekomme.

mathadvisor aktiv_icon

16:11 Uhr, 20.09.2025

"Notwendige Bedingung dazu ist, dass die Differenzen der Folgeglieder eine Nullfolge bilden."

Ja, aber nicht hinreichend, nützt also für die Konvergenz von

a_{n}

gar nichts.

"Auf de.wikipedia.org/wiki/Newtonverfahren#Erstes_Beispiel wird nämlich so vorgegangen."

Nein, da wird ganz anders vorgegangen. Außerdem ist es nur ein Beispiel für eine Abschätzung, und kein Konvergenzbeweis.

"Zum einen sind wohl mein Fall und derjenige auf Wikipedia nicht vergleichbar."

Schau dort unter "Lokale Konvergenz", das ist der allgemeine Fall, wende den auf Dein

f

an, das geht immer.

Du kannst so anfangen wie im Wikipedia-Beispiel (aber genau schauen, was dort steht), und für den Rest des Beweises wie im allgemeinen Fall vorgehen.

Sukomaki aktiv_icon

10:23 Uhr, 21.09.2025

Ich weiss nicht genau, auf welchen Abschnitt des Artikels Du Dich beziehst.

Ist es die "Lokale quadratische Konvergenz" unter "Konvergenzbetrachtungen"?

Die mit dem Lagrange-Restglied?

Der Beweis ist ja ehrlich gesagt für mich nicht ganz einfach. :-)

mathadvisor aktiv_icon

11:03 Uhr, 21.09.2025

Ja, das meine ich. Gehe vor wie eben erklärt (also erst wie im Beispiel), dann hast du auch mit Lagrange nichts zu tun.

Sukomaki aktiv_icon

17:52 Uhr, 21.09.2025

Ich habe mal die Herleitung auf mein Beispiel angewendet.

In meinem Beispiel ist

f (x) = x^{2} - a

\sqrt{a}

ist einfache Nullstelle. Daher ist dort die Ableitung ungleich Null.
Dadurch divergiert das Verfahren dort nicht.

Taylor-Entwicklung ergibt :

0 = f (\sqrt{a}) = f (x) + f ʹ (x) (\sqrt{a} - x) + \frac{1}{2} \cdot 2 \cdot (\sqrt{a} - x)^{2}

.

D.h. ich muss kein Restglied betrachten.

Umgestellt nach

x - \sqrt{a}

ist das

x - \sqrt{a} = \frac{f (x)}{f ʹ (x)} + \frac{1}{f ʹ (x)} (x - \sqrt{a})^{2}

.

In Newton-Schreibweise ist das

N_{f} (x) - \sqrt{a} = x - \frac{f (x)}{f ʹ (x)} - \sqrt{a} = \frac{1}{f ʹ (x)} (x - \sqrt{a})^{2}

.

Das kann betragsmäßig abgeschätzt werden durch

∣ N_{f} (x) - \sqrt{a} ∣ \leq \frac{1}{m_{1}} \cdot ∣ x - \sqrt{a} ∣^{2}

mit

m_{1} = \binom{min}{x \in I} ∣ f ʹ (x) ∣

.

Sei

K = \frac{1}{m_{1}}

.

Dann schreibt sich das als

∣ x_{n} - \sqrt{a} ∣ \leq K \cdot ∣ x_{n - 1} - \sqrt{a} ∣^{2}

Sei

d_{n}

die Größe

d_{n} = K \cdot ∣ x_{n} - \sqrt{a} ∣

.

Dann ist

d_{n} \leq K \cdot K \cdot ∣ x_{n - 1} - \sqrt{a} ∣^{2} = d_{n - 1}^{2}

.

Vollständige Induktion nach n zeigt, dass

K \cdot ∣ x_{n} - \sqrt{a} ∣ = d_{n} \leq d_{n - 1}^{2} \leq d_{n - 2}^{4} \leq \dots \leq d_{0}^{2^{n}} = (K \cdot ∣ x_{0} - \sqrt{a} ∣)^{2^{n}}

.

Wenn jetzt

x_{0}

nahe genug bei

\sqrt{a}

liegt (

∣ x_{0} - \sqrt{a} ∣ < \frac{1}{K}

), dann konvergiert

N_{f} (x_{n})

gegen

\sqrt{a}

.

Ist das richtig so weit?

Anmerkung : Sehr interessant ist auch das Newtonverfahren zu

z^{3} - 1

im Komplexen.

mathadvisor aktiv_icon

18:07 Uhr, 21.09.2025

Den einfacheren Weg willst Du anscheinend nicht (siehe oben), der ginge ohne Taylor und ohne Ableitungen und Du wärst sehr schnell bei der Abschätzung.
Wie Du willst. Aber dann musst Du

m_{1}

und

K

konkret (für Dein Beispiel) angeben, und nicht allgemein argumentieren. Und am Ende solltest ein Kriterium für den Startwert angeben.

Sukomaki aktiv_icon

18:51 Uhr, 21.09.2025

Mit

I = [\sqrt{a} - δ, \sqrt{a} + δ]

ist

m_{1} = 2 \cdot (\sqrt{a} - δ)

wobei

δ < \sqrt{a}

.

Den einfacheren Weg will ich, aber er entzieht sich meinem Blickfeld.

Ich will ja nur zeigen, dass

lim_{n \to \infty} a_{n} = \sqrt{a}

.

Lass mich doch wissen, welcher Ansatz Dir vorschwebt ohne Taylor und Ableitungen.

Und jetzt schreibe bitte etwas anderes als "(siehe oben)"!

Da werde ich nämlich nicht so recht schlau draus. :-D)

mathadvisor aktiv_icon

18:58 Uhr, 21.09.2025

Ich wiederhole:
"Du kannst so anfangen wie im Wikipedia-Beispiel (aber genau schauen, was dort steht), und für den Rest des Beweises wie im allgemeinen Fall vorgehen."
und dann sagte ich nochmal:
" Gehe vor wie eben erklärt (also erst wie im Beispiel),"

Wenn Du dem Beispiel folgst, landest Du schnell bei der Abschätzung. Damit dann weiter wie im allgemeinen Beweis.
Und auch nochmal: "Aber dann musst Du m1 und K konkret (für Dein Beispiel) angeben."
Heißt, da dürfen nur Größen aus Deiner Aufgabe drin vorkommen (also nur

a

).

Bitte diesmal die Hinweise komplett(!) lesen und ggf. nachfragen.

Sukomaki aktiv_icon

19:14 Uhr, 21.09.2025

Vielleicht reden wir ja aneinander vorbei.

Es wäre nett, wenn Du mir verraten könntest, welchem Beispiel genau ich folgen muss.

Meinst Du

f (x) = 1 - \frac{a}{x^{2}}

mit

N_{f} (x) = x_{n} - \frac{1 - \frac{a}{x_{n}^{2}}}{2 \frac{a}{x_{n}^{3}}} = \frac{x_{n}}{2} (3 - \frac{x_{n}^{2}}{a})

mathadvisor aktiv_icon

21:41 Uhr, 21.09.2025

Du hast von "Auf de.wikipedia.org/wiki/Newtonverfahren#Erstes_Beispiel wird nämlich so vorgegangen." geredet, und darauf hab ich mich ja direkt bezogen.
Im Beispiel wird ein Zusammenhang zwischen

x_{n + 1} - a

und

x_{n} - a

hergeleitet, das lässt sich auf Deine Situation leicht übertragen. Danach abschätzen und dann geht es weiter wie im Beweis (mit der Induktionsidee usw.).
Davon mal abgesehen, wird ja sicher in der zugehörigen Vorlesung was gesagt/erklärt worden sein. Damit sollte man stets zuerst versuchen zu arbeiten.

Sukomaki aktiv_icon

12:05 Uhr, 22.09.2025

Ach, weisst Du. Die zugehörige Vorlesung ist 28 Jahre her.

Soll heissen, wenn dort oder im Tutorium etwas dazu gesagt worden ist, weiss ich es nicht mehr.

Kannst Du

(\frac{3}{2} x_{n} - \frac{x_{n}^{3}}{2 a} - \frac{3}{2} \sqrt{a} + \frac{{\sqrt{a}}^{3}}{2 a}) : (x_{n} - \sqrt{a}) = \frac{3}{2} - \frac{x_{n}^{2} + x_{n} \sqrt{a} + a}{2 a}

im Kopf ausrechnen?

Ich habe dafür eine Polynomdivision gebraucht.

Nun aber zum eigentlichen Anliegen.

Es ist

f (x) = x^{2} - a

und

N_{f} (x) = \frac{1}{2} (x + \frac{a}{x})

Dann ist

x_{n + 1} - \sqrt{a} = \frac{1}{2} (x_{n} + \frac{a}{x_{n}}) - \frac{1}{2} (\sqrt{a} + \frac{a}{\sqrt{a}})

(das kann ich so machen, da

N_{f} (\sqrt{a}) = \sqrt{a}

)

Das ist gleich

\frac{1}{2} (x_{n} - \sqrt{a}) + \frac{1}{2} (\frac{a}{x_{n}} - \frac{a}{\sqrt{a}})

Hier sehe ich keine Chance,

(x_{n} - \sqrt{a})

auszuklammern.

Aber das ist doch nötig, um auf die Abschätzung zu kommen.

mathadvisor aktiv_icon

12:25 Uhr, 22.09.2025

Du findest wieder einen Weg es kompliziert zu machen.

x_{n + 1} - \sqrt{a} = ½ (x_{n} + \frac{a}{x_{n}}) - \sqrt{a} = . . .

Warum Du

\sqrt{a}

durch etwas komplizierteres ersetzen willst, weiß ich nicht. Man probiert doch erstmal den einfachen Weg.
Auch die Schreibweisen mit

N_{f}

brauchst Du nicht.

HAL9000

13:58 Uhr, 22.09.2025

Eine Anmerkung am Rande:

Es unnötig sich an dem Fall

x_{0} < \sqrt{a}

unnötig lang aufzuhalten, denn für jedes

x_{0} > 0

ist garantiert

x_{n} > 0

für alle

n

, und damit dann

x_{n} = \frac{1}{2 x_{n - 1}} {(x_{n - 1} - \sqrt{a})}^{2} + \sqrt{a} \geq \sqrt{a}

für alle

n \geq 1

, also diskutiert man Aspekte wie Monotonie u.a. eben erst ab Index 1, und entledigt sich so dieses Problems. ;-)

Mit obiger Darstellung bekommt man übrigens dann auch gleich

0 \leq x_{n} - \sqrt{a} = \frac{x_{n - 1} - \sqrt{a}}{2 x_{n - 1}} (x_{n - 1} - \sqrt{a}) \leq \frac{1}{2} (x_{n - 1} - \sqrt{a})

für alle

n \geq 2

,

woraus unmittelbar

0 \leq x_{n} - \sqrt{a} \leq \frac{1}{2^{n - 1}} (x_{1} - \sqrt{a})

folgt, was die Konvergenz dann ja per Sandwich erledigt.

Sukomaki aktiv_icon

19:32 Uhr, 22.09.2025

Das sieht gut aus. Danke sehr.

Respekt mal wieder, das flutscht nur so.

So etwas in der Art habe ich gesucht.

1591687

1591668

	Status: nicht eingeloggt	Noch nicht registriert?