가우스-레젠드르 알고리즘

가우스-레젠드르 알고리즘은 π의 숫자를 계산하는 알고리즘이다.25회 반복에 불과해 4500만 correct의 정확한 자릿수를 생성하는 등 급속한 수렴성을 보인 점이 눈에 띈다.그러나 단점은 컴퓨터 메모리 집약적이어서 마친과 같은 공식을 대신 사용하는 경우가 있다는 점이다.

이 방법은 칼 프리드리히 가우스(1777–1855)와 아드리아-마리 레전드르(1752–1833)의 개별 작업에 바탕을 둔 것으로 현대의 곱셈과 제곱근 알고리즘을 결합한 것이다.산술-기하 평균에 근사치를 위해 두 숫자를 반복적으로 산술 평균과 기하 평균으로 대체한다.

아래에 제시된 버전은 가우스-울러, 브렌트-살라민(또는 살라민-브렌트) 알고리즘으로도 알려져 있으며,^[1] 리차드 브렌트와 유진 살라민이 1975년에 독자적으로 발견했다.1999년 9월 18일부터 20일까지 π의 처음 206,158,430,000개의 소수 자릿수를 계산하는 데 사용되었고, 결과는 보르웨인의 알고리즘으로 확인되었다.

알고리즘.

1. 초기값 설정:
   $${\displaystyle a_{0}=1\qquad b_{0}={\frac {1}{{\sqrt{2}}:}\qquad t_{0}={\frac {1}{4}\qquad p_{0}=1}1.}$$

   
2. ${\displaystyle n_{}}$ ${\$과(와) ${\displaystyle b_{}}$ ${\$의 차이가 원하는 정확도에 도달할$$ 때까지 다음 지침을 반복하십시오.
   $${\displaystyle {\begin{aligned}a_{n+1}&={\frac {a_{n}+b_{n}}{2}},\\\\b_{n+1}&={\sqrt {a_{n}b_{n}}},\\\\t_{n+1}&=t_{n}-p_{n}(a_{n}-a_{n+1})^{2},\\\\p_{n+1}&=2p_{n}.\\end{aigned}}$$

   
3. π은 다음과 같이 근사하게 계산한다.
   $${\displaystyle \pi \pi \약 {\frac {(a_{n+1}+b_{n+1}^{2}}:{4t_{n+1}.}$$

   

처음 세 번의 반복은 다음과 같다(첫 번째 잘못된 자리까지 주어지는 근사치):

$3.140\190 }$

${\displaystyle 3.14159264\pair }$

${\displaystyle 3.1415926535897932382\cHB}$

알고리즘은 2차 정합성을 가지며, 이는 기본적으로 정확한 자릿수가 알고리즘의 각 반복과 함께 두 배가 된다는 것을 의미한다.

수학적 배경

산술-기하 평균의 한계

a와₀ b라는₀ 두 숫자의 산술-기하 평균은 시퀀스의 한계를 계산하여 구한다.

${\displaystyle {\n1}a_{n+1}&={\frac {a_{n}+b_{n}}{n1}:{n2}},\[6pt]b_{n+1}&={\sqrt{a_{n}b_{n}}}}},\end{ned}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

둘 다 같은 한계로 수렴하는 거지
If ${\displaystyle a_{0}=1}$ and ${\displaystyle b_{0}=\cos \varphi }$ then the limit is ${\textstyle {\pi \over 2K(\sin \varphi )}}$ where ${\displaystyle K(k)}$ is the complete elliptic integral of the first kind

${\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{1-k^{2}\sin ^{2}\}}.}$

${\displaystyle {\mathrm{c}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle \sin }$ ${\displaystyle }$ ${\displaystyle \phi }$ $\$ {\$displaystyle c_{$0}=\$sin \varphi$${\displaystyle {\},}_{}}$ ${\displaystyle c_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle a_{}}$- ${\displaystyle {\mathrm{i}}_{}}$ +$$1 {\$displaystyle c_{i+1}=a_{i}-a_${i+1}:{i$+$1}:{i+1}:{i$+$1}, 그러면

${\displaystyle \sin \sin \varphi )}{{i-1}c_{i}^{2}=1-{E(\sin \varphi )}}}K(\sin \varphi )}}}}}$

여기서 $E{\displaystyle }$( ${\displaystyle k}$) ${\displaystyle E(k)}$은 두 번째 유형의 완전한 타원 적분이다.

${\displaystyle E(k)=\int _{0}^{\pi /2}{\sqrt {1-k^{2}\sin ^{2}\theta }}\;d\theta }$ and ${\displaystyle K(k)=\int _{0}^{\pi /2}{\frac {d\theta }{\sqrt {1-k^{2}\sin ^{2}\theta }}}.$$}$

가우스는 이 두 가지 결과를 모두 알고 있었다.^{[2][3] [4]}

레전드레의 정체

$\phi$$$+$=$ = 1 2 $style$ {\displaystyle $\$$\mathrm{varphi}$ $}$ $\frac{\mathrm{및<img\; alt="\backslash varphi\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e"\; style="vertical-align:\; -0.838ex;\; width:1.52ex;\; height:2.176ex;"\; papago-attr-id="74"><img\; alt="\backslash theta\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/6e5ab2664b422d53eb0c7df3b87e1360d75ad9af"\; style="vertical-align:\; -0.338ex;\; width:1.09ex;\; height:2.176ex;"\; papago-attr-id="75">}}{}$$\theta {\displaystyle }$ {\$displaystyle \theta}{1 \over$ 2$}\pi }$ Legendre가$$ ID를 입증했다.

${\displaystyle K(\sin \varphi )E(\sin \varphi )+K(\sin \varphi )-K(\sin \varphi )={1 \over 2}\pi .}$^[2]

동등하게,

${\displaystyle \frac {\sin \varphi )[E(\cos \varphi )-K(\cos \varphi )]+K(\cos \varphi )E(\sin \varphi )={\frac {\pi{2}}:$

적분 미적분이 있는 기초 교정쇄

Gauss-Legendre 알고리즘은 적분 미적분만을 사용하여 증명될 수 있다.이것은 여기서도^[5] 여기서도 끝난다.^[6]

참고 항목

• π의 수치 근사치

참조