NUMAL Section 2.2.2.2

BEGIN SECTION : 2.2.2.2 (December, 1978)

AUTHOR:        C.G. VAN DER LAAN.

CONTRIBUTORS:  C.G. VAN DER LAAN, M. VOORINTHOLT.

INSTITUTE:     REKENCENTRUM RIJKSUNIVERSITEIT GRONINGEN.

RECEIVED:      780601.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS FOUR PROCEDURES ABOUT CHEBYSHEV POLYNOMIALS
    OF THE FIRST KIND:
    CHEPOLSUM:    EVALUATES A (FINITE) SUM OF CHEBYSHEV POLYNOMIALS,
    ODDCHEPOLSUM: EVALUATES A (FINITE) SUM OF CHEBYSHEV POLYNOMIALS
                  OF ODD DEGREE,
    CHEPOL:       EVALUATES A CHEBYSHEV POLYNOMIAL,
    ALLCHEPOL:    EVALUATES ALL CHEBYSHEV POLYNOMIALS WITH DEGREE LESS
                  THAN A GIVEN POSITIVE INTEGER.

KEYWORDS:

    (FINITE) SUM OF (SHIFTED) CHEBYSHEV POLYNOMIALS OF THE FIRST KIND,
    GOERTZEL,WATT,CLENSHAW,GENERALIZED HORNER ALGORITHM,
    LINEAR THREE TERM (INHOMOGENEOUS) RECURRENCE RELATION.

REFERENCES:

    CLENSHAW, C.W. (1962):
    CHEBYSHEV SERIES FOR MATHEMATICAL FUNCTIONS.
    MATH. TAB. NAT. PHYS. LAB. 5, LONDON. HMO.

    FOX, L. & I.B. PARKER (1972):
    CHEBYSHEV POLYNOMIALS IN NUMERICAL ANALYSIS.
    OXFORD UNIVERSITY PRESS.

    RIVLIN, T.J. (1974):
    THE CHEBYSHEV POLYNOMIALS.
    WILEY.

    STOER,J.(1972):
    EINFUEHRUNG IN DIE NUMERISCHE MATHEMATIK 1.
    HEIDELBERGER TASCHENBUECHER 105,SPRINGER-VERLAG.


SUBSECTION: CHEPOLSUM.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
    "REAL""PROCEDURE"CHEPOLSUM(N,X,A);
    "VALUE"N,X;"INTEGER"N;"REAL"X;"ARRAY"A;
    "CODE"31046;

    CHEPOLSUM:=THE VALUE OF THE CHEBYSHEV SUM
             A[0] + A[1]*T[1](X) + .... + A[N]*T[N](X),
             WHERE T[1](X),....,T[N](X) ARE CHEBYSHEV POLYNOMIALS
             OF THE FIRST KIND, OF DEGREE 1,....,N, RESPECTIVELY.

    THE MEANING OF THE FORMAL PARAMETERS IS :
    N : <ARITHMETIC EXPRESSION>;
        ENTRY: THE DEGREE OF THE POLYNOMIAL REPRESENTED BY THE
               CHEBYSHEV SUM (N>=0);
    X : <ARITHMETIC EXPRESSION>;
        ENTRY: THE ARGUMENT OF THE CHEBYSHEV POLYNOMIALS , ABS(X)<=1;
    A : <ARRAY IDENTIFIER>;
        "ARRAY" A[0:N];
        ENTRY: THE COEFFICIENTS OF THE CHEBYSHEV SUM MUST BE GIVEN IN
               ARRAY A, WHERE A[K] IS THE COEFFICIENT OF THE CHEBYSHEV
               POLYNOMIAL OF DEGREE K, 0<=K<=N.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N.

METHOD AND PERFORMANCE:

         N                          N  / 2*X  1 \ K  / A[K] \
        SUM A[K]*T[K](X) = (1,X) * SUM [        ]  * [      ]
        K=0                        K=0 \  -1  0 /    \  0   /
    WE USE THE CLENSHAW OR GENERALIZED HORNER ALGORITHM:
                         N
                        SUM A[K]*T[K](X) = (1,X) *
                        K=0

    / / A[0] \   / 2*X 1 \   / / A[1] \      / 2*X 1 \   / A[N] \ \  \
    [ [      ] + [       ] * [ [      ] +..+ [       ] * [      ] ]..].
    \ \  0   /   \ -1  0 /   \ \  0   /      \  -1 0 /   \  0   / /  /

    THIS PROCEDURE MAY BE USED:
    - TO EVALUATE THE SUM OF CHEBYSHEV POLYNOMIALS OF EVEN DEGREE
         N
        SUM A[K]*T[2*K](X) ,
        K=0
      BY THE CALL OF
        CHEPOLSUM(N,"IF" ABS(X)<ARREB "THEN" -1 "ELSE" 2*X*X-1,A)
      BECAUSE OF
        T[2*K](X) = T[K](T[2](X));
      (ARREB DENOTES THE MACHINE PRECISION)
    - TO EVALUATE THE SUM OF SHIFTED CHEBYSHEV POLYNOMIALS FOR 0<=X<=1
         N
        SUM A[K]*T'[K](X) ,
        K=0
      BY THE CALL OF
        CHEPOLSUM(N,2*X-1,A)
      BECAUSE OF
        T'[K](X) = T[K](2*X-1).

EXAMPLE OF USE :

    THE POLYNOMIAL : 1 + 1/2*T[1](X) + 1/4*T[2](X) IS EVALUATED FOR
    X = -1,0,1, WHERE T[1](X) AND T[2](X) ARE THE CHEBYSHEV POLYNOMIALS
    OF FIRST AND SECOND DEGREE, RESPECTIVELY.

    "BEGIN""ARRAY"A[0:2];
           A[2]:=.25;A[1]:=.5;A[0]:=1;
           OUTPUT(61,"("3(BZ.DD)")",CHEPOLSUM(2,-1,A),CHEPOLSUM(2,0,A),
           CHEPOLSUM(2,1,A))
    "END"

        .75  .75 1.75


SUBSECTION: ODDCHEPOLSUM.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
    "REAL""PROCEDURE" ODDCHEPOLSUM(N,X,A);
    "VALUE"N,X;"INTEGER"N;"REAL"X;"ARRAY"A;
    "CODE"31059;

    ODDCHEPOLSUM:= THE VALUE OF THE CHEBYSHEV SUM
             A[1]*T[1](X) + .... + A[N]*T[2*N+1](X),
             WHERE T[1](X),....,T[2*N+1](X) ARE CHEBYSHEV POLYNOMIALS
             OF THE FIRST KIND, OF (ODD) DEGREE 1,....,2*N+1.

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N : <ARITHMETIC EXPRESSION>;
        ENTRY: THE DEGREE OF THE POLYNOMIAL REPRESENTED BY
               THE CHEBYSHEV SUM IS 2*N+1 (N>=0);
    X : <ARITHMETIC EXPRESSION>;
        ENTRY: THE ARGUMENT OF THE CHEBYSHEV POLYNOMIALS, ABS(X)<=1;
    A : <ARRAY IDENTIFIER>;
        "ARRAY" A[0:N];
        ENTRY: THE COEFFICIENTS OF THE CHEBYSHEV SUM MUST BE GIVEN IN
               ARRAY A, WHERE A[K] IS THE COEFFICIENT OF THE CHEBYSHEV
               POLYNOMIAL OF DEGREE 2*K+1, 0<=K<=N.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N.

METHOD AND PERFORMANCE:

    FROM THE REPRESENTATION, FOR ABS(X)<=1,
     N                                   N  / 2*T[2](X) -1 \ K  /A[K] \
    SUM A[K]*T[2*K+1](X) = X * (1,-1) * SUM [              ]  * [     ]
    K=0                                 K=0 \    1       0 /    \  0  /
    WE USE THE CLENSHAW OR GENERALIZED HORNER ALGORITHM:
                        N                                  / / A[0] \
                       SUM A[K]*T[2*K+1](X) = X * (1,-1) * [ [      ] +
                       K=0                                 \ \   0  /

    / 2*T[2](X) -1 \   / / A[1] \     / 2*T[2](X) -1 \   / A[N] \ \  \
    [              ] * [ [      ]+...+[              ] * [      ] ]..].
    \     1      0 /   \ \   0  /     \     1      0 /   \   0  / /  /

    THIS PROCEDURE MAY BE USED TO EVALUATE THE SUM OF SHIFTED CHEBYSHEV
    POLYNOMIALS OF ODD DEGREE FOR 0<=X<=1,
         N
        SUM A[K]*T'[2*K+1](X) ,
        K=0
    BY THE CALL OF
        ODDCHEPOLSUM(N,2*X-1,A)
    BECAUSE OF
        T'[K](X) = T[K](2*X-1).

EXAMPLE OF USE:

    THE POLYNOMIAL 1/2*T[1](X) + 1/5*T[3](X) IS EVALUATED FOR X=-1,0,1,
    WHERE T[1](X) AND T[3](X) ARE CHEBYSHEV POLYNOMIALS OF THE FIRST
    AND THIRD DEGREE, RESPECTIVELY.

    "BEGIN"
         "ARRAY"A[0:1];
         A[1]:=.2;A[0]:=.5;
         OUTPUT(61,"("/,3(B,-Z.DD)")",ODDCHEPOLSUM(1,-1,A),
                                      ODDCHEPOLSUM(1,0,A),
                                      ODDCHEPOLSUM(1,1,A));
    "END"

    -.70  .00  .70


SUBSECTION: CHEPOL.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
    "REAL""PROCEDURE"CHEPOL(N,X);
    "VALUE"N,X;"INTEGER"N;"REAL"X;
    "CODE"31042;

    CHEPOL:=THE VALUE OF THE CHEBYSHEV POLYNOMIAL OF THE FIRST KIND OF
             DEGREE N FOR THE ARGUMENT X.

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N : <ARITHMETIC EXPRESSION>;
        ENTRY: THE DEGREE OF THE POLYNOMIAL (N>=0);
    X : <ARITHMETIC EXPRESSION>;
        ENTRY: THE ARGUMENT OF THE CHEBYSHEV POLYNOMIAL, ABS(X)<=1.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N.

METHOD AND PERFORMANCE: SEE ALLCHEPOL (NEXT SUBSECTION).

EXAMPLE OF USE: SEE NEXT SUBSECTION.


SUBSECTION: ALLCHEPOL.

CALLING SEQUENCE:

    THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
    "PROCEDURE"ALLCHEPOL(N,X,T);
    "VALUE"N,X;"INTEGER"N;"REAL"X;"REAL""ARRAY"T;
    "CODE"31043;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N : <ARITHMETIC EXPRESSION>;
        ENTRY: THE DEGREE OF THE LAST POLYNOMIAL (N>=0);
    X : <ARITHMETIC EXPRESSION>;
        ENTRY: THE ARGUMENT OF THE CHEBYSHEV POLYNOMIALS, ABS(X)<=1;
    T : <ARRAY IDENTIFIER>;
        "ARRAY" T[0:N];
        EXIT:  THE VALUES OF THE CHEBYSHEV POLYNOMIALS OF THE FIRST
               KIND OF DEGREES 0,1,...,N , FOR THE ARGUMENT X, ARE
               DELIVERED IN T[0],T[1],...,T[N], RESPECTIVELY.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N.

METHOD AND PERFORMANCE:

    FOR A DESCRIPTION OF THE ALGORITHM  SEE STOER,1972,P.21.
    THE MAXIMUM (ABSOLUTE) VALUE OF THE CHEBYSHEV POLYNOMIAL
    EQUALS 1 AS A NORMALIZATION.
    AN UPPER BOUND FOR THE (ABSOLUTE) ERROR IS A QUADRATIC FUNCTION
    OF THE DEGREE OF THE CHEBYSHEV POLYNOMIAL.THIS UPPER BOUND IS A
    ROUGH OVER-ESTIMATE FOR THE SPECIAL CASE ABS(X)<.5 (STOER,1972,
    P. 21-24).

EXAMPLE OF USE :

    BY THE PROCEDURE (ALL)CHEPOL THE CHEBYSHEV POLYNOMIALS OF THE FIRST
    KIND OF DEGREES 0,1,2 ARE EVALUATED AT -1,0,1.

    "BEGIN"
        "ARRAY"T[0:2];
        ALLCHEPOL(2,-1,T);OUTPUT(61,"("/,3(-DB)")",T[0],T[1],T[2]);
        ALLCHEPOL(2, 0,T);OUTPUT(61,"("/,3(-DB)")",T[0],T[1],T[2]);
        ALLCHEPOL(2, 1,T);OUTPUT(61,"("/,3(-DB)")",T[0],T[1],T[2]);
        OUTPUT(61,"("/,3(/,-D)")",CHEPOL(2,-1),CHEPOL(2,0),CHEPOL(2,1))
    "END"

       1 -1  1
       1  0 -1
       1  1  1

       1
      -1
       1

SOURCE TEXT(S):

"CODE" 31046;
"CODE" 31059;

"CODE" 31042;

"CODE" 31043;