Clenshaw 递推公式

Clenshaw 递推公式是一个求 Chebyshev 多项式的值的递归方法。设$T_n, U_n$分别是第一类和第二类 Chebyshev 多项式，由于其正交性，任意一个$n$次多项式$p(x)$都可由这两组多项式线性表示。这里假设

$$p(x) = \sum_{k=0}^n a_k T_k(x).$$

递推公式

Clenshaw 递推公式可以用来计算一多项式的切比雪夫多项式表示。作向下递归

步骤1：$b_{n+2} :=0, b_{n+1} := 0.$

步骤2：$b_k := 2 x b_{k+1} - b_{k+2} + a_k, k = n, n-1, \cdots,1.$

步骤3：$p(x) := x b_1 - b_2 + a_0, q(x) := 2 x b_1 - b_2 + a_0.$

则

$p(x) = \sum_{k=0}^n a_k T_k(x), q(x) = \sum_{k=0}^n a_k U_k(x).$