現(xiàn)代數(shù)值分析課件第2章線性方程組的直接法

1、第二章第二章 解線性方程組的直接方法解線性方程組的直接方法 高斯高斯(Gauss)(Gauss)消元法消元法 矩陣的三角分解法矩陣的三角分解法 矩陣的條件數(shù)與方程組的性態(tài)矩陣的條件數(shù)與方程組的性態(tài)11112211211222221122 nnnnnnnnnnna xa xa xba xa xa xba xa xa xb階線性方程組： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩陣表示記為這里解線性方程組的兩類方法解線性方程組的兩類方法: :直接法直接法: : 經(jīng)過有限次運算后可求得方程組精確解的方經(jīng)過有限次運算后可求得方程組精確解的方法法( (不計舍入誤

2、差不計舍入誤差!)!)迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法序列去逼近精確解的方法( (一般有限步內(nèi)得不到精確解一般有限步內(nèi)得不到精確解) )一、一、高斯消去法高斯消去法思思路路首先將方程組首先將方程組Ax=b 化為上三角方程組化為上三角方程組，此過程稱為此過程稱為消去過程消去過程，再求解上三角方程，再求解上三角方程組，此過程稱為組，此過程稱為回代過程回代過程. .2.1 高斯消去法和選主元高斯消去法高斯消去法和選主元高斯消去法將增廣矩陣將增廣矩陣的的第第 i 行行 + li1 第第1 1行行，得到：，得到：,)(記)

3、1()1(nnijaAA(1 )(1 )(1 )()1Tbbbbn消去過程：消去過程：第一步第一步：設(shè)設(shè) ，計算因子，計算因子0)1(11a)1(11)1(11aalii)1(1)1(1)1(12)1(11.baaan) 2(A) 2 (b其中其中) 1(11) 1()2() 1(11) 1()2(, 3 , 2, ,blbbnjialaaiiijiijij0)( kkka第第k步：步：設(shè)設(shè) ，計算因子，計算因子且計算且計算( )( )/(1,., )kkikikkklaaikn (1)()()(1)()()( ,1, .,)kkkijijikkjkkkiiikkaal abbl bi jkn

4、共進行共進行 n 1步，得到步，得到 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii定理定理2.1：若若A的所有的所有順序主子式順序主子式 均不為均不為0，則高斯，則高斯消去法能順序進行消元，得到唯一解。消去法能順序進行消元，得到唯一解。iiiiiaaaaA.)det(1111 回代過程：回代過程：例例2.1.1 高斯消元法高斯消元法 32303452536432321321321xxxxxxxxx 323034525364

5、32A 202230445 . 006432A 4200445 . 006432 42445 . 06432332321xxxxxxx1 = -13x2 = 8x3 = 2二、二、選主元消去法選主元消去法為避免這種情況的發(fā)生為避免這種情況的發(fā)生, 可通過交換方程的次序，選可通過交換方程的次序，選取絕對值大的元素作主元取絕對值大的元素作主元. 基于這種思想導(dǎo)出了主元基于這種思想導(dǎo)出了主元素法素法在高斯消去法消去過程中可能出現(xiàn)在高斯消去法消去過程中可能出現(xiàn) 的情況，的情況，這時高斯消去法將無法進行；即使主元素這時高斯消去法將無法進行；即使主元素 但很小，其作除數(shù)但很小，其作除數(shù) ，也會導(dǎo)致其它元素

6、數(shù)量級的嚴，也會導(dǎo)致其它元素數(shù)量級的嚴重增長和舍入誤差的擴散重增長和舍入誤差的擴散( )0kkka( )0kkkav 列主元消去法列主元消去法在第在第k步消元前，在系數(shù)矩陣第步消元前，在系數(shù)矩陣第k列的對角線以下列的對角線以下的元素中找出絕對值最大的元。的元素中找出絕對值最大的元。|m ax |0pkkkikkinaa 若若pk, 交換第交換第k個與第個與第p個方程后個方程后, 再繼續(xù)消去計算再繼續(xù)消去計算. . 這種方法稱為這種方法稱為列主元列主元GaussGauss消去法。消去法。 列主元列主元GaussGauss消去法保證了消去法保證了lik1 1 ( ( i = k +1, k +2,

7、，n ).).例例2.1.2 列主元法列主元法 6745150710623321xxx第一列中絕對值最大是第一列中絕對值最大是10，取，取10為主元為主元 6515707104623 6515462370710n階方程組第階方程組第k 輪消元時，選第輪消元時，選第k 列的后列的后( n k + 1 )個個元素中絕對值最大作主元。元素中絕對值最大作主元。 5 . 255 . 21 . 661 . 070710 2 . 62 . 65 . 255 . 270710 x3=6.2/6.2=1x2=(2.5-5x3)/2.5= -1x1=(7+7x2-0 x3)/10=0 x1=0 x2= -1x3=

8、1第二列的后兩個數(shù)中選出主元第二列的后兩個數(shù)中選出主元 2.5v 全主元消去法全主元消去法在第在第k 步消去前，步消去前， 在系數(shù)矩陣右下角的在系數(shù)矩陣右下角的n- k+1階階主子陣中，主子陣中，選絕對值最大的元素作為主元素選絕對值最大的元素作為主元素。(1) If p k then 交換第交換第 k 行與第行與第p 行行; If q k then 交換第交換第 k 列與第列與第 q 列列;(2) 消元消元列交換改變了列交換改變了xi 的順序，須記錄的順序，須記錄交換次序交換次序，解完后再換回來。解完后再換回來。,|m ax |0pqkkijkijnaa12122131233219/401/1

9、015.25/4910192340201420401419102314554155402014034.94.601/21.5254.940120404.934.601.5250.54.94012rrccllcclA 解：1320404.934.6001.433666.331614.41640,1.76514,2.35233xxx 回代：12312312310192320404455xxxxxxxxx例例2.1.3 全主元解方程組全主元解方程組: 運算量運算量 （Amount of Computation）（1 1）用克萊姆用克萊姆（CramerCramer）法則求解法則求解n n階線性方程組階

10、線性方程組每個行列式由每個行列式由n!項相加項相加, 而每項包含了而每項包含了n個因子相乘個因子相乘,乘法運算次數(shù)為乘法運算次數(shù)為(n-1) n!次次.,1, 2,.,iiDxinD僅考慮乘僅考慮乘(除除)法運算法運算, 計算解向量包括計算計算解向量包括計算n+1個行個行列式和列式和n次除法運算次除法運算, 乘乘(除除)法運算次數(shù)法運算次數(shù)N=(n+1)(n-1)n!+n.（2） 高斯消去法高斯消去法:在第在第1個消去步個消去步, 計算計算 li1(i=2,3,n), 有有n-1次除法運算次除法運算. 使使aij(1)變?yōu)樽優(yōu)?aij(2) 以及使以及使bi(1)變?yōu)樽優(yōu)閎i(2)有有n(n-

11、1)次乘法運算次乘法運算和和 n(n-1)次加次加(減減)法運算法運算.在第在第k個消去步個消去步, 有有n-k次除法運算次除法運算, (n-k+1)(n-k)次乘次乘法運算和相同的加法運算和相同的加(減減)法運算法運算.首先統(tǒng)計乘法運算總次數(shù)首先統(tǒng)計乘法運算總次數(shù). . 將每個消去步的乘法運算將每個消去步的乘法運算次數(shù)相加次數(shù)相加, ,有有 n(n-1)+(n-1)(n-2)+32+21=n(n-1)(n+1)/3加加(減減)法運算次數(shù)總計也為法運算次數(shù)總計也為n(n-1)(n+1)/3.除法運算總次數(shù)為除法運算總次數(shù)為n+(n-1)+1= n(n-1)/2回代過程的計算回代過程的計算除法運

12、算次數(shù)為除法運算次數(shù)為n次次. 乘法運算和加法運算的總次數(shù)乘法運算和加法運算的總次數(shù)都為都為n+(n-1)+1= n(n-1)/2次次 Gauss Gauss消去法消去法( (順序消去法順序消去法) ) 除法運算次數(shù)為除法運算次數(shù)為: n(n-1)/2+n= n(n+1)/2， 乘法運算次數(shù)為乘法運算次數(shù)為: n(n-1)(n+1)/3+n(n-1)/2= n(n-1)(2n+5)/6， 加加(減減)法運算次數(shù)為法運算次數(shù)為: n(n-1)(2n+5)/6通常也說通常也說Gauss消去法的運算次數(shù)與消去法的運算次數(shù)與n3同階同階,記為記為O(n3)u全主遠消去法全主遠消去法:比比 高斯消去法多

13、出高斯消去法多出 , 保證穩(wěn)定保證穩(wěn)定, 但費時但費時. 33nOu 列主元消去法列主元消去法: 比比 高斯消去法只多出高斯消去法只多出 的的 , 略省時略省時. 32nO2.22.2 三角分解法三角分解法 高斯消元法的矩陣形式：高斯消元法的矩陣形式：L U 分解分解 每一步消去過程相當于左乘初等變換矩陣每一步消去過程相當于左乘初等變換矩陣L1(2)(1)(2)(1)11112111113111 , 1101 2 3001L()()iin i, ,nbbAL ALllaall記：其中(3)(2)(3)(2)222222223222 , 10101 3 4001L()()iini, ,nbbAL

14、 ALlaall記：(3)(1)(3)(1)2121 , bbAL L AL L11,1,11010111= 01010101 iiiiiininiLiiLllll列列( )(1)121( )(1)121nnnnnn AL LL AbbL LL(1)111( )( )121nnnLLUAL LL AAA 的的 LU 分解分解( LU factorization )定理定理2.2.1： 若若A的所有順序主子式的所有順序主子式 均不為均不為0，則，則 A 的的 LU 分解唯一（其中分解唯一（其中 L 為為單位單位下三角陣）。下三角陣）。證明：證明：由由1中定理可知，中定理可知，LU 分解存在。下面

15、證明唯一性。分解存在。下面證明唯一性。若不唯一，則可設(shè)若不唯一，則可設(shè) A = L1U1 = L2U2 ，推出推出 121UU211122211LLUULL 上三角矩陣上三角矩陣對角線上為對角線上為1 1的的下三角矩陣下三角矩陣I L 為單位下三角陣而為單位下三角陣而 U 為為一般一般上三角陣的分上三角陣的分解稱為解稱為Doolittle 分解分解 （2）L 為一般下三角陣而為一般下三角陣而 U 為為單位單位上三角陣的分解稱為上三角陣的分解稱為Crout 分解分解。 Doolittle分解法分解法 ： 利用矩陣乘法，通過比較直接導(dǎo)出利用矩陣乘法，通過比較直接導(dǎo)出L 和和 U 的計算公式。的計算

16、公式。思思路路 nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia一般計算公式11i1111 , 1, , , 2, , jji jn inuala uL第一行乘第一行乘U 每一列：每一列： a11= u11, , a1n= u1nL每一行乘每一行乘U 第一列：第一列： a21 = l 21u11, , an1 = ln1u11l 21u12+ u22=a22, , l21u1n+ u2n=a2n l31u12+ l32u22=a32, , ln1u12+ ln2u22=an2L第二行乘第二行乘U 每一列：每一列：L每一行乘每一行乘U

17、第二列：第二列：注：注：該公式的特點：該公式的特點：U 的元素按行求的元素按行求, L 的元素按列求的元素按列求; 先求先求 U 的第的第k 行行, 再求再求 L 的第的第k 列列, U 和和 L 一行一列交叉計算一行一列交叉計算. 計算計算量與量與 Gauss 消去法同消去法同.1kjkr11ikirkk1 3, , j k , , n ( )/ ik 1 , , nkkjrjrkikrkrknual ulal u u 對計算 u22=a22 - l21u12, , u2n=a2n- l21u1n l32=(a32- l31u12)/u22, , ln2=(an2- ln1u12)/u22一

18、般地：一般地：LU 分解求解線性方程組 LY b , UXY AXb112221313212(1)1111121n22222nnn111 1 UXnnnnn nnnybybLYbybxyxyYxylllllluuuuuu 11-11 , 2, 3, , (1) Y iiijijjinybyybl解：ijii1( , in1, , 1 2) x nnnnnijij iyxuyxu xu 解：例例2.2.1 求矩陣的求矩陣的Doolittle分解分解 11242142612332442A 1122214161232/32442 112221013632/32442 95/192205013632/

19、32442 9000050036302442U 15/192201010012/30001L 舊元素減去左邊行與頂上列向量的點積舊元素減去左邊行與頂上列向量的點積 計算行不用除法計算行不用除法 計算列要除主對角元計算列要除主對角元注：注： 求解正定方程組的求解正定方程組的Cholesky方法方法(平方根法平方根法)回顧：回顧：對稱正定陣對稱正定陣A的幾個重要性質(zhì)的幾個重要性質(zhì)（1）A 1 亦對稱正定，且亦對稱正定，且 aii 0（2）A 的順序主子陣的順序主子陣 Ak 亦對稱正定亦對稱正定（3）A 的特征值的特征值 i 0 （4）A 的全部順序主子式的全部順序主子式 det ( Ak ) 0定

20、理定理2.2.2: 設(shè)矩陣設(shè)矩陣A對稱正定，則存在唯一的對角對稱正定，則存在唯一的對角元全為正的下三角陣元全為正的下三角陣G 使得使得 AGGT計算格式為計算格式為:12111,1, 2,1,2,.,kkkkkkjjkikijkjjikkkgagknagggikkng平方根法的優(yōu)點：平方根法的優(yōu)點：(1) 乘除法運算量比一般乘除法運算量比一般 LU分解要小得多；分解要小得多；不選主元的平方根法是數(shù)值穩(wěn)定的。不選主元的平方根法是數(shù)值穩(wěn)定的。(2)缺點：缺點：有有n 個開方運算。個開方運算。 為避免過多的開方運算，在更多情況下是將A分解為：A=LDLT，其中L為下三角，D為對角陣。事實上，由前面的

21、討論可知：A=LU，其中L 為單位下三角陣，U為上三角陣。記U的元素為uij，D=diag(uii)，由于A對稱正定，必有uii0(i=1,2,n)，所以U=DU*，其中*1*TTUD UA = AL=UA= LDL為單位上三角陣,由,知,因此。注：注：將矩陣將矩陣 A 作作Doolittle分解或分解或Crout分解分解, 由矩陣乘由矩陣乘法可得法可得 A 的的 LDLT 分解。分解。 解三對角方程組的解三對角方程組的追趕法追趕法 nnnnnnnfffxxxbacbacbacb212111122211定理定理2.2.3：若若 A 為為對角占優(yōu)對角占優(yōu) 的三對角陣，且滿足的三對角陣，且滿足 則

22、方程組有唯一的則方程組有唯一的LU分解。分解。0,0, 0|, 0|11 iinncaabcb第一步第一步 : 對對 A 作作Doolittle 分解分解追趕法公式的推導(dǎo)：追趕法公式的推導(dǎo)：（以四階為例）以四階為例）11112222223333334444112121223232334343411222133321111(1,2,3);iibcudlabcudALUlabcudlabuudl ul dudl ul dudl ul duububl ddciubl d比較對應(yīng)位置的元素，得遞推公式：第二步：2213324434443/;/laulaulauubl d1111212222233332

23、334444344112221333244431111yfyfl yyflyfLyflyfl yyfyfll yyfyfyfl yyfl yLyyfl yyf第三步：由：先求該過程稱為該過程稱為“追追”的過程。的過程。1111222233334444443334333432223211121/()/()/()/()/udxyudxyUxyudxyuxyxyuxyd xuyc xuxyc xuxyc xUxyxu第四步：再由回代解得解得：該過程稱為該過程稱為“趕趕”的過程。的過程。一般情形的三對角方程組計算公式：一般情形的三對角方程組計算公式：1111,1,2,1/,2,3,1,2,3,iiii

24、iiiiidcinublauinubl cin計算次序為：計算次序為：112233(1)(2)(3)iinndcublululu最最好好牢牢記記1212323434112223334412312233442244844154420121144114414411;2,4,2,2,2,2,22 2 2xxxxxxxxxxudludALUludludddulululu追趕例 . . ：法解方程解：(2,8,15,20)(2,4,7,6)(0.5,1,2,3)TTTLyyUxyx由，解得：再由，解得：直接比較等式兩邊的元素，可得到計算公式：直接比較等式兩邊的元素，可得到計算公式：第一步第一步: 對對

25、A 作作Crout 分解：分解：1122111nnnA 注注: 也可通過對也可通過對 A 作作Crout 分解進行求解分解進行求解111,(2,3, )/,(1,2,1)iiiiiiiiibaincbain第二步第二步: 追追即解：即解：fyL 111,fy1()(2,.,)iiiiifyyin第三步第三步: 趕趕即解：即解：yxU 1,(1,.,1)nniiiixyxyxin 2.3 矩陣的條件數(shù)與方程組的性態(tài)矩陣的條件數(shù)與方程組的性態(tài)預(yù)備知識預(yù)備知識范數(shù)范數(shù) 向量范數(shù)向量范數(shù) ( vector norms )nRyx,對任意對任意定義定義1：Rn空間的空間的向量范數(shù)向量范數(shù) | | ,對任

26、意對任意 滿足下列條件滿足下列條件00|;0|) 1 (xxx|) 2 (xxR|) 3 (yxyx常用向量范數(shù)：常用向量范數(shù)： 向量向量 的的Lp范數(shù)定義為范數(shù)定義為: :12( ,)TnXx xx1/1|(| ),1npppiiXxp 主要主要性質(zhì)性質(zhì)性質(zhì)性質(zhì)1:1:-x=x性質(zhì)性質(zhì)2 2: :x-yx-y性質(zhì)性質(zhì)3 3: : 向量范數(shù)向量范數(shù)x是是Rn上向量上向量x的連續(xù)函數(shù)的連續(xù)函數(shù). .范數(shù)等價范數(shù)等價: :設(shè)設(shè)A 和和B是是R上任意兩種范數(shù)，若存在上任意兩種范數(shù)，若存在 常數(shù)常數(shù) C1、C2 0 0 使得使得 , ,則稱則稱 A 和和B 等價等價。定理定理1 Rn 上上一切范數(shù)一切

27、范數(shù)都等價都等價。12212111|max |nniiiiniixxxxxx 向量向量 x 的的1范數(shù)范數(shù) 向量向量 x 的的2范數(shù)范數(shù) 向量向量 x 的的范數(shù)范數(shù) 矩陣范數(shù)矩陣范數(shù) ( matrix norms )nmRBA ,定義定義3:3:對任意對任意 , ,稱稱| | 為為Rm n空間的空間的矩陣矩陣范數(shù)范數(shù), 指指| |滿足滿足(1)-(3)(1)-(3)：00|;0|) 1 ( AAA(2) | | | |AAR對任意對任意|) 3(BABA (4) | AB | | A | | B |若還滿足若還滿足(4),(4),稱為相容的矩陣范數(shù)稱為相容的矩陣范數(shù)相容性相容性（1 1）矩陣范

28、數(shù)與）矩陣范數(shù)與矩陣矩陣范數(shù)的相容性范數(shù)的相容性: : ABAB ABAB（2 2）矩陣范數(shù)與）矩陣范數(shù)與向量向量范數(shù)相容性范數(shù)相容性設(shè)設(shè)AM，AM 是矩陣范數(shù)是矩陣范數(shù), xR n，xv 是向量范是向量范數(shù)數(shù). .如果滿足不等式如果滿足不等式: :Axv AM xv則稱矩陣范數(shù)則稱矩陣范數(shù)AM 與向量范數(shù)與向量范數(shù)xv 相容相容. .常用的算子范數(shù)常用的算子范數(shù)： 由向量范數(shù)由向量范數(shù) | |p 導(dǎo)出關(guān)于矩陣導(dǎo)出關(guān)于矩陣 A Rn n 的的p范數(shù)范數(shù): :pxpppxAxxAApx|max|max|10| 則則ppppppxAxABAAB| njijaAni1|max|1（行和范數(shù)行和范數(shù)）

29、 niijaAnj11|max|1（列和范數(shù)列和范數(shù)）)(|max2AAAT （譜范數(shù)譜范數(shù) ( spectral norm ) ）( operator norm ),又稱為從屬的矩陣范數(shù)又稱為從屬的矩陣范數(shù):算子算子范數(shù)范數(shù)注：注： 稱為稱為A的譜半徑。的譜半徑。1( )max|ii nA 定理定理2對任意算子范數(shù)對任意算子范數(shù) | | | | 有有: :|)(AA 證明：證明： 由算子范數(shù)的相容性，得到由算子范數(shù)的相容性，得到|xAxA 將任意一個特征根將任意一個特征根 所對應(yīng)的特征向量所對應(yīng)的特征向量 代入代入u|uAuA |uu 命題命題若若A A對稱，則有對稱，則有: :)(|2AA

30、 證明：證明：)()(|2maxmax2AAAAT 若若 是是 A 的一個特征根，則的一個特征根，則 2 必是必是 A2 的特征根。的特征根。又：對稱矩陣的特征根為實數(shù)，即又：對稱矩陣的特征根為實數(shù)，即 2(A) 為非負實數(shù)，為非負實數(shù)，故得證。故得證。)()(22maxAA 對某個對某個 A 的特征根的特征根 成立成立定理定理3若矩陣若矩陣 A 對某個算子范數(shù)滿足對某個算子范數(shù)滿足 |A| 1，則必有則必有.IA可逆；可逆；.111 |IAA證明證明: 若不然，則若不然，則 有非零解，即存在非零向有非零解，即存在非零向量量 使得使得 ()0IA x0 x00Axx00|1|Axx|1A 1(

31、)()IA IAI11()()IAA IA11()()IAIA IA11|()|1 | |()|IAAIA 病態(tài)方程組病態(tài)方程組線性方程組的性態(tài)（誤差分析）線性方程組的性態(tài)（誤差分析） ( Error Analysis for Linear system of Equations )例：方程組例：方程組1226826.000018.00001xx有精確解有精確解(1,1),(1,1),對系數(shù)矩陣和右端常熟項作微小變化對系數(shù)矩陣和右端常熟項作微小變化, ,則則1226825.999998.00002xx的解為的解為(10, -2). 擾動后方程組的解面目全非。擾動后方程組的解面目全非。Def :

32、如果方程組如果方程組 Ax = b 中中, 矩陣矩陣A和右端項和右端項 b 的變化的變化|A|和和|b |微小微小, 引起解向量引起解向量 x 的變化的變化|x |很大很大, 則稱則稱A為關(guān)于解為關(guān)于解方程組和矩陣求逆的病態(tài)矩陣方程組和矩陣求逆的病態(tài)矩陣, 稱相應(yīng)的方程組為病態(tài)方程組稱相應(yīng)的方程組為病態(tài)方程組.反之反之, 如果如果|A|和和|b |微小微小, |x |也微小也微小, 則稱則稱 A為良態(tài)矩為良態(tài)矩陣陣, Ax=b 為良態(tài)方程組為良態(tài)方程組. 思考思考:求解求解 時時, A 和和 的誤差對解的誤差對解 有何影響有何影響？Axbbx 設(shè)設(shè) A 精確，精確， 有誤差有誤差 ，得到的解為

33、，得到的解為 ，即，即bbxx1xAb1| | |xAb絕對誤差放大因子絕對誤差放大因子| |bAxAx又又1|Axb1| |xbAAxb相對誤差放大因子相對誤差放大因子()A xxbb矩陣和方程組病態(tài)程度的刻劃矩陣和方程組病態(tài)程度的刻劃 設(shè)設(shè) 精確，精確，A有誤差有誤差 ，得到的解為，得到的解為 ，即，即bA xx()()AAxxb()()A xxA xxb1()xAA xx 11| | |xAAxxAAAA()()AA xAAxb()AAxAx 1()A IAAxAx 111()xIAAAAx (只要只要 A充分小，使得充分小，使得11| | | 1)AAAA1111| | |1 | |1 | |AAAxAAAAxAAAAA 是關(guān)鍵是關(guān)鍵的誤差放大因子，稱為的誤差放大因子，稱為A的狀態(tài)數(shù)的狀態(tài)數(shù)(條件數(shù)條件數(shù))，記為記為cond (A) ,|1 AA注注: : cond(cond(A) ) 與與 所取的范數(shù)有關(guān)所取的范數(shù)有關(guān)常用條件數(shù)有：常用條件數(shù)有：cond 2(A)