Prev    Up    Next  

5.1 Der AGM-Algorithmus

Der Algorithmus des Arithmetisch-Geometrischen Mittelwertes (AGM) stellt eine effiziente Möglichkeit zur numerischen Berechnung des elliptischen Integrals erster Art dar [Cay76, XIII], [Tri48, IV, § 7], [Hur00, II-7, § 6].54 Er ist eine konsequente Anwendung der GAUSS-Transformation von Abschnitt 4.7.2 auf die elliptische Differentialgleichung 70 wiefolgt:55

-1--⋅∘----dθ------=  ∘----dφ-----.
1+ k   1 − λ2sin2θ      1− k2sin2φ
(158)

Aus der LEGENDRE-Form der elliptischen Differentialgleichung 70 kann man natürlich auch eine entsprechende GAUSS’sche Form ableiten. Dazu sollen zuerst die Darstellungsformen von Formel 9, 6, 7 und 8 rekapituliert und auf die Ausdrücke der linken und rechten Seite von Gleichung 158 angewandt werden.

pict

Mit dieser Indizierung schreibt sich Differentialgleichung 70 in der GAUSS-Form

       dt                  dt
∘--------1------- = ∘-------0--------.
  (t21 + a21)(t21 + b21)   (t20 +a20)(t02+ b20)
(159)

Bevor diese wichtige Relation nun bewiesen wird, sollen die Beziehungen zwischen den Modulen k und λ auf der Basis von aν  und bν  dargestellt werden.

   1-−-λ′  a0-−-b0
k= 1 + λ′ = a0 + b0
(160)

Ersetzt man auch auf der linken Seite noch das Modul, so ergibt sich folgende Gleichung.

pict

Nach Erweiterung der rechten Seite wiefolgt

 2   2            2
a1-− b1 = 4(a0−-b0)
  a21     4(a0+ b0)2

kann man (durch Vergleich von Zähler und Nenner) die Basisbeziehungen des AGM ableiten.

pict

Mit diesen Voraussetzungen ist ein Beweis von Differentialgleichung 159 einfach zu erbringen.

Beweis. Dazu geht man von der LEGENDRE’schen Form in Differentialgleichung 158 aus.

pict

Der “Multiplikator” a0∕(1+ k)  in dieser Darstellung ist nun aber genau Eins, was Anwendung von Formel 161 schnell zeigt (wenn man außerdem das Modul k durch λ′ ersetzt).

pict
__

Was nun die Beziehung zwischen t0  und t1  angeht, so ist sie ja durch die trigonometrische Beziehung 119 der GAUSS-Transformation festgelegt.

pict

Zurück zum eigentlichen Algorithmus läßt sich nun die folgende Iteration durchführen,

      ai+-bi          ∘  ----
ai+1 =   2  ,    bi+1 =   aibi
(164)

wobei die Anfangswerte a0  und b0  nicht-negative Zahlen (mit a0 > b0  ) sein sollen. Dabei nähern sich für i→  ∞ beide Werte a
 i  und b
 i  einem gemeinsamen Grenzwert,56 dem sogenannten AGM [Tod84].

M (a ,b) = lim a = lim b
    0  0   i→ ∞ i  i→∞  i
(165)

Um diesen Grenzwert zu finden, bildet man zuerst das unbestimmte elliptische Integral

∫
  ∞ -------dti-------
 −∞ ∘ --2---2--2---2-
      (ti + ai)(ti + bi)
(166)

und kombiniert es mit Relation 159.

∫ ∞                     ∫ ∞
    ∘------dti-------=     ∘---------dti+1---------.
 − ∞  (t2+ a2)(t2+ b2)    −∞  (t2  +a2  )(t2  + b2 )
        i   i  i   i           i+1    i+1  i+1   i+1
(167)

Die Beziehung zwischen den Integrationsgrenzen ist durch Gleichung 163 gegeben, d. h. wenn das Integrationsintervall auf der linken Seite von − ∞ nach + ∞ läuft, dann geschieht dasselbe auch auf der rechten Seite der Integralgleichung.

Nimmt man das rechtsseitige Integral als Ausgangspunkt für den nächsten Iterationsschritt,57 so kann man unter Berücksichtigung von Formel 165 auch schreiben:

pict

Bedenkt man weiterhin, daß der Integrand in Gleichung 166 eine gerade Funktion ist, kann folgende Integraldarstellung für M (a0,b0)  gegeben werden:

M (a0,b0) = ∫---------π-----------.
             ∞ ∘-------dt--------
            −∞   (t2 + a2) (t2+ b2)
                       0      0
(168)