解線性方程組的直接方法主元素方法課件

1第二章解線性方程組的直接方法Gauss消去法簡單易行，但其計算過程中，要求(稱為主元素)均不為零，因而適用范圍小，只適用于從1到先看一個例子。階順序主子式均不為零的矩陣A，計算實踐還表明,Gauss消去法的數(shù)值穩(wěn)定性差,當(dāng)出現(xiàn)小主元素時,會嚴(yán)重影響計算結(jié)果的精度,甚至導(dǎo)出錯誤的結(jié)果.§2主元素法1第二章解線性方程組的直接方法Gauss消去法簡單易行，但第二章解線性方程組的直接方法(2-10a)式（2-10a）中所有系數(shù)均有2位有效數(shù)字.[解]為減少誤差，計算過程中保留3位有效數(shù)字.按Gauss消去法步驟，第一次消元得同解方程組例2

求解方程組

2第二章解線性方程組的直接方法(2-10a)式（2-10a）3第二章解線性方程組的直接方法第二次消元得

回代得解容易驗證，方程組（2-10）的準(zhǔn)確解為顯然兩者相差很大.但若在解方程組前,先把方程的次序3第二章解線性方程組的直接方法第二次消元得回代得解容易4第二章解線性方程組的直接方法交換一下,如把（2-10a）改寫成

再用Gauss消去法求解，消元后得同解方程4第二章解線性方程組的直接方法交換一下,如把（2-10a）5第二章解線性方程組的直接方法產(chǎn)生上述現(xiàn)象的原因在于舍入誤差.因為按式(2-10)的方程順序進行消元時，主元回代得解與準(zhǔn)確解相同.都比較小，以它們?yōu)槌龜?shù)就增長了舍入誤差，從而導(dǎo)致計算結(jié)果不準(zhǔn)確。為了在計算過程中，抑制舍入誤差的增長,應(yīng)盡量避免小主元的出現(xiàn).如例2中第二種解法,通過交換方程次序,選取絕對值大的元素作主元.基于這種想法導(dǎo)出了主元素法.5第二章解線性方程組的直接方法產(chǎn)生上述現(xiàn)象的原因在于舍入誤6第二章解線性方程組的直接方法2.2.1列主元素法為簡便起見，我們用方程組（2-1）的增廣矩陣表示它，并直接在增廣矩陣上進行運算.6第二章解線性方程組的直接方法2.2.1列主元素法為簡7第二章解線性方程組的直接方法是在每次消元前，在要消去未知數(shù)的系數(shù)中找到絕對值最大的系數(shù)作主元，通過方程對換將其換到對角線上，然后進行消元。具體步驟如下：

第一步：首先在矩陣（2-11）的第1列中選取絕對值則中第1行與第矩陣為，然后進行第一次消元，得矩陣

最大的元，比如為將(2-11)行互換.為方便起見,記行互換后的增廣列主元素法基本思想:7第二章解線性方程組的直接方法是在每次消元前，在要消去未知8第二章解線性方程組的直接方法

第二步：在矩陣的第2列中選主元，比如使將矩陣行與第行互換，再進行第二次消元，得矩陣的第2第步：在矩陣

的第

k

列中選主元，如使將的第行與第行互換，進行第次消元.8第二章解線性方程組的直接方法第二步：在矩陣的9第二章解線性方程組的直接方法

如此經(jīng)過步，增廣矩陣（2-11）被化成上三角形，最后由回代過程求解。在上述過程中，主元是按列選取的，列主元素法由此得名.例2中的第二種解法就是按列主元素法進行的.2.2.2全主元素法如果不是按列選主元，而是在全體待選系數(shù)中選取主元，則得到全主元素法，其計算過程如下：p119第二章解線性方程組的直接方法如此經(jīng)過步，增廣矩陣（2-10第二章解線性方程組的直接方法第一步：在全體系數(shù)值最大的元作為主元，并通過行與列的互換把它換到中選取絕對的位置，然后進行第一次消元,得到矩陣第步：在矩陣的右下方階子矩陣的所有元素中,選取絕對值最大的元作為主元,并通過行與列的互換將它換到的位置，然后進行第次消元.經(jīng)過次消元后,得到與方程組(2-1)同解的上三角形方程組,再由回代過程求解.10第二章解線性方程組的直接方法第一步：在全體系數(shù)值最大的11第二章解線性方程組的直接方法例3

用主元素法求解線性方程組計算過程保留三位小數(shù)。[解]按列主元素法，求解過程如下:

p13p911第二章解線性方程組的直接方法例3用主元素法求解線性12第二章解線性方程組的直接方法12第二章解線性方程組的直接方法13第二章解線性方程組的直接方法由回代過程得解按全主元素法，求解過程如下:p1113第二章解線性方程組的直接方法由回代過程得解按全主元素法141415第二章解線性方程組的直接方法由回代過程得解

例3的計算結(jié)果表明，全主元素法的精度優(yōu)于主元素法,這是由于全主元素是在全體系數(shù)中選主元，故它對控制同解方程組為15第二章解線性方程組的直接方法由回代過程得解例316第二章解線性方程組的直接方法舍入誤差十分有效。但全主元素法在計算過程中，需同時作行與列的互換，因而程序比較復(fù)雜，計算時間較長.列主元素法的精度雖稍低于全主元素法，但其計算簡單,工作量大為減少,且計算經(jīng)驗與理論分析均表明,它與全主元素法同樣具有良好的數(shù)值穩(wěn)定性，故列主元素法是求解中小型稠密線性方程組的最好方法之一.16第二章解線性方程組的直接方法舍入誤差十分有效。但全主元17第二章解線性方程組的直接方法§2.3直接三角分解法2.3.1Gauss消去法的矩陣形式如果用矩陣形式表示，Gauss消去法的消元過程是對方程組（2-1）的增廣矩陣[A，b]進行一系列行初等變換，將系數(shù)矩陣A化成上三角形矩陣的過程.

將系數(shù)矩陣A化成上三角形矩陣的過程，也等價于用一串初等矩陣去左乘增廣矩陣，因此消元過程可以通過矩陣運算來表示。

我們知道,對矩陣進行一次初等行變換,相當(dāng)于用相應(yīng)的初等矩陣去左乘原來的矩陣.17第二章解線性方程組的直接方法§2.3直接三角分解法218的系數(shù)矩陣A的順序主子式不為零在Gauss消去法中,第一次消元時等價于用單位下三角陣設(shè)方程組18的系數(shù)矩陣A的順序主子式不為零在Gauss消去法中,第一19第二章解線性方程組的直接方法其中

（2-12）左乘矩陣即19第二章解線性方程組的直接方法其中（2-12）左乘矩陣20進行第二次消元時等價于用矩陣左乘其中于是有20進行第二次消元時等價于用矩陣左乘其中于是有第二章解線性方程組的直接方法一般地，第k次消元等價于用矩陣其中經(jīng)過次消元后得到（2-13）左乘矩陣2121第二章解線性方程組的直接方法一般地，第k次消元等價于用矩陣22第二章解線性方程組的直接方法因為的逆矩陣存在。容易求出均為非奇異陣，故它們22第二章解線性方程組的直接方法因為的逆矩陣存在。容易求出23第二章解線性方程組的直接方法

（2-14）

令2323第二章解線性方程組的直接方法（2-14）令2324于是有

(2-15)即（2-16）24于是有(2-15)即（2-16）25第二章解線性方程組的直接方法其中為單位下三角矩陣，

為上三角矩陣。這說明，消元過程實際上是把系數(shù)矩陣A分解成單位下三角陣與上三角矩陣的乘積的過程。25第二章解線性方程組的直接方法其中為單位下三角矩陣，為26第二章解線性方程組的直接方法上述分解稱為杜利特爾（Doolittle）分解，也稱為的問題就變得十分容易，它等價與求解兩個三角形方程組和分解.當(dāng)系數(shù)矩陣進行三角分解后，求解方程組因此，解線性方程組問題可轉(zhuǎn)26第二章解線性方程組的直接方法上述分解稱為杜利特爾（Do27第二章解線性方程組的直接方法化為矩陣的三角分解問題。2.3.2矩陣的三角分解正如Gauss消去法要在一定條件下才能進行到底一樣矩陣A也必須滿足一定條件才能進行三角分解.定理2.１設(shè)Ａ為n階方陣，若Ａ的順序主子式［證明］當(dāng)均不為零，則矩陣Ａ存在唯一的Doolittle分解。時，因為由３.１段的討論，存在矩陣p3327第二章解線性方程組的直接方法化為矩陣的三角分解問題。228第二章解線性方程組的直接方法其中,使得28第二章解線性方程組的直接方法其中,使得29第二章解線性方程組的直接方法由行列式的性質(zhì)易得

的各階順序主子式滿足假定結(jié)論對j=k-1成立,即29第二章解線性方程組的直接方法由行列式的性質(zhì)易得的各階30第二章解線性方程組的直接方法且于是有,因為故存在矩陣30第二章解線性方程組的直接方法且于是有,因為故存在矩陣31第二章解線性方程組的直接方法其中

，使得

且31第二章解線性方程組的直接方法其中，使得且32第二章解線性方程組的直接方法

,使得其中為單位下三角矩陣，為上三角矩陣。存在性得證。按歸納法原理，存在初等矩陣由式（2-15）得32第二章解線性方程組的直接方法,使得其中為單位下三33第二章解線性方程組的直接方法由于單位下（上）三角陣的逆仍是單位下（上）三角陣,所以對A是奇異的情況，可參考[1].惟一性。設(shè)矩陣A有兩種Doolittle分解當(dāng)A非奇異時，均為非奇異矩陣.于是由式（2-17），有上（下）三角陣的乘積仍為上（下）三角陣，故有(2-17)p2733第二章解線性方程組的直接方法由于單位下（上）三角陣的逆34第二章解線性方程組的直接方法兩個矩陣相等就是他們的對應(yīng)元素都相等，比較A與下面討論如何如何對A進行LU分解.LU的對應(yīng)元素，即可得出L,U中元的計算公式.A=LU,即由矩陣的乘法法則，得34第二章解線性方程組的直接方法兩個矩陣相等就是他們的對應(yīng)35設(shè)已定出U的第一行至第r-1行元素,與L的第一列至第r-1列元素,(注意到當(dāng)

)故有又故有(U的第r行)(L的第r列)35設(shè)已定出U的第一行至第r-1行元素,與L的第一列(注意36第二章解線性方程組的直接方法

由此可得計算和的公式（2-18）36第二章解線性方程組的直接方法由此可得計算和的公式（237第二章解線性方程組的直接方法計算過程應(yīng)按第1行,第1列,第2行，第2

列，...的順序進行.2.計算U的第r行，L的第r列計算U的第1行,L的第1列具體步驟如下：37第二章解線性方程組的直接方法計算過程應(yīng)按第1行,第1列38第二章解線性方程組的直接方法

的三角分解。例4

求矩陣[解]按式（2-18）38第二章解線性方程組的直接方法的三角分解。例4求矩陣39第二章解線性方程組的直接方法

所以39第二章解線性方程組的直接方法40第二章解線性方程組的直接方法兩個矩陣相等就是他們的對應(yīng)元素都相等，比較A與下面討論如何如何對A進行LU分解.LU的對應(yīng)元素，即可得出L,U中元的計算公式.A=LU,即由矩陣的乘法法則，得40第二章解線性方程組的直接方法兩個矩陣相等就是他們的對應(yīng)41第二章解線性方程組的直接方法計算過程應(yīng)按第1行,第1列,第2行，第2

列,...的順序進行.2.計算U的第r行，L的第列r計算U的第1行,L的第1列具體步驟如下：41第二章解線性方程組的直接方法計算過程應(yīng)按第1行,第1列42第二章解線性方程組的直接方法緊湊格式。根據(jù)式（2-18）的特點，矩陣的三角分解可按以下格式及順序進行。這種格式既便于記憶，又便于計算,稱為表2-142第二章解線性方程組的直接方法緊湊格式。根據(jù)式（2-1843第二章解線性方程組的直接方法框從外到內(nèi)進行。每一框中先算行，從左向右依次計算；再算列，自上而下求2.計算方法：按行計算時，需將所求元的對應(yīng)元逐項減去所在行左面各框的元乘以所在列上面各框相應(yīng)的元按列計算時，在作上述運算后還需除以所在框的對角元例4中矩陣說明：計算順序：將按表2-1列好，計算時按的三角分解按43第二章解線性方程組的直接方法框從外到內(nèi)進行。每一框中先44

(2)2

(2)2

(3)3

表2-2緊湊格式計算，結(jié)果見下表。第二章解線性方程組的直接方法44(2)2(2)2(3)345第二章解線性方程組的直接方法所以即由2.3.3直接三角分解法如果線性方程組的系數(shù)矩陣已進行三角分解則解方程組兩個三角形方程組等價于求解45第二章解線性方程組的直接方法所以即由2.3.3直接三46第二章解線性方程組的直接方法可求出(2-20)(2-19)46第二章解線性方程組的直接方法可求出(2-20)(2-147第二章解線性方程組的直接方法再由解得(2-22)(2-21)47第二章解線性方程組的直接方法再由解得(2-22)(2-48第二章解線性方程組的直接方法容易看出,式（2-20）與式（2-18）的運算規(guī)律相同,2-1的最后一列，按的計算方法即

表2-3是求解線性方程組的緊湊格式，其計算順序與故在利用三角分解求解方程組時，只需把右端向量計算方法與三角分解相同。按表2-3計算后，再按式列在表(2-22)即可求出方程組的解可求出48第二章解線性方程組的直接方法容易看出,式（2-20）與49第二章解線性方程組的直接方法

表2-349第二章解線性方程組的直接方法表2-350例：用杜利特爾分解法求解線性方程組解：設(shè)50例：用杜利特爾分解法求解線性方程組解：設(shè)51第二章解線性方程組的直接方法

按式（2-18）51第二章解線性方程組的直接方法按式（2-18）52第二章解線性方程組的直接方法

所以