Gram-Schmidt 正交化
逐次减去在已有方向上的投影，得到标准正交基 \(\mathbf{q}_1,\dots,\mathbf{q}_n\)。
18.06 · 第 16 课
Gram-Schmidt 正交化把一组无关向量改造成标准正交基。写成矩阵形式就是 \(A=QR\)：\(Q\) 列正交、\(R\) 上三角。代入法方程立刻得到 \(\hat{\mathbf{x}}=R^{-1}Q^T\mathbf{b}\)——最小二乘的计算因此大大简化。
给定无关向量 \(\mathbf{a}_1,\mathbf{a}_2,\dots,\mathbf{a}_n\)，构造标准正交向量 \(\mathbf{q}_1,\mathbf{q}_2,\dots,\mathbf{q}_n\)：
第一步。
\[\mathbf{A}_1 = \mathbf{a}_1,\qquad \mathbf{q}_1 = \frac{\mathbf{A}_1}{\|\mathbf{A}_1\|}.\]第二步。从 \(\mathbf{a}_2\) 中减去它在 \(\mathbf{q}_1\) 方向的分量，得到与 \(\mathbf{q}_1\) 正交的向量，再归一化：
\[\mathbf{A}_2 = \mathbf{a}_2 - (\mathbf{q}_1^T\mathbf{a}_2)\,\mathbf{q}_1,\qquad \mathbf{q}_2 = \frac{\mathbf{A}_2}{\|\mathbf{A}_2\|}.\]第 \(k\) 步。从 \(\mathbf{a}_k\) 中减去它在所有已有 \(\mathbf{q}_1,\dots,\mathbf{q}_{k-1}\) 方向的分量：
\[\mathbf{A}_k = \mathbf{a}_k - \sum_{j=1}^{k-1} (\mathbf{q}_j^T\mathbf{a}_k)\,\mathbf{q}_j,\qquad \mathbf{q}_k = \frac{\mathbf{A}_k}{\|\mathbf{A}_k\|}.\]每次减去投影。\((\mathbf{q}_j^T\mathbf{a}_k)\mathbf{q}_j\) 正是 \(\mathbf{a}_k\) 在 \(\mathbf{q}_j\) 方向上的投影。Gram-Schmidt 逐次剔除所有已有方向的分量，留下垂直分量。
数值稳定性。经典 Gram-Schmidt 在浮点运算中正交性会逐渐丧失。实际计算常用修正 Gram-Schmidt（MGS）或 Householder 变换。
把 Gram-Schmidt 的公式改写为原向量的表达式：
\[\begin{aligned} \mathbf{a}_1 &= \|\mathbf{A}_1\|\,\mathbf{q}_1,\\ \mathbf{a}_2 &= (\mathbf{q}_1^T\mathbf{a}_2)\,\mathbf{q}_1 + \|\mathbf{A}_2\|\,\mathbf{q}_2,\\ \mathbf{a}_k &= \sum_{j=1}^{k-1}(\mathbf{q}_j^T\mathbf{a}_k)\,\mathbf{q}_j + \|\mathbf{A}_k\|\,\mathbf{q}_k. \end{aligned}\]写成矩阵形式，这就是 \(A=QR\) 分解：
\[A = \begin{bmatrix}\mathbf{a}_1&\mathbf{a}_2&\cdots&\mathbf{a}_n\end{bmatrix} = \begin{bmatrix}\mathbf{q}_1&\mathbf{q}_2&\cdots&\mathbf{q}_n\end{bmatrix} \begin{bmatrix} \|\mathbf{A}_1\| & \mathbf{q}_1^T\mathbf{a}_2 & \cdots & \mathbf{q}_1^T\mathbf{a}_n \\ 0 & \|\mathbf{A}_2\| & \cdots & \mathbf{q}_2^T\mathbf{a}_n \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & \|\mathbf{A}_n\| \end{bmatrix}.\]其中 \(Q=[\mathbf{q}_1\ \cdots\ \mathbf{q}_n]\) 列标准正交（\(Q^TQ=I\)），\(R\) 是上三角矩阵且对角元为正（\(\|\mathbf{A}_k\|>0\)，由无关性保证）。
QR 是 Gram-Schmidt 的矩阵语言。Gram-Schmidt 是算法，\(A=QR\) 是代数结果。两者等价，但 \(A=QR\) 把正交化过程凝聚成一个因式分解。
把 \(A=QR\) 代入法方程 \(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\)：
\[A^TA = R^TQ^TQR = R^T R \quad (\text{因为 } Q^TQ=I).\]法方程变为
\[R^T R\,\hat{\mathbf{x}} = R^T Q^T \mathbf{b}.\]\(R^T\) 可逆，两边左乘 \((R^T)^{-1}\) 得到简化法方程：
\[R\,\hat{\mathbf{x}} = Q^T\mathbf{b}.\]\(R\) 是上三角矩阵，用回代法（back substitution）即可求解，无需矩阵求逆。
QR 让最小二乘更稳。直接解 \(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\) 的条件数是 \(\kappa(A)^2\)，而 \(R\hat{\mathbf{x}}=Q^T\mathbf{b}\) 的条件数是 \(\kappa(R)=\kappa(A)\)。QR 分解是数值最小二乘的标准方法。
设 \(A=\begin{bmatrix}1&0\\1&1\\1&0\end{bmatrix}\)，列向量 \(\mathbf{a}_1=\begin{bmatrix}1\\1\\1\end{bmatrix},\mathbf{a}_2=\begin{bmatrix}0\\1\\0\end{bmatrix}\)。
Gram-Schmidt：
\[\mathbf{q}_1 = \frac{1}{\sqrt{3}}\begin{bmatrix}1\\1\\1\end{bmatrix},\qquad \mathbf{A}_2 = \mathbf{a}_2 - (\mathbf{q}_1^T\mathbf{a}_2)\mathbf{q}_1 = \begin{bmatrix}0\\1\\0\end{bmatrix} - \frac{1}{\sqrt{3}}\cdot\frac{1}{\sqrt{3}}\begin{bmatrix}1\\1\\1\end{bmatrix} = \frac{1}{3}\begin{bmatrix}-1\\2\\-1\end{bmatrix}.\] \[\|\mathbf{A}_2\| = \frac{1}{3}\sqrt{6} = \frac{\sqrt{6}}{3},\qquad \mathbf{q}_2 = \frac{1}{\sqrt{6}}\begin{bmatrix}-1\\2\\-1\end{bmatrix}.\]\(R\) 矩阵：
\[R = \begin{bmatrix} \|\mathbf{A}_1\| & \mathbf{q}_1^T\mathbf{a}_2 \\ 0 & \|\mathbf{A}_2\| \end{bmatrix} = \begin{bmatrix} \sqrt{3} & \dfrac{1}{\sqrt{3}} \\ 0 & \dfrac{\sqrt{6}}{3} \end{bmatrix}.\]验证 \(Q R = A\)：
\[\mathbf{q}_1\cdot\sqrt{3} = \begin{bmatrix}1\\1\\1\end{bmatrix} = \mathbf{a}_1,\qquad \mathbf{q}_1\cdot\frac{1}{\sqrt{3}} + \mathbf{q}_2\cdot\frac{\sqrt{6}}{3} = \frac{1}{3}\begin{bmatrix}1\\1\\1\end{bmatrix} + \frac{1}{3}\begin{bmatrix}-1\\2\\-1\end{bmatrix} = \begin{bmatrix}0\\1\\0\end{bmatrix} = \mathbf{a}_2.\]问题 1：Gram-Schmidt 第 \(k\) 步中，\(\mathbf{A}_k\) 的计算方式是什么？
问题 2：在 \(A=QR\) 分解中，\(Q\) 和 \(R\) 分别具有什么性质？
问题 3：把 \(A=QR\) 代入法方程 \(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\)，化简后得到什么？
问题 4：用 QR 分解解最小二乘的主要数值优势是什么？
逐次减去在已有方向上的投影，得到标准正交基 \(\mathbf{q}_1,\dots,\mathbf{q}_n\)。
\(Q\) 列标准正交，\(R\) 上三角——Gram-Schmidt 的矩阵语言。
\(R\hat{\mathbf{x}}=Q^T\mathbf{b}\)，回代即可求解，条件数保持最优。
QR 分解避免了 \(A^TA\) 的条件数平方，是实际应用的首选方法。
lecture_slides/lecture_17.pdflecture_summaries/lecture_2_2_summary.pdf