W matematyce algorytm Borweina to algorytm opracowany przez Jonathana i Petera Borweinów do obliczania wartości 1 / π Pi and the AGM – A Study in Anallytic Number Theory and Computational Complexity .
szereg Ramanujana-Sato
Te dwa są przykładami serii Ramanujana – Sato . Powiązany algorytm Chudnowskiego wykorzystuje dyskryminator o numerze klasy 1.
Klasa numer 2 (1989)
Zacznij od ustawienia [ potrzebne źródło
ZA
= 212175710912
61
+ 1657145277365
b
= 13773980892672
61
+ 107578229802750
do
=
(
5280
(
236674 + 30303
61
)
)
3
{\ Displaystyle {\ rozpocząć {wyrównane} A & = 2121 75710912{\sqrt {61}}+1657145277365\\B&=13773980892672 {\sqrt {61}}+107578229802750\\C&=\left(5280\left(236674+30303{\sqrt {61}}\right)\right)^{3}\end{aligned}}}
Następnie
1 π
= 12
∑
n =
0
∞
( - 1
)
n
( 6 n ) ! ( ZA + n B )
( n !
)
3
( 3 n ) !
do
n +
1 2
{\ Displaystyle {\ Frac {1} {\ pi}} = 12 \ suma _ {n = 0} ^ {\ infty} {\ Frac {(-1) ^ {n} (6n)! \,(A+nB)}{(n!)^{3}(3n)!\,C^{n+{\frac {1}{2}}}}}}
Każdy dodatkowy wyraz częściowej sumy daje w przybliżeniu 25 cyfr.
Klasa numer 4 (1993)
Zacznij od ustawienia [ potrzebne źródło
A =
63365028312971999585426220
+ 28337702140800842046825600
5
+ 384
5
(
10891728551171178200467436212395209160385656017
+
4870929086578810225077338534541688721351255040
5
)
1 2
B =
7849910453496627210289749000
+ 3510586678260932028965606400
5
+ 2515968
3110
(
6260208323789001636993322654444020882161
+
2799650273060444296577206890718825190235
5
)
1 2
C =
− 214772995063512240
− 96049403338648032
5
− 1296
5
(
10985234579463550323713318473
+
4912746253692362754607395912
5
)
1 2
{\ Displaystyle {\ rozpocząć {wyrównane} A = {} i 63365028312971999585426220 \\ & {} + 28337702140800842046825600 {\ sqrt {5}} \\& {} + 384 {\ sqrt {5}} {\ duży (} 1089172855 1171178200467436212395209160385656017 \\&{}+\left.4870929086578810225077338534541688721351255040{\sqrt {5}}\right)^{\frac {1}{2}}\\B={}&7849910453496627210289749000\\&{}+35 10586678260932028965606400 {\ sqrt {5 }}\\&{}+2515968{\sqrt {3110}}{\big (}6260208323789001636993322654444020882161\\&{}+\left.279965027306044429657720689071882519023 5{\sqrt {5}}\right)^{\frac {1}{ 2}}\\C={}&-214772995063512240\\&{}-96049403338648032{\sqrt {5}}\\&{}-1296{\sqrt {5}}{\big (}10985234579463550323713318473\\&{ }+\left.4912746253692362754607395912{\sqrt {5}}\right)^{\frac {1}{2}}\end{wyrównane}}}
Następnie
-
do
3
π
=
∑
n =
0
∞
( 6 n ) !
( 3 n ) ! ( n !
)
3
ZA + n b do
3
n {
\ Displaystyle {\ Frac {\ sqrt {-C ^ {3}}} {\ pi}} = \ suma _ {n = 0} ^ {\ infty}} {\frac {(6n)!}{(3n)!(n!)^{3}}}{\frac {A+nB}{C^{3n}}}}}
Każdy dodatkowy wyraz serii daje w przybliżeniu 50 cyfr.
Algorytmy iteracyjne
Zbieżność kwadratowa (1984)
Zacznij od ustawienia
za
0
=
2
b
0
=
0
p
0
= 2 +
2
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {0} & = {\ sqrt {2}} \\ b_ {0} i = 0 \\ p_ {0} i = 2 +{\sqrt {2}}\end{wyrównane}}}
Następnie iteruj
za
n + 1
=
za
n
+
1
za
n
2
b
n + 1
=
( 1 +
b
n
)
za
n
za
n
+
b
n
p
n + 1
=
( 1 +
za
n + 1
)
p
n
b
n + 1
1 +
b
n + 1
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {n + 1} & = {\ Frac {{\ sqrt {a_ {n}}} + {\ Frac {1} {\ sqrt {a_ {n }}}}}{2}}\\b_{n+1}&={\frac {(1+b_{n}){\sqrt {a_{n}}}}{a_{n}+b_{ n}}}\\p_{n+1}&={\frac {(1+a_{n+1})\,p_{n}b_{n+1}}{1+b_{n+1} }}\end{wyrównane}}}
Wtedy p k π ; to znaczy, każda iteracja w przybliżeniu podwaja liczbę poprawnych cyfr. Algorytm nie jest samokorygujący; każda iteracja musi być wykonana z żądaną liczbą poprawnych cyfr, aby uzyskać końcowy wynik π .
Konwergencja sześcienna (1991)
Zacznij od ustawienia
za
0
=
1 3
s
0
=
3
- 1
2
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {0} & = {\ Frac {1} {3}} \\ s_ {0} & = {\ Frac {{\ sqrt {3}}-1}{2}}\end{wyrównane}}}
Następnie iteruj
r
k + 1
=
3
1 + 2
(
1 -
s
k
3
)
1 3
s
k + 1
=
r
k + 1
- 1
2
za
k + 1
=
r
k + 1
2
za
k
-
3
k
(
r
k + 1
2
- 1
)
{\ Displaystyle {\ rozpocząć {wyrównane} r_ {k + 1} & = {\ Frac {3} {1 + 2 \ lewo (1-s_ {k} ^ {3} \ prawej) ^ {\ frac {1}{3}}}}\\s_{k+1}&={\frac {r_{k+1}-1}{2}}\\a_{k+1}&=r_{k +1}^{2}a_{k}-3^{k}\left(r_{k+1}^{2}-1\right)\end{wyrównane}}}
k zbiega się sześciennie do 1 / π
Konwergencja kwarcowa (1985)
Zacznij od ustawienia
za
0
= 2
(
2
- 1
)
2
r
0
=
2
- 1
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {0} i = 2 \ lewo ({\ sqrt {2}} -1 \ prawej) ^ {2} \ \y_{0}&={\sqrt {2}}-1\end{wyrównane}}}
Następnie iteruj
y
k + 1
=
1 -
(
1 -
y
k
4
)
1 4
1 +
(
1 -
y
k
4
)
1 4
za
k + 1
=
za
k
(
1 +
y
k + 1
)
4
-
2
2 k + 3
y
k + 1
(
1 +
y
k + 1
+
y
k + 1
2
)
{\ Displaystyle {\ rozpocząć {wyrównane} y_ {k + 1} & = {\ Frac {1- \ lewo (1-y_ {k} ^ {4}\right)^{\frac {1}{4}}}{1+\left(1-y_{k}^{4}\right)^{\frac {1}{4}}}} \\a_{k+1}&=a_{k}\left(1+y_{k+1}\right)^{4}-2^{2k+3}y_{k+1}\left(1 +y_{k+1}+y_{k+1}^{2}\right)\end{wyrównane}}}
k jest 1 / π nie jest samokorygujący; każda iteracja musi być wykonana z żądaną liczbą poprawnych cyfr, aby uzyskać końcowy wynik π .
Jedna iteracja tego algorytmu odpowiada dwóm iteracjom algorytmu Gaussa-Legendre'a . Dowód tych algorytmów można znaleźć tutaj:
Zbieżność kwintyczna
Zacznij od ustawienia
za
0
=
1 2
s
0
= 5
(
5
- 2
)
=
5
ϕ
3
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {0} & = {\ Frac {1} {2}} \\ s_ {0} i = 5 \left({\sqrt {5}}-2\right)={\frac {5}{\phi ^{3}}}\end{wyrównane}}}
gdzie
ϕ =
1 +
5
2
{\ Displaystyle \ phi = {\ tfrac {1 + {\ sqrt {5}}} {2}}}
złoty podział . Następnie iteruj
x
n + 1
=
5
s
n
- 1
y
n + 1
=
(
x
n + 1
- 1
)
2
+ 7
z
n + 1
=
(
1 2
x
n + 1
(
y
n + 1
+
y
n + 1
2
- 4
x
n + 1
3
)
)
1 5
za
n + 1
=
s
n
2
za
n
-
5
n
(
s
n
2
- 5
2
+
s
n
(
s
n
2
- 2
s
n
+ 5
)
)
s
n + 1
=
25
(
z
n + 1
+
x
n + 1
z
n + 1
+ 1
)
2
s
n
{\ Displaystyle {\ rozpocząć {wyrównane} x_ {n + 1} i = {\ Frac {5} {s_ {n}} }-1\\y_{n+1}&=\left(x_{n+1}-1\right)^{2}+7\\z_{n+1}&=\left({\frac { 1}{2}}x_{n+1}\left(y_{n+1}+{\sqrt {y_{n+1}^{2}-4x_{n+1}^{3}}}\ prawo)\prawo)^{\frac {1}{5}}\\a_{n+1}&=s_{n}^{2}a_{n}-5^{n}\left({\frac {s_{n}^{2}-5}{2}}+{\sqrt {s_{n}\left(s_{n}^{2}-2s_{n}+5\right)}}\right )\\s_{n+1}&={\frac {25}{\left(z_{n+1}+{\frac {x_{n+1}}{z_{n+1}}}+1 \right)^{2}s_{n}}}\end{aligned}}}
k zbiega się kwintycznie do 1 / π
0
<
za
n
-
1 π
< 16 ⋅
5
n
⋅
mi
-
5
n
π
{\ Displaystyle 0 <a_ {n} - {\ Frac {1} {\ pi} <16 \ cdot 5 ^ {n} \ cdot mi ^{-5^{n}}\pi \,\!}
Konwergencja nonowa
Zacznij od ustawienia
za
0
=
1 3
r
0
=
3
- 1
2
s
0
=
(
1 -
0
r
3
)
1 3
{\ Displaystyle {\ rozpocząć {wyrównane} a_ {0} i = {\ Frac {1} {3}} \\ r_ {0 }&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=\left(1-r_{0}^{3}\right)^{\frac { 1}{3}}\end{wyrównane}}}
Następnie iteruj
t
n + 1
= 1 + 2
r
n
u
n + 1
=
(
9
r
n
(
1 +
r
n
+
r
n
2
)
)
1 3
v
n + 1
=
t
n + 1
2
+
t
n + 1
u
n + 1
+
u
n + 1
2
w
n + 1
=
27
(
1 +
s
n
+
s
n
2
)
v
n + 1
za
n + 1
=
w
n + 1
za
n
+
3
2 n - 1
(
1 -
w
n + 1
)
s
n + 1
=
(
1 -
r
n
)
3
(
t
n + 1
+ 2
u
n + 1
)
v
n + 1
r
n + 1
=
(
1 -
s
n + 1
3
)
1 3
{\ Displaystyle { \begin{aligned}t_{n+1}&=1+2r_{n}\\u_{n+1}&=\left(9r_{n}\left(1+r_{n}+r_{n} ^{2}\right)\right)^{\frac {1}{3}}\\v_{n+1}&=t_{n+1}^{2}+t_{n+1}u_{ n+1}+u_{n+1}^{2}\\w_{n+1}&={\frac {27\left(1+s_{n}+s_{n}^{2}\right )}{v_{n+1}}}\\a_{n+1}&=w_{n+1}a_{n}+3^{2n-1}\left(1-w_{n+1} \right)\\s_{n+1}&={\frac {\left(1-r_{n}\right)^{3}}{\left(t_{n+1}+2u_{n+1 }\right)v_{n+1}}}\\r_{n+1}&=\left(1-s_{n+1}^{3}\right)^{\frac {1}{3} }\end{wyrównane}}}
a k 1 / π
Zobacz też
Bibliografia
_ _ _ Springer, Berlin, 2001, ISBN 3-540-66572-2
^ Arndt, Jörg; Haenel, Christoph (1998). π Uwolniony ISBN 3-540-66572-2
^ Mak, Ronald (2003). Przewodnik programistów języka Java po obliczeniach numerycznych . Pearsona edukacyjnego. P. 353. ISBN 0-13-046041-9
^ Milla, Lorenz (2019), Łatwy dowód trzech rekurencyjnych algorytmów π , arXiv : 1907,04110
^ Henrik Vestermark (4 listopada 2016). „Praktyczna implementacja algorytmów π” (PDF) . Źródło 29 listopada 2020 r .
Linki zewnętrzne
