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;