上一节在二维情形研究的无位移 QR 迭代只是线性收敛,速度由特征值之比决定,而且对稠密的 矩阵,每一步都要做一次阶数为 的完整 QR 分解。实际使用的方法消除了这两个障碍。第一,先用正交相似把矩阵一次性约化为接近三角形的上 Hessenberg 形。第二,每个 QR 步用特征值的估计值作位移,使最后一个次对角元迅速变小。第三,一旦该元素可以忽略,就把问题分出来(收缩),在较小的矩阵上继续。本节证明使每个阶段成立的事实。本节用到 Householder QR 一节中的 Householder 反射、QR 迭代恒等式 ,以及本章前面各节的反幂迭代。
定义
定义 5.6.1
(上 Hessenberg 矩阵)
实矩阵 称为上 Hessenberg 矩阵,若 时 ;它在对角线及其以上,以及第一条次对角线上可以非零。
定义 5.6.2
(Householder 反射与 Givens 旋转)
Householder 反射为 ( 为非零向量),它是对称的正交矩阵。作用于第 行的 Givens 旋转 除下面的分块外与单位矩阵相同:
对于给定的 ,取 ,,就使 的第二个分量为零。
定义 5.6.3
(带位移的 QR 步与 Rayleigh 位移)
位移为 的带位移 QR 步取方阵 ,计算分解 ( 正交, 上三角),并构造
Rayleigh 位移为 ,即最后一个对角元。
因为 ,所以 ,即 与 正交相似,具有相同的特征值。
定义 5.6.4
(收缩)
若把次对角元 置零,使矩阵成为块上三角,就称矩阵被收缩。
Hessenberg 约化
定理 5.6.5
(约化为 Hessenberg 形)
对每个实 矩阵 ,存在由 Householder 反射相乘得到的正交矩阵 ,使 为上 Hessenberg 矩阵。若 对称,则 为三对角矩阵。
证明
(逐列消去)
令 ,对 构造 ,其中 , 是 中如下选取的 Householder 反射。设 为 第 列对角线以下的部分。取 ,其中当 时 ,否则 (这个符号避免相消),并在 时取 (当 时取 )。则 。
左乘 只改变第 行,并使第 列在第 行的元素为零。对列 ,其第 行的元素本来就是零(因为 ),零的线性组合仍为零,所以这些列不变。右乘 只组合第 列,所以第 列保持其全部零元素。做到 时,每一列 在第 行都是零,所以 是上 Hessenberg 矩阵,并且由于每个 都是对称正交矩阵,,其中 。若 ,则 对称;对称的 Hessenberg 矩阵在第一条次对角线以下为零,由对称性在第一条超对角线以上也为零,所以是三对角矩阵。
证明透视
为什么反射从对角线以下开始
约化依赖于每次乘法触及哪些行和列。向量 取自第 列、从第 行开始,所以 只作用于第 行与列。左乘使第 列在第 行以下化为零,并且不动第 行;右乘只组合第 列,碰不到第 列,所以已经造出的零得以保留。若反射改为从对角元开始构造,右乘就会把第 列本身与后面的列组合,刚造出的零一般会重新被填上。因此相似变换只能负担得起清除第一条次对角线以下的元素;剩下的次对角线,正是后面的 QR 迭代要驱使趋于零的部分。符号 另有作用:由于 ,只要 就有 ,并且 的第一个分量的计算不会发生相消。
约化所需的运算次数与 成正比,而且只需做一次。
Hessenberg 矩阵上带位移的 QR 步
定理 5.6.6
(QR 步保持 Hessenberg 形)
设 为上 Hessenberg 矩阵,。从 出发,对 ,令 为作用于第 行的 Givens 旋转,其选取使当前矩阵的 元素为零。则 为上三角矩阵, 为正交矩阵且 ,并且 是上 Hessenberg 矩阵。每一步的代价为 次运算。
证明
(用旋转化为三角形,再乘回)
矩阵 是 Hessenberg 矩阵,所以第 列在对角线以下只有一个非零元素,位于第 行。施加 时,前面的旋转 已使第 列成为上三角,并且只改变了第 行;第 行仍是原样,所以 元素就是原来的元素。旋转把它化为零,并且不影响第 列(它们在第 行的元素为零)。做完 次旋转后,矩阵是上三角矩阵,即 。由 得 。
为了计算 ,把 依次右乘 、 等等; 把第 列与第 列换成它们自身的线性组合。令 。我们用归纳法证明: 的第 列只在第 行有非零元素(而当 时只在第 行有非零元素)。 时这就是 的三角性。在 中,第 列只在第 行有元素(它是 的第 列的组合,或者就是 的第 列),而第 列就是 的第 列,元素在第 行。于是它们在 中的组合只在第 行有元素,这对 和 满足所述性质;其他列不变。取 ,即知 是上 Hessenberg 矩阵, 亦然。每个旋转改变两行(左乘)或两列(右乘),长度至多为 ,所以代价为 次运算,一步的代价为 。
对一般稠密矩阵,同样的分解需要 ,所以 Hessenberg 形使每一步的代价降低约一个 的因子。
定理 5.6.7
(Q 的最后一列是反幂迭代向量)
若 非奇异,其中 正交, 上三角,则 的最后一列 满足 ,其中 是 的最后一个对角元。因此 。并且 的最后一个次对角元满足 。
证明
(逆转置的最后一列)
由 得 。矩阵 是下三角矩阵,所以它的最后一列是 。因此 。取范数,由 得 的公式。 的最后一行是 ,所以 的最后一行是 最后一行的 倍,位置 的元素为 ,且 。
当 对称时,,所以 是以位移 、从 出发的一步反幂迭代;并且恰当这一步放大得很强时, 才小,也就是 接近某个特征值,而该特征向量的最后一个分量非零。对于对称的 及其特征对 ,其中 、 且 ,有 ,因此 。Rayleigh 位移 是 的 Rayleigh 商,所以是这种特征值的自然估计。本节不证明 Rayleigh 位移的收敛速度;对于对称三对角矩阵,实际上是三次收敛,下面的例子可见。
Rayleigh 位移在实际中效果很好,但“它一定有进展”这个说法并不成立。
反例模式
Rayleigh 位移可能让矩阵原封不动
很容易以为,取 Rayleigh 位移 的每一步都会使最后一个次对角元变小。取 ,它本来就是 Hessenberg 矩阵,所以 。此时 ,其 QR 分解(取 的对角元为正,这时分解唯一)为 ,。于是 :这一步重现了 ,次对角元仍然等于 。实际程序改用 Wilkinson 位移,即右下角 块中最接近 的特征值。这里该块就是 本身,两个特征值 和 与 同样接近,取其中任何一个都能一步使矩阵收缩。
算法与收缩
EIGENVALUES(A):
reduce A to Hessenberg form H = Q^T A Q
m = n
while m > 1:
repeat
choose a shift mu (for example h[m][m])
apply one shifted QR step to the leading m-by-m block of H
until |h[m][m-1]| is negligible
record h[m][m] as an eigenvalue; set h[m][m-1] = 0; m = m - 1
record h[1][1]
若 ,则 ,两个对角块为方阵,且 ,所以 的特征值就是 与 的特征值(按重数计)。因此当 时, 是特征值,问题化为左上角的 块。在浮点运算中,“可忽略”指小于单位舍入误差乘以 的一个小倍数;把这样的元素置零,相当于对 作了同样大小的扰动。实矩阵若有共轭复特征值,就不能用实正交相似化为三角形:迭代最后得到 对角块,只看单个次对角元的停止准则可能永远无法满足,需要复位移或双位移,本节不讨论。对称矩阵的特征值全为实数。
概念视角结构
次对角元为零即不变子空间
记 ,,其中 是前 列。由 得 ,而 恰好等价于 ,也就是 的前 列张成的子空间在 作用下保持不变。因此收缩就是分离出一个不变子空间, 的特征值正是 限制在该子空间上的特征值。
例题
例题 5.6.8
(3 阶矩阵的 Hessenberg 约化)
设
只需要一个反射()。第 列对角线以下的向量为 ,。因为 ,取 ,与 成比例。则 ,。取 ,
相似不变量的检查:迹为 ; 的行列式为 ;两个矩阵的 主子式之和都是 。 元素为零,所以 是 Hessenberg 矩阵。
例题 5.6.9
(以特征值作位移,一步收缩)
设 ,特征值为 和 ,取 。则 ,其中 ,,并且
一步就得到两个特征值。这是退化的情形: 是奇异矩阵,,所以关于最后一列的定理不能照原样应用;但界 与此结果一致,因为当 时右端趋于 。
例题 5.6.10
(三对角矩阵上带位移的 QR 步)
设 ,取 Rayleigh 位移 。则 。第一个旋转取 :,。施加它之后,第二列在第 行的元素为 ,然后第二个旋转取 ,得主元 ,,。结果为
且 。计算 得
其迹为 。以 重复,得到下表(已舍入):
| 步数 | ||
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0.2711 | 0.5714 |
| 2 | 0.003859 | 0.53950 |
| 3 | 0.5394951 |
三步之后,次对角元可以忽略,所以 是 的特征值,精确到约八位数字。剩下的块 含有另外两个特征值,它的迹 等于 ,与应有的结果一致。最后两次缩小与三次收敛相符:,而实际观察到的是 。
常见错误与细节
常见错误
(Hessenberg 形不是三角形)
约化为 Hessenberg 形是正交相似,所以特征值保持不变,但结果是 Hessenberg 矩阵而不是三角矩阵:第一条次对角线一般非零,所以还不能直接读出特征值。
常见错误
(忘记加回位移)
带位移的 QR 分解的是 而不是 。若算出 后不加回 ,得到的矩阵的特征值就是 的特征值平移 。
常见错误
(始终使用同一个位移)
位移应当在每次迭代时更新;固定的位移只给出向离位移最近的特征值的线性收敛,与固定位移的反幂迭代相同。
已经对称的矩阵在每一步(正交相似)之后仍保持对称,所以对称矩阵的 Hessenberg 形的三对角结构也被保持。
Rayleigh 位移并不保证对每个初始矩阵都收敛,上面的反例就说明了这一点。三次收敛是对称三对角矩阵上观察到的现象,本节没有证明。
把很小但不为零的次对角元收缩为零,是一种向后稳定的近似(对 的小扰动),并不是精确的陈述。
练习
快速检查
(证明若对称矩阵 用正交矩阵 约化为 Hessenberg 形 ,则 是三对角矩阵。)
先证明 是对称的。
解答 · 答案
满足 ,所以 对称。若 ,由 Hessenberg 性质 ,由对称性 (此时 ),所以只要 就有 。因此 是三对角矩阵。
练习 5.6.11
(对 ,证明位移 (另一个特征值)也能一步收缩。)
核心
用 Givens 旋转计算该 QR 步。
解答(3)
- 1
构造位移后的矩阵
- 2
选取使次对角元为零的旋转
关键一步
依据: 取 ,,旋转把 变为 。
- 3
乘回并加上位移
次对角元为零,两个特征值都出现在对角线上。
快速检查
(证明若上 Hessenberg 矩阵 有 ,则 的谱是其左上 块与右下 块的谱的并集。)
当 时, 是什么形状?
解答 · 答案
若 ,则第 行、第 列中对角线以下的元素全为零(Hessenberg 结构本来已使 处为零),所以 。块上三角矩阵的行列式等于各对角块行列式之积,所以 ,其根就是两个因子的根。
练习 5.6.12
(对 及 ,利用最后一列的公式精确计算 ,并对照三对角矩阵的例题检验 。)
核心
这里 是对称矩阵,所以 。
解答(3)
- 1
解一个线性方程组
解 。第三个方程给出 ;第一个 给出 ;第二个 给出 。
依据: 定理用 表示 。
- 2
应用范数公式
关键一步
与算出的 的最后一个对角元一致。
- 3
与次对角元比较
该元素为 ,其中 ,所以 。
快速检查
(稠密矩阵的一步 QR 约需 量级的运算,Hessenberg 矩阵的一步 QR 约需 量级。对 ,忽略常数,比较两者的量级,并说明当 个特征值各需要少数几步时节省了什么。)
把代价沿逐渐缩小的活动块加起来。
解答 · 答案
当 时,,,比值为 。若 个特征值各需要少数几步(随着特征值被收缩,活动块越来越小),Hessenberg 迭代的总代价为 量级,而用稠密步则为 量级;节省的是一个 量级的因子,代价是另加一次 量级的一次性约化。