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

第五章線性代數(shù)方程組的解法5.1預(yù)備知識(shí)1a

求解線性方程組

其中

且。2a

利用法則求解時(shí)存在的困難是：當(dāng)方程組的階數(shù)很大時(shí)，計(jì)算量為常用計(jì)算方法:

(1)直接解法：它是一類精確方法，即若不考慮計(jì)算過程中的舍入誤差，那么通過有限步運(yùn)算可以獲得方程解的精確結(jié)果.Gauss逐步（順序）消去法、Gauss主元素法、矩陣分解法等；3a(2)迭代解法：所謂迭代方法，就是構(gòu)造某種極限過程去逐步逼近方程組的解.經(jīng)典迭代法有：

迭代法、迭代法、逐次超松弛（SOR）迭代法等；4a5.1.1

向量空間及相關(guān)概念和記號(hào)

1向量的范數(shù)5a例:設(shè)求根據(jù)定義:6a范數(shù)的等價(jià)性例如：7a設(shè)為中的一個(gè)給定向量序列若對則稱向量序列收斂于向量命題:當(dāng)時(shí)這是因?yàn)?向量序列的收斂問題8a利用向量范數(shù)的等價(jià)性及向量范數(shù)的連續(xù)性,容易得到定理5.2的證明9a對于上的任何向量范數(shù),我們可以定義矩陣范數(shù).1.矩陣的范數(shù)5.1.2矩陣的一些相關(guān)概念及記號(hào)10a定理5.3

矩陣的從屬范數(shù)具有下列基本性質(zhì)：1），當(dāng)且僅當(dāng)時(shí)，2)4)時(shí)5)、

定理5.3中的性質(zhì)1),2)和3)是一般范數(shù)所滿足的基本性質(zhì)，性質(zhì)4)、5)被稱為相容性條件，一般矩陣范數(shù)并不一定滿足該條件.11a三種從屬范數(shù)計(jì)算：（1）矩陣的1-范數(shù)（列和范數(shù)）:（3）矩陣的2-范數(shù):其中:的最大特征值（2）矩陣的-范數(shù)（行和范數(shù)）:12a解：按定義例已知矩陣求13a矩陣范數(shù)的等價(jià)定理：對、，存在常數(shù)和，使得：幾種常用范數(shù)的等價(jià)關(guān)系：14a2.譜半徑：此時(shí)若為對稱陣，（因?yàn)椋?5a關(guān)于矩陣的譜半徑與矩陣的范數(shù)之間有如下關(guān)系.16a定義5.3稱矩陣序列是收斂的，如果存在，使得此時(shí)稱為矩陣序列的極限記為矩陣序列的充分必要條件為3.矩陣級(jí)數(shù)的收斂性17a18a

該定理將被應(yīng)用于解方程組的擾動(dòng)分析和Gauss消去法的舍入誤差分析.19a4矩陣的條件數(shù)

20a21a5幾種特殊矩陣

且至少有一個(gè)使不等式嚴(yán)格成立，則稱矩陣為按行對角占優(yōu)矩陣。若嚴(yán)格不等式均成立，則稱為按行嚴(yán)格對角占優(yōu)矩陣.類似地，可以給出矩陣為按列（嚴(yán)格）對角占優(yōu)矩陣的定義.22a證明我們只證按行嚴(yán)格對角占優(yōu)的情形，這時(shí)有從而矛盾23a24a§5.2Gauss消去法、矩陣分解25a2.1Gauss消去法下面通過簡單例子導(dǎo)出一般算法。設(shè)給定方程組(1)26a乘以第一個(gè)方程，這樣方程組（1）

(2)化為其中：顯然方程組（2）和原方程組（1）等價(jià)若，則以第個(gè)方程減去

(1)27a

得到(3)其中依此方法繼續(xù)下去，得到以（2）的第個(gè)方程減去(2)28a（4）從（4）的最后一個(gè)方程組得到其中29a再將代入（4）倒數(shù)第二個(gè)方程，可得：類似地，得到：我們稱將方程組（1）按以上步驟化為等價(jià)方程組（4）的過程為解線性方程組的消元過程

從（4）中得出解的過程稱為高斯消去法的回代過程

（4）30a一般情形對于一般的階線性代數(shù)方程組

即1.消元過程首先消去第一列除之外的所有元素，

31a設(shè)總可由消元過程得到系數(shù)矩陣為上三角陣的線性代數(shù)方程組，其第步的結(jié)果為32a其中這里取2.回代過程若通過消元過程原方程組已化為等價(jià)的三角形方程組33a且,則逐步回代可得原方程組的解34aGauss逐步消去法有如下的缺點(diǎn)：任一主元，就無法做下去任一絕對值很小時(shí),也不行（舍入誤差的影響大）2.2Gauss主元素消去法下面我們討論列主元消去法.假設(shè)Gauss消去法的消元過程進(jìn)行到第步，35a設(shè)36a并令為達(dá)到最大值的最小行標(biāo)，

則交換和中的第行和第行，再進(jìn)行消元過程的第步.這時(shí)每個(gè)乘子

都滿足

可以防止有效數(shù)字大量丟失而產(chǎn)生誤差.37a例用列主元消去法解如下方程組

解對增廣矩陣按列選主元再進(jìn)行高斯消元

38a39a回代求解得40a%magauss2.mfunctionx=magauss2(A,b,flag)%用途：列主元Gauss消去法解線性方程組Ax=b%格式：x=magauss(A,b,flag),A為系數(shù)矩陣,b為右端項(xiàng),若flag=0,%則不顯示中間過程，否則顯示中間過程,默認(rèn)為0,x為解向量ifnargin<3,flag=0;endn=length(b);fork=1:(n-1)

%選主元[ap,p]=max(abs(A(k:n,k)));p=p+k-1;ifp>kt=A(k,:);A(k,:)=A(p,:);A(p,:)=t;t=b(k);b(k)=b(p);b(p)=t;end41a

%消元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);ifflag~=0,Ab=[A,b],endend%回代x=zeros(n,1);x(n)=b(n)/A(n,n);fork=n-1:-1:1x(k)=(b(k)-A(k,k+1:n)*x(k+1:n))/A(k,k);end42a全主元消去法定義此時(shí)交換和的行及A的列，使主元位置的元素的絕對值具有給出的最大值，

然后進(jìn)行第步消元過程

注意：因?yàn)橛辛械慕粨Q，因此未知量的次序有改變，待消元過程結(jié)束時(shí)必須還原.多使用列主元消去法.43aGauss消去法的實(shí)質(zhì)是將矩陣分解為其中--單位下三角矩陣，--上三角矩陣.事實(shí)上，線性方程組經(jīng)過步消元過程后，有等價(jià)方程組其中：，而和的形式為：2.3矩陣的三角分解與Gauss消去法的變形44a（1）可以直接驗(yàn)證，

45a46a其中47a乘積是下三角陣，且對角元全部等于1

則也是對角元等于1的下三角陣

用矩陣依次左乘原給方程組兩邊，得等價(jià)方程組則其中48a由于為上三角陣，記

,于是得到(2)49aGauss逐步消去法等價(jià)于下述過程：2.求解三角形方程組（回代過程）.(注意上面的全部討論中要求)50a比較等式兩邊對應(yīng)元素算出Doolittle分解51aDoolittle分解計(jì)算順序?yàn)椤?/p>

…

…

…

第一層第二層第三層52aCrout分解：比較兩邊對應(yīng)的元素，得53a其中

、分別為單位下、上三角陣?yán)龑?shí)際上，進(jìn)一步可以做分解54a首先我們來看一個(gè)命題:證明:我們對A做分解其中

、分別為單位下、上三角陣又由于則當(dāng)為對稱正定矩陣時(shí)，

A存在三角分解其中為下三角矩陣

1.對稱正定陣的Cholesky分解55a于是有由于正定，故有取令即得證畢我們將上面的這種分解稱為Cholesky分解.下面我們討論Cholesky分解的算法.

56a比較兩邊對應(yīng)的元素，有：因正定，就有，故以的第二行乘的前兩列57a即得又可以解出一般地，對有由的正定性可知平方根中值為正的58a由矩陣乘法解得例59a設(shè)線性方程組的系數(shù)矩陣為三對角矩陣當(dāng)?shù)乃许樞蛑髯泳仃嚪瞧娈悤r(shí)可作如下分解2解三對角方程組的追趕法60a追趕法：（1）