yqjch特征值q.ppt

3.3 QR方法 在特征值计算问题上，QR方法具有里程碑意义。在1955年的时候，人们还觉得特征值的计算是十分困扰的问题，到1965年它的计算——基于QR方法的程序已经完全成熟。直到今天QR方法仍然是特征值计算的有效方法之一。 计算特征值问题的 QR 方法，实际上总是分成 2 个阶段： 定义: 拟上三角 (上Hessenberg)阵指一个 n 阶方阵 B， B 满足: 当 i j +1 时，bij= 0。 拟上三角矩阵有如下的形式: 3.3.1 矩阵的QR分解理论 定义1 把矩阵 A 分解为一个正交阵 Q 与一个上三角阵 R 的乘积, 称 A 的正交三角分解, 简称QR分解. 定义2 设 v∈Rn是单位向量, 即 vTv =1, 令 H = I - 2vvT (3.18) 其中, I 是 n×n 单位矩阵, 则矩阵 H 满足: HT = H; HTH = (I - 2vvT )(I - 2vvT ) = I. 即, H 是对称的正交阵. 式 (3.18) 定义的矩阵 H 称为Householder(豪斯荷尔德)矩阵,又称镜面映射矩阵. 注：镜面映射矩阵又称初等反射矩阵. 简称H-矩阵，它被单位向量 v 唯一确定。 任给非零向量x，令y=Hx，则 。正交变换是保模变换。 引理3.1 设有非零向量 s∈Rn 和单位向量 e∈Rn, 必存在 Householder 矩阵 H，使得 Hs = ? e 其中 ? 是实数，并且 。 定理3.2 任何 n 阶方阵 A 总可以分解为一个 正交阵 Q 与一个上三角阵 R 的乘积。 证: 正交阵 Q 与上三角阵 R 的构造过程如下： 设 n 阶方阵 A=[aij]; er=(0, …,0, 1, 0,…,0)T 是 n 维单位坐标向量。 （1）设 ai1 (i = 2, 3,…, n) 不全为零, 令 ? QR 方法的基本思想 给定实矩阵 A, QR 法可求出A的全部特征值，过程如下： (1) 令 A1 = A, (2) 做 A1的 QR 分解, A1 = Q1R1 , 交换乘法次序, 做 A2 = R1Q1 , 则 A2 = Q1TA1Q1 , A2与A1相似. (3) 对 A2再进行分解, A2 = Q2R2 , 交换乘法次序, 做 A3 = R2Q2 , 则 A3与A2相似. 一般地, 有 (4)对 Ak 进行分解, Ak = QkRk , 交换乘法次序, 做 Ak+1= Rk Qk , 则 Ak+1与Ak相似. Ak+1= QkTAkQk , 所以, Ak+1与 A 相似, 它们有相同的特征值. 最后, 矩阵序列{ Ak+1} 基本上收敛于一个上三角阵 RA, RA 主对角线上的元素是其全部特征值, 从而求出 A 的全部特征值. ? 基本 QR 法的迭代公式: 对于给定的 n 阶实矩阵 A, (1) 令 A1 = A, (2) Ak = QkRk , (对 Ak作QR分解) (3) Ak+1= Rk Qk , (交换乘法次序) (k =1, 2, … , n) Ak+1= QkTAkQk , 故 Ak+1 与 A 相似. 它们有相同的特征值. 计算特征值问题的 QR 方法，实际上总是分成 2 个阶段： 3.3.2 矩阵的拟上三角化 对一般 n 阶矩阵，QR算法的每一个迭代步需要 O(n3) 次乘法运算. 如果矩阵阶数稍大，这个算法几乎没有实际的应用价值. 通常采用的方法是先对矩阵作相似变换化为拟上三角矩阵(又称上Hessenberg 矩阵) 在此基础上应用QR迭代. 这时，QR 迭代步的乘法运算次数只需 O(n2) 次. 定义 拟上三角 (Hessenberg)阵指一个 n 阶方阵 B， B 满足: 当 i j +1 时，bij= 0。 拟上三角矩阵有如下的形式: (1) 设 ai1 (i = 3, 4,…, n) 不全为零, 令 ? 带双步位移的QR 法 (3.22) 定理3.3 若 A 的特征值的重数均是 1，则由式(3.22) 产生的矩阵序列 { Ak+1} 基本上收敛于一个分块上三角阵 RA, RA 的对角块均是 1 阶或 2 阶子块。特别, 若A为实对称阵, 则{Ak+1}收敛于对角阵 D= diag(?1, …,?n), ?i 是 A 的全部特征值. 基本上收敛是指对角块上方的元素可能不收敛！ 关于QR法的收敛性，有下面的定理 一