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;