計(jì)算方法3課件

1、第3章 線性方程組的數(shù)值解法三、 矩陣的三角分解及其應(yīng)用四、 線性代數(shù)方程組的性態(tài)與誤差分析五、 迭代法一、 線性方程組二、 高斯(Gauss)消元法求解上一頁(yè) 下一頁(yè) 返回 一、線性方程組 實(shí)際問題中的線性方程組分類：按系數(shù)矩陣中零元素的個(gè)數(shù)：稠密線性方程組稀疏線性方程組按未知量的個(gè)數(shù)：高階線性方程組低階線性方程組(如1000)(80%)按系數(shù)矩陣的形狀對(duì)稱正定方程組三角形方程組三對(duì)角占優(yōu)方程組 實(shí)際中，存在大量的解線性方程組的問題。很多數(shù)值方法到最后也會(huì)涉及到線性方程組的求解問題：如樣條插值的M和m關(guān)系式，曲線擬合的法方程，方程組的Newton迭代等問題。解線性方程組的兩類數(shù)值方法：直接法

2、: 經(jīng)過有限次四則運(yùn)算后可求得方程組精確解的方法(不計(jì)舍入誤差!)迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無(wú)窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）特點(diǎn)：準(zhǔn)確，可靠，理論上得到的解是精確的。適合于中小規(guī)模的方程組。特點(diǎn)：速度快，但有誤差。適合于大規(guī)模的方程組。Cramer法則是一種直接法，但無(wú)法實(shí)用 直接法概述直接法是將原方程組化為一個(gè)或若干個(gè)三角形方程組的方法對(duì)于線性方程組根據(jù)Cramer(克萊姆)法則,若則都是三角形方程組上述方法稱為直接三角形分解法不論是Gauss消元法還是直接三角形分解法,最終都?xì)w結(jié)為解三角形方程組一、三角形線性代數(shù)方程組的直接法若記下三角形線性方程組上

3、三角形線性方程組 Gauss消去法二、直接法 其解為其解為:按回代過程求解對(duì)方程組，作如下的變換，解不變：交換兩個(gè)方程的次序一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0的數(shù)一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0數(shù)，加到另一個(gè)方程二、Gauss消元法因此，對(duì)增廣矩陣(A，b )作如下的變換，解不變：交換矩陣的兩行某一行乘以一個(gè)非0的數(shù)某一行乘以一個(gè)非0數(shù)，加到另一行消元法就是對(duì)增廣矩陣作上述行的變換，變?yōu)槿切尉€性方程組，而后求根。用矩陣表示：=首先將A化為上三角陣，再回代求解。例3.1.1解化為同解方程組化為上三角方程組按回代過程求解上述求解三元線性代數(shù)方程組的方法即為Gauss消元法。(1) 定義行乘數(shù)相當(dāng)于第i

4、個(gè)方程-第一個(gè)方程行乘數(shù)新的第i方程同解！第一個(gè)方程不動(dòng)！ 且(1) 定義行乘數(shù)相當(dāng)于第i個(gè)方程-第二個(gè)方程行乘數(shù)新的第i方程同解！第一、二個(gè)方程不動(dòng)！ 系數(shù)矩陣與常數(shù)項(xiàng)： Gauss消元法的運(yùn)算量乘法次數(shù)：除法次數(shù)：全部回代過程需作乘除法的總次數(shù)為于是Gauss消元法的乘除法運(yùn)算總的次數(shù)為數(shù)級(jí)類似地，可得Gauss消元法的加減法運(yùn)算總的次數(shù)為由于計(jì)算機(jī)完成一次乘除運(yùn)算所耗時(shí)間要遠(yuǎn)遠(yuǎn)多于完成一次加減運(yùn)算的時(shí)間，而且按統(tǒng)計(jì)規(guī)律，在一個(gè)算法中，加減運(yùn)算和乘除運(yùn)算次數(shù)大體相當(dāng)，故在衡量一個(gè)算法的運(yùn)算量時(shí)只需統(tǒng)計(jì)乘除的運(yùn)算次數(shù)。Gauss消元法乘除法約為2700次而如果用Cramer法則的乘除法運(yùn)算次

5、數(shù)約為用行列式定義回代求解 從Gauss消元法的過程自然想到：如果在消元過程中把對(duì)角線上方未知量的系數(shù)也化為零，使方程組化成每個(gè)方程只含一個(gè)未知量的方程組，則無(wú)須回代就可得到解。這種消元法稱為GaussJordan消元法。但經(jīng)計(jì)算，它需要的乘除法次數(shù)為 顯然，其運(yùn)算量超過Gauss消元法。所以用GaussJordan消元法求解線性代數(shù)方程組是不可取的。不過，用它來求逆矩陣卻有方便之處。三、選主元Gauss消元法例3.1.3用Gauss消元法解線性方程組(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算）解本方程組的精度較高的解為用Gauss消元法求解(用3位十進(jìn)制浮點(diǎn)數(shù)計(jì)算)回代后得到主元9999與精確解相比,該結(jié)果相

6、當(dāng)糟糕！究其原因,在求行乘數(shù)時(shí)用了很小的數(shù)0.0001作除數(shù)! 上述例題表明：Gauss消元法是不穩(wěn)定的算法，其中小主元是不穩(wěn)定的根源。因而在Gauss消元法中要避免小主元的出現(xiàn)。這就需要采用“選主元”的技術(shù)。所謂選主元，簡(jiǎn)單地說就是選取絕對(duì)值最大的元素作主元。 全選主元Gauss消元法在此范圍內(nèi)選主元需進(jìn)行元素比較 列選主元Gauss消元法在此范圍內(nèi)選主元不必選主元的情況： 當(dāng)系數(shù)矩陣A對(duì)稱正定或嚴(yán)格對(duì)角占優(yōu)或不可約對(duì)角占優(yōu)時(shí)，可不必選主元?，F(xiàn)用列選主元消元法重解例3.1.3：將方程組的1,2行交換，即得回代后得到這是一個(gè)相當(dāng)不錯(cuò)的結(jié)果！0.9999例3.1.4解線性方程組(用8位十進(jìn)制尾數(shù)

7、的浮點(diǎn)數(shù)計(jì)算)解這個(gè)方程組和例3.1.3一樣，若用Gauss消元法計(jì)算會(huì)有小數(shù)作除數(shù)的現(xiàn)象，若采用換行的技巧（即列選主元消元法） ，則可避免。絕對(duì)值最大不需換行經(jīng)過回代后可得事實(shí)上,方程組的準(zhǔn)確解為 列選主元Gauss消元法的計(jì)算步驟? 列選主元Gauss消元法的流程圖開始輸出無(wú)解信息消元換行停機(jī)回代求解本算法主要由四個(gè)模塊組成 一些特殊情況, 主元就在對(duì)角線上,不需選主元. 元素滿足如下條件的矩陣 即對(duì)角線上每一元素的絕對(duì)值均大于同行其他各元素絕對(duì)值之和,這樣的矩陣稱為按行嚴(yán)格對(duì)角占優(yōu)矩陣,簡(jiǎn)稱嚴(yán)格對(duì)角占優(yōu)矩陣.例：性質(zhì)：嚴(yán)格對(duì)角占優(yōu)矩陣必定非奇異.上一頁(yè) 下一頁(yè) 返回 補(bǔ)充一、 LU分解法

8、 /* LU Factorization. */就 n=3的情況分析順序消去法的消元過程.上一頁(yè) 下一頁(yè) 返回 矩陣的三角(LU)分解法三、直接法 可見, 消元過程相當(dāng)于下述矩陣乘法運(yùn)算：由分塊乘法可得：直接計(jì)算可得由(*)式可得上一頁(yè) 下一頁(yè) 返回 Step 1:記M(1) =，則Step n 1: 其中 M (k)= 以上分析推廣到n階線性方程組可得上一頁(yè) 下一頁(yè) 返回 記為L(zhǎng)單位下三角陣/* unitary lower-triangular matrix */記 U =A 的 LU 分解/* LU factorization */也稱 A 的Doolittle分解上一頁(yè) 下一頁(yè) 返回 道

9、立特分解法 /* Doolittle Factorization */： LU 分解的緊湊格式 /* compact form */根據(jù)矩陣乘法法則,先比較等式兩邊第1行和第1列元素有：上一頁(yè) 下一頁(yè) 返回 設(shè)已定出U 的第1行到第k-1行的元素 L 的第1列到第k-1列的元素上一頁(yè) 下一頁(yè) 返回 (1),(2)兩式就是 LU分解的一般計(jì)算公式, 其結(jié)果與高斯消去法所得結(jié)果完全一樣. 避免了中間過程的計(jì)算,故稱為A的直接分解公式.上一頁(yè) 下一頁(yè) 返回 按上圖逐框求出矩陣A的LU分解,這種計(jì)算方法稱為緊湊格式法。上一頁(yè) 下一頁(yè) 返回 定理 若矩陣A非奇異, 則A能分解為L(zhǎng)U 的充分必要條件是A的

10、所有順序主子式 均不為0.定理 若非奇異矩陣A有LU 分解,則此分解是唯一的.上一頁(yè) 下一頁(yè) 返回 矩陣的Doolittle分解法的Matlab程序function 1,u=lu_Doolittle1(A)%A為可逆方陣，l為返回下三角矩陣，u為上三角陣n=length(A);u=zeros(n);l=eye(n);u(1,:)=A(1,:);l(2:n,1)=A(2:n,1)/u(1,1);for k=2:n u(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n); l(k+1:n,k)=(A(k+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/

11、u(k,k);end例：利用系數(shù)矩陣的LU分解, 求解方程組解：LU分解的緊湊格式為上一頁(yè) 下一頁(yè) 返回 在Matlab命令窗口執(zhí)行A=1 1 1 1;1 2 1 3;4 3 2 1;6 11 3 7;l,u=lu_Doolittle1(A)則求解原方程組等價(jià)于求解下面兩個(gè)方程組Ly=b及Ux=y上一頁(yè) 下一頁(yè) 返回 在Matlab命令窗口執(zhí)行A=1 1 1 1;1 2 1 3;4 3 2 1;6 11 3 7;b=6 12 14 45;y,x=LU_s(A,b)A=LU若U為單位上三角矩陣，則稱為Crout分解.Crout分解相應(yīng)的求解公式可類似得到。上一頁(yè) 下一頁(yè) 返回 二、平方根法 對(duì)稱

12、 正定矩陣的分解法將對(duì)稱 正定陣 A 做 LU 分解記為定理 設(shè)n階對(duì)稱正定矩陣A，則存在唯一的單位下三角陣L及對(duì)角陣D 使得 。 稱為矩陣A 的喬累斯基分解上一頁(yè) 下一頁(yè) 返回 定理 設(shè)矩陣A對(duì)稱正定，則存在唯一的對(duì)角元為正的下三角陣 L，使得 。 稱為對(duì)稱正定矩陣A 的喬累斯基分解 利用喬累斯基（Cholesky）分解式來求解Ax=b的方法也稱Cholesky方法或平方根法三、三對(duì)角方程組追趕法若A滿足Gauss消去法可行的條件，則可用LU分解法求解其中：上一頁(yè) 下一頁(yè) 返回 解方程組Ax=d分為兩步，即求解Ly=d和Ux=y，計(jì)算公式如下：上述方法為求解三對(duì)角方程組的追趕法，也稱Thom

13、as算法.上一頁(yè) 下一頁(yè) 返回 追趕法公式簡(jiǎn)單，計(jì)算量和存儲(chǔ)量都小，整個(gè)求解過程只需要5n-4次乘除運(yùn)算。 在分析方程組的解的誤差及下章中迭代法的收斂性時(shí)，常產(chǎn)生一個(gè)問題,即如何判斷向量 x 的“大小”，對(duì)矩陣也有類似的問題. 本節(jié)介紹n維向量范數(shù)和nn矩陣的范數(shù). 向量范數(shù)是三維歐氏空間中向量長(zhǎng)度概念的推廣，在數(shù)值分析中起著重要作用.四、線性代數(shù)方程組的性態(tài)與誤差分析定義3.3.1(一)向量和矩陣的范數(shù)按某種規(guī)則(或映射)1. 向量的范數(shù)由(3)可推出不等式：-(1)-(2)-(3)-(4)顯然并且由于例3.3.1 求下列向量的各種常用范數(shù)解向量范數(shù)是其分量的連續(xù)函數(shù)，即有下述定理：定理3.

14、3.1（向量范數(shù)連續(xù)性定理）證明 向量序列的收斂性定義3.3.2 如果向量序列x(k)Rn和向量 xRn滿足則稱向量序列x(k)收斂于向量 x，記為顯然，Rn 中向量序列x(k)收斂于 x 的充分必要條件是由下面向量范數(shù)的等價(jià)性定理可得到結(jié)論：如果在一種范數(shù)意義下向量序列收斂時(shí)，則在任何一種范數(shù)意義下向量序列亦收斂，即 有限維向量空間的范數(shù)等價(jià)性定理定理3.3.2注： 上述結(jié)論不能推廣到無(wú)限維空間。容易驗(yàn)證： （1） x2x1 n1/2x2； （2）xx2 n1/2x； （3）xx1 nx。3種范數(shù)相互等價(jià)證明 由 x12+ x22+ + xn2(|x1|+ |x2|+ +| xn|) 2，兩

15、邊開方得第一式成立； 由 (|x1|+ |x2|+ +| xn|) 2 n( |x1|2+ |x2|2+ + |xn|2)，兩邊開方得第二式成立。定義3.3.32. 矩陣的范數(shù)例3.3.2不難驗(yàn)證其滿足定義3.3.3的4個(gè)條件稱為Frobenius范數(shù)，簡(jiǎn)稱F-范數(shù)而且可以驗(yàn)證tr為矩陣的跡-(5)-(6)類似向量的 2-范數(shù)定義3.3.4-(7)簡(jiǎn)稱為從屬范數(shù)或?qū)С龇稊?shù)或算子p-范數(shù)由此可知，給出一種向量范數(shù)，就有一種相應(yīng)的矩陣范數(shù)顯然，由定義不難推出定義3.3.5由(8)式,可知算子范數(shù)和其對(duì)應(yīng)的向量范數(shù)是相容的-(8)-(9)根據(jù)向量的常用范數(shù)可以得到常用的矩陣算子范數(shù)-(10)-(11

16、)-(12)證明見書P70例3.3.3 解類似于向量的2-范數(shù)不過例3.3.4求矩陣A的各種常用范數(shù)解由于特征方程為容易計(jì)算計(jì)算較復(fù)雜對(duì)矩陣元素的變化比較敏感不是從屬范數(shù)較少使用(理論上)使用最廣泛性質(zhì)較好 矩陣范數(shù)的等價(jià)性定理定理3.3.3可以驗(yàn)證： （1）A2AF n1/2A2； （2） n-1/2 AA2 n1/2A； （3） n-1/2 A1A2 nA14種范數(shù)相互等價(jià)定義3.3.5-(13) 矩陣的譜半徑顯然，由定義可知定理3.3.4而證明實(shí)特征值為絕對(duì)值，復(fù)特征值為模即所以因此定理3.3.5 補(bǔ)充 矩陣序列的收斂性定義3.3.6 如果n階矩陣序列A(k) Rnn和矩陣ARnn 滿足

17、 （ 其中A(k)=(aij(k)nn , A=(aij)nn）則稱矩陣序列A(k)收斂于矩陣 A，記為顯然，Rnn 中矩陣序列A(k) 收斂于矩陣A 的充分必要條件是定理3.3.6 證明定理3.3.7-(14)證明補(bǔ)充練習(xí) 設(shè)則求相應(yīng)的各種范數(shù).解因?yàn)榱畹肁TA的特征值故可見求A1, A2 , A , (A).作業(yè)：設(shè) ,解: 顯然A1 =4,A=4 這里, 我們指出, 對(duì)于實(shí)對(duì)稱矩陣A, 有(A)=|A|2.(二) 線性代數(shù)方程組的性態(tài)與誤差分析1. 線性代數(shù)方程組的性態(tài) 判斷一個(gè)計(jì)算方法的好壞，可用方法是否穩(wěn)定、解的精確度高低以及計(jì)算量、存儲(chǔ)量大小等來衡量。然而，對(duì)于不同的問題，同一方法

18、卻可以產(chǎn)生完全不同的效果，這就涉及到所提供問題的性態(tài)，即“好、壞”。例3.3.5 可見，在上述方程組中，系數(shù)誤差的小擾動(dòng)對(duì)解的影響不大?？梢姡谏鲜龇匠探M中，系數(shù)誤差的小擾動(dòng)對(duì)解的影響很大。-(1)-(2)-(3)定義3.3.7定理3.3.8推論1推論2 常數(shù)項(xiàng) b 的擾動(dòng)對(duì)解的影響 系數(shù)矩陣A 的擾動(dòng)對(duì)解的影響定義3.3.8矩陣A的條件數(shù)與所取范數(shù)有關(guān)。通常記顯然，當(dāng)A對(duì)稱時(shí)，例3.3.6 試求例3.3.5中兩個(gè)線性代數(shù)方程組的條件數(shù)解 因而，第二個(gè)方程組的性態(tài)遠(yuǎn)比第一個(gè)方程組壞， 從而對(duì)系數(shù)的敏感程度要高得多。值得強(qiáng)調(diào)的是，線性代數(shù)方程組的性質(zhì)是問題本身的固有性質(zhì)。用一個(gè)穩(wěn)定的方法去解一個(gè)

19、良態(tài)的方程組，必然得到較準(zhǔn)確的結(jié)果。同樣用一個(gè)穩(wěn)定的方法去解一個(gè)病態(tài)的方程組，結(jié)果就可能很差。例3.3.7 解線性代數(shù)方程組的精確解為用列選主元消元法計(jì)算：回代后得到計(jì)算結(jié)果完全不可靠，實(shí)際上，此時(shí)因此，方程組病態(tài)！如把方程組的系數(shù)舍入成兩位有效數(shù)字例3.3.8設(shè)有線性代數(shù)方程組試分析其性態(tài)。試分別計(jì)算兩組方程組的精確解。它的精確解為x1 = -6.222. x2= 38.25 x3= -33.65.它的精確解為x1=x2=x3=1.條件數(shù)不是很好。兩個(gè)解相差大，說明解對(duì)系數(shù)矩陣敏感程度高事實(shí)上，上例中矩陣A是三階Hilbert矩陣n階Hilbert矩陣是有名的病態(tài)矩陣，它隨著矩陣階數(shù)的增大，

20、條件數(shù)迅速增大。解 “病態(tài)”方程的經(jīng)驗(yàn)判斷 “病態(tài)”問題的處理方法例3.3.9 解回代后得到用列選主元消元法計(jì)算：計(jì)算解很精確例3.3.10 解等價(jià)的方程組解回代后得到用列選主元消元法計(jì)算：與例3.3.7的計(jì)算結(jié)果相比，這是一個(gè)很好的近似解定理3.3.92. 誤差分析證明注: cond (A) 的具體大小與 | | 的取法有關(guān)，但相對(duì)大小一致。 cond (A) 取決于A，與解題方法無(wú)關(guān)。常用條件數(shù)有：cond 1(A)cond (A)cond2 (A)條件數(shù)的性質(zhì)： A可逆，則 cond p (A) 1； A可逆， R 則 cond ( A) = cond (A) ； A正交，則 cond

21、2 (A) =1； A可逆，R正交，則 cond 2 (RA) = cond 2 (AR) = cond (A)2 。上一頁(yè) 下一頁(yè) 返回 注：一般判斷矩陣是否病態(tài)，并不計(jì)算A1，而由經(jīng)驗(yàn)得出。 行列式的值很大或很?。ㄈ缒承┬?、列近似相關(guān)）； 元素間的數(shù)量級(jí)相差大，且無(wú)規(guī)則； 主元消去過程中出現(xiàn)小主元； 特征值相差大數(shù)量級(jí)。 直接法: 經(jīng)過有限次運(yùn)算后可求得方程組精確解的方法(不計(jì)舍入誤差!) 直接法比較適用于中小型方程組。直接法得到的解理論上是準(zhǔn)確的，但它們的計(jì)算量都是n3數(shù)量級(jí)，存儲(chǔ)量為n2數(shù)量級(jí)，這在n比較小的時(shí)候還比較合適（n400）。對(duì)于現(xiàn)在的很多實(shí)際問題，往往要我們求解n很大的高階方程組