For a matrix denoted by , we write for the submatrix formed from the rows through and the columns from through of the matrix. We also denote and by and , respectively. (Note that they are row and column vectors, respectively.)
Assume below that is an nonsingular matrix which can be LU factorized. In addition, assume that a positive integer exists such that all entries in the -th sub- and super-diagonal of are zero if . Namely, if , is zero.
We denote the LU factorization of by , where is a lower triangular matrix with unit diagonal elements, and is an upper triangular matrix.
The following algorithm P computes and from the input in-place in such a way that the strictly lower triangular part and the upper triangular part of will be and , respectively. In other words, will be for , and will be for , when it terminates.
for (k = 1; k < n; k = k + 1) { A[k+1:n,k] <- A[k+1:n,k] * (1 / A[k,k]); A[k+1:n,k+1:n] <- A[k+1:n,k+1:n] - A[k+1:n,k] * A[k,k+1:n]; }
Answer the following questions.
(1) Compute the LU factorization of the following matrix.
(2) Prove that and if .
(3) Assume that , , and . We wish to solve a set of linear systems,
where are the constant vectors, and are the unknown vectors. Explain the relative merits of the following methods (I) and (II) with respect to the amount of arithmetic operations.
(I) Compute first, and then compute each as .
(II) Compute the LU factorization of first, and then solve for . Solve for lastly.
Given that is banded with bandwidth , meaning for . The LU factorization maintains this band structure:
Lower Triangular Matrix :
By definition, has non-zero entries only in the lower triangular part and on the diagonal. For , because for these entries. Hence, also maintains the band structure.
Upper Triangular Matrix :
Similarly, has non-zero entries only in the upper triangular part. For , because for these entries. Hence, maintains the band structure.
Both methods have the same asymptotic complexity .
Efficiency in Practice:
Method (II) is generally more efficient and numerically stable because it avoids directly computing the inverse of , which can be computationally expensive and prone to numerical errors.
Storage Requirements:
Method (I) requires storing , which can be memory-intensive.
Method (II) only requires storing the LU factors, which is typically more storage-efficient.
Conclusion:
Method (II) is preferred due to its numerical stability and potentially lower storage requirements, even though both methods have the same theoretical computational complexity.