NUMAL Section 3.1.1.2.1.1
BEGIN SECTION : 3.1.1.2.1.1 (May, 1974)
AUTHOR : T.J. DEKKER.
CONTRIBUTOR : J. KOK.
INSTITUTE : MATHEMATICAL CENTRE.
RECEIVED : 731015.
BRIEF DESCRIPTION :
THIS SECTION CONTAINS TWO PROCEDURES :
A) LSQORTDEC, FOR THE HOUSEHOLDER TRIANGULARIZATION WITH COLUMN
INTERCHANGES OF THE COEFFICIENT MATRIX OF A LINEAR LEAST SQUARES
PROBLEM;
B) LSQDGLINV, FOR THE CALCULATION OF THE DIAGONAL ELEMENTS OF THE
INVERSE OF M'M, WHERE M IS THE COEFFICIENT MATRIX OF A LINEAR
LEAST SQUARES PROBLEM.
KEY WORDS :
LINEAR LEAST SQUARES PROBLEM,
HOUSEHOLDER TRIANGULARIZATION.
SUBSECTION : LSQORTDEC.
CALLING SEQUENCE:
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" LSQORTDEC(A, N, M, AUX, AID, CI); "VALUE" N, M;
"INTEGER" N, M; "INTEGER""ARRAY" CI; "ARRAY" A, AUX, AID;
"CODE" 34134;
THE MEANING OF THE FORMAL PARAMETERS IS :
A : <ARRAY IDENTIFIER>;
"ARRAY" A[1 : N,1 : M];
ENTRY :THE COEFFICIENT MATRIX OF THE
LINEAR LEAST SQUARES PROBLEM;
EXIT : IN THE UPPER TRIANGLE OF A (THE ELEMENTS
A[I,J] WITH I < J) THE SUPERDIAGONAL
ELEMENTS OF THE UPPER-TRIANGULAR MATRIX, PRODUCED BY
THE HOUSEHOLDER TRANSFORMATION; IN THE OTHER PART OF
THE COLUMNS OF A THE SIGNIFICANT ELEMENTS OF THE
GENERATING VECTORS OF THE HOUSEHOLDER MATRICES USED
FOR THE HOUSEHOLDER TRIANGULARIZATION;
N : <ARITHMETIC EXPRESSION>;
NUMBER OF ROWS OF THE MATRIX;
M : <ARITHMETIC EXPRESSION>;
NUMBER OF COLUMNS OF THE MATRIX (N >= M);
AUX : <ARRAY IDENTIFIER>;
"ARRAY" AUX[2 : 5];
ENTRY : AUX[2] CONTAINS A RELATIVE TOLERANCE USED FOR
CALCULATING THE DIAGONAL ELEMENTS OF THE
UPPER-TRIANGULAR MATRIX;
EXIT :
AUX[3] DELIVERS THE NUMBER OF THE DIAGONAL ELEMENTS OF
THE UPPER-TRIANGULAR MATRIX WHICH HAVE BEEN FOUND NOT
NEGLIGIBLE;
NORMAL EXIT AUX[3] = M;
AUX[5] := THE MAXIMUM OF THE EUCLIDEAN NORMS OF THE
COLUMNS OF THE GIVEN MATRIX;
AID : <ARRAY IDENTIFIER>;
"ARRAY" AID[1 : M];
NORMAL EXIT (AUX[3] = M) : AID CONTAINS THE DIAGONAL
ELEMENTS OF THE UPPER-TRIANGULAR MATRIX PRODUCED BY THE
HOUSEHOLDER TRIANGULARIZATION;
CI : <ARRAY IDENTIFIER>;
"INTEGER""ARRAY" CI[1 : M];
EXIT : CI CONTAINS THE PIVOTAL INDICES OF THE
INTERCHANGES OF THE COLUMNS OF THE GIVEN MATRIX.
PROCEDURES USED :
TAMMAT = CP34014,
ELMCOL = CP34023,
ICHCOL = CP34031.
REQUIRED CENTRAL MEMORY :
EXECUTION FIELD LENGTH : AN ARRAY OF M ELEMENTS IS DECLARED.
RUNNING TIME:
(C1 * M + C2) * M * (N - M / 3);
THE CONSTANTS C1 AND C2 DEPEND ON THE
ARITHMETIC OF THE COMPUTER.
LANGUAGE : ALGOL 60.
METHOD AND PERFORMANCE :
THE PROCEDURE LSQORTDEC IS A MODIFICATION OF THE PROCEDURE LSQDEC
DUE TO T.J. DEKKER (SEE REF [1], WHERE A DERIVATION IS GIVEN OF
A SET OF PROCEDURES BY
P. BUSINGER AND G.H. GOLUB, SEE REF [2]). THE METHOD IS
HOUSEHOLDER TRIANGULARIZATION WITH COLUMN INTERCHANGES.
LET M DENOTE THE GIVEN MATRIX. LSQORTDEC PRODUCES AN N-TH ORDER
ORTHOGONAL MATRIX Q AND AN N * M UPPER-TRIANGULAR MATRIX R SUCH
THAT R EQUALS QM WITH PERMUTED COLUMNS, Q IS THE PRODUCT OF
AT MOST M HOUSEHOLDER MATRICES WHICH ARE REPRESENTED BY THEIR
GENERATING VECTORS. M IS REDUCED TO R IN AT MOST M STAGES : AT
THE K-TH STAGE THE K-TH COLUMN OF THE (ALREADY MODIFIED) MATRIX IS
INTERCHANGED WITH THE COLUMN OF MAXIMUM EUCLIDEAN NORM (THE
PIVOTAL COLUMN); THEN THE MATRIX IS MULTIPLIED WITH A HOUSEHOLDER
MATRIX SUCH, THAT THE SUBDIAGONAL ELEMENTS OF THE K-TH COLUMN
BECOME ZERO, WHILE THE FIRST K - 1 COLUMNS REMAIN UNCHANGED.
THE PROCESS TERMINATES PREMATURELY, IF AT SOME STAGE THE
EUCLIDEAN NORM OF THE PIVOTAL COLUMN IS LESS THAN SOME TOLERANCE,
VIZ. A GIVEN TOLERANCE (AUX[2]) TIMES THE MAXIMUM OF THE
EUCLIDEAN NORMS OF THE COLUMNS OF THE GIVEN MATRIX.
LSQORTDEC DELIVERS THE SIGNIFICANT ELEMENTS OF THE GENERATING
VECTOR OF THE K-TH HOUSEHOLDER MATRIX (THE FIRST K - 1
ELEMENTS OF THIS VECTOR BEING ZERO) IN THE LOWER TRIANGLE PART OF
THE K-TH COLUMN OF THE ARRAY A (A[I,K] FOR I >= K).
OF THE RESULTING UPPER-TRIANGULAR MATRIX THE
DIAGONAL ELEMENTS ARE DELIVERED SEPARATELY IN AN ARRAY AID, AND THE
REMAINING ELEMENTS IN THE SUPER-TRIANGULAR PART OF THE ARRAY A.
FOR THE SOLUTION OF LEAST SQUARES PROBLEMS, ONLY CALLS WITH
N >= M ARE USEFUL.
REFERENCES :
[1] DEKKER, T.J. :
ALGOL 60 PROCEDURES IN NUMERICAL ALGEBRA, PART 1,
MC TRACT 22, 1968, MATHEMATISCH CENTRUM, AMSTERDAM.
[2] BUSINGER, P. AND G.H. GOLUB :
LINEAR LEAST SQUARES SOLUTION BY HOUSEHOLDER TRANSFORMATIONS,
NUM. MATH. 7 (1965), PP. 269 - 276.
EXAMPLE OF USE :
SEE EXAMPLE OF USE OF LSQSOL.
SUBSECTION : LSQDGLINV.
CALLING SEQUENCE :
THE HEADING OF THE PROCEDURE IS :
"PROCEDURE" LSQDGLINV(A, M, AID, CI, DIAG); "VALUE" M; "INTEGER" M;
"INTEGER""ARRAY" CI; "ARRAY" A, AID, DIAG;
"CODE" 34132;
THE MEANING OF THE FORMAL PARAMETERS IS :
A, M, AID, CI :
SEE 'CALLING SEQUENCE' OF LSQORTDEC (THIS SECTION);
THE CONTENTS OF A, AID AND CI SHOULD BE PRODUCED BY A
SUCCESSFUL CALL OF LSQORTDEC (AUX[3] = M) .
DIAG : <ARRAY IDENTIFIER>; "ARRAY" DIAG[1 : M];
EXIT : THE DIAGONAL ELEMENTS OF THE INVERSE OF M'M
WHERE M IS THE MATRIX OF THE LINEAR LEAST SQUARES
PROBLEM.
PROCEDURES USED :
VECVEC = CP34010,
TAMVEC = CP34012.
RUNNING TIME :
(C3 * M + C4) * M * M;
THE CONSTANTS C3 AND C4 DEPEND ON THE ARITHMETIC
OF THE COMPUTER.
LANGUAGE : ALGOL 60.
METHOD AND PERFORMANCE :
LSQDGLINV SHOULD BE CALLED AFTER A SUCCESSFUL CALL OF LSQORTDEC,
I.E. IF AUX[3] = M. LSQDGLINV CALCULATES THE DIAGONAL ELEMENTS
OF THE INVERSE OF M'M, WHERE M IS THE MATRIX OF A LINEAR
LEAST SQUARES PROBLEM.
THESE VALUES CAN BE USED FOR THE COMPUTATION OF THE STANDARD
DEVIATIONS OF LEAST SQUARES SOLUTIONS.
EXAMPLE OF USE :
SEE EXAMPLE OF USE OF LSQSOL.
SOURCE TEXT(S) :
"CODE" 34134;
"CODE" 34132;