Algoritmo de Clenshaw

En análisis numérico , el algoritmo de Clenshaw , también llamado suma de Clenshaw , es un método recursivo para evaluar una combinación lineal de polinomios de Chebyshev . ^{[1] [2]} El método fue publicado por Charles William Clenshaw en 1955. Es una generalización del método de Horner para evaluar una combinación lineal de monomios .

Se generaliza a algo más que polinomios de Chebyshev; se aplica a cualquier clase de funciones que puedan definirse mediante una relación de recurrencia de tres términos . ^[3]

Algoritmo de Clenshaw

En general, el algoritmo de Clenshaw calcula la suma ponderada de una serie finita de funciones : ${\displaystyle \phi _{k}(x)}$

$${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}\phi _{k}(x)}$$

${\displaystyle \phi _{k},\;k=0,1,\ldots }$

$${\displaystyle \phi _{k+1}(x)=\alpha _{k}(x)\,\phi _{k}(x)+\beta _{k}(x)\,\phi _{k-1}(x),}$$

${\displaystyle \alpha _{k}(x)}$ ${\displaystyle \beta _{k}(x)}$

El algoritmo es más útil cuando se trata de funciones que son complicadas de calcular directamente, pero que son particularmente simples. En las aplicaciones más comunes, no depende de y es una constante que no depende de ni ni de . ${\displaystyle \phi _{k}(x)}$ ${\displaystyle \alpha _{k}(x)}$ ${\displaystyle \beta _{k}(x)}$ ${\displaystyle \alpha (x)}$ ${\displaystyle k}$ ${\displaystyle \beta }$ ${\displaystyle x}$ ${\displaystyle k}$

Para realizar la suma de una serie dada de coeficientes , calcule los valores mediante la fórmula de recurrencia "inversa": ${\displaystyle a_{0},\ldots ,a_{n}}$ ${\displaystyle b_{k}(x)}$

$${\displaystyle {\begin{aligned}b_{n+1}(x)&=b_{n+2}(x)=0,\\b_{k}(x)&=a_{k}+\alpha _{k}(x)\,b_{k+1}(x)+\beta _{k+1}(x)\,b_{k+2}(x).\end{aligned}}}$$

Tenga en cuenta que este cálculo no hace referencia directa a las funciones . Después de calcular y , la suma deseada se puede expresar en términos de ellos y de las funciones más simples y : ${\displaystyle \phi _{k}(x)}$ ${\displaystyle b_{2}(x)}$ ${\displaystyle b_{1}(x)}$ ${\displaystyle \phi _{0}(x)}$ ${\displaystyle \phi _{1}(x)}$

$${\displaystyle S(x)=\phi _{0}(x)\,a_{0}+\phi _{1}(x)\,b_{1}(x)+\beta _{1}(x)\,\phi _{0}(x)\,b_{2}(x).}$$

Véase Fox y Parker ^[4] para obtener más información y análisis de estabilidad.

Ejemplos

Horner como un caso especial de Clenshaw

Un caso particularmente simple ocurre cuando se evalúa un polinomio de la forma

$${\displaystyle S(x)=\sum _{k=0}^{n}a_{k}x^{k}.}$$

$${\displaystyle {\begin{aligned}\phi _{0}(x)&=1,\\\phi _{k}(x)&=x^{k}=x\phi _{k-1}(x)\end{aligned}}}$$

${\displaystyle \alpha (x)=x}$ ${\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)}$$

$${\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x),}$$

método habitual de Horner

Caso especial para la serie Chebyshev

Consideremos una serie truncada de Chebyshev

$${\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 recursividad para los polinomios de Chebyshev son

$${\displaystyle \alpha (x)=2x,\quad \beta =-1,}$$

$${\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.}$$

Así, la recurrencia es

$${\displaystyle b_{k}(x)=a_{k}+2xb_{k+1}(x)-b_{k+2}(x)}$$

$${\displaystyle p_{n}(x)=a_{0}+xb_{1}(x)-b_{2}(x).}$$

Una forma de evaluar esto es continuar la recurrencia un paso más y calcular

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

) _seguido

$${\displaystyle p_{n}(x)={\tfrac {1}{2}}\left[a_{0}+b_{0}(x)-b_{2}(x)\right].}$$

Longitud del arco meridiano en el elipsoide

La suma de Clenshaw se utiliza ampliamente en aplicaciones geodésicas . ^[2] Una aplicación sencilla es sumar la serie trigonométrica para calcular la distancia del arco del meridiano en la superficie de un elipsoide. Estos 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 término inicial , el resto es una suma de la forma apropiada. No hay un término principal porque . ${\displaystyle C_{0}\,\theta }$ ${\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 ,}$$

$${\displaystyle \alpha _{k}(\theta )=2\cos \theta ,\quad \beta _{k}=-1.}$$

$${\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}}}$$

${\displaystyle \phi _{0}(\theta )=\sin 0=0}$ ${\displaystyle b_{1}(\theta )\sin(\theta )}$ ${\displaystyle C_{0}\,\theta }$

$${\displaystyle m(\theta )=C_{0}\,\theta +b_{1}(\theta )\sin \theta .}$$

Tenga en cuenta que el algoritmo requiere sólo la evaluación de dos cantidades trigonométricas y . ${\displaystyle \cos \theta }$ ${\displaystyle \sin \theta }$

Diferencia en longitudes de arco de meridianos

A veces es necesario calcular la diferencia de dos arcos de meridianos de manera que se mantenga una alta precisión relativa. Esto se logra usando 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 )}.}$$

^[5] ${\displaystyle m(\theta _{1})+m(\theta _{2})}$

$${\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}),}$$

$${\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}}}$$

${\displaystyle {\mathsf {M}}(\theta _{1},\theta _{2})}$ ${\displaystyle m}$ ${\displaystyle {\mathsf {F}}_{k}(\theta _{1},\theta _{2})}$

$${\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}),}$$

$${\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}}}$$

${\displaystyle \alpha }$ ${\displaystyle \beta =-1}$

$${\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}}}$$

${\displaystyle {\mathsf {B}}_{k}}$

$${\displaystyle {\frac {m(\theta _{1})-m(\theta _{2})}{\theta _{1}-\theta _{2}}}={\mathsf {M}}_{2}(\theta _{1},\theta _{2}).}$$

límitederivada ${\displaystyle \theta _{2}=\theta _{1}=\mu }$ ${\displaystyle \delta =0}$ ${\displaystyle m(\mu )}$ ${\displaystyle dm(\mu )/d\mu }$ ${\displaystyle {\mathsf {F}}_{1}}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle \lim _{\delta \to 0}(\sin k\delta )/\delta =k}$

Ver también

• Esquema de Horner para evaluar polinomios en forma monomio
• Algoritmo de De Casteljau para evaluar polinomios en forma de Bézier

Referencias

1. Clenshaw, CW (julio de 1955). "Una nota sobre el resumen de la serie de Chebyshev". Tablas matemáticas y otras ayudas a la computación . 9 (51): 118. doi : 10.1090/S0025-5718-1955-0071856-0 . ISSN  0025-5718. Tenga en cuenta que este artículo está escrito en términos de los polinomios desplazados de Chebyshev de primera especie . ${\displaystyle T_{n}^{*}(x)=T_{n}(2x-1)}$
2. Tscherning, CC; Poder, K. (1982), "Algunas aplicaciones geodésicas de Clenshaw Summation" (PDF) , Bolletino di Geodesia e Scienze Affini , 41 (4): 349–375, archivado desde el original (PDF) el 12 de junio de 2007 , Consultado el 2 de agosto de 2012.
3. Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 5.4.2. Fórmula de recurrencia de Clenshaw", Recetas numéricas: el arte de la informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8
4. Zorro, Leslie; Parker, Ian B. (1968), Polinomios de Chebyshev en análisis numérico , Oxford University Press, ISBN 0-19-859614-6
5. Karney, CFF (2014), Evaluación Clenshaw de sumas diferenciadas