Clenshaw递推公式

在数值分析中，Clenshaw递推公式 (由Charles William Clenshaw发现)是一个求切比雪夫多项式的值的递归方法。

切比雪夫多项式

N次切比雪夫多项式，是下面形式的多项式p(x)

$p(x)=\sum _{n=0}^{N}a_{n}T_{n}(x)$

其中T_n是n阶切比雪夫多项式.

Clenshaw递推公式

Clenshaw递推公式可以用来计算切比雪夫多项式的值。给定

$p(x)=\sum _{n=0}^{N}a_{n}T_{n}(x)$

我们定义

$b_{N}\,\!$	$:=a_{N}\,$
$b_{N-1}\,\!$	$:=2xb_{N}+a_{N-1}\,$
$b_{N-n}\,\!$	$:=2xb_{N-n+1}+a_{N-n}-b_{N-n+2}\,,\;n=2,\ldots ,N-1\,$
$b_{0}\,\!$	$:=xb_{1}+a_{0}-b_{2}\,$

于是

$p(x)=\sum _{n=0}^{N}a_{n}T_{n}(x)=b_{0}.$

(注)上面的公式在 $N=0,1$的情况下无意义。 此时我们可以用下面的公式：

$b_{N+2}:=0\,$

$b_{N+1}:=0\,$

$b_{j}:=2xb_{j+1}-b_{j+2}+a_{j}\,,\;j=N,\ldots ,1$ (downward, omit if N=0)

$p(x):=xb_{1}-b_{2}+a_{0}\,$

$q(x):=2xb_{1}-b_{2}+a_{0}\,$

这里

$p(x)=\sum _{n=0}^{N}a_{n}T_{n}(x)$

或者

$q(x)=\sum _{n=0}^{N}a_{n}U_{n}(x)$

其中$U_{n}(x)$是第二类切比雪夫多项式。