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 más que sólo 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 : donde es una secuencia de funciones que satisfacen la relación de recurrencia lineal donde los coeficientes y se conocen de antemano. ${\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 y son particularmente simples. En las aplicaciones más comunes, no depende de , y es una constante que no depende ni de 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 ellas 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).}$$

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

Ejemplos

Horner como caso especial de Clenshaw

Un caso particularmente simple ocurre cuando se evalúa un polinomio de la forma Las funciones son simplemente y son producidas por los coeficientes de recurrencia y . $${\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 y, en este caso, la suma es simplemente que es exactamente el método habitual de Horner . $${\displaystyle b_{k}(x)=a_{k}+xb_{k+1}(x)}$$ $${\displaystyle S(x)=a_{0}+xb_{1}(x)=b_{0}(x),}$$

Caso especial de la serie Chebyshev

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 recursión para los polinomios de Chebyshev están con las condiciones iniciales $${\displaystyle \alpha (x)=2x,\quad \beta =-1,}$$ $${\displaystyle T_{0}(x)=1,\quad T_{1}(x)=x.}$$

Por lo tanto, la recurrencia es y la suma final 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 (observe el coeficiente duplicado a ₀ ) seguido de $${\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].}$$

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 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 .}$$

Si se omite el término inicial, el resto es una suma de la forma adecuada. No hay 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 hacer los coeficientes en la relación de recursión y la evaluación de la serie está dada por El paso final se hace particularmente simple porque , por lo que el final de la recurrencia es simplemente ; el término se agrega por separado: $${\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 solo requiere la evaluación de dos cantidades trigonométricas y . ${\displaystyle \cos \theta }$ ${\displaystyle \sin \theta }$

Diferencia en las longitudes de los arcos meridianos

A veces es necesario calcular la diferencia de dos arcos meridianos de una manera que mantenga una alta precisión relativa. Esto se logra utilizando identidades trigonométricas para escribir La suma de Clenshaw se puede aplicar en este caso ^[5] siempre que calculemos y realicemos simultáneamente una suma matricial, donde El primer elemento de es el valor promedio de y el segundo elemento es la pendiente promedio. satisface la relación de recurrencia donde toma el lugar de en la relación de recurrencia, y . El algoritmo estándar de Clenshaw ahora se puede aplicar para obtener donde son matrices 2×2. Finalmente tenemos Esta técnica se puede utilizar en el límite y para calcular simultáneamente y la derivada , siempre que, al evaluar y , tomemos . $${\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 )}.}$$ ${\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}).}$$ ${\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}$

Véase también

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

Referencias

1. Clenshaw, CW (julio de 1955). "Una nota sobre la suma de las series de Chebyshev". Tablas matemáticas y otras ayudas para el cálculo . 9 (51): 118. doi : 10.1090/S0025-5718-1955-0071856-0 . ISSN  0025-5718. Téngase en cuenta que este artículo está escrito en términos de los polinomios de Chebyshev desplazados del primer tipo . ${\displaystyle T_{n}^{*}(x)=T_{n}(2x-1)}$
2. Tscherning, CC; Poder, K. (1982), "Algunas aplicaciones geodésicas de la suma de Clenshaw" (PDF) , Bolletino di Geodesia e Scienze Affini , 41 (4): 349–375, archivado desde el original (PDF) el 2007-06-12 , consultado el 2012-08-02
3. Press, 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 computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8
4. Fox, Leslie; Parker, Ian B. (1968), Polinomios de Chebyshev en análisis numérico , Oxford University Press, ISBN 0-19-859614-6
5. ( 2024). "El área de los polígonos loxodrómicos". Stud. Geophys. Geod . 68. doi : 10.1007/s11200-024-0709-z Apéndice B{{cite journal}}: CS1 maint: postscript (link)