NUMAL Section 2.2.3.1

BEGIN SECTION : 2.2.3.1 (October, 1974)

AUTHOR:     C.G. VAN DER LAAN.

INSTITUTE:  RIJKSUNIVERSITEIT GRONINGEN.

RECEIVED:   740701.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS THE PROCEDURES:
    SINSER FOR EVALUATING A SINE SERIES;
    COSSER FOR EVALUTING A COSINE SERIES;
    FOUSER,FOUSER1,FOUSER2 FOR EVALUATING A FOURIER SERIES
    (IN FOUSER THE SERIES IS RESTRICTED TO A SERIES WITH SINE
     COEFFICIENTS EQUAL TO COSINE COEFFICIENTS);
    COMFOUSER,COMFOUSER1,COMFOUSER2 FOR EVALUATING A COMPLEX FOURIER
    SERIES
    (IN COMFOUSER THE SERIES IS RESTRICTED TO A SERIES WITH REAL
    COEFFICIENTS).

KEYWORDS:

    FINITE FOURIER SERIES EVALUATION,
    TRIGONOMETRIC POLYNOMIAL EVALUATION,
    GOERTZEL,WATT,CLENSHAW,REINSCH ALGORITHM,
    LINEAR THREE-TERM INHOMOGENEOUS RECURRENCE RELATION.


SUBSECTION : SINSER.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE"SINSER(N,THETA,B);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA;"ARRAY"B;
    "CODE" 31090;

    SINSER:= THE VALUE OF THE SINE SERIES
             B[1]*SIN(THETA)+...+B[N]*SIN(N*THETA).

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE NUMBER OF TERMS IN THE SINE SERIES;
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE SINE SERIES;
    B:      <ARRAY IDENTIFIER>;
            "ARRAY"B[1:N];
            ENTRY: THE COEFFICIENTS OF THE SINE SERIES.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: N MULTIPLICATIONS; 3N ADDITIONS;
               3 SINE/COSINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : COSSER.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE"COSSER(N,THETA,A);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA;"ARRAY"A;
    "CODE" 31091;

    COSSER:= THE VALUE OF THE COSINE SERIES
             A[0]+A[1]*COS(THETA)+...+A[N]*COS(N*THETA).

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE TRIGONOMETRIC POLYNOMIAL.
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE COSINE SERIES.
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[0:N];
            ENTRY: THE COEFFICIENTS OF THE COSINE SERIES.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
             (IN FIRST ORDER: N MULTIPLICATIONS; 3N ADDITIONS;
              2 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : FOUSER.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE"FOUSER (N,THETA,A);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA;"ARRAY"A;
    "CODE" 31092;

    FOUSER := THE VALUE OF THE FOURIER SERIES
              A[0]+A[1]*(COS(THETA)+SIN(THETA))+...+A[N]*(COS(N*THETA)
              +SIN(N*THETA)).

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE TRIGONOMETRIC POLYNOMIAL;
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[0:N];
            ENTRY: THE COEFFICIENTS OF THE (FINITE) FOURIER SERIES.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: N MULTIPLICATIONS; 3N ADDITIONS;
               3 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : FOUSER1.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE"FOUSER1(N,THETA,A,B);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA;"ARRAY"A,B;
    "CODE" 31093;

    FOUSER1:= THE VALUE OF THE FOURIER SERIES
              A[0]+A[1]*COS(THETA)+B[1]*SIN(THETA)+...
              +A[N]*COS(N*THETA)+B[N]*SIN(N*THETA).

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE TRIGONOMETRIC POLYNOMIAL;
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    A,B:    <ARRAY IDENTIFIER>;
            "ARRAY"A[0:N],B[1:N];
            ENTRY: THE COEFFICIENTS OF THE (FINITE) FOURIER SERIES,
                   WITH A[K] COEFFICIENT OF COS(K*THETA), (K=0,...,N)
                   AND  B[K] COEFFICIENT OF SIN(K*THETA), (K=1,...,N).

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: 4N MULTIPLICATIONS; 4N ADDITIONS;
               2 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : FOUSER2.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "REAL""PROCEDURE"FOUSER2(N,THETA,A,B);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA;"ARRAY"A,B;
    "CODE" 31094;

    FOUSER2:= THE VALUE OF THE FOURIER SERIES
              A[0]+A[1]*COS(THETA)+B[1]*SIN(THETA)+...
              +A[N]*COS(N*THETA)+B[N]*SIN(N*THETA).

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE TRIGONOMETRIC POLYNOMIAL;
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    A,B:    <ARRAY IDENTIFIER>;
            "ARRAY"A[0:N],B[1:N];
            ENTRY: THE COEFFICIENTS OF THE (FINITE) FOURIER SERIES,
                   WITH A[K] COEFFICIENT OF COS(K*THETA), (K=0,...,N)
                   AND  B[K] COEFFICIENT OF SIN(K*THETA), (K=1,...,N).

PROCEDURES USED: SINSER = CP31090,
                 COSSER = CP31091.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: 2N MULTIPLICATIONS; 6N ADDITIONS;
               6 COSINE/SINE EVALUATIONS).

LANGUAGE : ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : COMFOUSER.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE"COMFOUSER (N,THETA,A,RR,RI);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA,RR,RI;"ARRAY"A;
    "CODE" 31095;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE POLYNOMIAL IN EXP(I*THETA);
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    A:      <ARRAY IDENTIFIER>;
            "ARRAY"A[0:N];
            ENTRY: THE REAL COEFFICIENTS A[K] (K=0,...,N) IN THE SERIES
                   FN(THETA)=A[0]+A[1]*EXP(I*THETA)+...+A[N]*EXP(I*
                   THETA)**N, MUST BE GIVEN IN ARRAY A;
    RR,RI:  <VARIABLE>;
            EXIT:  THE REAL PART AND THE IMAGINARY PART OF FN(THETA)
                   ARE DELIVERED IN RR AND RI, RESPECTIVELY.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER:  N MULTIPLICATIONS; 3N ADDITIONS;
               3 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : COMFOUSER1.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE"COMFOUSER1(N,THETA,AR,AI,RR,RI);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA,RR,RI;"ARRAY"AR,AI;
    "CODE" 31096;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE POLYNOMIAL IN EXP(I*THETA);
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    AR,AI:  <ARRAY IDENTIFIER>;
            "ARRAY"AR,AI[0:N];
            ENTRY: THE REAL PART AND THE IMAGINARY PART OF THE COMPLEX
                   COEFFICIENTS C[K] (K=0,...,N) IN THE SERIES
                   FN(THETA)=C[0]+C[1]*EXP(I*THETA)+...+C[N]*EXP(I*
                             THETA)**N
                   MUST BE GIVEN IN ARRAY AR AND AI, RESPECTIVELY;
    RR,RI:  <VARIABLE>;
            EXIT:  THE REAL PART AND THE IMAGINARY PART OF FN(THETA)
                   ARE DELIVERED IN RR AND RI, RESPECTIVELY.

PROCEDURES USED: NONE.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: 4N MULTIPLICATIONS; 4N ADDITIONS;
               2 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORMANCE : SEE COMFOUSER2 (THIS SECTION).


SUBSECTION : COMFOUSER2.

CALLING SEQUENCE:

    THE HEADING OF THE PROCEDURE READS:
    "PROCEDURE"COMFOUSER2(N,THETA,AR,AI,RR,RI);
    "VALUE"N,THETA;"INTEGER"N;"REAL"THETA,RR,RI;"ARRAY"AR,AI;
    "CODE" 31097;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            ENTRY: THE DEGREE OF THE POLYNOMIAL IN EXP(I*THETA);
    THETA:  <ARITHMETIC EXPRESSION>;
            ENTRY: THE ARGUMENT OF THE FOURIER SERIES;
    AR,AI:  <ARRAY IDENTIFIER>;
            "ARRAY"AR,AI[0:N];
            ENTRY: THE REAL PART AND THE IMAGINARY PART OF THE COMPLEX
                   COEFFICIENTS C[K] (K=0,...,N) IN THE SERIES
                   FN(THETA)=C[0]+C[1]*EXP(I*THETA)+...+C[N]*EXP(I*
                             THETA)**N
                   MUST BE GIVEN IN ARRAY AR AND AI, RESPECTIVELY;
    RR,RI:  <VARIABLE>;
            EXIT:  THE REAL PART AND THE IMAGINARY PART OF FN(THETA)
                   ARE DELIVERED IN RR AND RI, RESPECTIVELY.

PROCEDURES USED: COMFOUSER= CP31095.

RUNNING TIME: PROPORTIONAL TO N
              (IN FIRST ORDER: 2N MULTIPLICATIONS; 6N ADDITIONS;
               6 COSINE/SINE EVALUATIONS).

LANGUAGE: ALGOL 60.

METHOD AND PERFORANCE:

    FOR THE EVALUATION OF A FINITE FOURIER SERIES
    (=TRIGONOMETRIC POLYNOMIAL OF DEGREE N SEE POLYA AND SZEGOE, 1971,
    P. 76)
    FN(THETA)=A[0]+A[1]*COS(THETA)+B[1]*SIN(THETA)+...+
              A[N]*COS(N*THETA)+B[N]*SIN(N*THETA),
    TWO ALGORITHMS ARE USED:

    1.  HORNER SCHEME
        LET C[K]=A[K]+I*B[K], K=0,...,N
        AND Z=EXP(-I*THETA)
        THEN
            FN(THETA)=RE(C[0]+C[1]*Z+...+C[N]*Z**N).
        THE ALGORITHM IS GIVEN BY:
            P:=C[N]
            P:=P*Z+C[K], K=N-1,...,0
            FN(THETA):=RE(P).
        (FOUSER1)
    2.  A COMBINATION OF THE CLENSHAW ALGORITHM (SEE GENTLEMAN(1969,II)
        , VAN DER LAAN, LUKE(1969, P.327-329) OR STOER(1972, P.62,63))
        AND THE MODIFICATION OF REINSCH (SEE REINSCH(1967), VAN DER
        LAAN, STOER(1972, P.64,65)).
        (SINSER,COSSER,FOUSER,FOUSER2)
    A MODIFICATION OF THE IDEA OF NEWBERY IS NOT IMPLEMENTED BECAUSE
    OF THE INTRODUCTION OF SINE (COSINE) TERMS IN A COSINE (SINE)
    SERIES AND THE INEFFICIENCY OF THE ALGORITHM (SEE VAN DER
    LAAN OR NEWBERY(1973)).

    FOR THE EVALUATION OF A FINITE COMPLEX FOURIER SERIES
    FN(THETA)=AR[0]+I*AI[0]+(AR[1]+I*AI[1])*EXP(I*THETA)+...
              +(AR[N]+I*AI[N])*EXP(I*THETA)**N,
    TWO ALGORITHMS, IN REAL ARITHMETIC, ARE USED:
    1. HORNER SCHEME
       LET C[K]=AR[K]+I*AI[K], K=0,...,N
       AND Z=EXP(I*THETA)
       THEN
           FN(THETA)=C[0]+C[1]*Z+...+C[N]*Z**N.
       THE ALGORITHM IS GIVEN BY
           P:=C[N]
           P:=P*Z+C[K], K=N-1,N-2,...,0
           FN(THETA):=P.
       (COMFOUSER1)
    2. A COMBINATION OF THE CLENSHAW ALGORITHM AND THE MODIFICATION OF
       REINSCH.
       LET CAR=AR[0]+AR[1]*COS(THETA)+...+AR[N]*COS(N*THETA),
           SAI=      AI[1]*SIN(THETA)+...+AI[N]*SIN(N*THETA),
           SAR=      AR[1]*SIN(THETA)+...+AR[N]*SIN(N*THETA),
           CAI=AI[0]+AI[1]*COS(THETA)+...+AI[N]*COS(N*THETA)
       THEN FN(THETA)=CAR-SAI+I*(SAR+CAI).
       (COMFOUSER,COMFOUSER2)
    THE HORNER SCHEME IS IMPLEMENTED BECAUSE OF THE SIMPLICITY OF
    THE ALGORITHM (ALTHOUGH THIS ALGORITHM IS LESS EFFICIENT THAN THE
    GOERTZEL/WATT/CLENSHAW/REINSCH ALGORITHM) AND THE STABLE NATURE
    OF ORTHOGONAL TRANSFORMATIONS.
    A COMBINATION OF THE ALGORITHM OF GOERTZEL/WATT/CLENSHAW AND THE
    MODIFICATION OF REINSCH IS IMPLEMENTED BECAUSE OF THE EFFICIENCY
    OF THE GWC ALGORITHM AND THE STABILITY OF THE MODIFICATION OF
    REINSCH, ESPECIALLY FOR SMALL VALUES OF THE ARGUMENT (MOD. PI).
    AN UPPER BOUND FOR THE ERROR GROWTH IS GIVEN BY A LINEAR FUNCTION
    OF THE DEGREE FOR BOTH (IMPLEMENTED) ALGORITHMS (SEE VAN DER LAAN).

REFERENCES:

    GENTLEMAN,W.M.(1969):
    AN ERROR ANALYSIS OF GOERTZEL'S(WATT'S) METHOD FOR COMPUTING
    FOURIER COEFFICIENTS.
    COMP.J.,VOL.12,P.160-165.

    LAAN,C.G.VAN DER(TO APPEAR):
    ORTHOGONAL POLYNOMIALS IN NUMERICAL ANALYSIS 1.
    ERROR ANALYSIS OF LINEAR TWO-TERM AND THREE-TERM RECURRENCE
    RELATIONS.

    LUKE,Y.L.(1969):
    THE SPECIAL FUNCTIONS AND THEIR APPROXIMATIONS.VOL.1.
    ACADEMIC PRESS.

    NEWBERY,A.C.R.(1973):
    ERROR ANALYSIS FOR FOURIER SERIES EVALUATION.
    MATH.COMP.,VOL.26,P.923-924.

    POLYA,G. AND G.SZEGOE(1971):
    AUFGABEN UND LEHRSAETZE AUS DER ANALYSIS II.
    HEIDELBERGER TASCHENBUECHER 74. SPRINGER.

    REINSCH,C.(1967):
    A NOTE ON TRIGONOMETRIC INTERPOLATION.
    BERICHT NR. 6709.
    ABTEILUNG MATHEMATIK DER TECHNISCHEN UNIVERSITAET MUENCHEN.

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

EXAMPLE OF USE:

    THE FOURIER SERIES .5+COS(THETA)+SIN(THETA)
    IS EVALUATED FOR THE ARGUMENTS 0,PI/2,PI, BY MEANS OF FOUSER

    "BEGIN""REAL"THETA,PI;"ARRAY"A[0:1];
       PI:=ARCTAN(1)*4;A[0]:=.5;A[1]:=1;
       "FOR"THETA:=0,PI/2,PI"DO"
       OUTPUT(61,"("/,B-D.DD")",FOUSER(1,THETA,A))
    "END"

     1.50
     1.50
    -0.50

SOURCE TEXTS:

"CODE" 31090;

"CODE" 31091;
"CODE" 31092;

"CODE" 31093;

"CODE" 31094;
"CODE" 31095;

"CODE" 31096;

"CODE" 31097;