佚名

数值线性代数

什么是线性

  • 根据Gauss消元法，我们认为如下运算是线性的
    • （域）系数可以进行加法、减法、乘法、除法，这对应于域
    • （Abel群）不同的行可以进行加法，这对应于Abel群
  • 除此之外，域上的运算、Abel群上的运算应该是相容的
    • （域的加法，关于Abel群）

          \[ (\lambda_1 + \lambda_2)v = \lambda_1v + \lambda_2v. \]

    • （域的乘法，关于Abel群）

          \[ (\lambda_1\lambda_2)v = \lambda_1(\lambda_2v). \]

    • （Abel群的加法，关于域）

          \[ \lambda(v_1 + v_2) = \lambda v_1 + \lambda v_2. \]

    • 在域中，减法为加法的逆运算，除法为乘法的逆运算。因此，我们只考虑了加法、乘法，并且域也可以减弱为环（有单位元素1的交换环），满足

          \[ 1v = v. \]

    • 加法的相容性，也叫做分配律。在左右两边，加法满足分配律，这对应于\otimes
  • Abel范畴、模范畴
    • 域（Field）、Abel群经过\otimes，可以得到向量空间（Vector Space）

          \[ V = F \otimes A. \]

    • 环（Ring）、Abel群经过\otimes，可以得到模（Module）

          \[ M = R \otimes A. \]

    • Abel群、环、域、模、向量空间，它们都是Abel群，所以它们都可以在Abel范畴中讨论。在Abel范畴中，我们可以定义核ker、像im，可参见Abel范畴和导出函子
      • Abel群 –> 加法
      • 环 –> 加法、乘法
      • 域 –> 加法、减法、乘法、除法
      • 模 –> 系数为环，加法
      • 向量空间 –> 系数为域，加法
    • Abel群也是\mathbb{Z}-模，所以它们也可以在模范畴中讨论。在模范畴中，我们可以定义Hom、\otimes，可参见模范畴和同态函子、张量积函子
    • 矩阵的集合既是环（乘法为矩阵的乘法），也是F-向量空间，我们称这样的空间为F-代数。因此，矩阵代数为有单位元素的、结合的、非交换的F-代数。
      • 注意，环的乘法是结合的，而代数的乘法不一定是结合的，比如Lie代数（乘法为Poisson括号）不是结合的，我们有Jacobi恒等式

从线性空间到张量

  • 向量空间中的元素称为向量，向量空间也叫作线性空间
    • 在求解线性方程时，如果某些行乘以常数倍相加等于另一行，那么有一部分方程不是独立的
    • 类似地，如果存在不全为0的\lambda_i，使得

          \[ \sum_{i = 1}^n \lambda_iv_i = 0, \]

      那么v_1, \ldots, v_n称为线性相关的，此时某些向量乘以常数倍相加等于另一个向量
    • 因此，所有独立的方程，对应于数量最多的线性无关的向量组，它称为极大线性无关组，其数量称为秩。在线性空间中，数量最多的线性无关的向量组也叫做基底，其数量也叫做维数
  • 设V为n维F-线性空间，e_1, \ldots, e_n为F-基底
    • （基底是线性无关的）我们有

          \[ \sum_{i = 1}^n \lambda_ie_i = 0 \Rightarrow \lambda_i = 0. \]

    • （基底可以生成线性空间）对任意v \in V，我们有

          \[ \sum_{i = 1}^n \lambda_ie_i = v,\; \lambda_i \in F. \]

    • 在固定一组F-基底后，V可以等同于F^n。我们也将维数记为

          \[ n = dim_FV. \]

    • 线性映射f为保持加法、系数的映射，

          \[ f(v_1 + v_2) = f(v_1) + f(v_2),\; f(\lambda v) = \lambda f(v). \]

      在固定一组F-基底后，对任意v = \sum_{i = 1}^n \lambda_ie_i，我们有

          \[ f(v) = \sum_{i = 1}^n \lambda_if(e_i). \]

      因此，f只需指定在基底上的值，即可线性扩张为V上的线性映射
  • 所有线性映射V \to F构成一个线性空间，称为对偶线性空间

        \[ V^* = Hom(V, F). \]

    V^*的对偶基底e^1, \ldots, e^n满足e^i(e_j) = \delta_j^i，它们可以线性扩张为V上的线性映射，

        \[ e^i(v) = \sum_{j = 1}^n \lambda_je^i(e_j) = \lambda_i. \]

    • （e^i是线性无关的）如果\sum_{i = 1}^n \lambda_ie^i = 0，那么将其作用于e_j，可得\lambda_j = 0
    • （e^i可以生成V^*）对任意f \in V^*，我们有

          \[ f = \sum_{i = 1}^n f(e_i) \cdot e^i. \]

    • 线性映射V \to F即线性函数，通常记为配对\langle{f, v}\rangle = f(v)，故

          \[ f = \sum_{i = 1}^n \langle{f, e_i}\rangle \cdot e^i,\; f \in V^*. \]

  • 双线性形式\beta对两个分量都是线性的，即对于任意固定的v、w，\beta(v, \cdot)、\beta(\cdot, w)都为线性映射V \to F。在左右两边，双线性形式的加法满足分配律，这对应于\otimes。因此，类似于线性映射的情形，我们有

        \[ e^i(v)e^j(w) = (e^i \otimes e^j)(v, w),\; \beta = \sum_{i, j = 1}^n \beta(e_i, e_j)e^i \otimes e^j. \]

    所有双线性形式V \times V \to F构成一个线性空间

        \[ V^* \otimes V^*. \]

  • 现在，利用Hom、\otimes，我们可以构造一般的张量空间

        \[ V \otimes \cdots \otimes V \otimes V^* \otimes \cdots \otimes V^*. \]

    如果V的数量为r、V^*的数量为s，那么其中的元素称为(r, s)-型张量。张量的集合既是环（乘法为\otimes），也是F-向量空间，故我们可以得到张量代数
    • 在数值计算中，我们通常固定一组F-基底。此时，(r, s)-型张量可以等同于F^{n^{r + s}}中的元素，即F上的r + s维数组
    • (2, 0)-型、(1, 1)-型、(0, 2)-型张量可以等同于F^{n^2}中的元素，即F上的矩阵，这是在数值计算中最常见的情形

矩阵的更多性质

  • 我们考虑最常见的情形，即矩阵。同时，我们考虑复数域，故我们可以使用Cauchy积分定理、Cauchy积分公式、代数基本定理。关于复数域，可参见复数域上的分析
  • (0, 2)-型张量即双线性形式\mathbb{C}^n \times \mathbb{C}^n \to \mathbb{C}，

        \[ \beta(x, y) = x^TBy = \sum_{i, j = 1}^n b_{ij}x_iy_j. \]

    它对应于一个二次型

        \[ \beta(x, x) = x^TBx = \sum_{i, j = 1}^n b_{ij}x_ix_j. \]

    • 我们可以使用配方法，将二次型转化为平方和（平方项可以带系数）。这等价于存在一个可逆矩阵C、一个对角矩阵\Lambda，使得

          \[ y = Cx,\; x^TBx = y^T\Lambda y. \]

      即

          \[ (C^{-1})^TBC^{-1} = \Lambda. \]

      因此，关于矩阵B的变换为C^TBC（将C^{-1}重命名为C），它称为合同变换
  • (1, 1)-型张量即线性变换\mathbb{C}^n \to \mathbb{C}^n，

        \[ f = \sum_{i, j = 1}^n a_{ij}e_j \otimes e^i,\; f(e_i) = \sum_{j = 1}^n a_{ij}e_j. \]

    线性变换f的矩阵为A = (a_{ij})，我们有

        \[ \begin{bmatrix}f(e_1) \\ \vdots \\ f(e_n)\end{bmatrix} = \begin{bmatrix}a_{11} & \ldots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \ldots & a_{nn} \end{bmatrix} \cdot \begin{bmatrix}e_1 \\ \vdots \\ e_n\end{bmatrix}. \]

    如果我们更换一组基底，那么

        \[ \begin{bmatrix}c_{11} & \ldots & c_{1n} \\ \vdots & & \vdots \\ c_{n1} & \ldots & c_{nn}\end{bmatrix} \cdot \begin{bmatrix}f(e_1') \\ \vdots \\ f(e_n')\end{bmatrix} = \begin{bmatrix}a_{11} & \ldots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \ldots & a_{nn}\end{bmatrix} \cdot \begin{bmatrix}c_{11} & \ldots & c_{1n} \\ \vdots & & \vdots \\ c_{n1} & \ldots & c_{nn}\end{bmatrix} \cdot \begin{bmatrix}e_1' \\ \vdots \\ e_n'\end{bmatrix}. \]

    因此，关于矩阵A的变换为C^{-1}AC，它称为相似变换
    • （核、像）线性变换对应于矩阵，反过来，矩阵也对应于线性变换（即线性算子）。矩阵A的核kerA、像imA为\mathbb{C}^n的子空间。如果取kerA的一组基底e_1, \ldots, e_r，然后扩充为\mathbb{C}^n的一组基底e_1, \ldots, e_n，那么imA的一组基底为Ae_{r + 1}, \ldots, Ae_n，从而

          \[ dimkerA + dimimA = n. \]

      商空间\mathbb{C}^n / kerA的一组基底为[e_{r + 1}], \ldots, [e_n]，故我们有同构定理

          \[ \mathbb{C}^n / kerA \cong imA. \]

    • （矩阵乘积的核）对于矩阵乘积的核V = ker(AB)，取线性映射B|_V: V \to \mathbb{C}^n，我们有

          \[ dimkerB|_V + dimimB|_V = dimV. \]

      注意到imB|_V \subset kerA，故dimker(AB) \leq dimkerB + dimkerA。利用数学归纳法，

          \[ dimker\prod_i A_i \leq \sum_i dimkerA_i. \]

    • （直和）对于子空间V_1, \ldots, V_r，如果V_i \cap \sum_{j \neq i} V_j = \{ 0 \}，那么子空间之间的向量是线性无关的，它们可以构成直和\bigoplus_i V_i。由于V_i的基底可以合成为\bigoplus_i V_i的基底，故

          \[ dim\bigoplus_i V_i = \sum_i dimV_i. \]

  • 类似于合同变换，我们考虑相似变换的对角化问题

        \[ C^{-1}AC = \Lambda. \]

    因为矩阵的乘法为左边的行、乘以右边的列，所以我们可以对矩阵进行分块，然后进行乘法。比如，对于列向量的分块C = \begin{bmatrix}v_1 \cdots v_n\end{bmatrix}，我们有

        \[ A \cdot \begin{bmatrix}v_1 \cdots v_n\end{bmatrix} = \begin{bmatrix}v_1 \cdots v_n\end{bmatrix} \cdot \begin{bmatrix}\lambda_1 & & \\ & \ddots \\ & & \lambda_n\end{bmatrix} = \begin{bmatrix}\lambda_1v_1 \cdots \lambda_nv_n\end{bmatrix}. \]

    因此，\lambda_i、v_i满足如下方程

        \[ Av = \lambda v, \]

    其中，\lambda称为特征值，v称为特征向量
  • 每个特征值满足特征多项式P(\lambda)的方程，

        \[ P(\lambda) = \det(\lambda I - A) = 0. \]

    由代数基本定理，我们可以找到P(\lambda)的所有零点（对于一般的域不成立），

        \[ P(\lambda) = (\lambda - \lambda_1) \cdots (\lambda - \lambda_n). \]

    如果所有零点互不相同，那么我们取n个特征向量v_i \in ker(A - \lambda_iI)，即可解决对角化问题。因此，难点在于零点重复的情形，

        \[ P(\lambda) = \prod_i (\lambda - \lambda_i)^{n_i}. \]

    如果我们取v_i \in ker(A - \lambda_iI)^{n_i}，那么我们需要证明，这样可以得到n个线性无关的向量，即

        \[ \mathbb{C}^n = \bigoplus_i ker(A - \lambda_iI)^{n_i}. \]

    • （Bézout定理）尽管矩阵的集合是非交换环，然而矩阵A生成的多项式的集合是交换环，它类似于一元多项式环。对于

          \[ v \in ker(A - \lambda_iI)^{n_i} \cap \sum_{j \neq i} ker(A - \lambda_jI)^{n_j}, \]

      由Bézout定理，存在矩阵A的多项式U(A)、V(A)，满足

          \[ U(A)(A - \lambda_iI)^{n_i} + V(A)\prod_{j \neq i} (A - \lambda_jI)^{n_j} = I, \]

      故

          \[ 0 = U(A)(A - \lambda_iI)^{n_i}v + V(A)\prod_{j \neq i} (A - \lambda_jI)^{n_j}v = Iv = v. \]

      从而，ker(A - \lambda_iI)^{n_i}可以构成直和，并且

          \[ \sum_i dimker(A - \lambda_iI)^{n_i} \leq n. \]

    • （Cayley-Hamilton定理）另一方面，由矩阵乘积的核的不等式，

          \[ \sum_i dimker(A - \lambda_iI)^{n_i} \geq dimker\prod_i (A - \lambda_iI)^{n_i}. \]

      由下面的Cayley-Hamilton定理，

          \[ dimker\prod_i (A - \lambda_iI)^{n_i} = dimkerP(A) = dimker0 = n. \]

      因此，直和分解成立
    • （Jordan标准型）对任意v \in ker(A - \lambda_iI)^{n_i}，如果r为满足(A - \lambda_iI)^rv = 0的最小值，那么如下向量组为线性无关的，

          \[ v,\; (A - \lambda_iI)v,\; \ldots,\; (A - \lambda_iI)^{r - 1}v, \]

      原因是若

          \[ \mu_0v + \mu_1(A - \lambda_iI)v + \cdots + \mu_{r - 1}(A - \lambda_iI)^{r - 1}v = 0, \]

      则(A - \lambda_iI)^{r - 1}, \ldots, (A - \lambda_iI)作用于上式，可得\mu_0, \ldots, \mu_{r - 1}为0。如果取上述形式的向量组作为基底，那么矩阵A可以对角化为如下形式的矩阵块，

          \[ \begin{bmatrix}\lambda_i\end{bmatrix},\; \begin{bmatrix}\lambda_i & 1 \\ 0 & \lambda_i\end{bmatrix},\; \begin{bmatrix}\lambda_i & 1 & 0 \\ 0 & \lambda_i & 1 \\ 0 & 0 & \lambda_i\end{bmatrix},\; \ldots \]

      这称为Jordan标准型，故对于零点重复的情形，矩阵A不一定能完全对角化
  • Cayley-Hamilton定理是指

        \[ P(A) = 0. \]

    受到知乎的启发，我们可以用复分析的方法来证明（对于一般的域，我们可以用代数方法来证明）
    • 由于P(z)为多项式，故它为\mathbb{C}上的全纯函数。由Cauchy积分公式，

          \[ P(w) = \frac{1}{2\pi i}\int_{\partial\Omega} \frac{P(z)}{z - w}dz. \]

      将w转换为矩阵A，

          \[ P(A) = \frac{1}{2\pi i}\int_{\partial\Omega} P(z)(zI - A)^{-1}dz. \]

    • 注意，

          \[ P(z)(zI - A)^{-1} = \det(zI - A)(zI - A)^{-1} = adj(zI - A), \]

      并且伴随矩阵的系数全部为行列式（即多项式），故它们为\mathbb{C}上的全纯函数。由Cauchy积分定理，

          \[ P(A) = \frac{1}{2\pi i}\int_{\partial\Omega} adj(zI - A)dz = 0. \]

      P(w)为有奇点的情形，但是利用伴随矩阵、行列式的性质，P(A)为没有奇点的情形，所以Cayley-Hamilton定理成立

从QR分解到奇异值分解

  • 为了从直和分解进入正交分解，我们需要将基底转换为单位正交基
    • \mathbb{C}^n上的内积、范数分别为

          \[ \langle{x, y}\rangle_{\mathbb{C}^n} = x^T\overline{y},\; ||x|| = \sqrt{\langle{x, x}\rangle_{\mathbb{C}^n}}. \]

      如果一个向量的范数为1，那么它称为单位向量。如果两个向量的内积为0，那么它们称为正交的。因此，单位正交基等价于

          \[ \langle{e_i, e_j}\rangle_{\mathbb{C}^n} = \delta_{ij},\; 1 \leq i, j \leq n. \]

      注意，正交强于线性无关
    • 伴随算子A^*为转置共轭，

          \[ \langle{Ax, y}\rangle_{\mathbb{C}^n} = (Ax)^T\overline{y} = x^T\overline{\overline{A^T}y} = \langle{x, A^*y}\rangle_{\mathbb{C}^n}. \]

      Hermite矩阵满足A^* = A，酉矩阵满足AA^* = I（在实数域上，如果内积中的\overline{y}更换为y、Hermite矩阵更换为实对称矩阵A^T = A、酉矩阵更换为正交矩阵AA^T = I，那么我们可以得到下面的所有结果）
  • （Gram-Schmidt正交化）设一组基底为a_1, \ldots, a_n。我们将a_1单位化得到q_1，将a_2减去q_1常数倍并单位化得到q_2，重复这一过程，直到得到单位正交基q_1, \ldots, q_n
    • function GramSchmidt(a_1, \ldots, a_n)
      • for i = 1, \ldots, n
        • for j = 1, \ldots, i - 1
          • r_{ji} \leftarrow \langle{a_i, q_j}\rangle_{\mathbb{C}^n}
        • q_i \leftarrow a_i - \sum_{j = 1}^{i - 1} r_{ji}q_j
        • r_{ii} \leftarrow ||q_i||
        • q_i \leftarrow q_i / r_{ii}
      • return (q_1, \ldots, q_n)
  • （QR分解）如果将a_i作为可逆矩阵A、将q_i作为酉矩阵Q、将r_{ji}作为上三角矩阵R，那么我们可以得到QR分解

        \[ A = QR. \]

    同时，利用Gram-Schmidt正交化，我们可以找到一组单位正交基，或者将单位正交的向量组扩充为一组单位正交基
  • （Hermite矩阵的特征值）如果A为Hermite矩阵，那么直和分解具有更好的性质

        \[ \mathbb{C}^n = \bigoplus_i ker(A - \lambda_iI)^{n_i}. \]

    • 对于特征值\lambda_i、特征向量x_i，利用伴随算子的性质，

          \[ \lambda_i||x_i||^2 = \langle{Ax_i, x_i}\rangle_{\mathbb{C}^n} = \langle{x_i, Ax_i}\rangle_{\mathbb{C}^n} = \overline{\lambda_i}||x_i||^2. \]

      因此，\lambda_i为实数（在实数域上，特征值、特征值的共轭是成对出现的，所以我们可以将它们更换为2个实特征值）
    • 对于x \in ker(A - \lambda_iI)^{n_i}，利用伴随算子的性质，

          \[ 0 = \langle{(A - \lambda_iI)^{n_i}x, (A - \lambda_iI)^{n_i - 2}x}\rangle_{\mathbb{C}^n} = ||(A - \lambda_iI)^{n_i - 1}x||^2. \]

      因此，x \in ker(A - \lambda_iI)^{n_i - 1}。重复这一过程，直到得到

          \[ ker(A - \lambda_iI)^{n_i} = ker(A - \lambda_iI). \]

    • 对于x_i \in ker(A - \lambda_iI)、x_j \in ker(A - \lambda_jI)，利用伴随算子的性质，

          \[ \lambda_i\langle{x_i, x_j}\rangle_{\mathbb{C}^n} = \langle{Ax_i, x_j}\rangle_{\mathbb{C}^n} = \langle{x_i, Ax_j}\rangle_{\mathbb{C}^n} = \lambda_j\langle{x_i, x_j}\rangle_{\mathbb{C}^n}. \]

      因此，ker(A - \lambda_iI)、ker(A - \lambda_jI)正交
    • 最终，我们可以得到正交分解

          \[ \mathbb{C}^n = \bigoplus_i ker(A - \lambda_iI). \]

      进一步，在每个ker(A - \lambda_iI)中取一组单位正交基。如果将单位正交基作为酉矩阵C、将特征值\lambda_i作为对角矩阵\Lambda，那么矩阵A可以完全对角化

          \[ C^*AC = C^{-1}AC = \Lambda. \]

  • （奇异值分解）到现在为止，我们只考虑了n \times n的矩阵A。在数值计算中，我们需要考虑m \times n的矩阵A，此时特征值推广为奇异值
    • 注意，AA^*为m \times m的Hermite矩阵，故存在m \times m的酉矩阵U，使得UAA^*U^*为对角矩阵。令B = UA，类似于半正定矩阵，我们有

          \[ x^TBB^*\overline{x} = ||B^Tx||^2 \geq 0,\; x \in \mathbb{C}^m. \]

      因此，对角矩阵的元素非负，我们取一个对角元素为正的对角矩阵块\Lambda，然后对矩阵B进行分块，

          \[ BB^* = \begin{bmatrix}\Lambda^2 & 0 \\ 0 & 0\end{bmatrix},\; \begin{bmatrix}B_1 \\ B_2\end{bmatrix}\begin{bmatrix}B_1^* & B_2^*\end{bmatrix} = \begin{bmatrix}\Lambda^2 & 0 \\ 0 & 0\end{bmatrix}. \]

    • 对于矩阵B_1、B_2，我们有

          \[ B_1B_1^* = \Lambda^2,\; B_2B_2^* = 0. \]

      由第二式的对角线，可得B_2 = 0。由第一式，可得B_3 = B_1^*\Lambda^{-1}的列向量构成单位正交的向量组，

          \[ B_3^*B_3 = \Lambda^{-1}B_1B_1^*\Lambda^{-1} = I. \]

      将其扩充为一组单位正交基，可得n \times n的酉矩阵V = \begin{bmatrix}B_3 & B_4\end{bmatrix}。最终，我们可以得到奇异值分解，\Lambda的对角元素为矩阵A的奇异值，

          \[ UAV = BV = \begin{bmatrix}B_1 \\ 0\end{bmatrix}\begin{bmatrix}B_3 & B_4\end{bmatrix} = \begin{bmatrix}\Lambda & 0 \\ 0 & 0\end{bmatrix}. \]