M<=2 ?
k=k+1
得到最后一个或两个 特征根
超过最大迭代次数 失败
得到全部特征根 成功
结束
图 1 带双步位移的 QR 分解法求特征根算法流程图
Hr 的构造方法如下： 若������������������������������������ = 0，(������������ ≥ ������������ + 2)，则取������������������������ = ������������ ； 否则，取
其中 Q 为正交阵。
′ ′ ，λ′ 因此������������������������+1 与 A 相似，设 A 和������������������������+1 的特征值分别为λ1 ，λ2 … λ������������ 和λ1 2 … λ������������ ，对应的特 ′ ′ ′ ，x2 … x������������ ，则有 征值分别为x1 ，x2 … x������������ 和x1 (������������ = 1，2 … ������������) λ������������ = λ′ ������������ ′ (������������ = 1，2 … ������������) x������������ = Qx������������ 实特征根对应的特征向量即为 Q 中对应的列向量。
������������������������ = ������������(������������) ������������������������ ������������������������ = ������������(������������)������������ ������������������������
( ) (������������) (������������ )
(������������)
则有
4. 拟上三角化 用 QR 方法求特征值时， 直接对 A 进行分解迭代次数太多， 因此先对 A 进行拟上三角化， 再对得到的拟上三角阵进行 QR 分解，从而减少迭代次数。 拟上三角化过程与 QR 分解类似，从 r=1 开始，记������������(1) = ������������，构造相似变换矩阵 Hr，使 r=n-2 时，有 ������������(������������−1) = ������������������������−2 ������������(������������−2) ������������������������−2 得到的������������(������������−1) 即为拟上三角阵。 Hr 的构造方法如下： ������������(������������+1) = ������������������������ ������������(������������) ������������������������
ห้องสมุดไป่ตู้
开始
对A进行拟上三角化 得到A(n-1)
初始化 给定精度er0， 最大迭代次数L
k=1 m=n A1=A(n-1)
|am, m-1 (k)| < er0 ? N |am-1, m-2 (k)| < er0 ? N k=L ? N 带双步位移的 QR分解
Y
Y
Y
得到一对 共轭特征根 m=m-2
得到一个 实特征根 m=m-1
数值分析计算实习（二）
姓名：张时毓 学号：SY1403531
一、方案设计 1. 用带双步位移的 QR 分解法求 A 的全体特征根 先对 A 进行拟上三角化，得到������������(������������−1) ，然后对������������(������������−1) 用带双步位移的 QR 分解法进行 QR 分解，逐步得到 A 的全部特征根。算法流程图如图 1 所示。 2. 求实特征根对应的特征向量 设拟上三角化过程为 其中������������′ 为正交阵。 QR 分解迭代过程为 ������������(������������−1) = ������������′−1 ������������������������′
������������������������ = (0 … 0, ������������������������������������ … ������������������������������������ )������������
(������������)
(������������)
3. QR 分解 从 r=1 开始，记������������(1) = ������������，构造相似变换矩阵 Hr，使 r=n-1 时，有 其中 ������������(������������) = ������������������������−1 ������������(������������−1) R = ������������(������������) Q = ������������1 ������������2 … ������������������������−1 A = QR ������������(������������+1) = ������������������������ ������������(������������)
若每步计算先算 Hr，再由������������(������������+1) = ������������������������ ������������(������������) 计算������������(������������+1) ，则需做一次矩阵减法、一次向量 乘法和一次矩阵乘法，即 n2 次减法和 n2+n3 次乘法，计算量大，因此，令 ℎ������������ = 1 ‖������������ ‖2 2 ������������ ������������������������ ������������������������ = ℎ������������
若������������������������������������ = 0，(������������ ≥ ������������ + 1)，则取������������������������ = ������������ ； 否则，取
������������������������ = (0 … 0, ������������������������+1,������������ … ������������������������������������ )������������ +‖������������������������ ‖ ������������������������ = � +‖������������������������ ‖ e = ������������������������+1 ������������������������+1,������������ ≤ 0 ������������������������+1,������������ > 0
������������ ������������(������������+1) = ������������(������������) − ������������������������ ������������������������ ������������ ������������(������������+1) = ������������ (������������) − ������������������������ ������������������������ 此时，计算������������(������������+1) 只需作 n2 次减法和 n+ n2 次乘法，计算量大大降低。
������������ ������������������������ = ������������������������ − ������������������������ ������������������������ = (0 … 0, ������������������������������������ − ������������������������ … ������������������������������������ )������������ ������������ 2������������������������ ������������������������ 0 ������������ = � ������������−1 � ������������������������ = ������������ − 2 0 ������������ ‖������������������������ ‖2 ������������−1
������������1 = ������������(������������−1) −1 −1 −1 −1 ������������������������+1 = ������������������������ ������������������������ ������������������������ = ������������������������ … ������������2 ������������1 ������������1 ������������1 ������������2 … ������������������������ = (������������1 ������������2 … ������������������������ )−1 ������������(������������−1) (������������1 ������������2 … ������������������������ ) 记������������′ ′ = ������������1 ������������2 … ������������������������ ，则有 ������������������������+1 = ������������′′−1 ������������(������������−1) ������������′′ = ������������′′−1 ������������′−1 ������������������������′ ������������′′ = (������������′ ������������′′ )−1 ������������(������������′ ������������′′ ) 其中������������′′ 为正交阵。 记Q = ������������′ ������������′′ ，则有 ������������������������+1 = ������������−1 ������������������������