IS CS-2019S2-05

题目来源：Problem 5 日期：2024-08-03 题目主题：Math-线性代数-矩阵分解

Solution

1. Cholesky Decomposition Reduction

To derive the Cholesky decomposition of an $n-1$ dimensional real symmetric matrix from that of an $n$ dimensional matrix $\mathbf{A}$, we start with the given lower triangular matrix $\mathbf{L}$:

$$\mathbf{L}=\left(\begin{array}{cc}{\lambda }_1& 0\\ {\mathbf{\ell }}_1& {\mathbf{L}}^{(1)}\end{array}\right),$$

where ${\lambda }_1$ is a positive real number, ${\mathbf{\ell }}_1$ is an $n-1$ dimensional real vector, and ${\mathbf{L}}^{(1)}$ is an $n-1$ dimensional real lower triangular matrix whose diagonal entries are all positive. Given the Cholesky decomposition of $\mathbf{A}$:

$$\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\top },$$

we can expand the matrix multiplication:

$$\mathbf{A}=\left(\begin{array}{cc}{\lambda }_1& 0\\ {\mathbf{\ell }}_1& {\mathbf{L}}^{(1)}\end{array}\right)\left(\begin{array}{cc}{\lambda }_1& {\mathbf{\ell }}_1^{\top }\\ 0& {\mathbf{L}}^{(1)\top }\end{array}\right)=\left(\begin{array}{cc}{\lambda }_1^2& {\lambda }_1{\mathbf{\ell }}_1^{\top }\\ {\lambda }_1{\mathbf{\ell }}_1& {\mathbf{\ell }}_1{\mathbf{\ell }}_1^{\top }+{\mathbf{L}}^{(1)}{\mathbf{L}}^{(1)\top }\end{array}\right).$$

Here, the top left element ${\lambda }_1^2$ represents the $(1,1)$-entry of $\mathbf{A}$, the vector ${\lambda }_1{\mathbf{\ell }}_1$ represents the first row of $\mathbf{A}$ (excluding the $(1,1)$-entry), and the matrix ${\mathbf{\ell }}_1{\mathbf{\ell }}_1^{\top }+{\mathbf{L}}^{(1)}{\mathbf{L}}^{(1)\top }$ represents the $(n-1)\times (n-1)$ dimensional block of $\mathbf{A}$ after the first row and first column.

Thus, the matrix $\mathbf{A}$ can be represented in block form as:

$$\mathbf{A}=\left(\begin{array}{cc}{a}_{11}& {\mathbf{a}}_{12}^{\top }\\ {\mathbf{a}}_{12}& {\mathbf{A}}_{22}\end{array}\right),$$

where $a_{11}={\lambda }_1^2$, ${\mathbf{a}}_{12}={\lambda }_1{\mathbf{\ell }}_1$, and ${\mathbf{A}}_{22}={\mathbf{\ell }}_1{\mathbf{\ell }}_1^{\top }+{\mathbf{L}}^{(1)}{\mathbf{L}}^{(1)\top }$. The $n-1$ dimensional real symmetric matrix ${\mathbf{A}}_{22}$ can thus be decomposed as ${\mathbf{L}}^{(1)}{\mathbf{L}}^{(1)\top }$, completing the reduction.

2. Solving a System of Linear Equations

To solve a system of linear equations $\mathbf{Ax}=\mathbf{b}$ where $\mathbf{A}$ is positive-definite, we use the Cholesky decomposition:

1. Compute Cholesky Decomposition: $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\top }$.
2. Solve $\mathbf{Ly}=\mathbf{b}$: Perform forward substitution to find $\mathbf{y}$.
3. Solve ${\mathbf{L}}^{\top }\mathbf{x}=\mathbf{y}$: Perform backward substitution to find $\mathbf{x}$.

3. Positivity of the $(1,1)$-entry of $\mathbf{A}$

To prove that the $(1,1)$-entry of $\mathbf{A}$ is positive, we rely on the fact that $\mathbf{A}$ is a positive-definite matrix. A real symmetric matrix $\mathbf{A}$ is positive-definite if and only if all its leading principal minors are positive.

The $(1,1)$-entry of $\mathbf{A}$, denoted as $a_{11}$, is the first leading principal minor of the matrix $\mathbf{A}$. For $\mathbf{A}$ to be positive-definite, this minor must be positive. Therefore, $a_{11}>0$. This result holds because positive-definite matrices have all positive eigenvalues, and the $(1,1)$-entry is also the first leading principal minor.

4. Total Number of Arithmetic Operations for Cholesky Decomposition

To determine the total number of arithmetic operations required for the Cholesky decomposition of an $n\times n$ positive-definite real symmetric matrix $\mathbf{A}$, we consider the steps involved in computing the lower triangular matrix $\mathbf{L}$, where $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\top }$. The operations include:

1. Calculation of Diagonal Elements: The diagonal elements ${\lambda }_i$ are computed as:

   $${\lambda }_i=\sqrt{a_{ii}-\sum _{k=1}^{i-1}{\ell }_{ik}^2}$$

   This involves:

   • Calculating the sum ${\sum }_{k=1}^{i-1}{\ell }_{ik}^2$, which requires $(i-1)$ multiplications and $(i-2)$ additions.
   • A subtraction from $a_{ii}$ with ${\sum }_{k=1}^{i-1}{\ell }_{ik}^2$.
   • Taking the square root, which is considered a constant-time operation.

   The total operations for all diagonal elements are approximately:

   $$\sum _{i=1}^n\left((i-1)+(i-2)+1+1\right)=\sum _{i=1}^n(2i-1)=2\sum _{i=1}^{n}i-n$$ $$=2\frac{n(n+1)}{2}-n=n(n+1)-n=n^2$$

2. Calculation of Off-diagonal Elements: The off-diagonal elements ${\ell }_{ij}$ for $j<i$ are computed as:

   $${\ell }_{ij}=\frac{1}{{\lambda }_i}(a_{ij}-\sum _{k=1}^{j-1}{\ell }_{ik}{\ell }_{jk})$$

   This involves:

   • Calculating the product ${\ell }_{ik}{\ell }_{jk}$ for $k=1$ to $j-1$, which requires $(j-1)$ multiplications.
   • Summing these products, which requires $(j-2)$ additions.
   • Subtracting the sum from $a_{ij}$, which requires one subtraction.
   • Dividing by ${\lambda }_i$, which requires one division.

   The total operations for all off-diagonal elements are:

   $$\sum _{i=2}^n\sum _{j=1}^{i-1}\left((j-1)+(j-2)+2\right)=\sum _{i=2}^n\sum _{j=1}^{i-1}(2j-1)$$ $$=\sum _{i=2}^n\left(\frac{(2i-1)(i-1)}{2}\right)=\frac{1}{2}\sum _{i=2}^n(2i-1)(i-1)$$ $$=\frac{1}{2}\left(\sum _{i=1}^n(2i-1)(i-1)-1\right)=\frac{1}{2}\left(\frac{4n^3-3n^2-n}{6}-1\right)$$

For large $n$, the dominant term is:

$$\frac{n^3}{3}$$

Thus, the total number of arithmetic operations required for the Cholesky decomposition of $\mathbf{A}$ is approximately $c\times n^p$ with $c=\frac{1}{3}$ and $p=3$. This means that the complexity of the Cholesky decomposition scales as $O(n^3)$, where the constant factor $\frac{1}{3}$ indicates the proportion of operations compared to the cubic growth rate.

知识点

Cholesky分解正定矩阵矩阵分解线性方程组复杂度分析

重点词汇

Cholesky decomposition Cholesky 分解

positive-definite 正定

lower triangular matrix 下三角矩阵

arithmetic operations 四则运算

参考资料

1. Matrix Computations by Gene H. Golub and Charles F. Van Loan, Chap. 4, Sections 4.2 and 4.3.
2. Introduction to Linear Algebra by Gilbert Strang, Chap. 5, Section 5.6.