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)$是第二類切比雪夫多項式。