Gram-Schmidt过程

Gram-Schmidt过程 (Gram-Schmidt Process)

Gram-Schmidt过程是由丹麦数学家约尔根·格拉姆（Jørgen Gram，1850–1916）和德国数学家埃哈德·施密特（Erhard Schmidt，1876–1959）分别于1883年和1907年独立提出的一种线性代数基本算法，用于将有限维内积空间中的一组线性无关向量转化为与之张成相同子空间的标准正交基（orthonormal basis）。格拉姆最早在其关于最小二乘法的论文中隐含地使用了该正交化思想，而施密特则在其关于积分方程的研究中给出了明确的递推表述，使其成为泛函分析和数值线性代数的基石之一。该过程不仅是理论上的构造性工具——它从本质上确证了任何有限维内积空间均拥有标准正交基——更是QR分解、最小二乘法和计算数学等诸多应用领域的核心算法基础。

几何直觉：投影与正交化

Gram-Schmidt过程的几何思想极为直观：给定一组线性无关向量 $\{v_1, v_2, \ldots, v_n\}$，依次将每个向量 $v_k$ 减去其在已构造的正交向量 $\{u_1, \ldots, u_{k-1}\}$ 上的正交投影之和，从而得到与之前所有向量正交的新向量 $u_k$，最后再做单位化处理。简言之，每一步都"剥离"掉当前向量中与已有正交基分量重合的部分，保留与之垂直的剩余分量——这正是投影定理（Projection Theorem）在有限维空间的直接应用。

以一维和二维为例：取第一个向量直接单位化，$e_1 = v_1 / \|v_1\|$。对于第二个向量，计算 $v_2$ 在 $e_1$ 方向上的投影标量 $\langle v_2, e_1 \rangle$，将其从 $v_2$ 中减去得到残差 $u_2 = v_2 - \langle v_2, e_1 \rangle e_1$。由内积的双线性性可验证 $\langle u_2, e_1 \rangle = \langle v_2, e_1 \rangle - \langle v_2, e_1 \rangle \langle e_1, e_1 \rangle = 0$，故残差与 $e_1$ 正交，单位化即得 $e_2$。在三维空间中，$v_3$ 需同时减去在 $e_1$ 和 $e_2$ 上的投影，以此类推，高维情形完全类似。

形式化算法

设 $V$ 是装备内积 $\langle \cdot, \cdot \rangle$ 的内积空间（实数域或复数域），$\{v_1, v_2, \ldots, v_n\}$ 为 $V$ 中一组线性无关向量。经典Gram-Schmidt过程（Classical Gram-Schmidt, CGS）按如下递推构造正交向量组 $\{u_1, \ldots, u_n\}$ 和标准正交向量组 $\{e_1, \ldots, e_n\}$：

步骤 1（初始化）：

步骤 k（$k = 2, 3, \ldots, n$）：

其中 $\langle v_k, e_j \rangle$ 是 $v_k$ 在已得标准正交方向 $e_j$ 上的投影系数（对实内积空间即为标量投影），$\sum_{j=1}^{k-1} \langle v_k, e_j \rangle e_j$ 为 $v_k$ 在子空间 $\operatorname{span}\{e_1, \ldots, e_{k-1}\}$ 上的正交投影。归一化因子 $\|u_k\| = \sqrt{\langle u_k, u_k \rangle}$ 保证 $e_k$ 为单位向量。由于 $\{v_1, \ldots, v_n\}$ 线性无关，每一步均有 $u_k \neq 0$，故分母不为零，算法始终可以进行直至输出完整的标准正交基。

输出结果 $\{e_1, e_2, \ldots, e_n\}$ 满足两条核心性质：其一，标准正交性，即 $\langle e_i, e_j \rangle = \delta_{ij}$（Kronecker delta）；其二，张成保持性，即对任意 $k = 1, \ldots, n$，均有 $\operatorname{span}\{e_1, \ldots, e_k\} = \operatorname{span}\{v_1, \ldots, v_k\}$。第二条性质意味着该过程在逐步构造正交基时，前 $k$ 个正交向量始终与原始前 $k$ 个向量张成同一子空间，这在理论和算法分析中至关重要。

与QR分解的关系

Gram-Schmidt过程与矩阵的QR分解本质上是同一个数学事实的两种等价表达。将线性无关向量按列排成 $m \times n$ 矩阵 $A = [v_1 \; v_2 \; \cdots \; v_n]$，则存在具有标准正交列的矩阵 $Q = [e_1 \; e_2 \; \cdots \; e_n]$（满足 $Q^T Q = I_n$）和 $n \times n$ 上三角矩阵 $R$，使得：

其中 $R$ 的元素 $r_{ij}$ 直接由Gram-Schmidt过程中的投影系数和范数给出：

若 $A$ 为方阵且满秩，则 $Q$ 为正交矩阵（$Q^{-1} = Q^T$），此时QR分解是唯一的（要求 $R$ 的对角线元素为正）。这一分解将矩阵求逆、求解线性方程组等问题转化为三角系统的回代，兼具理论优美性与计算实用性。

修正Gram-Schmidt与数值稳定性

经典Gram-Schmidt过程在浮点运算环境下面临严重的数值稳定性问题：当输入向量接近线性相关时，舍入误差的累积导致输出的 $e_k$ 迅速丧失正交性。修正Gram-Schmidt过程（Modified Gram-Schmidt, MGS）通过重组计算顺序克服了这一缺陷。其核心差异在于：CGS对每个 $v_k$ 一次性减去所有 $k-1$ 个投影项；而MGS在每产生一个新的正交方向 $e_j$ 后，立即从所有尚未处理的剩余向量 $v_{j+1}, \ldots, v_n$ 中减掉该方向上的投影分量，将投影运算与向量更新交错进行。数学上CGS与MGS在精确算术下等价，但在有限精度算术下，MGS的正交性误差仅以条件数的线性函数增长，远优于CGS的条件数平方级增长。更稳健的替代方案还包括基于Householder反射和Givens旋转的QR分解方法，其正交性保持能力又优于MGS，是LAPACK等标准数值库的首选实现。

存在性、唯一性与推广

在任意有限维内积空间中，给定任何一组线性无关向量，Gram-Schmidt过程都保证了标准正交基的构造性存在。这从本质上确证了：任何有限维内积空间都拥有标准正交基，且任何这样的基都可以通过该过程从任意起点扩充获得。值得注意的是，输出结果并非唯一——它依赖于输入向量的排列顺序。对同一组向量做重排后执行Gram-Schmidt，通常得到不同的标准正交基（对应于QR分解中不同的置换矩阵）。若要求标准正交基具有唯一性，需额外施加条件，例如要求与给定基之间的过渡矩阵为主对角线元素均为正的三角矩阵。

在函数空间中，Gram-Schmidt过程同样可用于从单项式基 $\{1, x, x^2, \ldots\}$ 出发，构造在特定加权内积 $\langle f, g \rangle_w = \int_a^b f(x) g(x) w(x) \, dx$ 意义下的正交多项式。所有经典正交多项式——包括勒让德多项式（$w(x)=1$）、切比雪夫多项式（$w(x)=1/\sqrt{1-x^2}$）、拉盖尔多项式（$w(x)=e^{-x}$）和埃尔米特多项式（$w(x)=e^{-x^2}$）——均可视为对单项式基在不同权函数内积下执行Gram-Schmidt过程的直接结果。这为特殊函数论提供了统一的构造视角，也解释了正交多项式满足三项递推关系的深层代数根源。

应用概览

Gram-Schmidt过程的应用遍及纯数学与计算科学的多个分支。在最小二乘法中，对于超定方程组 $Ax \approx b$，其正规方程 $A^T A x = A^T b$ 的条件数为原矩阵条件数的平方，直接求解可能导致精度严重损失；而通过QR分解将问题转化为 $Rx = Q^T b$ 后，仅需回代上三角系统，数值稳定性显著改善，QR分解本身便由Gram-Schmidt或等价方法实现。在特征值计算中，QR算法（Francis算法，1961）是求解一般矩阵全部特征值的事实标准方法，其每一迭代步都依赖QR分解，该算法至今仍是MATLAB、NumPy等数值环境中\texttt{eig}函数的底层引擎。在信号处理中，将非正交基转换为正交基是匹配追踪和正交匹配追踪等稀疏表示算法的标准化预处理步骤。在量子力学中，希尔伯特空间中的态矢量正交化直接依赖Gram-Schmidt或其等价过程，例如在构造正交归一的Wannier函数或处理简并微扰论中的零阶近似时。在机器学习的主成分分析（PCA）和特征工程中，Gram-Schmidt思想也以去相关和正交初始化的变体形式出现，确保特征之间线性独立，避免多重共线性对模型训练的干扰。