В математика , Алгоритм Борвейна является алгоритм разработан Джонатан и Питер Борвейн чтобы вычислить значение 1 /π Пи и AGM - исследование аналитической теории чисел и вычислительной сложности .[1]
Рамануджан – Сато серия
Эти два примера Рамануджан – Сато серия . Связанные Алгоритм Чудновского использует дискриминант с номером класса 1.
Класс № 2 (1989) Начните с установки[нужна цитата
А = 212175710912 61 + 1657145277365 B = 13773980892672 61 + 107578229802750 C = ( 5280 ( 236674 + 30303 61 ) ) 3 { displaystyle { begin {align} A & = 212175710912 { sqrt {61}} + 1657145277365 B & = 13773980892672 { sqrt {61}} + 107578229802750 C & = { big (} 5280 (236674 + 30303 { sqrt {61}}) { big)} ^ {3} end {align}}} потом
1 / π = 12 ∑ п = 0 ∞ ( − 1 ) п ( 6 п ) ! ( А + п B ) ( п ! ) 3 ( 3 п ) ! C п + 1 / 2 { displaystyle 1 / pi = 12 sum _ {n = 0} ^ { infty} { frac {(-1) ^ {n} (6n)! , (A + nB)} {(n! ) ^ {3} (3n)! , C ^ {n + 1/2}}} , !} Каждый дополнительный член частичной суммы дает примерно 25 цифр.
Класс № 4 (1993) Начните с установки[нужна цитата
А = 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 {align} A = {} & 63365028312971999585426220 & {} + 28337702140800842046825600 { sqrt {5}} & {} + 384 { sqrt {5}} (10891728551171178200467436212395209160 4870929086578810225077338534541688721351255040 { sqrt {5}}) ^ {1/2} B = {} & 7849910453496627210289749000 & {} + 3510586678260932028965606400 { sqrt {5}} & {} + sqrt {5}} & {} 25 (6260208323789001636993322654444020882161 & {} + 2799650273060444296577206890718825190235 { sqrt {5}}) ^ {1/2} C = {} & - 214772995063512240 & {} - {5803240} sq38 & {} - {5803240} sq38 } -1296 { sqrt {5}} (10985234579463550323713318473 & {} + 4912746253692362754607395912 { sqrt {5}}) ^ {1/2} end {выровнено}}} потом
− C 3 π = ∑ п = 0 ∞ ( 6 п ) ! ( 3 п ) ! ( п ! ) 3 А + п B C 3 п { displaystyle { frac { sqrt {-C ^ {3}}} { pi}} = sum _ {n = 0} ^ { infty} {{ frac {(6n)!} {(3n )! (п!) ^ {3}}} { frac {A + nB} {C ^ {3n}}}}} Каждый дополнительный член ряда дает примерно 50 цифр.
Итерационные алгоритмы
Квадратичная сходимость (1984) Начните с установки[2]
а 0 = 2 б 0 = 0 п 0 = 2 + 2 { displaystyle { begin {align} a_ {0} & = { sqrt {2}} b_ {0} & = 0 p_ {0} & = 2 + { sqrt {2}} end {выровнено}}} Затем повторите
а п + 1 = а п + 1 / а п 2 б п + 1 = ( 1 + б п ) а п а п + б п п п + 1 = ( 1 + а п + 1 ) п п б п + 1 1 + б п + 1 { displaystyle { begin {align} 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 {выровнено}}} потом п k π ; то есть каждая итерация примерно удваивает количество правильных цифр. Алгоритм такой нет самокорректирующийся; каждая итерация должна выполняться с желаемым количеством правильных цифр для π окончательный результат.
Кубическая конвергенция (1991) Начните с установки
а 0 = 1 3 s 0 = 3 − 1 2 { displaystyle { begin {align} a_ {0} & = { frac {1} {3}} s_ {0} & = { frac {{ sqrt {3}} - 1} {2} } конец {выровнено}}} Затем повторите
р k + 1 = 3 1 + 2 ( 1 − s k 3 ) 1 / 3 s k + 1 = р k + 1 − 1 2 а k + 1 = р k + 1 2 а k − 3 k ( р k + 1 2 − 1 ) { displaystyle { begin {align} 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 ^ {к} (г_ {к + 1} ^ {2} -1) конец {выровнено}}} потом аk сходится кубически к 1 /π ; то есть каждая итерация примерно втрое увеличивает количество правильных цифр.
Конвергенция четвертой степени (1985) Начните с установки[3]
а 0 = 2 ( 2 − 1 ) 2 у 0 = 2 − 1 { displaystyle { begin {align} a_ {0} & = 2 { big (} { sqrt {2}} - 1 { big)} ^ {2} y_ {0} & = { sqrt {2}} - 1 end {align}}} Затем повторите
у k + 1 = 1 − ( 1 − у k 4 ) 1 / 4 1 + ( 1 − у k 4 ) 1 / 4 а k + 1 = а k ( 1 + у k + 1 ) 4 − 2 2 k + 3 у k + 1 ( 1 + у k + 1 + у k + 1 2 ) { displaystyle { begin {align} 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 {выровнено}}} потом а k π ; то есть каждая итерация увеличивает количество правильных цифр примерно в четыре раза. Алгоритм такой нет самокорректирующийся; каждая итерация должна выполняться с желаемым количеством правильных цифр для π окончательный результат.
Одна итерация этого алгоритма эквивалентна двум итерациям Алгоритм Гаусса – Лежандра .Подтверждение этих алгоритмов можно найти здесь:[4]
Квинтическая конвергенция Начните с установки
а 0 = 1 2 s 0 = 5 ( 5 − 2 ) { displaystyle { begin {align} a_ {0} & = { frac {1} {2}} s_ {0} & = 5 ({ sqrt {5}} - 2) end {выравнивается} }} Затем повторите
Икс п + 1 = 5 s п − 1 у п + 1 = ( Икс п + 1 − 1 ) 2 + 7 z п + 1 = ( 1 2 Икс п + 1 ( у п + 1 + у п + 1 2 − 4 Икс п + 1 3 ) ) 1 / 5 а п + 1 = s п 2 а п − 5 п ( s п 2 − 5 2 + s п ( s п 2 − 2 s п + 5 ) ) s п + 1 = 25 ( z п + 1 + Икс п + 1 / z п + 1 + 1 ) 2 s п { displaystyle { begin {align} 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 {align}}} Затемk квинтически сходится к 1 /π (то есть каждая итерация примерно в пять раз увеличивает количество правильных цифр), и выполняется следующее условие:
0 < а п − 1 π < 16 ⋅ 5 п ⋅ е − 5 п π { displaystyle 0 Неконическая конвергенция Начните с установки
а 0 = 1 3 р 0 = 3 − 1 2 s 0 = ( 1 − р 0 3 ) 1 / 3 { displaystyle { begin {align} a_ {0} & = { frac {1} {3}} r_ {0} & = { frac {{ sqrt {3}} - 1} {2} } s_ {0} & = (1-r_ {0} ^ {3}) ^ {1/3} end {align}}} Затем повторите
т п + 1 = 1 + 2 р п ты п + 1 = ( 9 р п ( 1 + р п + р п 2 ) ) 1 / 3 v п + 1 = т п + 1 2 + т п + 1 ты п + 1 + ты п + 1 2 ш п + 1 = 27 ( 1 + s п + s п 2 ) v п + 1 а п + 1 = ш п + 1 а п + 3 2 п − 3 ( 1 − ш п + 1 ) s п + 1 = ( 1 − р п ) 3 ( т п + 1 + 2 ты п + 1 ) v п + 1 р п + 1 = ( 1 − s п + 1 3 ) 1 / 3 { displaystyle { begin {align} 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 {выровнено}}} потом а k π ; то есть каждая итерация приблизительно умножает количество правильных цифр на девять.[5]
Смотрите также
Рекомендации
^ Джонатан М. Борвейн, Питер Б. Борвейн, Пи и AGM - исследование аналитической теории чисел и вычислительной сложности , Wiley, New York, 1987. Многие из их результатов доступны в: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Berlin, 2001, ISBN 3-540-66572-2 ^ Арндт, Йорг; Хенель, Кристоф (1998). π РазвязанныйISBN 3-540-66572-2 ^ Мак, Рональд (2003). Руководство программиста Java по численным вычислениям . Pearson Educational. п. 353. ISBN 0-13-046041-9 ^ Милла, Лоренц (2019), Простое доказательство трех рекурсивных π-алгоритмов , arXiv :1907.04110 ^ Хенрик Вестермарк (4 ноября 2016 г.). «Практическая реализация π-алгоритмов» (PDF) . Получено 29 ноябрь 2020 . внешняя ссылка
