Em matemática , o algoritmo de Borwein é um algoritmo desenvolvido por Jonathan Borwein e Peter Borwein para calcular o valor de 1/π Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity .[ 1]
Série de Ramanujan–Sato
editar
Estes dois são exemplos de séries de Ramanujan–Sato . O relacionado algoritmo de Chudnovsky usa um discriminante com classe número 1.
Número classe 2 (1989)
editar
Iniciando com
A
=
212175710912
61
+
1657145277365
B
=
13773980892672
61
+
107578229802750
C
=
(
5280
(
236674
+
30303
61
)
)
3
{\displaystyle {\begin{aligned}A&=212175710912{\sqrt {61}}+1657145277365\\B&=13773980892672{\sqrt {61}}+107578229802750\\C&={\big (}5280(236674+30303{\sqrt {61}}){\big )}^{3}\end{aligned}}}
Então
1
/
π
=
12
∑
n
=
0
∞
(
−
1
)
n
(
6
n
)
!
(
A
+
n
B
)
(
n
!
)
3
(
3
n
)
!
C
n
+
1
/
2
{\displaystyle 1/\pi =12\sum _{n=0}^{\infty }{\frac {(-1)^{n}(6n)!\,(A+nB)}{(n!)^{3}(3n)!\,C^{n+1/2}}}\,\!}
Cada termo adicional da soma parcial fornece aproximadamente 25 dígitos.
Número classe 4 (1993)
editar
Iniciando com
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 {\begin{aligned}A={}&63365028312971999585426220\\&{}+28337702140800842046825600{\sqrt {5}}\\&{}+384{\sqrt {5}}(10891728551171178200467436212395209160385656017\\&{}+4870929086578810225077338534541688721351255040{\sqrt {5}})^{1/2}\\B={}&7849910453496627210289749000\\&{}+3510586678260932028965606400{\sqrt {5}}\\&{}+2515968{\sqrt {3110}}(6260208323789001636993322654444020882161\\&{}+2799650273060444296577206890718825190235{\sqrt {5}})^{1/2}\\C={}&-214772995063512240\\&{}-96049403338648032{\sqrt {5}}\\&{}-1296{\sqrt {5}}(10985234579463550323713318473\\&{}+4912746253692362754607395912{\sqrt {5}})^{1/2}\end{aligned}}}
Então
−
C
3
π
=
∑
n
=
0
∞
(
6
n
)
!
(
3
n
)
!
(
n
!
)
3
A
+
n
B
C
3
n
{\displaystyle {\frac {\sqrt {-C^{3}}}{\pi }}=\sum _{n=0}^{\infty }{{\frac {(6n)!}{(3n)!(n!)^{3}}}{\frac {A+nB}{C^{3n}}}}}
Cada termo adicional da soma parcial fornece aproximadamente 50 dígitos.
Algoritmos iterativos
editar
Convergência quadrática (1984)
editar
Iniciando com[ 2]
a
0
=
2
b
0
=
0
p
0
=
2
+
2
{\displaystyle {\begin{aligned}a_{0}&={\sqrt {2}}\\b_{0}&=0\\p_{0}&=2+{\sqrt {2}}\end{aligned}}}
Então iterar
a
n
+
1
=
a
n
+
1
/
a
n
2
b
n
+
1
=
(
1
+
b
n
)
a
n
a
n
+
b
n
p
n
+
1
=
(
1
+
a
n
+
1
)
p
n
b
n
+
1
1
+
b
n
+
1
{\displaystyle {\begin{aligned}a_{n+1}&={\frac {{\sqrt {a_{n}}}+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{aligned}}}
Então p k π π .
Convergência cúbica (1991)
editar
Iniciando com
a
0
=
1
3
s
0
=
3
−
1
2
{\displaystyle {\begin{aligned}a_{0}&={\frac {1}{3}}\\s_{0}&={\frac {{\sqrt {3}}-1}{2}}\end{aligned}}}
Então iterar
r
k
+
1
=
3
1
+
2
(
1
−
s
k
3
)
1
/
3
s
k
+
1
=
r
k
+
1
−
1
2
a
k
+
1
=
r
k
+
1
2
a
k
−
3
k
(
r
k
+
1
2
−
1
)
{\displaystyle {\begin{aligned}r_{k+1}&={\frac {3}{1+2(1-s_{k}^{3})^{1/3}}}\\s_{k+1}&={\frac {r_{k+1}-1}{2}}\\a_{k+1}&=r_{k+1}^{2}a_{k}-3^{k}(r_{k+1}^{2}-1)\end{aligned}}}
Então ak converge cubicamente para 1/π ; isto é, cada iteração aproximadamente triplica o número de dígitos corretos.
Convergência quártica (1985)
editar
Iniciando com[ 3]
a
0
=
2
(
2
−
1
)
2
y
0
=
2
−
1
{\displaystyle {\begin{aligned}a_{0}&=2{\big (}{\sqrt {2}}-1{\big )}^{2}\\y_{0}&={\sqrt {2}}-1\end{aligned}}}
Então iterar
y
k
+
1
=
1
−
(
1
−
y
k
4
)
1
/
4
1
+
(
1
−
y
k
4
)
1
/
4
a
k
+
1
=
a
k
(
1
+
y
k
+
1
)
4
−
2
2
k
+
3
y
k
+
1
(
1
+
y
k
+
1
+
y
k
+
1
2
)
{\displaystyle {\begin{aligned}y_{k+1}&={\frac {1-(1-y_{k}^{4})^{1/4}}{1+(1-y_{k}^{4})^{1/4}}}\\a_{k+1}&=a_{k}(1+y_{k+1})^{4}-2^{2k+3}y_{k+1}(1+y_{k+1}+y_{k+1}^{2})\end{aligned}}}
Então a k π ; isto é, cada iteração aproximadamente quadruplica o número de dígitos corretos. O algoritmo não é auto-corretivo; cada iteração deve ser feita com o número desejado de dígitos corretos para o resultado final de π .
Convergência quíntica
editar
Iniciando com
a
0
=
1
2
s
0
=
5
(
5
−
2
)
{\displaystyle {\begin{aligned}a_{0}&={\frac {1}{2}}\\s_{0}&=5({\sqrt {5}}-2)\end{aligned}}}
Então iterar
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
a
n
+
1
=
s
n
2
a
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 {\begin{aligned}x_{n+1}&={\frac {5}{s_{n}}}-1\\y_{n+1}&=(x_{n+1}-1)^{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}}}\right)\right)^{1/5}\\a_{n+1}&=s_{n}^{2}a_{n}-5^{n}\left({\frac {s_{n}^{2}-5}{2}}+{\sqrt {s_{n}(s_{n}^{2}-2s_{n}+5)}}\right)\\s_{n+1}&={\frac {25}{(z_{n+1}+x_{n+1}/z_{n+1}+1)^{2}s_{n}}}\end{aligned}}}
Então ak converge quinticamente para 1/π (isto é, cada iteração aproximadamente quintuplica o número de dígitos corretos), e a seguinte condição é verificada:
0
<
a
n
−
1
π
<
16
⋅
5
n
⋅
e
−
5
n
π
{\displaystyle 0<a_{n}-{\frac {1}{\pi }}<16\cdot 5^{n}\cdot e^{-5^{n}}\pi \,\!}
Convergência de ordem nove
editar
Iniciar com
a
0
=
1
3
r
0
=
3
−
1
2
s
0
=
(
1
−
r
0
3
)
1
/
3
{\displaystyle {\begin{aligned}a_{0}&={\frac {1}{3}}\\r_{0}&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=(1-r_{0}^{3})^{1/3}\end{aligned}}}
Então iterar
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
a
n
+
1
=
w
n
+
1
a
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}&=(9r_{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}&={\frac {27(1+s_{n}+s_{n}^{2})}{v_{n+1}}}\\a_{n+1}&=w_{n+1}a_{n}+3^{2n-1}(1-w_{n+1})\\s_{n+1}&={\frac {(1-r_{n})^{3}}{(t_{n+1}+2u_{n+1})v_{n+1}}}\\r_{n+1}&=(1-s_{n+1}^{3})^{1/3}\end{aligned}}}
Então a k π ; isto é,cada iteração aproximadamente multiplica por nove o número de dígitos corretos.[ 4]
Referências
↑ Jonathon M. Borwein, Peter B. Borwein, Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity , Wiley, New York, 1987. Many of their results are available in: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Berlin, 2001, ISBN 3-540-66572-2
↑ Arndt, Jörg; Haenel, Christoph (1998). π UnleashedISBN 3-540-66572-2 ↑ Mak, Ronald (2003). The Java Programmers Guide to Numerical Computation . [S.l.]: Pearson Educational. p. 353. ISBN 0-13-046041-9 ↑ «Nonic Iterations» . sfu.ca . Consultado em 11 de agosto de 2018 Ligações externas
editar
