Clenshaw遞推公式

在數值分析中，Clenshaw遞推公式 (由Charles William Clenshaw發現)是一個求切比雪夫多項式的值的遞歸方法。

切比雪夫多項式

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

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

其中T_n是n階切比雪夫多項式.

Clenshaw遞推公式

Clenshaw遞推公式可以用來計算切比雪夫多項式的值。給定

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

我們定義

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

於是

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

(注)上面的公式在 ${\displaystyle N=0,1}$的情況下無意義。 此時我們可以用下面的公式：

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

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

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

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

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

這裡

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

或者

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

其中${\displaystyle U_{n}(x)}$是第二類切比雪夫多項式。