円周率.jp (http://xn--w6q13e505b.jp/formula/agm.html)

AGM系

平均

$n$ 個の数値 $\{a_n\}$ の平均を取る場合, その計算方法は何種類もあるが,代表的なものとして次の 3 種類の平均の取り方を挙げる.

表 1: 3 種類の平均
相加平均(算術平均) 相乗平均(幾何平均) 調和平均
\[ M_A = \frac{1}{n}\sum_{k=1}^na_k \] \[ M_G = \left(\prod_{k=1}^n a_k \right)^{1/n} \] \[ M_H = \left(\frac{1}{n} \sum_{k=1}^n \frac{1}{a_k} \right)^{-1} \]

2 数 $a$,$b$ に対して算術平均 (Arithmetic mean) と幾何平均 (Geometric mean) を繰り返し取ると共通の値に行きつく. この値を算術幾何平均 (AGM ; Arithmetic Geometric Mean) といい, $M(a, b)$ で表す.

Gauß-Legendre の公式

数式表現

\[ a_0 = 1,\ b_0 = \frac{1}{\sqrt{2}} \] \[ a_{k+1} = \frac{1}{2} (a_k + b_k),\ b_{k+1} = \sqrt{a_kb_k} \]

のとき,

\[ \pi = \frac{2 M(a_0, b_0)}{1-\sum_{k=0}^{\infty}2^k(a_k^2-b_k^2)} \]

アルゴリズム表現

計算機で計算を行う場合,数式で表現されたままの計算を行うのは難しい.

1 つ 1 つの値が求めようとする $d$ 桁分の値を保持しなければならないため, メモリや HDD といった記憶装置の使用領域を抑えるためには, 同じ領域を使いまわさなければならない. また,繰り返しを無限に行うことはできないので適切な回数処理を 繰り返したら処理を終えなければならない. そのための実現アルゴリズムとして以下のようなものがある. また,[JW06] ではより演算量を落としたアルゴリズムが提案されている.

  • $A=1$
  • $B=\dfrac{1}{\sqrt{2}}$
  • $T=\dfrac{1}{4}$
  • $X=1$
  • while $|A-B|\gt10^{-d}$ do
    • $Y=A$
    • $A=\frac{1}{2}$(A+B)$
    • $B=\sqrt{BY}$
    • $T=T-X(Y-A)^2$
    • $X=2X$
  • end of while
  • $\pi = \dfrac{(A+B)^2}{4T}$