Clenshaw algorithm
In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials.
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In numerical analysis, the Clenshaw algorithm, also called Clenshaw summation, is a recursive method to evaluate a linear combination of Chebyshev polynomials.[1][2] The method was published by Charles William Clenshaw in 1955. It is a generalization of Horner's method for evaluating a linear combination of monomials.
It generalizes to more than just Chebyshev polynomials; it applies to any class of functions that can be defined by a three-term recurrence relation.[3]
Clenshaw algorithm
edit edit sourceIn full generality, the Clenshaw algorithm computes the weighted sum of a finite series of functions ϕk(x): S(x)=∑k=0nakϕk(x) where ϕk,k=0,1,… is a sequence of functions that satisfy the linear recurrence relation ϕk+1(x)=αk(x)ϕk(x)+βk(x)ϕk−1(x), where the coefficients αk(x) and βk(x) are known in advance.
The algorithm is most useful when ϕk(x) are functions that are complicated to compute directly, but αk(x) and βk(x) are particularly simple. In the most common applications, α(x) does not depend on k, and β is a constant that depends on neither x nor k.
To perform the summation for given series of coefficients a0,…,an, compute the values bk(x) by the "reverse" recurrence formula: bn+1(x)=bn+2(x)=0,bk(x)=ak+αk(x)bk+1(x)+βk+1(x)bk+2(x).
Note that this computation makes no direct reference to the functions ϕk(x). After computing b2(x) and b1(x), the desired sum can be expressed in terms of them and the simplest functions ϕ0(x) and ϕ1(x): S(x)=ϕ0(x)a0+ϕ1(x)b1(x)+β1(x)ϕ0(x)b2(x).
See Fox and Parker[4] for more information and stability analyses.
Examples
edit edit sourceHorner as a special case of Clenshaw
edit edit sourceA particularly simple case occurs when evaluating a polynomial of the form S(x)=∑k=0nakxk. The functions are simply ϕ0(x)=1,ϕk(x)=xk=xϕk−1(x) and are produced by the recurrence coefficients α(x)=x and β=0.
In this case, the recurrence formula to compute the sum is bk(x)=ak+xbk+1(x) and, in this case, the sum is simply S(x)=a0+xb1(x)=b0(x), which is exactly the usual Horner's method.
Special case for Chebyshev series
edit edit sourceConsider a truncated Chebyshev series pn(x)=a0+a1T1(x)+a2T2(x)+⋯+anTn(x).
The coefficients in the recursion relation for the Chebyshev polynomials are α(x)=2x,β=−1, with the initial conditions T0(x)=1,T1(x)=x.
Thus, the recurrence is bk(x)=ak+2xbk+1(x)−bk+2(x) and the final results are b0(x)=a0+2xb1(x)−b2(x), pn(x)=12[a0+b0(x)−b2(x)].
An equivalent expression for the sum is given by pn(x)=a0+xb1(x)−b2(x).
Meridian arc length on the ellipsoid
edit edit sourceClenshaw summation is extensively used in geodetic applications.[2] A simple application is summing the trigonometric series to compute the meridian arc distance on the surface of an ellipsoid. These have the form m(θ)=C0θ+C1sinθ+C2sin2θ+⋯+Cnsinnθ.
Leaving off the initial C0θ term, the remainder is a summation of the appropriate form. There is no leading term because ϕ0(θ)=sin0θ=sin0=0.
The recurrence relation for sinkθ is sin(k+1)θ=2cosθsinkθ−sin(k−1)θ, making the coefficients in the recursion relation αk(θ)=2cosθ,βk=−1. and the evaluation of the series is given by bn+1(θ)=bn+2(θ)=0,bk(θ)=Ck+2cosθbk+1(θ)−bk+2(θ),for n≥k≥1. The final step is made particularly simple because ϕ0(θ)=sin0=0, so the end of the recurrence is simply b1(θ)sin(θ); the C0θ term is added separately: m(θ)=C0θ+b1(θ)sinθ.
Note that the algorithm requires only the evaluation of two trigonometric quantities cosθ and sinθ.
Difference in meridian arc lengths
edit edit sourceSometimes it necessary to compute the difference of two meridian arcs in a way that maintains high relative accuracy. This is accomplished by using trigonometric identities to write m(θ1)−m(θ2)=C0(θ1−θ2)+∑k=1n2Cksin(12k(θ1−θ2))cos(12k(θ1+θ2)). Clenshaw summation can be applied in this case[5] provided we simultaneously compute m(θ1)+m(θ2) and perform a matrix summation, 𝖬(θ1,θ2)=[(m(θ1)+m(θ2))/2(m(θ1)−m(θ2))/(θ1−θ2)]=C0[μ1]+∑k=1nCk𝖥k(θ1,θ2), where δ=12(θ1−θ2),μ=12(θ1+θ2),𝖥k(θ1,θ2)=[coskδsinkμsinkδδcoskμ]. The first element of 𝖬(θ1,θ2) is the average value of m and the second element is the average slope. 𝖥k(θ1,θ2) satisfies the recurrence relation 𝖥k+1(θ1,θ2)=𝖠(θ1,θ2)𝖥k(θ1,θ2)−𝖥k−1(θ1,θ2), where 𝖠(θ1,θ2)=2[cosδcosμ−δsinδsinμ−sinδδsinμcosδcosμ] takes the place of α in the recurrence relation, and β=−1. The standard Clenshaw algorithm can now be applied to yield 𝖡n+1=𝖡n+2=𝟢,𝖡k=Ck𝖨+𝖠𝖡k+1−𝖡k+2,for n≥k≥1,𝖬(θ1,θ2)=C0[μ1]+𝖡1𝖥1(θ1,θ2), where 𝖡k are 2×2 matrices. Finally we have m(θ1)−m(θ2)θ1−θ2=𝖬2(θ1,θ2). This technique can be used in the limit θ2=θ1=μ and δ=0 to simultaneously compute m(μ) and the derivative dm(μ)/dμ, provided that, in evaluating 𝖥1 and 𝖠, we take limδ→0(sinkδ)/δ=k.
See also
edit edit source- Horner scheme to evaluate polynomials in monomial form
- De Casteljau's algorithm to evaluate polynomials in Bézier form
References
edit edit source- ^ Clenshaw, C. W. (July 1955). "A note on the summation of Chebyshev series". Mathematical Tables and Other Aids to Computation. 9 (51): 118. doi:10.1090/S0025-5718-1955-0071856-0. ISSN 0025-5718. Note that this paper is written in terms of the Shifted Chebyshev polynomials of the first kind Tn∗(x)=Tn(2x−1). Wikipedia revision 1339479080, retrieved 2026-11-19
- ^ a b Tscherning, C. C.; Poder, K. (1982), "Some Geodetic applications of Clenshaw Summation" (PDF), Bolletino di Geodesia e Scienze Affini, 41 (4): 349–375, archived from the original (PDF) on 2007-06-12, retrieved 2012-08-02 Wikipedia revision 1339479080, retrieved 2026-11-19
- ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 5.4.2. Clenshaw's Recurrence Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8 Wikipedia revision 1339479080, retrieved 2026-11-19
- ^ Fox, Leslie; Parker, Ian B. (1968), Chebyshev Polynomials in Numerical Analysis, Oxford University Press, ISBN 0-19-859614-6 Wikipedia revision 1339479080, retrieved 2026-11-19
- ^ Karney, C. F. F. (2024). "The area of rhumb polygons". Stud. Geophys. Geod. 68 (3–4): 99–120. arXiv:2303.03219. doi:10.1007/s11200-024-0709-zAppendix B
{{cite journal}}: CS1 maint: postscript (link) Wikipedia revision 1339479080, retrieved 2026-11-19
Text derived from https://en.wikipedia.org/w/index.php?oldid=1339479080 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Clenshaw algorithm” publication date (×1) · confidence 0.95 revision URL