秦 (1)如何减小运算量一收缩技巧(deflation) 分而治之算法的计算复杂性分析如下：用t(n)表示对n阶矩阵调用函数dc_e1g 的运算量，则 t(n)=2t(n/2)递归调用dc_eig两次 +O(n计算D+auuT的特征值和特征向量 +c.n3 计算Q. 如果计算Q时使用的是稠密矩阵乘法，则c=2;若不计O(2)项，则由递归 公式t(n)=2t(n/2)+c.n3可得t(n)≈c.4n3/3. 事实上，由于收缩(deflation)现象的存在，常数c通常比l小得多。 http://math.ecnu.edu.cn/~jypan 26/77 (1) 如何减小运算量 — 收缩技巧 (deflation) 分而治之算法的计算复杂性分析如下: 用t(n) 表示对n 阶矩阵调用函数 dc_eig 的运算量, 则 t(n) = 2 t(n/2) 递归调用 dc_eig 两次 + O(n 2 ) 计算 D + αuu ⊺ 的特征值和特征向量 + c · n 3 计算 Q. 如果计算 Q 时使用的是稠密矩阵乘法, 则 c = 2; 若不计 O(n 2 ) 项, 则由递归 公式 t(n) = 2 t(n/2) + c · n 3 可得 t(n) ≈ c · 4n 3/3. 事实上, 由于收缩 (deflation) 现象的存在, 常数 c 通常比 1 小得多. http://math.ecnu.edu.cn/~jypan 26/77