線性方程組的直接解法

1線性方程組的直接解法

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

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

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

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

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

/*backwardsubstitution*/。=

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

解方程組解step1

消元8Step2

對上三角形方程進行回代求解,得

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

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

≤n-1)

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

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

若A的所有順序主子式

/*determinantofleadingprincipalsubmatrices*/

均不為0，則高斯消元無需換行即可進行到底，得到唯一解。注：事實上，只要A

非奇異，即A1

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

-1)=0時,消元過程不能繼續(xù)進行；當akk

(k-1)

≠0時,雖然消元過程可以進行,但若

akk

(k-1)

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

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

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

算法:

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

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

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

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

Step1

尋找行號ik

,使得Step2

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

否則轉Step7

算法:

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

計算

Step4forj=k+1,…,n+1

計算

回代過程Step5Step6fori=n-1,…,1

計算

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

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

每一步不計算lik

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

變?yōu)?;把akk(k-1)

所在列的上、下元素全消為0;這種方法是不是比Gauss消去法更好?Gauss消去法過程中，消去對角線下方和上方的元素，稱這種方法為高斯-約當消去法.這種方法不用回代過程了，看上去是要好些？24運算量

/*AmountofComputation*/由于計算機中乘除/*multiplications/divisions*/

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

Gauss消去法:Stepk：設，計算因子且計算共進行n

1步(nk)次(nk)2

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

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

Gauss-Jordan消去法:

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

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

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

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

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

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

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

（計算其他元素，但少k列，k行）

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

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