The IMSL_CHNNDSOL function solves a real symmetric nonnegative definite system of linear equations Ax = b. Computes the solution to Ax = b given the Cholesky factor.
This routine requires an IDL Advanced Math and Stats license. For more information, contact your sales or technical support representative.
The IMSL_CHNNDSOL function solves a system of linear algebraic equations having a symmetric nonnegative definite (positive semidefinite) coefficient matrix. It first computes a Cholesky (LLH or RHR) factorization of the coefficient matrix A. The factorization algorithm is based on the work of Healy (1968) and proceeds sequentially by columns. The i-th column is declared to be linearly dependent on the first i – 1 columns if:
where ε (specified by TOLERANCE) may be set. When a linear dependence is declared, all elements in the i-th row of R (column of L) are set to zero. Modifications due to Farebrother and Berry (1974) and Barrett and Healy (1978) for checking for matrices that are not nonnegative definite also are incorporated. The IMSL_CHNNDSOL function declares A to be not nonnegative definite and issues an error message if either of the following conditions is satisfied:
Healy’s (1968) algorithm and the IMSL_CHNNDSOL function permit the matrices A and R to occupy the same storage. Barrett and Healy (1978), in their remark, neglect this fact. The IMSL_CHNNDSOL function uses:
in condition 2 above to remedy this problem.
If an inverse of the matrix A is required and the matrix is not (numerically) positive definite, then the resulting inverse is a symmetric g2 inverse of A. For a matrix G to be a g2 inverse of a matrix A, G must satisfy conditions 1 and 2 for the Moore- Penrose inverse but generally fail conditions 3 and 4. The four conditions for G to be a Moore-Penrose inverse of A are as follows:
- AGA = A
- GAG = G
- AG is symmetric
- GA is symmetric
The solution of the linear system Ax = b is computed by solving the factored version of the linear system RTRx = b as two successive triangular linear systems. In solving the triangular linear systems, if the elements of a row of R are all zero, the corresponding element of the solution vector is set to zero. For a detailed description of the algorithm, see Section 2 in Sallas and Lionti (1988). This routine is useful to solve normal equations in a linear least-squares problem.
Example
A solution to a system of four linear equations is obtained. Maindonald (1984, pp. 83–86, 104–105) discusses the computations for the factorization and solution to this problem.
RM, a, 4, 4
row 0: 36 12 30 6
row 1: 12 20 2 10
row 2: 30 2 29 1
row 3: 6 10 1 14
RM, b, 4, 1
row 0: 18
row 1: 22
row 2: 7
row 3: 20
x = IMSL_CHNNDSOL(b, a)
PM, x
IDL prints:
0.166667
0.500000
0.00000
1.00000
Errors
Warning Errors
MATH_INCONSISTENT_EQUATIONS_2: Linear system of equations is inconsistent.
MATH_NOT_NONNEG_DEFINITE: Matrix A is not non-negative definite.
Syntax
Result = IMSL_CHNNDSOL(B[, A] [, /DOUBLE] [, FACTOR=value] [, INVERSE=variable] [, TOLERANCE=value])
Return Value
A solution x of the linear system Ax = b.
Arguments
B
Matrix containing the right-hand side.
A (optional)
(Optional) Two-dimensional matrix containing the coefficient matrix. Element A(i, j) contains the j-th coefficient of the i-th equation.
Keywords
DOUBLE (optional)
If present and nonzero, double precision is used.
FACTOR (optional)
The LLT factorization of A. The lower-triangular part of this matrix contains L, and the upper-triangular part contains LT.
INVERSE (optional)
Named variable into which the inverse of the matrix A is stored.
TOLERANCE (optional)
Tolerance used in determining linear dependence. Default: 100ε, where ε is machine precision.
Version History
See Also
IMSL_CHNNDFAC, IMSL_LINLSQ, IMSL_QRFAC, IMSL_SVDCOMP