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

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

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

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

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

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

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

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

8、, 若flag=0, % 則不顯示中間過程，否則顯示中間過程, 默認為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,湘潭大學數(shù)學與計算科學學院,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,湘潭大學數(shù)學與計算科學學院,43,全主元消去法,定義,此時交換 和 的行及a的列，使主元位置的元素 的絕對值具有給出的最大值 ，,然后進行第 步消元過程,湘潭大學數(shù)學與計算科學學院,44,gauss消去法的實質(zhì)是將矩陣 分解為,其中 -單位下三角矩陣， -上三角矩陣.,事實上，線性方程組,經(jīng)過 步消元過程后，有等價方程組,其中： ，而 和 的形式為：,2.3 矩陣的三角分解與gauss消去法的變形,湘潭大學數(shù)學與計算科學學院,45,（1）

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

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