Algoritmus Borweins - Borweins algorithm - Wikipedia

v matematika, Borweinův algoritmus je algoritmus vymyslel Jonathan a Peter Borwein vypočítat hodnotu 1 /π. Vymysleli několik dalších algoritmů. Vydali knihu Pi a AGM - studie analytické teorie čísel a výpočetní složitosti.^[1]

Série Ramanujan – Sato

Tyto dva příklady jsou příklady a Série Ramanujan – Sato. Související Chudnovského algoritmus používá diskriminační s třídou číslo 1.

Třída číslo 2 (1989)

Začněte nastavením^{[Citace je zapotřebí ]}

${ displaystyle { begin {aligned} A & = 212175710912 { sqrt {61}} + 1657145277365 B & = 13773980892672 { sqrt {61}} + 107578229802750 C & = { big (} 5280 (236674 + 30303 { sqrt {61}}) { big)} ^ {3} end {zarovnáno}}}$

Pak

${ displaystyle 1 / pi = 12 součet _ {n = 0} ^ { infty} { frac {(-1) ^ {n} (6n)! , (A + nB)} {{n! ) ^ {3} (3n)! , C ^ {n + 1/2}}} , !}$

Každý další člen částečného součtu poskytuje přibližně 25 číslic.

Třída číslo 4 (1993)

Začněte nastavením^{[Citace je zapotřebí ]}

${ displaystyle { begin {Zarovnáno} A = {} & 63365028312971999585426220 & {} + 28337702140800842046825600 { sqrt {5}} & {} + 384 { sqrt {5}} (10891728551171178200467436212395209160385655459160385 4870929086578810225077338534541688721351255040 { sqrt {5}}) ^ {1/2} B = {} & 7849910453496627210289749000 & {} + 3510586678260932028965606400 { sqrt {5}} & {} + 2515 {31} (6260208323789001636993322654444020882161 & {} + 2799650273060444296577206890718825190235 { sqrt {5}}) ^ {1/2} C = {} & - 214772995063512240 & {} - 96049403338648032 } -1296 { sqrt {5}} (10985234579463550323713318473 & {} + 4912746253692362754607395912 { sqrt {5}}) ^ {1/2} end {zarovnáno}}}$

Pak

${ displaystyle { frac { sqrt {-C ^ {3}}} { pi}} = součet _ {n = 0} ^ { infty} {{ frac {(6n)!} {(3n )! (n!) ^ {3}}} { frac {A + nB} {C ^ {3n}}}}}$

Každý další člen série dává přibližně 50 číslic.

Iterativní algoritmy

Kvadratická konvergence (1984)

Začněte nastavením^[2]

${ displaystyle { begin {aligned} a_ {0} & = { sqrt {2}} b_ {0} & = 0 p_ {0} & = 2 + { sqrt {2}} end {zarovnaný}}}$

Pak opakujte

${ 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 {zarovnáno}}}$

Pak p_k kvadraticky konverguje k π; to znamená, že každá iterace přibližně zdvojnásobí počet správných číslic. Algoritmus je ne samoopravující; každá iterace musí být provedena s požadovaným počtem správných číslic pro πkonečný výsledek.

Kubická konvergence (1991)

Začněte nastavením

${ displaystyle { begin {aligned} a_ {0} & = { frac {1} {3}} s_ {0} & = { frac {{ sqrt {3}} - 1} {2} } end {zarovnáno}}}$

Pak opakujte

${ 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 {zarovnáno}}}$

Pak A_k konverguje kubicky na 1 /π; to znamená, že každá iterace přibližně ztrojnásobuje počet správných číslic.

Kvartová konvergence (1985)

Začněte nastavením^[3]

${ displaystyle { begin {aligned} a_ {0} & = 2 { big (} { sqrt {2}} - 1 { big)} ^ {2} y_ {0} & = { sqrt {2}} - 1 end {zarovnáno}}}$

Pak opakujte

${ 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 {zarovnáno}}}$

Pak A_k konverguje kvartálně proti 1 /π; to znamená, že každá iterace přibližně čtyřnásobí počet správných číslic. Algoritmus je ne samoopravující; každá iterace musí být provedena s požadovaným počtem správných číslic pro πkonečný výsledek.

Jedna iterace tohoto algoritmu je ekvivalentní dvěma iteracím Gauss – Legendre_algoritmus Důkaz těchto algoritmů naleznete zde:^[4]

Kvintická konvergence

Začněte nastavením

${ displaystyle { begin {aligned} a_ {0} & = { frac {1} {2}} s_ {0} & = 5 ({ sqrt {5}} - 2) end {align} }}$

Pak opakujte

${ 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)}} vpravo) s_ {n + 1} & = { frac {25} {(z_ {n + 1} + x_ {n + 1} / z_ {n + 1} +1) ^ {2} s_ {n}}} end {zarovnáno}}}$

Pak_k quintically konverguje na 1 /π (to znamená, že každá iterace přibližně pětinásobí počet správných číslic) a platí následující podmínka:

${ displaystyle 0$

Nonická konvergence

Začněte nastavením

${ displaystyle { begin {aligned} a_ {0} & = { frac {1} {3}} r_ {0} & = { frac {{ sqrt {3}} - 1} {2} } s_ {0} & = (1-r_ {0} ^ {3}) ^ {1/3} end {zarovnáno}}}$

Pak opakujte

${ 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-3} (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 {zarovnáno}}}$

Pak A_k konverguje nonically na 1 /π; to znamená, že každá iterace přibližně vynásobí počet správných číslic devíti.^[5]

Viz také

• Bailey – Borwein – Plouffe vzorec
• Chudnovského algoritmus
• Algoritmus Gauss – Legendre
• Série Ramanujan – Sato

Reference

externí odkazy

• Pi vzorce od Wolfram MathWorld