線性代數方程組的直接解法第1頁，課件共74頁，創作于2023年2月線性方程組的數值解法一般有兩類：直接法：就是經過有限步算術運算，可求得方程組精確解的方法（若計算過程中沒有舍入誤差），如克萊姆法則就是一種直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法:(第四章介紹）就是用某種極限過程去逐步逼近線性方程組的精確解的方法。也就是從解的某個近似值出發，通過構造一個無窮序列去逼近精確解的方法。(一般有限步內得不到精確解)第2頁，課件共74頁，創作于2023年2月3.2解線性方程組的直接法（高斯消去法）

3.2.1高斯消去法的基本思想例3.1解線性方程組

①②③解:

該方程組的求解過程實際上是將中學學過的消元法標準化,將一個方程乘或除以某個常數,然后將兩個方程相加減,逐步減少方程中的未知數,最終使每個方程只含有一個未知數,從而得出所求的解。整個過程分為消元和回代兩個部分。

第3頁，課件共74頁，創作于2023年2月（1）消元過程第1步:將方程①乘上(-2)加到方程②上去,將方程①乘上加到方程③上去,這樣就消去了第2、3個方程的項,于是就得到等價方程組④⑤第4頁，課件共74頁，創作于2023年2月第2步：將方程

④乘上加到方程

⑤上去，這樣就消去了第3個方程的項，于是就得到等價方程組

⑥這樣，消元過程就是把原方程組化為上三角形方程組，其系數矩陣是上三角矩陣。

（2）回代過程回代過程是將上述三角形方程組自下而上求解，從而求得原方程組的解：

第5頁，課件共74頁，創作于2023年2月前述的消元過程相當于對原方程組

的增廣矩陣進行下列變換(表示增廣矩陣的第行）同樣可得到與原方程組等價的方程組⑥第6頁，課件共74頁，創作于2023年2月

由此看出,高斯消去法解方程組基本思想是設法消去方程組的系數矩陣A的主對角線下的元素,而將Ax=b化為等價的上三角形方程組,然后再通過回代過程便可獲得方程組的解。換一種說法就是用矩陣行的初等變換將原方程組系數矩陣化為上三角形矩陣,而以上三角形矩陣為系數的方程組的求解比較簡單,可以從最后一個方程開始,依次向前代入求出未知變量這種求解上三角方程組的方法稱為回代,通過一個方程乘或除以某個常數,以及將兩個方程相加減,逐步減少方程中的變元數,最終將方程組化成上三角方程組,一般將這一過程稱為消元,然后再回代求解。通常把按照先消元,后回代兩個步驟求解線性方程組的方法稱為高斯（Gauss）消去法。第7頁，課件共74頁，創作于2023年2月3.2.2高斯消去法算法構造

線性方程組(3.1)用矩陣形式表示為

(3.3)解線性方程組（3.1）的高斯（Gauss）消去法的消元過程就是對(3.3)的增廣矩陣進行行初等變換。將例3.1中解三階線性方程組的消去法推廣到一般的階線性方程組并記則高斯消去法的算法構造歸納為：

第8頁，課件共74頁，創作于2023年2月⑴消元過程,高斯消去法的消元過程由n-1步組成：第1步設,把(3.3)中的第一列中元素消為零,令用乘以第1個方程后加到第個方程上去,消去第2～n個方程的未知數,得到即其中

第9頁，課件共74頁，創作于2023年2月第k步

（k=2,3,…,n-1）繼續上述消元過程，設第k-1次消元已經完成，得到與原方程組等價的方程組

記為其中第10頁，課件共74頁，創作于2023年2月只要,消元過程就可以進行下去,直到經過n-1次消元之后，消元過程結束，得到與原方程組等價的上三角形方程組,記為或者寫成

第11頁，課件共74頁，創作于2023年2月即

(3.7)（2）回代過程就是對上三角方程組（3.7）自下而上逐步回代解方程組計算，即

第12頁，課件共74頁，創作于2023年2月（3）高斯消去法的計算步驟：①消元過程;設計算②回代過程

第13頁，課件共74頁，創作于2023年2月(4)高斯消去法流程圖

，見P42(5)

Gauss消去法計算量≈①消元計算:aij(k+1)=aij(k)-mik

akj(k)

(i,j=k+1,k+2,…,n)第一步計算乘數mik,mik=ai1/a11

(i=2,3,…,n)需要n-1次除法運算,計算aij(2）(i,j=2,3,…,n)需要(n-1)2次乘法運算及(n-1)2次加減法運算,第14頁，課件共74頁，創作于2023年2月第k步加減法次數乘法次數除法次數123…n-1(n-1)2(n-2)2(n-3)2…1(n-1)2(n-2)2(n-3)2…1(n-1)(n-2)(n-3)…1合計n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次數：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3n(n2-1)加減法次數：AS=n(n-1)(2n-1)/6第15頁，課件共74頁，創作于2023年2月3.2.3高斯消去法的適用條件定理3.1方程組系數矩陣的順序主子式全不為零則高斯消去法能實現方程組的求解。證明上三角形方程組是從原方程組出發，通過逐次進行“一行乘一數加到另一行”而得出的，該變換不改變系數矩陣順序主子式的值。

第16頁，課件共74頁，創作于2023年2月設方程組系數矩陣，其順序主子式（m=1,2,…，n）

經變換得到的上三角形方程組的順序主子式所以能實現高斯消去法求解

（m=1,2,…，n）第17頁，課件共74頁，創作于2023年2月定義3.1設矩陣每一行對角元素的絕對值都大于同行其他元素絕對值之和

則稱A為嚴格對角占優矩陣。

定理3.2若方程組的系數矩陣A為嚴格對角占優，則用高斯消去法求解時，全不為零。

第18頁，課件共74頁，創作于2023年2月證:先考察消元過程的第1步,因A為嚴格對角占優,故故,又根據高斯消去公式得

于是再利用方程組的對角占優性,由上式可進一步得又由得

故有當A為嚴格對角占優時,,余下的子陣仍是對角占優的，從而又有。依次類推全不為零。定理證畢。第19頁，課件共74頁，創作于2023年2月一般線性方程組使用高斯消去法求解時，在消元過程中可能會出現的情況，這時消去法將無法進行；即使，但它的絕對值很小時，用其作除數，會導致其他元素數量級的嚴重增長和舍入誤差的擴散，將嚴重影響計算結果的精度。實際計算時必須避免這類情況的發生。主元素消去法就可彌補這一缺陷。第20頁，課件共74頁，創作于2023年2月交換原則：通過方程或變量次序的交換，使在對角線位置上獲得絕對值盡可能大的系數作為akk(k)，稱這樣的akk(k)

為主元素，并稱使用主元素的消元法為主元素法根據主元素選取范圍分為：列主元素法、行主元素法、全主元素法記筆記3.2.4高斯主元素消去法第21頁，課件共74頁，創作于2023年2月主元素法的意義例3.2用高斯消去法求下列方程組的解

解：確定乘數，再計算系數假設計算在4位浮點十進值的計算機上求解,則有

這時方程組的實際形式是

由此回代解出,但這個解不滿足原方程組,解是錯誤的。這是因為所用的除數太小使得上式在消元過程中“吃掉”了下式，解決這個問題的方法之一就是采用列選主元高斯消元法。即按列選絕對值大的系數作為主元素，則將方程組中的兩個方程相交換，原方程組變為

得到消元后的方程組第22頁，課件共74頁，創作于2023年2月這時

因而方程組的實際形式是由此回代解出,這個結果是正確的可見用高斯消去法解方程組時,小主元可能導致計算失敗,因為用絕對值很小的數作除數,乘數很大,引起約化中間結果數量級嚴重增長,再舍入就使得計算結果不可靠了,故避免采用絕對值很小的主元素。以便減少計算過程中舍入誤差對計算解的影響。第23頁，課件共74頁，創作于2023年2月全主元素消去法是通過方程或變量次序的交換，使在對角線位置上獲得絕對值盡可能大的系數作為，稱這樣的為主元素。盡管它的算法更穩定，但計算量較大，實際應用中大多數使用列主元素消去法即可滿足需要。

第24頁，課件共74頁，創作于2023年2月全主元素法不是按列選主元素，而是在全體待選系數中選取，則得全主元素法。例3.3用全主元素法解下列線組

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解：選擇所有系數中絕對值最大的40作為主元素，交換第一、二行和交換第一、二列使該主元素位于對角線的第一個位置上，得40x2-20x1+

x3=4(4)-19x2+10x1-2x3=3(5)

4x2+x1+5x3=5(6)記筆記第25頁，課件共74頁，創作于2023年2月計算m21=-19/40=0.475，m31=4/40=0.1(5)-m21(4),(6)-m31(4)消去x2

得0.5x1–1.525x3=4.9(7)3x1+4.9

x3=4.6(8)選4.9為主元素

4.9x3+3x1=4.6(9)1.525x3+0.5x1=4.9(10)計算m32=-1.525/4.9=-0.31122，(10)-m32(9)消去x2得1.43366x1=6.33161(11)記筆記第26頁，課件共74頁，創作于2023年2月保留有主元素的方程40x2-20x1+

x3=4(4)

4.9x3+3x1=4.6(9)

1.43366x1=6.33161(11)進行回代x1=4.41634

x3=-1.76511x2=2.35230第27頁，課件共74頁，創作于2023年2月3.2.4.1列主元素法列主元素法就是在待消元的所在列中選取主元，經方程的行交換，置主元素于對角線位置后進行消元的方法。例3.4用列主元素法解下列線性方程組

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解：選擇-20作為該列的主元素，-20x1+40x2+x3=3(4)

10x1-19x2-2x3=4(5)x1+4x2+5x3=5(6)計算m21

=10/-20=-0.5

m31=1/-20=-0.05第28頁，課件共74頁，創作于2023年2月(5)-m21(4),(6)-m31(4)得x2–1.5x3=5(7)6x2+5.05x3=5.2(8)選6為主元素6x2+5.05x3=5.2(9)x2–1.5x3=5(10)計算m32=1/6=0.16667，

(10)-m32(9)得-2.34168x3=4.13332(11)記筆記第29頁，課件共74頁，創作于2023年2月保留有主元素的方程-20x1+40x2+x3=4(4)6x2+5.05x3=5.2(9)-2.34168x3=4.13332(11)進行回代x3=-1.76511x2=2.35230x1=4.41634記筆記

列選主元素的計算方法與高斯消去法完全一樣,不同的是在每步消元之前要按列選出主元第30頁，課件共74頁，創作于2023年2月例3.5用矩陣的初等行變換求解解方程組

解:用矩陣的初等行變換求解,對增廣矩陣(下面帶下劃線元素為主元素)第31頁，課件共74頁，創作于2023年2月第32頁，課件共74頁，創作于2023年2月3.3矩陣三角分解法

3.3.1矩陣三角分解原理

應用高斯消去法解n階線性方程組Ax=b,經過n步消元之后,得出一個等價的上三角型方程組A(n)x=b(n),對上三角形方程組用逐步回代就可以求出解來。上述過程可通過矩陣分解來實現。將非奇異陣A分解成一個下三角陣L和一個上三角陣U的乘積A=LU稱為對矩陣A的三角分解，又稱LU分解第33頁，課件共74頁，創作于2023年2月其中第34頁，課件共74頁，創作于2023年2月方程組Ax=b的系數矩陣A經過順序消元逐步化為上三角型A(n),相當于用一系列初等變換左乘A的結果。事實上，第1列消元將A(1)=A化為A(2)，若令：則根據距陣左乘有L1A(1)=A(2)第35頁，課件共74頁，創作于2023年2月第2列消元將A(2)化為A(3)，若令：經計算可知L2A(2)=A(3),依此類推,一般有LkA(k)=A(k+1)第36頁，課件共74頁，創作于2023年2月mi1=a(1)

i1/a(1)

11i=2,3,……n于是矩陣經過消元化為上三角陣的過程可表示為上述矩陣是一類初等矩陣,它們都是單位下三角陣，且其逆矩陣也是單位下三角陣,只需將

改為,就得到。即第37頁，課件共74頁，創作于2023年2月于是有

其中第38頁，課件共74頁，創作于2023年2月L為由乘數構成的單位下三角陣，U為上三角陣，由此可見，在的條件下，高斯消去法實質上是將方程組的系數矩陣A分解為兩個三角矩陣的乘積A=LU。這種把非奇異矩陣A分解成一個下三角矩陣L和一個上三角矩陣U的乘積稱為矩陣的三角分解，又稱LU分解。顯然，如果,由行列式的性質知，方程組系數矩陣A的前n-1個順序主子矩陣非奇異，即順序主子式不等于零，即第39頁，課件共74頁，創作于2023年2月其中（A的主子陣）

反之,可用歸納法證明,如果A的順序主子式則于是得到下述定理：

第40頁，課件共74頁，創作于2023年2月定理3.5設。如果A順序各階主子式,,則A可惟一地分解成一個單位下三角陣L和一個非奇異的上三角陣U的乘積。證：由于A各階主子式不為零,則消元過程能進行到底,前面已證明將方程組的系數矩陣A用初等變換的方法分解成兩個三角矩陣的乘積A=LU的過程。

現僅證明分解的惟一性。設A有兩種LU分解其中為單位下三角陣，為上三角陣

∵A的行列式均為非奇異矩陣,有上式兩邊左邊同乘，右邊同乘得上式左邊為單位下三角陣,右邊為上三角陣,故應為單位陣,即惟一性得證。第41頁，課件共74頁，創作于2023年2月把A分解成一個單位上三角陣L和一個下三角陣U的乘積稱為杜利特爾（Doolittle）分解。其中

第42頁，課件共74頁，創作于2023年2月若把A分解成一個下三角陣L和一個單位上三角陣U的乘積稱為克洛特分解Crout）

其中第43頁，課件共74頁，創作于2023年2月3.3.2用三角分解法解方程組求解線性方程組Ax=b時,先對非奇異矩陣A進行LU分解使A=LU，那么方程組就化為LUx=b從而使問題轉化為求解兩個簡單的的三角方程組Ly=b求解yUx=y求解x這就是求解線性方程組的三角分解法的基本思想。下面只介紹杜利特爾（Doolittle）分解法。設A=LU為第44頁，課件共74頁，創作于2023年2月由矩陣乘法規則由此可得U的第1行元素和L的第1列元素第45頁，課件共74頁，創作于2023年2月再確定U的第k行元素與L的第k列元素,對于k=2,3,…,n計算：①

計算U的第k行元素

（j=k,k+1,…,n）

②計算L的第k列元素（i=k,k+1,…,n）

第46頁，課件共74頁，創作于2023年2月利用上述計算公式便可逐步求出U與L的各元素求解Ly=b,即計算:

求解Ux=y,即計算：第47頁，課件共74頁，創作于2023年2月顯然,當時,解Ax=b直接三角分解法計算才能完成。設A為非奇異矩陣,當時計算將中斷或者當絕對值很小時，按分解公式計算可能引起舍入誤差的積累，因此可采用與列主元消去法類似的方法，對矩陣進行行交換，則再實現矩陣的三角分解。用直接三角分解法解Ax=b大約需要次乘除法。

第48頁，課件共74頁，創作于2023年2月例3.8用三角分解法解方程組

求解Ly=b得y=[2，2，1]T

求解Ux=y得x=[-1，0，1]T所以方程組的解為

第49頁，課件共74頁，創作于2023年2月3.5追趕法在數值計算中,有一種系數矩陣是三對角方程組

簡記為Ax=f,A滿足條件（1）（2）（3）第50頁，課件共74頁，創作于2023年2月用歸納法可以證明，滿足上述條件的三對角線性方程組的系數矩陣A非奇異，所以可以利用矩陣的直接三角分解法來推導解三對角線性方程組的計算公式，用克洛特分解法，將A分解成兩個三角陣的乘積，設A=LU

按乘法展開

則可計算

可依次計算當，由上式可惟一確定L和U。

第51頁，課件共74頁，創作于2023年2月例3.9用追趕法求解三對角方程組

解由Ly=f

解出y又由Ux=y解出x第52頁，課件共74頁，創作于2023年2月記筆記3.6向量和矩陣的范數向量范數是用來度量向量長度的,它可以看成是二、三維解析幾何中向量長度概念的推廣。用Rn表示n維實向量空間。第53頁，課件共74頁，創作于2023年2月記筆記3.6向量和矩陣的范數定義3.2

對任一向量XRn,按照一定規則確定一個實數與它對應,該實數記為||X||,若||X||滿足下面三個性質:(1)||X||0；||X||=0當且僅當X=0；(2)對任意實數，||X||=||||X||；對任意向量YRn，||X+Y||||X||+||Y||

則稱該實數||X||為向量X的范數第54頁，課件共74頁，創作于2023年2月在Rn中，常用的幾種范數有：記筆記其中x1,x2,…,xn分別是X的n個分量。以上定義的范數分別稱為1-范數，2-范數和-范數第55頁，課件共74頁，創作于2023年2月當不需要指明使用哪一種向量范數時，就用記號||.||泛指任何一種向量范數。有了向量的范數就可以用它來衡量向量的大小和表示向量的誤差。設x*為Ax=b的精確解，x為其近似解，則其絕對誤差可表示成||x-x*||，其相對誤差可表示成記筆記3.6向量和矩陣的范數或第56頁，課件共74頁，創作于2023年2月第57頁，課件共74頁，創作于2023年2月例3.11設x=(1,0,-1,2)T,計算

解:=1+0+|-1|+2=4第58頁，課件共74頁，創作于2023年2月定理3.7對于任意向量x,有證:∵

∴即

當p→∞，

∴第59頁，課件共74頁，創作于2023年2月定義3.4(向量序列的極限)設為中的一向量序列，,記。如果(i=1,2,…,n)，則稱收斂于向量，記為定理3.8（向量范數的等價性）設為上任意兩種向量范數,則存在常數C1,,C2>0,使得對任意恒有（證:略）

第60頁，課件共74頁，創作于2023年2月定理3.9

其中為向量中的任一種范數。

證由于

而對于上的任一種范數,由定理3.7知存在常數C1，C2，使于是可得從而定理得證。第61頁，課件共74頁，創作于2023年2月定義3.5（矩陣的范數）如果矩陣的某個

非負的實值函數，滿足則稱是上的一個矩陣范數(或模)第62頁，課件共74頁，創作于2023年2月第63頁，課件共74頁，創作于2023年2月定義3.7（矩陣的譜半徑）設的特征值為,稱為A的譜半徑。例3.12計算方陣

的三種常用范數第64頁，課件共74頁，創作于2023年2月例3.12計算方陣

的三種范數

解先計算

所以,從而

第65頁，課件共74頁，創作于2023年2月定理3.11設A為n階方陣,則對任意矩陣范數都有證:設為A的特征值，x是對應于的特征向量,則x=Ax。兩端取范數并依據其性質得由于x≠0，故，所以第66頁，課件共74頁，創作于2023年2月3.7誤差分