Gauss消去法 下面讨论实现过程: 第一步:消元。进行到第k步时必有 Ik Lk+1 In kk b, k+lk k+1k+1 k+ln k+1 k n,k+1 a(kk)作为主元,第k行依次乘a(ik)a(kk)加到第行,=k+1n 总共n-1步完成,k=1n1
下面讨论实现过程： 第一步：消元。进行到第k步时必有 + + + + + + + + n k n k n n n k k k k k n k kk k k kn k k k n a a a b a a a b a a a b a a a a b , 1 1, 1, 1 1, 1 , 1 1 1 1 1, 1 1 1 a(k,k)作为主元，第k行依次乘a(i,k)/a(k,k)加到第i行,i=k+1:n。 总共n-1步完成，k=1:n-1. 一、Gauss消去法
for k=l:n if a(k,k)==0, break, end fori=k+l: n a(i, k)=a(i,k)/a(k,k) b(i)=b(1)-a(i,k)·b(k) forj=k+l:n (2,j)=a(2,j)-a(1,k)·a(k, end ene e eno a(kk)=0,则上述消去法无法进行;或当其绝对值相对 太小可能会出现大的计算误差。选主元法可避免这种情况。下 面介绍常用的按列选主元的Gaus法
end end end end a i j a i j a i k a k j for j k :n b i b i a i k b k a i k a i k a k k fori k n if a k k for k n ( , ) ( , ) ( , ) ( , ); 1 ( ) ( ) ( , ) ( ); ( , ) ( , )/ ( , ); 1: ( , ) 0 ,break, end; 1: 1 = − = + = − = = + == = − 当a(k,k)=0，则上述消去法无法进行；或当其绝对值相对 太小可能会出现大的计算误差。选主元法可避免这种情况。下 面介绍常用的按列选主元的Gauss法
列主元Gaus法 for k=l: n-1 Lg, kk]= max( abs(a(k: n,k)); 运算量(只考虑乘 kk=k+kk-1 除运算): ta=a(k, k: n), tb=b(k) 第k步=n-k次除法 a(k,k: n)=a(kk,k: n); b(k)=b(kk) +nk次乘法 a(kk,k: n)=ta, b(kk)=tb for i=k+l:n +(n-k)(n-k)次 a(i, k)=a(i, k)/a(k, k) 乘法; b(i)=b(1)-a(i,k)·b(k); n总的乘除运算量 for j=k+ln ∑(n-k)2+2∑(m-k) k=1 em s eng C D=a(i,y-a(i, k)a(k,j) n+n-n d
end end end a i j a i j a i k a k j for j k :n b i b i a i k b k a i k a i k a k k fori k n a k k k n t a b k k t b a k k n a k k k n b k b k k t a a(k,k:n) ;t b b(k) k k k k k q k k abs a k n k for k n ( , ) ( , ) ( , ) ( , ); 1 ( ) ( ) ( , ) ( ); ( , ) ( , )/ ( , ); 1: ( , : ) ; ( ) ; ( , : ) ( , : ); ( ) ( ); ; 1; [ , ] max( ( ( : , ))); 1: 1 = − = + = − = = + = = = = = = = + − = = − 列主元Gauss 法 运算量 (只考虑乘 除运算）： 第k步=n-k次除法 + n - k次乘法 + （ n -k)*(n -k) 次 乘法 ; ( ) 31( ) 2 ( ) 33 2 11 11 2 o nn n n n k n k nk nk== + − − + − −= −= 总的乘除运算量 =
第二步:回代求解 an, n =(b-∑a(,)·x)/a(,1);=n-1 j=t+1 0%%%%%%% b(n)=b(n)/a(n,n) fori 1:-1:1 for j=i+l: n d=a+a(i2j)·b(0) e b()=(b(1)-d)/a(i2i) enc
第二步：回代求解 ( ( , ) )/ ( , ); 1:1 / ( , ); 1 = − = − = = + x b a i j x a i i i n x b a n n n j i i i j n n end b i b i d a i i end d d a i j b j for j i n d fori n b n b n a n n ( ) ( ( ) )/ ( , ); ( , ) ( ); 1: 0; 1: 1:1 ( ) ( )/ ( , ); = − = + = + = = − − = %%%%%%%%
二、LU分解法 LU分解的目的是将矩阵A转换为两个矩阵的乘积,即 A=LU,L是单位下三角矩阵,U为上三角矩阵。此时, 方程Ax=b分LUx=b分→Ly=b,Ux=y 好处是:对于线性方程组,如果需要多次求解不同的非 齐次项,此时LU分解的效率将大大超过高斯消去法。 LU分解的 MATLAB命令:[,u]=u(A)和[up]=lu(A 前面讲到的不选主元的高斯消去法和列主元高斯消去法将能实现LU 分解。 不选主元的高斯消去法用于下面两类矩阵肯定能成,即严格对角占优 矩阵或对称正定矩阵,其他矩阵就难说了 列主元高斯消去法是解决一般中小型稠密矩阵方程组最有效的方法之 。下面讲解列主元高斯消去法实现LU分解的算法
二、LU分解法 LU分解的目的是将矩阵A转换为两个矩阵的乘积，即 方程 。 是单位下三角矩阵， 为上三角矩阵。此时， Ax b LUx b Ly b U x y A LU L = = = = = , , U 好处是：对于线性方程组，如果需要多次求解不同的非 齐次项，此时LU分解的效率将大大超过高斯消去法。 LU分解的MATLAB命令：[l,u]=lu(A) 和[l,u,p]=lu(A) 前面讲到的不选主元的高斯消去法和列主元高斯消去法将能实现LU 分解。 不选主元的高斯消去法用于下面两类矩阵肯定能成，即严格对角占优 矩阵或对称正定矩阵，其他矩阵就难说了！ 列主元高斯消去法是解决一般中小型稠密矩阵方程组最有效的方法之 一。下面讲解列主元高斯消去法实现LU分解的算法