解線性方程組的直接方法ppt課件

1、1第二章第二章 解線性方程組的直接方法解線性方程組的直接方法第二章第二章 解線性方程組的直接方法解線性方程組的直接方法2.1 高斯高斯Gauss消去法消去法 2.2 主元素法主元素法2.3 直接三角分解法直接三角分解法2.4 平方根法與改良的平方根法平方根法與改良的平方根法2.5 誤差分析誤差分析 2第二章第二章 解線性方程組的直接方法解線性方程組的直接方法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111在科學(xué)研討和工程技術(shù)所提出的計(jì)算問題中，經(jīng)常會遇在科學(xué)研討和工程技術(shù)所提出的計(jì)算問題中，經(jīng)常會遇到線性方程組的求解問題，如計(jì)算插值函數(shù)與擬

2、合函數(shù)到線性方程組的求解問題，如計(jì)算插值函數(shù)與擬合函數(shù), ,構(gòu)造求解微分方程的差分格式等，都包含了解線性方程構(gòu)造求解微分方程的差分格式等，都包含了解線性方程組的問題。因此，線性方程組的解法在數(shù)值計(jì)算中占有組的問題。因此，線性方程組的解法在數(shù)值計(jì)算中占有極重要的位置。極重要的位置。設(shè)設(shè)n n階線性方程組階線性方程組(2-1)p93第二章第二章 解線性方程組的直接方法解線性方程組的直接方法bAx 111212122212,nnnnnnaaaaaaAaaa ,21nxxxxnbbbb21其矩陣方式為其矩陣方式為 (2-2)其中其中第二章第二章 解線性方程組的直接方法解線性方程組的直接方法0det()

3、,A det()(1,2, )det( )iiAxinAiA1nn!) 1(nn30n假設(shè)線性方程組假設(shè)線性方程組2-12-1的系數(shù)行列式不為零，即的系數(shù)行列式不為零，即法那么，其解法那么，其解為為其中其中向量所得的矩陣。這種方法需求計(jì)算向量所得的矩陣。這種方法需求計(jì)算個個n列式并作列式并作次除法，而每個次除法，而每個n 階行列式計(jì)算需作階行列式計(jì)算需作次乘法，計(jì)算量非常驚人。如次乘法，計(jì)算量非常驚人。如那么該方程組有獨(dú)一解。由克萊姆那么該方程組有獨(dú)一解。由克萊姆(carmer)為用方程組為用方程組2-12-1的右端向量的右端向量b b替代替代A A中第中第i i列列階行階行時時,就就5第二章

4、第二章 解線性方程組的直接方法解線性方程組的直接方法351038. 2次乘法?？梢姶纬朔ā？梢奀ramer法那么在實(shí)際上法那么在實(shí)際上絕對正確的絕對正確的, ,但當(dāng)?shù)?dāng)n n較大時，在實(shí)踐計(jì)算中卻是不可行的較大時，在實(shí)踐計(jì)算中卻是不可行的. .解線性方程組的方法大致可分為兩類：解線性方程組的方法大致可分為兩類：直接方法和直接方法和迭代法。直接方法是指假設(shè)計(jì)算過程中不產(chǎn)生舍入誤差迭代法。直接方法是指假設(shè)計(jì)算過程中不產(chǎn)生舍入誤差,經(jīng)過有限次運(yùn)算可求得方程組的準(zhǔn)確解的方法。經(jīng)過有限次運(yùn)算可求得方程組的準(zhǔn)確解的方法。是從解的某個近似值出發(fā)，經(jīng)過構(gòu)造一個無窮序列去逼近是從解的某個近似值出發(fā)，經(jīng)過構(gòu)造一個

5、無窮序列去逼近準(zhǔn)確解的方法。普通地，有限步內(nèi)得不到準(zhǔn)確解。準(zhǔn)確解的方法。普通地，有限步內(nèi)得不到準(zhǔn)確解。本章引見幾種常用的解線性方程組的直接方法及有關(guān)本章引見幾種常用的解線性方程組的直接方法及有關(guān)問題。在以下文中問題。在以下文中, ,如不作特別闡明如不作特別闡明, ,均假設(shè)方程組均假設(shè)方程組2-12-1的系數(shù)矩陣非奇特，方程組存在獨(dú)一解。的系數(shù)矩陣非奇特，方程組存在獨(dú)一解。需作約需作約迭代法迭代法6第二章第二章 解線性方程組的直接方法解線性方程組的直接方法不難想象，假設(shè)線性方程組的系數(shù)矩陣為三角形矩陣不難想象，假設(shè)線性方程組的系數(shù)矩陣為三角形矩陣, ,那么該方程組極易求解。如今計(jì)算機(jī)上常用的直接

6、方法大那么該方程組極易求解。如今計(jì)算機(jī)上常用的直接方法大多是先將方程組多是先將方程組2-12-1變構(gòu)成等價的三角形方程組變構(gòu)成等價的三角形方程組, ,然然后求解后求解. . 1 高斯高斯Gauss消去法消去法2.1.1 Gauss消去法消去法 化線性方程組為等價的三角形方程組的方法有多種，化線性方程組為等價的三角形方程組的方法有多種，由此導(dǎo)出不同的直接方法，其中由此導(dǎo)出不同的直接方法，其中GaussGauss消去法是最根本消去法是最根本的一種方法的一種方法. .先舉例闡明先舉例闡明GaussGauss消去法的根本思想和過程。消去法的根本思想和過程。7第二章第二章 解線性方程組的直接方法解線性方

7、程組的直接方法-15-318-3)-(2 1533 -126321321321xxxxxxxxx931721 57- 9-15-63232321xxxxxxx1)32( 例例1 1 解線性方程組解線性方程組解解 先消去方程組先消去方程組2-3中后兩個方程中的變量中后兩個方程中的變量 x1,得同解方程組得同解方程組8第二章第二章 解線性方程組的直接方法解線性方程組的直接方法2x123233+=6-15-9= -57 2266=55xxxxxx33,x 11x再消去方程組再消去方程組(2-3)1中第三個方程中的變量中第三個方程中的變量(2-3)的同解方程組的同解方程組, ,又得又得(2-3)2這是

8、一個三角形方程組。由這是一個三角形方程組。由2-3)2容易解出容易解出22,x 9第二章第二章 解線性方程組的直接方法解線性方程組的直接方法)1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11nnnnnnnnnnbxaxaxabxaxaxabxaxaxa上述求解過程的根本思想是：先逐次消去變量上述求解過程的根本思想是：先逐次消去變量, ,將方將方程化成同解的上三角形方程組，此過程稱為消元過程程化成同解的上三角形方程組，此過程稱為消元過程. .然然后按方程相反順序求解上三角形方程組，得到原方程組的后按方程相反順序求解上三角形方程組，得到

9、原方程組的解解, ,此過程稱為回代過程此過程稱為回代過程. .這種方法稱為這種方法稱為GaussGauss消去法消去法, ,它由它由消元過程和回代過程構(gòu)成。消元過程和回代過程構(gòu)成。為后面符號一致同見，將方程組為后面符號一致同見，將方程組2-1改寫成以下改寫成以下方式方式(2-4)p210第二章第二章 解線性方程組的直接方法解線性方程組的直接方法)1()1(bxAbbAA)1()1(,0)1(11a), 3 , 2(/)1(11)1(11niaalii), 3 , 2(1nili簡記為簡記為,其中其中普通地，求解普通地，求解n n階方程組階方程組2-12-1的的GaussGauss法的步驟如下：

10、法的步驟如下：消元過程消元過程第一步：設(shè)第一步：設(shè),記記將式將式2-4中第中第 i 個方程減去第個方程減去第1 1個方程乘以個方程乘以完成第一次消元完成第一次消元, ,得得(2-4)(2-4)的同解方程組的同解方程組)2()2(2)2(2)2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnbxaxabxaxabxaxaxa(2-5)11第二章第二章 解線性方程組的直接方法解線性方程組的直接方法(2)(1)(1)11,ijijijaal a)2()2(bxA0)2(22a), 3(/)2(22)2(22niaalii2(3, )ilin其中其中方程組方程組2-5

11、簡記為簡記為第二步：設(shè)第二步：設(shè)第第k k步：設(shè)第步：設(shè)第k-1k-1次消元完成后得方程組次消元完成后得方程組2-42-4的同的同,記記將式將式2-5中第中第i個方程減去第個方程減去第2個方程乘以個方程乘以完成第二次消元完成第二次消元.解方程組為解方程組為(2)(1)(1)11( ,2,3, )iiibbl bi jn 12第二章第二章 解線性方程組的直接方法解線性方程組的直接方法(1)(1)(1)(1)(1)111122111(2)(2)(2)(2)222222( )( )( )( )( )( )kknnkknnkkkkkkknnkkkknkknnnna xa xa xa xbaxaxaxb

12、axaxbaxaxb (2-6)()(kkbxA0)(kkka), 1(/)()(nkiaalkkkkikik將式將式2-6中第中第i個方程減去第個方程減去第k個方程乘以個方程乘以簡記為簡記為設(shè)設(shè),記記13第二章第二章 解線性方程組的直接方法解線性方程組的直接方法), 1(nkilik,完成第完成第k次消元，得同解方程組次消元，得同解方程組(1)(1)(1)(1)(1)(1)111122111111(2)(2)(2)(2)(2)222221122( )( )( )( )11(1)(1)(1)11111(1kkkknnkkkknnkkkkkkkkkkknnkkkkkkkknnknka xa xa

13、 xaxa xbaxaxaxaxbaxaxaxbaxaxba1)(1)(1)1kkkknnnnxaxb (2-7)14第二章第二章 解線性方程組的直接方法解線性方程組的直接方法 1kkkijijikkjaal a,1n其中其中按上述作法，完成按上述作法，完成次消元后次消元后, ,方程組方程組(2-1)(2-1)化成同解化成同解的上三角形方程組的上三角形方程組(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333( )( ) nnnnnnnnnnnnaxaxaxaxbaxaxaxbaxaxbaxb(2-8) 11kkkiiikkb

14、bl bi, jk,n 15第二章第二章 解線性方程組的直接方法解線性方程組的直接方法( )( ) nnAxb( )( )( )( )( )1= / = ( ) / ( =1,2,1)nnnnnnnkkkkkkllkkl kxbaxbaxak nn 簡記為簡記為按變量的逆序逐漸回代得方程組按變量的逆序逐漸回代得方程組2-1的解。的解。 (2-9) 回代過程回代過程16第二章第二章 解線性方程組的直接方法解線性方程組的直接方法,),(),(1nbbbaATnij. 1k0kkanki, 1ikikiikkkikbbabaaa/nkj, 1ijkjikijaaaa算法算法2.1置置2.假設(shè)假設(shè)，轉(zhuǎn)

15、，轉(zhuǎn)3；否那么輸出失敗信息，停機(jī)。；否那么輸出失敗信息，停機(jī)。置置 對對1.輸入輸入3.對對置置17第二章第二章 解線性方程組的直接方法解線性方程組的直接方法1,knkk10,nna nnnnbab/1 , 2, 1nnknklkkklklkbabab1/ )(,xb 4.假設(shè)假設(shè)轉(zhuǎn)轉(zhuǎn)5 5；否那么；否那么,轉(zhuǎn)轉(zhuǎn)2。輸出失敗信息，停機(jī)；否那么，置輸出失敗信息，停機(jī)；否那么，置6.對對置置 7.輸出輸出停機(jī)。停機(jī)。5.假設(shè)假設(shè)18第二章第二章 解線性方程組的直接方法解線性方程組的直接方法kn) 1)(knkn) 1(31)(211nnknknnk) 1(2)-(11nnknnk 除法次數(shù)除法次數(shù)

16、2.1.2 Gauss消去法的計(jì)算量消去法的計(jì)算量由于計(jì)算機(jī)作乘除運(yùn)算所需時間遠(yuǎn)大于作加減運(yùn)算由于計(jì)算機(jī)作乘除運(yùn)算所需時間遠(yuǎn)大于作加減運(yùn)算所需時間，故我們只討論乘除運(yùn)算量所需時間，故我們只討論乘除運(yùn)算量. .k由消去法步驟知，在進(jìn)展第由消去法步驟知，在進(jìn)展第次消元時，需作除法次消元時，需作除法次次, ,乘法乘法次，故消元過程中乘除運(yùn)次，故消元過程中乘除運(yùn)算總量為算總量為乘法次數(shù)乘法次數(shù)19第二章第二章 解線性方程組的直接方法解線性方程組的直接方法kx) 1(kn)(121)-(11nnknnk33) 1(2) 1(2) 1(3232nnnnnnnnnN98903303033023由式由式2-9，在回代過程中，計(jì)算，在回代過程中，計(jì)算需求需求次乘除法，整個回代過程需求乘除運(yùn)算的總量為次乘除法，整個回代過程需求乘除運(yùn)算的總量為所以所以,Gauss消去法的乘除總運(yùn)算量為消去法的乘除總運(yùn)算量為由上式容易求出，用由上式容易求出，用Gauss消去法求解消去法求解30階線性方階線性方程組時程組時, ,共需乘除運(yùn)算次數(shù)為共需乘除運(yùn)算次數(shù)為遠(yuǎn)少于用遠(yuǎn)少于用CramerCramer法那么求解所需的乘除運(yùn)算量法那么求解所需的乘除運(yùn)算量. .20第二章第二章 解線性方程組的直接方法解線性方程組的直接方法)(kkka1