用局部坐标变换对角化
实对称矩阵具有实特征值和标准正交特征向量基。Jacobi 特征值方法反复只旋转两个坐标方向,以求得这种对角结构。每次旋转消去一个非对角元素,却不改变特征值。其他元素可能重新出现,所以重要的问题不是某个位置是否一直保持为零,而是非对角部分的总量是否减小。
这是特征值算法,不是用于求解线性方程组的 Jacobi 定常迭代。下文对实对称 矩阵 在精确算术中讨论,。有限精度可能破坏精确对称性和精确消零;下述收敛证明本身并未建立舍入误差界。
一次平面旋转
定义 5.3.1
(Jacobi 平面旋转)
选取下标 ,将对应的对称 块简记为
令 除坐标 外与单位矩阵相同,在这两个坐标上的块为
更新采用 。
由于 正交,这是一种正交相似变换:对称性和特征值多重集都保持不变。在这个具体的符号约定下,新的主元元素为
命题 5.3.2
(消去主元的旋转)
若 ,无需旋转。若 ,令 、,并选取
就使 ,并且新的对角元素为
证明
(解主元方程)
由于 ,条件 等价于 ,即 。所选的 是这个二次方程中模较小的根:当 时它是 , 的情形对称。它满足 。当 时方程为 , 是一个根。
展开 得 。由于 ,便得 。该 块经正交相似变换,迹保持不变,所以 。
所选的根避免了在所示代数公式中对两个很大且接近的数作减法。实际浮点代码中,即使计算 或 也可能上溢;缩放公式和仔细实现是另一个数值问题。
常见错误
(混用旋转的符号约定)
其他教材可能选用转置后的旋转,使 的符号相反。更新式 、 的主元公式、 的公式以及对角元素的更新都取决于这个选择,必须一起改变。若主元公式取自一种约定,更新却取自另一种,得到的矩阵仍然与 相似,但其主元元素一般不为零。
二维例子
例题 5.3.3
(一次旋转对角化 2 阶矩阵)
对 ,有 ,故 、。一次旋转给出
的列是归一化特征向量: 对应 1, 对应 3。把一列的符号反转,仍表示同一特征方向。
概念视角几何
旋转到主轴
这个块定义二次型 。记 ,主元方程 就是 ,而所选的根满足 。把坐标轴旋转这个角度,交叉项随之消失,新的坐标轴就是这个二次型的主轴。在上面的例子中,主轴方向是 和 。
非对角部分的减小
定义 5.3.4
(非对角测度)
方阵 的非对角 Frobenius 测度的平方定义为
每个元素的两个对称位置都计入。
命题 5.3.5
(消去旋转下的精确减少量)
若一次 Jacobi 旋转消去 ,则
证明
(正交混合保持成对平方和)
对每个 ,数对 乘以一个正交 矩阵,故其平方和不变。由对称性,相应行元素给出同样的贡献。两行两列之外的元素不变。只有两个主元位置从非对角和中消失,各贡献 。这也说明为什么如果只统计一个三角部分,因子二会改变。
例题 5.3.6
(三对角矩阵的非对角测度)
对
。消去主元 的一次旋转得到 。其他一些非对角元素会改变:与第三个坐标耦合的两个元素被旋转。这里 ,,被旋转的数对 变成 ,其平方和仍为 。
例题 5.3.7
(第二次旋转后的填入)
从上面的 继续,其元素为 、、、、、。最大主元并列,模均为 ,选取 。取 、、,得 ,于是 ,,。旋转后的矩阵约为
所以 ,与恒等式一致。第一次旋转已置零的元素 ,现在约为 。两步的保证上界为 ,实际值 低于此界。
常见错误
(以为已置零的元素会一直保持为零)
在坐标 所在平面内的旋转,会把第 、 行与列同其余各行各列混合,所以一般会重新填入先前旋转已清除的元素,上一个例子已经说明。收敛来自总测度 的减小,而不是来自元素一经置零便永远固定。
最大主元收敛性
定义 5.3.8
(最大主元 Jacobi 方法)
在第 步,若 ,选取使 最大的 ,并应用上面的消零旋转。并列时可任意选择。如果非对角测度为零,则停止。
定理 5.3.9
(非对角测度的线性减小)
在精确算术下,使用最大主元策略有
因此,只要迭代无限继续,就有 。当 时因子为零,一次非平凡旋转便使矩阵对角化。
证明
(最大元素不小于平均值)
完整和式中有 个非对角元素。最大主元的模 至少不小于其中每一个,故 。将该界代入精确减少恒等式。当 时,因子严格介于零与一之间,反复应用得到趋于零的几何上界。
证明透视
主元规则与正交性各在哪里起作用
这个证明用到两个互相独立的事实,各在一处起作用。旋转的正交性给出精确恒等式 ,对任何使用消零旋转的主元它都成立。主元规则只通过下界 起作用: 个平方数中最大的一个不小于它们的平均值。没有这条规则时,恒等式仍然成立,但 可能为零,这时什么也不会减小。两处计数必须采用同一个约定:恒等式减去主元的两个副本,而平均值是对两个三角部分一起取的。
下面的例子说明主元规则不能省去。
反例模式
忽略最大元素的主元规则
断言:任何在固定位置施行消零旋转的规则,都使非对角测度几何地减小。取
则 。若算法始终选择 ,且当所选元素为零时什么也不做,就会发现 ,矩阵保持不变,非对角测度永远保持 。这不是对正确指定的循环 Jacobi 方法的反例;它只说明反复选择已为零的位置不满足最大主元条件。最大主元是 :此时 ,,,一次旋转便得到 ,。
累积旋转与近似特征对
令 ,。每个 都正交,且
记 为 的第 列,。
命题 5.3.10
(累积各列的残差)
每个 都是单位向量, 是它对 的 Rayleigh 商,并且
证明
(由相似关系读出残差)
关系式 说明 。减去 后剩下 。各列 标准正交,所以其平方范数为 ,它是定义 的和的一部分。由于 是正交矩阵的一列,范数为一,而 就是 Rayleigh 商。
因此收敛定理给出每一列的残差趋于零。对称矩阵的残差界说明,非对角范数很小时,每个对角元素都接近某个特征值。每一步的相似变换保持整个特征值多重集。
常见错误
(由小残差读出极限特征向量)
这些结论本身不能证明 的每一列都收敛到某个指定特征向量,也不能说明某个对角下标对应事先指定的特征值。特征向量的符号不唯一,重特征值的特征空间也有不唯一的基。若声称特征向量有极限,或单个特征值具有某个收敛速度,还需额外假设和单独论证。
实际停止规则可在 非零时,将 与相对于此范数的容差比较。精确正交相似变换保持 Frobenius 范数。残差估计解释了该准则的意义;实际代码还须考虑浮点误差,并单独处理零矩阵。
练习与解答
快速检查
(对 ,使用所述 约定求 和对应特征向量。)
这里 。
解答 · 答案
、,故所述旋转给出 、,即 。列 和 分别对应 1 和 5。
快速检查
(一个对称 迭代矩阵满足 。一次最大主元旋转后,新的非对角测度平方有什么上界?)
使用因子 。
解答 · 答案
,所以新的平方测度至多为 。
快速检查
(对上面的 三对角例子,不计算 的所有元素,解释为什么消去 后非对角测度平方为 2。)
使用精确减少恒等式。
解答 · 答案
精确减少量是 ,因此从 4 变为 2。旋转保持其余成对元素的平方和。
快速检查
(若 ,可对每个累积旋转列和对应对角值说什么?这是否单独证明了当 时这些列收敛?)
想一想对称矩阵的残差界。
解答 · 答案
每列都是单位向量,对其对角值的特征对残差范数至多为 ,所以由对称性,必有某个特征值与该对角值相差不超过 。单凭一次小残差的观察,并不能证明列的序列收敛到某个指定的特征向量。