NUMAL Section 3.1.1.3.1.1
BEGIN SECTION : 3.1.1.3.1.1 (February, 1979)
AUTHOR : D.T.WINTER
INSTITUTE : MATHEMATICAL CENTRE
RECEIVED : 731217
BRIEF DESCRIPTION :
THIS SECTION CONTAINS 2 PROCEDURES FOR THE SOLUTION OF AN
OVERDETERMINED SYSTEM OF LINEAR EQUATIONS:
SOLSVDOVR SOLVES AN OVERDETERMINED SYSTEM OF LINEAR EQUATIONS ,
MULTIPLYING THE RIGHT-HAND SIDE BY THE PSEUDO-INVERSE OF THE GIVEN
MATRIX; THE SINGULAR VALUES DECOMPOSITION SHOULD BE AVAILABLE.
SOLOVR CALCULATES THE SINGULAR VALUES DECOMPOSITION AND SOLVES AN
OVERDETERMINED SYSTEM OF LINEAR EQUATIONS.
KEYWORDS :
BEST LEAST-SQUARES SOLUTION
SINGULAR VALUES
PSEUDO-INVERSE
SUBSECTION : SOLSVDOVR
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" SOLSVDOVR(U, VAL, V, M, N, X, EM);
"VALUE" M,N; "INTEGER" M,N; "ARRAY" U, VAL, V, X, EM; "CODE" 34280;
THE MEANING OF THE FORMAL PARAMETERS IS :
U: <ARRAY IDENTIFIER>;
"ARRAY" U[1:M,1:N];
ENTRY:THE MATRIX U IN THE SINGULAR VALUES DECOMPOSITION U*S*V'.
VAL: <ARRAY IDENTIFIER>;
"ARRAY" VAL[1:N];
ENTRY:THE SINGULAR VALUES.
V: <ARRAY IDENTIFIER>;
"ARRAY" V[1:N,1:N];
ENTRY:THE MATRIX V IN THE SINGULAR VALUES DECOMPOSITION.
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF UNKNOWNS.
M: <ARITHMETIC EXPRESSION>;
THE LENGTH OF THE RIGHT-HAND SIDE VECTOR, N SHOULD SATISFY
N <= M.
X: <ARRAY IDENTIFIER>;
"ARRAY" X[1:M];
ENTRY: THE RIGHT-HAND SIDE VECTOR;
EXIT: THE SOLUTION VECTOR IN X[1:N].
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[6:6];
ENTRY: EM[6]: THE MINIMAL NON-NEGLECTABLE SINGULAR VALUE.
PROCEDURES USED :
MATVEC = CP34011
TAMVEC = CP34012
REQUIRED CENTRAL MEMORY : AN AUXILIARY ARRAY OF N REALS IS DECLARED.
RUNNING TIME : ROUGHLY PROPORTIONAL TO (M + N) * N
METHOD AND PERFORMANCE :
THE SOLUTION IS FOUND IN THREE STEPS :
1. U' * X = X1 IS CALCULATED,
2. VAL+ * X1 = X2 IS CALCULATED, HERE VAL+ DENOTES THE DIAGONAL
MATRIX OBTAINED FROM VAL BY SETTING VAL+[I,I] = 1/VAL[I] IF
VAL[I] GREATER THAN OR EQUAL TO EM[6], AND 0 OTHERWISE,
3. THE SOLUTION V * X2 IS CALCULATED.
SUBSECTION : SOLOVR
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"INTEGER" "PROCEDURE" SOLOVR(A, M, N, X, EM);
"VALUE" M, N; "INTEGER" M, N; "ARRAY" A, X, EM; "CODE" 34281;
SOLOVR:= THE NUMBER OF SINGULAR VALUES NOT FOUND, I.E. ZERO IF ALL
SINGULAR VALUES ARE CALCULATED.
THE MEANING OF THE FORMAL PAREMETERS IS :
A: <ARRAY IDENTIFIER>;
"ARRAY" A[1:M,1:N];
ENTRY: THE MATRIX OF THE SYSTEM;
M: <ARITHMETIC EXPRESSION>;
THE NUMBER OF ROWS OF A;
N: <ARITHMETIC EXPRESSION>;
THE NUMBER OF COLUMNS OF A, N <= M;
X: <ARRAY IDENTIFIER>;
"ARRAY" X[1:M];
ENTRY: THE RIGHT-HAND SIDE VECTOR;
EXIT: THE SOLUTION VECTOR IN X[1:N];
EM: <ARRAY IDENTIFIER>;
"ARRAY" EM[0:7];
ENTRY: EM[0]: THE MACHINE PRECISION;
EM[2]: THE RELATIVE PRECISION OF THE SINGULAR VALUES;
EM[4]: THE MAXIMAL NUMBER OF ITERATIONS TO BE PERFORMED IN
THE SINGULAR VALUES DECOMPOSITION;
EM[6]: THE MINIMAL NON-NEGLECTABLE SINGULAR VALUE;
EXIT:EM[1]: THE INFINITY NORM OF THE MATRIX;
EM[3]: THE MAXIMAL NEGLECTED SUPERDIAGONAL ELEMENT;
EM[5]: THE NUMBER OF ITERATIONS PERFORMED IN THE SINGULAR
VALUES DECOMPOSITION;
EM[7]: THE NUMERICAL RANK OF THE MATRIX, I.E. THE NUMBER OF
SINGULAR VALUES GREATER THAN OR EQUAL TO EM[6].
PROCEDURES USED :
QRISNGVALDEC = CP34273
SOLSVDOVR = CP34280
REQUIRED CENTRAL MEMORY :
AUXILIARY ARRAYS ARE DECLARED TO A TOTAL OF (N + 2) * N REALS
RUNNING TIME : ROUGHLY PROPORTIONAL TO (M + N) * N * N
METHOD AND PERFORMANCE :
THE SOLUTION IS FOUND IN TWO STEPS :
1. THE SINGULAR VALUES DECOMPOSITION IS CALCULATED BY MEANS OF THE
PROCEDURE QRISNGVALDEC (SECTION 3.5.1.2);
2. THE SOLUTION IS CALCULATED BY MEANS OF THE PROCEDURE SOLSVDOVR,
(THIS SECTION);
REFERENCES :
WILKINSON, J.H. AND C.REINSCH
HANDBOOK OF AUTOMATIC COMPUTATION, VOL. 2 (CONTRIBUTION I-10)
LINEAR ALGEBRA
HEIDELBERG (1971)
EXAMPLE OF USE :
FIRST A PROGRAM IS GIVEN, AND THEN THE RESULTS OF THIS PROGRAM :
"BEGIN" "ARRAY" A[1:8,1:5], B[1:8], EM[0:7];
"INTEGER" I;
A[1,1]:=22; A[1,2]:= A[2,3]:=10; A[1,3]:= A[7,1]:= A[8,5]:=2;
A[1,4]:= A[3,5]:=3; A[1,5]:= A[2,2]:=7; A[2,1]:=14; A[2,5]:=8;
A[2,4]:= A[8,3]:=0; A[3,1]:= A[3,3]:= A[6,5]:=-1; A[3,2]:=13;
A[3,4]:=-11; A[4,1]:=-3; A[4,2]:= A[4,4]:= A[5,4]:= A[8,4]:=-2;
A[4,3]:=13; A[4,5]:= A[5,5]:= A[8,1]:=4; A[5,1]:= A[6,1]:=9;
A[5,2]:=8; A[5,3]:= A[6,2]:= A[7,5]:=1; A[6,3]:=-7;
A[6,4]:= A[7,4]:= A[8,2]:=5; A[7,2]:=-6; A[7,3]:=6;
B[1]:=-1; B[2]:=2; B[3]:= B[7]:=1; B[4]:=4; B[5]:= B[8]:=0;
B[6]:=-3; EM[0]:="-14; EM[2]:="-12; EM[4]:=80; EM[6]:="-10;
I:= SOLOVR(A, 8, 5, B, EM);
OUTPUT(61, "("4B, "("NUMBER SINGULAR VALUES NOT FOUND : ")",
3ZD,/, 4B, "("NORM : ")", N,/, 4B, "("MAX NEGL SUBD ELEM : ")",
N,/, 4B, "("NUMBER ITERATIONS : ")", 3ZD, /, 4B, "("RANK : ")",
3ZD, /")", I, EM[1], EM[3], EM[5], EM[7]);
OUTPUT(61, "("/, 4B, "("SOLUTION VECTOR")",/,/, 5(4B, N, /)")",
B[1], B[2], B[3], B[4], B[5])
"END"
NUMBER SINGULAR VALUES NOT FOUND : 0
NORM : +4.4000000000000"+001
MAX NEGL SUBD ELEM : +4.3977072741076"-014
NUMBER ITERATIONS : 6
RANK : 3
SOLUTION VECTOR
-8.3333333333334"-002
+1.0989227456287"-015
+2.5000000000000"-001
-8.3333333333332"-002
+8.3333333333334"-002
"EOP"
SOURCE TEXT(S):
"CODE" 34280;
"CODE" 34281;