清华大学高等数值分析(李津)第二次实践作业.docx

奇异值分解算法分析及利用SVD进行图像压缩报告提纲：一、 奇异值分解二、 SVD算法三、 实验过程四、 实验结果分析五、 SVD法图像压缩及结果分析奇异值分解定义 设，的特征值的非负平方根称作的奇异值；的奇异值的全体记作当为复矩阵时，只需将改为，定义仍然成立定理（奇异值分解定理） 设，则必存在正交矩阵和使得 其中[2]当为复矩阵时，只需将定理中改为酉矩阵，其它不变，定理仍然成立奇异值分解通常简称为SVD，是的奇异值，向量和分别是第个左奇异向量和第个右奇异向量SVD算法1. QR迭代算法（1）输入及允许误差.（2）二对角化：计算Householder变换 使得其中； 具体算法，书面作业中题目具体解释3）收敛性检验：（i）将所有满足的j置零；（ii）如果，则输出有关信息结束；否则，，确定正整数，使得， ，；（iii）如果存在i满足使得，则，转步（iv），否则转步（4）.（iv）确定和使 //这也相对于所以可以直接调用givens变换算法得到 //这相当于（v）如果，则，，，，转步（iv），否则转步（i）.（4）SVD迭代：将书上的追赶法作用于二对角阵，得， , 然后转步（3）。

2. 分而治之分而治之算法的第一步也和QR迭代算法一样，先将矩阵二对角化得到二对角矩阵B；然后将求B的SVD问题分为两个子问题 先将B写成如下的形式： 其中，为上二对角矩阵，是相应维数的向量中的第j个单位向量，并且一般我们取 现在假如我们已经求得了，的SVD如下： ，并且令为的最后一行，为的第一行那么将这些带入B，我们可以得到： 可以看出中间的矩阵形式上很简单，除了对角元素和第k行上的元素，其它元素都为0；这里先把它的SVD的计算问题放到最后，而假定已知其SVD为：，将它带入上式，就可以得到B的SVD分解式： 其中 ；而计算，的SVD时也可递归地应用这种办法，至到子问题足够得小3. 单边雅克比迭代法虽然以上两种方法都可以对二对角矩阵求出具有很高的相对精度的奇异值和奇异值分解式；但是将一个稠密矩阵二对角化这个过程却可能会造成很大的相对误差[17]所以所有基于先将矩阵二对角化的SVD方法都不可能具有可靠的良好的相对精确度以下所要介绍的Jacobi方法和这些方法完全不同，它通过一系列平面旋转（一般文献中在介绍Jacobi方法时为了方便也将平面旋转称为Jacobi变换）；最终使得矩阵收敛于一个对角矩阵： 其中每一个设计成，使得对于一对选定的指标，有如下式子成立： 最终收敛时，令，有，且具有互相正交的列向量，可以将写成，其中为对角矩阵，为正交矩阵；从而得到原矩阵的SVD分解式。

在Jacobi算法中，令是最初的矩阵，是经过一次Jacobi旋转过得到的矩阵，其中为对角矩阵，是列向量范数全为1的矩阵可以知道对进行单边的Jacobi变换相当于对矩阵进行双边的Jacobi变换实验过程针对以上三种SVD算法用matlab进行数值模拟，三个算法源自NAG matlab工具箱（第24版，64bit），分别为f08kb（QR迭代），f08kd（分而治之）和f08kj（单边雅克比迭代）实验中选出10个矩阵（大小1200×960，将图像压缩应用的5张图片每张图片一分为二得到10个矩阵）对每种算法的内存占用量、运算时间、最小特征值误差，以及左特征向量和右特征向量的计算误差进行了计算，并得到了相应的曲线图特征向量的误差通过和列向量范数的均方误差来评估至于最小特征值误差，默认matlab自带的svd算法得到的结果是“准确”的，作为参考标准事实上，无法得到准确的特征值，用matlab自带svd作为标准严格来说也是不准确的图片文件为附件中的image1.jpg，image2.jpg，image3.jpg，image,4.jpg，image,5.jpg 实验结果分析 下面对算法的内存使用，计算速度，最小特征值精度，奇异向量误差进行了比较，各图中红色曲线为QR迭代法，绿色代表分而治之方法，蓝色代表单边雅克比方法。

1. 内存使用很明显，分而治之内存占用最少，大概而QR迭代的一半，雅克比最大，大概比QR迭代多占用一半的内存2. 计算时间计算时间上，分而治之最快，QR迭代次之，单边雅克比法最慢，花费时间大概是传统QR的十倍，是分而治之的20倍3. 最小特征值精度 从图中可以看到，传统QR算法和分而治之的最小奇异值几乎是完全一样的，而单边雅克比则不同，计算精度上没有明显的差别，但雅克比计算结果温度，而另外两种则抖动相对较大对各误差求和得到三种算法的误差和分别为2.8363e-15，3.2270e-15和1.9147e-15，相比之下，雅克比算法精度最高，传统QR算法次之，分而治之精度最差，原因在报告第一部分已经提及，但三者差别并不明显由于计算过程中的系统精度为2.2204e-16，显然实验得到的最小奇异值的误差大概在系统精度的5~10倍4. 左奇异向量误差 奇异向量误差上来看，分而治之最小，这与分而治之的算法原理一致，矩阵越 小计算的正交阵正交度越高而雅克比的奇异向量的误差相对来说就要大得多，大概为传统QR迭代的5倍5. 右奇异向量误差右奇异向量误差的规律和左奇异向量一致，但总体误差更小，因为右奇异向量就是计算中的特征向量，且矩阵阶数小，而左奇异向量是通过奇异值和特征向量反推得到的，故精度要差。

总体来说，传统QR方法程序简单，但占用内存大，在计算精度和运算速度方面居中分而治之的方法在内存占用和运算速度方面占有绝对优势，计算精度方面，奇异值精度没有传统QR好，但左右奇异向量的正交性要好于传统QR方法单边雅克比方法的奇异值计算精度方面有优势，内存占用居中，但奇异向量的正交性差，运算速度相比前两种方法慢一个数量级实际应用中，根据需要选择特定的SVD算法注：图像数据在附件中SVD法图像压缩 实验中所用照片为附件中image1.jpg，image2.jpg，image3.jpg，image,4.jpg，image,5.jpg首先将彩色图片灰度化，得到两维的矩阵（1200×1920），采用matlab自带的svd算法进行奇异值分解取前l项奇异值和奇异向量的乘积求和得到的图像成为前l项压缩，l取20、80、300，给出压缩后的图像，并进行比较以狗的照片为例分析，另外4张图像类似，见附件可以看到，l=20时有明显的不清晰，就连光滑的背景都有明显的杂点；l=80时已经很清晰了，但放大看仍有噪点和部分细节分辨率下降；而l=300时就几乎和原图的清晰度一样了SVD压缩事实上是一种有损压缩，压缩过程中丢掉了图片的大量信息，这些信息有可能是一些重要的细节。

附件清单1. 程序清单（main.m，SVDfun.m）2. 原彩色图片五张3. 实验得到的图片20张（每个图4张）4. 计算部分中的图像数据（matlab data.mat）。