Logo

格拉姆-施密特正交化

1. 基本概述

在向量空间中，基向量通常不是正交的。若直接使用不正交的基进行数学运算（如解方程组、最小二乘法等），可能会引入额外的复杂性，并导致数值计算不稳定。为了解决这一问题，格拉姆-施密特 (Gram-Schmidt) ~(\textbf{Gram-Schmidt})~正交化提供了一种简单的算法，此方法可以将非正交基向量转化为正交基。下面的动画演示了 R3 ~\mathbb{R^3}~中的一组非正交基转化为正交基的过程：
下面我们通过示例来展示通过施密特方法将非正交基转化为正交基的过程。给定 R3 ~\mathbb{R^3}~子空间 W ~W~中的两个非正交的基向量：
 x1=[360],x2=[122]~\mathbf{x}_1 = \begin{bmatrix}3 \\ 6 \\ 0\end{bmatrix},\quad \mathbf{x}_2 = \begin{bmatrix}1 \\ 2 \\ 2\end{bmatrix}
我们来构造一个正交基 {v1,v2} ~\{\mathbf{v}_1,\mathbf{v}_2\}~来表示子空间 W=Span{x1,x2} ~W = \text{Span} \{\mathbf{x}_1,\mathbf{x}_2\}~。方法也很简单，首先，任选一个向量 x1 ~\mathbf{x}_1~作为第一个正交向量 v1 ~\mathbf{v}_1~。接着，对于下一个向量 x2 ~\mathbf{x}_2~，计算它在 v1 ~\mathbf{v}_1~上的投影，并从 x2 ~\mathbf{x}_2~中减去这个投影，得到新的正交向量 v2 ~\mathbf{v}_2~。下面的动画演示了这个过程：

开通会员解锁全部动画

2. 具体步骤

在下面的示例中，我们将使用施密特正交化过程，将一组 R4 ~\mathbb{R^4}~中的线性无关向量转换为正交基，并详细展示每个步骤。给定如下向量：
x1=[1111],x2=[0111],x3=[0011]\mathbf{x_1} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{x_2} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{x_3} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix}
这些向量是线性无关的，可以作为 R4 ~\mathbb{R^4}~中三维子空间 W=Span{x1,x2,x3}~W = \text{Span}\{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3\}的基。以下是正交化的具体步骤：

可以直接选择 v1=x1 ~\mathbf{v}_1 = \mathbf{x}_1~：
v1=[1111]\mathbf{v}_1 = \begin{bmatrix}1 \\ 1 \\ 1\\ 1 \end{bmatrix}
此时， v1 ~\mathbf{v}_1~张成的子空间 W1=Span{v1} ~W_1 = \text{Span}\{\mathbf{v}_1\}~。

我们要从 x2 ~\mathbf{x}_2~中减去它在 v1 ~\mathbf{v}_1~上的投影，得到一个与 v1 ~\mathbf{v}_1~正交的向量 v2 ~\mathbf{v}_2~。 首先，计算 x2 ~\mathbf{x}_2~在 v1 ~\mathbf{v}_1~上的投影：
projv1x2=x2⋅v1v1⋅v1v1\text{proj}_{\mathbf{v_1}} \mathbf{x_2} = \frac{\mathbf{x_2} \cdot \mathbf{v_1}}{\mathbf{v_1} \cdot \mathbf{v_1}} \mathbf{v_1}
计算内积 x2⋅v1 ~\mathbf{x}_2\cdot \mathbf{v}_1~和 v1⋅v1 ~\mathbf{v}_1\cdot \mathbf{v}_1~：
x2⋅v1=0×1+1×1+1×1+1×1+1×1=3v1⋅v1=1×1+1×1+1×1+1×1+1×1=4\begin{align*}\mathbf{x_2} \cdot \mathbf{v_1} &= 0 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 = 3 \\ \mathbf{v_1} \cdot \mathbf{v_1} &= 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 + 1 \times 1 = 4\end{align*}
因此，投影是：
projv1x2=3/4[1111]=[3/43/43/43/4]\text{proj}_{\mathbf{v_1}} \mathbf{x_2} = 3/4 \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 3/4 \\ 3/4 \\ 3/4 \\ 3/4 \end{bmatrix}
接下来，计算v2=x2−projv1x2\mathbf{v}_2 = \mathbf{x}_2 - \text{proj}_{\mathbf{v}_1} \mathbf{x}_2：
v2=[0111]−[3/43/43/43/4]=[−3/41/41/41/4]\mathbf{v_2} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} - \begin{bmatrix} 3/4 \\ 3/4 \\ 3/4 \\ 3/4 \end{bmatrix} = \begin{bmatrix} -3/4 \\ 1/4 \\ 1/4 \\ 1/4 \end{bmatrix}

为了简化计算，我们可以选择将 v2 ~\mathbf{v}_2~乘以 4 ~4~：
v2′=4×v2=[−3111]\mathbf{v_2'} = 4 \times \mathbf{v_2} = \begin{bmatrix} -3 \\ 1 \\ 1 \\ 1 \end{bmatrix}

现在，我们需要从 x3 ~\mathbf{x}_3~中减去它在 v1 ~\mathbf{v}_1~和 v2 ~\mathbf{v}_2~上的投影，得到一个与 v1 ~\mathbf{v}_1~ 和 v2 ~\mathbf{v}_2~正交的向量 v3 ~\mathbf{v}_3~。首先，计算 x3 ~\mathbf{x}_3~在 v1 ~\mathbf{v}_1~和 v2′ ~\mathbf{v_2'}~上的投影，下面是 x3 ~\mathbf{x}_3~在 v1 ~\mathbf{v}_1~上的投影：
projv1x3=x3⋅v1v1⋅v1v1=[1/21/21/21/2]\text{proj}_{\mathbf{v_1}} \mathbf{x_3} = \frac{\mathbf{x_3} \cdot \mathbf{v_1}}{\mathbf{v_1} \cdot \mathbf{v_1}} \mathbf{v_1} =\begin{bmatrix}1/2 \\ 1/2 \\ 1/2 \\ 1/2 \end{bmatrix}
下面是 x3 ~\mathbf{x}_3~在 v2′ ~\mathbf{v_2'}~上的投影：
projv2′x3=x3⋅v2′v2′⋅v2′v2′=[−6/112/112/112/11]\text{proj}_{\mathbf{v_2'}} \mathbf{x_3} = \frac{\mathbf{x_3} \cdot \mathbf{v_2'}}{\mathbf{v_2'} \cdot \mathbf{v_2'}} \mathbf{v_2'} =\begin{bmatrix}-6/11 \\ 2/11 \\ 2/11 \\ 2/11\end{bmatrix}
接下来，从 x3 ~\mathbf{x}_3~中减去这两个投影，得到 x3 ~\mathbf{x}_3~：
v3=x3−projv1x3−projv2′x3=[−2/31/31/31/3]\mathbf{v_3} = \mathbf{x_3} - \text{proj}_{\mathbf{v_1}} \mathbf{x_3} - \text{proj}_{\mathbf{v_2'}} \mathbf{x_3} =\begin{bmatrix}-2/3 \\ 1/3 \\ 1/3 \\ 1/3\end{bmatrix}
最终得到了三个正交向量 v1,v2,v3 ~\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3~：
v1=[1111],v2′=[−3111],v3=[−2/31/31/31/3]\mathbf{v_1} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{v_2'} = \begin{bmatrix} -3 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{v_3} = \begin{bmatrix} -2/3 \\ 1/3 \\ 1/3 \\ 1/3 \end{bmatrix}

3. 定理及推导过程

施密特正交化的过程可由以下定理给出：

  1. 基础步骤 (k=1) ~(k=1)~：

    • 当 k=1 ~k=1~时，设置 v1=x1 ~\mathbf{v}_1=\mathbf{x}_1~，显然 W1=Span{v1}=Span{x1} ~W_1 = \text{Span}\{\mathbf{v}_1\}=\text{Span}\{\mathbf{x}_1\}~，因此 v1 ~\mathbf{v}_1~作为 W1 ~W_1~的唯一向量，自然属于 W1 ~W_1~的正交基。

  2. 归纳假设：

    • 假设对于某个 k<p ~k\lt p~，我们已经构造了正交基 {v1,v2,⋯ ,vk} ~\{\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_k\}~，并且它们是子空间 Wk={x1,x2,⋯ ,xk} ~W_k=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_k\}~的正交基。

  3. 归纳步骤：

    • 需要证明对于 k+1 ~k+1~，构造的向量vk+1=xk+1−projWkxk+1\mathbf{v}_{k+1} = \mathbf{x}_{k+1} - \text{proj}_{W_k} \mathbf{x}_{k+1}也是 Wk+1=Span{x1,⋯ ,xk+1} ~W_{k+1}=\text{Span}\{\mathbf{x}_1,\cdots,\mathbf{x}_{k+1}\}~的正交基。

    • 构造 vk+1 ~\mathbf{v}_{k+1}~：
      vk+1=xk+1−projWkxk+1\mathbf{v_{k+1}} = \mathbf{x_{k+1}} - \text{proj}_{W_k} \mathbf{x_{k+1}}
      其中， projWkxk+1 ~\text{proj}_{W_k} \mathbf{x}_{k+1}~代表的是 xk+1 ~\mathbf{x}_{k+1}~在 Wk ~W_k~上的投影。根据正交投影的定义，它可以表示为：
      projWkxk+1=∑i=1kxk+1⋅vivi⋅vivi\text{proj}_{W_k} \mathbf{x}_{k+1} = \sum_{i=1}^{k} \frac{\mathbf{x}_{k+1} \cdot \mathbf{v}_i}{\mathbf{v}_i \cdot \mathbf{v}_i} \mathbf{v}_i
      这里的 vi ~\mathbf{v}_i~是 Wk ~W_k~中的正交基向量， xk+1 ~\mathbf{x}_{k+1}~在 Wk ~W_k~上的投影等于在各分量 vi ~\mathbf{v}_i~上的投影之和。
    • 我们考虑 vk+1 ~\mathbf{v}_{k+1}~与 Wk ~W_k~中任意一个向量 vi ~\mathbf{v}_i~的点积：
      vk+1⋅vi=(xk+1−projWkxk+1)⋅vi\mathbf{v}_{k+1} \cdot \mathbf{v}_i = (\mathbf{x}_{k+1} - \text{proj}_{W_k} \mathbf{x}_{k+1}) \cdot \mathbf{v}_i
      将 projw+1xk+1 ~\text{proj}_{w+1} \mathbf{x}_{k+1}~展开：
      vk+1⋅vi=xk+1⋅vi−(∑j=1kxk+1⋅vjvj⋅vjvj)⋅vi\mathbf{v}_{k+1} \cdot \mathbf{v}_i = \mathbf{x}_{k+1} \cdot \mathbf{v}_i - \left( \sum_{j=1}^{k} \frac{\mathbf{x}_{k+1} \cdot \mathbf{v}_j}{\mathbf{v}_j \cdot \mathbf{v}_j} \mathbf{v}_j \right) \cdot \mathbf{v}_i
      由于 {v1,⋯ ,vk} ~\{\mathbf{v}_1,\cdots,\mathbf{v}_k\}~是正交基，因此 vj⋅vi=0  (i≠j) ~\mathbf{v}_j\cdot \mathbf{v}_i = 0\,~(i\neq j)~而 vi⋅vi≠0 ~\mathbf{v}_i\cdot \mathbf{v}_i\neq 0~，所以只有当 j=i ~j=i~时，第二项非零：
      vk+1⋅vi=xk+1⋅vi−xk+1⋅vivi⋅vivi⋅vi\mathbf{v}_{k+1} \cdot \mathbf{v}_i = \mathbf{x}_{k+1} \cdot \mathbf{v}_i - \frac{\mathbf{x}_{k+1} \cdot \mathbf{v}_i}{\mathbf{v}_i \cdot \mathbf{v}_i} \mathbf{v}_i \cdot \mathbf{v}_i
      这两个项相互抵消，得到：
      vk+1⋅vi=0\mathbf{v}_{k+1}\cdot \mathbf{v}_i = 0
      因此， vk+1 ~\mathbf{v}_{k+1}~与 Wk ~W_k~中的每一个向量 vi ~\mathbf{v}_i~都正交，且vk+1≠0\mathbf{v}_{k+1} \neq 0，所以 {v1,v2,⋯ ,vk+1} ~\{\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_{k+1}\}~是 Wk+1 ~W_{k+1}~的正交基。
  4. 归纳终止：

    • 当 k+1=p ~k+1 = p~时，归纳过程终止，证明完成。

4. 构建标准正交基

把正交基进一步标准化，使得每个基向量的模长为 1 ~1~，就得到了标准正交基 (Orthonormal Bases) ~(\textbf{Orthonormal Bases})~，标准正交基可以进一步简化计算。在施密特正交化的步骤中，对每次得到的正交向量 vi ~\mathbf{v}_i~进行标准化处理即可得到标准正交基。对向量进行标准化的公式为：
u=v∥v∥\mathbf{u} = \frac{\mathbf{v}}{\|\mathbf{v}\|}
对于下面两个正交向量：
v1=[360],v2=[002]\mathbf{v}_1 = \begin{bmatrix}3 \\ 6 \\ 0\end{bmatrix},\mathbf{v}_2 = \begin{bmatrix}0 \\ 0 \\ 2\end{bmatrix}
进行标准化后：
u1=v132+62+02=[1/52/50],u2=v202+02+22=[001]\mathbf{u}_1 = \frac{\mathbf{v}_1}{\sqrt{3^2 + 6^2 + 0^2}} = \begin{bmatrix}1/\sqrt{5} \\ 2/\sqrt{5} \\ 0 \end{bmatrix},\quad \mathbf{u}_2 = \frac{\mathbf{v}_2}{\sqrt{0^2 + 0^2 + 2^2}} = \begin{bmatrix}0 \\ 0 \\ 1\end{bmatrix}

5. QR 矩阵分解

QR \mathbf{Q}\mathbf{R}~分解是一种将矩阵分解为一个正交矩阵 Q ~\mathbf{Q}~和一个上三角矩阵 R ~\mathbf{R}~的方法，它广泛应用于最小二乘问题、特征值计算和解线性方程组等场景。与 LU ~\mathbf{L}\mathbf{U}~分解相比， QR ~\mathbf{Q}\mathbf{R}~分解不仅适用于方阵，还能应用于任意矩阵。而施密特正交化方法为 QR ~\mathbf{Q}\mathbf{R}~分解提供了基础。通过施密特正交化，我们可以将矩阵 A ~\mathbf{A}~的列空间转换为标准正交基，从而实现了 QR ~\mathbf{Q}\mathbf{R}~ 分解。有如下定理：

  1. 构造标准正交基

    • 令 A ~\mathbf{A}~的列向量 {x1,x2,⋯ ,xn} ~\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\}~构成 Col(A) ~\text{Col}(\mathbf{A})~的基。根据定理 11 ~11~，可以通过施密特正交化构造一个标准正交基 {u1,u2,⋯ ,un} ~\{\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_n\}~来表示 Col(A) ~\text{Col}(\mathbf{A})~。

  2. 构造矩阵 Q ~\mathbf{Q}~
    • 定义矩阵 Q ~\mathbf{Q}~为：
      Q=[u1u2⋯un]\mathbf{Q} = \begin{bmatrix}\mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_n \end{bmatrix}
      其中 u1,u2,⋯ ,un ~\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_n~是通过拉姆-施密特正交化得到的标准正交基。

  3. 表示 xk ~\mathbf{x}_k~为正交基的线性组合：

    • 对于每个 k=1,⋯ ,n ~k=1,\cdots,n~，xk \mathbf{x}_k~可以表示为 {x1,x2,⋯ ,xk} ~\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_k\}~的线性组合。由于 xk ~\mathbf{x}_k~在 Span{x1,⋯ ,xk} ~\text{Span}\{\mathbf{x}_1,\cdots,\mathbf{x}_k\}~中，存在常数 r1k,r2k,⋯ ,rkk ~r_{1k},r_{2k},\cdots,r_{kk}~，使得：
      xk=r1ku1+⋯+rkkuk+0uk+1+⋯+0un{x_k = r_{1k} \mathbf{u}_1 + \cdots + r_{kk} \mathbf{u}_k + 0 \mathbf{u}_{k+1} + \cdots + 0 \mathbf{u}_n}
      可以将这些系数提取成一个列向量，对于 xk ~\mathbf{x}_k~可以表示为：
      xk=Qrk=[u1 u2 … un][r1kr2k⋮rkk0⋮0]\mathbf{x}_k = \mathbf{Q}\mathbf{r}_k = \begin{bmatrix} \mathbf{u}_1 \ \mathbf{u}_2 \ \dots \ \mathbf{u}_n \end{bmatrix} \begin{bmatrix} r_{1k} \\ r_{2k} \\ \vdots \\ r_{kk} \\ 0 \\ \vdots \\ 0 \end{bmatrix}

  4. 构造 QR ~\mathbf{Q}\mathbf{R}~

    • 对于所有 k=1,⋯ ,n ~k=1,\cdots,n~，我们可以定义：
      R=[r1r2⋯rn]\mathbf{R} = \begin{bmatrix}\mathbf{r}_1 & \mathbf{r}_2 & \cdots & \mathbf{r}_n \end{bmatrix}
      那么矩阵 A ~\mathbf{A}~可以表示为：
      A=[x1x2⋯xn]=[Qr1Qr2⋯Qrn]=QR\mathbf{A} = \begin{bmatrix} \mathbf{x}_1 & \mathbf{x}_2 & \cdots \mathbf{x}_n \end{bmatrix} = \begin{bmatrix} \mathbf{Q}\mathbf{r}_1 & \mathbf{Q}\mathbf{r}_2 & \cdots & \mathbf{Q}\mathbf{r}_n \end{bmatrix} = \mathbf{Q}\mathbf{R}
    • 把 QR ~\mathbf{Q}\mathbf{R}~展开更为清晰：
      A=[x1x2⋯xn]=[u1u2⋯un][r11r12r13…r1n0r22r23…r2n00r33…r3n⋮⋮⋮⋱⋮000…rnn]\mathbf{A} = \begin{bmatrix} \mathbf{x}_1 & \mathbf{x}_2 & \cdots \mathbf{x}_n \end{bmatrix} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots \mathbf{u}_n \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & r_{13} & \dots & r_{1n} \\ 0 & r_{22} & r_{23} & \dots & r_{2n} \\ 0 & 0 & r_{33} & \dots & r_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & r_{nn} \end{bmatrix}
由于 Q ~\mathbf{Q}~是正交矩阵，根据定理 6 QTQ=I ~\mathbf{Q}^T\mathbf{Q} = \mathbf{I}~，因此有如下推导：
QTA=QT(QR)=IR=R\mathbf{Q}^T \mathbf{A} = \mathbf{Q}^T (\mathbf{Q}\mathbf{R}) = \mathbf{I} \mathbf{R} = \mathbf{R}
矩阵 R ~\mathbf{R}~可以通过这种方式计算得到。接下来，通过一个示例来展示如何对矩阵 A ~\mathbf{A}~进行QR\mathbf{Q}\mathbf{R}分解。给定 A ~\mathbf{A}~：
A=[100110111111]\mathbf{A} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}

  1. 提取矩阵 A ~\mathbf{A}~的列向量

    • 将 A ~\mathbf{A}~的列向量表示为 x1,x2,x3 ~\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_3~：
      x1=[1111],x2=[0111],x3=[0011]\mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{x}_2 = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{x}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix}

  2. 构建正交矩阵 Q ~\mathbf{Q}~

    • 应用施密特正交化生成正交基：
      v1=[1111],v2=[−3/41/41/41/4],v3=[0−2/31/31/3]\mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix},\quad \mathbf{v}_2 = \begin{bmatrix} -3/4 \\ 1/4 \\ 1/4 \\ 1/4 \end{bmatrix},\quad \mathbf{v}_3 = \begin{bmatrix} 0 \\ -2/3 \\ 1/3 \\ 1/3 \end{bmatrix}
      标准化 v1,v2,v3 ~\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3~得到u1,u2,u3\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3：
      u1=12[1111],u2=112[−3111],u3=16[0−211]\mathbf{u_1} = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{u_2} = \frac{1}{\sqrt{12}} \begin{bmatrix} -3 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{u_3} = \frac{1}{\sqrt{6}} \begin{bmatrix} 0 \\ -2 \\ 1 \\ 1 \end{bmatrix}
      将 u1,u2,u3 ~\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3~作为 Q ~\mathbf{Q}~的列向量：
      Q=[1/2−3/1201/21/12−2/61/21/121/61/21/121/6]\mathbf{Q} = \begin{bmatrix} 1/2 & -3/\sqrt{12} & 0 \\ 1/2 & 1/\sqrt{12} & -2/\sqrt{6} \\ 1/2 & 1/\sqrt{12} & 1/\sqrt{6} \\ 1/2 & 1/\sqrt{12} & 1/\sqrt{6} \end{bmatrix}
  3. 计算上三角矩阵 R ~\mathbf{R}~
    • 使用 QTA=R ~\mathbf{Q}^T\mathbf{A} = \mathbf{R}~：
      R=[23/2103/232/12002/6]\mathbf{R} = \begin{bmatrix} 2 & 3/2 & 1 \\ 0 & 3/2\sqrt{3} & 2/\sqrt{12} \\ 0 & 0 & 2/\sqrt{6} \end{bmatrix}

6.3 正交投影

6.5 最小二乘问题

bei an浙ICP备2024102481号