【机器学习的数学基础】（一）线性代数(Linear Algebra)（上+）

【机器学习的数学基础】（一）线性代数(Linear Algebra)（上）

2 线性代数(Linear Algebra)（上+）

2.3 线性方程组的求解

前面我们介绍了方程组的一般形式，即：
$$\begin{array}{rl}{a}_{11}{x}_1+\cdots +a_{1n}{x}_n& =b_1\\ & ⋮\\ a_{m1}{x}_1+\cdots +a_{mn}{x}_n& =b_m\end{array}$$

其中$a_{ij}\in \mathbb{R}$，$b_i\in \mathbb{R}$为已知常数，$x_j$为未知量，$i=1,\dots ,m,j=1,\dots ,n$。到目前为止，我们看到矩阵可以作为一种简洁的方法来表达线性方程组，这样我们可以将线性方程组写成$\mathbf{A}\mathbf{x}=\mathbf{b}$。此外，我们还定义了基本的矩阵运算，如矩阵的加法和乘法。下面，我们将重点讨论线性方程组的求解，并提供一种求矩阵逆的算法。

2.3.1 特解和通解

在讨论如何求解线性方程组之前，让我们先看一个例子。考虑方程组

$$\left[\begin{array}{cccc}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]=\left[\begin{array}{c}42\\ 8\end{array}\right](2.38)$$

这个方程组有两个方程和四个未知数。因此，一般来说，我们可以得到无穷多个解。这个方程组的形式为极简形式，前两列都由一个0和一个1组成。

我们目标是找到标量$x_1,\dots ,x_4$，使得${\sum }_{i=1}^4{x}_i{\mathbf{c}}_i=\mathbf{b}$，其中${\mathbf{c}}_i$为矩阵的第$i$列，$b$为方程组的(2.38)的右侧。对于该方程组，可通过取第一列的42倍和第二列的8倍得到解：

$$\mathbf{b}=\left[\begin{array}{c}42\\ 8\end{array}\right]=42\left[\begin{array}{l}1\\ 0\end{array}\right]+8\left[\begin{array}{l}0\\ 1\end{array}\right]$$

因此，方程组的一个解为$[42,8,0,0{]}^{\top }$，这个解叫做特解(particular solution or special solution)。

然而，这并不是这个线性方程组的唯一解。要得到其他解，我们需要创造性地使用矩阵的列以非平凡( non-trivial)的方式生成向量$0$：特解与方程组的矩阵相乘，然后等式两边同时加上$0$不会影响该等式。

我们使用前两列（它们的形式非常简单）表示第三列
$$\left[\begin{array}{l}8\\ 2\end{array}\right]=8\left[\begin{array}{l}1\\ 0\end{array}\right]+2\left[\begin{array}{l}0\\ 1\end{array}\right]$$

则有$0=8{\mathbf{c}}_1+2{\mathbf{c}}_2-1{\mathbf{c}}_3+0{\mathbf{c}}_4$，得到解：$\left(x_1,x_2,x_3,x_4\right)=(8,2,-1,0)$。事实上，这个解按任意${\lambda }_1\in \mathbb{R}$的缩放都会产生$0$向量，即：
$$\left[\begin{array}{llll}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left({\lambda }_1\left[\begin{array}{c}8\\ 2\\ -1\\ 0\end{array}\right]\right)={\lambda }_1\left(8c_1+2c_2-c_3\right)=0$$

同样地，我们使用前两列表示方程组中矩阵的第四列，对于任意${\lambda }_2\in \mathbb{R}$生成另一组$0$的非平凡版本
$$\left[\begin{array}{llll}1& 0& 8& -4\\ 0& 1& 2& 12\end{array}\right]\left({\lambda }_2\left[\begin{array}{c}-4\\ 12\\ 0\\ -1\end{array}\right]\right)={\lambda }_2\left(-4{\mathbf{c}}_1+12{\mathbf{c}}_2-{\mathbf{c}}_4\right)=0$$

把所有的解放在一起，得到方程组的所有解，称为通解(general solution)，以集合形式表示为：
$$\left\{x\in {\mathbb{R}}^4:x=\left[\begin{array}{c}42\\ 8\\ 0\\ 0\end{array}\right]+{\lambda }_1\left[\begin{array}{c}8\\ 2\\ -1\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}-4\\ 12\\ 0\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}$$

备注：
线性方程组的一般求解包括以下三个步骤：

• (1) 找到$Ax=b$的特解。
• (2) 找到$Ax=0$的所有解。
• (3) 结合步骤(1)和(2)中的解得到通解。
• 注意通解和特解都不是唯一的。

上例中的线性方程组很容易求解，因为方程组中的矩阵有特别简便的形式，这使我们能够通过代值检验得到特解和通解。然而，一般方程组不会是这种简单的形式。

幸运的是，有一种构造性的算法可以将任何线性方程组转换成这种特别简单的形式：高斯消元法( Gaussian elimination)。高斯消元法的关键是对线性方程组进行初等变换，将方程组转换成简单形式。然后，我们可以用以上三个步骤求解线性方程组。

2.3.2 初等变换

求解线性方程组的关键是初等变换(elementary transformations)，它能在解集保持不变的前提下，将方程组变换为更简单的形式：

• （1）两个方程（表示方程组的矩阵的行）的交换
• （2）方程(行)乘一个常数$\lambda \in \mathbb{R}\backslash \{0\}$
• （3）两个等式(行)的相加

备注：（1）、（2）、（3）可以组合。

例 2.6
对于$a\in \mathbb{R}$，求下列方程组的所有解：
$$\begin{array}{rrrrrrrrccc}-2x_1& +& 4x_2& -& 2x_3& -& x_4& +& 4x_5& =& -3\\ 4x_1& -& 8x_2& +& 3x_3& -& 3x_4& +& x_5& =& 2\\ x_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ x_1& -& 2x_2& & & -& 3x_4& +& 4x_5& =& a\end{array}$$

我们首先把这个方程组转换成紧致的矩阵表示$\mathbf{A}\mathbf{x}=\mathbf{b}$。我们不再显式地提及变量$\mathbf{x}$，而是建立增广矩阵(augmented matrix)（形式为$[\mathbf{A}\mid \mathbf{b}]$）

我们用垂直线把方程组的左手边和右手边分开。
$$\left[\begin{array}{rrrrrr}-2& 4& -2& -1& 4& -3\\ 4& -8& 3& -3& 1& 2\\ 1& -2& 1& -1& 1& 0\\ 1& -2& 0& -3& 4& a\end{array}\right]\begin{array}{l}\text{Swap with }{R}_3\\ \\ \text{Swap with }{R}_1\\ \end{array}$$

交换第一行$R_1$和第三行$R_3$得到：

$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 4& -8& 3& -3& 1& 2\\ -2& 4& -2& -1& 4& -3\\ 1& -2& 0& -3& 4& a\end{array}\right]\begin{array}{l}\\ -4R_1\\ +2R_1\\ -R_1\end{array}$$

我们使用上式中指定的变换（例如，上式包括第2行减去四倍第1行）后，我们得到
$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& -1& -2& 3& a\end{array}\right]$$
我们用$⇝$来表示增广矩阵的初等变换。

$$\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& -1& -2& 3& a\end{array}\right]\begin{array}{l}\\ \\ \\ -R_2-R_3\end{array}$$

$$⇝\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& -1& 1& -3& 2\\ 0& 0& 0& -3& 6& -3\\ 0& 0& 0& 0& 0& a+1\end{array}\right]\begin{array}{l}\cdot (-1)\\ \cdot (-\frac{1}{3})\end{array}$$
$$⇝\left[\begin{array}{rrrrrr}1& -2& 1& -1& 1& 0\\ 0& 0& 1& -1& 3& -2\\ 0& 0& 0& 1& -2& 1\\ 0& 0& 0& 0& 0& a+1\end{array}\right]$$

这个（增广）矩阵现在变成一种简便的形式——行阶梯形式（row-echelon form，REF）。将这个紧凑的表示法还原为显式表示法，我们得到
$$\begin{array}{rrrrrrccccc}{x}_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ & & & & x_3& -& x_4& +& 3x_5& =& -2\\ & & & & & & x_4& -& 2x_5& =& 1\\ & & & & & & & & 0& =& a+1\end{array}$$

仅当$a=-1$时方程组才有解。一个特解为：
$$\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]=\left[\begin{array}{c}2\\ 0\\ -1\\ 1\\ 0\end{array}\right]$$

通解：
$$\left\{x\in {\mathbb{R}}^5:x=\left[\begin{array}{c}2\\ 0\\ -1\\ 1\\ 0\end{array}\right]+{\lambda }_1\left[\begin{array}{l}2\\ 1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}2\\ 0\\ -1\\ 2\\ 1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}$$

下面，我们将详细介绍一种获得线性方程组特解和通解的构造性方法。

备注：主元和阶梯结构

行的前导系数（leading coefficient，从左开始的第一个非零数）称为主元(Pivots )，并且始终严格地位于上方行的主元的右侧。因此，任何行阶梯型(row-echelon form)的方程组都具有“阶梯(staircase)”结构。

定义 2.6(行阶梯型)

一个矩阵为行阶梯型(row-echelon form)矩阵需满足：

• 所有只包含零的行都位于矩阵的底部；相应地，所有至少包含一个非零元素的行都位于只包含零的行的顶部。
• 只看非零行，从左边开始的第一个非零数字（也称为主元或前导系数）总是严格地位于它上面的行主元的右边。

备注：基本变量和自由变量

行阶梯型的主元对应的变量称为基本变量(basic variables)，其他变量称为自由变量(free variables)。

例如，对于
$$\begin{array}{rrrrrrccccc}{x}_1& -& 2x_2& +& x_3& -& x_4& +& x_5& =& 0\\ & & & & x_3& -& x_4& +& 3x_5& =& -2\\ & & & & & & x_4& -& 2x_5& =& 1\\ & & & & & & & & 0& =& a+1\end{array}$$
$x_1，x_3，x_4$为基本变量，$x_2，x_5$为自由变量。

备注：(求特解)

当我们需要确定一个特解时，行阶梯型方便了我们求解。为了做到这一点，我们用主元列来表示方程组的右侧，即$\mathbf{b}={\sum }_{i=1}^P{\lambda }_i{\mathbf{p}}_i$，其中${\mathbf{p}}_i,i=1,\dots ,P$为主元所在列，即主元列。

${\lambda }_i$很容易确定，我们可以从最右边的主元列开始，向左一 一确定。

在上一个例子中，我们试图找到${\lambda }_1，{\lambda }_2，{\lambda }_3$，使得：
$${\lambda }_1\left[\begin{array}{l}1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{l}1\\ 1\\ 0\\ 0\end{array}\right]+{\lambda }_3\left[\begin{array}{c}-1\\ -1\\ 1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ -2\\ 1\\ 0\end{array}\right]$$

从这里，我们相对直观地发现${\lambda }_3=1,{\lambda }_2=-1,{\lambda }_1=2$。而对于非主元列，我们隐式地将其系数设置为0。因此，我们得到特解为：$[2,0,-1,1,0{]}^{\top }$

备注：行最简阶梯型

一个方程组为行最简阶梯型(Reduced Row Echelon Form，也称为 row-reduced echelon form 或 row canonical form)需要满足：

• 它是行阶梯型
• 每个主元都为1
• 主元是其所在列中唯一的非零项。

行最简阶梯型将在后面的第2.3.3节中扮演重要的角色，因为它使我们可以直接地确定线性方程组的通解

备注：高斯消元法

高斯消元法(Gaussian elimination)是一种通过初等变换将线性方程组转化为行最简阶梯型的算法。

例 2.7行最简阶梯型

有以下行最简阶梯型矩阵(粗体1为主元)：
$$\mathbf{A}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\end{array}\right](2.49)$$

求$\mathbf{A}\mathbf{x}=0$的解的关键是非主元列，我们需要将其表示为主元列的（线性）组合；而行最简阶梯型使这一点相对简单。我们用左边的主元列的倍数和来表示非主元列：

第二列是第一列的3倍（我们可以忽略第二列右边的主元列）。因此，为了得到$0$，我们需要将第一列的三倍减去第二列。

现在，我们来看看第二个非主元列——第五列。

第五列可以由第一个主元列的3倍、第二个主元列的9倍和第三个主元列的−4倍表示。我们需要根据主元列的索引，并将第五列转换为第一列的3倍、第二列（非主元列）的0倍、第三列(第二个非主元列)的9倍和第四列的-4倍（即第三主元列）之和，然后减去第五列得到$0$。最后，可以求解这个齐次方程组。

总之，$\mathbf{A}\mathbf{x}=0,\mathbf{x}\in {\mathbb{R}}^5$的所有解都由下式给出
$$\left\{\mathbf{x}\in {\mathbb{R}}^5:\mathbf{x}={\lambda }_1\left[\begin{array}{c}3\\ -1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}3\\ 0\\ 9\\ -4\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\right\}(2.50)$$

2.3.3 Minus-1 技巧

下面，我们将介绍一个实用的技巧来求解齐次线性方程组$\mathbf{A}\mathbf{x}=0$的解$\mathbf{x}$，其中$\mathbf{A}\in {\mathbb{R}}^{k\times n},\mathbf{x}\in {\mathbb{R}}^n$

首先，我们假设$\mathbf{A}$是行最简阶梯型，且没有只包含零的行，即：
$$\mathbf{A}=\left[\begin{array}{ccccccccccccccc}0& \cdots & 0& 1& \ast & \cdots & \ast & 0& \ast & \cdots & \ast & 0& \ast & \cdots & \ast \\ ⋮& & ⋮& 0& 0& \cdots & 0& 1& \ast & \cdots & \ast & ⋮& ⋮& & ⋮\\ ⋮& & ⋮& ⋮& ⋮& & ⋮& 0& ⋮& & ⋮& ⋮& ⋮& & ⋮\\ ⋮& & ⋮& ⋮& ⋮& & ⋮& ⋮& ⋮& & ⋮& 0& ⋮& & ⋮\\ 0& \cdots & 0& 0& 0& \cdots & 0& 0& 0& \cdots & 0& 1& \ast & \cdots & \ast \end{array}\right]$$

其中$\ast$为随机的实数，$\mathbf{A}$每行的第一个非零项必须为1，相应列中的所有其他项必须为0。

含主元的列$j_1,\dots ,j_k$（用粗体标记）是标准单位向量$e_1,\dots ,e_k\in {\mathbb{R}}^k$。我们通过添加$n-k$行将该矩阵扩展为$n\times n$-矩阵$\tilde{\mathbf{A}}$，扩展所添加行的形式为：

$$\left[\begin{array}{lllllll}0& \cdots & 0& -1& 0& \cdots & 0\end{array}\right](2.52)$$

所以增广矩阵$\tilde{\mathbf{A}}$的对角线包含1或-1。然后，包含−1作为主元的列是齐次方程组$\mathbf{A}\mathbf{x}=0$的解。更准确地说，这些列构成$\mathbf{A}\mathbf{x}=0$的解空间的基，我们也将其称为核或零空间(见2.7.3节)。

例 8 (Minus-1 Trick)
对于(2.49)这一最简阶梯型(REF)矩阵：
$$\mathbf{A}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\end{array}\right]$$

现在我们通过在对角线上的主元缺失的地方添加(2.52)形式的行，将这个矩阵扩展为一个5 × 5的矩阵
$$\tilde{\mathbf{A}}=\left[\begin{array}{ccccc}1& 3& 0& 0& 3\\ 0& -1& 0& 0& 0\\ 0& 0& 1& 0& 9\\ 0& 0& 0& 1& -4\\ 0& 0& 0& 0& -1\end{array}\right]$$

我们可以通过取$\tilde{\mathbf{A}}$内包含对角线上-1的的列，立即得到$\mathbf{A}\mathbf{x}=0$的解：
$$\left\{\begin{array}{l}x\in {\mathbb{R}}^5:\mathbf{x}={\lambda }_1\left[\begin{array}{c}3\\ -1\\ 0\\ 0\\ 0\end{array}\right]+{\lambda }_2\left[\begin{array}{c}3\\ 0\\ 9\\ -4\\ -1\end{array}\right],{\lambda }_1,{\lambda }_2\in \mathbb{R}\}\end{array}\right\}$$

与例2.7的结果相同。

求逆

为了计算$\mathbf{A}\in {\mathbb{R}}^{n\times n}$的逆${\mathbf{A}}^{-1}$，我们需要找到满足$\mathbf{A}\mathbf{X}={\mathbf{I}}_n$的矩阵$\mathbf{X}$。$\mathbf{X}={\mathbf{A}}^{-1}$。我们可以把它写成一组线性方程组$\mathbf{A}\mathbf{X}={\mathbf{I}}_n$并求解$\mathbf{X}=\left[{\mathbf{x}}_1|\cdots |{\mathbf{x}}_n\right]$。我们使用增广矩阵表示法来表示这组线性方程组，并对其做以下变换：
$$\left[\mathbf{A}\mid {\mathbf{I}}_n\right]⇝\cdots ⇝\left[{\mathbf{I}}_n\mid {\mathbf{A}}^{-1}\right]$$

这意味着，如果我们把增广方程组简化成行最简阶梯型，我们就可以在方程组的右手边读出该矩阵的逆。因此，确定矩阵的逆矩阵相当于求解线性方程组。

例 2.9 用高斯消元法求逆矩阵

求
$$\mathbf{A}=\left[\begin{array}{llll}1& 0& 2& 0\\ 1& 1& 0& 0\\ 1& 2& 0& 1\\ 1& 1& 1& 1\end{array}\right]$$
的逆。

我们写出增广矩阵

$$\left[\begin{array}{cccccccc}1& 0& 2& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 1& 0& 0\\ 1& 2& 0& 1& 0& 0& 1& 0\\ 1& 1& 1& 1& 0& 0& 0& 1\end{array}\right]$$
并利用高斯消元法将其化为行最简阶梯型：
$$\left[\begin{array}{cccccccc}1& 0& 0& 0& -1& 2& -2& 2\\ 0& 1& 0& 0& 1& -1& 2& -2\\ 0& 0& 1& 0& 1& -1& 1& -1\\ 0& 0& 0& 1& -1& 0& -1& 2\end{array}\right]$$

这样，所需的逆矩阵就在其右侧给出了：
$${\mathbf{A}}^{-1}=\left[\begin{array}{cccc}-1& 2& -2& 2\\ 1& -1& 2& -2\\ 1& -1& 1& -1\\ -1& 0& -1& 2\end{array}\right]$$

我们可以通过执行乘法$\mathbf{A}{\mathbf{A}}^{-1}$是否等于${\mathbf{I}}_4$来检验。

2.3.4 求解线性方程组的算法

在下文中，我们将简要讨论$\mathbf{A}\mathbf{x}=\mathbf{b}$形式的线性方程组的求解方法。这里我们假设存在解。如果没有解，我们就需要求助于近似的解决办法，如第九章的线性回归，这里不作介绍。

如果我们可以确定逆${\mathbf{A}}^{-1}$，那么$\mathbf{A}\mathbf{x}=\mathbf{b}$的解就表示为$\mathbf{x}={\mathbf{A}}^{-1}\mathbf{b}$。然而，只有当$\mathbf{A}$是一个方阵并且可逆时，这种方法才可行，但通常情况并非如此。不过，在适当的的假设下（即$\mathbf{A}$需要有线性独立的列），我们可以使用以下变换：
$$\mathbf{A}\mathbf{x}=\mathbf{b}*{\mathbf{A}}^{\top }\mathbf{A}\mathbf{x}={\mathbf{A}}^{\top }\mathbf{b}*\mathbf{x}={\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }\mathbf{b}$$

即使用Moore-Penrose伪逆(Moore-Penrose pseudo-inverse)${\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }$来确定$\mathbf{A}\mathbf{x}=\mathbf{b}$的Moore-Penrose伪逆解${\left({\mathbf{A}}^{\top }\mathbf{A}\right)}^{-1}{\mathbf{A}}^{\top }\mathbf{b}$，这也对应于最小范数最小二乘法的解。

这种方法的缺点是需要对矩阵的积和${\mathbf{A}}^{\top }\mathbf{A}$的逆进行大量计算。此外，出于数值精度的原因，通常不建议计算逆或伪逆。因此，在下文中，我们将简要讨论求解线性方程组的其他方法。

高斯消元法在计算行列式、检查向量集是否线性独立、计算矩阵的逆，计算矩阵的秩，和确定向量空间的基时起着重要作用。高斯消元法是一种直观而有建设性的方法来解决一个含成千上万变量的线性方程组。然而，对于具有数百万个变量的方程组，这是不切实际的，因为所需的运算量是按联立方程组的数量的立方增长的。

在实践中，许多线性方程组都是通过定常迭代方法(stationary iterative methods)间接求解的，如Richardson方法、Jacobi方法、Gauß-Seidel方法和逐次超松弛方法，或Krylov子空间方法，如共轭梯度、广义最小残差或双共轭梯度。

设${\mathbf{x}}_{\ast }$是$\mathbf{A}\mathbf{x}=\mathbf{b}$的解。这些迭代方法的关键思想是建立以下形式的迭代
$${\mathbf{x}}^{(k+1)}=\mathbf{C}{\mathbf{x}}^{(k)}+\mathbf{d}$$

通过寻找适当的$\mathbf{C}$和$\mathbf{d}$，在每次迭代中减小残差$\Vert {\mathbf{x}}^{(k+1)}-{\mathbf{x}}_{\ast }\Vert$直至收敛到${\mathbf{x}}_{\ast }$。我们将在3.1节中引入范数$\Vert \cdot \Vert$，它允许我们计算向量之间的相似性。