Hintergrundwissen
Antiker Algorithmus für Wurzel 2
Einleitung
Der folgende Algorithmus war bereits in der gr. Antike bekannt, und wird vom gr. Theon von Smyrna (ca 140 AD) erwähnt [MathWorld]. Vermutlich ist er sogar noch älter [BRESSOUD].
Algorithmus
Wir definieren zwei Folgen (an)nεIN, (bn)nεIN durch a0 = b0 = 1 und
an+1 = an + 2*bn
bn+1 = an + bn
Dann gilt:
an / bn konvergiert gegen √2
Approximation von √2
| n | an | bn | |√2 - an/bn| |
| 0 | 1/1 | 1 | 0.4... |
| 1 | 3/2 | 1,5 | 0,08... |
| 2 | 7/5 | 1,4 | 0,01... |
| 3 | 17/12 | 1,416... | 0,002... |
| 4 | 41/29 | 1,4137... | 0,0004... |
| 5 | 99/70 | 1,41428... | 0,00007... |
Approximationsfehler
Der Approximationsfehler kann abgeschätzt werden durch
|√2 - an/bn| < 1/2b2
Erläuterung 1
Geht man von der Kettenbruchentwicklung von Wurzel 2 = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...] aus, so erkennt man, dass der Algorithmus von Smyrna genau die Näherungsbrüche der Kettenbruchentwicklung von Wurzel 2 datstellt.
Erläuterung 2
(1) Der Algorithmus liefert alle Lösungen der Pellschen Gleichung:
a2 - 2b2 = +-1 (**)
Offensichtlich ist (a,b)=(1,1) eine Lösung von (**). Sei nun (a,b) eine beliebige Lösung, dann ist auch (a+2b,a+b) eine Lösung, denn (a+2b)2-2(a+b)2 = -(a2 - 2b2) = +-1.
(2) Jede Lösung von (**) ist eine Approximation für Wurzel 2, denn
a2 - 2b2 = +1 => a/b = sqrt(2 +- 1/b2)