線性代數(shù)方程組的直接法

線性代數(shù)方程組的直接法第1頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/262第七章解線性方程組的直接方法數(shù)值分析（NumericalAnalysis）第2頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月AX=b很多實(shí)際問題都可歸結(jié)為求解線性方程組：2023/7/263寫成矩陣形式：第3頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月線性方程組數(shù)值解法的分類：直接法：經(jīng)過有限步算術(shù)運(yùn)算即可求得方程組精確解的方法（適用于中等規(guī)模的n階線性方程組）

◆Gauss消去法及其變形◆矩陣的三角分解法迭代法：用某種極限過程去逐步逼近線性方程組精確解的方法。（適用于高階線性方程組）

◆Jacobi迭代法

◆

Gauss-Seidel迭代法

◆逐次超松弛法2023/7/264第4頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/265§1Gauss消去法或

AX=b消元手續(xù)第5頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/266舉例說明消去法的基本思想：基本思想：用逐次消去未知數(shù)的方法把原來方程組AX=b化為與其等價(jià)的三角方程組，然后再用回代法寫出方程組的解。事實(shí)上，將方程組化為與其等價(jià)的三角方程組的過程就是用行的初等變換將原來方程組的系數(shù)矩陣化為簡(jiǎn)單形式，然后再求解。第6頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月1．消元

基本思想：通過消元手續(xù)將上述方程組化為三角形方程組進(jìn)行求解。2023/7/267Guass消去法第7頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月消元公式2023/7/268第8頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2.回代2023/7/269第9頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月回代公式2023/7/2610第10頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月Gauss消去法可執(zhí)行的前提：【定理1】按順序Gauss消去法所形成的各主元素的充要條件是矩陣的順序主子式，即2023/7/2611第11頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【推論】如果的順序主子式2023/7/2612第12頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理2】如果的所有順序主子式都不為零，即則可通過Gauss消去法將前面的方程組約化為三角方程組。2023/7/2613作業(yè)：P1971，2，7不進(jìn)行交換兩行的初等變換！第13頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2614矩陣的三角分解借助矩陣?yán)碚摲治鱿シ?！建立Gauss消去法和矩陣?yán)碚撻g的關(guān)系！對(duì)于或

AX=b第14頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月在Gauss消元法中，每一步消去過程相當(dāng)于左乘初等變換矩陣Lk2023/7/2615第15頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2616第16頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月A

的

LU

分解其中單位下三角形。2023/7/2617第17頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理3】（矩陣的LU分解）設(shè)A為nn矩陣，如果解AX=b用高斯消去法（限制不進(jìn)行行的交換，即）能夠完成，則矩陣A可分解為單位下三角矩陣L與上三角矩陣U的乘積，即

A=LU且這種分解是唯一的。2023/7/2618第18頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月注：（1）L為單位下三角陣而U為一般上三角陣的分解稱為Doolittle

分解（2）L為一般下三角陣而U為單位上三角陣的分解稱為Crout分解。

2023/7/2619第19頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2620系數(shù)矩陣的三角分解！第20頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月21計(jì)算量（1）消元過程的計(jì)算量：第1步計(jì)算乘數(shù)mi1(i=1,2,…,n)，需要n-1次除法運(yùn)算；計(jì)算需要次乘法和次加、減法。第k步加、減法次數(shù)乘法次數(shù)除法次數(shù)12……n-1111合計(jì)第21頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月22第k步加、減法次數(shù)乘法次數(shù)除法次數(shù)123…2….2…1…nn-1n-11合計(jì)(2)計(jì)算b(n)計(jì)算量:進(jìn)行

次乘法和

加、減法；(3)回代過程的計(jì)算量:總計(jì)算量：

次乘除法和次加減法較大時(shí)乘除法次數(shù)：較大時(shí)加減法次數(shù)：第22頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月§2

Gauss主元素消去法【例4】用Gauss消去法解方程組選主元素的必要性！要求用具有舍入的10位浮點(diǎn)數(shù)進(jìn)行計(jì)算。精確到10位的精確解為：【解法1】（高斯消去法）消元：舍去或者說被“吃”舍去或者說被“吃”計(jì)算解：2023/7/2623第23頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月顯然,計(jì)算解與精確解解相差太大，原因是用很小的數(shù)作除數(shù)，使得舍入誤差太大，從而計(jì)算結(jié)果不可靠?！窘夥?】用行變換的高斯消去法消元：計(jì)算解:該結(jié)果較好。該例子說明，在采用高斯消去法解方程組時(shí)，應(yīng)避免采用絕對(duì)值很小主元素。對(duì)一般系數(shù)矩陣，最好保持乘數(shù)，因此在高斯消去法中引進(jìn)選主元素技巧。24第24頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月1、完全主元素消去法選主元素消元法：為非奇異矩陣，第一步：（1）選主元素：在A中選取絕對(duì)值最大的元素作為主元素，即確定使（2）交換行列：交換中第1行和i1行元素，第1列和第j1列元素。注意調(diào)換兩未知量，并做記錄。交換后的元素仍記為。（3）第1次消元計(jì)算：重復(fù)進(jìn)行上述過程，設(shè)已完成第1步至第k-1步的選主元素、交換行列和消元計(jì)算，使為增廣矩陣。25第25頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月第k步：（1）選主元素：選取使（2）交換行列：交換中第k行和ik行元素，第k列和第jk列元素。（3）消元計(jì)算：2023/7/2626第26頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月回代求解工作量大。經(jīng)過上述過程，方程組約化為：缺點(diǎn)：優(yōu)點(diǎn)：數(shù)值穩(wěn)定改進(jìn)方法：列主元消去法，且此時(shí)其中是未知數(shù)調(diào)換后的順序，則完全主元素消去法優(yōu)缺點(diǎn)：完全主元素消去法步驟見P172!27第27頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月列主元素法考慮依次按列選主元素，然后換行，再進(jìn)行消元計(jì)算。設(shè)已完成第1步~第k-1步計(jì)算，得到與原方程組等價(jià)的方程組其中方框內(nèi)為第k步選主元素區(qū)域。2、列主元素消去法28第28頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月輸入矩陣階數(shù)n，增廣矩陣

A(n,n+1);對(duì)于(1)按列選主元：選取l，

使

(2)如果，交換A(n,n+1)

的第k行與第l

行元素(3)

消元計(jì)算：回代計(jì)算2023/7/2629列主元素消去法步驟見P173!第29頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月矩陣運(yùn)算描述列主元素消去法！30先換行再消元！【定理4】（列主元素的三角分解）如果Ａ為非奇異矩陣，則存在排列矩陣P，使得PA=LU，其中L是單位下三角陣，U是上三角陣。第30頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【例5】用列主元素消去法解方程組我們用4位浮點(diǎn)數(shù)進(jìn)行計(jì)算。解：消元：舍去或者說被“吃”已知精確解：2023/7/26第31頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月回代計(jì)算解：高斯選主元消去法的步驟：注：該解若取兩位有效數(shù)字，則與精確解完全相同。優(yōu)點(diǎn)：數(shù)值穩(wěn)定修正方法：消元，回代。高斯-約當(dāng)（Gauss-Jordam）消去法。缺點(diǎn)：既消元，又回代2023/7/2632第32頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月3、高斯—約當(dāng)（Gauss–Jordan)消去法

高斯消去法始終是消去對(duì)角線下方的元素，Gauss–Jordan消去法要消去對(duì)角線下方和上方的元素。假設(shè)G--J消去法已完成第1步～第k-1步，得到與原方程組等價(jià)的方程組，其中第k步計(jì)算：（1）按列選主元：即確定ik，使（2）換行：交換的第k行和第ik行元素（3）消元計(jì)算：33第33頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月（4）計(jì)算主行（主元素所在行）計(jì)算解：上述過程結(jié)束后，有2023/7/2634第34頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月說明：在解方程組，一般不用高斯-約當(dāng)消去法。因?yàn)橛?jì)算量太大，但是在解多個(gè)方程組而它們的系數(shù)矩陣相同時(shí)，用此方法，即求系數(shù)矩陣的逆矩陣A-1

時(shí)，比較合適。設(shè)為非奇異矩陣。如果用列主元G-J消去法將（A,I）化為（I,T），則。不用回代，將A化為單位矩陣，則解為常數(shù)項(xiàng)列?！径ɡ?】（高斯—約當(dāng)法求逆矩陣）優(yōu)點(diǎn)：缺點(diǎn)：計(jì)算量較大，大約是次乘除法。注：該方法與高等代數(shù)中求逆矩陣方法的不同之處是有選主元，實(shí)際上選主元就是交換兩行的位置，仍是初等變換，在一般的求逆矩陣方法中也有交換兩行元素。2023/7/2635第35頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【例6】用列主元素G-J消去法求的逆矩陣A-1解：

2023/7/2636第36頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月所以G-J列主元求逆算法見P176算法3！2023/7/2637第37頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2638作業(yè)：P19912第38頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2639§3

Gauss消去法

的變形直接三角分解法直接從矩陣A的元素得到計(jì)算Ｌ，U元素的遞推公式，而不需要任何中間步驟，稱之為直接三角分解法。這樣，AX=bL(UX)=bLY=b，UX=Y。不選主元的三角分解(Doolittle分解法)

第39頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月通過比較法直接導(dǎo)出L和

U的計(jì)算公式。思路40通過n步可以直接計(jì)算定出L，U的元素，其中第r步確定U的第r行和L的第r列元素。第1步：設(shè)第r-1步已確定U的第r-1行和L的第r-1列元素。第40頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月41第r步：故：故：第41頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月LU分解求解線性方程組:2023/7/2642第42頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月直接三角分解法解AX=b的計(jì)算公式:對(duì)于r=2,3,…,n，(2)計(jì)算U的第r行元素

(3)計(jì)算L的第r列元素

(r

n)(1)2023/7/2643第43頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月(4)(5)2023/7/2644第44頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【例7】用直接三角分解法解解：用分解計(jì)算公式得：求解：2023/7/2645第45頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2646選主元的三角分解選主元素三角分解算法見P179!第46頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2.平方根法(對(duì)稱正定矩陣而言)矩陣的LDR分解【定理6】若n階矩陣A的所有順序主子式均不等于零，則矩陣A存在唯一的分解式A=LDR，其中L和R分別是n階單位下三角陣和單位上三角陣，D是n階對(duì)角元素不為零的對(duì)角陣，上述分解也稱為A的LDR分解。2023/7/2647第47頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月平方根法

如果A為對(duì)稱矩陣，

且A的所有順序主子式均不等于零，則A可唯一分解為A=LDLT，其中L是n階單位下三角陣和D是對(duì)角陣?！径ɡ?】（對(duì)稱矩陣的三角分解定理）2023/7/2648第48頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月設(shè)A是對(duì)稱

正定矩陣，做LU分解U=uij=u11uij/uii111u22unn記為

A對(duì)稱即記D1/2=則仍是下三角陣，且有2023/7/2649第49頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理5】（對(duì)稱正定矩陣的三角分解或Cholesky分解）2023/7/2650

如果A為對(duì)稱正定矩陣，則存在一個(gè)實(shí)的非奇異下三

角矩陣，使A=LLT

，且當(dāng)限定的對(duì)角元素為正時(shí)，這種分解是唯一的。如何確定L呢？第50頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月下面用直接法確定L中元素。2023/7/2651其中，注意到所以因此第51頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月用平方根法解線性代數(shù)方程組的算法（1）對(duì)矩陣A進(jìn)行Cholesky分解，即A=LLT，由矩陣乘法：對(duì)于

i=1,2,…,n計(jì)算2023/7/2652第52頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月（2）求解下三角形方程組

（3）求解LTX=y2023/7/2653第53頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月改進(jìn)平方根法

其中2023/7/2654第54頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月改進(jìn)平方根法解對(duì)稱正定方程組的算法2023/7/2655第55頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月令LTX=y，先解下三角形方程組LDY=b得解上三角形方程組LTX=Y得2023/7/2656第56頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月3.追趕法2023/7/2657第57頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2658第58頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月§4向量和矩陣的范數(shù)

1．向量范數(shù)【定義】設(shè)XRn，X

表示定義在Rn上的一個(gè)實(shí)值函數(shù)，稱之為X的范數(shù)，它具有下列性質(zhì)：（3）三角不等式：即對(duì)任意兩個(gè)向量X,YRn，恒有

(1)非負(fù)性：即對(duì)一切XRn，X

0,X

>0(2)齊次性：即對(duì)任何實(shí)數(shù)aR，XRn，2023/7/2659由上可得：第59頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月

設(shè)X=(x1,x2,…,xn)T，則有

（1）（2）（3）三個(gè)常用的向量范數(shù)：范數(shù)等價(jià):設(shè)‖·‖s和‖·‖t是Rn上任意兩種范數(shù)，若存在常數(shù)c1，c2

>0使得:

,則稱

‖·‖s和‖·‖t等價(jià)。2023/7/2660第60頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理5】(N(x)的連續(xù)性)定義在Rn上的向量范數(shù)是X分量的連續(xù)函數(shù)。【定理6】（向量范數(shù)的等價(jià)性）在Rn上定義的任一向量范數(shù)都與范數(shù)等價(jià)，即存在正數(shù)M與m(M>m)對(duì)一切XRn，不等式成立。推論：Rn上定義的任何兩個(gè)范數(shù)都是等價(jià)的。

2023/7/2661第61頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月對(duì)常用范數(shù)，容易驗(yàn)證下列不等式：

2023/7/2662第62頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定義2】設(shè)為Rn中一向量序列，即其中若對(duì)任何i(i=1,2,…,n)都有則向量

稱為向量序列的極限，或者說向量序列依坐標(biāo)收斂于向量，記為2023/7/2663第63頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理7.13】向量序列依坐標(biāo)收斂于X*的充要條件是向量序列依范數(shù)收斂與依坐標(biāo)收斂是等價(jià)的。【定義3】設(shè)A為n階方陣，Rn中已定義了向量范數(shù)，則稱為矩陣A的范數(shù)或模，記為。即2023/7/2664第64頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月（1）當(dāng)A=0時(shí)，＝0，當(dāng)A0時(shí)，>0（2）對(duì)任意實(shí)數(shù)k

和任意A，有（3）對(duì)任意兩個(gè)n階矩陣A，B有（4）對(duì)任意兩個(gè)n階矩陣A，B，有2023/7/26652．矩陣的范數(shù)【定義3】（矩陣范數(shù)）如果矩陣的某個(gè)非負(fù)的實(shí)值函數(shù)滿足條件：則稱是上的一個(gè)矩陣范數(shù)(模)。第65頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月2023/7/2666矩陣和向量相容的范數(shù)：其中滿足矩陣范數(shù)的定義，稱為A的Frobenius范數(shù)。第66頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【例5】設(shè)A＝(aij)∈M。定義證明：這樣定義的非負(fù)實(shí)數(shù)不是相容的矩陣范數(shù).證明：設(shè)從而2023/7/2667第67頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理8】設(shè)n

階方陣A=(aij)nn，則（Ⅰ）與相容的矩陣范數(shù)是（Ⅱ）與相容的矩陣范數(shù)是其中1為矩陣ATA的最大特征值。（Ⅲ）與相容的矩陣范數(shù)是上述三種范數(shù)分別稱為矩陣的1-范數(shù)，2-范數(shù)和∞-范數(shù)。2023/7/2668第68頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月可以證明,對(duì)方陣和，有(向量||·||2的直接推廣)Frobenius范數(shù):2023/7/2669第69頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月3．矩陣范數(shù)與特征值之間的關(guān)系【定理9】矩陣A

的任一特征值的絕對(duì)值不超過A的范數(shù)，即

【定義4】矩陣A的諸特征值的最大絕對(duì)值稱為A的譜半徑，記為：并且如果A為對(duì)稱矩陣，則

2023/7/2670第70頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月注:Rn×n中的任意兩個(gè)矩陣范數(shù)也是等價(jià)的。【定義5】設(shè)||·||為Rn×n上的矩陣范數(shù)，A,B∈Rn×n稱||A-B||為A與B之間的距離?！径x6】設(shè)給定Rn×n中的矩陣序列，若則稱矩陣序列收斂于矩陣A，記為2023/7/2671第71頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定理10】設(shè)B∈Rn×n，則由B的各冪次得到的矩陣序列Bk,k=0,1,2…)收斂于零矩陣的充要條件為。2023/7/2672第72頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月求解時(shí)，A

和的誤差對(duì)解有何影響？設(shè)A

精確，有誤差，得到的解為，即絕對(duì)誤差放大因子又相對(duì)誤差放大因子§5

誤差分析2023/7/2673第73頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月設(shè)精確，A有誤差，得到的解為，即

Waitaminute…

Whosaidthat(I+A1A)isinvertible?(只要A充分小，使得

是關(guān)鍵的誤差放大因子，稱為A的條件數(shù)，記為cond(A),越則A越病態(tài)，難得準(zhǔn)確解。大2023/7/2674第74頁(yè)，課件共80頁(yè)，創(chuàng)作于2023年2月【定義7】設(shè)A為n階非奇異矩陣，稱數(shù)為矩陣A的條件數(shù)。條件數(shù)的性質(zhì)：

ⅰ）cond