投影笔记 · Shun Li's Notes

本文的矩阵部分均在实数域上讨论，采用欧氏内积；未特别注明时，向量范数为 $2$ -范数，矩阵范数为其诱导的谱范数。Hilbert 空间中的算子范数由该空间的内积范数诱导。

幂等矩阵

Definition

称方阵 $A$ 是一个幂等矩阵(idempotent)，如果满足 $A^2 = A$ 。

根据定义显然有：如果满足 $A$ 是幂等矩阵，那么 $A^{\mathsf{T}}$ 也是幂等矩阵。因为 $x^2-x$ 是方阵 $A$ 的化零多项式， $A$ 的特征值集合只能是 $\{0,1\}$ 的子集，并且每一个Jordan块都是 $1\times 1$ 的。可以据此给幂等矩阵进行初步的分类：

特征值全为 1，对应单位方阵 $I$ ；（除此之外的幂等矩阵都是奇异矩阵）
特征值全为 0，对应零方阵 $O$ ；
特征值包括 0 和 1，对应一般的幂等矩阵 $A$ 。（特征值只有 0 和 1 并不能推出 $A$ 是幂等矩阵，还要求可以相似对角化）

因为幂等矩阵的特征值只可能为 0 和 1，而矩阵的迹是特征值的和： $\text{tr}(A) = \lambda_1 + \cdots + \lambda_n$ ，因此幂等矩阵的秩和迹相等

Copy LaTeX

如果 $A$ 是幂等矩阵，那么容易验证 $I - A$ 同样也是幂等矩阵

Copy LaTeX

对于非平凡的幂等矩阵 $A$ （排除 $O$ ）的范数有如下显然的结论

Copy LaTeX

同理，在排除 $A=I$ 的非平凡情形下， $\| I - A \| \ge 1$ ，这两个结论也可以从 $\|A\| \ge \rho(A)$ 直接推出。

一个自然的问题是：这里得到的范数下界在什么时候取等？一个已知的线性代数结论是：对于正规方阵 $M$ （满足 $M M^\top = M^\top M$ ），可以取等 $\| M \| = \rho(M)$ 。如果幂等方阵 $A$ 是正规方阵，由于它是实矩阵且特征值只含有 0 和 1，可以正交相似对角化。因此存在正交方阵 $Q$ ，使得

Copy LaTeX

此时必然有 $A = A^\top$ 为对称方阵。事实上，对称性条件是充要的，有如下命题：

Proposition

对于非平凡的幂等矩阵 $A$ （排除 $I$ 和 $O$ ）

Copy LaTeX

Proof

若 $A$ 对称，则 $A$ 是正规矩阵，可以正交相似对角化，由于 $A$ 的特征值只含有 0 和 1，那么必然存在正交方阵 $Q$ ，使得

Copy LaTeX

此时自然有 $\|A\| = 1$ 。

反之，假设 $\|A\|=1$ 。设 $\text{rank}(A)=r$ ，取 $A$ 的列空间的一组标准正交基作为 $Q_1\in\mathbb{R}^{n\times r}$ 的列向量，再补充成正交方阵 $Q=[Q_1,Q_2]$ 。因为 $A^2=A$ ，所以 $A$ 作用在其列空间上等于恒等变换，于是

Copy LaTeX

由于正交相似变换不改变矩阵 $2$ -范数，

Copy LaTeX

因此 $\|I_r+CC^\top\|\le 1$ 。但 $CC^\top$ 是半正定矩阵，若 $C\ne O$ ，则 $I_r+CC^\top$ 至少有一个特征值严格大于 $1$ ，矛盾。所以 $C=O$ ，从而

Copy LaTeX

这说明 $Q^\top A Q$ 对称，因此 $A=A^\top$ 。

因此，可以在非平凡幂等矩阵的基础上，自然地划分出对称幂等矩阵和非对称幂等矩阵两类。除此之外，还有如下结论：

Theorem

对于非平凡的幂等矩阵 $A$ （排除 $I$ 和 $O$ ），始终有下式成立

Copy LaTeX

Proof

根据对称性，只需要证明对于任意 $x \in \mathbb{R}^n$ ，都有 $\| A x \| \le \| I - A\| \| x \|$ 。将 $x$ 分解得到

Copy LaTeX

先处理两种特殊情况：如果 $y = 0$ ，那么 $\|A x\| = 0$ ，得证；如果 $z = 0$ ，那么

Copy LaTeX

最后的不等号利用了 $\| I - A \| \ge 1$ 的结论。由于 $y,z \neq 0$ ，可以定义

Copy LaTeX

注意到

Copy LaTeX

因此

Copy LaTeX

由 $x$ 的任意性可得 $\|A\| \le \|I-A\|$ ，由对称性可得 $\|A\| = \|I-A\|$ 。

Remark

证明参考 Szyld, Daniel B. "The many proofs of an identity on the norm of oblique projections." Numerical Algorithms 42, no. 3 (2006): 309-323.

投影变换

Definition

称线性变换 $\mathcal{P}: V \to V$ 是一个投影变换(projection)，如果满足 $\mathcal{P}^2 = \mathcal{P}$ 。

Remark

这是代数意义下的定义，不依赖范数、拓扑或内积结构。显然对于有限维空间 $V$ ，投影变换的矩阵表示是一个幂等矩阵，两个概念相互对应。在赋范空间，尤其是 Banach 空间中讨论投影算子时，通常关注有界线性幂等算子。若进一步在 Hilbert 空间中讨论伴随算子、正交性和正交投影，则通常假设 $\mathcal{P}\in\mathcal{L}(H)$ 。单纯的代数幂等条件 $\mathcal{P}^2=\mathcal{P}$ 只能给出代数直和分解，不保证像空间和核空间具有良好的拓扑性质，也不保证算子范数有限。

考虑投影变换 $\mathcal{P}$ 的像空间 $\text{Im}(\mathcal{P})$ 和核空间 $\text{Ker}(\mathcal{P})$ ，有如下结论：

Proposition

对于投影变换 $\mathcal{P}$ ：

$\mathcal{P}$ 限制在 $\text{Im}(\mathcal{P})$ 上的作用是恒等映射： $\left.\mathcal{P}\right|_{\text{Im}(\mathcal{P})} = \mathcal{I}$ ；
通过 $\mathcal{P}$ 可以确定 $V$ 的一种直和分解： $V = \text{Im}(\mathcal{P}) \oplus \text{Ker}(\mathcal{P})$ 。

Proof

第一个结论显然。对于第二个结论，任取 $\beta \in \text{Im}(\mathcal{P}) \cap \text{Ker}(\mathcal{P})$ ，得到

Copy LaTeX

因此 $\text{Im}(\mathcal{P}) \cap \text{Ker}(\mathcal{P}) = \{0\}$ 。任取 $\alpha \in V$ ，可以分解为 $\alpha = \mathcal{P} \alpha + (\mathcal{I}-\mathcal{P})\alpha$ ，其中 $(\mathcal{I}-\mathcal{P})\alpha$ 满足 $\mathcal{P} (\mathcal{I}-\mathcal{P})\alpha = (\mathcal{P} - \mathcal{P}^2)\alpha = 0$ ，因此 $(\mathcal{I}-\mathcal{P})\alpha \in \text{Ker}(\mathcal{P})$ ，得证直和分解。

如果 $\mathcal{P}$ 是一个投影变换，那么 $\mathcal{Q} = \mathcal{I}-\mathcal{P}$ 同样也是一个投影变换，因为

Copy LaTeX

并且 $\mathcal{P}$ 和 $\mathcal{Q}$ 显然具有如下的性质：

Copy LaTeX

反过来，可以通过空间的一对直和分解来构造一对相应的投影变换：

Definition

对于 $V$ 的直和分解： $V = V_1 \oplus V_2$ ，可以构造两个对应的投影变换 $\mathcal{P}$ 和 $\mathcal{Q}$ ：

Copy LaTeX

由直和分解的性质可知，上述方式给出了两个线性变换的严格定义。称 $\mathcal{P}$ 是沿着 $V_2$ 向 $V_1$ 的投影，称 $\mathcal{Q}$ 是沿着 $V_1$ 向 $V_2$ 的投影。

可以将这里的构造方式直接作为投影变换的定义，容易推出 $\mathcal{P}^2 = \mathcal{P}$ 和 $\mathcal{Q}^2 = \mathcal{Q}$ 。此时显然有 $\mathcal{P} + \mathcal{Q} = \mathcal{I}$ ，以及

Copy LaTeX

Note

补空间通常不唯一，例如 $V = V_1 \oplus V_2 = V_1 \oplus V_3$ ，但是这只能推出 $V_2$ 与 $V_3$ 同构， $\text{dim}(V_2) = \text{dim}(V_3)$ ，但是无法得到 $V_2 = V_3$ 。

正交投影 / 斜投影

如果 $H$ 是一个 Hilbert 空间，还可以进一步引入正交投影的定义：

Definition

称有界投影 $\mathcal{P}\in\mathcal{L}(H)$ 是一个正交投影(orthogonal projection)，如果像空间 $\text{Im}(\mathcal{P})$ 和核空间 $\text{Ker}(\mathcal{P})$ 相互正交

Copy LaTeX

即

Copy LaTeX

否则称 $\mathcal{P}$ 为斜投影(oblique projection)。

Remark

若 $M\subset H$ 是闭子空间，则有正交分解 $H=M\oplus M^\perp$ ，并存在到 $M$ 上的有界正交投影。若 $M$ 不是闭的，一般只能投影到 $\overline M$ ，不能把任意向量正交投影到 $M$ 本身。

对于前文中构造的投影变换对 $(\mathcal{P},\mathcal{Q})$ ， $\mathcal{P}$ 是正交投影/斜投影等价于 $\mathcal{Q}$ 是正交投影/斜投影。

Proposition

设 $\mathcal{P}\in\mathcal{L}(H)$ 且 $\mathcal{P}^2=\mathcal{P}$ 。则 $\mathcal{P}$ 是正交投影等价于 $\mathcal{P}$ 是自伴变换，在有限维实 Hilbert 空间中，选取标准正交基后，对应的矩阵表示 $P$ 是对称矩阵；复 Hilbert 空间中则是 Hermitian 矩阵。任意非正交基下的矩阵表示未必具有这种性质。

Proof

若 $\mathcal{P}$ 是正交投影，根据定义

Copy LaTeX

得到 $\mathcal{P}^* (\mathcal{I}-\mathcal{P}) = \mathcal{O}$ ，因此 $\mathcal{P}^* = \mathcal{P}^*\mathcal{P}$ 。对两边取伴随可得 $\mathcal{P}=\mathcal{P}^*\mathcal{P}$ ，于是 $\mathcal{P}=\mathcal{P}^*$ 。

反过来，若 $\mathcal{P}=\mathcal{P}^*$ ，则对任意 $x,y\in H$ ，

Copy LaTeX

因为 $(\mathcal{I}-\mathcal{P})\mathcal{P}=\mathcal{P}-\mathcal{P}^2=\mathcal{O}$ 。所以 $\text{Im}(\mathcal{P})\perp\text{Ker}(\mathcal{P})$ ，即 $\mathcal{P}$ 是正交投影。

从几何角度分析可知，正交投影作用于所有向量都会保持模长不增，如果向量正好位于像空间，则可以保持模长不变；斜投影作用于向量则无法保持不增关系，对于某些向量，斜投影后的向量模长会增长，如果向量正好位于像空间，则可以保持模长不变。因此，有界投影的算子范数满足：

若 $\mathcal{P}\ne\mathcal{O}$ ，则 $\|\mathcal{P}\|\ge 1$ ；
对于非零的有界投影：正交投影当且仅当 $\|\mathcal{P}\|=1$ ；斜投影当且仅当 $\|\mathcal{P}\|>1$ 。

有限维投影的矩阵表示

为了简化讨论，下面假设 $V$ 是一个有限维的实 Hilbert 空间， $\text{dim}(V) = n$ ，并固定一组标准正交基，将 $V$ 等距识别为带欧氏内积的 $\mathbb{R}^n$ 。此时投影变换 $\mathcal{P}$ 可以用幂等矩阵 $P \in \mathbb{R}^{n \times n}$ 表示。虽然在有限维情形下始终有

Copy LaTeX

但是正交投影的要求 $\text{Im}(\mathcal{P})\,\, \bot \,\,\text{Ker}(\mathcal{P})$ 并不是平凡的。

对于一个给定的投影变换 $\mathcal{P}$ ，考虑它的矩阵表示 $P$ ：不妨设投影变换 $\mathcal{P}$ 具有 $k$ 维的像空间 $\text{Im}(\mathcal{P})$ ，取它的一组基记作矩阵 $U$ ，

Copy LaTeX

取核空间的正交补空间 $(\text{Ker}(\mathcal{P}))^\bot$ 的一组基（维数为 $k$ ），记作矩阵 $W$ ，

Copy LaTeX

Note

$U$ 的几何含义为： $\text{span}(U) = \text{Im}(\mathcal{P}) = \text{Ker}(\mathcal{I} - \mathcal{P})$ ，即投影 $\mathcal{P}$ 作用在 $\text{span}(U)$ 保持不变

Copy LaTeX

$W$ 的几何含义为： $\text{span}(W) = (\text{Ker}(\mathcal{P}))^\bot= (\text{Im}(\mathcal{I}-\mathcal{P}))^\bot$ ，即投影 $\mathcal{P}$ 的误差与 $\text{span}(W)$ 正交

Copy LaTeX

Lemma

按照上述方式构造得到的 $U$ 和 $W$ 满足 $W^{\mathsf{T}} U \in \mathbb{R}^{k \times k}$ 可逆。

Proof

假设存在 $U x \in \text{Im}(\mathcal{P})$ ，使得 $W^{\mathsf{T}} U x = 0$ ，那么

Copy LaTeX

由于直和分解 $V = \text{Im}(\mathcal{P}) \oplus \text{Ker}(\mathcal{P})$ ，可以得到 $U x = 0$ ，因此 $x = 0$ 。

Remark

对于固定的投影 $\mathcal{P}$ ，显然 $U,W$ 的选取不唯一，甚至可以要求选择的基底满足 $W^{\mathsf{T}} U = I$ 。

Theorem

投影变换 $\mathcal{P}$ 的矩阵表示为

Copy LaTeX

其中列满秩矩阵 $U$ 的列空间为 $\text{Im}(\mathcal{P})$ ，

Copy LaTeX

列满秩矩阵 $W$ 的列空间为 $(\text{Ker}(\mathcal{P}))^\bot$ ，

Copy LaTeX

Proof

将 $x$ 分解

Copy LaTeX

那么 $x_1 = \mathcal{P} x \in \text{Im}(\mathcal{P})$ ，存在 $y$ 使得 $x_1 = U y$ ； $x_2 \in \text{Ker}(\mathcal{P})$ 满足正交性

Copy LaTeX

前面的引理保证了 $W^{\mathsf{T}} U$ 可逆，因此可以解出

Copy LaTeX

进而得到 $x_1$ 的表达式

Copy LaTeX

由 $x$ 的任意性可得 $\mathcal{P}$ 的矩阵表示为 $P = U(W^{\mathsf{T}} U)^{-1} W^{\mathsf{T}}$ 。

Remark

在无穷维可分 Hilbert 空间中，公式

Copy LaTeX

可以安全地理解为有限秩情形，其中 $U,W:\mathbb{F}^k\to H$ 。若 $k=\infty$ ，则 $W^*U$ 是无穷维算子，其逆的存在性和有界性都需要额外检查。

显然上述构造的矩阵是一个幂等矩阵：

Copy LaTeX

并且矩阵表示与基底的选取无关，例如取两个新的基底

Copy LaTeX

其中 $R_1,R_2 \in \mathbb{R}^{k \times k}$ 为可逆的变换，代入可得

Copy LaTeX

上述构造过程反过来也成立：

Theorem

任给两个列满秩的矩阵 $U \in \mathbb{R}^{n \times k}$ 和 $W \in \mathbb{R}^{n \times k}$ ，保证 $W^{\mathsf{T}} U$ 可逆，可以据此构造一个投影矩阵

Copy LaTeX

满足 $P$ 的像空间为 $\text{span}(U)$ ，核空间的正交补为 $\text{span}(W)$ 。

这个构造给出一般投影：当 $\text{span}(U)=\text{span}(W)$ 时为正交投影，否则为斜投影。

前面构造的是一般的投影变换所对应的矩阵表示，如果添加正交性条件 $\text{Im}(\mathcal{P})\,\, \bot \,\,\text{Ker}(\mathcal{P})$ ，即 $\text{Im}(\mathcal{P}) = (\text{Ker}(\mathcal{P}))^\bot$ ，此时必然存在可逆的变换 $R \in \mathbb{R}^{k \times k}$ ，使得 $W = U R$ ，代入化简得到

Copy LaTeX

这表明只需要提供 $U$ 就可以唯一确定对应的正交投影，有如下定理

Theorem

正交投影变换 $\mathcal{P}$ 的矩阵表示 $P$ 为

Copy LaTeX

其中列满秩矩阵 $U$ 的列空间为 $\text{Im}(\mathcal{P}) = (\text{Ker}(\mathcal{P}))^\bot$ ，

Copy LaTeX

上述构造过程反过来也成立：

Theorem

任给列满秩的矩阵 $U \in \mathbb{R}^{n \times k}$ ，可以据此构造一个正交投影矩阵

Copy LaTeX

满足 $P$ 的像空间和核空间的正交补均为 $\text{span}(U)$ 。如果 $U$ 是列向量单位正交的（ $U^{\mathsf{T}} U = I$ ），对应的正交投影矩阵就可以进一步化简为

Copy LaTeX

考虑一些最简单的情况：

Example

考虑只有一个列向量的情况： $U = [\alpha] \in \mathbb{R}^{n \times 1}$ ，可以据此构造正交投影 $\mathcal{P}$ ，对应的矩阵表示为

Copy LaTeX

几何含义为： $P x$ 就是 $x$ 在 $\alpha$ 方向的分量

Copy LaTeX

Example

考虑两个列向量的情况： $U = [\alpha] \in \mathbb{R}^{n \times 1}$ ， $W = [\beta] \in \mathbb{R}^{n \times 1}$ ，满足 $\alpha^{\mathsf{T}} \beta \neq 0$ 。可以据此构造投影 $\mathcal{P}$ ，对应的矩阵表示为

Copy LaTeX

几何含义为：

Copy LaTeX

当 $\alpha$ 与 $\beta$ 共线时，这是正交投影；不共线时才是斜投影。

斜投影的范数误差估计

对于给定的列满秩的矩阵 $U \in \mathbb{R}^{n \times k}$ ，考虑任意一个列满秩的矩阵 $W \in \mathbb{R}^{n \times k}$ ，满足 $W^{\mathsf{T}} U$ 可逆，可以定义向 $\text{span}(U)$ 的一般投影

Copy LaTeX

对于任意的 $b \in \mathbb{R}^{n}$ ，投影 $\mathcal{P}$ 可以给出 $b$ 在 $\text{span}(U)$ 的一个近似（记作 $\hat{b}$ ）

Copy LaTeX

但是显然最优近似是 $b$ 在 $\text{span}(U)$ 的正交投影（记作 $\hat{b}_*$ ）

Copy LaTeX

可以基于正交投影的误差 $\| b - \hat{b}_*\|$ 给出一般投影的误差估计 $\| b - \hat{b}\|$ ：对 $\hat{b}$ 进行分解

Copy LaTeX

这里利用了 $\mathcal{P}\hat{b}_* = \hat{b}_*$ ，因此

Copy LaTeX

误差可以拆分为意义明确的两部分：投影误差 $b - \hat{b}_*$ 和模型误差 $\mathcal{P}(b - \hat{b}_*)$ 。对误差的范数进行估计

Copy LaTeX

这里利用了对于非平凡的投影 $\mathcal{P}$ （排除 $\mathcal{I}$ 和 $\mathcal{O}$ ）都有 $\|\mathcal{I} - \mathcal{P}\| = \|\mathcal{P}\|$ 。因此，在固定列满秩矩阵 $U\in \mathbb{R}^{n \times k}$ 的前提下，列满秩矩阵 $W\in \mathbb{R}^{n \times k}$ 所对应投影的近似效果可以通过如下系数控制

Copy LaTeX

斜投影与插值

对于列满秩的矩阵 $U,W \in \mathbb{R}^{n \times k}$ ，满足 $W^{\mathsf{T}} U$ 可逆，可以定义向 $\text{span}(U)$ 的一般投影

Copy LaTeX

对于任意的 $b \in \mathbb{R}^{n}$ ，投影的误差 $b - \mathcal{P}b$ 与 $\text{span}(W)$ 正交，即

Copy LaTeX

如果特别地取 $W = [e_{i_1} \cdots e_{i_k}]$ （称为掩码矩阵），其中 $e_j$ 是仅有第 $j$ 分量为 $1$ 其余分量为 $0$ 的单位向量，显然 $W$ 列满秩要求 $\mathcal{I} = \{i_j\}$ 是一组互异的指标， $W^{\mathsf{T}} U$ 可逆的要求即 $U$ 的 $k \times k$ 子矩阵 $U(\mathcal{I},:)$ 是可逆的。注意到

Copy LaTeX

因此

Copy LaTeX

这表明

Copy LaTeX

即基于掩码矩阵 $W$ 构造的投影 $\mathcal{P}$ 具有插值性，但是只能在 $k$ 个分量上进行严格插值。

Remark

这个思路的具体应用就是 DEIM，因为 $ W^{\mathsf{T}} r$ 的计算量很小，为了保证投影的近似效果，可以采用贪心法选取索引。

Moore–Penrose 广义逆与最小二乘问题

对于任意矩阵 $A \in \mathbb{R}^{n \times m}$ ，都存在唯一的 Moore–Penrose 广义逆 $A^\dagger$ ，满足

Copy LaTeX

$A^\dagger$ 可以通过奇异值分解给出显式表达式

Copy LaTeX

如果 $A$ 是列满秩的，那么 $A^\dagger$ 的显式表达式为 $A^\dagger = (A^{\mathsf{T}} A)^{-1} A^{\mathsf{T}}$ 。

Remark

上述结论是有限维矩阵结论。在 Hilbert 空间中，Moore--Penrose 逆仍可定义，但它未必是有界算子。对于有界线性算子 $A:H_1\to H_2$ ， $A^\dagger$ 有界当且仅当 $\text{Ran}(A)$ 是闭的。

给定任意矩阵 $A \in \mathbb{R}^{n \times k}$ ，对于任意的 $b \in \mathbb{R}^{n}$ ， $A x = b$ 未必有解，此时考虑求解如下最小二乘问题

Copy LaTeX

最小二乘解 $x_*$ 满足 $A x_*$ 是空间 $\text{span}(A)$ 中对 $b$ 的最优近似，具体表达式为

Copy LaTeX

最小二乘解通常不是唯一的，其中范数最小的称为最小范数最小二乘解 $x_0$ ，显然 $x_0 = A^\dagger b$ 。若 $A$ 是列满秩的，那么可以证明 $I - A^\dagger A = 0$ ，从而最小范数最小二乘解 $x_0$ 就是唯一的最小二乘解。

Remark

在无穷维 Hilbert 空间中，最小二乘问题的解存在性依赖于逼近子空间是否闭。有限维子空间总是闭的，因此有限秩 Galerkin 或 DEIM 型近似没有这个问题；但若使用无限维子空间或一般算子值域，则必须检查闭值域条件。

对于任意矩阵 $\widetilde{U} \in \mathbb{R}^{n \times k_1}$ 和 $\widetilde{W} \in \mathbb{R}^{n \times k_2}$ （不要求列满秩，不要求 $k_1 = k_2$ ），都可以利用 Moore–Penrose 广义逆构造如下幂等矩阵

Copy LaTeX

这对应一个投影变换 $\mathcal{P}$ 。记 $A=\widetilde{W}^{\mathsf{T}}\widetilde{U}$ ，则

Copy LaTeX

但是一般不能把它理解为到整个 $\text{span}(\widetilde{U})$ 上、并沿着 $(\text{span}(\widetilde{W}))^\bot$ 的投影，而只能得到如下较弱的性质：

像空间 $\text{Im}(\mathcal{P})$ 是 $\text{span}(\widetilde{U})$ 的一个子空间；无法保证对于 $v \in \text{span}(\widetilde{U})$ ，都有 $\mathcal{P} v = v$ 。
$(\text{span}(\widetilde{W}))^\bot$ 是核空间 $\text{Ker}(\mathcal{P})$ 的一个子空间；无法保证误差 $v - \mathcal{P} v$ 与 $\text{span}(\widetilde{W})$ 正交。

线性方程组的子空间近似求解

考虑线性方程组的近似求解

Copy LaTeX

假设我们选取了合适的 $k$ 维子空间 $\mathcal{U} \subset \mathbb{R}^n$ （ $k \ll n$ ）进行近似求解，基底 $U \in \mathbb{R}^{n \times k}$ （ $U$ 列满秩），设近似解为

Copy LaTeX

代入后，需要近似满足超定系统

Copy LaTeX

对于这个超定方程组，可以要求余量 $r = f - A U \alpha$ 满足一定的约束，例如余量正交化，或者余量最小化。

先考虑余量正交化条件：选取一个新的 $k$ 维子空间 $\mathcal{W} \subset \mathbb{R}^n$ ，基底 $W \in \mathbb{R}^{n \times k}$ （ $W$ 列满秩），要求余量与 $\mathcal{W}$ 正交，即

Copy LaTeX

如果 $\mathcal{W}=\mathcal{U}$ ，称为 Galerkin 方法，否则称为 Petrov-Galerkin 方法。假设 $W^{\mathsf{T}} A U$ 可逆，那么可以解得

Copy LaTeX

记原问题的精确解为 $x_* = A^{-1} f$ ，两者的差

Copy LaTeX

核心就是对算子 $A^{-1}$ 的近似

Copy LaTeX

这里存在几个显著的难点：

即使问题保证 $A$ 可逆， $W^{\mathsf{T}} A U$ 也可能是不可逆的，这取决于 $U,W$ 的选取；一些特殊的情况可以保证，例如：
1. 因为 $A U$ 肯定是列满秩的，取 $W=AU$ 可以保证；
2. 如果 $A$ 实对称正定，取 $W=U$ 可以保证。
某些问题中的 $A$ 有特定结构，例如是稀疏的，但是 $U (W^{\mathsf{T}} A U)^{-1} W^{\mathsf{T}}$ 通常不是稀疏矩阵；
$U (W^{\mathsf{T}} A U)^{-1} W^{\mathsf{T}}$ 对 $A^{-1}$ 的逼近效果难以刻画。

然后考虑余量最小化条件：例如在 2-范数意义下

Copy LaTeX

定义凸泛函

Copy LaTeX

易知 $\varphi$ 的极值点 $\alpha$ 满足

Copy LaTeX

因此等价于在上述 Petrov–Galerkin 条件中取 $W = A U$ ，不一定对应斜投影。其它范数意义下的余量最小化通常不再等价于一个固定测试空间给出的线性 Petrov--Galerkin 条件；其最优性条件可能是非线性的，甚至是非光滑的。

具体应用上述思想，可以得到两大类方法：

如果 $U,W$ 的构造是取自 Krylov 子空间 $\mathcal{K}_k(A)$ ，对方程组进行迭代求解，在迭代过程中 $U,W$ 不断扩充，那么就对应于 Krylov 迭代方法；
如果 $U,W$ 的构造是取自于已知的数据快照，那么就对应于时间无关问题的线性方程组问题的降阶方法，求解效果取决于快照数据。

Galerkin / Petrov-Galerkin 方法不是单纯的投影，而是对余量的投影约束条件，自然给出的是解算子 $A^{-1}$ 的低秩近似：

Copy LaTeX

若反过来希望用类似形式近似算子 $A$ 本身，则需要另外构造：对于可逆矩阵 $A \in \mathbb{R}^{n \times n}$ ，任给两个列满秩的矩阵 $U \in \mathbb{R}^{n \times k}$ 和 $W \in \mathbb{R}^{n \times k}$ ，在 $W^{\mathsf{T}} A^{-1} U$ 可逆时，可以写出投影形式的近似

Copy LaTeX

但这已经是另一个投影近似问题。