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;