Numerisches Wurzelziehen

Neue Frage »

plizzz Auf diesen Beitrag antworten »
Numerisches Wurzelziehen
Hallo,

ich habe folgende Aufgabe vor mir: Ich habe eine positive rationale Zahl a und eine natürlich Zahl p. Ich soll jetzt zeigen, dass die Wurzel von a auf p Nachkommastellen genau in O(log(p)+log(a+1)) berechnet werden kann.


Ich möchte hierzu das Heron-Verfahren nehmen und denke, dass das der richtige Ansatz ist. Aus Analysis weiß ich (es ist auch nicht allzu schwer einzusehen), dass für den Fehler in der n+1-ten Iteration gilt:



Ab dem Zeitpunkt, wo der Fehler kleiner als Wurzel von a ist, halbiert sich der Fehlerterm immer mindestens und ab da gilt die Aussage. Mein Problem ist nur, zu zeigen, dass ich bei irgendeinem Startwert hinreichend schnell in diesen Bereich komme und an dieser Stelle komme ich echt nicht weiter.

Jemand eine Idee, wie der Startwert gewählt werden muss und wie man dann zeigt, dass das Verfahren hinreichend schnell konvergiert?

Vielen Dank und freundlichen Grüße,

plizzz
plizzz Auf diesen Beitrag antworten »

Hat sich erledigt. Eine bessere Fehlerabschätzung liefert das Ergebnis.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »