最近用到这个技巧实在很巧妙，记录一下留在这里……数值计算中我们有时候要用一些截断的函数展开来逼近某些复杂的函数，如：这个展开的函数有可能是某些特殊函数，比如Bessel函数、Chebyshev多项式、Laguerre多项式之类的。为了计算这个函数在某个点的取值，一般的思路是把每一项的特殊函数值算出来，再乘以系数加起来。但其实这往往不是一个好主意，这样做往往是数值不稳定的，你可能会不断地用超过计算机表示范围的大数乘小数，或者用大数加小数，结果可能误差很大或者干脆发散掉。一个更好的解决方案就是Clenshaw求和。如果我们采用的特殊函数有一个递推关系：而且这个关系对于都适用（超出的项约定等于0），那么我们考虑这样一个数列：那么你会发现，算到最后，正是你要求的函数值，而对于很多特殊函数，0阶函数往往特别简单（比如Laguerre多项式，）。于是计算就完成了。为什么这是对的？解出，带入第一个式子，我们有：根据递推关系，前面的所有项都统统为0，所以。这也提示了如果递推关系不到该怎么办（比如，广义超几何函数的递推关系只在时成立）。这时候你只需要找到上式后面几项，令系数等于0解出新的递推关系补足这几个系数（注意系数可以是的函数）就好。这个算法有个特别的好处：很多时候你甚至不需要调用额外的库和函数来计算任何一个特殊函数，时间复杂度是，额外的空间开销是，比直接求和既快又省还稳定。来源：知乎 www.zhihu.com作者：赵永峰【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。点击下载