NUMAL Section 7.1.1.1.1
BEGIN SECTION : 7.1.1.1.1 (November, 1978)
AUTHOR: C.G. VAN DER LAAN
CONTRIBUTORS: C.G. VAN DER LAAN, M. VOORINTHOLT
INSTITUTE: REKENCENTRUM RIJKSUNIVERSITEIT GRONINGEN
RECEIVED: 780601
BRIEF DESCRIPTION:
NEWTON CALCULATES THE COEFFICIENTS OF THE NEWTON POLYNOMIAL
THROUGH GIVEN INTERPOLATION POINTS AND CORRESPONDING
FUNCTION VALUES.
KEYWORDS:
NEWTON INTERPOLATION,
POLYNOMIAL COEFFICIENTS,
DIVIDED DIFFERENCES.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE" NEWTON(N,X,F);
"VALUE"N;"INTEGER"N;"ARRAY"X,F;
"CODE" 36010;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE DEGREE OF THE POLYNOMIAL;
X: <ARRAY IDENTIFIER>;
"ARRAY"X[0:N];
ENTRY: THE INTERPOLATION POINTS;
F: <ARRAY IDENTIFIER>;
"ARRAY"F[0:N];
ENTRY: THE FUNCTION VALUES AT THE INTERPOLATION POINTS;
EXIT: THE COEFFICIENTS OF THE NEWTON POLYNOMIAL.
PROCEDURES USED: NONE.
RUNNING TIME: THE NUMBER OF DIVISIONS IS N(N+1)/2.
METHOD AND PERFORMANCE:
THE POLYNOMIAL OF DEGREE N IN X IS REPRESENTED AS
N K-1
SUM (A[K] * PROD (X-X[L])).
K=0 L=0
THE COEFFICIENTS OF THE (NEWTON) POLYNOMIAL, A[0:N], ARE
CALCULATED BY INTERPOLATION AT THE GIVEN ARGUMENTS, X[0:N],
AND FUNCTION VALUES, F[0:N]; THE RESULTING SET OF EQUATIONS IS
SOLVED BY TRANSFORMING THE CORRESPONDING LOWER TRIANGULAR MATRIX
TO DIAGONAL FORM.
EXAMPLE OF USE:
"BEGIN" "ARRAY" X,F[0:2];
X[0]:=0;X[1]:=.5;X[2]:=1;
F[0]:=1;F[1]:=F[2]:=0;
NEWTON(2,X,F);
OUTPUT(61,"("/,"("THE NEWTON COEFF. ARE")",
/,3(N)")",F[0],F[1],F[2]);
"END"TSTNEWTON
THE NEWTON COEFF. ARE
+1.0000000000000"+000 -2.0000000000000"+000 +2.0000000000000"+000
SOURCE TEXT(S):
"CODE" 36010;