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

수학노트
둘러보기로 가기 검색하러 가기
(피타고라스님이 이 페이지를 개설하였습니다.)
 
 
(사용자 2명의 중간 판 76개는 보이지 않습니다)
1번째 줄: 1번째 줄:
 +
==개요==
  
 +
* [[산술 기하 평균 (arithmetic-geometric mean)]]을 활용하여 파이값을 빠르게 계산할 수 있는 알고리즘
 +
 +
 +
==타원적분과 산술 기하 평균==
 +
===타원적분===
 +
* [[타원적분]] 항목 참조
 +
* <math>K(k) = \int_0^{\frac{\pi}{2}} \frac{d\theta}{\sqrt{1-k^2 \sin^2\theta}}</math>
 +
* <math>E(k) = \int_0^{\frac{\pi}{2}} \sqrt{1-k^2 \sin^2\theta}d\theta</math>
 +
* <math>k'=\sqrt{1-k^2}</math>
 +
* <math>K'(k) : = K(k')</math>
 +
* <math>E'(k) : = E(k')</math>
 +
 +
===타원적분에 대한 르장드르 항등식===
 +
* 르장드르 항등식
 +
:<math>E(k)K'(k)+E'(k)K(k)-K(k)K'(k)=\frac{\pi}{2}</math>
 +
* 특별히 다음과 같은 관계가 성립함
 +
:<math>2K(\frac{1}{\sqrt{2}})E(\frac{1}{\sqrt{2}})-K(\frac{1}{\sqrt{2}})^2=\frac{\pi}{2} \label{leg}</math>
 +
* [[타원적분]] 항목 참조
 +
 +
===타원적분과 산술 기하 평균의 관계===
 +
* [[란덴변환(Landen's transformation)]]에서 다음을 얻었다
 +
:<math>K(k)=\frac{\pi}{2M(1,\sqrt{1-k^2})}</math>
 +
* 특별히 다음이 성립
 +
:<math>K(\frac{1}{\sqrt2})=\frac{\pi}{2M(1,\frac{1}{\sqrt2})} \label{mk}</math>
 +
* 참고로 이 등식은 [[렘니스케이트(lemniscate) 곡선의 길이와 타원적분]]에도 등장한다
 +
 +
 +
==가우스-살라민 알고리즘==
 +
;보조정리
 +
주어진 양수 <math>0<k<1</math>에 대하여 다음과 같이 수열 <math>a_n,b_n,c_n</math>을 정의하자.
 +
:<math>
 +
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}
 +
</math>
 +
다음이 성립한다
 +
:<math>\sum_{i=0}^{\infty} 2^{i-1} c_i^2  = 1 - \frac{E(k)}{K(k)} \label{lem}</math>
 +
 +
 +
;정리
 +
다음과 같이 수열 <math>a_n,b_n,c_n,\pi_n</math>을 정의하자.
 +
:<math>
 +
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}
 +
</math>
 +
이 때, 수열 <math>\pi_n</math>은 <math>\pi</math>로 수렴한다.
 +
 +
;증명
 +
<math>M=M(1,1/\sqrt{2})</math>, <math>K=K(1/\sqrt{2})</math>, <math>E=E(1/\sqrt{2})</math>로 두자
 +
 +
\ref{leg}로부터 다음을 얻는다
 +
:<math>2KE-K^2=\frac{\pi}{2}</math>
 +
즉,
 +
:<math>\frac{2E}{K}-1=\frac{\pi}{2K^2}</math>
 +
\ref{mk}로부터 <math>2MK=\pi</math>를 얻는다
 +
 +
\ref{lem}로부터
 +
:<math>
 +
\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}
 +
</math>■
 +
===수치 계산===
 +
*  수열 <math>\pi_n</math>의 처음 여섯항을 계산한 결과
 +
:<math>
 +
3.1405792505221682483113312689758233117734402375129\\ 3.1415926462135422821493444319826957743144372233456\\ 3.1415926535897932382795127748018639743812255048354\\ 3.1415926535897932384626433832795028841971146782836\\ 3.1415926535897932384626433832795028841971693993751\\ 3.1415926535897932384626433832795028841971693993751
 +
</math>
 +
 +
 +
 +
==또다른 알고리즘==
 +
* 수열 <math>x_n, y_n, \pi_n</math>을 다음과 같이 정의하자
 +
:<math>
 +
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
 +
</math>
 +
* 수열 <math>\pi_n</math>은 원주율로 수렴한다
 +
* 다음은 처음 여섯개의 항을 계산한 결과.
 +
:<math>
 +
3.1426067539416226007907198236183018919713562462772\\3.1415926609660442304977522351203396906792842568645\\3.1415926535897932386457739917571417940347896238675\\3.1415926535897932384626433832795028841972241204666\\ 3.1415926535897932384626433832795028841971693993751\\ 3.1415926535897932384626433832795028841971693993751
 +
</math>
 +
* 한번씩 계산할 때마다, 대략 두 배 정도 정확한 자리수
 +
* 9번째까지 계산한다면, 1000자리 이상의 파이값을 계산
 +
 +
 +
 +
 +
 +
==관련된 학부 과목과 미리 알고 있으면 좋은 것들==
 +
 +
* [[일변수미적분학]]
 +
* [[해석개론]]
 +
* [[복소함수론]]
 +
 +
 +
 +
 +
 +
==관련된 항목들==
 +
 +
* [[타원함수]]
 +
* [[타원적분]]
 +
* [[렘니스케이트(lemniscate) 곡선의 길이와 타원적분|lemniscate 적분]]
 +
* [[자코비 세타함수]]
 +
* [[라마누잔과 파이]]
 +
 +
 +
 +
 +
 +
==매스매티카 파일 및 계산 리소스==
 +
 +
* https://docs.google.com/leaf?id=0B8XXo8Tve1cxNjc0NTM0ZGUtNWVmYS00YjFjLWE1OWMtZTVmMDkxNTI5OWRk&sort=name&layout=list&num=50
 +
* 파이썬 http://www.johndcook.com/blog/2012/06/03/calculating-pi-with-agm-and-mpmath/
 +
 +
 +
 +
==사전형태의 자료==
 +
 +
* http://en.wikipedia.org/wiki/Arithmetic-geometric_mean
 +
* http://en.wikipedia.org/wiki/Salamin-Brent_algorithm
 +
 +
 +
 +
==관련도서==
 +
 +
* [http://www.amazon.com/PI-AGM-Analytic-Computational-Complexity/dp/047131515X Pi and the AGM]
 +
** Jonathan M. Borwein, Peter B. Borwein, 1998
 +
 +
 +
 +
 +
==관련논문==
 +
 +
* [http://wwwmaths.anu.edu.au/%7Ebrent/pub/pub028.html 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 ([[1939326/attachments/1144114|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
 +
* [http://www.jstor.org/stable/2323302 Gauss, Landen, Ramanujan, the Arithmetic-Geometric Mean, Ellipses, π, and the Ladies Diary]
 +
** Gert Almkvist and Bruce Berndt
 +
** <cite>The American Mathematical Monthly</cite>, Vol. 95, No. 7 (Aug. - Sep., 1988), pp. 585-608
 +
* [http://www.jstor.org/stable/2325206 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, <cite>The American Mathematical Monthly</cite>, Vol. 96, No. 3 (Mar., 1989), pp. 201-219
 +
* [http://www.jstor.org/stable/3619132 Recent Calculations of π: The Gauss-Salamin Algorithm]
 +
** Nick Lord, <cite>The Mathematical Gazette</cite>, Vol. 76, No. 476 (Jul., 1992), pp. 231-242
 +
* [http://www.jstor.org/stable/2690037 The Ubiquitous π]
 +
** Dario Castellanos, <cite>Mathematics Magazine</cite>, Vol. 61, No. 2 (Apr., 1988), pp. 67-98
 +
* [http://www.jstor.org/stable/2031275 The Arithmetic-Geometric Mean and Fast Computation of Elementary Functions]
 +
** J. M. Borwein and P. B. Borwein, <cite>[http://www.jstor.org/action/showPublication?journalCode=siamreview SIAM Review]</cite>, Vol. 26, No. 3 (Jul., 1984), pp. 351-366
 +
*  Computation of pi Using Arithmetic-Geometric Mean ([[1939326/attachments/1341646|pdf]])
 +
** E. Salamin, Mathematics of Computation 30(1976) 565-570
 +
[[분류:원주율]]
 +
 +
==메타데이터==
 +
===위키데이터===
 +
* ID :  [https://www.wikidata.org/wiki/Q476167 Q476167]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'arithmetic'}, {'OP': '*'}, {'LOWER': 'geometric'}, {'LEMMA': 'mean'}]
 +
* [{'LOWER': 'agm'}, {'LEMMA': 'method'}]
 +
* [{'LEMMA': 'AGM'}]

2021년 2월 17일 (수) 04:46 기준 최신판

개요


타원적분과 산술 기하 평균

타원적분

  • 타원적분 항목 참조
  • \(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}\]

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

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

  • 특별히 다음이 성립

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


가우스-살라민 알고리즘

보조정리

주어진 양수 \(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자리 이상의 파이값을 계산



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



관련된 항목들



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


사전형태의 자료


관련도서



관련논문

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'arithmetic'}, {'OP': '*'}, {'LOWER': 'geometric'}, {'LEMMA': 'mean'}]
  • [{'LOWER': 'agm'}, {'LEMMA': 'method'}]
  • [{'LEMMA': 'AGM'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=산술_기하_평균을_이용한_원주율의_계산&oldid=52329"