Heron- vs. Newtonverfahren: Unterschiede und Konvergenzeigenschaft

Question

in der Kodierungsvorlesung haben wir den Begriff des Algorithmus behandelt. Dabei haben wir Aspekte wie "terminierend" und "deterministisch" besprochen. Als Beispiel für einen Algorithmus wurde das Heron-Verfahren vorgestellt. Bei der Berechnung des nächsten Ausgangswertes kam mir daheim nun das Newton-Verfahren in den Sinn, welches ähnlich aussieht.

Frage 1:

Worin liegt bitte der Unterschied zwischen Heron- und Newtonverfahren? Mein Skript ist in dieser Hinsicht leider verwirrend, weil die beiden Begriffe abwechselnd vorkommen.

Frage 2:

Im Skript steht: "Wir wollen noch anmerken, dass das Newton-Verfahren deterministisch und terminierend ist. Letzteres geht aus der Konvergenzeigenschaft des Newton-Verfahrens hervor."

Wieder beide Verfahren in einem Satz. Doch wieso der zweite Satz? Ist es bitte nicht so, dass es Situationen gibt, in denen die Folge aus den berechneten x's nicht gegen einen bestimmten Wert konvergiert? Für mich wäre es schlüssiger, wenn der Aspekt des Terminierens daraus folgen würde, dass man beim Heron-Verfahren ja eine obere Limite für den Schätzfehler wählen muss und dies folglich das Abbruchkriterium darstellt.

Worin liegt bitte mein Überlegungsfehler?

Answer 1

Worin liegt bitte der Unterschied zwischen Heron- und Newtonverfahren? Mein Skript ist in dieser Hinsicht leider verwirrend, weil die beiden Begriffe abwechselnd vorkommen.

Das eine ist ein Spezialfall des anderen.

Heronverfahren ist zur Berechnung von Quadratwurzeln , also etwa so:
Wenn du Wurzel aus g haben willst, beginnst du mit einem Startwert  x1 und berechnest
den nächsten Näherungswert durch

x2 =   0,5 * ( x2 + g / x1 ) und diese Folge von Näherungswerten konvergiert gegen wurzel(g).

Mit dem Newtonverfahren ist es genau so. Wenn du damit wurzel(g) annähern willst,
suchst du also eine Nullstelle der Funktion mit f(x) = x^2 - g

Dann geht das nach Newton so:

x2 = x1 -  f  (x1) / f ' (x1)
     = x1  -  ( x1^2 - g ) /  (2x1 )
    =  x1  -   0,5x1  -   g / ( 2x1 )
   = 0,5x1  -  g / (2x1)
   = 0,5 * ( x1  -  g/x1 )     also genau das Gleiche wie bei Heron.

Comments

danke für Deine Antwort. Würdest Du mir bezüglich des Terminierens zu stimmen, das dies auf die zu wählende Limite zurückzuführen ist?