ガウス＝ルジャンドルのアルゴリズム

ガウス＝ルジャンドルのアルゴリズム

ガウス＝ルジャンドルのアルゴリズムは、円周率を計算するための洗練された反復計算手法です。このアルゴリズムは、カール・フリードリヒ・ガウスとアドリアン＝マリ・ルジャンドルの研究に基づいており、特にその収束の速さが評価されています。

特徴と利点

このアルゴリズムは、2009年に約2兆6000億桁（2,576,980,370,000桁）の円周率を計算するために実際に用いられました。とりわけ、円周率の精度を求める際の収束の速さは、他のアルゴリズムと比較しても顕著です。具体的には、希望する桁数に到達するために必要な反復回数が相対的に少なくて済みます。

アルゴリズムの概要

円周率を求める手順は、まず初期値を設定します。以下のような値が用意されます：

• - $a_0 = 1$
• - $b_0 = rac{1}{ an(1)}$
• - $t_0 = rac{1}{4}$
• - $p_0 = 1$

この初期値をもとに、次の反復式に従い計算を行います：
1. $a_{n+1} = rac{a_n + b_n}{2}$
2. $b_{n+1} = rac{2a_n b_n}{a_n + b_n}$
3. $t_{n+1} = t_n - p_n (a_n - a_{n+1})^2$
4. $p_{n+1} = 2p_n$

この計算を、求めたい桁数に達するまで繰り返します。たとえば、小数第$n$位までの精度を保つためには、件数として$O( ext{log} 2 n)$回程度の反復で十分です。

円周率の近似

ガウス＝ルジャンドルのアルゴリズムを利用して計算した円周率$oldsymbol{ ext{π}}$の近似式は次のように表されます：
$$ ext{π} ext{≈} rac{(a + b)^2}{4t}$$

この式から、反復計算によって得られる変数の値を用いて円周率を求めることが可能です。初回の反復から数回の計算を行った結果、初歩的な値から次第に正確な値に近づく様子が見て取れます。

1. 1回目の計算結果: $3.140...$ (小数第2位まで正しい)
2. 2回目の計算結果: $3.14159264...$ (小数第7位まで正しい)
3. 3回目の計算結果: $3.1415926535897932382...$ (小数第18位まで正しい)

このようにして、収束の速さが非常に優れていることが実証されます。ガウス自身もこの手法を用いて、数回の反復によって12桁までの正しさを確認しています。

実装例

ガウス＝ルジャンドルのアルゴリズムはPythonなどのプログラミング言語で実装可能です。その例は非常に多く、数多くの応用があります。

数学的背景

このアルゴリズムに関する数学的な基盤には、算術幾何平均やルジャンドルの恒等式が存在します。算術幾何平均は二つの数の平均を計算する手法であり、ガウス＝ルジャンドルアルゴリズムにおいては非常に重要な役割を果たします。さらに、ルジャンドル恒等式もこのアルゴリズムの理論的背景とされています。

結論

ガウス＝ルジャンドルのアルゴリズムは、円周率の計算において非常に効果的で、利用しやすい手法です。その収束の速さや広範な応用性により、数学界だけでなく多くの実用分野でも重宝されています。

もう一度検索