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
q≤xn+1≤xn \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=q−dx_0=\sqrt q -d. Also d2>0d^2>0   ⟹  q>q−d2\implies q>q-d^2   ⟹  q>(q−d)(q+d)\implies q>(\sqrt q-d)(\sqrt q+d)   ⟹  qq−d>q+d\implies \dfrac q{\sqrt q-d}>\sqrt q+d   ⟹  −d+qq−d>q\implies -d+\dfrac q{\sqrt q-d}>\sqrt q   ⟹  q−d+qq−d>2q\implies \sqrt q -d+\dfrac q{\sqrt q-d}>2\sqrt q   ⟹  12(q−d+qq−d)>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   ⟹  xn−q>=0\implies x_n-\sqrt q>=0   ⟹  (xn−q)2>=0\implies (x_n-\sqrt q)^2>=0   ⟹  xn2−2qxn+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+1−q=12(xn+qxn)−qx_{n+1}-\sqrt q=\dfrac 1 2\left(x_n+\dfrac q {x_n}\right)-\sqrt q =12xn(xn2+q−2xnq)=\dfrac 1 {2x_n}(x_n^2+q-2x_n\sqrt q) =12xn(xn−q)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+1−q<=12xn(x1−q)2=(x1−q)22⋅1xnx_{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+1−qx_{n+1}-\sqrt q eine Nullfolge (Satz 5225D), womit xn→qx_n\to\sqrt q gezeigt wurde.
Aus xn+1−q=12xn(xn−q)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+1−q≤12q(xn−q)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е
Datenschutzerklärung

 

Wurzeln