文档介绍：1 SVD (奇异值分解)算法及其评估本文第一部分对 SVD 进行了简单的介绍,给出了定义和奇异值分解定理;第二部分简要地列举了 SVD 的应用;第三部分则构造和分析了各种求解 SVD 的算法, 特别对传统 QR 迭代算法和零位移 QR 迭代算法进行了详细完整的分析;第四部分给出了复矩阵时的处理办法;第五部分是对各种算法的一个简要的总结。一、 SVD 简介定义 设 m n A R ??, T A A 的特征值的非负平方根称作 A 的奇异值; A 的奇异值的全体记作?? A?[1] 。当A 为复矩阵 m n C ?时,只需将 T A A 改为 H A A ,定义 仍然成立。定理 (奇异值分解定理) 设 m n A R ??,则必存在正交矩阵?? 1 ,..., m m m U u u R ?? ?和?? 1 ,..., n n n V v v R ?? ?使得0 0 0 rT r n r r U AV m r ??? ??? ??? ?,…() 其中 1 1 ( ,..., ), ... 0 r r r diag ? ???? ? ???[2] 。当A 为复矩阵 m n C ?时,只需将定理中, U V 改为酉矩阵,其它不变,定理 仍然成立[1] 。称分解式() 为矩阵 A 的奇异值分解,通常简称为 SVD 。 i?是A 的奇异值,向量 iu 和 iv 分别是第 i 个左奇异向量和第 i 个右奇异向量。从A 的奇异值分解,我们可以得到 A 的一些非常有用的信息,下面的推论就列举其中几条最基本的结论[1] : 推论 设 m n r A C ??,则(1)A 的非零奇异值的个数就等于( ) r rank A ?; (2) 1 ,..., r n v v ?是( ) A 的一组标准正交基; (3) 1 ,..., r u v 是( ) A 的一组标准正交基; (4) 1 rH i i i i A u v ????称为 A 的满秩奇异值分解; 其中( ) A , ( ) A 分别指得是 A 的零空间和值域。为了方便,我们采用如下表示奇异值的记号: ( ) A iA?= 的第 i 大奇异值; max ( ) A A?= 的最大奇异值; min ( ) A A?= 的最小奇异值。现在来考察矩阵奇异值的几何意义[1,2] ,不妨设 m n ?,此时有?? 2 : , , 1 n n n E y C y Ax x C x ? ? ??? 2 是一个超椭球面,它的 n 个半轴长正好是 A 的n 个奇异值 1 2 ... 0 n ? ? ?? ???,这些轴所在的直线正好是 A 的左奇异向量所在的直线,它们分别是对应的右奇异向量所在直线的象。一般地我们假设 m n ?,(对于 m n ?的情况,我们可以先对 A 转置,然后进行奇异值分解,最后对所求得的 SVD 分解式进行转置就可以得到原式 SVD 分解式), 此时我们对() 进行化简将 U 表示为: 1 2 ( , ), U U U ?…() 则可以得到更加细腻的 SVD 分解式[2,3] : 1 T A U V ? ?…() 其中 1U 具有 n 列m 维正交向量,V 和() 式中的定义相同; 1 2 ( , ,..., ) n diag ? ????, 并且 1 2 ... 0 n ? ? ?? ???为矩阵 A 的奇异值。二、 SVD 应用在现代科学计算中 SVD 具有广泛的应用,在已经比较成熟的软件包 LINPAC K 中列举的应用有以下几点[3]: (1) 确定矩阵的秩(rank) 假设矩阵 A 的秩为 r ,那么 A 的奇异值满足如下式子 1 1 ... ... 0 r r n ? ????? ?????; 反之,如果 0 r??,且 1 ... 0 r n ? ??? ??,那么矩阵 A 的秩为 r ,这样奇异值分解就可以被用来确定矩阵的秩了。事实的计算中我们几乎不可能计算得到奇异值正好等于 0,所以我们还要确定什么时候计算得到的奇异值足够接近于 0,以致可以忽略而近似为 0。关于这个问题,