1. Gram-Schmidt正交化的修正策略

(标准 Gram-Schmidt 正交化) 给定 $n \times m(m \leqslant$$n)$ 阶列满秩矩阵 $\boldsymbol{X}=\left[\boldsymbol{x}_ {1}, \boldsymbol{x}_ {2}, \cdots, \boldsymbol{x}_ {m}\right]$, 本算法产 生 $n \times m$ 阶正交矩阵 $\boldsymbol{Q}=\left[\boldsymbol{q}_ {1}, \boldsymbol{q}_ {2}, \cdots, \boldsymbol{q}_ {m}\right]$和 $m \times m$ 阶非奇异上三角矩阵 $\boldsymbol{R}=\left(r_ {i k}\right)$.

可以看出，当 $\boldsymbol{x}_ {k}$ 与前面的 $\boldsymbol{x}_ {i}$ 接近线性相关时，$r_ {k k}$将接近于 0，用它作分母会导致很大的舍入误差 ，$\boldsymbol{q}_ {i}$ 之间很快失去了正交性。一种改进就是修正的 Gram-Schmidt 交化。它把算法的第 3 行和第 4 行修改为下面的循环:

在不考虑舍入误差时，上述计算结果 $\widetilde{\boldsymbol{q}}$ 与算法 中第 4 行的 $\widetilde{\boldsymbol{q}}$ 是相同的。修正的 Gram-Schmidt 正交化利用了最新的 $\widetilde{\boldsymbol{q}}$，有助于减少舍入误差影响。

2. Arnoldi分解和Lanczos分解的区别

给定矩阵$\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 和向量 $\boldsymbol{v} \in \mathbb{R}^n$ , 设 $\boldsymbol{K}_ {k+1}(\boldsymbol{A}, \boldsymbol{v})=\left[\boldsymbol{v}, \boldsymbol{A} \boldsymbol{v}, \cdots, \boldsymbol{A}^{k} \boldsymbol{v}\right] $是列满秩的，并假定它的 QR 分解为

式中: $\boldsymbol{V}_ {k+1}=\left[\boldsymbol{v}_ {1}, \boldsymbol{v}_ {2}, \cdots, \boldsymbol{v}_ {k+1}\right] \in \mathbb{R}^{n \times(k+1)}$ 满足 $\boldsymbol{V}_ {k+1}^{\mathrm{T}} \boldsymbol{V}_ {k+1}=$$\boldsymbol{I}_ {k+1}$，$\boldsymbol{R}_ {k+1}$ 为非奇异的上三角矩阵。

Arnoldi 分解式为

其中 $\boldsymbol{H}_k$ 为 $(k+1)\times k$ 阶的上 Hessenberg 矩阵。

当 $A \in \mathbb{R}^{n \times n}$ 是对称矩阵时, 对应的 Arnoldi 分解就变成

式中:

称上式为一个长度为 $k$ 的 Lanczos 分解。因此，Lanczos 分解是 Arnoldi 的特殊情形。

3. 投影方法的基本框架

投影方法的基本框架为： step 1, 选取一对子空间 $\mathcal{K}$ 和 $\mathcal{L} .$
step 2, 选取 $\mathcal{K}$ 和 $\mathcal{L}$ 的基 $\boldsymbol{V}=\left[\boldsymbol{v}_ {1}, \cdots, \boldsymbol{v}_ {m}\right]$ 和 $\boldsymbol{W}=\left[\boldsymbol{w}_ {1}, \cdots, \boldsymbol{w}_ {m}\right] .$
step 3, 计算残差 $\boldsymbol{r}=\boldsymbol{b}-\boldsymbol{A} \boldsymbol{x} .$
step 4, 解方程组 $\boldsymbol{W}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{V} \boldsymbol{y}=\boldsymbol{W}^{\mathrm{T}} \boldsymbol{r}$ 得到 $\boldsymbol{y}$.
step 5, 计算近似解 $\boldsymbol{x}:=\boldsymbol{x}+\boldsymbol{V} \boldsymbol{y}$.

4. 3阶矩阵的Householder变换和Givens变换

习题1. 设

利用 Householder 变换求 $\boldsymbol{A}$ 的 $\mathrm{QR}$ 分解。

解：$\boldsymbol{s}_ 1 = [0,1,0]^ {\top}$, $e_1 = [1, 0, 0]^ {\top}$, $c_1 = -\mathrm{sgn}(a_ {11})\Vert s_1 \Vert = 1$, $u_1 = s_1 - c_1 e_1 = [-1,1,0]^ {\top}$,

则有

$\boldsymbol{s}_ 2 = [0,4,3]^ {\top}$，($H_2A_1$ 不改变 $A_1$ 的第一行)，$e_2 = [0, 1, 0]^ {\top}$, $c_2 = -\mathrm{sgn}(a_ {22})\Vert s_2 \Vert = -5$, $u_2 = s_2-c_2e_2 = [0,9,3]^ {\top}$,

于是

从而

故$H_2H_1A=R$，令 $Q^{\top}=H_2H_1$，由于$H_1, H_2$ 为对称矩阵，故

满足 $A=QR$.

习题2. 设

利用 Givens 变换求矩阵 $\boldsymbol{A}$ 的 QR 分解。

$s_1 = [2,0,2]^{\top}$，取 $G_ {12}=I_ {3}$ 即可，则有 $A_1=G_ {12}A=A$。

对于 $G_ {13}$，$c=\frac{x_1}{\sqrt{x_1^2+x_3^2}}=\frac{\sqrt{2}}{2}$，$c=\frac{x_3}{\sqrt{x_1^2+x_3^2}}=\frac{\sqrt{2}}{2}$，令

于是

$s_2 = [ \frac{3\sqrt{2}}{2},2, -\frac{\sqrt{2}}{2}]^{\top}$，对于 $G_ {23}$，$c=\frac{x_2}{\sqrt{x_2^2+x_3^2}}=\frac{2\sqrt{2}}{3}$，$s=\frac{x_3}{\sqrt{x_2^2+x_3^2}}=-\frac{1}{3}$，令

于是

故$G_ {23}G_ {13}G_ {12}A=R$，令 $Q^{\top}=G_ {23}G_ {13}G_ {12}$，于是

满足 $A=QR$。

5. HSS迭代中参数$\alpha$与特征值分布

命题1. 设 $A \in \mathbb{C}^{n \times n}$ 为正定矩阵, $\boldsymbol{H}=\frac{1}{2}\left(\boldsymbol{A}+\boldsymbol{A}^{\mathrm{H}}\right)$ 和$S=\frac{1}{2}\left(\boldsymbol{A}-\boldsymbol{A}^{\mathrm{H}}\right)$ 为其 Hermite 和反 Hermite 部分, 且 $\alpha$ 是一个正常数. 则 $\mathrm{HSS}$ 迭代矩阵 $\boldsymbol{M}(\alpha)$ 为

且其谱半径 $\rho(\boldsymbol{M}(\alpha))$ 有上界

式中: $\lambda(\boldsymbol{H})$ 为矩阵 $\boldsymbol{H}$ 的谱集，因此成立

即 $\mathrm{HSS}$ 迭代收敘到线性方程组 $\boldsymbol{Ax}=\boldsymbol{b}$ 的唯一解 $\boldsymbol{x}^{*} \in \mathbb{C}^{n} .$

证明

记

注意到对任意的 $\alpha>0$，$\alpha \boldsymbol{I}+\boldsymbol{H}$ 和 $\alpha \boldsymbol{I}+\boldsymbol{S}$ 是非奇异的，利用矩阵谱的相似不变性，得

记 $\boldsymbol{Q}(\alpha)=(\alpha \boldsymbol{I}-\boldsymbol{S})(\alpha \boldsymbol{I}+\boldsymbol{S})^{-1}$， 注意到 $\boldsymbol{S}^{\mathrm{H}}=-\boldsymbol{S}$，有

即 $\boldsymbol{Q}(\alpha)$ 是酉矩阵，故有 $|Q(\alpha)|_ {2}=1$。从而有

由于 $\lambda_ {i}>0(i=1,2, \cdots, n)$ 及 $\alpha>0$，容易推得 $\rho(\boldsymbol{M}(\alpha)) \leqslant$$\sigma(\alpha)<1$ 。

命题2. 设 $A \in \mathbb{C}^{n \times n}$ 为正定矩阵，$\boldsymbol{H}=\frac{1}{2}\left(\boldsymbol{A}+\boldsymbol{A}^{\mathrm{H}}\right)$ 和$\boldsymbol{S}=\frac{1}{2}\left(\boldsymbol{A}-\boldsymbol{A}^{\mathrm{H}}\right)$ 为其 Hermite 和反Hermite 部分，且 $\lambda_ {\min }$ 和 $\lambda_ {\max }$分别为矩阵 $\boldsymbol{H}$ 的最小和最大特征值，$\alpha$ 是一个正常数。则

且

式中: $\kappa(\boldsymbol{H})=\lambda_ {\max } / \lambda_ {\min }$ 为 $\boldsymbol{H}$ 的谱条件数。

证明

对任意的 $\alpha>0$, 函数 $f(\lambda)=\frac{\alpha-\lambda}{\alpha+\lambda}$ 关于 $\lambda$ 是单调递减的 $\left(f^{\prime}(\lambda)=-2 \alpha /(\alpha+\lambda)^2<0\right)$, 故有

若 $\alpha^ { * }$ 是 $\sigma(\alpha)$ 的极小点，则必有 $\alpha^ { * }=\lambda_ {\min }>0$， $\alpha^ { * }-\lambda_ {\max }<0$,

从上式解得

从而推论的结论成立。

6. 迭代法的外推思想

使用迭代格式求解方程组 $\boldsymbol{Ax}=\boldsymbol{b}$ 时，迭代过程可能收敛，也可能不收敛。我们希望找到一种改进方法，使得不收敛的格式变得收敛，收敛慢的格式变得收敛快。

给定第 $k$ 次迭代后的估计解 $\boldsymbol{x}^{(k)}$，由迭代格式 $\boldsymbol{x}^{k+1}=B\boldsymbol{x}^{k}+\boldsymbol{f},\ k=1,2,\cdots$ 得到了一 个新的估计解 $\boldsymbol{B} \boldsymbol{x}^{(k)}+\boldsymbol{f}$，再将它与 $\boldsymbol{x}^{(k)}$，$\boldsymbol{x}^{(k-1)}$ 等进行适当的组合，就可能得到更快的迭代收敛速度。这就是迭代法加速的基本思想。

在迭代格式 $\boldsymbol{x}^{k+1}=B\boldsymbol{x}^{k}+\boldsymbol{f},\ k=1,2,\cdots$ 中引入一个参数 $\gamma \neq 0$，构造新的迭代格式

式中:

若上述迭代格式收敛到某个 $x^{*}$，则有

所以，不管 $\gamma \neq 0$ 如何选取，当迭代格式 $\eqref{eq1}$ 收敛时，它必定收敛到原来方程组 $\boldsymbol{x}=\boldsymbol{B} \boldsymbol{x}+\boldsymbol{f}$ 的解。因此希望选取一个比较好的参数 $\gamma$，使得迭代格式 $\eqref{eq1}$ 收敛得尽可能快。这就是外推法。

7. 广义极小参量法（GMRES）

广义极小残量法 $(\mathrm{GMRES})$ ： (1) 令 $\boldsymbol{v}_ {1}=\boldsymbol{r}_ {0} /\left|\boldsymbol{r}_ {0}\right|_ {2}$，产生一个长度为 $k$ 的 Arnoldi 分解 $\boldsymbol{A} \boldsymbol{V}_ {k}=\boldsymbol{V}_ {k} \boldsymbol{H}_ {k}+\beta_ {k} \boldsymbol{v}_ {k+1} \boldsymbol{e}_ {k}^{\mathrm{T}}=\boldsymbol{V}_ {k+1} \widetilde{\boldsymbol{H}}_ {k+1, k}$
(2) 利用 Givens 变换求 $\widetilde{\boldsymbol{H}}_ {k+1, k}$ 的 QR 分解 $\left(\boldsymbol{G}_ {k} \boldsymbol{G}_ {k-1} \cdots \boldsymbol{G}_ {2} \boldsymbol{G}_ {1}\right) \widetilde{\boldsymbol{H}}_ {k+1, k}=\left[\begin{array}{c}\boldsymbol{R}_ {k} \ \mathbf{0}\end{array}\right]$ 并按式

求得向量 $\boldsymbol{t}_ {k}$ 和数 $\rho_ {k} .$
(3) 用回代法求解上三角方程组 $\boldsymbol{R}_ {k} \boldsymbol{z}_ {k}=\boldsymbol{t}_ {k}$, 得 $\boldsymbol{z}_ {k} .$
(4) 计算 $\boldsymbol{x}_ {k}=\boldsymbol{x}_ {0}+\boldsymbol{V}_ {k} \boldsymbol{z}_ {k} .$
(5) 若 $\left|\rho_ {k}\right| / \beta<\varepsilon($ 事先给定的误差界 $)$，则终止；否则增加 $k$ 的值，重复上面的过程。

重启技术是为了节省计算机内存，预处理技术是为了使系数矩阵的谱相对集中，从而加快速度。

8. BCGSTAB方法避免残差震荡，保持下降的修正策略

$\mathrm{BCGSTAB}$ 方法是为了改进 $\mathrm{CGS}$ 方法之残量的范数剧烈抖动而提出的。这一方法的基本思想是 $\mathrm{CGS}$ 方法的残量 $\boldsymbol{r}_ {k}^{\mathrm{CGS}}$ 满足

可以考虑不用多项式 $\varphi_ {k}$，而是选择一个其他的 $k$ 次多项式 $\widetilde{\varphi}_ {k}$，使

以期待这样选取的相对残差范数 $\left|\boldsymbol{r}_ {k}\right|_ {2} /\left|\boldsymbol{r}_ {0}\right|_ {2}$ 的振荡性有所改进。

一种选择 $\widetilde{\varphi}_ {k}$ 的方法是根据递推公式

式中: $\omega_ {k+1}$ 为待定参数。BCGSTAB 方法正是利用这一参数的可选择性来改进相对残差范数的振荡性。

9. 线性最小二乘问题的等价形式

设 $A \in \mathbb{C}^{m \times n}, \boldsymbol{b} \in \mathbb{C}^{m}$, 确定 $\boldsymbol{x} \in \mathbb{C}^{n}$ 使得

问题 $\eqref{eq2}$ 称为线性最小二乘问题 $($ Least Squares, $\mathrm{LS}$ 问题 $)$，而 $\boldsymbol{x}$ 则称为最小二乘解或极小解。称 $\boldsymbol{r}(\boldsymbol{x})=\boldsymbol{b}-\boldsymbol{A} \boldsymbol{x}$ 为残差向量 ，简称残量。

$Ax=b$ 有解 $\iff$ $AA^{+}b=b$，通解 $x=A^{+}b + (I-A^{+}A)z$，唯一极小范数解 $x_ {0}=A^{+}b$，

$Ax=b$ 无解 $\Longrightarrow$ 唯一极小范数最小二乘解 $x_ {0}=A^{+}b$。

法方程

$\boldsymbol{x}$ 是最小二乘问题 $\eqref{eq2}$ 的极小解，即 $x \in S_ {\mathrm{LS}}$ 的充分必要条件是 $\boldsymbol{x}$ 为方程

的解，其中式 $\eqref{eq3}$ 称为最小二乘问题的法方程。
证明：最小二乘问题 $\eqref{eq2}$ 等价于极小化问题

由于 $\boldsymbol{A}^{\mathrm{H}} \boldsymbol{A} \in \mathbb{C}^{n \times n}$ 是半正定矩阵，因此 $n$ 元实函数 $\varphi(\boldsymbol{x})$ 是凸函数，故 $x$ 是最小二乘问题 $\eqref{eq2}$ 的极小解等价于

KKT方程

设 $A \in \mathbb{C}^{m \times n}$，$\boldsymbol{b} \in \mathbb{R}^{n}$。则 $\boldsymbol{x}$ 和 $\boldsymbol{r}=\boldsymbol{b}-\boldsymbol{A} \boldsymbol{x}$ 分别为最小二乘问题 $\eqref{eq2}$ 的极小解和残量的充分必要条件是 $x$ 和$\boldsymbol{r}$ 为鞍点系统

的解。上述线性系统称为最小二乘问题的KKT 方程。
证明 ：若 $x$ 为最小二乘问题 $\eqref{eq2}$ 的极小解，而 $\boldsymbol{r}=\boldsymbol{b}-\boldsymbol{A} \boldsymbol{x}$ 为 其残量，则

由广义逆 $A^{\dagger}$ 的性质及等式 $r+A x=b$，得

故式 $\eqref{eq4}$ 是相容的线性系统，且 $x$ 和 $r$ 满足式 $\eqref{eq4}$。 反之，通过验证广义逆的四个条件，可以验证

故式 $\eqref{eq4}$ 的任一解向量 $x, r$ 有如下形式

式中: $\boldsymbol{y} \in \mathbb{C}^{m}, \boldsymbol{z} \in \mathbb{C}^{n}$ 为任意向量。故满足式 $\eqref{eq4}$ 的任一组向量 $\boldsymbol{x}, \boldsymbol{r}$ 分别为式 $\eqref{eq4}$ 的极小解和残量。证毕。

10. 求解LS问题的QR方法

本节考虑最小二乘问题 $\eqref{eq2}$ 中的矩阵 $A \in \mathbb{R}^{m \times n}(m \geqslant n)$ 的情形。根据正交矩阵保持向量 2 范数不变的性质，对于任意的正交矩阵 $Q \in \mathbb{R}^{m \times m}$，最小二乘问题 $\eqref{eq2}$ 等价于

这样, 就可望通过适当选取正交矩阵 $Q$，使原问题 $\eqref{eq2}$ 转化为较为容易求解的最小二乘问题 $\eqref{eq5}$ ，这就是正交化方法一 $\mathrm{QR}$ 分解方法的基本思想。

11. 求矩阵特征值的基本QR方法下三角矩阵趋于0

定理1 设对称矩阵 $A \in \mathbb{R}^{n \times n}$ 满足

对应的规范正交化特征向量为 $\boldsymbol{x}_ {1}, \boldsymbol{x}_ {2}, \cdots, \boldsymbol{x}_ {n}$。如果单位坐标向量

中的 $\alpha_ {1} \neq 0$，那么由算法 $7.5$ 生成的矩阵序列 ${\boldsymbol{A}_ {k}}$ 具有收敛性质

证明：记 $\widetilde{Q}_ {k}$ 的第 1 列为 $\widetilde{\boldsymbol{q}}_ {1}^{(k)}=\widetilde{\boldsymbol{Q}}_ {k} \boldsymbol{e}_ {1}$，$\widetilde{\boldsymbol{R}}_ {k}$ 的第 1 个对角元为$\widetilde{r}_ {11}^{(k)}$，则由式 $(7.52)$ 可知

注意到 $\Vert \widetilde{\boldsymbol{q}}_ {1}^ {(k)}\Vert_ {2}=1, \widetilde{r}_ {11}^ {(k)} \neq 0$ (因矩阵 $A$ 非奇异 )。从而 $\vert \widetilde{r}_ {11}^ {(k)}\vert =\Vert A^ {k} e_ {1} \Vert_ {2}$。于是，根据幂法的收敛性，有

式中：$\boldsymbol{z}_ {1}$ 为矩阵 $\boldsymbol{A}$ 的对应于 $\lambda_ {1}$ 的规范化特征向量 $($ 可以相差一个常数因子 $\pm 1) .$ 进而, 由式 $(7.51)$，可以把 $\boldsymbol{A}_ {k+1}$ 写成

式中：$a_ {11}^{(k+1)}=\left(\widetilde{\boldsymbol{q}}_ {1}^{(k)}\right)^{\mathrm{T}} \boldsymbol{A} \widetilde{\boldsymbol{q}}_ {1}^{(k)}, \boldsymbol{\alpha}^{(k+1)}=\left(\widetilde{\boldsymbol{Q}}_ {k-1}^{(k)}\right)^{\mathrm{T}} \boldsymbol{A} \widetilde{\boldsymbol{q}}_ {1}^{(k)}$。 根据式 $(7.55)$，得

故由引理 7.1，得

因此, $\lim _ {k \rightarrow \infty} \boldsymbol{\alpha}^{(k+1)}=\mathbf{0}$。于是有

即式 $(7.54)$ 成立。证毕。

定理2 设 $\boldsymbol{A}=\boldsymbol{X} \boldsymbol{\Lambda} \boldsymbol{X}^{-1}$，其中 $\boldsymbol{\Lambda}=\operatorname{diag}\left(\lambda_ {1}, \lambda_ {2}, \cdots, \lambda_ {n}\right)$。如果 (1) $\left|\lambda_ {1}\right|>\left|\lambda_ {2}\right|>\cdots>\left|\lambda_ {n}\right|>0$；(2) $\boldsymbol{X}^{-1}$ 具有 LU 分解：$\boldsymbol{X}^{-1}=\boldsymbol{L} \boldsymbol{U}$， 则 $\mathrm{QR}$ 方法基本收敛于上三角矩阵。 证明： 由式 $(7.51)$ 可知，只需分析 $\widetilde{Q}_ {k}$ 的极限情况。而由式 $(7.52)$，只需分析 $A^{k}$ 的极限情况。注意到

令

则

由于 $L$ 是单位下三角形，故

由假设条件 $\mathbb{1}$ 知，$\boldsymbol{E}_ {k} \rightarrow \boldsymbol{O}$ 且 $\left(\boldsymbol{E}_ {k}\right)_ {i j}$ 的收敛速度是 $\left|\lambda_ {i} / \lambda_ {j}\right|$. 设 $\boldsymbol{X}=Q R$ 且 $R$ 的对角元均为正数，则有

因为 $\boldsymbol{E}_ {k} \rightarrow \boldsymbol{O}(k \rightarrow \infty)$, 故当 $k$ 充分大时， $\boldsymbol{I}+\boldsymbol{R} \boldsymbol{E}_ {k} \boldsymbol{R}^{-1}$ 非奇异，所以有唯一的 QR 分解$\boldsymbol{I}+\boldsymbol{R} \boldsymbol{E}_ {k} \boldsymbol{R}^{-1}=\widehat{\boldsymbol{Q}}_ {k} \widehat{\boldsymbol{R}}_ {k}\left(\widehat{\boldsymbol{R}}_ {k}\right.$ 的对角元为正 $)$，而且当 $k \rightarrow \infty$ 时，$\widehat{\boldsymbol{Q}}_ {k} \rightarrow \boldsymbol{I}, \widehat{\boldsymbol{R}}_ {k} \rightarrow \boldsymbol{I}$。 此时，$\boldsymbol{A}^{k}$ 有如下分解

妨碍上式成为 $A^{k}$ 的 $\mathrm{QR}$ 分解的仅仅是上式右端第 2 个因子(上三角矩阵 )​ 的对角元可能非正。为补救这一点，可引入两个对角正交矩阵

式中: $\boldsymbol{U}_ {i i}(i=1,2, \cdots, n)$ 为矩阵 $\boldsymbol{U}$ 的对角元。于是

是 $A^{k}$ 的唯一 QR 分解。从而由式 $(7.51)$，有

将 $\boldsymbol{A}=\boldsymbol{X} \boldsymbol{\Lambda} \boldsymbol{X}^{-1}=Q \boldsymbol{R} \boldsymbol{\Lambda} \boldsymbol{R}^{-1} \boldsymbol{Q}^{-1}$ 代入上式，得

因为 $\widehat{\boldsymbol{Q}}_ {k}^{-1} \boldsymbol{R} \boldsymbol{\Lambda} \boldsymbol{R}^{-1} \widehat{\boldsymbol{Q}}_ {k} \rightarrow \boldsymbol{R} \boldsymbol{\Lambda} \boldsymbol{R}^{-1} \equiv \overline{\boldsymbol{R}}($ 上三角矩阵 $)$，所以 $\boldsymbol{A}_ {k}$ 的对角线以下元素收敛于 $0$。因为 $D_ {1}^{k}$ 可能不收敛，故 $\boldsymbol{A}_ {k}$ 基本收敛 于 $\overline{\boldsymbol{R}}$。证毕。

12. Krylov子空间求大规模特征值问题的思想

设 $(\lambda, \boldsymbol{x})$ 是矩阵 $\boldsymbol{A}$ 的一个特征对，即

再假定

于是，由式 $\eqref{eq6}$有

从而有

因此，若 $(\lambda, \boldsymbol{y})$ 是 $\boldsymbol{H}_ {k}=\boldsymbol{V}_ {k}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{V}_ {k}$ 的特征对，则可用 $\left(\lambda, \boldsymbol{V}_ {k} \boldsymbol{y}\right)$近似 $A$ 的特征对。这样就将大型特征值问题 $\eqref{eq6}$ 转化为一个小型特征值问题:

这就是用 Krylov 子空间方法求解大规模特征值问题的基本思想。

13. 数值代数理论基础

1.正定矩阵定义

设 $A \in \mathbb{R}^{n \times n}$， 若对任意的非零向量 $x \in \mathbb{R}^{n}$ 有$(\boldsymbol{A} \boldsymbol{x}, \boldsymbol{x})>0(\geqslant 0)$，则称 $\boldsymbol{A}$ 为 $($ 实 $)$ 正定 矩阵 $($ 半正定矩阵 $)$， 若 $\boldsymbol{A}$还是对称的，则称为 $($ 实 $)$ 对称正定矩阵 $($ 对称半正定矩阵 $)$。

2.Schur分解

设 $A \in \mathbb{C}^{n \times n}$，则存在酉矩阵 $\boldsymbol{P} \in \mathbb{C}^{n \times n}$ 使得

式中：$\boldsymbol{T}$ 为上三角矩阵，其对角元素是 $\boldsymbol{A}$ 的特征值，而且可以选取 $\boldsymbol{P}$ 使得 $\boldsymbol{T}$ 的对角元可以任意排列。

3.奇异值定义

设 $A \in \mathbb{C}_ {r}^{m \times n}(r \geqslant 1)$，记 Hermite 矩阵 $A^{\mathrm{H}} \boldsymbol{A}$ 的 $n$ 个特征值为 $\lambda_ {1} \geqslant \lambda_ {2} \geqslant \cdots \lambda_ {r}>\lambda_ {r+1}=\cdots=\lambda_ {n}=0$，则称

为 $A$ 的奇异值。

4.奇异值分解定理

设 $A \in \mathbb{C}_ {r}^{m \times n}$ 的正奇异值为 $\sigma_ {1}, \sigma_ {2}, \cdots, \sigma_ {r}$。则存在 $m$ 阶酉矩阵 $\boldsymbol{U}$ 和 $n$ 阶酉矩阵 $\boldsymbol{V}$，使得

式中：$\boldsymbol{\Sigma}$ 为 $m \times n$ 阶对角矩阵，且这里 $\boldsymbol{\Sigma}_ {r}=\operatorname{diag}\left(\sigma_ {1}, \sigma_ {2}, \cdots, \sigma_ {r}\right), \sigma_ {i}>0,1 \leqslant i \leqslant r, r \leqslant \min {m, n} $。

5.矩阵范数

6.谱半径

设 $A \in \mathbb{C}^{n \times n}$，其特征值为 $\lambda_ {1}, \lambda_ {2}, \cdots, \lambda_ {n}$，则称

为矩阵 $A$ 的谱半径。由上述定义，$|\boldsymbol{A}|_ {2}$ 可定义为

特别地，当 $A$ 为 Hermite 矩阵时，有

$\boldsymbol{A}$ 的谱半径不超过 $\boldsymbol{A}$ 的任何范数，即

7.满秩分解

设 $A \in \mathbb{C}_ {r}^{m \times n}(r>0)$, 若存在列满秩矩阵 $\boldsymbol{F} \in \mathbb{C}_ {r}^{m \times r}$ 和行满秩矩阵 $G \in \mathbb{C}_ {r}^{r \times n}$，使得 $\boldsymbol{A}=\boldsymbol{F} G$，则称 $\boldsymbol{F} \boldsymbol{G}$ 为 $\boldsymbol{A}$ 的 一个满秩分解。

由

可知

于是有

8.矩阵广义逆的计算

设$A$ 的最大秩分解 $A=FG$ , 则 $\boldsymbol{A}^{\dagger}=\boldsymbol{G}^{\mathrm{H}}\left(\boldsymbol{G}\boldsymbol{G}^{\mathrm{H}}\right)^{-1} \left(\boldsymbol{F}^{\mathrm{H}}\boldsymbol{F}\right)^{-1}\boldsymbol{F}^{\mathrm{H}}$。

已知

求 $\boldsymbol{A}$ 的满秩分解和 $A^{\dagger}$。

解

因此，有