线性代数

在本课程中，假定你知道什么是矩阵和向量，知道简单的算法，如如何将它们相乘，以及一些属性，如矩阵的可逆性。本附录介绍了一些通常不属于线性代数第一课程的概念和定理。

范数

范数（norm）是将绝对值的概念概括到多维对象（如向量和矩阵）的一种方式。有许多定义范数的方法，也有关于不同范数之间关系的理论。这里我们只给出基本的定义；更多的细节可以参见任何一本线性代数教科书，例如[82]。

向量范数

向量空间$V$上的任意函数$n(⋅)$的范数有如下性质：

  • $x\in V$时 $n(x)\geqslant 0$ 且$x=0$时 $n(x)=0$.
  • 对于$x\in V, \lambda \in \mathbb{R}$，总有$n(\lambda x)=|\lambda|n(x)$.
  • $n(x+y)\leqslant n(x)+n(y)$

对于任意的$p\geqslant 1$，向量范数的定义为： $$ |x|{p}=\sqrt[p]{\sum{i}\left|x{i}\right|^{p}} $$ 常见的范数有$|\cdot|_1$（”绝对值之和”）和$|\cdot|_2$（”平方之和的平方根”）；$|\cdot|\infty$定义为$\lim\limits_{p\rightarrow \infty}|\cdot|_p$ ，不难看出，这等于

$$ |x|{\infty}=\max {i}\left|x_{i}\right| $$

矩阵范数

通过将大小为$n$的矩阵视为长度为$n^2$的向量，我们可以定义Frobenius矩阵范数。 $$ |A|{F}=\sqrt{\sum{i, j}\left|a{i j}\right|^{2}} $$ 然而，我们将主要研究相关的矩阵范数。 $$ |A|{p}=\sup {|x|{p}=1}|A x|{p}=\sup {x} \frac{|A x|{p}}{|x|{p}} $$ 根据定义，可以得出 $$ |A x| \leqslant|A||x| $$ 为相关范数。容易得出：

  • $|A|{1}=\max {j} \sum{i}\left|a{i j}\right|$
  • $|A|{\infty}=\max {j} \sum{i}\left|a{i j}\right|$

观察$|A|{2}=\sup {|x|_{2}=1} x^{t} A^{t} A x$，不难得出$|A|_2$是$𝐴$的最大奇异值，是$𝐴^tA$的最大特征值的根。

矩阵的条件数定义为： $$ \kappa(A)=|A|\left|A^{-1}\right| $$ 在对称情况下，使用2-norm，这就是最大和最小特征值之间的比率。

格兰-施密特正交化

Gram-Schmidt（GS）算法将一系列的向量进行归纳正交。这可以用来把一个向量空间的任意基变成一个正交基；也可以看成是把一个矩阵$A$变成一个具有正交列的矩阵。如果$Q$有正交列，那么$Q^tQ$就是对角线，这通常是一个很方便的属性。

GS算法的基本原理可以用两个向量$u,v$来证明。假设我们想要一个向量$v′$，使$u,v$和$u,v′$横跨同一空间，但$v′\perp u$。为此，我们令 $$ v^{\prime} \leftarrow v-\frac{u^{t} v}{u^{t} u} u $$ 很容易看出，这满足要求。

假设我们有一组向量$u_1,…,u_n$，我们想将其正交化，通过连续应用上述变换来做到这一点。

  1. For i = 1,...,n:
  2. For j = 1, ... i − 1:
  3. let c_{ji} = u_{jt} u_i/u_{jt} u_j 
  4.   For i = 1,...,n:
  5. update u_i <- u_i − u_{j}c_{ji}

通常情况下，上述算法中的向量$v$被归一化；这就增加了一条线 $$ u_i\leftarrow u_i/|u_i| $$ 到算法中。GS正交化与这种归一化，应用于矩阵，也被称为QR因式分解。

练习 13.1 假设我们将GS算法应用于一个矩形矩阵$A$的列，得到一个矩阵$Q$。证明有一个上三角矩阵$R$，使得$A=QR$。(提示：看上面的$c_{ji}$系数。)如果我们按照上面的算法将正交向量归一，$Q$有一个额外的属性：$Q^tQ= I$。也要证明这一点。

上面给出的GS算法可以计算出所需的结果，但是只能用精确的算术。如果$v$和其中一个$u_i$之间的角度很小，计算机的实现就会很不准确。在这种情况下，修改后的Gram-Schmidt（MGS）算法会表现得更好。

  1. For 𝑖 = 1,...,𝑛:
  2. For 𝑗 = 1, ... 𝑖 − 1:
  3. let 𝑐𝑗𝑖 = 𝑢𝑗𝑡 𝑢𝑖/𝑢𝑗𝑡 𝑢𝑗 update 𝑢𝑖 ← 𝑢𝑖 − 𝑢𝑗𝑐𝑗𝑖

为了与MGS形成对比，最初的GS算法也被称为经典的Gram-Schmidt（CGS）。为了说明这两种方法的区别，请考虑矩阵 $$ A=\left(\begin{array}{lll} 1 & 1 & 1 \ \epsilon & 0 & 0 \ 0 & \epsilon & 0 \ 0 & 0 & \epsilon \end{array}\right) $$ 其中$\epsilon$是机器精度的顺序，因此在机器算术中$1+\epsilon^2=1$。CGS方法如下。

  • 在机器运算中，第一列的长度为1，因此 $$ q{1}=a{1}=\left(\begin{array}{l} 1 \ \epsilon \ 0 \ 0 \end{array}\right) $$

    • 第二列被正交为$v\leftarrow a_2-1·q_1$，得到

$$ v=\left(\begin{array}{c} 0 \ -\epsilon \ \epsilon \ 0 \end{array}\right), \quad \text { normalized: } \quad q_{2}=\left(\begin{array}{c} 0 \ -\frac{\sqrt{2}}{2} \ \frac{\sqrt{2}}{2} \ 0 \end{array}\right) $$

  • 第三列被正交为$v\leftarrow a3-c_1q_1-c_2q_2$ ，其中 $$ \left{\begin{array}{l} c{1}=q{1}^{t} a{3}=1 \ c{2}=q{2}^{t} a{3}=0 \end{array} \quad \Rightarrow v=\left(\begin{array}{c} 0 \ -\epsilon \ 0 \ \epsilon \end{array}\right) ; \quad \text { normalized: } \quad q{3}=\left(\begin{array}{c} 0 \ \frac{\sqrt{2}}{2} \ 0 \ \frac{\sqrt{2}}{2} \end{array}\right)\right. $$

很容易看出，$q_2$和$q_3$根本就不是正交的。相比之下，MGS方法的不同之处在于最后一步。

  • 如前所述，$q1^ta_3= 1$，所以 $$ v \leftarrow a{3}-q_{1}=\left(\begin{array}{c} 0 \ -\epsilon \ \epsilon \ 0 \end{array}\right) $$

然后，$q2^t v = \sqrt{2} \epsilon$（注意之前$q_2^t a_3 = 0$），所以第二次更新得出 $$ v \leftarrow v-\frac{\sqrt{2}}{2} \epsilon q{2}=\left(\begin{array}{c} 0 \ \frac{\epsilon}{2} \ -\frac{\epsilon}{2} \ \epsilon \end{array}\right), \quad \text { normalized: }\left(\begin{array}{c} 0 \ \frac{\sqrt{6}}{6} \ -\frac{\sqrt{6}}{6} \ 2 \frac{\sqrt{6}}{6} \end{array}\right) $$ 现在所有的$q_i^tq_j$对于$i\neq j$的顺序都是$\epsilon$。

幂法

向量序列 $$ xi = Ax{i-1} $$ 其中$x_0$是某个起始向量，被称为幂法，因为它计算的是随后的矩阵幂与向量的乘积。矩阵幂乘以一个向量，所以称为幂法。

$$ x_i=A^ix_0 $$ 有些情况下，$x_i$向量之间的关系很简单。例如，如果$x_0$是一个特征向量，对于某些标量$\lambda$，我们有 $$ Ax_0 = \lambda x_0 \quad \text{ and } \quad x_i=\lambda^i x_0 $$ 然而，对于一个任意的向量$x_0$，序列${x_i}_i$很可能由独立的向量组成，直到一个点。

练习 13.2 让$A$和$x$为$n\times n$矩阵和维度$n$向量 $$ A=\left(\begin{array}{ccccc} 1 & 1 & & & \ & 1 & 1 & & \ & & \ddots & \ddots & \ & & & 1 & 1 \ & & & 1 \end{array}\right), \quad x=(0, \ldots, 0,1)^{t} $$ 说明对于$i < n，$序列 $[x, Ax, …, A_ix]$ 是一个独立的集合。为什么在$i \geqslant n$的情况下这不再是真的？现在考虑矩阵$B$： $$ A=\left(\begin{array}{ccccc} 1 & 1 & & & \ & 1 & 1 & & \ & & \ddots & \ddots & \ & & & 1 & 1 \ & & & &1 \end{array}\right), \quad x=(0, \ldots, 0,1)^{t} $$ 说明在$i<n/2$的情况下，$[y, By, …, B_iy]$是一个独立的集合，但对于任何更大的$i$值都不是。

虽然在一般情况下，向量$x，Ax，A2x，……$可以预期是独立的，但在计算机运算中，这个故事不再那么清晰。假设矩阵有特征值$\lambda_0 > \lambda_1 \geqslant ⋯ \lambda{n-1}$和相应的特征向量$u_i$，因此

$$ Aui = \lambda_i u_i $$ 让向量$x$写为 $$ x=c_0u_0+\cdots+c{n-1}u{n-1} $$ 那么 $$ A^ix=c_0\lambda_0^iu_i+\cdots+c{n-1}\lambda^i{n-1}u{n-1} $$ 如果我们把它写成 $$ A^{i} x=\lambda{0}^{i}\left[c{0} u{i}+c{1}\left(\frac{\lambda{1}}{\lambda{0}}\right)^{i}+\cdots+c{n-1}\left(\frac{\lambda{n-1}}{\lambda_{0}}\right)^{i}\right] $$ 我们看到，从数值上看，$A^ix$将逐渐接近于主导特征向量$u_0$的倍数。因此，任何使用$A^ix$向量的独立性的计算都可能是不准确的。

非负矩阵；佩伦向量

如果𝐴是一个非负矩阵，最大的特征值具有其特征向量为非负的特性：这就是佩伦-弗洛本纽斯定理。

定理4 如果一个非负矩阵$A$是不可逆的，其特征值满足

  • 幅度最大的特征值$\alpha_1$是实数和简单的。

$$ \alpha_1>|\alpha_2|\geqslant … $$

  • 相应的特征向量为正数。

格什戈林定理

寻找矩阵的特征值通常很复杂。然而，有一些工具可以估计特征值。在本节中，我们将看到一个定理，在某些情况下，它可以提供关于特征值的有用信息。

令$A$是一个方形矩阵，$x$是一个特征对：$Ax=\lambda x$。从一个分量来看，我们有 $$ a{ii}x_i+\sum{j\neq i}a{ij}x_j = \lambda x_i $$ 范数： $$ (a{ii}-\lambda)\leqslant \sum{j\neq j}|a{ij}||\frac{xj}{x_i}| $$ 取决于$i$的值，在此情况下$|x_i|$是最大的，我们发现 $$ (a{ii}-\lambda)\leqslant \sum{j\neq i}|a{ij}|. $$ 这句话可以解释如下。

特征值$\lambda$位于以$ai$为半径的圆内 $\sum{j\neq i}|a_{ij}|$.

由于我们不知道哪一个$i$的值是最大的，我们只能说存在某个$i$的值，使得$\lambda$位于这样一个圆中。这就是Gershgorin定理。

定理5 让$A$是一个正方形矩阵，让$Di$是中心为$a_i$，半径为$\sum{j\neq i}|a{ij}|$的圆，那么特征值包含在圆$\cup_i D_i$的联盟中。 如果常数向量不是特征向量，我们可以得出结论，特征值在这些圆盘的内部。

Householder 反射器

在某些情况下，问题出现了，如何将一个子空间转化为另一个子空间。在某种意义上，Householder reflectors是这个问题的最小解决方案。考虑一个单位向量$u$，并让 $$ H = I -2uu^t $$ 对于这个矩阵，我们有$Hu = -u$，如果$u \perp v$，那么$Hv = v$。换句话说，$v$的倍数的子空间

的倍数子空间被翻转，而正交子空间则保持不变。现在我们来看看将一个空间映射到另一个空间的原始问题。让原空间被一个向量$x$，所产生的空间为$y$，则注意到

$$ \left{\begin{array}{l} x=(x+y) / 2+(x-y) / 2 \ y=(x+y) / 2-(x-y) / 2 \end{array}\right. $$ 换句话说，我们可以根据$u=(x-y)/2$，用反射器将$x$映射为$y$。

householder

我们可以将Householder反射器概括为一种形式 $$ H=I-2uv^t $$ 在LU因子化中使用的矩阵$L_i$（见第5.3节）可以被看作是$L_i = I-\ell_i e_i^t$的形式。

其中$e_i$在$i$的位置上有一个一，而$\ell_i$在该位置以下只有非零。这种形式也使得我们很容易看到$L_i^{-1} =I = I+\ell_i e_i^t$： $$ (I-uv^t)(I+uv^t)=I-uv^tuv^t=0 $$ 若$v^tu=0$。