佚名

从线性方程出发

矩阵、行列式

  • 求解线性方程
    • 一元一次方程ax =b，其解为

          \[ x = a^{-1}b. \]

    • 二元一次方程组

          \begin{equation*}\begin{cases} a_{11}x_1 + a_{12}x_2 = b_1, \\ a_{21}x_1 + a_{22}x_2 = b_2. \end{cases}\end{equation*}

      根据系数的排列位置，记

          \[ A = \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix},\; B = \begin{bmatrix}b_1 \\ b_2\end{bmatrix}. \]

      二元一次方程组AX = B，其解为

          \[ X = A^{-1}B. \]

  • 我们需要定义什么是乘法AX、什么是逆A^{-1}
    • 因为右边的系数B为竖向排列的，所以我们令解X也为竖向排列的。从而，我们们可以得到乘法

          \[ \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix} \cdot \begin{bmatrix}x_1 \\ x_2\end{bmatrix} = A \cdot X = AX = \begin{bmatrix}a_{11}x_1 + a_{12}x_2 \\ a_{21}x_1 + a_{22}x_2\end{bmatrix}. \]

      也就是说，乘法是左边的行，乘以右边的列。注意，乘法为结合的，但是为非交换的
    • 我们也可以直接求解方程组
      • （消元过程）将第一式乘以-a_{21} / a_{11}加到第二式，可以消去x_1，

            \[ \bigg(a_{22} - a_{12}\frac{a_{21}}{a_{11}}\bigg)x_2 = b_2 - b_1\frac{a_{21}}{a_{11}}. \]

      • （代回过程）我们可以解得x_2，

            \[ x_2 = \frac{a_{11}b_2 - a_{21}b_1}{a_{11}a_{22} - a_{12}a_{21}}. \]

        将x_2代回到第一式，我们可以解得x_1（由于下标1、2是对称的，故相当于1、2对换），

            \[ x_1 = \frac{a_{22}b_1 - a_{12}b_2}{a_{11}a_{22} - a_{12}a_{21}}. \]

    • 从而，我们可以得到逆

          \begin{equation*}\begin{split} X &= \frac{1}{a_{11}a_{22} - a_{12}a_{21}}\begin{bmatrix}a_{22}b_1 - a_{12}b_2 \\ a_{11}b_2 - a_{21}b_1\end{bmatrix} \\ &= \frac{1}{a_{11}a_{22} - a_{12}a_{21}}\begin{bmatrix}a_{22} & -a_{12} \\ -a_{21} & a_{11}\end{bmatrix} \cdot \begin{bmatrix}b_1 \\ b_2\end{bmatrix} \\ &= A^{-1} \cdot B. \end{split}\end{equation*}

  • A、X、B称为矩阵。因此，矩阵的乘法、逆可以用于求解方程组
    • 当a_{11}a_{22} - a_{12}a_{21} \neq 0时，A^{-1}存在，A可逆，方程组有唯一解
    • 当a_{11}a_{22} - a_{12}a_{21} = 0时，A^{-1}不存在，A不可逆。不过，此时A的两行系数只相差常数倍，如果B的两行系数相差同样的倍数，那么方程组有多于一个解，否则方程组无解
    • 在第一种情形中，独立的方程为2个（非退化）；在第二种情形中，独立的方程为1个或0个（退化）。因此，可逆即非退化，不可逆即退化
  • 因为a_{11}a_{22} - a_{12}a_{21}决定了A是否可逆，以及方程组解的个数，所以它称为决定式（Determinant），也叫做行列式，记为\det(A)。同时，

        \[ A^{-1} = \frac{1}{\det(A)}adj(A),\; adj(A) = \begin{bmatrix}a_{22} & -a_{12} \\ -a_{21} & a_{11}\end{bmatrix}. \]

    注意，adj(A)对应于伴随（Adjugate）矩阵，A^*对应于伴随（Adjoint）算子，这里存在词语冲突，Adjugate、Adjoint是不同的
    • Adjugate更接近于Conjugate（共轭），比如在四元数中，四元数的共轭对应于伴随矩阵
    • Adjoint更常见，比如范畴论中的伴随函子
  • 由于矩阵的逆满足

        \[ A \cdot A^{-1} = A^{-1} \cdot A = I,\; I = \begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}, \]

    其中I为单位矩阵，故伴随矩阵满足

        \[ A \cdot adj(A) = adj(A) \cdot A = \det(A)I. \]

Cramer法则、Gauss消元法

  • 现在，我们将二元一次方程组推广到n元一次方程组，即一般的线性方程。为了方便起见，我们考虑A为可逆矩阵
    • Cramer法则
      • 求解线性方程，等价于求矩阵的逆
      • 求矩阵的逆，等价于求行列式、伴随矩阵
      • 在一般情形下，伴随矩阵的系数全部为行列式。因此，线性方程的求解可以完全化归为行列式的计算，比如

            \[ x_1 = \frac{\det\begin{bmatrix}b_1 & a_{12} \\ b_2 & a_{22}\end{bmatrix}}{\det\begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix}},\; x_2 = \frac{\det\begin{bmatrix}a_{11} & b_1 \\ a_{21} & b_2\end{bmatrix}}{\det\begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix}}. \]

    • Gauss消元法
      • （消元过程）交换两行，使得第一行第一列不为零。将第一行乘以常数倍加到其他行，可以消去第一列的元。从第二行开始继续消元，直到倒数第一行只剩一个元
      • （代回过程）解得倒数第一行的元，将其代回到其他行。从倒数第二行开始继续求解，直到解得全部元
  • 由Cramer法则、Gauss消元法，可得一般情形下的行列式、伴随矩阵
    • （Cramer法则）对于三元一次方程组，如果令第二、三行的x_1系数为0，那么x_2、x_3的方程组化归为二元一次方程组，比如

          \[ x_2 = \frac{\det\begin{bmatrix}a_{11} & b_1 & a_{13} \\ 0 & b_2 & a_{23} \\ 0 & b_3 & a_{33}\end{bmatrix}}{\det\begin{bmatrix}a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & a_{32} & a_{33}\end{bmatrix}} \Rightarrow x_2 = \frac{\det\begin{bmatrix}b_2 & a_{23} \\ b_3 & a_{33}\end{bmatrix}}{\det\begin{bmatrix}a_{22} & a_{23} \\ a_{32} & a_{33}\end{bmatrix}}. \]

      为了保持解是相同的，分子、分母应该相差相同的倍数a_{11}，比如

          \[ \det\begin{bmatrix}a_{11} & b_1 & a_{13} \\ 0 & b_2 & a_{23} \\ 0 & b_3 & a_{33}\end{bmatrix} = a_{11}\det\begin{bmatrix}b_2 & a_{23} \\ b_3 & a_{33}\end{bmatrix}. \]

      因此，高阶行列式可以展开为低阶行列式
    • （Gauss消元法）考虑如下三种运算，它们对应于三种初等矩阵。注意，它们对应于行列式的反对称性、线性
      • （反对称性）交换两行，比如

            \[ C = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix},\; A = \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix},\; CA = \begin{bmatrix}a_{21} & a_{22} \\ a_{11} & a_{12}\end{bmatrix}. \]

      • （线性，系数）某一行乘以常数倍，比如

            \[ C = \begin{bmatrix}c & 0 \\ 0 & 1\end{bmatrix},\; A = \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix},\; CA = \begin{bmatrix}ca_{11} & ca_{12} \\ a_{21} & a_{22}\end{bmatrix}. \]

      • （线性，加法）某一行加到另一行，比如

            \[ C = \begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix},\; A = \begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{bmatrix},\; CA = \begin{bmatrix}a_{11} + a_{21} & a_{12} + a_{22} \\ a_{21} & a_{22}\end{bmatrix}. \]

      • 对于初等矩阵C，我们有

            \[ \det(CA) = \det(C)\det(A). \]

        对于一般的矩阵C，这个等式也成立
        • 当C可逆时，由于三种运算求解线性方程，等价于三种初等矩阵生成C，故等式成立
        • 当C不可逆时，CA也不可逆，相应的行列式为0，故等式成立
    • 高阶行列式可以展开为低阶行列式，并且行列式具有反对称性，故n阶行列式为

          \[ \det(A) = (-1)^0a_{11}M_{11} + \cdots + (-1)^{n - 1}a_{1n}M_{1n}. \]

      • a_{1j}为第j列对换到第1列（j \to j - 1 \to \cdots \to 1）后展开的系数，所以需要乘以(-1)^{j - 1}。M_{1j}为A去掉第1行、第j列后的行列式
      • 一般地，\det(A)I可以表示为A \cdot adj(A)，也可以表示为

            \[ \begin{bmatrix}a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \cdots & a_{nn}\end{bmatrix} \cdot \begin{bmatrix}(-1)^{1 + 1}M_{11} & \cdots & (-1)^{1 + n}M_{n1} \\ \vdots & & \vdots \\ (-1)^{n + 1}M_{1n} & \cdots & (-1)^{n + n}M_{nn}\end{bmatrix}. \]

        因此，伴随矩阵为右边的矩阵，它的系数全部为行列式
    • 高阶行列式每展开一次就下降一阶，并且行、列下标i、j被去掉。如果将其完全展开为a_{ij}，那么行、列下标不能重复
      • 当行下标固定为1~n时，列下标为1~n的置换，再加上反对称性，故n阶行列式为

            \[ \det(A) = \sum_{\sigma \in S_n} sign(\sigma) \cdot a_{1\sigma(1)} \cdots a_{n\sigma(n)}, \]

        其中，S_n为n元置换群。当置换\sigma为偶数个对换时，sign(\sigma) = 1；当置换\sigma为奇数个对换时，sign(\sigma) = -1
      • 我们既可以固定行下标，也可以固定列下标，所以行列式关于行、列是对称的。取A^T的第i行等于A的第i列，它称为A的转置，满足

            \[ \det(A^T) = \det(A). \]

  • 上面，我们可以由行列式的性质，得到行列式的表达式。反过来，我们也可以由行列式的表达式，以及de Rham上同调群的定义中的外代数，直接导出行列式的所有性质

线性方程的求解，数值计算

  • 尽管线性方程的求解可以完全化归为行列式的计算，并且行列式可以完全展开为a_{ij}，然而S_n的阶为n!，计算复杂度太高。因此，线性方程的求解通常基于Gauss消元法
    • // 消元过程（Gaussian Elimination，GE）
    • function GE(A, b)
      • n \leftarrow dim(b)
      • for row = 1, \ldots, n
        • for row' = row + 1, \ldots, n
          • factor \leftarrow a_{row', row} / a_{row, row}
          • for col = row, \ldots, n
            • a_{row', col} \leftarrow a_{row', col} - factor \times a_{row, col}
          • b_{row'} \leftarrow b_{row'} - factor \times b_{row}
      • return (A, b)
    • // 代回过程（Backward Substitution，BS）
    • function BS(U, b)
      • n \leftarrow dim(b)
      • for row = n, \ldots, 1
        • solution \leftarrow b_{row}
        • for row' = row + 1, \ldots, n
          • solution \leftarrow solution - u_{row, row'} \times b_{row'}
        • b_{row} \leftarrow solution / u_{row, row}
      • return b
  • 在数值计算中，我们通常使用浮点数。因此，Gauss消元法的矩阵为浮点数矩阵
    • 在一般情形下，浮点数等于0是不会成立的。为了方便起见，我们省略了交换两行的运算
    • Gauss消元法的计算复杂度可以用浮点运算次数（Floating-Point Operations，flops）来表示，包括加法、减法、乘法、除法等。比如，消元过程为

          \[ \sum_{i = 1}^n\sum_{j = i + 1}^n [2(n - i + 1) + 3] \sim \sum_{i = 1}^n 2(n - i)^2 \sim \frac 23n^3\, (flops), \]

      代回过程为

          \[ \sum_{i = 1}^n [2(n - i) + 1] \sim \sum_{i = 1}^n 2(n - i) \sim n^2\, (flops). \]

      因此，Gauss消元法的计算复杂度为O(n^3)
    • 消元过程完成后，矩阵A作为上三角矩阵U传入代回过程。如果将消元过程的所有factor作为下三角矩阵L，并且L的对角线为1，那么我们可以得到LU分解

          \[ A = LU. \]