高斯消去法ppt課件.ppt

《高斯消去法ppt課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第五章解線性方程組的直接方法5.1高斯消去法5.2高斯主元素消去法5.4誤差分析5.3矩陣的三角分解7/28/2021數(shù)值分析【本章重點(diǎn)】1．Gauss消去法和列主元消去法及其實(shí)現(xiàn)條件。2．矩陣的三角分解，含LU分解和LLT分解及三對角方程組的追趕法。3．向量和矩陣范數(shù)的定義及性質(zhì)。4．矩陣條件數(shù)及病態(tài)矩陣定義和解方程組直接法的誤差估計(jì)。在自然科學(xué)和工程技術(shù)中許多問題的解決轉(zhuǎn)化為解線性方程組，而這些方程組的系數(shù)矩陣大致分為兩種，一種是低階稠密矩陣，一種是高階稀疏矩陣。引言解線性方程組的數(shù)值解也有兩種：直接法，就是經(jīng)過有限步算

2、術(shù)運(yùn)算，可以求得線性方程組的解，但實(shí)際計(jì)算時有舍入誤差的存在和影響，所以求得的結(jié)果也只能是近似解對低階稠密矩陣和部分大型稀疏矩陣有效。迭代法，就是用某種極限過程去逐步逼近精確解，是解決大型稀疏矩陣的重要方法。從一個初始向量出發(fā)，按照一定的迭代格式，構(gòu)造出一個趨向于真解的無窮序列。7/28/2021數(shù)值分析高斯消去法是一個古老的求解線性方程組的方法，但由于它的改進(jìn)、變形得到的選主元素消去法、三角分解法仍是在計(jì)算機(jī)上求解系數(shù)矩陣為中、低階稠密矩陣的線性方程組常用的有效方法，所以本節(jié)介紹這一方法?！?高斯消去法用高斯消去法求解n階線性方

3、程組Ax=b的基本思想是在逐步消元的過程中，把方程組的系數(shù)矩陣化為上三角矩陣，從而將原方程組約化為容易求解的等價(jià)三角方程組，然后進(jìn)行回代求解。一、高斯消去法7/28/2021數(shù)值分析例1用消去法求解方程組11164-152-21111164-150-4-1-1111164-1500-2-6還原為方程組（消元過程）（回代過程）x3=3，x2=2，x1=1設(shè)有方程組改寫成矩陣形式：簡記為：一般線性方程組的高斯消去法7/28/2021數(shù)值分析將原方程組記為其中則第一步（k=1)，若a11不等于0，則可以計(jì)算乘數(shù)用-mi1乘方程組的第一個

4、方程加到第i個方程，則原方程組同解方程組為：其中簡記為第二步，設(shè)經(jīng)過k-1次消元后的同解方程組為設(shè)計(jì)算乘數(shù)用-mik乘上面的線性方程組的第k個方程加到第i個方程，可以消去xk元,得到同解方程組其中7/28/2021數(shù)值分析重復(fù)上述過程，可以將方程組化為等價(jià)的簡單方程組其中為上梯形陣。當(dāng)m=n時，與原方程組等價(jià)的方程組為即（消元過程）由上述方程組很快可以求出：（回代過程）乘除運(yùn)算量乘除運(yùn)算量：由于計(jì)算機(jī)中做乘除運(yùn)算的時間遠(yuǎn)遠(yuǎn)超過做加減運(yùn)算時間，故估計(jì)運(yùn)算量時，往往只估計(jì)乘除的次數(shù)。第k步：消去第k列設(shè)，計(jì)算計(jì)算(i=k+1,…,n)

5、回代求解：(i=k+1,…,n)n–k次(n–k)2次n–k次n(n+1)/2次高斯消去法總的乘除運(yùn)算量為：7/28/2021定理1設(shè)Ax=b,其中A∈Rn×n(1)如果則可通過高斯消去法，將方程組化為等價(jià)三角形方程組，計(jì)算公式為：(a)消元計(jì)算(k=1,2,…,n)(b)回代計(jì)算(2)如果系數(shù)矩陣A為非奇異矩陣則可通過高斯消去法與初等行變換方法，將方程組約化為三角形方程組。定理2約化的主元素的充要條件是矩陣A的順序主子式即證明略推論如果矩陣A的順序主子式則functionx=gauss(A,b)n=length(b);x=zer

6、os(n,1);fori=1:n-1%消元過程fork=i+1:nforj=i+1:nA(k,j)=A(k,j)+A(i,j)*(-A(k,i)/A(i,i));endb(k)=b(k)+b(i)*(-A(k,i)/A(i,i));A(k,i)=0;endenddisp(A)disp(b)pausex(n)=b(n)/A(n,n);fori=n-1:-1:1%回代過程sum=0;forj=i+1:nsum=sum+A(i,j)*x(j);endx(i)=(b(i)-sum)/A(i,i);end程序設(shè)計(jì)A=[111;04-1;2-

7、21];b=[651]';x=gauss(A,b)程序執(zhí)行消元后的A11104-100-2消元后的b65-6x=123二、矩陣的三角分解由上面消去法的分析知，若方程組的系數(shù)矩陣A的順序主子式不等于0，高斯消元的過程是作一系列初等行變換，等價(jià)于矩陣A左乘一個初等矩陣。一般第k步消元，A(k)化為A(k+1),b(k)化為b(k+1),相當(dāng)于所以第一次消元可表示為：其中：重復(fù)以上過程，最后得到令為單位下三角矩陣。定理2（矩陣的LU分解）設(shè)A為一個n階矩陣，若其順序主子式Di≠0(i=1,2,…,n)。則A可分解為一個單位下三角形矩陣L

8、和一個上三角形矩陣U的乘積，且這種分解是唯一的。證明：存在性由定理1可得；唯一性：設(shè)有兩種分解，即A=LU=L1U1所以由L可逆，U1可逆，知L-1L1=UU1-1左邊為單位下三角形矩陣，右邊為上三角形矩陣，所以均為單位矩陣，即有L=L1,U=U1