IS CS-2022W-01

题目来源：Problem 1 日期：2024-07-04 题目主题：CS-算法-矩阵分解

具体题目

1. Compute the LU factorization of the following matrix.

$$\mathbf{A}=\left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 1& 1& 0\\ 0& -2& 2& 1\\ 0& 0& -3& 3\end{array}\right)$$

1. Prove that $L_{i,j}=0$ and $U_{i,j}=0$ if $|i-j|>w$.

2. Assume that $n\gg 1$, $w\ll n$, and $m\gg n$. We wish to solve a set of linear systems,

$$\mathbf{A}{\mathbf{x}}_i={\mathbf{b}}_i,i=1,2,\dots ,m,$$

where ${\mathbf{b}}_i(i=1,2,\dots ,m)$ are the constant vectors, and ${\mathbf{x}}_i(i=1,2,\dots ,m)$ 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 ${\mathbf{A}}^{-1}$ first, and then compute each ${\mathbf{x}}_i$ as ${\mathbf{A}}^{-1}{\mathbf{b}}_i$.

(II) Compute the LU factorization of $\mathbf{A}$ first, and then solve $\mathbf{L}{\mathbf{y}}_i={\mathbf{b}}_i$ for ${\mathbf{y}}_i$. Solve $\mathbf{U}{\mathbf{x}}_i={\mathbf{y}}_i$ lastly.

正确解答

1. Compute the LU factorization of $\mathbf{A}$

We start by applying the given algorithm P to compute the LU factorization of $\mathbf{A}$.

Step-by-step computation:

1. Initial matrix $\mathbf{A}$:

$$\mathbf{A}=\left(\begin{array}{cccc}1& 1& 0& 0\\ -1& 1& 1& 0\\ 0& -2& 2& 1\\ 0& 0& -3& 3\end{array}\right)$$

1. First iteration ($k=1$):
   • Update $A[2:4,1]$ by dividing by $A[1,1]$:

$$A[2:4,1]\leftarrow A[2:4,1]\times (1/A[1,1])=\left(\begin{array}{c}-1\\ 0\\ 0\end{array}\right)\times 1=\left(\begin{array}{c}-1\\ 0\\ 0\end{array}\right)$$

• Update $A[2:4,2:4]$:

$$A[2:4,2:4]\leftarrow A[2:4,2:4]-A[2:4,1]\times A[1,2:4]=\left(\begin{array}{ccc}1& 1& 0\\ -2& 2& 1\\ 0& -3& 3\end{array}\right)-\left(\begin{array}{c}-1\\ 0\\ 0\end{array}\right)\times \left(\begin{array}{ccc}1& 0& 0\end{array}\right)$$

Simplifying:

$$A[2:4,2:4]=\left(\begin{array}{ccc}2& 1& 0\\ -2& 2& 1\\ 0& -3& 3\end{array}\right)$$

1. Second iteration ($k=2$):
   • Update $A[3:4,2]$ by dividing by $A[2,2]$:

$$A[3:4,2]\leftarrow A[3:4,2]\times (1/A[2,2])=\left(\begin{array}{c}-2\\ 0\end{array}\right)\times \frac{1}{2}=\left(\begin{array}{c}-1\\ 0\end{array}\right)$$

• Update $A[3:4,3:4]$:

$$A[3:4,3:4]\leftarrow A[3:4,3:4]-A[3:4,2]\times A[2,3:4]=\left(\begin{array}{cc}2& 1\\ -3& 3\end{array}\right)-\left(\begin{array}{c}-1\\ 0\end{array}\right)\times \left(\begin{array}{cc}1& 0\end{array}\right)$$

Simplifying:

$$A[3:4,3:4]=\left(\begin{array}{cc}3& 1\\ -3& 3\end{array}\right)$$

1. Third iteration ($k=3$):
   • Update $A[4,3]$ by dividing by $A[3,3]$:

$$A[4,3]\leftarrow A[4,3]\times (1/A[3,3])=-3\times \frac{1}{3}=-1$$

• Update $A[4,4]$:

$$A[4,4]\leftarrow A[4,4]-A[4,3]\times A[3,4]=3-(-1)\times 1=4$$

The resulting matrices $\mathbf{L}$ and $\mathbf{U}$ are:

$$\mathbf{L}=\left(\begin{array}{cccc}1& 0& 0& 0\\ -1& 1& 0& 0\\ 0& -1& 1& 0\\ 0& 0& -1& 1\end{array}\right),\mathbf{U}=\left(\begin{array}{cccc}1& 1& 0& 0\\ 0& 2& 1& 0\\ 0& 0& 3& 1\\ 0& 0& 0& 4\end{array}\right)$$

2. Prove that $L_{i,j}=0$ and $U_{i,j}=0$ if $|i-j|>w$

Given that $\mathbf{A}$ is banded with bandwidth $w$, meaning $A_{i,j}=0$ for $|i-j|>w$. The LU factorization $\mathbf{A}=\mathbf{LU}$ maintains this band structure:

• Lower Triangular Matrix $\mathbf{L}$:

  • By definition, $\mathbf{L}$ has non-zero entries only in the lower triangular part and on the diagonal. For $|i-j|>w$, $L_{i,j}=0$ because $A_{i,j}=0$ for these entries. Hence, $\mathbf{L}$ also maintains the band structure.

• Upper Triangular Matrix $\mathbf{U}$:

  • Similarly, $\mathbf{U}$ has non-zero entries only in the upper triangular part. For $|i-j|>w$, $U_{i,j}=0$ because $A_{i,j}=0$ for these entries. Hence, $\mathbf{U}$ maintains the band structure.

Therefore, $L_{i,j}=0$ and $U_{i,j}=0$ if $|i-j|>w$.

3. Method Comparison for Solving $\mathbf{A}{\mathbf{x}}_i={\mathbf{b}}_i$

Method (I): Compute ${\mathbf{A}}^{-1}$ first, then ${\mathbf{x}}_i={\mathbf{A}}^{-1}{\mathbf{b}}_i$

• Steps:
  1. Compute ${\mathbf{A}}^{-1}$, which requires $O(n^3)$ operations.
  2. Compute each ${\mathbf{x}}_i={\mathbf{A}}^{-1}{\mathbf{b}}_i$, which requires $O(n^2)$ operations per ${\mathbf{x}}_i$.
  3. Total operations for $m$ systems: $O(n^3)+m\cdot O(n^2)=O(n^3+m{n}^2)$.

Method (II): Compute the LU factorization, then solve $\mathbf{L}{\mathbf{y}}_i={\mathbf{b}}_i$ and $\mathbf{U}{\mathbf{x}}_i={\mathbf{y}}_i$

• Steps:

  1. Compute the LU factorization of $\mathbf{A}$, which requires $O(n^3)$ operations.

  2. Solve $\mathbf{L}{\mathbf{y}}_i={\mathbf{b}}_i$ and $\mathbf{U}{\mathbf{x}}_i={\mathbf{y}}_i$ for each ${\mathbf{x}}_i$, which requires $O(n^2)$ operations per ${\mathbf{x}}_i$.

  3. Total operations for $m$ systems: $O(n^3)+m\cdot O(n^2)=O(n^3+m{n}^2)$.

Comparison

• Arithmetic Operations:

  • Both methods have the same asymptotic complexity $O(n^3+m{n}^2)$.

• Efficiency in Practice:

  • Method (II) is generally more efficient and numerically stable because it avoids directly computing the inverse of $\mathbf{A}$, which can be computationally expensive and prone to numerical errors.

• Storage Requirements:

  • Method (I) requires storing ${\mathbf{A}}^{-1}$, 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.

知识点

LU分解稀疏矩阵复杂度分析 递归内存效率

难点解题思路

对大型稀疏矩阵，直接计算逆矩阵通常会引入数值不稳定性，且计算开销较大。LU 分解通过三角矩阵简化了问题，解决了计算复杂度和数值稳定性的问题。

解题技巧和信息

对于稀疏矩阵的 LU 分解，注意带状结构的保持，有助于减少计算量。在求解线性方程组时，优先考虑分解矩阵的方法以优化计算效率。

重点词汇

1. LU factorization LU 分解
2. band matrix 带状矩阵
3. numerical stability 数值稳定性
4. computational complexity 计算复杂度

参考资料

1. Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations. Johns Hopkins University Press. Chap. 3.
2. Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM. Chap. 21.