在前面的算法描述过程中，我们假定d山互不相等且不能为零。 事实上，若d:=d+1或u:=0,则d:即为D+auuT的特征值，这种现象我们 称为收缩(deflation). 在实际计算时，当d:-d+1或小于一个给定的阈值时，我们就近似认为d 为D+auuT的特征值，即出现收缩现象。 在实际计算中，收缩现象会经常发生，而且非常频繁，所以我们可以而且应该利 用这种优点加快分而治之算法的速度。 由于主要的计算量集中在计算Q,即算法最后一步的矩阵乘积.如果，=0，则 d为特征值，其对应的特征向量为e,即Q的第i列为e,故计算Q的第i列时 不需要做任何的计算 当d=d+1时，也存在一个类似的简化 http://math.ecnu.edu.cn/-jypan 27/77
在前面的算法描述过程中, 我们假定 di 互不相等且 ui 不能为零. 事实上, 若 di = di+1 或 ui = 0, 则 di 即为 D + αuu ⊺ 的特征值, 这种现象我们 称为收缩 (deflation) . 在实际计算时, 当 di − di+1 或 |ui | 小于一个给定的阈值时, 我们就近似认为 di 为 D + αuu ⊺ 的特征值, 即出现收缩现象. 在实际计算中, 收缩现象会经常发生, 而且非常频繁, 所以我们可以而且应该利 用这种优点加快分而治之算法的速度. 由于主要的计算量集中在计算 Q, 即算法最后一步的矩阵乘积. 如果 ui = 0, 则 di 为特征值, 其对应的特征向量为 ei , 即 Qˆ 的第 i 列为 ei , 故计算 Q 的第 i 列时 不需要做任何的计算. 当 di = di+1 时, 也存在一个类似的简化. http://math.ecnu.edu.cn/~jypan 27/77
秦 (2)特征方程求解 通常我们可以使用牛顿法来计算特征方程(A)=0的解 当d≠d+1且≠0时，用牛顿法计算f()在(d+1,d)中的零点入 如果|小于给定的阈值时，我们可直接将d山作为特征值入的一个近似. 但当很小（却大于给定的阈值）时，此时f()在区间[d+1,d中的大部分处 的斜率几乎为0（见下图）.这时，如果任取[d+1,d中的一个点作为迭代初始 点，经过一次牛顿迭代后，迭代解可能会跑到区间[山+1，d]的外面，造成不收敛 http://math.ecnu.edu.cn/~jypan 28/77
(2) 特征方程求解 通常我们可以使用牛顿法来计算特征方程 f(λ) = 0 的解. 当 di ̸= di+1 且 ui ̸= 0 时, 用牛顿法计算 f(λ) 在 (di+1, di) 中的零点 λi . 如果 |ui | 小于给定的阈值时, 我们可直接将 di 作为特征值 λi 的一个近似. 但当 ui 很小 (却大于给定的阈值) 时, 此时 f(λ) 在区间 [di+1, di ] 中的大部分处 的斜率几乎为 0 (见下图). 这时, 如果任取 [di+1, di ] 中的一个点作为迭代初始 点, 经过一次牛顿迭代后, 迭代解可能会跑到区间 [di+1, di ] 的外面, 造成不收敛. http://math.ecnu.edu.cn/~jypan 28/77
0=0.005 秦 6 2 0 -2 345 6 图4.1f()=1+0.005(点+点+点+点)的图像 http://math.ecnu.edu.cn/~jypan 29/77
图 4.1 f(λ) = 1 + 0.005 1 4−λ + 1 3−λ + 1 2−λ + 1 1−λ 的图像 http://math.ecnu.edu.cn/~jypan 29/77
秦 这时需要采用修正的牛顿法.假设我们已经计算出入：的一个近似入，下面我们 需要从入出发，利用牛顿迭代计算下一个近似，直至收敛.我们知道牛顿法的基 本原理是使用（入）在点入的切线来近似f(),并将切线的零点作为下一个近 似，即用直线来近似曲线∫(A): 当：很小时，这种近似方法会出现问题，此时不能使用直线来近似().这时， 我们可以寻找其它简单函数()来近似f(),然后用h()的零点作为f()零 点的近似，并不断迭代下去，直至收敛， 当然，h()需要满足一定的要求： (1)必须容易构造； (2)其零点容易计算： (3)尽可能与f)相近 http://math.ecnu.edu.cn/~jypan 30/77
这时需要采用修正的牛顿法. 假设我们已经计算出 λi 的一个近似 λ˜, 下面我们 需要从 λ˜ 出发, 利用牛顿迭代计算下一个近似, 直至收敛. 我们知道牛顿法的基 本原理是使用 f(λ) 在点 λ˜ 的切线来近似 f(λ), 并将切线的零点作为下一个近 似, 即用直线来近似曲线 f(λ). 当 ui 很小时, 这种近似方法会出现问题, 此时不能使用直线来近似 f(λ). 这时, 我们可以寻找其它简单函数 h(λ) 来近似 f(λ), 然后用 h(λ) 的零点作为 f(λ) 零 点的近似, 并不断迭代下去, 直至收敛. 当然, h(λ) 需要满足一定的要求: (1) 必须容易构造; (2) 其零点容易计算; (3) 尽可能与 f(λ) 相近. http://math.ecnu.edu.cn/~jypan 30/77
秦 下面给出构造h(入)的一种方法. 因为d和d+1是f()的奇点，所以我们令 h()=, C2 4-入十4+1-入+， 其中c1,c2,c3为参数.显然，h()的零点很容易计算（与Newton法相差无几）. 在选取这些参数时，要使得(A)在入附近尽可能地接近f().记 f()=1+a∑4- ≌1+a(亚1()+乎2() http://math.ecnu.edu.cn/~jypan 31/77
下面给出构造 h(λ) 的一种方法. 因为 di 和 di+1 是 f(λ) 的奇点, 所以我们令 h(λ) = c1 di − λ + c2 di+1 − λ + c3, 其中 c1, c2, c3 为参数. 显然, h(λ) 的零点很容易计算 (与 Newton 法相差无几). 在选取这些参数时, 要使得 h(λ) 在 λ˜ 附近尽可能地接近 f(λ). 记 f(λ) = 1 + α Xn k=1 u 2 k dk − λ = 1 + α X i k=1 u 2 k dk − λ + Xn k=i+1 u 2 k dk − λ ! ≜ 1 + α Ψ1(λ) + Ψ2(λ) . http://math.ecnu.edu.cn/~jypan 31/77