산술 기하 평균을 이용한 원주율의 계산

간단한 소개

• AGM(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}{\)

\(q=e^{2\pi i \tau}\)

\(\theta_{2}(\tau)= \sum_{n=-\infty}^\infty q^{(n+\frac{1}{2})^2/2}\)

\(\theta_3(\tau)=\sum_{n=-\infty}^\infty q^{n^2/2}\)

\(\theta_{4}(\tau)= \sum_{n=-\infty}^\infty (-1)^n q^{n^2/2}\)

\(k=k(\tau)=\frac{\theta_2^2(\tau)}{\theta_3^2(\tau)}\)

\(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}=\frac{\theta_4^2(\tau)}{\theta_3^2(\tau)}\)

\(K'(k) = K(k')\)

\(E'(k) = E(k')\)

 

 

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

For \(\phi\!\) and \(\theta\!\) such that \(\phi+\theta={1 \over 2}\pi\!\)

 

\[K(\sin \phi) E(\sin \theta ) + K(\sin \theta ) E(\sin \phi) - K(\sin \phi) K(\sin \theta) = {1 \over 2}\pi\!\]

• 다음과 같이 표현 가능

\(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}\)

 

 

타원적분과 AGM의 관계

• 란덴변환(Landen's transformation) 에 의해 다음이 성립함.

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

특별히, \(K(\frac{1}{\sqrt2})=\frac{\pi}{2M(1,\frac{1}{\sqrt2})}\)

 

한편, \(a_{n+1}={a_n+b_n \over 2}\),  \(b_{n+1}=\sqrt{a_n b_n}\) , \(a_0=1\), \(b_0=\sqrt{1-k^2}\) ,  \(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)}\)

 

 

가우스-살라민 알고리즘

[/pages/1939326/attachments/1341696 Salamin.jpg]

(증명)

\(2K(\frac{1}{\sqrt{2}})E(\frac{1}{\sqrt{2}})-K(\frac{1}{\sqrt{2}})^2=\frac{\pi}{2}\)

\(K(\frac{1}{\sqrt2})=\frac{\pi}{2M(1,\frac{1}{\sqrt2})}\)

 

\(\sum_{i=0}^{\infty} 2^{i-1} c_i^2 = 1 - \frac{E(k)}{K(k)}\)

를 결합하여 증명가능.

 

 

 

 

또다른 알고리즘

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

 

• 위에 정의된 수열 \(\pi_n\)은 파이로 수렴하게 된다. 다음은 다섯번째 항까지 계산한 결과.

\(\pi_1=3.1426067539416226007907198236183018919713562462772\)
\(\pi_2=3.1415926609660442304977522351203396906792842568645\)
\(\pi_3=3.1415926535897932386457739917571417940347896238675\)
\(\pi_4=3.1415926535897932384626433832795028841972241204666\)
\(\pi_5=3.1415926535897932384626433832795028841971693993751\)

• 한번씩 계산할 때마다, 대략 두 배 정도 정확한 자리수
• 9번째까지 계산한다면, 1000자리 이상의 파이값을 계산
• 매쓰매티카 노트
  
  • Pi_and_AGM.nb

 

 

관련된 학부 과목과 미리 알고 있으면 좋은 것들

• 일변수미적분학
• 해석개론
• 복소함수론

 

 

 

관련된 다른 주제들

• 타원적분, 타원함수, 타원곡선
  
  • 타원적분
  • lemniscate 적분
• 자코비 세타함수
• #

 

 

표준적인 도서 및 추천도서

• Pi and the AGM
  
  • Jonathan M. Borwein, Peter B. Borwein

 

 

위키링크

• http://en.wikipedia.org/wiki/Arithmetic-geometric_mean
• http://en.wikipedia.org/wiki/Salamin-Brent_algorithm

 

 

관련논문

• Multiple-precision zero-finding methods and the complexity of elementary function evaluation
  
  • R. P. Brent, Analytic Computational Complexity (edited by J. F. Traub), Academic Press, New York, 1975, 151–176
• The arithmetic-geometric mean of Gauss (pdf)
  
  • D.A. Cox, Enseignement Math. 30 (1984) 275-330
• Gauss and the arithmetic-geometric mean
  
  • D.A. Cox, Notices Amer. Math. Soc. 32(2) (1985) 147-151

• Gauss, Landen, Ramanujan, the Arithmetic-Geometric Mean, Ellipses, π, and the Ladies Diary
  
  • Gert Almkvist and Bruce Berndt
  • The American Mathematical Monthly, Vol. 95, No. 7 (Aug. - Sep., 1988), pp. 585-608
• Ramanujan, Modular Equations, and Approximations to Pi or How to Compute One Billion Digits of Pi
  
  • J. M. Borwein, P. B. Borwein and D. H. Bailey, The American Mathematical Monthly, Vol. 96, No. 3 (Mar., 1989), pp. 201-219
• Recent Calculations of π: The Gauss-Salamin Algorithm
  
  • Nick Lord, The Mathematical Gazette, Vol. 76, No. 476 (Jul., 1992), pp. 231-242
• The Ubiquitous π
  
  • Dario Castellanos, Mathematics Magazine, Vol. 61, No. 2 (Apr., 1988), pp. 67-98
• The Arithmetic-Geometric Mean and Fast Computation of Elementary Functions
  
  • J. M. Borwein and P. B. Borwein, SIAM Review, Vol. 26, No. 3 (Jul., 1984), pp. 351-366
• Computation of pi Using Arithmetic-Geometric Mean (pdf)
  
  • E. Salamin, Mathematics of Computation 30(1976) 565-570