FANDOM


算術幾何平均(Arithmetic-geometric mean,AGM)公式(ガウス=ルジャンドルの公式)

M(a,b)をaとbの算術幾何平均とし、

$ a_1 = 1 , b_1 = \frac{1}{\sqrt2} , a_{k+1} = \frac{a_k+b_k}{2} , b_{k+1} = \sqrt{a_k b_k} $

とすると、

$ \pi = \frac{M(a_1,b_1)}{1-\sum_{k=1}^\infty (a_k^2-b_k^2)} $

である。

$ \pi_n=\frac{2a_{n+1}^2}{1-\sum_{k=0}^n2^k(a_k^2-b_k^2)} $

とすると、このアルゴリズムの精度は

$ \pi-\pi_n\leq\frac{\pi^22^{n+4}e^{-2^{n+1}\pi}}{a_\infty^2} $,もしくは$ \pi-\pi_n\leq\frac{1}{2^{n+1}\pi^2}(\pi-\pi_n)^2 $

これを見てわかるとおり、このアルゴリズムは二次収束である。実際には

$ t_1 = \frac{1}{4}, t_{n+1} = t_n - 2^{n-2}(a_n - b_n)^2 $

として

$ \pi \approx \frac{(a_n+b_n)^2}{4t_n} $

という形で計算される。また、さらに変形を行い、

$ \begin{align} &a_1=\frac{2+\sqrt{2}}{4},b_1=2^{-\frac{1}{4}},t_1 = \frac{\sqrt{2}-1}{8} \\ &a_{n+1}=\frac{a_n+b_n}{2},y=(a_{n+1}-b_n)^2,t_{n+1}=t_n-2^ny,b_{n+1}=\sqrt{a_{n+1}^2-y} \end{align} $

$ \pi \approx \frac{(a_n+b_n)^2}{4t_n} $

という形で計算することもできる。

漸化式に根号が含まれたこの式は計算に向かないと思うかもしれないが、先に示したとおり二次収束する。そのため、円周率の計算に使われることもある。 このアルゴリズムの発見者のひとりであるガウス自身、このアルゴリズムを4回反復し、円周率12桁の近似を得たと言われている。

ちなみに、$ M(0,\frac{1}{4})=\frac{1}{2\pi} $(ニコラウス・クザーヌスの公式)が15世紀には知られていた。

また、

$ a_0 = 2\sqrt{3} , b_0 = 3 , \frac{1}{a_{k+1}} = \frac{1}{a_k} + \frac{1}{b_k}, b_{k+1} = \sqrt{a_k b_k} $

とすると、

$ \pi = \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n $(アルキメデスの公式)

これは3と2√3の調和幾何平均に等しい。

Borwein兄弟はさらに3次収束、4次収束する類似の式を発見した。

3次収束の式

$ a_1 = 1 , b_1 = \frac{\sqrt{3}-1}{2} , a_{k+1} = \frac{a_k+2b_k}{3} , b_{k+1} = \sqrt[3]{\frac{b_k(a_k^2+a_kb_k+b_k^2)}{3}} $

とすると、

$ \pi =\lim_{n\to\infty} \frac{3a_{n+1}^2}{1-\sum_{k=1}^n 3^k(a_k^2-b_k^2)} $

である。この式を変形すると、

$ t_1 = 1, t_{n+1} = t_n + (3^{n+1}-3^n)(a_{n+1})^2 $

として

$ \pi \approx \frac{3a_n^2}{1-(t_n-3^na_n^2)} $

となる。


4次収束の式

$ a_1 = 1 , b_1 = 2^{-\frac{1}{4}} , a_{k+1} = \frac{a_k+b_k}{2} , b_{k+1} = \sqrt[4]{\frac{a_kb_k(a_k^2+b_k^2)}{3}} $

とすると、

$ \pi =\lim_{n\to\infty} \frac{2a_{n+1}^4}{1-2\sum_{k=1}^n 4^k\left[a_k^4-\left(\frac{a_k^2+b_k^2}{2}\right)\right]} $

である。

このアルゴリズムの精度は

$ \pi-\pi_n\leq\frac{\pi^24^{n+2}e^{-2^{2n+1}\pi}}{a_\infty^2} $

また、この式の$ a_n,b_n $は最初に示した二次収束のアルゴリズムの$ \sqrt{a_{2n}},\sqrt{b_{2n}} $と一致する。

Borweinの収束公式

Borwein兄弟は、算術幾何積分公式と同様に、任意のnに対してn次収束するようなアルゴリズムで円周率を求めることが可能であることを証明し、いくつかについて具体的な例を示した。特に2番目と7番目の公式はコンピュータによる計算が比較的容易であり、円周率の計算にも使われる。

2次収束の公式(1984)

$ \begin{align} &a_0=\sqrt{2},b_0=0,a_{n+1}=\frac{a_n+1}{2\sqrt{a_n}},b_{n+1}=\frac{\sqrt{a_n}(1+b_n)}{a_n+b_n}, \\ &p_0=2+\sqrt{2},p_{n+1}=p_nb_{n+1}\frac{1+a_{n+1}}{1+b_{n+1}} \\ \end{align} $

のとき、

$ \lim_{n\to\infty}p_n=\pi $

2次収束の公式(1987)

$ \begin{align} &y_0=\sqrt{2},z_1=\sqrt[4]{2},y_{n+1}=\frac{1+y_n}{2\sqrt{y_n}},z_{n+1}=\frac{1+y_nz_n}{(1+z_n)\sqrt{y_n}} \\ &f_0=2+\sqrt{2},f_n=f_{n-1}\frac{1+y_n}{1+z_n} \end{align} $

のとき

$ \lim_{n\to\infty}f_n=\pi $

なお、この式の精度は$ \pi-f_n<10^{-2^{n+1}} $

4次収束の公式

$ y_0=\frac{1}{\sqrt{2}},y_{n+1}=\frac{1-\sqrt{1-y_n^2}}{1+\sqrt{1-y_n^2}},\alpha_0=\frac{1}{2},\alpha_{n+1}=((1+y_{n+1})^2\alpha_n)-2^{n+1}y_{n+1} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

4次収束の公式

$ y_0=\frac{1}{3},y_{n+1}=\frac{1-\sqrt{1-y_n^2}}{1+3\sqrt{1-y_n^2}},\alpha_0=\frac{1}{3},\alpha_{n+1}=((1+3y_{n+1})\alpha_n)-2^ny_{n+1} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

4次収束の公式

$ y_0=2,y_{n+1}=\frac{4}{1+\sqrt{(4-y_n)(2+y_n)}},\alpha_0=\frac{1}{3},\alpha_{n+1}=y_n\alpha_n+\frac{2^n}{3}(1-y_n) $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

3次収束の公式

$ \begin{align} &y_0=\frac{\sqrt{3}-1}{2},y_{n+1}=\frac{1-\sqrt[3]{1-y_n^3}}{1+2\sqrt[3]{1-y_n^3}}, \\ &\alpha_0=\frac{1}{3},\alpha_{n+1}=((1+2y_{n+1})^2\alpha_n)-4\cdot3^{n-1}(1+y_{n+1})y_{n+1} \\ \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

4次収束の公式

$ \begin{align} &y_0=\sqrt{2}-1,y_{n+1}=\frac{1-\sqrt[4]{1-y_n^4}}{1+\sqrt[4]{1-y_n^4}}, \\ &\alpha_0=6-4\sqrt{2},\alpha_{n+1}=((1+y_{n+1})^4\alpha_n)-2^{2n+3}(1+y_{n+1}+y_{n+1}^2)y_{n+1} \\ \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

ちなみに、この公式は「電卓で円周率を1億桁計算する方法」として(ジョークで)紹介されたものである。 常識的な反復回数(15回)で1億桁を計算することができることに由来し、この数式の収束の速さを示すエピソードとなっている。


5次収束の公式

$ \begin{align} &S_0=5(\sqrt{5}-2),\alpha_0=\frac{1}{2},S_{n+1}=\frac{25}{S_n\left(Z_n+\frac{X_n}{Z_n}+1\right)^2}, \\ &X_n=\frac{5}{S_n}-1,Y_n=(X_n-1)^2+7,Z=\frac{1}{2}\sqrt[5]{X_n(Y_n+\sqrt{Y_n^2-4X_n^3})} \\ &\alpha_{n+1}=S_n^2\alpha_n-5^n\left(\frac{S_n^2-5}{2}+\sqrt{S_n(S_n^2-2S_n+5)}\right) \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

7次収束の公式

$ \begin{align} &\alpha_0=\frac{4}{3\sqrt{7}},\mathbf{M}=\left(2\cos\left(\frac{4\pi ij}{7}\right)\right)_{1\leq i,j\leq3}=\left( \begin{array}{ccc} 2\cos\left(\frac{4\pi}{7}\right)&2\cos\left(\frac{8\pi}{7}\right) &2\cos\left(\frac{12\pi}{7}\right) \\ 2\cos\left(\frac{8\pi}{7}\right)&2\cos\left(\frac{16\pi}{7}\right) &2\cos\left(\frac{24\pi}{7}\right) \\ 2\cos\left(\frac{12\pi}{7}\right)&2\cos\left(\frac{24\pi}{7}\right) &2\cos\left(\frac{36\pi}{7}\right) \\ \end{array} \right) \\ &=\left( \begin{array}{ccc} 2\cos\left(\frac{4\pi}{7}\right)&2\cos\left(\frac{6\pi}{7}\right) &2\cos\left(\frac{2\pi}{7}\right) \\ 2\cos\left(\frac{6\pi}{7}\right)&2\cos\left(\frac{2\pi}{7}\right) &2\cos\left(\frac{4\pi}{7}\right) \\ 2\cos\left(\frac{2\pi}{7}\right)&2\cos\left(\frac{4\pi}{7}\right) &2\cos\left(\frac{6\pi}{7}\right) \\ \end{array} \right) \\ &x_2<x_1<x_3,f(x_1)=f(x_2)=f(x_3)=0,f(x)=27^4x^3-27^332x^2+27^2325x-13^4 \\ &y_1=\sqrt[7]{x_1^3x_3},y_2=\sqrt[7]{x_2^3x_1},y_3=\sqrt[7]{x_3^3x_2},\mathbf{s_0}=\left(\frac{27}{13}\right)^{\frac{3}{7}}\left(\begin{array}{c}y_1 \\y_2 \\y_3\end{array}\right), \\ &\mathbf{s_n}=\frac{1}{7}\sqrt{m_{n-1}}[\mathbf{M\cdot s}_{n-1}'+\mathbf{1}]=\left(\begin{array}{c}s_{1,n} \\s_{2,n} \\s_{3,n}\end{array}\right),\mathbf{1}=\left(\begin{array}{c}1 \\1 \\1\end{array}\right) \\ &g_{1,n}=s_{1,n}s_{2,n}s_{3,n},g_{2,n}=s_{1,n}^3s_{2,n}+s_{2,n}^3s_{3,n}+s_{3,n}^3s_{1,n}, \\ &g_{3,n}=1-\frac{10}{7}g_{1,n}+\frac{1}{7}g_{2,n},g_{4,n}=3-\frac{51}{7}g_{1,n}+\frac{10}{7}g_{2,n} \\ &\beta_n<\mu_n<\gamma_n,h(\beta_n)=h(\mu_n)=h(\gamma_n)=0, \\ &h(x)=x^3-g_{4,n}x^2+g_{3,n}(2g_{4,n}-3g_{3,n})x-g_{3,n}^4 \\ &\mathbf{s}'_n=\left(\begin{array}{c}\sqrt[7]{\frac{\mu^3\gamma}{g_{3,n}^3}} \\\sqrt[7]{\frac{\beta^3\mu}{g_{3,n}^3}} \\\sqrt[7]{\frac{\gamma^3\beta}{g_{3,n}^3}}\end{array}\right),m_n\frac{49}{1+2\mathbf{s'_n\cdot 1}},\alpha_{n+1}=m_n\alpha_n+\sqrt{7}\frac{7^n}{3}(1-m_n) \\ \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

9次収束の公式

$ \begin{align} &\alpha_0=\frac{1}{3},s_1=\frac{\sqrt{3}-1}{2},s_n'=(1-s_n^3)^{\frac{1}{3}},s_{n+1}'=\frac{(1-s_n)^3}{(t_n+2u_n)(t_n^2+t_nu_n+u_n^2)} \\ &t_n=1+2s_n,u_n=[9s_n(1+s_n+s_n^2)]^{\frac{1}{3}},m_n=27\frac{(1+s_n'+s_n'^2)^3}{t^2_n+t_nu_n+u_n^2} \\ &\alpha_{n+1}=m_{n+1}\alpha_n+3^{2n-1}(1-m_{n+1}) \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $

16次収束の公式

$ \begin{align} &\alpha_0=\frac{1}{3},s_1=\sqrt{2}-1,s_n'=(1-s_n^4)^{\frac{1}{4}},s_{n+1}'=\frac{(1-s_n)^4}{(t_n+u_n)^2(t_n^2+u_n^2)} \\ &t_n=1+s_n,u_n=[8s_n(1+s_n^2)]^{\frac{1}{4}},m_{1,n}=\left(\frac{1+s_n'}{2}\right)^4,m_{2,n}=\frac{1}{t_n^4} \\ &\alpha_{n+1}=16m_{1,n+1}\alpha_n+\frac{4^{2n+1}}{3}(1-4m_{1,n+1}-12m_{2,n+1}) \end{align} $

のとき

$ \lim_{n\to\infty}\alpha_n=\frac{1}{\pi} $