标准正交基使坐标与投影的计算变得简单,但给定的一组基往往并非标准正交。Gram–Schmidt 在不改变输入列表各个初始段所生成子空间的前提下,构造标准正交列表。其关键步骤是残差:减去先前方向已能解释的部分,再把剩下的部分单位化。零残差表示线性相关,而不是一个可以单位化的方向。
现有的内积课证明了 Gram–Schmidt;空间与映射提供向量空间基础。本节进一步讨论初始段张成空间、相关列表及薄 QR。
记号与约定
设 为有限维实或复内积空间。采用对第一变量线性的内积。在标准正交的列坐标下,
因此,向量 沿单位向量 的系数为 ,而不是 。星号表示共轭转置;在实数域上就是普通转置。
定义 9.1.1
(对标准正交列表的残差)
设 是 中的标准正交列表,。 对该列表的残差为
列表为空时求和为空,。列表 的有序初始段张成空间是子空间 ,。
减去先前的方向
先假设 线性无关。递归地把 定义为 对 的残差,并令 。
定理 9.1.2
(线性无关输入的 Gram–Schmidt)
设 线性无关。令
则每个 ,递归因而有定义;列表 标准正交;并且
证明
(正交性、残差非零与初始段张成空间相等)
对 作归纳,假设 标准正交,且初始段张成空间如所述。对每个 ,
所以残差垂直于先前所有保留的方向。它不可能为零:否则定义式会使 属于这些方向的张成空间;由归纳,该空间就是它之前的输入向量所张成的空间,与线性无关矛盾。因此可以合法地单位化,得到一个与其余向量垂直的新单位向量。
重构方程为
它说明 ,所以 的初始段张成空间包含于 的。反过来,每个残差都是 与先前 的线性组合,因而是 的线性组合,所以 属于 的初始段张成空间。两个包含关系都成立。
证明透视
线性无关用在哪里,以及为何两个包含关系都要证
证明只用一次线性无关:使 ,这样才能作除法。正交性则不需要它,因为抵消 对任何残差都成立。归纳假设用了两次:先前 的标准正交性使求和只剩一项;先前初始段张成空间相等,则把“”翻译成“ 是 的线性组合”。
单凭正交性不能证明张成空间相等: 个标准正交向量可以落在另一个 维子空间内。由重构方程得到的包含关系,加上维数计算或另一方向的直接包含,才完成论证。没有线性无关时,同一计算在每个非零步骤仍给出正交性,但遇到零残差,递归便停止。
结果依赖于输入次序。最终张成空间固定,但改变次序通常会产生不同的中间方向。把某个输入乘以复相位,也可能改变其单位化后的方向。固定的是所述递归构造,并约定残差的范数取正实数。
常见错误
(把系数的两个变量次序写反)
对第一变量线性的内积, 在 中的系数是 。在 中取 ,。正确的系数为 ,残差 ,与 垂直。次序反了的系数 给出 ,它与 的内积为 。在实数域上两种次序相同,所以这个错误只在 上出现。
相关列表需要略去输入
对一般的有序列表,保留截至目前所得的标准正交列表。从下一个输入减去它在该列表张成空间上的投影。若残差非零,加入其单位化后的向量;若为零,略去这个输入,保持当前列表不变。
在每个阶段,保留列表的张成空间等于输入初始段的张成空间。零残差等价于当前向量属于先前保留方向的张成空间,所以略去它不会损失信息。非零残差使维数增加一。由归纳可知,即使原列表含有零向量或重复向量,最终保留列表仍是整个输入张成空间的一组标准正交基。
这是精确算术下的结论。在浮点计算中,很小的残差并不自动证明精确的线性相关。数值阈值需要另作误差分析;本章不作这类数值断言。
反例模式
对相关列表使用 Gram–Schmidt
命题:对任意 个向量执行线性无关情形的递归,必得 个标准正交向量。在 取 ,。则 ,,投影为 ,故 。公式 要除以 :不存在第二个单位向量;张成空间只是一条直线,其中放不下长度为 的标准正交列表。修正:略去残差为零的输入,并报告保留向量的个数,此处为 。
例题 9.1.3
(含重复方向的相关列表)
在 取 ,,。首先 。对 :,投影为 ,残差为 ,略去 。对 :,投影为 ,,,所以 。保留列表 有两个向量,等于输入列表的秩。验算:,且 。
三角形重构就是薄 QR 分解
设 为列向量线性无关的实或复 矩阵,所以 。对其各列应用该构造,令 ,并定义
定理 9.1.4
(薄 QR 分解)
若 是列向量线性无关的 矩阵,则 ,其中 , 为上三角矩阵且对角元为正实数。这个分解是唯一的。
证明
(存在性来自重构,唯一性来自被强制的各步)
存在性就是把重构方程 逐列读出,再加上 的标准正交性。
唯一性:设 是任一符合要求的分解。第一列强制给出 ;单位范数及对角元为正的约定强制 ,并确定 。归纳地,设 已确定。把 与 ()作内积,固定 。剩下的部分是 ,所以它的正范数固定 ,进而固定 。
这里 只含所需的 个标准正交列。当 时, 是到列空间的投影,而不是环境空间上的恒等算子。若没有对角元为正的约定,符号或复相位便可在两个因子之间转移。
对相关的列,保留的 有 列,重构矩阵的尺寸为 。它不是方阵形式的可逆三角矩阵。略去零残差后,若不改变这些尺寸,便不能声称得到列满秩情形的 QR 分解。
例题 9.1.5
( 矩阵的薄 QR)
设 ,两列为 ,。则 ,。其次 , ,。所以 ,。验算 ,并重构第二列:。因 ,:例如 把 送到 。
用 Gram 矩阵核对计算
对列满秩分解,
行列式恒等式来自两个三角方阵因子的行列式相乘;即使在复数情形,对角元也都是正实数。更一般地,Gram 矩阵第 行、第 列的元素为 。它正定当且仅当向量线性无关,因为它在系数列处的二次型取值,就是相应线性组合的范数平方。
这为残差长度提供了一个有用的独立检查。对上面的例子, 的行列式为 ,而 。但它不能取代标准正交性的检查:只有正确的行列式,并不能确定每个内积。
概念视角代数
三角因子就是 Cholesky 因子
由于 ,而 是对角元为正的上三角矩阵, 就是 Gram 矩阵 的 Cholesky 因子;对正定矩阵而言,在对角元为正的约定下这个因子唯一。因此对 的各列做 Gram–Schmidt,所得三角矩阵与只对 Gram 矩阵做分解所得的相同,无须构造 。在上面的例子中,,其中 。
同一构造适用于多项式
向量不一定是坐标列。对次数有界的实多项式,定义
这是内积。对称性及双线性由积分得到。若非零多项式的范数平方为零,连续性及区间中某个函数值非零的点,会给出一个小区间,使其平方在该区间上有正的下界,产生矛盾。这样的点存在,因为非零多项式不可能在整个区间上恒为零。
所以,对单项式应用 Gram–Schmidt 会得到标准正交的多项式。其系数由实际的内积积分得到,不能把单项式的坐标列当作欧氏向量。
例题 9.1.6
(在 上把 标准正交化)
,所以 。对 :(被积函数为奇函数),故 ,,。对 :,在 方向的投影为 ,而 。于是 ,,所以 。验算:。
清单与常见错误
- 对线性无关输入,每个残差都非零,而且每个初始段的张成空间保持不变。
- 对相关输入,略去零残差,并报告保留基的维数。不要除以零。
- 在对第一变量线性的约定下,系数为 ;复数域上共轭不可省略。
- 线性无关列的薄 QR 满足 , 上三角且对角元为正实数。这些要求给出唯一性。
- 对非欧氏内积,应使用它实际的配对计算系数与范数。
对一个拟定的答案,要检查配对、残差范数及重构。正交向量未必是单位向量;标准正交列表未必张成所需空间;矩阵乘积尺寸正确也不够,它还必须重构输入。
小测
快速检查
(在 中对 , 作一步 Gram–Schmidt:求 和残差 。)
解答 · 答案
。,所以投影为 ,。它与 垂直:。
快速检查
(把 中的列表 交给带略去规则的 Gram–Schmidt。保留多少个向量?哪一个输入被略去?)
解答 · 答案
保留两个。,,而 对它们的残差为 ,所以第三个输入被略去。个数等于 。
快速检查
(若 是 矩阵的薄 QR 分解,且 ,是否有 ?)
解答 · 答案
没有。 的秩为 ,不可能是单位矩阵。它是到 的列空间的正交投影;只有 成立。