格拉姆–施密特过程

格拉姆–施密特过程是线性代数中的一种算法，用于从有序的线性无关向量组构造标准正交基。它依次减去每个向量沿先前已构造方向的分量，再将剩余向量归一化。所得向量与原向量组张成同一子空间。将这一过程应用于矩阵的列向量，可得到QR分解，从而将其几何解释与计算方法联系起来。(github.com)

数学背景

设 $v_1,\ldots,v_n$ 是实数域或复数域上一个配备了内积的向量空间中的向量。两个向量正交，是指它们的内积为零；标准正交还要求每个向量的长度为一。格拉姆–施密特过程使用由内积诱导的范数：

\|v\|=\sqrt{\langle v,v\rangle}.

这一构造适用于抽象的内积空间，而不限于坐标向量：多项式空间和适当的函数空间也可以使用这一过程。(people.tamu.edu)

通常假定输入向量组线性无关。如果输入是有限维空间的一组基，输出就是该空间的一组标准正交基。更一般地，输出是输入向量组的线性包的一组基，而这个线性包可能是所在空间的一个真线性子空间。(github.com)

经典构造

约定 $\langle x,y\rangle$ 对第一个变量共轭线性，对第二个变量线性。令

u_1=v_1,\qquad q_1=\frac{u_1}{\|u_1\|}.

对于 $k=2,\ldots,n$ ，定义

u_k=v_k-\sum_{j=1}^{k-1}q_j\langle q_j,v_k\rangle, \qquad q_k=\frac{u_k}{\|u_k\|}.

求和中的每一项都是 $v_k$ 在 $q_j$ 方向上的正交投影。减去这些投影的和，剩下的就是垂直于所有先前已构造方向的分量。如果省略归一化步骤，得到的就是两两正交的向量 $u_k$ ，而不是单位向量 $q_k$ 。(archive.nptel.ac.in)

这一构造的正确性可直接由内积的性质推出。假设先前的 $q_j$ 已构成标准正交向量组，则对于每个 $i<k$ ，都有

\langle q_i,u_k\rangle =\langle q_i,v_k\rangle -\sum_{j<k}\langle q_i,q_j\rangle \langle q_j,v_k\rangle =0.

此外，每个新向量都是前 $k$ 个输入向量的线性组合，而定义式又将 $v_k$ 表示为这些新向量的线性组合。因此，

\operatorname{span}(q_1,\ldots,q_k) =\operatorname{span}(v_1,\ldots,v_k).

线性无关性保证 $u_k\ne0$ ，因而可以进行归一化。(archive.nptel.ac.in)

如果输入向量组线性相关，残差为零就表明当前向量已经属于此前保留向量的线性包，因此可以将其舍弃。输出通常取决于输入顺序，但最终张成的子空间不受顺序影响。(people.tamu.edu)

计算示例

考虑欧几里得空间 $\mathbb R^3$ 中的向量

v_1=(1,1,0),\qquad v_2=(1,0,1).

采用标准点积，第一个归一化向量为

q_1=\frac{(1,1,0)}{\sqrt2}.

第二个残差向量为

u_2=v_2-q_1\langle q_1,v_2\rangle =(1,0,1)-\tfrac12(1,1,0) =(\tfrac12,-\tfrac12,1).

因此，

q_2=\frac{(1,-1,2)}{\sqrt6}.

直接计算可得 $\langle q_1,q_2\rangle=0$ ，且两个向量的范数均为一。这个例子展示了上述一般构造： $q_1,q_2$ 构成两个输入向量所张成平面的一组标准正交基。(archive.nptel.ac.in)

矩阵形式与最小二乘法

将 $n$ 个线性无关向量作为一个 $m\times n$ 矩阵 $A$ 的列，其中 $m\ge n$ 。格拉姆–施密特过程给出

A=QR,

其中 $Q=[q_1\ \cdots\ q_n]$ ， $R$ 为上三角矩阵。其元素为

r_{jk}=\langle q_j,v_k\rangle\quad(j<k), \qquad r_{kk}=\|u_k\|>0.

关系式 $Q^*Q=I_n$ 中， $Q^*$ 表示共轭转置， $I_n$ 表示单位矩阵。对于实矩阵， $Q^*=Q^T$ 。当 $m=n$ 时，实数情形下的 $Q$ 是正交矩阵，复数情形下则是酉矩阵。(github.com)

对于普通最小二乘法，在精确算术下，最小化 $\|Ax-b\|_2$ 可归结为求解

Rx=Q^*b.

拟合向量为 $QQ^*b$ 。这种方法不需要显式构造正规方程 $A^*Ax=A^*b$ ，这一差别在数值计算中十分重要。(ocw.mit.edu)

修正格拉姆–施密特过程与数值表现

在浮点运算中，经典格拉姆–施密特过程可能丧失正交性，尤其是在输入向量接近线性相关时。修正格拉姆–施密特过程改变了运算顺序：先令 $w=v_k$ ，然后依次计算

r_{jk}=\langle q_j,w\rangle,\qquad w\leftarrow w-q_jr_{jk},

最后将 $w$ 归一化。因此，每次投影使用的都是更新后的残差，而不是原始向量。这两个版本在精确算术下等价，但其数值稳定性有所不同。(ocw.mit.edu)

修正格拉姆–施密特过程通常能更好地保持正交性，但仍可能出现严重的正交性损失。重正交化通过重复减去投影的步骤，进一步消除沿先前向量方向残留的分量。这两个基本版本都需要 $O(mn^2)$ 次算术运算。豪斯霍尔德变换提供了另一种构造 QR 分解的方法，在浮点计算中能更好地保持正交性。(netlib.org)

函数空间与迭代方法

采用内积

\langle f,g\rangle=\int_{-1}^{1}\overline{f(x)}g(x)\,dx,

对 $1,x,x^2,\ldots$ 应用格拉姆–施密特过程，可得到正交多项式。按惯用方式缩放后，它们就是勒让德多项式，前几项为 $1$ 、 $x$ 和 $(3x^2-1)/2$ 。勒让德多项式的惯用归一化方式与单位范数归一化不同。在可分的希尔伯特空间中，对线性包稠密的可数向量组进行正交化，可以得到闭线性包意义下的一组标准正交基。(people.tamu.edu)

在数值线性代数中，格拉姆–施密特过程也用于构造克雷洛夫子空间的基。对连续施加矩阵作用所生成的向量依次进行正交化，是阿诺尔迪迭代的基础；该迭代提供了广义最小残差法求解线性方程组时所使用的标准正交基。(netlib.org)