下一节:BB分解取逆 上一级:转换为标准问题 上一节:转换为标准问题

BB取逆

BB为非奇异矩阵, 则问题 (8.1)等价于
(B1A)x=λxy~(B1A)=λy~,(8.3)(B^{-1}A) x = \lambda x \quad \mathrm{且} \quad\tilde{y}^{\ast} (B^{-1} A) = \lambda \tilde{y}^{\ast}, \tag{8.3}
其中 y~=By\tilde{y} = B^{\ast} y。 或者,问题 (8.1)也等价于
(AB1)x~=λx~y(AB1)=λy,(8.4)(AB^{-1})\tilde{x} = \lambda \tilde{x} \quad \mathrm{且} \quad y^{\ast} (AB^{-1}) = \lambda y^{\ast}, \tag{8.4}
其中 x~=Bx\tilde{x} = B x。 若主要关注右特征向量,则(8.3)更优,因为它避免了额外的反向变换。

对于迭代方法,如第 7章所述, 针对简化标准特征值问题 (8.3) 或(8.4),无需计算 B1AB^{-1}AAB1AB^{-1}。这是处理大型稀疏AABB的关键观察点。 只需计算矩阵-向量乘积,例如

r=(B1A)q,r = (B^{-1}A) q,
对于给定向量qq。对于双侧Lanczos型方法,向量
s=(B1A)ps = (B^{-1}A)^{\ast}p
对于给定向量pp也是必要的。 注意,向量 r=(B1A)qr = (B^{-1}A) q可以分两步计算:
(a) 形成u=Aqu = A q
(b) 解Br=uB r = urr

类似地,若必要,向量 s=(B1A)ps = (B^{-1}A)^{\ast}p可以这样计算:
(a)^{\prime}Bv=pB^{\ast} v = pvv
(b)^{\prime} 形成s=Avs = A^{\ast} v

每一步都可以利用稀疏性。 一般而言,除了Jacobi-Davidson方法外,迭代方法在步骤(b) (及(b)^{\prime})需要精确求解线性系统。若可能,优先使用直接线性系统求解器,例如利用BB的LU分解。详见第 10.3节关于稠密或稀疏LU分解的讨论。

这种转换为标准形式引入的误差 可能与 A2B12\Vert A\Vert _2 \Vert B^{-1}\Vert _2成正比。 若BB为病态矩阵,则此方法可能存在问题。 在这种情况下,可以考虑使用SI变换或下文讨论的Jacobi-Davidson方法。



下一节:BB分解取逆 上一级:转换为标准问题 上一节:转换为标准问题
Susan Blackford 2000-11-20