施密特正交化(Gram-Schmidt Orthogonalization)-Toy模板网

这篇具有很好参考价值的文章主要介绍了施密特正交化(Gram-Schmidt Orthogonalization)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

注：本博文为本人阅读论文、文章后的原创笔记，未经授权不允许任何转载或商用行为，否则一经发现本人保留追责权利。有问题可留言联系，欢迎指摘批评，共同进步！！！

1 Gram-Schmidt的计算公式推导

问：以三维情况为例，已知三个线性无关的向量 $\mathbf{a}$ 、 $\mathbf{b}$ 、 $\mathbf{c}$ ，如何能找到三个正交向量 $\bm{\alpha_1}$ 、 $\bm{\alpha_2}$ 、 $\bm{\alpha_3}$ ，在归一化后能形成标准正交基： $\mathbf{e_1}$ 、 $\mathbf{e_2}$ 、 $\mathbf{e_3}$ ? 施密特正交化,数理基础,算法,矩阵,线性代数

公式:

对三个线性无关的向量 $\mathbf{a}$ 、 $\mathbf{b}$ 、 $\mathbf{c}$ 进行Gram-Schmidt正交化，所得的正交向量 $\bm{\alpha_1}$ 、 $\bm{\alpha_2}$ 、 $\bm{\alpha_3}$ 分别为:
$\begin{aligned} \bm{\alpha_1} &= \mathbf{a} \\ \bm{\alpha_2} &= \mathbf{b}-\frac{\mathbf{b} \ \bm{\alpha_1}}{|\bm{\alpha_1}|^2} \ \bm{\alpha_1} \\ \bm{\alpha_3} &= \mathbf{c}-\frac{\mathbf{c} \ \bm{\alpha_1}}{|\bm{\alpha_1}|^2} \ \bm{\alpha_1}-\frac{\mathbf{c} \ \bm{\alpha_2}}{|\bm{\alpha_2}|^2} \ \bm{\alpha_2} \end{aligned}$

对 $n$ 个线性无关的向量 $\mathbf{a}$ 、 $\mathbf{b}$ 、 $\cdots$ 、 $\mathbf{x}$ 进行Gram-Schmidt正交化，所得的正交向量 $\bm{\alpha_1}$ 、 $\bm{\alpha_2}$ 、 $\cdots$ 、 $\bm{\alpha_n}$ 分别为:
$\begin{aligned} \bm{\alpha_1} &= \mathbf{a} \\ \bm{\alpha_2} &= \mathbf{b}-\frac{\mathbf{b} \ \bm{\alpha_1}}{|\bm{\alpha_1}|^2} \ \bm{\alpha_1} \\ \bm{\alpha_3} &= \mathbf{c}-\frac{\mathbf{c} \ \bm{\alpha_1}}{|\bm{\alpha_1}|^2} \ \bm{\alpha_1}-\frac{\mathbf{c} \ \bm{\alpha_2}}{|\bm{\alpha_2}|^2} \ \bm{\alpha_2} \\ \vdots \\ \bm{\alpha_n} &= \mathbf{x}-\frac{\mathbf{x} \ \bm{\alpha_1}}{|\bm{\alpha_1}|^2} \ \bm{\alpha_1}-\frac{\mathbf{x} \ \bm{\alpha_2}}{|\bm{\alpha_2}|^2} \ \bm{\alpha_2} \ - \ \cdots - \ \frac{\mathbf{x} \ \bm{\alpha_{n-1}}}{|\bm{\alpha_{n-1}}|^2} \ \bm{\alpha_{n-1}} \end{aligned}$
公式解读：在使用第n个向量计算第n个正交向量时，只要在第n个向量中排除掉前(n-1)个正交向量的组分，就能得到第n个正交向量。

具体推导的图解请参看知乎回答。

2 Gram-Schmidt的意义

将非正交基转为正交基，便于表示。
通俗来说，就是将一对歪歪斜斜的基向量掰成标准正交基。（强迫症）

3 Modified Gram-Schmidt (以算法模式计算正交向量)

Gram-Schmidt公式推到中的方法是纯数的方法，但是在数值运算方法中（计算机操作）不会严格按照数学方法来。具体如下所述。

从Gram-Schmidt分解结果可以看出：
若对线性无关向量组{ $\mathbf{w_k}$ }进行Schmidt正交化得到标准正交基{ $\mathbf{u_k}$ }，经过移项可得到原向量组可以表示为标准正交基的线性组合：
$\begin{aligned} \mathbf{w_1} &= r_{11} \ \mathbf{u_1} \\ \mathbf{w_2} &= r_{21} \ \mathbf{u_1} + r_{22} \ \mathbf{u_2} \\ &\vdots \\ \mathbf{w_L} &= r_{L1} \ \mathbf{u_1} + r_{L2} \ \mathbf{u_2} + \cdots + r_{LL}\mathbf{u_L} \\ \end{aligned}$
因此，要完成正交化分解，我们需要找系数组{ $r_k$ }和标准正交基{ $\mathbf{u_k}$ }：

由此，我们看拿出Modified G-S的思想是：
使用第k个线性无关向量组的向量 $\mathbf{w_k}$ 计算第k个正交基 $\mathbf{u_k}$ 时，就是在 $\mathbf{w_k}$ 中排除掉前 $k - 1$ 个正交基的组分，剩余的就是 $\mathbf{u_k}$ 的组分，再除以系数即可。

3.1 Modified G-S会出现的问题：当矩阵开始存在微小误差时，会在运算过程中不断累积误差，导致越算越不准确，以至于计算所得的基不正交

情景：假设 $e$ 是一个接近与0的正数（作为一个微小的初始误差），那么请对矩阵 $\mathbf{W}\ = \begin{pmatrix} 1 & 1 & 1\\ e & 0 & 0\\ 0 & e & 0\\ 0 & 0 & e \end{pmatrix}$ 进行Gram-Schmidt正交化：

此时问题就很明显地体现出来了，向量 $\mathbf{u_2}$ 和 $\mathbf{u_3}$ 明显不正交，没法作为正交基使用。
问题的原因：误差“e”作为一个很小的误差，在每一次派出组分操作的过程中都被积累起来了（误差积累），导致越往后算越不准确，Gram-Schmidt就失效了。

为了解决这一问题，就有了Stable Gram-Schmidt算法（SGS）。

4 Stable Gram-Schmidt

不同于Modified Gram-Schmidt，SGS算法的核心思想是：
每使用一个线性无关组向量 $\mathbf{w_k}$ 求出一个单位正交基向量 $\mathbf{u_k}$ ，那么剩余的 $\mathbf{w_{k+1}}$ 到 $\mathbf{w_L}$ 这些向量都要立即原地减去其中所含的 $\mathbf{u_k}$ 组分，进行更新。

每计算出一个新的单位正交基向量，就当场把剩余线性无关组向量中的此组分排除掉

4.1 G-S 的复杂度（计算量）

施密特正交化,数理基础,算法,矩阵,线性代数

4.2 使用SGS算法解决误差问题

与3.1中的问题一致，使用SGS可以抵消微小误差的影响，算法更具有鲁棒性。
施密特正交化,数理基础,算法,矩阵,线性代数

4.3 MGS和SGS运算的区别在哪里？

我们注意到，使用两种算法计算所得的 $\mathbf{u_3}$ 向量时不同的，因此着重比较一下两算法计算 $\mathbf{u_3}$ 时的差别：( $\mathbf{u_3} = \frac{\mathbf{v_3}}{||\mathbf{v_3}||_2}$ )

MGS:（当使用到 $\mathbf{w_3}$ 计算 $\mathbf{u_3}$ 时，从 $\mathbf{w_3}$ 中一次性减去 $\mathbf{u_1}$ 和 $\mathbf{u_2}$ 的组分）
$\mathbf{v_3}=\mathbf{w_3}-(\mathbf{u_1^Tw_3})\mathbf{u_1}-(\mathbf{u_2^Tw_3})\mathbf{u_2}$
SGS：（当利用 $\mathbf{w_1}$ 求出 $\mathbf{u_1}$ 时， $\mathbf{w_2}$ 和 $\mathbf{w_3}$ 都立即减去其中所含的 $\mathbf{u_1}$ 组分进行更新；当利用 $\mathbf{w_2^{new}}$ 求出 $\mathbf{u_2}$ 时， $\mathbf{w_3^{new}}$ 立即减去其中所含的 $\mathbf{u_2}$ 组分进行更新，然后再求出 $\mathbf{u_3}$ ）
$\begin{aligned} \mathbf{w_3^{new}} &= \mathbf{w_3}-(\mathbf{u_1^Tw_3})\mathbf{u_1} \\ \mathbf{v_3} &= \mathbf{w_3^{new}}-(\mathbf{u_2^Tw_3^{new}})\mathbf{u_2} \\ &= (\mathbf{w_3}-(\mathbf{u_1^Tw_3})\mathbf{u_1})-(\mathbf{u_2^T(\mathbf{w_3}-(\mathbf{u_1^Tw_3})\mathbf{u_1})})\mathbf{u_2} \\ &= \mathbf{w_3}-(\mathbf{u_1^Tw_3})\mathbf{u_1}-(\mathbf{u_2^Tw_3})\mathbf{u_2} + (\mathbf{u_1^T}\mathbf{w_3})(\mathbf{u_2^T}\mathbf{u_1})\mathbf{u_2} \end{aligned}$
由此可见，SGS相较于MGS只是多了最后一项 $(\mathbf{u_1^Tw_3})(\mathbf{u_2^Tu_1})\mathbf{u_2}$ .

从理论上讲， $\mathbf{u_1}$ 与 $\mathbf{u_2}$ 是要正交的，因此 $\mathbf{u_2^Tu_1}=0$ ，最后多出的这一项在理论上就是不存在了。
但是在数值计算(计算机运算)时候存在一定的误差，此时最后这一项不再为0，它的存在也有助于保证在误差存在情况下的稳定性。
这一项在理论上不存在，但实际上有利于保持stability.

5 GS和LS（最小二乘法）

在一个 $k$ 维空间中，我们已知了 $k - 1$ 个单位正交基向量 $\mathbf{u_1}$ 、 $\mathbf{u_2}$ 、 $\cdots$ 、 $\mathbf{u_{k-1}}$ ，这些正交基列向量组成一个矩阵 $\mathbf{A}$ ={ $\mathbf{u_1} \ \mathbf{u_2} \ \cdots \ \mathbf{u_{k-1}}$ }。此外，还已知一个在 $k$ 维上都有分量的向量 $\mathbf{w}$ 。问：如何找到第 $k$ 个单位正交基向量 $\mathbf{u_k}$ 呢？

实际上，要找到这最后一个正交向量，我们只需要排除掉向量 $\mathbf{w}$ 中所含有的前( $k - 1$ )个单位正交向量组分即可。因此，我们可以找一个系数向量 $\mathbf{x}$ ，其中包含了前( $k - 1$ )个单位正交向量组分的系数，在所有可能的向量 $\mathbf{x}$ 中，我们希望 $\mathbf{Ax}$ 就是向量 $\mathbf{w}$ 中前( $k - 1$ )个单位正交向量组分，因此可以使用LS算法来进行优化：
$\mathbf{x^*} = arg\min_{x}||\mathbf{w}-\mathbf{Ax}||_2^2 \\ \mathbf{v_k} = \mathbf{w}-\mathbf{Ax^*} \\ \mathbf{u_k} = \frac{\mathbf{v_k}}{||\mathbf{v_k}||_2}$
我们来看看这个最优的 $\mathbf{x^*}$ 究竟是什么呢？
$\begin{aligned} \mathbf{x^*} &= arg\min_{x}||\mathbf{w}-\mathbf{Ax}||_2^2 \\ &=(\mathbf{A^TA})\mathbf{A^Tw_k} \\ &=\mathbf{A^Tw_k} \\ &= \begin{pmatrix} \mathbf{u_1^Tw_k} \\ \vdots \\ \mathbf{u_{k-1}^Tw_k} \end{pmatrix} \end{aligned}$
果然，最优的 $\mathbf{x^*}$ 就是由向量 $\mathbf{w}$ 中前 $k - 1$ 个单位正交基的组分的系数组成的。这样才能实现 $||\mathbf{w}-\mathbf{Ax}||_2^2$ 的最小化，即当向量 $\mathbf{w}$ 排除到其他组分后，剩下的 $\mathbf{u_k}$ 组分才能恰好与矩阵 $\mathbf{A}$ 所确定的超平面正交。
所以，回到问题，最后一个正交向量是：
$\mathbf{v_k} = \mathbf{w}-\mathbf{Ax^*}(把组分全部排除掉)$ 文章来源地址https://www.toymoban.com/news/detail-796964.html