NUMAL Section 3.3.1.1.3.3
BEGIN SECTION : 3.3.1.1.3.3 (December, 1979)
AUTHOR/CONTRIBUTOR: J.J.G. ADMIRAAL.
INSTITUTE: UNIVERSITY OF AMSTERDAM.
RECEIVED: 761101.
BRIEF DESCRIPTION:
THE PROCEDURE SYMEIGIMP IMPROVES A GIVEN APPROXIMATION OF
A REAL SYMMETRIC EIGENSYSTEM AND CALCULATES ERROR BOUNDS
FOR THE EIGENVALUES.
KEYWORDS:
EIGENVALUES.
EIGENVECTORS.
SYMMETRIC MATRIX.
RAYLEIGH QUOTIENTS.
ERROR BOUNDS.
IMPROVED EIGENSYSTEM.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" SYMEIGIMP(N,A,VEC,VAL1,VAL2,LBOUND,UBOUND,AUX);
"VALUE" N;"INTEGER" N;
"ARRAY" A,VEC,VAL1,VAL2,LBOUND,UBOUND,AUX;
"CODE" 36401;
THE MEANING OF THE FORMAL PARAMETERS IS:
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF MATRIX A;
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:N,1:N] CONTAINS A REAL SYMMETRIC MATRIX
WHOSE EIGENSYSTEM HAS TO BE IMPROVED;
VEC: <ARRAY IDENTIFIER>;
"ARRAY" VEC[1:N,1:N] CONTAINS A MATRIX WHOSE COLUMNS ARE
A SYSTEM OF APPROXIMATE EIGENVECTORS OF MATRIX A;
ENTRY: INITIAL APPROXIMATIONS;
EXIT: IMPROVED APPROXIMATIONS;
VAL1: <ARRAY IDENTIFIER>;
"ARRAY" VAL1[1:N];
ENTRY: INITIAL APPROXIMATIONS OF THE EIGENVALUES OF A;
EXIT: THE HEAD PARTS OF THE DOUBLE PRECISION IMPROVED
APPROXIMATIONS OF THE EIGENVALUES OF A;
VAL2: <ARRAY IDENTIFIER>;
"ARRAY" VAL2[1:N];
EXIT: THE TAIL PARTS OF THE DOUBLE PRECISION
IMPROVED EIGENVALUES OF A;
LBOUND,
UBOUND: <ARRAY IDENTIFIER>;
EXIT: "ARRAY" LBOUND, UBOUND [1:N] CONTAIN THE LOWER
AND UPPER ERRORBOUNDS RESPECTIVELY FOR THE EIGENVALUE
APPROXIMATIONS IN VAL1,VAL2[1:N] SUCH THAT THE
I-TH EXACT EIGENVALUE LIES BETWEEN VAL1[I]+VAL2[I]
-LBOUND[I] AND VAL1[I]+VAL2[I]+UBOUND[I];
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[0:5];
ENTRY: AUX[0]= THE RELATIVE PRECISION OF THE ELEMENTS OF A;
AUX[2]= THE RELATIVE TOLERANCE FOR THE RESIDUAL
MATRIX; THE ITERATION ENDS WHEN THE MAXIMUM
ABSOLUTE VALUE OF THE RESIDUAL ELEMENTS IS
SMALLER THAN AUX[2]*AUX[1].
AUX[4]= THE MAXIMUM NUMBER OF ITERATIONS ALLOWED;
EXIT: AUX[1]= INFINITY NORM OF THE MATRIX A;
AUX[3]= MAXIMUM ABSOLUTE ELT. OF THE RESIDUAL MATRIX
AUX[5]= NUMBER OF ITERATIONS;
PROCEDURES USED:
LNGMATVEC = CP34411,
LNGMATMAT = CP34413,
LNGTAMMAT = CP34414,
VECVEC = CP34010,
MATMAT = CP34013,
TAMMAT = CP34014.
MERGESORT = CP36405,
VECPERM = CP36404,
ROWPERM = CP36403,
ORTHOG = CP36402,
QRISYM = CP34163,
INFNRMMAT = CP31064.
RUNNING TIME: ROUGHLY PROPORTIONAL TO N CUBED.
REQUIRED CENTRAL MEMORY:
AUXILIARY ARRAYS ARE DECLARED TO A TOTAL OF 3*N*N + 6*N REALS
AND N INTEGERS; MOREOVER, N INTEGERS OR N BOOLEANS ARE USED
BY MERGESORT, VECPERM AND ROWPERM.
METHOD AND PERFORMANCE: SEE[1].
REFERENCES:
[1]. J.J.G. ADMIRAAL.
ITERATIEF VERBETEREN VAN REEEL SYMMETRISCH EIGENSYSTEEM
EN BEREKENEN VAN FOUTGRENZEN VOOR DE VERKREGEN EIGENWAARDEN.
DOCTORAL SCRIPTION,MARCH 1976,
UNIVERSITEIT VAN AMSTERDAM.
[2]. R.T. GREGORY AND D.L. KARNEY.
A COLLECTION OF MATRICES FOR TESTING COMPUTATIONAL
ALGORITHMS,
WILEY-INTERSCIENCE, 1969.
EXAMPLE OF USE.
"BEGIN" "INTEGER" I,J;"REAL" S;
"ARRAY" A,X[1:4,1:4],VAL1,VAL2,LBOUND,UBOUND[1:4],EM,AUX[0:5];
A[1,1]:=A[2,2]:=A[3,3]:=A[4,4]:=6;
A[1,2]:=A[2,1]:=A[3,1]:=A[1,3]:=4;
A[4,2]:=A[2,4]:=A[3,4]:=A[4,3]:=4;
A[1,4]:=A[4,1]:=A[3,2]:=A[2,3]:=1;
"FOR" I:=1 "STEP" 1 "UNTIL" 4 "DO"
"FOR" J:=I "STEP" 1 "UNTIL" 4 "DO" X[I,J]:=X[J,I]:=A[I,J];
OUTPUT(61,"(""("A")",/,4(4(+DB),/)")",A);
EM[0]:="-14;EM[4]:=100;EM[2]:="-5;
QRISYM(X,4,VAL1,EM);
AUX[0]:=0;AUX[4]:=10;AUX[2]:="-14;
SYMEIGIMP(4,A,X,VAL1,VAL2,LBOUND,UBOUND,AUX);
OUTPUT(61,"("/,"("THE EXACT EIGENVALUES ARE: -1 , +5 , +5 , +15")",
//,"("THE DIFFERENCES BETWEEN THE CALCULATED AND THE EXACT ")",
"("EIGENVALUES")",
//,4(N,/)")",(VAL1[1]+1)+VAL2[1],(VAL1[2]-5)+VAL2[2],(VAL1[3]-
5)+VAL2[3],(VAL1[4]-15)+VAL2[4]);
OUTPUT(61,"("/,"("LOWERBOUNDS UPPERBOUNDS")",//")");
"FOR" I:=1 "STEP" 1 "UNTIL" 4 "DO"
OUTPUT(61,"("2(+D.D"+DD5B),/")",LBOUND[I],UBOUND[I]);
OUTPUT(61,"("/,"("NUMBER OF ITERATIONS = ")",ZD//,
"("INFINITY NORM OF A = ")",ZD//,
"("MAXIMUM ABSOLUTE ELEMENT OF RESIDU = ")",D.D"+DD")",
AUX[5],AUX[1],AUX[3])
"END" EXAMPLE OF USE
DELIVERS:
A
+6 +4 +4 +1
+4 +6 +1 +4
+4 +1 +6 +4
+1 +4 +4 +6
THE EXACT EIGENVALUES ARE: -1 , +5 , +5 , +15
THE DIFFERENCES BETWEEN THE CALCULATED AND THE EXACT EIGENVALUES
-6.3423147029256"-022
+5.5934784498910"-018
+4.0389678347316"-028
-5.5947317864427"-018
LOWERBOUNDS UPPERBOUNDS
+1.2"-23 +1.2"-23
+7.5"-09 +7.5"-09
+1.0"-13 +1.0"-13
+5.6"-18 +5.6"-18
NUMBER OF ITERATIONS = 2
INFINITY NORM OF A = 15
MAXIMUM ABSOLUTE ELEMENT OF RESIDU = 2.8"-14
SOURCETEXT:
"CODE" 36401;