Editing Clenshaw algorithm (section)

==Clenshaw algorithm==

In full generality, the Clenshaw algorithm computes the weighted sum of a finite series of functions <math>\phi_k(x)</math>:
<math display="block">S(x) = \sum_{k=0}^n a_k \phi_k(x)</math>
where <math>\phi_k,\; k=0, 1, \ldots</math> is a sequence of functions that satisfy the linear recurrence relation
<math display="block">\phi_{k+1}(x) = \alpha_k(x)\,\phi_k(x) + \beta_k(x)\,\phi_{k-1}(x),</math>
where the coefficients <math>\alpha_k(x)</math> and <math>\beta_k(x)</math> are known in advance.

The algorithm is most useful when <math>\phi_k(x)</math> are functions that are complicated to compute directly, but <math>\alpha_k(x)</math> and <math>\beta_k(x)</math> are particularly simple.  In the most common applications, <math>\alpha(x)</math> does not depend on <math>k</math>, and <math>\beta</math> is a constant that depends on neither <math>x</math> nor <math>k</math>.

To perform the summation for given series of coefficients <math>a_0, \ldots, a_n</math>, compute the values <math>b_k(x)</math> by the "reverse" recurrence formula:
<math display="block"> \begin{align}
  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{align} </math>

Note that this computation makes no direct reference to the functions <math>\phi_k(x)</math>.  After computing <math>b_2(x)</math> and <math>b_1(x)</math>,
the desired sum can be expressed in terms of them and the simplest functions <math>\phi_0(x)</math> and <math>\phi_1(x)</math>:
<math display="block">S(x) = \phi_0(x)\,a_0 + \phi_1(x)\,b_1(x) + \beta_1(x)\,\phi_0(x)\,b_2(x).</math>

See Fox and Parker<ref name="FoxParker">{{Citation |first1=Leslie |last1=Fox |first2=Ian B. |last2=Parker |title=Chebyshev Polynomials in Numerical Analysis |publisher=Oxford University Press |year=1968 |isbn=0-19-859614-6}}</ref> for more information and stability analyses.