Algoritmo de Clenshaw

Un caso particularmente sencillo se presenta al evaluar un polinomio de la forma $${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}x^{k}.}$$ Las funciones son simplemente $${\displaystyle {\begin{aligned}\phi _{0}(x)&=1,\\\phi _{k}(x)&=x^{k}=x\phi _{k-1}(x)\end{aligned}}}$$ y son producidos por los coeficientes de recurrencia${\displaystyle \alpha (x)=x}$y${\displaystyle \beta =0}$.

En este caso, la fórmula de recurrencia para calcular la suma es $${\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(x)}$$ y, en este caso, la suma es simplemente $${\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x),}$$ que es exactamente el método habitual de Horner .

Consideremos una serie de Chebyshev truncada.$${\displaystyle p_{n}(x)=a_{0}+a_{1}T_{1}(x)+a_{2}T_{2}(x)+\cdots +a_{n}T_{n}(x).}$$

Los coeficientes en la relación de recurrencia para los polinomios de Chebyshev son $${\displaystyle \alpha (x)=2x,\quad \beta =-1,}$$ con las condiciones iniciales $${\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.}$$

Por lo tanto, la recurrencia es $${\displaystyle b_{k}(x)=a_{k}+2xb_{k+1}(x)-b_{k+2}(x)}$$ y los resultados finales son $${\displaystyle b_{0}(x)=a_{0}+2xb_{1}(x)-b_{2}(x),}$$$${\displaystyle p_{n}(x)={\tfrac {1}{2}}\left[a_{0}+b_{0}(x)-b_{2}(x)\right].}$$

Una expresión equivalente para la suma viene dada por $${\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).}$$

La suma de Clenshaw se utiliza ampliamente en aplicaciones geodésicas . ^{[ 2 ]} Una aplicación simple es sumar las series trigonométricas para calcular la distancia del arco meridiano en la superficie de un elipsoide. Estas tienen la forma $${\displaystyle m(\theta )=C_{0}\,\theta +C_{1}\sin \theta +C_{2}\sin 2\theta +\cdots +C_{n}\sin n\theta .}$$

Dejando de lado el inicial${\displaystyle C_{0}\,\theta }$término, el resto es una suma de la forma apropiada. No hay término principal porque${\displaystyle \phi _{0}(\theta )=\sin 0\theta =\sin 0=0}$.

La relación de recurrencia para${\displaystyle \sin k\theta }$es $${\displaystyle \sin(k+1)\theta =2\cos \theta \sin k\theta -\sin(k-1)\theta ,}$$ haciendo los coeficientes en la relación de recursión $${\displaystyle \alpha _{k}(\theta )=2\cos \theta ,\quad \beta _{k}=-1.}$$ y la evaluación de la serie viene dada por $${\displaystyle {\begin{aligned}b_{n+1}(\theta )&=b_{n+2}(\theta )=0,\\b_{k}(\theta )&=C_{k}+2\cos \theta \,b_{k+1}(\theta )-b_{k+2}(\theta ),\quad \mathrm {for\ } n\geq k\geq 1.\end{aligned}}}$$ El paso final se simplifica particularmente porque${\displaystyle \phi _{0}(\theta )=\sin 0=0}$, por lo que el final de la recurrencia es simplemente${\displaystyle b_{1}(\theta )\sin(\theta )}$; el${\displaystyle C_{0}\,\theta }$El término se añade por separado: $${\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .}$$

Nótese que el algoritmo solo requiere la evaluación de dos cantidades trigonométricas.${\displaystyle \cos \theta }$y${\displaystyle \sin \theta }$.

A veces es necesario calcular la diferencia de dos arcos meridianos de forma que se mantenga una alta precisión relativa. Esto se logra utilizando identidades trigonométricas para escribir $${\displaystyle m(\theta _{1})-m(\theta _{2})=C_{0}(\theta _{1}-\theta _{2})+\sum _{k=1}^{n}2C_{k}\sin {\bigl (}{\textstyle {\frac {1}{2}}}k(\theta _{1}-\theta _{2}){\bigr )}\cos {\bigl (}{\textstyle {\frac {1}{2}}}k(\theta _{1}+\theta _{2}){\bigr )}.}$$ La suma de Clenshaw se puede aplicar en este caso ^{[ 5 ]} siempre que calculemos simultáneamente${\displaystyle m(\theta _{1})+m(\theta _{2})}$ y realizar una suma de matrices, $${\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})={\begin{bmatrix}(m(\theta _{1})+m(\theta _{2}))/2\\(m(\theta _{1})-m(\theta _{2}))/(\theta _{1}-\theta _{2})\end{bmatrix}}=C_{0}{\begin{bmatrix}\mu \\1\end{bmatrix}}+\sum _{k=1}^{n}C_{k}{\mathsf {F}}_{k}(\theta _{1},\theta _{2}),}$$ dónde $${\displaystyle {\begin{aligned}\delta &={\tfrac {1}{2}}(\theta _{1}-\theta _{2}),\\[1ex]\mu &={\tfrac {1}{2}}(\theta _{1}+\theta _{2}),\\[1ex]{\mathsf {F}}_{k}(\theta _{1},\theta _{2})&={\begin{bmatrix}\cos k\delta \sin k\mu \\{\dfrac {\sin k\delta }{\delta }}\cos k\mu \end{bmatrix}}.\end{aligned}}}$$ El primer elemento de${\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})}$es el valor promedio de${\displaystyle m}$y el segundo elemento es la pendiente media. ${\displaystyle {\mathsf {F}}_{k}(\theta _{1},\theta _{2})}$satisface la relación de recurrencia $${\displaystyle {\mathsf {F}}_{k+1}(\theta _{1},\theta _{2})={\mathsf {A}}(\theta _{1},\theta _{2}){\mathsf {F}}_{k}(\theta _{1},\theta _{2})-{\mathsf {F}}_{k-1}(\theta _{1},\theta _{2}),}$$ dónde $${\displaystyle {\mathsf {A}}(\theta _{1},\theta _{2})=2{\begin{bmatrix}\cos \delta \cos \mu &-\delta \sin \delta \sin \mu \\-\displaystyle {\frac {\sin \delta }{\delta }}\sin \mu &\cos \delta \cos \mu \end{bmatrix}}}$$ toma el lugar de${\displaystyle \alpha }$en la relación de recurrencia, y${\displaystyle \beta =-1}$. El algoritmo estándar de Clenshaw ahora se puede aplicar para producir $${\displaystyle {\begin{aligned}{\mathsf {B}}_{n+1}&={\mathsf {B}}_{n+2}={\mathsf {0}},\\[1ex]{\mathsf {B}}_{k}&=C_{k}{\mathsf {I}}+{\mathsf {A}}{\mathsf {B}}_{k+1}-{\mathsf {B}}_{k+2},\qquad \mathrm {for\ } n\geq k\geq 1,\\[1ex]{\mathsf {M}}(\theta _{1},\theta _{2})&=C_{0}{\begin{bmatrix}\mu \\1\end{bmatrix}}+{\mathsf {B}}_{1}{\mathsf {F}}_{1}(\theta _{1},\theta _{2}),\end{aligned}}}$$ dónde${\displaystyle {\mathsf {B}}_{k}}$son matrices de 2×2. Finalmente tenemos $${\displaystyle {\frac {m(\theta _{1})-m(\theta _{2})}{\theta _{1}-\theta _{2}}}={\mathsf {M}}_{2}(\theta _{1},\theta _{2}).}$$ Esta técnica puede utilizarse en el límite${\displaystyle \theta _{2}=\theta _{1}=\mu }$y${\displaystyle \delta =0}$calcular simultáneamente ${\displaystyle m(\mu )}$y el derivado${\displaystyle dm(\mu )/d\mu }$, siempre que, al evaluar${\displaystyle {\mathsf {F}}_{1}}$y${\displaystyle {\mathsf {A}}}$, tomamos${\displaystyle \lim _{\delta \to 0}(\sin k\delta )/\delta =k}$.