1、湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,1,第五章 線性代數(shù)方程組的解法,5.1 預(yù)備知識(shí),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,2,求解線性方程組,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,3,利用 法則求解時(shí)存在的困難是：當(dāng)方程 組的階數(shù) 很大時(shí)，計(jì)算量為,常用計(jì)算方法:,(1) 直接解法：它是一類(lèi)精確方法，即若不考慮計(jì)算過(guò)程中的舍入誤差，那么通過(guò)有限步運(yùn)算可以獲得方程解的精確結(jié)果.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,4,(2) 迭代解法：所謂迭代方法，就是構(gòu)造某種極限過(guò)程去逐步逼近方程組的解.,經(jīng)典迭代法有：,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,5,5.1.1 向量空間及相關(guān)概念和記號(hào),1 向量的范數(shù),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,6,根

2、據(jù)定義:,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,7,范數(shù)的等價(jià)性,例如：,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,8,向量序列,若對(duì),則稱(chēng)向量序列 收斂于向量,這是因?yàn)?2 向量序列的收斂問(wèn)題,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,9,利用向量范數(shù)的等價(jià)性及向量范數(shù)的連續(xù)性, 容易得到定理5.2的證明,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,10,對(duì)于 上的任何向量范數(shù),我們可以定義矩陣范數(shù).,1. 矩陣的范數(shù),5.1.2 矩陣的一些相關(guān)概念及記號(hào),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,11,定理5.3 矩陣的從屬范數(shù)具有下列基本性質(zhì)：,1） ，當(dāng)且僅當(dāng) 時(shí)，,2),定理5.3中的性質(zhì) 1), 2) 和 3)是一般范數(shù)所滿足的基本性質(zhì)，性質(zhì) 4)

3、、5) 被稱(chēng)為相容性條件，一般矩陣范數(shù)并不一定滿足該條件.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,12,三種從屬范數(shù)計(jì)算：,（1）矩陣的1-范數(shù)（列和范數(shù)）:,（3）矩陣的2-范數(shù):,其中 : 的最大特征值,（2）矩陣的 -范數(shù)（行和范數(shù)）:,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,13,解：,按定義,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,14,矩陣范數(shù)的等價(jià)定理：,幾種常用范數(shù)的等價(jià)關(guān)系：,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,15,2. 譜半徑：,此時(shí),若 為對(duì)稱(chēng)陣，,（ 因?yàn)?）,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,16,關(guān)于矩陣的譜半徑與矩陣的范數(shù)之間有如下關(guān)系.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,17,定義5.3,稱(chēng)矩陣序列 是收斂的，,

4、如果存在 ，使得,此時(shí)稱(chēng) 為矩陣序列 的極限,記為,3. 矩陣級(jí)數(shù)的收斂性,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,18,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,19,該定理將被應(yīng)用于解方程組的擾動(dòng)分析和gauss消去法的舍入誤差分析.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,20,4 矩陣的條件數(shù),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,21,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,22,5 幾種特殊矩陣,且至少有一 個(gè)使不等式嚴(yán)格成立，則稱(chēng)矩陣,為按行對(duì)角占優(yōu)矩陣。若 嚴(yán)格不等,式均成立，則稱(chēng) 為按行嚴(yán)格對(duì)角占優(yōu)矩陣.,類(lèi)似地，可以給出矩陣 為按列（嚴(yán)格）對(duì)角 占優(yōu)矩陣的定義.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,23,證明 我們只證按行嚴(yán)格對(duì)角占優(yōu)的情形

5、，這時(shí)有,從而,矛盾,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,24,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,25,5.2 gauss消去法、矩陣分解,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,26,2.1 gauss消去法,下面通過(guò)簡(jiǎn)單例子導(dǎo)出一般算法。,設(shè)給定方程組,(1),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,27,乘以第一個(gè)方程，這樣方程組（1）,其中：,顯然方程組（2）和原方程組（1）等價(jià),(1),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,28,其中,依此方法繼續(xù)下去，得到,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,29,（4）,從（4）的最后一個(gè)方程組得到,其中,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,30,再將,代入（4）倒數(shù)第二個(gè)方程，可得：,類(lèi)似地，得到：,我們稱(chēng)

6、將方程組（1）按以上步驟化為等價(jià)方程組 （4）的過(guò)程為解線性方程組的消元過(guò)程,從（4）中得出解的過(guò)程稱(chēng)為高斯消去法的回代過(guò)程,（4）,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,31,一般情形,1. 消元過(guò)程,首先消去第一列除 之外的所有元素，,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,32,設(shè),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,33,其中,這里取,2. 回代過(guò)程,若通過(guò)消元過(guò)程原方程組已化為等價(jià)的三角形 方程組,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,34,且 , 則逐步回代可得原方程組的解,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,35,gauss逐步消去法有如下的缺點(diǎn)：,任一主元 ，就無(wú)法做下去,任一 絕對(duì)值很小時(shí),也不行（舍入誤差的影響大）,2.

7、2 gauss主元素消去法,下面我們討論列主元消去法.,設(shè),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,37,并令 為達(dá)到最大值 的最小行標(biāo) ，,可以防止有效數(shù)字大量丟失而產(chǎn)生誤差.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,38,例 用列主元消去法解如下方程組,解 對(duì)增廣矩陣按列選主元再進(jìn)行高斯消元,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,39,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,40,回代求解得,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,41,%magauss2.m function x=magauss2(a,b,flag) %用途：列主元gauss消去法解線性方程組ax=b %格式：x=magauss(a,b,flag), a為系數(shù)矩陣, b為右端項(xiàng)

8、, 若flag=0, % 則不顯示中間過(guò)程，否則顯示中間過(guò)程, 默認(rèn)為0, x為解向量 if nargink t=a(k,:); a(k,:)=a(p,:); a(p,:)=t; t=b(k); b(k)=b(p); b(p)=t; end,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,42,%消元 m=a(k+1:n,k)/a(k,k); a(k+1:n,k+1:n)=a(k+1:n,k+1:n)-m*a(k,k+1:n); b(k+1:n)=b(k+1:n)-m*b(k); a(k+1:n,k)=zeros(n-k,1); if flag=0, ab=a,b, end end %回代 x=zeros(n,1

9、); x(n)=b(n)/a(n,n); for k=n-1:-1:1 x(k)=(b(k)-a(k,k+1:n)*x(k+1:n)/a(k,k); end,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,43,全主元消去法,定義,此時(shí)交換 和 的行及a的列，使主元位置的元素 的絕對(duì)值具有給出的最大值 ，,然后進(jìn)行第 步消元過(guò)程,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,44,gauss消去法的實(shí)質(zhì)是將矩陣 分解為,其中 -單位下三角矩陣， -上三角矩陣.,事實(shí)上，線性方程組,經(jīng)過(guò) 步消元過(guò)程后，有等價(jià)方程組,其中： ，而 和 的形式為：,2.3 矩陣的三角分解與gauss消去法的變形,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,45,（1）

10、,可以直接驗(yàn)證 ，,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,46,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,47,其中,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,48,則 也是對(duì)角元等于1的下三角陣,用矩陣 依次左乘原給方程組 兩邊，得等價(jià)方程組,則,其中,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,49,(2),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,50,gauss逐步消去法等價(jià)于下述過(guò)程：,2. 求解三角形方程組 （回代過(guò)程）.,(注意上面的全部討論中要求 ),湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,51,比較等式兩邊對(duì)應(yīng)元素算出,doolittle分解,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,52,doolittle分解計(jì)算順序?yàn)?第一層,第二層,第三層,湘潭大學(xué)數(shù)學(xué)與計(jì)算科

11、學(xué)學(xué)院,53,crout分解：,比較兩邊對(duì)應(yīng)的元素，得,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,54,其中,、 分別為單位下、上三角陣,例,實(shí)際上，進(jìn)一步可以做分解,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,55,首先我們來(lái)看一個(gè)命題:,證明:,我們對(duì)a做分解,其中,、 分別為單位下、上三角陣,1. 對(duì)稱(chēng)正定陣的cholesky分解,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,56,于是有,由于 正定， 故有,取,令,即得,證畢,我們將上面的這種分解稱(chēng)為cholesky分解.,下面我們討論cholesky分解的算法.,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,57,比較兩邊對(duì)應(yīng)的元素，有：,以 的第二行乘 的前兩列,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,58,即得,又可以解出,由 的正定性可知平方根中值 為正的,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,59,由矩陣乘法解得,例,湘潭大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,60,設(shè)線性方程組 的系數(shù)矩陣 為三對(duì)角矩陣,當(dāng) 的所有順序主子矩陣非奇異時(shí)可作如下分解,2 解三對(duì)角