Konvergenzbetrachtungen zum Heron-Verfahren

Sei q>0q>0 eine reelle Zahl, deren Quadratzahl wir mittels Heron-Verfahren bestimmen wollen. Bei der Analyse der Konvergenz beschränken wir uns auf den Fall eines positiven Startwertes x0>0x_0>0.
Ist x0<qx_0<\sqrt q, so lässt sich zeigen, dass x1>qx_1>\sqrt q. Außerdem werden wir sehen, dass die Iterationsfolge für n>1n>1 eine monoton fallende Folge mit der unteren Schranke q\sqrt q ist, damit konvergiert sie nach Satz 5225A.

Satz C7VC (Eigenschaften der Heronfolge)

Für n>=1n>=1 gilt
qxn+1xn \sqrt{q} \le x_{n+1} \le x_n,
Außerdem gilt x1>qx_1>\sqrt q falls x0<qx_0<\sqrt q.

Beweis

Bevor wir die eigentliche Ungleichung mittels vollständiger Induktion beweisen, zeigen wir einige Hilfsungleichungen.
i) Sei x0<qx_0<\sqrt q, dann gibt es ein d>0d>0 mit x0=qdx_0=\sqrt q -d. Also d2>0d^2>0     q>qd2\implies q>q-d^2     q>(qd)(q+d)\implies q>(\sqrt q-d)(\sqrt q+d)     qqd>q+d\implies \dfrac q{\sqrt q-d}>\sqrt q+d     d+qqd>q\implies -d+\dfrac q{\sqrt q-d}>\sqrt q     qd+qqd>2q\implies \sqrt q -d+\dfrac q{\sqrt q-d}>2\sqrt q     12(qd+qqd)>q\implies\dfrac 1 2\left( \sqrt q -d+\dfrac q{\sqrt q-d}\right)>\sqrt q     x1>q\implies x_1>\sqrt q.
ii) Wir zeigen nun q<=xn\sqrt q<=x_n für n>=1n>=1 mittels vollständiger Induktion. Nach i) gilt x1>=qx_1>=\sqrt q. Sei nun xn>qx_n>\sqrt q     xnq>=0\implies x_n-\sqrt q>=0     (xnq)2>=0\implies (x_n-\sqrt q)^2>=0     xn22qxn+q>=0\implies x_n^2-2\sqrt q x_n+q>=0     xn2+q>=2qxn\implies x_n^2+q>=2\sqrt q x_n     xn+qxn>=2q\implies x_n+\dfrac q {x_n}>=2\sqrt q     12(xn+qxn)>=q\implies \dfrac 1 2\left(x_n+\dfrac q {x_n}\right)>=\sqrt q     xn+1>=q\implies x_{n+1} >=\sqrt q. iii) Nach ii) gilt für n>=1n>=1: q<=xn\sqrt q<=x_n     q<=xn2\implies q<=x_n^2     qxn<=xn\implies \dfrac q{x_n}<=x_n     xn+qxn<=2xn\implies x_n+ \dfrac q{x_n}<=2x_n     12(xn+qxn)<=xn\implies \dfrac 1 2\left( x_n+ \dfrac q{x_n}\right)<=x_n     xn+1<=xn\implies x_{n+1}<=x_n. \qed

Satz (Quadratische Konvergenz der Heronfolge)

Für x0>0x_0>0 konvergiert die Heronfolge xn+1=12(xn+qxn)x_n+1=\dfrac 1 2\left(x_n+\dfrac q {x_n}\right) quadratisch gegen die Wurzel q\sqrt q.

Beweis

Es gilt xn+1q=12(xn+qxn)qx_{n+1}-\sqrt q=\dfrac 1 2\left(x_n+\dfrac q {x_n}\right)-\sqrt q =12xn(xn2+q2xnq)=\dfrac 1 {2x_n}(x_n^2+q-2x_n\sqrt q) =12xn(xnq)2=\dfrac 1 {2x_n}(x_n-\sqrt q)^2. Nach Satz C7VC ist xn<=x1x_n<=x_1 für n>=1n>=1, also auch xn+1q<=12xn(x1q)2=(x1q)221xnx_{n+1}-\sqrt q<=\dfrac 1 {2x_n}(x_1-\sqrt q)^2=\dfrac{(x_1-\sqrt q)^2} 2\cdot \dfrac 1 {x_n}. Die rechte Seite ist eine Nullfolge und daher ist auch xn+1qx_{n+1}-\sqrt q eine Nullfolge (Satz 5225D), womit xnqx_n\to\sqrt q gezeigt wurde.
Aus xn+1q=12xn(xnq)2x_{n+1}-\sqrt q=\dfrac 1 {2x_n}(x_n-\sqrt q)^2 können wir wegen xn>=qx_n>=\sqrt q auch xn+1q12q(xnq)2x_{n+1}-\sqrt q\le \dfrac 1 {2\sqrt q }(x_n-\sqrt q)^2 ableiten, womit die quadratische Konvergenz gezeigt ist. \qed
 
 

Hochtechnologie ist im wesentlichen mathematische Technologie.

Enquete-Kommission der Amerikanischen Akademie der Wissenschaften

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе