NUMAL Section 2.2.1.1
BEGIN SECTION : 2.2.1.1 (October, 1975)
AUTHOR: C.G. VAN DER LAAN.
INSTITUTE: REKENCENTRUM RIJKSUNIVERSITEIT GRONINGEN.
RECEIVED: 741114.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS THE PROCEDURES POL, TAYPOL, NORDERPOL AND
DERPOL.
POL EVALUATES A POLYNOMIAL;
DERPOL EVALUATES THE FIRST K DERIVATIVES OF A POLYNOMIAL;
NORDERPOL EVALUATES THE FIRST K NORMALIZED DERIVATIVES OF A
POLYNOMIAL (I.E. J-TH DERIVATIVE/(J FACTORIAL),J=0,1,...,K<=DEGREE;
TAYPOL EVALUATES X**J*(J-TH DERIVATIVE)/(J FACTORIAL),
J=0,1,...,K<=DEGREE.
KEYWORDS:
POLYNOMIAL EVALUATION,
(NORMALIZED) DERIVATIVES,
DERIVATIVES OF A POLYNOMIAL.
SUBSECTION: POL.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"REAL""PROCEDURE" POL(N,X,A);
"VALUE"N,X;"INTEGER"N;"REAL"X;"ARRAY"A;
"CODE" 31040;
POL:=A[0]+A[1]*X+...+A[N]*X**N;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
ENTRY: THE DEGREE OF THE POLYNOMIAL;
X: <ARITHMETIC EXPRESSION>;
ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[0:N];
ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
A[0]+A[1]*X+...+A[N]*X**N.
PROCEDURES USED: NONE.
RUNNING TIME: PROPORTIONAL TO N
(N MULTIPLICATIONS AND ADDITIONS).
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD USED FOR EVALUATION IS HORNER'S RULE (SYNTHETIC
DIVISION). THE ERROR GROWTH IS GIVEN BY A LINEAR FUNCTION OF THE
DEGREE OF THE POLYNOMIAL (SEE VAN DER LAAN, STOER(1972) P. 29 (EX.
11) OR WILKINSON(1963) P. 36,37).
SUBSECTION: DERPOL.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"PROCEDURE" DERPOL(N,K,X,A);
"VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
"CODE" 31243;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
ENTRY: THE DEGREE OF THE POLYNOMIAL;
K: <ARITHMETIC EXPRESSION>;
ENTRY: THE FIRST K DERIVATIVES ARE TO BE CALCULATED;
X: <ARITHMETIC EXPRESSION>;
ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[0:N];
ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
A[0]+A[1]*X+...+A[N]*X**N;
EXIT: THE J-TH DERIVATIVE IS DELIVERED IN A[J], J=0,1,...,K<=
DEGREE; THE OTHER ELEMENTS ARE GENERALLY ALTERED.
PROCEDURES USED :
NORDERPOL = CP31242
RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
THE NUMBER OF MULTIPLICATIONS IS N, IN FIRST ORDER.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE TAYPOL(THIS SECTION).
SUBSECTION: NORDERPOL.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"PROCEDURE" NORDERPOL(N,K,X,A);
"VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
"CODE" 31242;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
ENTRY: THE DEGREE OF THE POLYNOMIAL;
K: <ARITHMETIC EXPRESSION>;
THE FIRST K NORMALIZED DERIVATIVES ARE TO BE CALCULATED
(I.E. (J-TH DERIVATIVE)/(J FACTORIAL), J=0,1,...,K<=DEGREE).
X: <ARITHMETIC EXPRESSION>;
ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[0:N];
ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
A[0]+A[1]*X+...+A[N]*X**N;
EXIT: THE J-TH NORMALIZED DERIVATIVE IS DELIVERED IN A[J]
J=0,1,...,K<=DEGREE; THE OTHER ELEMENTS ARE GENERALLY
ALTERED.
PROCEDURES USED: NONE.
REQUIRED CENTRAL MEMORY: AN AUXILIARY ARRAY OF ORDER N + 1 IS DECLARED.
RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
THE NUMBER OF MULTIPLICATIONS/DIVISIONS IS 2 * N + K.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE TAYPOL(THIS SECTION).
SUBSECTION: TAYPOL.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"PROCEDURE" TAYPOL(N,K,X,A);
"VALUE"N,K,X;"INTEGER"N,K;"REAL"X;"ARRAY"A;
"CODE" 31241;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
ENTRY: THE DEGREE OF THE POLYNOMIAL;
K: <ARITHMETIC EXPRESSION>;
ENTRY: THE FIRST K TERMS X**J*(J-TH DERIVATIVE)/(J FACTORIAL),
J=0,1,...,K<=DEGREE, ARE TO BE CALCULATED;
X: <ARITHMETIC EXPRESSION>;
ENTRY: THE ARGUMENT OF THE POLYNOMIAL;
A: <ARRAY IDENTIFIER>;
"ARRAY"A[0:N];
ENTRY: THE COEFFICIENTS OF THE POLYNOMIAL
A[0]+A[1]*X+...+A[N]*X**N;
EXIT: THE J-TH TERM X**J*(J-TH DERIVATIVE)/(J FACTORIAL), IS
DELIVERED IN A[J], J=0,1,...,K<=DEGREE; THE OTHER
ELEMENTS ARE GENERALLY ALTERED.
PROCEDURES USED: NONE.
RUNNING TIME: THE NUMBER OF ADDITIONS IS (K+1)*(N-K/2) AND
THE NUMBER OF MULTIPLICATIONS IS 2 * N.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
THE METHOD OF EVALUATION IS GIVEN BY TRAUB AND SHAW(1972,1974).
LET X**J*(J-TH DERIVATIVE OF THE POLYNOMIAL)/(J FACTORIAL)=
(J OVER J)*A[J]*X**J+(J+1 OVER J)*A[J+1]*X**(J+1)+...+(N OVER J)*
A[N]*X**N,THEN THE J-TH DERIVATIVE (UP TO A FACTOR) CAN BE OBTAINED
FROM THE BINOMIAL COEFFICIENTS FOLLOWED BY EVALUATION OF THE ABOVE
INPRODUCT. THE SHAW AND TRAUB ALGORITHM PERFORMS THE BUILDING UP OF
THE BINOMIAL COEFFICIENTS IMPLICITLY.
WE HAVE NOT IMPLEMENTED THE MORE SOPHISTICATED ALGORITHM, BASED
ON DIVISORS OF N+1, BECAUSE OF THE MORE COMPLEX APPEARANCE
OF THE IMPLEMENTATION AND BECAUSE OF THE DIFFICULTY IN CHOSING
THE MOST EFFICIENT DIVISOR. OUR (RESTRICTED) IMPLEMENTATION OF THE
ONE-PARAMETER FAMILY OF ALGORITHMS PRESERVES THE LINEAR NUMBER OF
MULTIPLICATIONS (2*N (NORDERPOL, TAYPOL) AND 3*N (DERPOL)).
THE ABSOLUTE ERROR IS OF ORDER MAX((N OVER N)*A[N]*X**(N-K),...,
(N OVER K)*A[K]), FOR THE K-TH NORMALIZED DERIVATIVE (SEE VAN DER
LAAN OR WOZNIAKOWSKI).
REFERENCES:
[1].SHAW,M. AND J. TRAUB:
ON THE NUMBER OF MULTIPLICATIONS FOR THE EVALUATION OF A
POLYNOMIAL AND SOME OF ITS DERIVATIVES (21 P.).
JOURN. ACM, 1974, VOL. 21, NO. 1, P. 161-167.
[2].STOER,J. :
EINFUEHRUNG IN DIE NUMERISCHE MATHEMATIK 1.
SPRINGER, 1972.
[3].VAN DER LAAN C.G.:
ORTHOGONAL POLYNOMIALS IN NUMERICAL ANALYSIS.
1. ERROR ANALYSIS OF RECURRENCE RELATIONS IN FLOATING-POINT
COMPUTATION, (TO APPEAR).
[4].WILKINSON,J.H. :
ROUNDING ERRORS IN ALGEBRAIC PROCESSES.
HSO, NOTES ON APPLIED SCIENCES NO. 32, 1963.
[5].WOZNIAKOWSKI,H.:
ROUNDING ERROR ANALYSIS FOR THE EVALUATION OF A POLYNOMIAL AND
SOME OF ITS DERIVATIVES.
SIAM J. OF NUM. AN. VOL 11, NO. 4, P. 780-787.
EXAMPLE OF USE:
AS A FORMAL TEST OF THE PROCEDURE DERPOL THE DERIVATIVES OF THE
POLYNOMIAL 3*X**3-2*X**2+X-1 ARE CALCULATED AT X=1.
"BEGIN""ARRAY"A[0:3];
A[3]:=3;A[2]:=-2;A[1]:=1;A[0]:=-1;
DERPOL(3,3,1,A); OUTPUT(61,"("
"("THE 0-TH UNTIL AND INCLUDING THE 3-TH DERIVATIVES :")",
4(BZDB)")",A[0],A[1],A[2],A[3]);
"END" EXAMPLE OF USE;
THE 0-TH UNTIL AND INCLUDING THE 3-TH DERIVATIVES : 1 6 14 18
SOURCE TEXT(S):
"CODE" 31040;
"CODE" 31241;
"CODE" 31242;
"CODE" 31243;