"산술 기하 평균을 이용한 원주율의 계산"의 두 판 사이의 차이

2020년 12월 28일 (월) 06:35 판

개요

산술 기하 평균 (arithmetic-geometric mean)을 활용하여 파이값을 빠르게 계산할 수 있는 알고리즘

타원적분과 산술 기하 평균

타원적분

타원적분 항목 참조
\(K(k) = \int_0^{\frac{\pi}{2}} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}\)
\(E(k) = \int_0^{\frac{\pi}{2}} \sqrt{1-k^2 \sin^2\theta}d\theta\)
\(k'=\sqrt{1-k^2}\)
\(K'(k) : = K(k')\)
\(E'(k) : = E(k')\)

타원적분에 대한 르장드르 항등식

르장드르 항등식

\[E(k)K'(k)+E'(k)K(k)-K(k)K'(k)=\frac{\pi}{2}\]

특별히 다음과 같은 관계가 성립함

\[2K(\frac{1}{\sqrt{2}})E(\frac{1}{\sqrt{2}})-K(\frac{1}{\sqrt{2}})^2=\frac{\pi}{2} \label{leg}\]

타원적분 항목 참조

타원적분과 산술 기하 평균의 관계

란덴변환(Landen's transformation)에서 다음을 얻었다

\[K(k)=\frac{\pi}{2M(1,\sqrt{1-k^2})}\]

특별히 다음이 성립

\[K(\frac{1}{\sqrt2})=\frac{\pi}{2M(1,\frac{1}{\sqrt2})} \label{mk}\]

참고로 이 등식은 렘니스케이트(lemniscate) 곡선의 길이와 타원적분에도 등장한다

가우스-살라민 알고리즘

보조정리

주어진 양수 \(0<k<1\)에 대하여 다음과 같이 수열 \(a_n,b_n,c_n\)을 정의하자. \[ a_0=1,b_0=\sqrt{1-k^2} \\ a_{n+1}={a_n+b_n \over 2},b_{n+1}=\sqrt{a_n b_n}\\ c_n=\sqrt{a_n^2-b_n^2} \] 다음이 성립한다 \[\sum_{i=0}^{\infty} 2^{i-1} c_i^2 = 1 - \frac{E(k)}{K(k)} \label{lem}\]

정리

다음과 같이 수열 \(a_n,b_n,c_n,\pi_n\)을 정의하자. \[ a_0=1,b_0=\frac{1}{\sqrt{2}}\\ a_{n+1}={a_n+b_n \over 2},b_{n+1}=\sqrt{a_n b_n}\\ c_n=\sqrt{a_n^2-b_n^2}=\frac{c_{n-1}^2}{4a_n} \\ \pi_n=\frac{2a_{n+1}^2}{1-\sum_{k=0}^{n} 2^kc_k^2} \] 이 때, 수열 \(\pi_n\)은 \(\pi\)로 수렴한다.

증명

\(M=M(1,1/\sqrt{2})\), \(K=K(1/\sqrt{2})\), \(E=E(1/\sqrt{2})\)로 두자

\ref{leg}로부터 다음을 얻는다 \[2KE-K^2=\frac{\pi}{2}\] 즉, \[\frac{2E}{K}-1=\frac{\pi}{2K^2}\] \ref{mk}로부터 \(2MK=\pi\)를 얻는다

\ref{lem}로부터 \[ \begin{aligned} \lim_{n\to \infty}\pi_n&=\lim_{n\to \infty} \frac{2a_{n+1}^2}{1-\sum_{k=0}^{n} 2^kc_k^2}\\ &=\frac{2M^2}{1-2(1-E/K)}=\frac{2M^2}{{\pi}/{2K^2}}=\frac{\pi^2/2K^2}{{\pi}/{2K^2}}\\ &=\pi \end{aligned} \]■

수치 계산

수열 \(\pi_n\)의 처음 여섯항을 계산한 결과

\[ 3.1405792505221682483113312689758233117734402375129\\ 3.1415926462135422821493444319826957743144372233456\\ 3.1415926535897932382795127748018639743812255048354\\ 3.1415926535897932384626433832795028841971146782836\\ 3.1415926535897932384626433832795028841971693993751\\ 3.1415926535897932384626433832795028841971693993751 \]

또다른 알고리즘

수열 \(x_n, y_n, \pi_n\)을 다음과 같이 정의하자

\[ x_0=\sqrt{2},\pi_0=2+\sqrt{2},y_1=\sqrt[4]{2} \\ x_{n+1}=\frac{1}{2}(\sqrt{x_{n}}+\frac{1}{\sqrt{x_{n}}}),\quad n\geq0 \\ y_{n+1}=\frac{y_{n}\sqrt{x_n}+\frac{1}{\sqrt{x_{n}}}}{y_n+1}, \quad n\geq1 \\ \pi_n=\pi_{n-1}\frac{x_n+1}{y_n+1}, \quad n\geq1 \]

수열 \(\pi_n\)은 원주율로 수렴한다
다음은 처음 여섯개의 항을 계산한 결과.

\[ 3.1426067539416226007907198236183018919713562462772\\3.1415926609660442304977522351203396906792842568645\\3.1415926535897932386457739917571417940347896238675\\3.1415926535897932384626433832795028841972241204666\\ 3.1415926535897932384626433832795028841971693993751\\ 3.1415926535897932384626433832795028841971693993751 \]

한번씩 계산할 때마다, 대략 두 배 정도 정확한 자리수
9번째까지 계산한다면, 1000자리 이상의 파이값을 계산

매스매티카 파일 및 계산 리소스

사전형태의 자료

메타데이터

위키데이터

ID : Q476167