Algoritmo de Borwein

Em matemática, o algoritmo de Borwein é um algoritmo desenvolvido por Jonathan Borwein e Peter Borwein para calcular o valor de 1/[[Pi|Predefinição:Math]]. Desenvolveram diversos outros algoritmos. Publicaram o livro Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity.

Série de Ramanujan–Sato

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)

Iniciando com

$\begin{array}{cc}A& =212175710912\sqrt{61}+1657145277365\\ B& =13773980892672\sqrt{61}+107578229802750\\ C& =(5280(236674+30303\sqrt{61}){)}^3\end{array}$

Então

$1/\pi =12\sum _{n=0}^{\mathrm{\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)

Iniciando com

$\begin{array}{cc}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{array}$

Então

$\frac{\sqrt{-C^3}}{\pi }=\sum _{n=0}^{\mathrm{\infty }}\frac{(6n)!}{(3n)!(n!{)}^3}\frac{A+nB}{C^{3n}}$

Cada termo adicional da soma parcial fornece aproximadamente 50 dígitos.

Algoritmos iterativos

Convergência quadrática (1984)

Iniciando com

$\begin{array}{cc}{a}_0& =\sqrt{2}\\ b_0& =0\\ p_0& =2+\sqrt{2}\end{array}$

Então iterar

$\begin{array}{cc}{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{array}$

Então p_k converge quadraticamente para [[Pi|Predefinição:Math]]; isto é, cada iteração dobra aproximadamente 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 Predefinição:Math.

Convergência cúbica (1991)

Iniciando com

$\begin{array}{cc}{a}_0& =\frac{1}{3}\\ s_0& =\frac{\sqrt{3}-1}{2}\end{array}$

Então iterar

$\begin{array}{cc}{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{array}$

Então a_k converge cubicamente para 1/Predefinição:Math; isto é, cada iteração aproximadamente triplica o número de dígitos corretos.

Convergência quártica (1985)

Iniciando com

$\begin{array}{cc}{a}_0& =2(\sqrt{2}-1{)}^2\\ y_0& =\sqrt{2}-1\end{array}$

Então iterar

$\begin{array}{cc}{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{array}$

Então a_k converge quarticamente para 1/Predefinição:Math; 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 Predefinição:Math.

Convergência quíntica

Iniciando com

$\begin{array}{cc}{a}_0& =\frac{1}{2}\\ s_0& =5(\sqrt{5}-2)\end{array}$

Então iterar

$\begin{array}{cc}{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}(y_{n+1}+\sqrt{y_{n+1}^2-4x_{n+1}^3})\right)}^{1/5}\\ a_{n+1}& =s_n^2{a}_n-5^n(\frac{s_n^2-5}{2}+\sqrt{s_n(s_n^2-2s_n+5)})\\ s_{n+1}& =\frac{25}{(z_{n+1}+x_{n+1}/z_{n+1}+1{)}^2{s}_n}\end{array}$

Então a_k converge quinticamente para 1/Predefinição:Math (isto é, cada iteração aproximadamente quintuplica o número de dígitos corretos), e a seguinte condição é verificada:

$0<a_n-\frac{1}{\pi }<16\cdot 5^n\cdot e^{-5^n}\pi$

Convergência de ordem nove

Iniciar com

$\begin{array}{cc}{a}_0& =\frac{1}{3}\\ r_0& =\frac{\sqrt{3}-1}{2}\\ s_0& =(1-r_0^3{)}^{1/3}\end{array}$

Então iterar

$\begin{array}{cc}{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{array}$

Então a_k converge nonicamente para 1/Predefinição:Math; isto é,cada iteração aproximadamente multiplica por nove o número de dígitos corretos.

Ver também

• Fórmula BBP
• Algoritmo de Chudnovsky
• Algoritmo de Gauss-Legendre
• Séries de Ramanujan–Sato

Ligações externas

• Pi Formulas from Wolfram MathWorld