克伦肖算法

在数值分析中，克伦肖算法，也叫克伦肖求和法，是一种评估切比雪夫多项式线性组合的递归方法。该方法由CharlesWilliamClenshaw于1955年发表。它是Horner评估单项式线性组合的方法的一般化。它不仅仅适用于切比雪夫多项式；它还适用于任何一类可由三期递归关系定义的函数。

在完全通用的情况下，Clenshaw算法计算有限序列的函数的加权和{displaystylephi_{k}(x)}是直接计算很复杂的函数。是直接计算很复杂的函数，但{displaystyleβ}是一个常数，既不依赖于k，也不依赖于β。{displaystyle{begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,b_{k}(x)&=a_{k}+alpha_{k}(x),b_{k+1}(x)+beta_{k+1}(x),b_{k+2}(x).end{aligned}}}请注意，这种计算方法没有直接提到函数{displaystyleb_{1}(x)}，所需的和可以用它们和最简单的函数表示。，所需的和可以用它们和最简单的函数来表示{displaystyleS(x)==phi_{0}(x),a_{0}+phi_{1}(x),b_{1}(x)+beta_{1}(x),phi_{0}(x),b_{2}(x)。更多信息和稳定性分析见Fox和Parker。

例子Horner是Clenshaw的一个特例一个特别简单的例子发生在评估一个形式的多项式时并由递归系数产生α(x)=x{displaystyleΑ(x)=x}和{displaystyleβ=0}。在这种情况下，计算和的递推公式是{displaystylep_{n}(x)={frac{1}{2}}left[b_{0}(x)-b_{2}(x)right].}

克伦肖求和法被广泛用于大地测量的应用中。一个简单的应用是