NUMAL Section 3.1.2.1.1.1.2.3
BEGIN SECTION : 3.1.2.1.1.1.2.3 (June, 1974)
AUTHOR: W. HOFFMANN.
CONTRIBUTOR: J. C. P. BUS.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731210.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS FOUR PROCEDURES
FOR SOLVING A SYSTEM OF LINEAR EQUATIONS WITH A
TRIDIAGONAL MATRIX;
SOLTRI CALCULATES A SOLUTION BY FORWARD AND BACK SUBSTITUTION IF
THE TRIANGULAR DECOMPOSED FORM AS DELIVERED BY DECTRI IS GIVEN.
DECSOLTRI PERFORMS THE TRIANGULAR DECOMPOSITION OF THE GIVEN
MATRIX ( NOT USING ANY PIVOTING STRATEGY DURING THE PROCESS ) AND
CALCULATES THE SOLUTION BY FORWARD AND BACK SUBSTITUTION.
SOLTRIPIV CALCULATES A SOLUTION BY FORWARD AND BACK SUBTITUTION,IF
THE TRIANGULAR DECOMPOSED FORM AS DELIVERED BY DECTRIPIV IS GIVEN.
DECSOLTRIPIV PERFORMS THE TRIANGULAR DECOMPOSITION OF THE GIVEN
MATRIX ( USING PARTIAL PIVOTING ) AND CALCULATES THE SOLUTION BY
FORWARD AND BACK SUBSTITUTION.
KEYWORDS:
ALGEBRAIC EQUATIONS,
LINEAR SYSTEMS,
TRIDIAGONAL MATRIX,
FORWARD AND BACK SUBSTITUTION.
SUBSECTION: SOLTRI.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" SOLTRI(SUB, DIAG, SUPER, N, B);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, B;
"CODE" 34424;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1, N - 1];
ENTRY : THE SUBDIAGONAL OF THE
LOWER-BIDIAGONAL MATRIX, AS DELIVERED BY DECTRI (SECTION
3.1.2.1.1.1.2.1);
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1:N];
ENTRY : THE DIAGONAL OF THE LOWER-
BIDIAGONAL MATRIX, AS DELIVERED BY DECTRI;
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY : THE SUPERDIAGONAL OF THE
UPPER-BIDIAGONAL MATRIX AS DELIVERED BY DECTRI;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
EXIT: THE CALCULATED SOLUTION OF THE LINEAR SYSTEM.
PROCEDURES USED: NONE.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
SOLTRI CALCULATES THE SOLUTION OF A LINEAR SYSTEM WITH A
TRIDIAGONAL MATRIX, WITH FORWARD AND BACK SUBSTITUTION; THE
TRIANGULARLY DECOMPOSED FORM OF THE MATRIX, AS PRODUCED BY DECTRI
(SECTION 3.1.2.1.1.1.2.1), SHOULD BE GIVEN; ONE CALL OF DECTRI
FOLLOWED BY SEVERAL CALLS OF SOLTRI MAY BE USED TO SOLVE SEVERAL
LINEAR SYSTEMS HAVING THE SAME TRIDIAGONAL MATRIX, BUT DIFFERENT
RIGHT-HAND SIDES.
EXAMPLE OF USE: SEE DECSOLTRI (THIS SECTION).
SUBSECTION: DECSOLTRI.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" DECSOLTRI(SUB, DIAG, SUPER, N, AUX, B);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AUX, B;
"CODE" 34425;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1: N - 1];
ENTRY: THE SUBDIAGONAL OF THE GIVEN MATRIX T, SAY;
T[I + 1, I] SHOULD BE GIVEN IN SUB[I], I = 1,
..., N - 1;
EXIT: SUPPOSE L DENOTES THE LOWER-BIDIAGONAL MATRIX, SUCH
THAT LU = T, FOR SOME UPPER-BIDIAGONAL MATRIX U,
WITH UNIT DIAGONAL ELEMENTS, THEN L[I + 1, I] WILL
BE DELIVERED IN SUB[I], I = 1, ..., AUX[3] - 1;
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1: N];
ENTRY: THE DIAGONAL OF T;
EXIT: L[I, I] WILL BE DELIVERED IN DIAG[I], I = 1, ...,
AUX[3];
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY: THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
IN SUPER[I], I = 1, ..., N - 1;
EXIT: U[I, I + 1] WILL BE DELIVERED IN SUPER[I], I = 1,
..., AUX[3] - 1;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:5];
ENTRY :
AUX[2]: A RELATIVE TOLERANCE; A REASONABLE CHOICE FOR THIS
VALUE IS AN ESTIMATE OF THE RELATIVE PRECISION OF
THE MATRIX ELEMENTS, HOWEVER, IT SHOULD NOT BE
CHOSEN SMALLER THAN THE MACHINE PRECISION;
EXIT :
AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
NORM OF THE MATRIX (SEE SECTION 3.1.2.1.1.1.2.1,
SUBSECTION DECTRI);
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
EXIT: IF AUX[3] = N, THEN THE SOLUTION OF THE LINEAR
SYSTEM IS OVERWRITTEN ON B, ELSE B REMAINS
UNALTERED.
PROCEDURES USED:
DECTRI = CP34423,
SOLTRI = CP34424.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
DECSOLTRI CALCULATES THE SOLUTION OF A LINEAR SYSTEM WITH A
TRIDIAGONAL MATRIX; THE TRIANGULAR DECOMPOSITION IS DONE BY CALLING
DECTRI (SECTION 3.1.2.1.1.1.2.1) AND THE FORWARD AND BACK
SUBSTITUTION BY CALLING SOLTRI (THIS SECTION); IF AUX[3] < N, THEN
THE EFFECT OF DECSOLTRI IS MERELY THAT OF DECTRI.
EXAMPLE OF USE:
LET T BE A TRIDIAGONAL MATRIX WITH SUBDIAGONAL AND SUPERDIAGONAL
ELEMENTS I * 2 AND I RESPECTIVELY (I = 1, ..., N - 1), AND DIAGONAL
ELEMENTS I + 10 (I = 1, ..., N); LET B BE THE SECOND COLUMN OF T;
THEN THE SOLUTION OF THE LINEAR SYSTEM TX = B IS GIVEN BY THE
SECOND UNIT VECTOR; BY THE FOLLOWING PROGRAM WE MAY SOLVE THIS
SYSTEM AND PRINT THE ERROR IN THE CALCULATED SOLUTION.
"BEGIN"
"INTEGER" I;
"ARRAY" D, SUB, SUPER, B[1:30], AUX[2:5];
"FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
"BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
B[I]:= 0
"END"; B[1]:= 1; B[2]:= 12; B[3]:= 4;
AUX[2]:= "-14;
DECSOLTRI(SUB, D, SUPER, 30, AUX, B);
OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
AUX[3], AUX[5]);
B[2]:= B[2] - 1;
OUTPUT(71, "("//"("ERROR IN THE SOLUTION: ")", N")",
SQRT(VECVEC(1, 30, 0, B, B)))
"END"
RESULTS:
AUX[3] AND AUX[5]:
+3.0000000000000"+001
+1.2400000000000"+002
ERROR IN THE SOLUTION: +0.0000000000000"+000
SUBSECTION: SOLTRIPIV.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" SOLTRIPIV(SUB, DIAG, SUPER, N, AID, PIV, B);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AID, B;
"BOOLEAN" "ARRAY" PIV;
"CODE" 34427;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1, N - 1];
ENTRY : THE SUBDIAGONAL OF THE
LOWER-BIDIAGONAL MATRIX, AS DELIVERED BY DECTRIPIV (SECTION
3.1.2.1.1.1.2.1);
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1:N];
ENTRY: THE DIAGONAL OF THE LOWER-
BIDIAGONAL MATRIX, AS DELIVERED BY DECTRIPIV;
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY : THE FIRST CODIAGONAL OF
THE UPPER-TRIANGULAR MATRIX AS DELIVERED BY DECTRIPIV;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
AID: <ARRAY IDENTIFIER>;
"ARRAY" AID[1: N - 2];
ENTRY: THE SECOND CODIAGONAL OF
THE UPPER-TRIANGULAR MATRIX AS DELIVERED BY DECTRIPIV;
PIV: <ARRAY IDENTIFIER>;
"BOOLEAN""ARRAY" PIV[1: N-1];
ENTRY: THE PIVOT-
INFORMATION AS DELIVERED BY DECTRIPIV;
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1:N];
ENTRY: THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
EXIT: THE CALCULATED SOLUTION OF THE LINEAR SYSTEM.
PROCEDURES USED: NONE.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
SOLTRIPIV CALCULATES THE SOLUTION OF A LINEAR SYSTEM WITH A
TRIDIAGONAL MATRIX, WITH FORWARD AND BACK SUBSTITUTION; THE
TRIANGULARLY DECOMPOSED FORM OF THE MATRIX,AS PRODUCED BY DECTRIPIV
(SECTION 3.1.2.1.1.1.2.1), SHOULD BE GIVEN; ONE CALL OF DECTRIPIV
FOLLOWED BY SEVERAL CALLS OF SOLTRIPIV MAY BE USED TO SOLVE SEVERAL
LINEAR SYSTEMS HAVING THE SAME TRIDIAGONAL MATRIX, BUT DIFFERENT
RIGHT-HAND SIDES.
EXAMPLE OF USE:
LET T BE THE MATRIX AS GIVEN IN THE EXAMPLE OF USE OF DECSOLTRI
(THIS SECTION) AND LET B1 AND B2 BE THE SECOND AND THIRD COLUMN OF
T, THEN THE SOLUTIONS OF THE LINEAR SYSTEMS TX = B1 AND TX = B2
ARE GIVEN BY THE SECOND AND THIRD UNIT VECTOR RESPECTIVELY; IN THE
FOLLOWING PROGRAM THESE SYSTEMS ARE SOLVED AND THE ERRORS IN THE
CALCULATED SOLUTIONS ARE PRINTED.
"BEGIN"
"INTEGER" I;
"ARRAY" D, SUB, SUPER, AID, B1, B2[1:30], AUX[2:5];
"BOOLEAN" "ARRAY" PIV[1:29];
"FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
"BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
B1[I]:= B2[I]:= 0
"END"; B1[1]:= 1; B1[2]:= 12; B1[3]:= 4;
B2[2]:= 2; B2[3]:= 13; B2[4]:= 6;
AUX[2]:= "-14;
DECTRIPIV(SUB, D, SUPER, 30, AID, AUX, PIV);
SOLTRIPIV(SUB, D, SUPER, 30, AID, PIV, B1);
SOLTRIPIV(SUB, D, SUPER, 30, AID, PIV, B2);
OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
AUX[3], AUX[5]);
B1[2]:= B1[2] - 1; B2[3]:= B2[3] - 1;
OUTPUT(71, "("//"("ERROR IN B1: ")",N,/,"("ERROR IN B2: ")",N")",
SQRT(VECVEC(1, 30, 0, B1, B1)), SQRT(VECVEC(1, 30, 0, B2, B2)))
"END"
RESULTS:
AUX[3] AND AUX[5]:
+3.0000000000000"+001
+1.2400000000000"+002
ERROR IN B1: +0.0000000000000"+000
ERROR IN B2: +0.0000000000000"+000
SUBSECTION: DECSOLTRIPIV.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" DECSOLTRIPIV(SUB, DIAG, SUPER, N, AUX, B);
"VALUE" N; "INTEGER" N; "ARRAY" SUB, DIAG, SUPER, AUX, B;
"CODE" 34428;
THE MEANING OF THE FORMAL PARAMETERS IS:
SUB: <ARRAY IDENTIFIER>;
"ARRAY" SUB[1: N - 1];
ENTRY: THE SUBDIAGONAL OF THE GIVEN MATRIX T, SAY;
T[I + 1, I] SHOULD BE GIVEN IN SUB[I], I = 1,
..., N - 1;
EXIT: THE ELEMENTS OF SUB WILL BE OVERWRITTEN;
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1: N];
ENTRY: THE DIAGONAL OF T;
EXIT: THE ELEMENTS OF DIAG WILL BE OVERWRITTEN;
SUPER: <ARRAY IDENTIFIER>;
"ARRAY" SUPER[1: N - 1];
ENTRY: THE SUPERDIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN
IN SUPER[I], I = 1, ..., N - 1;
EXIT: THE ELEMENTS OF SUPER WILL BE OVERWRITTEN;
N: <ARITHMETICAL EXPRESSION>;
THE ORDER OF THE MATRIX;
AUX: <ARRAY IDENTIFIER>;
"ARRAY" AUX[2:5];
ENTRY:
AUX[2]: A RELATIVE TOLERANCE; A REASONABLE CHOICE FOR THIS
VALUE IS AN ESTIMATE OF THE RELATIVE PRECISION OF
THE MATRIX ELEMENTS, HOWEVER, IT SHOULD NOT BE
CHOSEN SMALLER THAN THE MACHINE PRECISION;
EXIT:
AUX[3]: THE NUMBER OF ELIMINATION STEPS PERFORMED;
AUX[5]: IF AUX[3] = N, THEN AUX[5] WILL EQUAL THE INFINITY-
NORM OF THE MATRIX (SEE SECTION 3.1.2.1.1.1.2.1.,
SUBSECTION DECTRIPIV);
B: <ARRAY IDENTIFIER>;
"ARRAY" B[1 : N];
ENTRY: THE RIGHT-HAND SIDE OF THE LINEAR SYSTEM;
EXIT: IF AUX[3] = N, THEN THE SOLUTION OF THE LINEAR
SYSTEM WILL BE OVERWRITTEN ON B, ELSE B WILL REMAIN
UNALTERED.
PROCEDURES USED: NONE.
REQUIRED CENTRAL MEMORY:
EXECUTION FIELD LENGTH: ONE AUXILIARY ARRAY OF TYPE BOOLEAN AND
ORDER N IS DECLARED IN DECSOLTRIPIV;
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
ONE CALL OF DECSOLTRIPIV IS EQUIVALENT WITH CALLING CONSECUTIVELY
DECTRIPIV (SECTION 3.1.2.1.1.1.2.1) AND SOLTRIPIV (THIS SECTION);
HOWEVER, DECSOLTRIPIV DOES NOT MAKE USE OF DECTRIPIV AND SOLTRIPIV,
TO SAVE MEMORY SPACE AND TIME; THIS IS ONLY TRUE IN THE CASE THAT
LINEAR SYSTEMS WITH DIFFERENT MATRICES HAVE TO BE SOLVED; IF
AUX[3] < N THEN
DECSOLTRIPIV IS TERMINATED PREMATURELY (SEE DECTRIPIV IN SECTION
3.1.2.1.1.1.2.1).
EXAMPLE OF USE:
THE SAME LINEAR SYSTEM AS GIVEN IN THE EXAMPLE OF USE OF DECSOLTRI
MAY BE SOLVED WITH DECSOLTRIPIV BY THE FOLLOWING PROGRAM:
"BEGIN"
"INTEGER" I;
"ARRAY" D, SUB, SUPER, B[1:30], AUX[2:5];
"FOR" I:= 1 "STEP" 1 "UNTIL" 30 "DO"
"BEGIN" SUB[I]:= I * 2; SUPER[I]:= I; D[I]:= I + 10;
B[I]:= 0
"END"; B[1]:= 1; B[2]:= 12; B[3]:= 4;
AUX[2]:= "-14;
DECSOLTRIPIV(SUB, D, SUPER, 30, AUX, B);
OUTPUT(71, "("/,"("AUX[3] AND AUX[5]:")",2(/,N)")",
AUX[3], AUX[5]);
B[2]:= B[2] - 1;
OUTPUT(71, "("//"("ERROR IN THE SOLUTION: ")", N")",
SQRT(VECVEC(1, 30, 0, B, B)))
"END"
RESULTS:
AUX[3] AND AUX[5]:
+3.0000000000000"+001
+1.2400000000000"+002
ERROR IN THE SOLUTION: +0.0000000000000"+000
SOURCE TEXTS:
"CODE" 34424;
"CODE" 34425;
"CODE" 34427;
"CODE" 34428;