線性方程組的直接解法

1線性方程組的直接解法

Gauss消去法直接三角分解方法方程組的性態(tài)與誤差估計(jì)2在自然科學(xué)與工程技術(shù)中，很多問(wèn)題的解決常常歸結(jié)為解線性方程組的問(wèn)題：很多數(shù)值計(jì)算方法到最后也涉及到線性方程組的求解問(wèn)題：如電學(xué)中的網(wǎng)絡(luò)問(wèn)題，機(jī)械和建筑結(jié)構(gòu)的設(shè)計(jì)和計(jì)算等。

如求樣條插值的M和m的關(guān)系式，解曲線擬合的法方程，求矩陣特征值的反冪法等問(wèn)題。電子計(jì)算機(jī)線性方程組{稠密和稀疏（按系數(shù)矩陣含零元多少分）高階和低階（按階數(shù)的高低分）對(duì)稱(chēng)正定、對(duì)角占優(yōu)等（按系數(shù)矩陣的形狀性質(zhì)分）基本解法{直接法（通過(guò)有限步計(jì)算得到精確解，適用于低階、大型帶型陣）

迭代法（通過(guò)逐次迭代逼近得到近似解，適用于大型稀疏、非帶型陣）線性方程組及方法分類(lèi)4求解線性方程組：對(duì)此方程組進(jìn)行求解有兩種方法：采用Cramer法則、消元法。5Cramer(克萊姆)法則

對(duì)于20階的線性方程組,若用Cramer法則求解,其乘、除運(yùn)算次數(shù)為9.7*1020,用一億次/秒的計(jì)算機(jī),要30.8萬(wàn)年！若用高斯消去法進(jìn)行數(shù)值求解，乘、除運(yùn)算只需約3060次。定理：如果線性方程組則方程組有唯一解：其中Ak是將A的第k列元素依次換成常數(shù)項(xiàng)b1,…,bn得到的行列式。的系數(shù)行列式非零，即計(jì)算量大6Gauss消去法一、高斯順序消去法思路首先將A化為上三角陣

/*upper-triangularmatrix*/，再回代求解

/*backwardsubstitution*/。=

是一種古老的求解線性方程組的方法,按自然順序進(jìn)行消元的方法.7例1

解方程組解step1

消元8Step2

對(duì)上三角形方程進(jìn)行回代求解,得

下面我們來(lái)一般性地討論求解n階線性方程組的高斯順序消去法.9消元Step1：設(shè)，計(jì)算因子將增廣矩陣/*augmentedmatrix*/第i行l(wèi)i1

第1行，得到與(1)式等價(jià)的方程組10Step2：一般第k次消元(1≤k

≤n-1)

1112Step3：繼續(xù)上述過(guò)程,且設(shè)aii（i-1）≠0(i=1,2,…,n-1),直到完成第n-1

次消元,最后得到與A(0)x=b(0)等價(jià)的三角形方程組A(n-1)x=b(n-1).將(1)式化為(2)式的過(guò)程稱(chēng)為消元過(guò)程.forforforGauss消去法的消元過(guò)程算法Gauss消去法工作量為14回代定理

若A的所有順序主子式

/*determinantofleadingprincipalsubmatrices*/

均不為0，則高斯消元無(wú)需換行即可進(jìn)行到底，得到唯一解。注：事實(shí)上，只要A

非奇異，即A1

存在，則可通過(guò)逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。15高斯順序消去法流程圖FTk=k+1FT消元過(guò)程回代過(guò)程16順序消去法的缺點(diǎn)為：當(dāng)主元akk(k

-1)=0時(shí),消元過(guò)程不能繼續(xù)進(jìn)行；當(dāng)akk

(k-1)

≠0時(shí),雖然消元過(guò)程可以進(jìn)行,但若

akk

(k-1)

≈0時(shí),時(shí),會(huì)出現(xiàn)很小的數(shù)作除數(shù)的現(xiàn)象,使舍入誤差增大,導(dǎo)致解的嚴(yán)重失真.17例2解方程組/*精確解為*/用Gauss消去法計(jì)算：二、主元素消去法18

由上例可以看出,為提高算法的數(shù)值穩(wěn)定性,應(yīng)選取絕對(duì)值盡可能大的元素作主元.按列部分選主元的消去法也稱(chēng)列主元消去法。19解：20一些特殊情況,主元就在對(duì)角線上,不需選主元.如元素滿足如下條件的矩陣

即對(duì)角線上每一元素的絕對(duì)值均大于同行其他各元素絕對(duì)值之和,這樣的矩陣稱(chēng)為按行嚴(yán)格對(duì)角占優(yōu)矩陣,簡(jiǎn)稱(chēng)嚴(yán)格對(duì)角占優(yōu)矩陣.例如性質(zhì)：嚴(yán)格對(duì)角占優(yōu)矩陣必定非奇異.

算法:

Gauss列主元消去算法求方程組Ax=b

的解.輸入:增廣矩陣An(n+1)=（A|b）.輸出:

近似解xk=ak,n+1(k=1,2,…,n)

或失敗信息.消元過(guò)程fork=1,2,…,n-1doStep1-Step4

Step1

尋找行號(hào)ik

,使得Step2

如果，則交換第k行和ik行；

否則轉(zhuǎn)Step7

算法:

Gauss列主元消去算法（續(xù)）Step3fori=k+1,…,n

計(jì)算

Step4forj=k+1,…,n+1

計(jì)算

回代過(guò)程Step5Step6fori=n-1,…,1

計(jì)算

Step7Output(系數(shù)矩陣奇異);/*不成功*/STOP.

編程時(shí)此處調(diào)用回代算法23三、高斯-約當(dāng)消去法（求矩陣逆）與Gauss消去法的主要區(qū)別：

每一步不計(jì)算lik

，而是先將當(dāng)前主元akk(k-1)

變?yōu)?;把a(bǔ)kk(k-1)

所在列的上、下元素全消為0;這種方法是不是比Gauss消去法更好?Gauss消去法過(guò)程中，消去對(duì)角線下方和上方的元素，稱(chēng)這種方法為高斯-約當(dāng)消去法.這種方法不用回代過(guò)程了，看上去是要好些？24運(yùn)算量

/*AmountofComputation*/由于計(jì)算機(jī)中乘除/*multiplications/divisions*/

運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)加減/*additions/subtractions*/運(yùn)算的時(shí)間，故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)乘除的次數(shù)，而且通常以乘除次數(shù)的最高次冪為運(yùn)算量的數(shù)量級(jí)。

Gauss消去法:Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行n

1步(nk)次(nk)2

次(nk)次(nk)(nk+2)

次消元時(shí)乘除次數(shù)：1次(ni+1)次回代時(shí)乘除次數(shù)：Gauss消去法的總乘除次數(shù)為，運(yùn)算量為級(jí)。25

Gauss-Jordan消去法:

運(yùn)算量約為。故通常只用于求逆矩陣，而不用于解方程組。求逆矩陣即。Gauss-Jordan消元法求矩陣的逆

Gauss消元法有許多變形，列主元素法是其中之一，在列主元法的基礎(chǔ)上還可對(duì)算法進(jìn)行如下的修改：在消元過(guò)程中選主元后，先將主元化為1，然后將主元所在列上，下方各元素均化為0，這樣消元的結(jié)果使系數(shù)矩陣化為了單位陣，無(wú)需回代就得到了原方程之解，這種無(wú)回代過(guò)程的列主元素法稱(chēng)為Gauss-Jordan消元法。

Gauss-Jordan消元法比順序消去法計(jì)算量大一點(diǎn)，實(shí)踐中使用不多，但用它求逆陣卻十分方便。因?yàn)橄^(guò)程實(shí)質(zhì)上就是對(duì)系數(shù)矩陣A實(shí)行初等變換，將A化為單位陣，相當(dāng)于對(duì)A左乘了一系列的初等變換陣M1，M2，…，Mn-1，Mn，使：緊接下屏Gauss-Jordan消元法求矩陣的逆（續(xù)1）這表明同樣的一組初等變換在將A化為I的同時(shí)，可將I化為A1，即有：

因此，以Gauss-Jordan消元法求A的逆陣，就是要找到Mi(i=1,2,…,n)，以它們逐個(gè)左乘(A,I),逐列將A的對(duì)角線上的元素化為1，而其余元素化為0，最終將A化為單位陣，則I化為A的逆陣A1。Gauss-Jordan消元法求矩陣的逆（續(xù)2）設(shè)增廣陣為：

這里aij(1)=a1j，上述aij(2)的計(jì)算與Gauss消元法基本上相同，僅僅由于m11與Gauss消元法中的乘數(shù)l11不相同引起第一行元素a1j(2)與aij(2)計(jì)算不相同，假若把增廣陣中I的各列視為A的第n+1列，第n+2列，…，那么上述計(jì)算公式中的第二個(gè)下標(biāo)可擴(kuò)充到2n。Gauss-Jordan消元法求矩陣的逆（續(xù)3）…Gauss-Jordan消元法求逆陣(續(xù)4)Gauss-Jordan消元法求逆陣(續(xù)5)Gauss-Jordan消元法求逆陣(續(xù)6)1……設(shè)經(jīng)過(guò)k–1步后得到：Gauss-Jordan消元法求逆陣(續(xù)7)其中：Gauss-Jordan消元法求逆陣(續(xù)8)完成n步消元后，A1放在原A的位置。

Gauss-Jordan法求逆陣的具體步驟

按上述緊縮存貯原則，可節(jié)省存貯單元，同時(shí)還使得整個(gè)計(jì)算更簡(jiǎn)單了?？煽偨Y(jié)求逆步驟如下：上述1，2是求第k列元素，構(gòu)成Mk（即求主列）

（計(jì)算其他元素，但少k列，k行）

用上述Gauss-Jordan法求逆陣，計(jì)算量約為n3，是Gauss消元法的3倍，為保證方法穩(wěn)定性，還可選列主元，若仍按上述緊縮存貯原則，則最后需按行交換的相反次序作列交換才能得到A1。

Gauss-Jordan法求逆陣的具體步驟(續(xù))Gauss-Jordan法求逆陣舉例例解：按緊縮存貯方式，逐次計(jì)算結(jié)果與存