■因数分解の算法(その16)

 (その14)ではムーアヘッド平均を扱ったが,ムーアヘッド平均は算術平均と幾何平均の一般化になっていた.たとえば,算術平均・幾何平均の不等式

  (a^2+b^2)/2≧ab

の左辺も右辺も

  (a^xb^y+a^yb^x)/2

の特別な場合になっていることに気づかれたであろう.

 x≧y≧0として(x,y)を指標と呼ぶことにするが,左辺は指標(x,y)=(2,0),右辺は指標(x,y)=(1,1)である.また,いずれにおいてもx+y=2という条件が満たされている.

 不等式

  (a^2+b^2)/2≧ab

  M(2,0)≧M(1,1)

と書くことにするが,M(x,y)をムーアヘッド平均と呼ぶことにする.ムーアヘッド平均は算術平均と幾何平均の一般化である.

 ベキ平均を

  Mr=((a^r+b^r)/2)^(1/r)

と定義すると,

  M1=(a+b)/2 → 算術平均A

  M-1=2/(1/x+1/y)=2xy/(x+y) → 調和平均H

  M2=((a^2+b^2)/2)^(1/2) → ユークリッド平均E

となる.

 ベキ平均では(ab)^(1/2) → 幾何平均Gを定義できないという不便さがあるが,これも平均の重要な一般化である(H<G<A<E).今回のコラムでは,平均の応用として算術幾何平均を取り扱うことにする.

===================================

【1】算術幾何平均

 aがx^2=0の解ならばa=2/aが成り立ちます.aがいくらか不正確,たとえば過小評価であるならば,2/aは過大評価となります.過小評価と過大評価の中間(算術平均)はaと2/aのいずれよりもよい評価となります.

 かくして算術平均:

  an+1=1/2(an+2/an)

によって定義される数列は√(2)に収束することになります.この場合,2の平方根をニュートン法x:=x-f(x)/f'(x)で求めるのと同じことになります.ニュートン法の幾何学的意味は「初期値x0における関数の勾配を求めて,接線とx軸の交点を求める.この点において,同様の作業を行うとxは順次解に近づいていく.」と解釈されます.

 次に,算術平均に加えて,幾何平均も考えることにします.

「2数a0,b0をとり,それらの算術平均a1=(a0+b0)/2,幾何平均b1=√a0b0を計算する.次に,a1,b1の算術平均と幾何平均を計算し,a2=(a1+b1)/2,b2=√a1b1とする.すると,anとbnは急速に同じ極限M(a,b)に到達する.」

(証明)

a0>b0とする.

a1=(a0+b0)/2<(a0+a0)/2=a0

b1=√a0b0>√b0b0=b0

a1−b1=(a0+b0)/2−√a0b0=1/2(√a0−√b0)>0

帰納的に

a0>・・・>an >an+1>bn+1>bn >・・・>b0

より数列{an},{bn}は単調数列となり,同じ値に収束することがわかる.

 このように,1組の数(a,b)に対して,算術および幾何平均を考えて,

  (a,b):=((a+b)/2,√(ab))

と繰り返す算法を算術幾何平均法と呼びます.

===================================

【2】一般化

  xn=f(xn-1,yn-1)

  yn=g(xn-1,yn-1)

を繰り返すとき,数列xn,ynが同じ極限M(x,y)に収束し,極限関数M(x,y)が具体的に定められるのはどのような場合でしょうか?

[1]収束性

 答えを先にいうと,f,gが比較可能な平均という性質をもつとき,同じ値に収束することが証明されます.

(1)平均の定義

  x<yならば、x<f(x,y)<y

  λ>0ならば,f(λx,λy)=λf(x,y)

(2)比較可能関数の定義

  2つの関数の間に不等式f(x,y)≦g(x,y)が成り立つ.

この意味でH,G,A,Eは平均の条件を満たし,不等式H<G<A<Eが成り立ちます.

[2]極限関数

 極限関数M(x,y)は初期値(x0,y0)の如何に関わらず,

  M(x,y)=M(x0,y0)

したがって

  M(x,y)=M(f(x,y),g(x,y))

を満たします(不変性).

(例1)f=2xy/(x+y)=H,f=(x+y)/2=A

とおくと,x0y0=x1y2=・・・という不変性を示す.この極限関数は

  M(x,y)=(xy)^(1/2)=G

に急速に収束する.→算術調和平均

(例2)f=G,g=Aならば極限M(a,b)は楕円積分

  M(a,b)=1/(2/π∫(0,π/2)dφ/√{(acosφ)^2+(bsinφ)^2})

により表すことができる(ガウス).→算術幾何平均

 ラグランジュ,ガウス,ルジャンドルは18世紀に算術幾何平均を熟知していたようです.ガウス・ルジャンドルの算術幾何平均法では,反復のたびに有効数字は2倍になりますから,数値計算アルゴリズムの強力な武器となりえます.

 楕円積分の二重周期は算術幾何平均法を使って計算されます.実際,東京大学の金田康正氏のグループは楕円積分の計算と関係した算術幾何平均法を用いて円周率πの計算の世界記録を樹立しました.その計算量はO(nlogn)となり,計算能率はarctan(x)の展開公式O(n^2)よりも格段に優れています.円周率πの計算や巨大な素数の発見はコンピュータシステムの信頼性や処理速度といった性能をテストするのに最適ということです.

===================================

【3】バリエーション

(1)2数a0,b0をとり,a1=(a0+b0)/2,b1=√a1b0=√b0(a0+b0)/2を計算する.次に,a2=(a1+b1)/2,b2=√a2b1とする.bnを計算するときan-1でなく最新のanを使っていることに注意されたい.

 すると,anとbnは急速に同じ極限M(a,b)に到達する.このとき,極限関数はM(a,b)=

(b^2−a^2)^(1/2)/arccos(a/b)    (0≦a<bのとき)

a                         (a=bのとき)

(a^2−b^2)^(1/2)/arccosh(a/b)   (b<aのとき)

で与えられる(パッフ).

(2)0≦a0<b0なる2数a0,b0をとり,a1={a0(a0+b0)/2}^(1/2),b1={b0(a0+b0)/2}^(1/2)を計算する.これを繰り返すとanとbnは急速に同じ極限M(a,b)に到達する(カールソン).

  M(a,b)={(b^2−a^2)/2log(a/b)}^(1/2)

===================================