NUMAL Section 7.1.3.2.1
BEGIN SECTION : 7.1.3.2.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:
THIS SECTION CONTAINS THREE PROCEDURES:
MINMAXPOL: CALCULATES THE COEFFICIENTS OF THE POLYNOMIAL
(AS A SUM OF POWERS) WHICH APPROXIMATES A FUNCTION,
GIVEN FOR DISCRETE ARGUMENTS, IN SUCH A WAY THAT THE
INFINITY NORM OF THE ERROR VECTOR IS MINIMIZED.
INI: SELECTS A (SUB)SET OF INTEGERS OUT OF A GIVEN
SET OF INTEGERS;
SNDREMEZ: EXCHANGES AT MOST N+1 NUMBERS WITH NUMBERS OUT OF
A REFERENCE SET;
(INI AND SNDREMEZ ARE AUXILIARY PROCEDURES USED IN MINMAXPOL.)
KEYWORDS:
(SECOND) REMEZ ALGORITHM,
MINIMAX POLYNOMIAL APPROXIMATION.
REFERENCES:
MEINARDUS, G. (1964):
APPROXIMATION OF FUNCTION AND THEIR NUMERICAL TREATMENT (GERMAN).
SPRINGER TRACTS IN NATURAL PHILOSOPHY, VOL. 4.
DEKKER, T.J. (1967):
CURSUS WETENSCHAPPELIJK REKENEN A.
MATHEMATISCH CENTRUM.
SUBSECTION : MINMAXPOL.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE"MINMAXPOL(N,M,Y,FY,CO,EM);
"VALUE"N,M;"INTEGER"N,M;"ARRAY"Y,FY,CO,EM;
"CODE" 36022;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE DEGREE OF THE APPROXIMATING POLYNOMIAL (N>=0);
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF REFERENCE FUNCTION VALUES VIZ. ARGUMENTS
IS M+1;
Y,FY: <ARRAY IDENTIFIERS>;
"ARRAY"Y,FY[0:M];
ENTRY: FY[I] IS THE FUNCTION VALUE AT Y[I], FOR I=0,...M;
CO: <ARRAY IDENTIFIER>;
"ARRAY"CO[0:N];
EXIT: THE COEFFICIENTS OF THE APPROXIMATING POLYNOMIAL
(CO[N] IS COEFFICIENT OF Y**N);
EM: <ARRAY IDENTIFIER>;
"ARRAY"EM[0:3];
ENTRY: EM[2]:THE MAXIMUM ALLOWED NUMBER OF
ITERATIONS (SAY 10*N+5);
EXIT: EM[0]:THE DIFFERENCE OF THE GIVEN FUNCTION AND
THE POLYNOMIAL IN THE FIRST APPROXIMATION
POINT;
EM[1]:THE INFINITY NORM OF THE ERROR OF
APPROXIMATION OVER THE DISCRETE INTERVAL;
EM[3]:THE NUMBER OF ITERATIONS PERFORMED.
PROCEDURES USED: ELMVEC = CP34020,
DUPVEC = CP31030,
NEWTON = CP36010,
POL = CP31040,
NEWGRN = CP31050,
INI = CP36020,
SNDREMEZ = CP36021.
REQUIRED CENTRAL MEMORY:
AN INTEGER ARRAY AND THREE (REAL) ARRAYS OF N+2 ELEMENTS AS
WELL AS A (REAL) ARRAY OF M+1 ELEMENTS ARE INTERNALLY DECLARED.
RUNNING TIME:
THE SECOND REMEZ ALGORITHM (ON A DISCRETE SET) IS QUADRATIC
CONVERGENT;IN EACH ITERATION THE NUMBER OF OPERATIONS
(MULTIPLICATIONS AND ADDITIONS) IS PROPORTIONAL TO M*N.
METHOD AND PERFORMANCE: SEE MEINARDUS (1969),CH.7.
EXAMPLE OF USE:
"BEGIN""INTEGER"N;
"PROCEDURE" COMPUTE(N,A,B,F);
"VALUE" N,A,B;"INTEGER" N;"REAL" A,B;
"REAL" "PROCEDURE" F;
"BEGIN" "INTEGER" K,L,M;
"REAL"R,T,IDM;
"ARRAY" COEF[0:N],EM[0:3];
EM[2]:=10*N+5;
M:=100*N+10;
"BEGIN" "ARRAY" Y,FY[0:M];
IDM:=(B-A)/M;
R:=Y[0]:=A;FY[0]:=F(R);
R:=Y[M]:=B;FY[M]:=F(R);
L:=M-1;
"FOR"K:=1"STEP"1"UNTIL"L"DO"
"BEGIN"R:=Y[K]:=A+K*IDM;FY[K]:=F(R) "END";
MINMAXPOL(N,M,Y,FY,COEF,EM);
OUTPUT(61,"(""("COEF:")"/")");
"FOR"K:=0"STEP"1"UNTIL"N"DO"OUTPUT(61,"(" ")",COEF[K]);
OUTPUT(61,"("/8S/,2(N),2(B+3ZDB),/")","("EM[0:3]")",EM[0],
EM[1],EM[2],EM[3]);
"END";
"END" COMPUTE;
"REAL""PROCEDURE"F(X);"VALUE"X;"REAL"X;
F:=1/(X-10);
"FOR" N:=1"DO"
"BEGIN" OUTPUT(61,"("//,"("DEGREE=")",D//")",N);
COMPUTE(N,-1,1,F)
"END"
"END"
DEGREE=1
COEF:
-1.0050378153393"-001 -1.0101010101010"-002
EM[0:3]
-5.0631947616870"-004 +5.0631947616870"-004 +15 +3
SUBSECTION : INI.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE" INI(N,M,S);
"VALUE"N,M;"INTEGER"N,M;"INTEGER""ARRAY"S;
"CODE" 36020;
THE MEANING OF THE FORMAL PARAMETERS IS:
N,M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF POINTS TO BE SELECTED EQUALS N+1;
THE REFERENCE SET CONTAINS THE NUMBERS 0,1,...,M (M>=N);
S: <ARRAY IDENTIFIER>;
"INTEGER" "ARRAY" S[0:N];
EXIT: THE SELECTED INTEGERS ARE DELIVERED IN S.
PROCEDURES USED: NONE.
METHODS AND PERFORMANCE:
THE ARGUMENTS FOR WHICH THE CHEBYSHEV POLYNOMIAL OF DEGREE N
ATTAINS ITS EXTREME VALUES ON THE INTERVAL [-1,1] ARE TRANSFORMED
TO THE INTERVAL [0,M] BY A LINEAR TRANSFORMATION; FINALLY THE
NUMBERS ARE PROPERLY ROUNDED.
EXAMPLE OF USE:
"BEGIN""INTEGER""ARRAY"S[0:2];
INI(2,20,S);
OUTPUT(61,"(""("INI SELECTS OUT OF 0,1,...,20 THE NUMBERS:")",/,
3(B-ZDB)")",S[0],S[1],S[2])
"END"
INI SELECTS OUT OF 0,1,...,20 THE NUMBERS:
0 10 20
SUBSECTION : SNDREMEZ.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE"SNDREMEZ(N,M,S,G,EM);
"VALUE"N,M;"INTEGER"N,M;"INTEGER""ARRAY"S;"ARRAY" G,EM;
"CODE" 36021;
THE MEANING OF THE FORMAL PARAMETERS IS:
N,M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF POINTS TO BE EXCHANGED IS SMALLER THAN
OR EQUAL TO N+1; THE REFERENCE SET CONTAINS THE
NUMBERS 0,1,...,M (M>=N);
S: <ARRAY IDENTIFIER>;
"INTEGER" "ARRAY" S[0:N];
ENTRY: IN S ONE MUST GIVE N+1 (STRICTLY)
MONOTONE INCREASING NUMBERS OUT OF 0,...,M;
EXIT : N+1 (STRICTLY) MONOTONE INCREASING NUMBERS OUT OF
THE NUMBERS 0,1,...,M;
G: <ARRAY IDENTIFIER>;
"ARRAY" G[0:M];
ENTRY: IN ARRAY G[0:M] ONE MUST GIVE FUNCTION VALUES;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:1];
ENTRY: 0<EM[0]<=G[I],I=0,...,M;
EXIT : EM[1]:=INFINITY NORM OF ARRAY G[0:M].
PROCEDURES USED: INFNRMVEC = CP31061.
METHOD AND PERFORMANCE:
THE SECOND REMEZ ALGORITHM IS USED (MEINARDUS,G.(1964)).
EXAMPLE OF USE:
"BEGIN""ARRAY"EM[0:1],G[0:7];"INTEGER""ARRAY"S[0:2];
G[0]:=10;G[1]:=12;G[2]:=-15;G[3]:=-10;
G[4]:=-14;G[5]:=15;G[6]:=10;G[7]:=11;
EM[0]:=10;S[0]:=0;S[1]:=3;S[2]:=6;
OUTPUT(61,"(""("THE NUMBERS:")",/,"("S[J]:")",3(B-D),/,
"("G[S[J]]:")",3(B-DD)")",
S[0],S[1],S[2],G[S[0]],G[S[1]],G[S[2]]);
SNDREMEZ(2,7,S,G,EM);
OUTPUT(61,"("//,"("ARE EXCHANGED WITH:")",/,"("S[J]:")",3(B-D),/,
"("G[S[J]]:")",3(B-DD),//,
"("THE REFERENCE SET OF FUNCTIONVALUES IS:")",/,8(B-DD)")",
S[0],S[1],S[2],G[S[0]],G[S[1]],G[S[2]] ,
G[0],G[1],G[2],G[3],G[4],G[5],G[6],G[7])
"END"
THE NUMBERS:
S[J]: 0 3 6
G[S[J]]: 10 -10 10
ARE EXCHANGED WITH:
S[J]: 0 2 5
G[S[J]]: 10 -15 15
THE REFERENCE SET OF FUNCTIONVALUES IS:
10 12 -15 -10 -14 15 10 11
SOURCE TEXT(S) :
"CODE" 36022;
"CODE" 36020;
"CODE" 36021;