NUMAL Section 3.3.2.2.1
BEGIN SECTION : 3.3.2.2.1 (July, 1974)
AUTHOR : C.G. VAN DER LAAN.
CONTRIBUTORS : H.FIOLET, C.G. VAN DER LAAN.
INSTITUTE : MATHEMATICAL CENTRE.
RECEIVED: 731016.
BRIEF DESCRIPTION :
THIS SECTION CONTAINS THE PROCEDURES VALQRICOM AND QRICOM.
VALQRICOM CALCULATES THE EIGENVALUES OF A COMPLEX UPPER-HESSENBERG
MATRIX WITH A REAL SUBDIAGONAL.
QRICOM CALCULATES THE EIGENVECTORS AS WELL.
KEYWORDS :
EIGENVALUES,
EIGENVECTORS,
COMPLEX UPPER-HESSENBERG MATRIX,
QR-ITERATION.
SUBSECTION: VALQRICOM.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"INTEGER" "PROCEDURE" VALQRICOM(A1, A2, B, N, EM, VAL1, VAL2);
"VALUE" N; "INTEGER" N; "ARRAY" A1, A2, B, EM, VAL1, VAL2;
"CODE" 34372;
THE MEANING OF THE FORMAL PARAMETERS IS:
A1,A2: <ARRAY IDENTIFIER>;
"ARRAY" A1,A2[1:N,1:N];
ENTRY:
THE REAL PART AND THE IMAGINARY PART OF THE UPPER
TRIANGLE OF THE UPPER-HESSENBERG MATRIX MUST BE GIVEN IN
THE CORRESPONDING PARTS OF THE ARRAYS A1 AND A2;
THE ELEMENTS IN THE UPPER TRIANGLE OF THE ARRAYS A1 AND
A2 ARE ALTERED;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N-1];
ENTRY:
THE REAL SUBDIAGONAL OF THE UPPER-HESSENBERG MATRIX;
THE ELEMENTS OF THE ARRAY B ARE ALTERED;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE GIVEN MATRIX;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:5];
ENTRY:
EM[0]: THE MACHINE PRECISION;
EM[1]: AN ESTIMATE OF THE NORM OF THE UPPER-HESSENBERG
MATRIX (E.G. THE SUM OF THE INFINITY NORMS OF THE
REAL AND IMAGINARY PARTS OF THE MATRIX);
EM[2]: THE RELATIVE TOLERANCE FOR THE QR-ITERATION;
(E.G. THE MACHINE PRECISION);
EM[4]: THE MAXIMUM ALLOWED NUMBER OF ITERATIONS;
(E.G. 10 * N);
EXIT:
EM[3]: THE MAXIMUM ABSOLUTE VALUE OF THE SUBDIAGONAL
ELEMENTS NEGLECTED;
EM[5]: THE NUMBER OF ITERATIONS PERFORMED;
EM[5]:=EM[4]+1 IN THE CASE VALQRICOM^=0;
VAL1,VAL2: <ARRAY IDENTIFIER>;
"ARRAY" VAL1,VAL2[1:N];
EXIT:
THE REAL PART AND THE IMAGINARY PART OF THE CALCULATED
EIGENVALUES ARE DELIVERED IN THE ARRAYS VAL1 AND VAL2,
RESPECTIVELY;
VALQRICOM:=0, PROVIDED THE PROCESS IS COMPLETED WITHIN EM[4]
ITERATIONS; OTHERWISE, VALQRICOM:= THE NUMBER, K, OF EIGENVALUES
NOT CALCULATED AND ONLY THE LAST N-K ELEMENTS OF THE ARRAYS VAL1
AND VAL2 ARE APPROXIMATE EIGENVALUES OF THE UPPER-HESSENBERG
MATRIX.
PROCEDURES USED:
COMKWD = CP34345,
ROTCOMROW = CP34358,
ROTCOMCOL = CP34357,
COMCOLCST = CP34352.
RUNNING TIME: PROPORTIONAL TO N**2 * NUMBER OF ITERATIONS.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SEE QRICOM (THIS SECTION).
EXAMPLE OF USE:
AS A FORMAL TEST OF THE PROCEDURE VALQRICOM THE ZEROS OF THE
POLYNOMIAL X**4 + (4+2*I)* X**3 + (5+6*I)* X**2 + (2+6*I)* X + 2*I
ARE OBTAINED BY MEANS OF THE CALCULATION OF THE EIGENVALUES OF THE
FOLLOWING COMPANION MATRIX:
(SEE WILKINSON AND REINSCH, 1971, CONTRIBUTION II/15)
-4-2*I -5-6*I -2-6*I -2*I
1 0 0 0
0 1 0 0
0 0 1 0
"BEGIN"
"REAL" "ARRAY" A1,A2[1:4,1:4],B[1:3],EM[0:5],VAL1,VAL2[1:4];
"INTEGER" I;
INIMAT(1,4,1,4,A1,0);INIMAT(1,4,1,4,A2,0);
A1[1,1]:=-4;A1[1,2]:=-5;A1[1,3]:=A2[1,1]:=A2[1,4]:=-2;
A2[1,2]:=A2[1,3]:=-6;
B[1]:=B[2]:=B[3]:=1;
EM[0]:=5"-14;EM[1]:=27;EM[2]:="-12;EM[4]:=15;
OUTPUT(61,"(""("VALQRICOM: ")",D/")",
VALQRICOM(A1,A2,B,4,EM,VAL1,VAL2));
OUTPUT(61,"(""("EIGENVALUES:")",/,"("REAL PART")",14B,
"("IMAGINARY PART")",/")");
"FOR" I:=1,2,3,4 "DO" OUTPUT(61,"("N,N/")",VAL1[I],VAL2[I]);
OUTPUT(61,"(""("EM[3]: ")",D.D"+DD/,"("EM[5]: ")",3D")",
EM[3],EM[5])
"END"
OUTPUT:
VALQRICOM: 0
EIGENVALUES:
REAL PART IMAGINARY PART
-1.0000001920467"+000 -1.0000000831019"+000
-9.9999980795324"-001 -9.9999991689805"-001
-1.0000000047492"+000 +1.6824958523393"-007
-9.9999999525076"-001 -1.6824956397352"-007
EM[3]: 3.2"-14
EM[5]: 010
SUBSECTION: QRICOM.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE READS:
"INTEGER" "PROCEDURE" QRICOM(A1,A2,B,N,EM,VAL1,VAL2,VEC1,VEC2);
"VALUE" N; "INTEGER" N;
"ARRAY" A1, A2, B, EM, VAL1, VAL2, VEC1, VEC2;
"CODE" 34373;
THE MEANING OF THE FORMAL PARAMETERS IS:
A1,A2: <ARRAY IDENTIFIER>;
"ARRAY" A1,A2[1:N,1:N];
ENTRY:
THE REAL PART AND THE IMAGINARY PART OF THE UPPER
TRIANGLE OF THE UPPER-HESSENBERG MATRIX MUST BE GIVEN IN
THE CORRESPONDING PARTS OF THE ARRAYS A1 AND A2;
THE ELEMENTS IN THE UPPER TRIANGLE OF THE ARRAYS A1 AND
A2 ARE ALTERED;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N-1];
ENTRY:
THE REAL SUBDIAGONAL OF THE UPPER-HESSENBERG MATRIX;
THE ELEMENTS OF THE ARRAY B ARE ALTERED;
N: <ARITHMETIC EXPRESSION>;
THE ORDER OF THE GIVEN MATRIX;
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:5];
ENTRY:
EM[0]: THE MACHINE PRECISION;
EM[1]: AN ESTIMATE OF THE NORM OF THE UPPER-HESSENBERG
MATRIX (E.G. THE SUM OF THE INFINITY NORMS OF THE
REAL AND IMAGINARY PARTS OF THE MATRIX);
EM[2]: THE RELATIVE TOLERANCE FOR THE QR-ITERATION;
(E.G. THE MACHINE PRECISION);
EM[4]: THE MAXIMUM ALLOWED NUMBER OF ITERATIONS;
(E.G. 10 * N);
EXIT:
EM[3]: THE MAXIMUM ABSOLUTE VALUE OF THE SUBDIAGONAL
ELEMENTS NEGLECTED;
EM[5] THE NUMBER OF ITERATIONS PERFORMED;
EM[5]:=EM[4]+1 IN THE CASE QRICOM^=0;
VAL1,VAL2: <ARRAY IDENTIFIER>;
"ARRAY" VAL1,VAL2[1:N];
EXIT:
THE REAL PART AND THE IMAGINARY PART OF THE CALCULATED
EIGENVALUES ARE DELIVERED IN THE ARRAYS VAL1 AND VAL2,
RESPECTIVELY;
VEC1,VEC2: <ARRAY IDENTIFIER>;
"ARRAY" VEC1,VEC2[1:N,1:N];
EXIT:
THE EIGENVECTORS OF THE UPPER-HESSENBERG MATRIX;
THE EIGENVECTOR WITH REAL PART VEC1[1:N,J] AND IMAGINARY
PART VEC2[1:N,J] CORRESPONDS TO THE EIGENVALUE
VAL1[J] + VAL2[J] * I, J=1,...,N;
QRICOM:=0, PROVIDED THE PROCESS IS COMPLETED WITHIN EM[4]
ITERATIONS; OTHERWISE, QRICOM:= THE NUMBER, K, OF EIGENVALUES NOT
CALCULATED AND ONLY THE LAST N-K ELEMENTS OF THE ARRAYS VAL1 AND
VAL2 ARE APPROXIMATE EIGENVALUES OF THE UPPER-HESSENBERG MATRIX,
AND NO USEFUL EIGENVECTORS ARE DELIVERED.
PROCEDURES USED:
COMKWD = CP34345,
ROTCOMROW = CP34358,
ROTCOMCOL = CP34357,
COMCOLCST = CP34352,
COMROWCST = CP34353,
MATVEC = CP34011,
COMMATVEC = CP34354,
COMDIV = CP34342.
REQUIRED CENTRAL MEMORY: TWO AUXILIARY ARRAYS OF ORDER N ARE DECLARED.
RUNNING TIME: PROPORTIONAL TO N**2 * NUMBER OF ITERATIONS.
LANGUAGE: ALGOL 60.
THE FOLLOWING HOLDS FOR BOTH PROCEDURES:
METHOD AND PERFORMANCE:
THE UPPER-HESSENBERG MATRIX IS TRANSFORMED BY MEANS OF FRANCIS' QR
ITERATION ( FRANCIS, 1961, AND WILKINSON, 1965 ) INTO A COMPLEX
UPPER TRIANGULAR MATRIX. THE EIGENVALUES ARE THE DIAGONAL ELEMENTS
OF THE LATTER MATRIX. TO CALCULATE THE EIGENVECTORS WE FIRST SOLVE
THE RESULTING TRIANGULAR SYSTEM OF LINEAR EQUATIONS AND
SUBSEQUENTLY PERFORM THE CORRESPONDING BACKTRANSFORMATION.
EXAMPLE OF USE:
QRICOM CALCULATES THE EIGENVALUES AND EIGENVECTORS OF THE
FOLLOWING MATRIX:
(SEE WILKINSON AND REINSCH, 1971, CONTRIBUTION II/15)
-4-2*I -5-6*I -2-6*I -2*I
1 0 0 0
0 1 0 0
0 0 1 0
THE EIGENVECTORS ARE NORMALIZED BY THE PROCEDURE SCLCOM.
(SEE SECTION 1.2.11.).
ONLY THE EIGENVECTOR CORRESPONDING TO VAL1[1] + VAL2[1] * I IS
PRINTED BY THE FOLLOWING PROGRAM.
"BEGIN"
"REAL" "ARRAY" A1,A2,VEC1,VEC2[1:4,1:4],B[1:3],
EM[0:5],VAL1,VAL2[1:4];
"INTEGER" I;
INIMAT(1,4,1,4,A1,0);INIMAT(1,4,1,4,A2,0);
A1[1,1]:=-4;A1[1,2]:=-5;A1[1,3]:=A2[1,1]:=A2[1,4]:=-2;
A2[1,2]:=A2[1,3]:=-6;
B[1]:=B[2]:=B[3]:=1;
EM[0]:=5"-14;EM[1]:=27;EM[2]:="-12;EM[4]:=15;
OUTPUT(61,"(""("QRICOM: ")",D/")",
QRICOM(A1,A2,B,4,EM,VAL1,VAL2,VEC1,VEC2));
OUTPUT(61,"(""("EIGENVALUES:")",/,"("REAL PART")",14B,
"("IMAGINARY PART")",/")");
"FOR" I:=1,2,3,4 "DO" OUTPUT(61,"("N,N/")",VAL1[I],VAL2[I]);
SCLCOM(VEC1,VEC2,4,1,4);
OUTPUT(61,"(""("FIRST EIGENVECTOR:")",/,"("REAL PART")",14B,
"("IMAGINARY PART")",/")");
"FOR" I:=1,2,3,4 "DO" OUTPUT(61,"("N,N/")",VEC1[I,1],VEC2[I,1]);
OUTPUT(61,"(""("EM[3]: ")",D.D"+DD/,"("EM[5]: ")",3D")",
EM[3],EM[5])
"END"
OUTPUT:
QRICOM: 0
EIGENVALUES:
REAL PART IMAGINARY PART
-9.9999980795324"-001 -9.9999991689805"-001
-1.0000001920467"+000 -1.0000000831019"+000
-1.0000000047492"+000 +1.6824958523393"-007
-9.9999999525076"-001 -1.6824956397352"-007
FIRST EIGENVECTOR:
REAL PART IMAGINARY PART
+1.0000000000000"+000 -1.7763568394003"-015
-5.0000004155098"-001 +5.0000009602339"-001
-5.4472417687634"-008 -5.0000013757436"-001
+2.5000014403510"-001 +2.5000006232645"-001
EM[3]: 3.2"-14
EM[5]: 010
REFERENCES:
DEKKER, T.J. (1968),
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 1,
MATH. CENTRE TRACTS 22, MATHEMATISCH CENTRUM;
DEKKER, T.J. AND W.HOFFMANN (1968),
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 2,
MATH. CENTRE TRACTS 23, MATHEMATISCH CENTRUM;
FRANCIS, J.G.F. (1961),
THE QR-TRANSFORMATION, PART 1 AND 2,
COMP.J. 4, P.265-271 AND P.332-345;
RUHE, A. (1966),
EIGENVALUES OF A COMPLEX MATRIX BY THE QR METHOD.
BIT, 6, P.350-358;
WILKINSON, J.H. (1965),
THE ALGEBRAIC EIGENVALUE PROBLEM,
CLARENDOM PRESS, OXFORD;
SOURCE TEXT(S) :
"CODE" 34372;
"CODE" 34373;