NUMAL Section 3.1.2.1.1.2.2.3
BEGIN SECTION : 3.1.2.1.1.2.2.3 (February, 1979)
AUTHOR: W. HOFFMANN.
CONTRIBUTOR: J. C. P. BUS.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 731215.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS TWO PROCEDURES
FOR SOLVING A SYSTEM OF LINEAR EQUATIONS WITH A SYMMETRIC
TRIDIAGONAL MATRIX;
SOLSYMTRI CALCULATES A SOLUTION IF THE
TRIANGULARLY DECOMPOSED FORM, AS DELIVERED BY DECSYMTRI (SECTION
3.1.2.1.1.2.2.1), IS GIVEN;
DECSOLSYMTRI PERFORMS THE TRIANGULAR
DECOMPOSITION AS WELL AS THE FORWARD AND BACK SUBSTITUTION TO
CALCULATE THE SOLUTION OF THE GIVEN LINEAR SYSTEM.
KEYWORDS:
ALGEBRAIC EQUATIONS,
LINEAR SYSTEMS,
SYMMETRIC TRIDIAGONAL MATRIX,
FORWARD AND BACK SUBSTITUTION.
SUBSECTION: SOLSYMTRI.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" SOLSYMTRI(DIAG, CO, N, B);
"VALUE" N; "INTEGER" N; "ARRAY" DIAG, CO, B; "CODE" 34421;
THE MEANING OF THE FORMAL PARAMETERS IS:
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1:N];
ENTRY: THE DIAGONAL MATRIX, AS
DELIVERED BY DECSYMTRI (SECTION 3.1.2.1.1.2.2.1);
CO: <ARRAY IDENTIFIER>;
"ARRAY" CO[1: N - 1];
ENTRY: THE CODIAGONAL OF THE UNIT
UPPER-BIDIAGONAL MATRIX AS DELIVERED BY DECSYMTRI;
N: <ARITHMETIC 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.
METHOD AND PERFORMANCE:
SOLSYMTRI CALCULATES THE SOLUTION OF A LINEAR SYSTEM WITH A
SYMMETRIC TRIDIAGONAL MATRIX, WITH FORWARD AND BACK SUBSTITUTION;
THE TRIANGULARLY DECOMPOSED FORM OF THE MATRIX, AS PRODUCED BY
DECSYMTRI (SECTION 3.1.2.1.1.2.2.1), SHOULD BE GIVEN; ONE CALL OF
DECSYMTRI FOLLOWED BY SEVERAL CALLS OF SOLSYMTRI MAY BE USED TO
SOLVE SEVERAL LINEAR SYSTEMS HAVING THE SAME SYMMETRIC TRIDIAGONAL
MATRIX, BUT DIFFERENT RIGHT HAND SIDES.
EXAMPLE OF USE: SEE DECSOLSYMTRI (THIS SECTION).
SUBSECTION: DECSOLSYMTRI.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"PROCEDURE" DECSOLSYMTRI(DIAG, CO, N, AUX, B);
"VALUE" N; "INTEGER" N; "ARRAY" DIAG, CO, AUX, B; "CODE" 34422;
THE MEANING OF THE FORMAL PARAMETERS IS:
DIAG: <ARRAY IDENTIFIER>;
"ARRAY" DIAG[1: N];
ENTRY: THE DIAGONAL OF THE GIVEN MATRIX T, SAY;
EXIT: SUPPOSE U DENOTES THE UNIT UPPER-BIDIAGONAL MATRIX,
SUCH THAT U'DU = T FOR SOME DIAGONAL MATRIX D,
WHERE U' DENOTES THE TRANSPOSED MATRIX; THEN D[I,I]
WILL BE DELIVERED IN DIAG[I], I = 1, ..., AUX[3];
CO: <ARRAY IDENTIFIER>;
"ARRAY" CO[1: N - 1];
ENTRY: THE CODIAGONAL OF T; T[I, I + 1] SHOULD BE GIVEN IN
CO[I], I = 1, ..., N - 1;
EXIT: U[I, I + 1] WILL BE DELIVERED IN CO[I], I = 1, ...,
AUX[3] - 1;
N: <ARITHMETIC 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, ELSE AUX[5] IS SET EQUAL TO
THE VALUE OF THAT ELEMENT WHICH CAUSES THE
BREAKDOWN OF THE DECOMPOSITION;
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:
DECSYMTRI = CP34420,
SOLSYMTRI = CP34421.
METHOD AND PERFORMANCE:
DECSOLSYMTRI CALCULATES THE SOLUTION OF A LINEAR SYSTEM WITH A
SYMMETRIC TRIDIAGONAL MATRIX; THE TRIANGULAR DECOMPOSITION IS DONE
BY CALLING DECSYMTRI (SECTION 3.1.2.1.1.2.2.1) AND THE FORWARD AND
BACK SUBSTITUTION BY CALLING SOLSYMTRI (THIS SECTION); IF AUX[3]<N,
THEN THE EFFECT OF DECSOLSYMTRI IS MERELY THAT OF DECSYMTRI.
EXAMPLE OF USE:
LET T BE A SYMMETRIC TRIDIAGONAL MATRIX OF ORDER 100 WITH DIAGONAL
ELEMENTS I (I = 1, ..., 100) AND CODIAGONAL ELEMENTS I * 2 (I = 1,
..., 99); LET THE RIGHT HAND SIDE B BE GIVEN BY 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, CO, B[1:100], AUX[2:5];
"FOR" I:= 1 "STEP" 1 "UNTIL" 100 "DO"
"BEGIN" D[I]:= I; CO[I]:= I * 2; B[I]:= 0 "END";
B[1]:= B[2]:= 2; B[3]:= 4;
AUX[2]:= "-14;
DECSOLSYMTRI(D, CO, 100, AUX, B);
B[2]:= B[2] - 1;
OUTPUT(71, "("/,"(" AUX[3] AND AUX[5]:")",2(/4B,N)")",
AUX[3], AUX[5]);
OUTPUT(71, "("//,"(" ERROR IN THE SOLUTION:")",N,/")",
SQRT(VECVEC(1, 100, 0, B, B)))
"END"
RESULTS:
AUX[3] AND AUX[5]:
+1.0000000000000"+002
+4.9300000000000"+002
ERROR IN THE SOLUTION:+0.0000000000000"+000
SOURCE TEXTS:
"CODE" 34421;
"CODE" 34422;