数值6(选主元高斯消元法)课程介绍.ppt

QR分解 [Q R]=qr(A) Q正交矩阵,R上三角矩阵 QR=A (5)A的奇异值分解: A=USVH;[U,S,V] = SVD(A) 概念:设 , AHA 的特征值为 令 , 称实数 为 A 的奇异值 (6) 非负矩阵分解: 给定非负矩阵A,计算A=WH,其中W和H为非负矩阵。 * 矩阵分解的应用1 I=imread(monalisa.pgm); [U,S,V]=svd(double(I)); s=diag(S); Snew=diag([s(1:10);zeros(size(s,1)-10,1)]); figure,imshow(U*Snew*V,[]) Snew=diag([s(1:50);zeros(size(s,1)-50,1)]); figure, imshow(U*Snew*V,[]) * 矩阵分解的应用 推荐书籍: Matrix Factorization Techniques for Recommender Systems * Netflix 直接法总结: 高斯消元法是一个复杂度为O(n3)的浮点运算有限序列, 并最终给出一个解。因此高斯消元法叫做求解线性方程组的直接方法。 理论上直接方法在有限步之内给出精确解(当然在一有限精度的计算机上执行时得到的结果将只是近似的)。 * (n-1)n! (Cramer法则 ) O(n3) (高斯消元法) O(n 2.373) O(n2+epsilon)? 1985 参考: The Smart Money’s on Numerical Analysts, SIAM News, 2012 O(n2.81) (Strassen算法) * */27 */27 */27 */27 */27 */27 */27 */27 */27 《数值分析》6 列主元消元法 直接三角分解法 特殊矩阵的分解 矩阵分解的应用 ? ? ? ? * 例1 * 例2 则该方程的精确解为 * 主元素的不同选择竟然会导致计算结果如此之大的差异。 * 没有成千上万次算术运算造成的舍入误差累积,矩阵也不接近于奇异。 部分选主元的高斯消元法: 绝对值小的主元素可能产生麻烦,最好每一步选取每一列中最大的元素作为主元素以使高斯消元法具有较好的数值稳定性。 例3 * A = (F1-1F2-1 ··· Fn-1-1 ) A(n – 1)=LU P1A= F1-1P2F2-1 ··· Fn-2-1 Pn-1 Fn-1-1 U L? U * Fn-1 Pn-1 ··· F2P2 F1P1A= U Pn-1Pn-2···P1A = Pn-1Pn-2···P2 F1-1P2F2-1 ··· Fn-2-1 Pn-1 Fn-1-1 U = (Pn-1Pn-2···P2 )F1-1 (P2P3···Pn-1 ) (Pn-1Pn-2···P3 ) F2-1 ··· (Pn-2 Pn-1)(Pn-1) Fn-2-1 ( Pn-1 ) Fn-1-1 U L U Matlab 命令: [L,U,P] = lu(A) * P1A= F1-1P2F2-1 ··· Fn-2-1 Pn-1 Fn-1-1 U L? U edit lutx bslashtx 矩阵的Doolittle分解 A = LU, L为单位下三角矩阵,U为上三角矩阵. a11= u11, ···, a1n= u1n a21 = m21u11, ··· , an1 = mn1u11 * 对A的元素aij ,当 j≥k 和 i≥k时 m21u12+ u22=a22, ··· , m21u1n+ u2n=a2n u22=a22 - m21u12, ··· , u2n=a2n- m21u1n m31u12+ m32u22=a32, ··· , mn1u12+ mn2u22=an2 m32=(a32- m31u12)/u22, ··· , mn2=(an2- mn1u12)/u22 * 矩阵L和矩阵U的元素计算公式 计算次序 1 2 3 4 5 6 * 例4 求矩阵的Doolittle分解 ? ? ? * * 矩阵Crout分解 计算次序 1 2 3 4 5 6 * 例6 求矩阵