众所周知,圆周率 π 是数学里最经典的常数之一。虽然我们平时背的是 3.1415926⋯,但真正要高精度计算 π,并不是靠“量圆”或者“背小数”,而是靠各种收敛极快的公式和迭代算法。
这篇文章主要想整理一下几类常见的求 π 方法,最后介绍一个我自己瞎想出来的高阶迭代公式,请大佬轻喷。
1. 最朴素的想法:从几何出发
最早的求 π 方法,基本都和圆有关。
比如阿基米德的方法,就是用内接正多边形和外切正多边形夹逼圆周长。边数越多,多边形越接近圆,于是就能把 π 夹在一个越来越小的区间里。
这个方法思想很漂亮:
内接多边形周长<圆周长<外切多边形周长
但它有个明显缺点:收敛速度不算快。想要很多位小数,需要把多边形边数搞得非常大。
所以它适合理解 π,但不适合现代高精度计算。
2. 无穷级数法
后来人们发现,π 可以写成很多无穷级数。
最经典的例子是莱布尼茨公式:
4π=1−31+51−71+⋯
也就是:
π=4k=0∑∞2k+1(−1)k
这个公式非常简洁,而且很好证明,但问题也非常严重:收敛太慢。
比如要算很多位 π,这个公式基本不现实。它的美感远大于实用价值。
3. Machin 类公式
为了提高速度,可以利用反正切函数:
arctanx=x−3x3+5x5−7x7+⋯
当 x 比较小时,这个级数收敛会快很多。
著名的 Machin 公式是:
4π=4arctan51−arctan2391
因为 51 和 2391 都比较小,所以实际收敛速度比莱布尼茨公式强得多。
很长一段时间里,Machin 类公式都是计算 π 的重要工具。
4. Ramanujan 与 Chudnovsky 公式
再往后,就出现了变态级别的公式。
Ramanujan 给出过很多极快收敛的 π 公式,其中一类大概长这样:
π1=980122k=0∑∞(k!)43964k(4k)!(1103+26390k)
这个公式每一项能带来很多位正确数字。
现代计算 π 最有名的公式之一是 Chudnovsky 公式:
π1=12k=0∑∞(3k)!(k!)36403203k+3/2(−1)k(6k)!(13591409+545140134k)
它收敛极快,是高精度计算 π 的经典算法之一。
不过这类公式虽然快,但推导背景比较深,涉及模形式、椭圆函数等内容,不是正常人很容易自然想到的东西。
5. 从“求 π”变成“求方程的根”
其实还有一种思路:
因为
sinπ=0
所以求 π,可以看成求方程
sinx=0
的正根。
当然,sinx=0 有很多根:
0,π,2π,3π,⋯
如果初值选在 π 附近,比如 x0=3,那么目标就是收敛到 π。
这时自然可以想到牛顿法。
对
f(x)=sinx
使用牛顿法:
xn+1=xn−f′(xn)f(xn)
因为
f′(x)=cosx
所以:
xn+1=xn−cosxnsinxn
也就是:
xn+1=xn−tanxn
这个迭代在靠近 π 时是二阶收敛的。
所谓二阶收敛,大概意思是:如果当前误差是 en,下一步误差大约会变成 en2 量级。也就是说,一旦接近正确答案,正确位数会增长得很快。
但我就想:牛顿法是二阶收敛,那有没有办法构造更高阶的迭代?
答案是:有的兄弟,有的
6. 一个高阶求 π 的想法
我的想法是,不直接对 sinx 用牛顿法,而是考虑:
g(x)=sinx1
因为当 x→π 时,sinx→0,所以 g(x) 在 x=π 附近会趋向无穷。
换句话说,π 不是 g(x) 的零点,而是 g(x) 的一个极点。
对这种函数,可以尝试利用高阶导数的比值构造迭代。
我想到的公式是:
xn+1=xn+(p−1)dxp−1dp−1(sinx1)x=xndxp−2dp−2(sinx1)x=xn
其中 p≥2。
如果写得紧凑一点,就是:
xn+1=xn+(p−1)g(p−1)(xn)g(p−2)(xn),g(x)=sinx1
并希望有:
n→∞limxn=π
7. 为什么这个公式看起来有道理?
在 x=π 附近,令误差:
e=x−π
因为
sinx=sin(π+e)=−sine
而当 e 很小时:
sine≈e
所以:
sinx≈−e
于是:
sinx1≈−e1
也就是说,g(x)=sinx1 在 π 附近的主要部分很像:
−x−π1
而对
h(x)=x−π1
求导,有:
h(k)(x)=(−1)kk!(x−π)−k−1
于是高阶导数的比值大概会把 x−π 提取出来。
这就说明,用
g(p−1)(x)g(p−2)(x)
这种结构,确实有机会构造出一个把 x 往 π 推的高阶迭代。
直观地说,这个公式不是像牛顿法那样看函数的切线,而是利用更多阶导数的信息,试图一次性榨出更多误差项。
8. 特殊情况:当 p=2 时
当 p=2,公式变成:
xn+1=xn+g′(xn)g(xn)
其中:
g(x)=sinx1
计算导数:
g′(x)=−sin2xcosx
所以:
g′(x)g(x)=−sin2xcosxsinx1−cosxsinx−tanx
因此:
xn+1=xn−tanxn
刚好退化成普通牛顿法。
这点我感觉还挺有意思:也就是说,这个公式可以看作牛顿法的一种高阶推广。
9. 这个公式的优点和问题
这个公式理论上的优点是:
如果 p 越大,它利用的导数阶数越高,局部收敛阶也可能越高。也就是说,在已经离 π 比较近的时候,它可能比普通牛顿法收敛得更猛。
但是它也有很现实的问题:
第一,高阶导数不好算。
sinx1 的高阶导数会越来越复杂,实际计算时并不一定划算。
第二,高阶迭代不等于高效算法。
一个算法快不快,不只看迭代次数,还要看每一步的计算量。如果一步里要算特别复杂的高阶导数,那么总耗时可能反而更大。
第三,初值很重要。
这种迭代应该是局部收敛的,也就是初始值要离 π 比较近。比如 x0=3 这种就比较自然。如果初值乱选,可能跑到别的根,甚至发散。
所以我不敢说它一定能超过 Chudnovsky 这种顶级公式,但从迭代法角度看,它至少是一个挺有意思的高阶构造。
10. 总结
求 π 的方法有很多:
从阿基米德的几何夹逼,到莱布尼茨级数,再到 Machin 公式、Ramanujan 公式、Chudnovsky 公式,思路越来越抽象,收敛也越来越快。
而本文最后这个公式,是从另一个角度出发:
把求 π 看成求 sinx=0 的根,再把根转化成 sinx1 的极点,然后利用高阶导数比值构造迭代。
公式如下:
xn+1=xn+(p−1)dxp−1dp−1(sinx1)x=xndxp−2dp−2(sinx1)x=xn
并猜想在合适初值下:
n→∞limxn=π
其中 p 越大,理论上的局部收敛阶越高。