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;