《QR分解SVD分解最小乘问题数值上机报告》由会员分享，可在线阅读，更多相关《QR分解SVD分解最小乘问题数值上机报告（6页珍藏版）》请在金锄头文库上搜索。
1、QRQR 分解、分解、SVDSVD 分解、最小二乘问题数值上机报告分解、最小二乘问题数值上机报告练习练习 6.136.13 随机构造一个可逆方阵，利用不同的方法给出它的 QR 分解，观察所得列向 量的正交性、CPU 时间和所谓的向后稳定性。解： 本题中所得列向量的正交性由来进行刻画。向后稳定性由| I|2来进行刻画。|A - |2实验步骤：实验步骤： 1、首先分别编写出 CGS、MGS、Householder、Givens 等不同方法进行矩阵的 QR 分解 的程序。 2、在主程序中调用这些子程序。 其中在编写利用 Householder 矩阵进行矩阵的 QR 分解时，可以利用 H 矩阵作为秩一
2、修正矩阵在计算复杂度方面的优势，即,只需 2n+1 次乘除法运算。H g = 1()实验数据：实验数据： （1）取实验矩阵 A 为满秩的 200*200 的随机矩阵时得到的数据如下：方法CPU 时间/s正交性向后稳定性CGS1.11874e-014.63254e-123.96137e-16 MGS 5.03241e-027.32464e-148.21329e-15 Householder 3.62422e-021.60387e-147.46142e-14 Givens 6.95802e+007.95465e-151.93225e-13（2）取实验矩阵 A 为满秩的 400*400 的随机矩阵时
3、得到的数据如下：方法CPU 时间/s正交性向后稳定性CGS1.239653.82420e-111.00456e-14 MGS0.253403.72890e-131.43460e-14 Householder0.156783.12282e-145.18852e-13 Givens225.922771.40292e-144.36238e-13实验数据分析：实验数据分析： 1.从向后稳定性上来看，CGS 和 MGS 给出的 QR 乘积均能很好地近似原始矩阵 A，因此 都是向后稳定的算法。而 Householder 方法和 Givens 方法的向后稳定性略差。2.从所求得列向量的正交性来看，CGS 方
4、法最差，MGS 比 CGS 稍好，Householder 方法 和 Givens 方法的表现最好。Householder 方法给出的 Q 具有更好的列正交性。 3.从 CPU 时间上来看，Givens 方法所耗时间最长，这是合理的，因为对应于一个 Householder 矩阵，Givens 方法中要构造一系列 Givens 矩阵。理论分析，对于稠密阵， Householder 方法所需的乘除法次数是 Givens 方法的一半。 且由讲义所指出，有如下结果：N = 12( + 1 )( + 1 ) 2133. = 12( 1) 2而由 Householder 镜像变换法的计算复杂度略低于 MGS
5、 方法，Householder 方法所耗的 CPU 时间略低于 MGS 方法，故是合理的。练习 6.14 实现本章的两张图。（1）本题为了验证当矩阵的条件数非常恶劣时，CGS 和 MGS 两种直交化方法给出的对 角线元素也存在明显的差异。取实验矩阵 C 是由一个元素快速变化的对角矩阵相继地左乘和右乘两个任意的直交阵而得到的。则明显 C 的条件数非常(2 )80 = 1恶 0 劣。下图将两种方法给出的分解所得的上三角矩阵 R 的对角线元素绘制出来。从上图中可以看出 MGS 方法可以计算到数量级，而 CGS 方法只能计算到数10 1910 10量级，这从实验的角度说明了修正的 MGS 方法的数值健
6、壮性比传统的 CGS 方法更好， 与我们理论分析的结果相吻合。（2）本题说明了奇异值分解在图像压缩中也有很好的应用价值。由于存储在计算机中 的图像本质上是矩阵，对图像的主要结构有限的相应数学解读为矩阵具有重要价值的 主奇异值个数 k 远远小于矩阵的阶数 n。利用矩阵的奇异值分解，只需记录前 k 个主奇 异值,及其相应的奇异向量和 ,从而将图像的数据存储量从 mn 下降到。( + + 1)如上图所示：矩阵阶数为 200*320，当取 k=15 时，利用 SVD 分解，取前 15 个主特征值 来恢复出的小丑图像已与原始图像没有明显的差别了。由此原本的数据存储量为 64000 减为 7185，缩减了
7、约 88.8%的数据存储量。由此可以看出奇异值分解在图像压缩中也 有很好的应用价值。练习 6.15 考虑列满秩的最小二乘问题，其中系数矩阵和右端项分别 ( 1) 1= 为：A ( 1)= (1:,1: 1) =21 1200 00 01 00 00 10 0001 0021 12=(1 +1 ,2 ,3 , , 2 ,1 + 1 ,0).对应的最小二乘解为 分别用= (1,1,1,1,1).（a）法方程组；(b) MGS 方法；（c）Householder 法；（d）Givens 法这四种方法来 求解这个最小二乘问题。 令 n 从 5 增加到 30，绘图比较上述四种算法的计算工作量（可用 CP
8、U 时间表示）和计算精度与 n 的关系；实验步骤：实验步骤： 1.分别编写求解最小二乘解的四个方法对应的程序，再在主程序中调用这些子程序。 2.设置方程组的列数 n 从 5 变到 30，分别记录不同方法对应所耗的 CPU 时间和与真解 的误差大小。 3.作出图像，分析图像得出结论。 实验数据：实验数据： 得到的图像如下：图像分析：图像分析： 1.从第一张图中可以看出，这里对应四种不同的方法所耗的 CPU 时间从小到大依次为 法方程组方法，MGS 方法，Givens 方法，Householder 方法。法方程组方法由于无需进 行矩阵的 QR 分解，所以计算工作量最小，且编程中利用了 MATLAB
9、 的左除方法，故所 耗时间最少是合理的。而理论上对于稠密阵，Givens 方法的乘除法次数远多于 Householder 方法，所消耗的 CPU 时间也应该比 Householder 多才对。分析认为主要是 由于编程的格式造成了这种不合理的现象出现，编写的 Householder 算法是利用了教 科书上提供的算法，里面包含一堆 for 循环，而且属于 BLAS-1 量级，故虽然理论上所 需的乘除法次数较少，但所耗的 CPU 时间仍然较多。而 Givens 法由于在编程过程中采 用了 BLAS-2 代码级别，借助于 MATLAB 的并行处理技术，所花的时间比 Householder 法少，也是合
10、理的。2.从第二张图中可以看出，法方程组的误差最大，相应的计算精度最小。而 MGS 方法 和 Givens 方法对应的计算精度最好，这是由于 MGS 和 Givens 法均进行了矩阵的 QR 分 解，且后续计算过程利用了 MATLAB 自带的左除方法，所以计算精度较好，但理论上 Householder 方法的计算精度应该比 Givens 方法好才对，推测是由于在编写 Householder 方法是利用了教科书上所给的算法，且没有利用 MATLAB 已做过优化的左 除方法，故计算精度较差。法方程组的计算精度最差的原因是由于法方程组的条件数 变位原来方程组条件数的平方，从下图可以看出条件数在急剧增大，当 n=30 时， 的 2 条件数已达到了 57966，所以计算精度较小。A
