1. 各种分解

1.1 LU 与 LDU 分解

  • 定义：某矩阵 $A=LU$，则 $U$ 是对 $A$ 作行简化后得到的上三角矩阵。

  • 例子： $$ A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 4 & 6 \\ 2 & 2 & 6 \end{pmatrix} \sim \begin{pmatrix} 1 & 2 & 3 \\ 0 & -4 & -6 \\ 0 & -2 & 0 \end{pmatrix} \sim \begin{pmatrix} 1 & 2 & 3 \\ 0 & -4 & -6 \\ 0 & 0 & 3 \end{pmatrix} \leftarrow \text{这个是 } U $$

    • $L$ 是变换阵（消元矩阵的逆）。
    • $L = (l_1, l_2, l_3)$。注意：在变换中的“减”在这里是正数（即乘数）。
    • $l_1 = (1, 4, 2)^T$ (对应第一列消元系数，主元为1，下面分别是4, 2)。
    • $l_2 = (0, 1, 1/2)^T$。
    • $l_3 = (0, 0, 1)^T$。
    • 注意：是要减第 $i$ 行的系数！要依次算！

  • LDU 分解：就是让 $U$ 也成单位上三角，把对角元提入 $D$，自己除以它们。

  • Doolittle 分解法：本质就是：先算 $U$ 第一行，$L$ 第一列，再算 $U$ 第二行，$L$ 第二列……

Cholesky 分解

  • 对象：对半正定（实为对称正定）矩阵 $A$ 的 LDU 分解的转化。
  • 推导： 设 $A=LDU$。由于 $A$ 对称 ($A^T=A$)，推出 $L=U^T$ (即 $U=L^T$)。 即 $A = L D L^T$。 设 $D = \tilde{D} \cdot \tilde{D}$ (直接开根号即可，因为 $A$ 半正定，$U$ 对角线上元素非负)。 则 $A = L \tilde{D} (L \tilde{D})^T$。 记 $\tilde{L} = L \tilde{D}$。有 $A = \tilde{L} \tilde{L}^T$。这就叫 Cholesky 分解。

1.3 满秩分解

  • 定义：某矩阵 $A=FG$，$r(A)=r(F)=r(G)$。$F$ 列满秩，$G$ 行满秩。
  • 方法：仍是对 $A$ 作行初等变换，得到行最简矩阵。
    • 例：$A = \begin{pmatrix} 0 & 1 & 0 & -1 \\ 0 & 2 & 0 & -2 \\ 0 & 3 & 0 & -2 \end{pmatrix} \sim \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ (行最简)。
    • 取 $G = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$ (非零行)。
    • $F = \begin{pmatrix} 1 & -1 \\ 2 & -2 \\ 3 & -2 \end{pmatrix}$ (取 $A$ 中对应主元列的列向量，这里主元在第2、4列)。
  • 理论联系：实际上，相抵分解中 $A = P \begin{bmatrix} I_r & 0 \\ 0 & 0 \end{bmatrix} Q$，有 $F = P \begin{bmatrix} I_r \\ 0 \end{bmatrix}$，$G = [I_r, 0] Q$。

1.4 QR 分解

  • 定义：某矩阵 $A=QR$。其中 $Q$ 是正交矩阵，$R$ 是上三角矩阵（笔记中写“单位上三角”可能有误，通常 $R$ 对角元为正，若 $Q$ 未单位化则 $R$ 对角元为模长）。
  • 方法：实际上就是先对 $A$ 作 Gram-Schmidt 正交化，得到 $Q$，然后保留变化中的系数，得到 $R$。
  • 计算细节： 设 $A = (\alpha_1, \alpha_2, \dots, \alpha_n)$。记 $(q_1, \dots, q_n) = Q$。 应有：
    1. $\beta_1 = \alpha_1 \rightarrow q_1 = \frac{\alpha_1}{|\alpha_1|}$
    2. $\beta_2 = \alpha_2 - \frac{q_1 \cdot \alpha_2}{q_1 \cdot q_1} q_1 \rightarrow q_2 = \frac{\beta_2}{|\beta_2|}$
    3. $\beta_3 = \alpha_3 - \frac{q_1 \cdot \alpha_3}{q_1 \cdot q_1} q_1 - \frac{q_2 \cdot \alpha_3}{q_2 \cdot q_2} q_2 \dots$
    • $R$ 矩阵元素 $R_{ij} = q_i^T \alpha_j$ (当 $i \le j$)。

1.5 谱分解 (开始涉及特征值了！)

  • 条件：如果所有特征值的代数重数与几何重数相同，则可进行谱分解。
  • 形式：$A = P D P^{-1}$。($P$ 正交，$D$ 对角 —— 针对实对称矩阵)。
  • 计算：
    1. 算 $A$ 的所有特征值 $\lambda_1, \dots, \lambda_n$，构成 $D$。
    2. 然后对于某 $\lambda_i$，算 $(\lambda I - A)x=0$ 的特征向量，然后作 Schmidt 正交化。
    3. (# 不同 $\lambda$ 的特征子空间天然正交)。拼成 $P$，即可！

1.6 Jordan 标准形与 Jordan 分解

  • 条件：如果某特征值代数重数大于几何重数，用 Jordan 分解。
  • 1.6.1 标准形：$J_m(\lambda) = \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}_{m \times m}$。
  • 1.6.2 定义：任意 $A = P J P^{-1}$。其中 $J = \text{diag}(J_{m_1}(\lambda_1), \dots, J_{m_k}(\lambda_k))$。
  • 1.6.3 广义特征空间：
    • 一般认为特征空间为 $(A-\lambda I)x=0$ 的解空间。
    • 记 $V_k$ 为 $\dim \ker(A-\lambda I)^k$ (笔记写 $\text{dim}(A-\lambda I)^k$，指核空间维数)。$N((A-\lambda I)^k)$ 叫广义特征子空间。
  • 1.6.4 如何计算？
    • 1.6.4.1 计算 $A$ 的特征值。
    • 1.6.4.2 对于每个特征值 $\lambda$，设其代数重数为 $a$，几何重数为 $g$。
      • 若 $a=g$，则 $\lambda$ 对应是一阶 Jordan 块（即对角元）。
      • 若 $a>g$，考查 $V_k$。$\lambda$ 对应阶数为 $k$ 的 Jordan 块个数 $N_k$。
      • 公式：$N_k = \text{rank}(A-\lambda I)^{k-1} - 2\text{rank}(A-\lambda I)^k + \text{rank}(A-\lambda I)^{k+1}$ (笔记中写的是维数形式 $2v_k - v_{k-1} - v_{k+1}$，本质一样)。
      • 依照这个 $N_k$，给出 $\lambda$ 对应的 Jordan 块组，进而给出 $J$。
    • 1.6.4.3 如何算 P？
      • 对于某个 $\lambda$ 对应阶数为 $k$ 的 Jordan 块，依次算：
      • $(\lambda I - A)p_1 = 0$, $(\lambda I - A)p_2 = p_1$, $\dots$, $(\lambda I - A)p_k = p_{k-1}$。
      • (一定会有 $p_1$ 能拉出这么长串)。
      • $(p_1, p_2, \dots, p_k) \rightarrow$ 对应 Jordan 块 $\begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}$。
      • 这样把 $p_i$ 们对照着 $J$ 的排法拼起来，即得到了 $P$。注意：不用正交化。

1.7 奇异值分解 (SVD)

  • 1.7.1 定义：对 $A \in \mathbb{R}^{m \times n}$，存在正交阵 $U \in \mathbb{R}^{m \times m}$, $V \in \mathbb{R}^{n \times n}$，以及 $\Sigma \in \mathbb{R}^{m \times n}$ (广义对角阵)。
    • 满足 $A = U \Sigma V^T$。
    • 其中 $\Sigma$ 形如 $\begin{pmatrix} \sigma_1 & & & 0 \\ & \ddots & & \\ & & \sigma_r & \\ 0 & & & 0 \end{pmatrix}$。称 $\sigma_1 \dots \sigma_r$ 为 $A$ 的奇异值。
    • $U$ 的列向量是左奇异向量，$V$ 的列向量称右奇异向量。
  • 1.7.2 计算：
    1. 计算奇异值：计算 $A^T A$ 的所有特征值 $\lambda_1 \ge \lambda_2 \dots \ge \lambda_r > 0 = \lambda_{r+1} = \dots = \lambda_n$。$\sigma_i = \sqrt{\lambda_i}$。
    2. 计算右奇异向量 V：求解 $(A^T A - \lambda I)x=0$ 的基础解系，也即求 $A^T A$ 的特征向量。单位正交化 (Gram-Schmidt) 后拼成 $V$。
    3. 计算左奇异向量 U：
      • 对于前 $r$ 个非零 $\sigma_i$，有 $u_i = \frac{A v_i}{\sigma_i}$。这 $r$ 个向量必然标准正交。
      • 对于 $m > r$ 时，后面的向量补上一些正交单位向量即可。
  • 1.7.3 常用：
    1. 伪逆：$A^+ = V \Sigma^{-1} U^T$。$\Sigma^{-1}$ 是对所有非零 $\sigma_i$ 取倒数。
      • 是满足 $A A^+ A = A$, $A^+ A A^+ = A^+$, $(A A^+)^T = A A^+$, $(A^+ A)^T = A^+ A$ 的伪逆。
      • 题对 $Ax=b$ 作最小二乘解，有 $x = A^+ b$ 是最小范数二乘解。
    2. Eckart-Young 定理：设 $A = U \Sigma V^T$。$U_r$ 表示前 $r$ 列，$\Sigma_r$ 表示 $(\sigma_1 \dots \sigma_r)$，$V_r$ 表示前 $r$ 行（注：应为 $V_r^T$ 前 $r$ 行）。矩阵的秩不超过 $r$ 时，对 $A$ 的最小范数逼近是 $U_r \Sigma_r V_r^T$。
    3. 极分解：$A = U_0 T_0$。$U$ 为酉矩阵（方阵），$T$ 半正定。
      • $U_0 = U V^T$, $T_0 = V \Sigma V^T$。

1.8 Schur (舒尔) 分解

  • 定义：$A$ 是复方阵，则必然存在酉矩阵 $U$，上三角阵 $T$，s.t. $U^* A U = T \Leftrightarrow A = U T U^*$。
  • 且 $T$ 的对角线上全是 $A$ 的特征值。（不太常见于计算）。
  • 计算思路：取 $A$ 特征值 $\lambda_1 \dots \lambda_n$。设 $\lambda_1$ 对应单位特征向量 $\xi_1$。
    • 把 $\xi_1$ 扩充成一组基 $\xi_1 \dots \xi_n$ 记作 $U_1$。
    • 则 $U_1^* A U_1 = \begin{pmatrix} \lambda_1 & * \\ 0 & A_1 \end{pmatrix}$。这样就能作递归计算了。

2. 基本计算

2.1 矩阵函数

  • 实数函数也可以对矩阵作。核心是泰勒展开（因为矩阵只有幂运算）。
  • 一般计算 $f(A)$，会先把 $A$ 化作 $A = P J P^{-1}$ (Jordan 标准形)。
  • 有 $f(A) = P f(J) P^{-1}$。
  • $f(J)$ 的计算定式： 设 $J = J_k(\lambda) = \begin{pmatrix} \lambda & 1 & & 0 \\ & \ddots & \ddots & \\ 0 & & & \lambda \end{pmatrix}$。 则 $f(J) = \begin{pmatrix} f(\lambda) & f’(\lambda) & \frac{1}{2!}f’’(\lambda) & \dots & \frac{f^{(k-1)}(\lambda)}{(k-1)!} \\ 0 & f(\lambda) & f’(\lambda) & \dots & \vdots \\ \vdots & & \ddots & \ddots & \frac{1}{2!}f’’(\lambda) \\ 0 & \dots & 0 & f(\lambda) & f’(\lambda) \\ 0 & \dots & 0 & 0 & f(\lambda) \end{pmatrix}$。 (Taylor 展开可证)。

2.2 一阶常系数线性齐次常微分方程组

  • 一般看上去如：$\frac{dX(t)}{dt} = A \cdot X(t)$。
    • $X(t) = ()n$ (列向量), $A = (){n \times n}$, $X(0) = X_0$。
  • 把 $A, \lambda$ 视作“数”，有解：$X(t) = e^{At} X_0$。
  • $e^{At}$ 又涉及到了矩阵函数运算了。

2.3 最小二乘类计算

  • 常常可化为求 $A \cdot x = b$ 最近似解。
  • 熟知 $\hat{x} = A^+ b$ 是最优解，但计算太烦了。
  • 这时这样算：$A \cdot x \approx b \Leftrightarrow A^T A x = A^T b$ (正规方程)。
  • 这样 $x = (A^T A)^{-1} A^T b$ 也是最小二乘解。

2.4 矩阵函数的谱定义计算法 (多项式插值定理)

  • 定理：设 $A$ 的极小多项式为 $m_A(\lambda) = (\lambda - \lambda_1)^{m_1} \dots (\lambda - \lambda_s)^{m_s}$。($m_i$ 是 $\lambda_i$ 对应 Jordan 的最大阶数)。
  • 若 $f(z)$ 在 $A$ 的谱上有定义，则存在多项式 $r(z)$，$\deg r < \deg m_A$。
  • 满足 (s.t.)：$f^{(j)}(\lambda_i) = r^{(j)}(\lambda_i)$, $i=1 \dots s, j=0 \dots m_i-1$。
  • 用法：把这个 $r$ 解出来，直接算 $r(A)$。
  • 评价：(不用 Jordan 分解，很快)。但本质一样。

2.5 Rayleigh 商与推广

  • 定义：给定实对称阵 $S$，它的 Rayleigh 商定义为：$R(x) = \frac{x^T S x}{x^T x}$。
  • 性质：则有 $\lambda_{\min} \le R(x) \le \lambda_{\max}$。
    • 利用谱分解 $S = Q \Lambda Q^T$, $x = Qy$。有 $R(y) = \frac{y^T \Lambda y}{y^T y}$。
  • 广义 Rayleigh 商：定义为 $R_M(x) = \frac{x^T S x}{x^T M x}$。
    • 其最大值为 $M^{-1} S$ 的最大特征值 (若 $M$ 正定)。