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

1、第三章 線性方程組的數(shù)值解法,討論線性方程組解法的必要性,工程實(shí)際中的許多問題都?xì)w結(jié)為解線性方程組,我們知道線 性方程組 a11x1+ a12x2+ +a1nxn=b1 a21x1+ a22x2+ +a2nxn=b2 an1x1+ an2x2+ +annxn=b2 即 Ax = B 若|A| 0, 根據(jù)克萊姆(Gramer)法則, 方程組有唯一解 Xi=Di/D ( i=1, 2 , , n ) 然而,對(duì)于較高階的情況, 用這種方法求解是不現(xiàn)實(shí)的。一 個(gè) n 階行列式有 n! 項(xiàng), 每一項(xiàng)又是 n 個(gè)數(shù)的乘積。就算不計(jì)舍 入誤差對(duì)計(jì)算結(jié)果的影響 , 對(duì)較大的 n , 其運(yùn)算量之大 不考 慮加減

2、，僅乘除次數(shù)就需 (n+1) n! (n-1) +n , 也是計(jì)算機(jī)在一般 情況下難以容許的。因此 , 我們要討論線性方程組的另外兩種 解法: 直接法和迭代法。,解線性方程組的直接法和迭代法,一、直接法 經(jīng)過有限步運(yùn)算就能求得精確解的方法。 包括： 1. 順序高斯消去法 2. 選主元高斯消去法 3. 高斯約當(dāng)消去法 4. 矩陣三角分解法 二、迭代法 用某種極限過程去逐步逼近精確解的方法。 包括： 1. 雅可比迭代法 2. 賽得爾迭代法 3. 松弛迭代法 下面我們將介紹解線性方程組的直接法。,第一節(jié) 順序高斯消去法,一、順序高斯消去法的基本思想,順序高斯消去法分為消元和回代兩個(gè)過程。 首先應(yīng)用矩

3、陣的初等變換將系數(shù)矩陣A按自然順序化為上三角矩陣，與此同時(shí)將方程的右端向量B增補(bǔ)作為A的第n+1列，構(gòu)成增廣矩陣，同時(shí)參加變換。然后應(yīng)用回代過程計(jì)算方程的解。,二、順序高斯消去法舉例,例 2x1 + 6x2 - 4x3 = 4 (1) x1 + 4x2 - 5x3 = 3 (2) 6x1 - x2 +18x3 = 2 (3) 解 a. 消元過程 第一次消元： (1)(-1/2)+(2) 、(1)(-6/2)+(3) 得 2x1 + 6x2 - 4x3 = 4 (1) x2 - 3x3 = 1 (2) -19x2 + 30 x3 = -10 (3) 第二次消元： (2) (-(-19)/1)+(

4、3) 得 2x1 + 6x2 - 4x3 = 4 (1) x2 - 3x3 = 1 (2) - 27x3 = 9 (3) b. 回代過程 x3 = 9/(-27) = -1/3， x2 = 1 + 3x3 = 1-1= 0， x1 = (4 + 4x3 + 6x2 )/2= (4+4(-1/3)+60)/2 = 4/3,三、一般線性方程組的求解過程(第一次消元過程) 第一次消元過程: 推出: 第一次消元即: ( i , j = 2, 3, , n ),三、一般線性方程組的求解過程(第k次消元及回代過程) 第k次消元過程: (i, j=k+1, , n) 回代過程: （i =n-1,2,1）,四

5、、順序高斯消去法計(jì)算量分析,用計(jì)算機(jī)作四則運(yùn)算時(shí)，加減操作所花的機(jī)器時(shí)間比乘除操 作少得多, 所以我們僅統(tǒng)計(jì)乘除次數(shù)。 1. 消元過程(共需n-1次消元） 第k次消元時(shí)需除：n-k 第k次消元時(shí)需乘：(n-k)(n-k+1) 共需乘除次數(shù)： (n-1)+(n-1)n+(n-2)+(n-2)(n-1)+1+12 = n3/3+n2 /2-5n/6 2. 回代過程 需除：n 需乘：1+2+(n-1)= (n-1)n/2 共需乘除次數(shù)：n+ (n-1)n/2= n2/2+n/2 所以總共需乘除次數(shù): n3/3+n2 /2-5n/6+n2/2+n/2 = n3/3+n2 -n/3 。 n3/3+n2

6、-n/3(n+1) n! (n-1)+n(克萊姆法則需的乘除次數(shù)),因此 順序高斯消去法從計(jì)算量上考慮是可行的。,五、順序高斯消去法計(jì)算機(jī)實(shí)現(xiàn),根據(jù)一般線性方程組的求解過程知,消元過程實(shí)際 上是一個(gè)三重（層）循環(huán)，而回代過程實(shí)際上是一個(gè) 二重（層）循環(huán)。據(jù)此，我們便可編出求解線性方程 組的程序。,第二節(jié) 選主元高斯消去法,前面介紹的順序高斯消去法,也叫順序選主元法。 當(dāng)出現(xiàn)主元素 akk(k) = 0 時(shí), 消元過程將無法繼續(xù)進(jìn)行， 或者即使akk(k) 0時(shí)，但如果絕對(duì)值很小，用它作除 數(shù)也會(huì)導(dǎo)致其它元素的數(shù)量級(jí)急劇增大和舍入誤差擴(kuò) 大, 將嚴(yán)重影響計(jì)算結(jié)果的精度。為了克服這一缺陷， 下面介

7、紹選主元高斯消去法。選主元高斯消去法有列 主元高斯消去法和全主元高斯消去法兩種。我們首先 介紹列主元高斯消去法。,一、列主元高斯消去法,列主元消去法的主要思想是：在第k次消元時(shí)，從k列的以下的各個(gè)元素中選出絕對(duì)值最大的元素，然后通過行交換將其交換到k行上，再做第k次消元（同順序高斯消去法）；回代過程與順序高斯消去法完全相同。,用列主元高斯消去法解線性方程組舉例 例 0.01x1 + 2x2 - 0.5x3 = - 5 - x1 - 0.5x2 + 2x3 = 5 5x1 - 4x2 + 0.5x3 = 9 解 0.01 2 - 0.5 - 5 5 - 4 0.5 9 A,b = - 1 - 0

8、.5 2 5 (1) (3) -1 - 0.5 2 5 5 - 4 0.5 9 0.01 2 - 0.5 5 (2)+(1)*1/5 5 - 4 0.5 9 5 - 4 0.5 9 (3)-(1)*1/500 0 - 1.30 2.10 6.80 (2) (3) 0 2.01 0.501 - 5.02 0 2.01 0.501 - 5.02 0 - 1.30 2.10 6.80 5 -4 0.5 9 (3)+(2)*1.30/2.01 0 2.01 0.501 - 5.02 0 0 1.78 3.55 回代 x3 = 1.99 , x2 = - 2.00 , x1 = 0.001,列主元高斯消

9、去法的計(jì)算步驟（計(jì)算機(jī)實(shí)現(xiàn)） 1 . 消元過程 對(duì) k = 1，2， ，n-1 作下列運(yùn)算: (1) 按列選主元 確定 r , 使?jié)M足 若ark = 0 , 說明系數(shù)矩陣奇異，則停止計(jì)算(結(jié)束) ; (2) 行交換 若 rk , 則交換第 k 行和第 r 行 ; (3) 消元計(jì)算 對(duì) i = k+1 , k+2 , , n , j= k+1 , k+2 , , n+1 計(jì)算 2 . 回代過程 若ann = 0 , 則系數(shù)矩陣為奇異，停止計(jì)算(結(jié)束) ; 否則計(jì) 算 ( k= n , n-1, , 1),二、全主元高斯消去法 全主元消去法與列主元消去法的不同之處，是在第k次消元時(shí)，從系數(shù)矩陣的右

10、下角(n-k+1)階子矩陣： 中，選取絕對(duì)值最大的元素作為主元素，如果它位于第r行第s列，則通過交換k,r兩行及交換k,s兩列，使主元素位于 的位置，然后進(jìn)行消元計(jì)算。由于作列的交換改變了方程中未知量的次序，因此回代過程要按未知量調(diào)換后的編號(hào)順序求解。,全主元消去法解線性方程組舉例 例 0.01x1 + 2x2 - 0.5x3 = - 5 - x1 - 0.5x2 + 2x3 = 5 5x1 - 4x2 + 0.5x3 = 9 解 0.01 2 - 0.5 - 5 5 - 4 0.5 9 A,b = - 1 - 0.5 2 5 (1) (3) -1 - 0.5 2 5 5 - 4 0.5 9

11、0.01 2 - 0.5 5 (2)+(1)*1/5 5 - 4 0.5 9 5 0.5 - 4 9 (3)-(1)*1/500 0 -1.30 2.10 6.80 交換(2)、(3)列 0 2.10 -1.30 6.80 0 2.01 - 0.501 -5.02 0 - 0.501 2.01 -5.02 5 0.5 - 4 9 (3)+(2)*0.501/2.10 0 2.10 -1.30 6.8 即 0 0 1.70 -3.40 回代得：x2 = - 2.00 , x3 = 2.00 , x1 = 0.00,全主元高斯消去法的計(jì)算步驟(計(jì)算機(jī)實(shí)現(xiàn)) 1. 記錄未知量的初始順序( ti =

12、i , i = 1 , 2 , , n ) 2. 消元過程 對(duì)k = 1, 2 , , n-1 作下列運(yùn)算： （1）選主元 確定 r,s 使 若ars=0,說明系數(shù)矩陣奇異，結(jié)束。 （2）行交換和列交換 若rk , 則交換 r , k 兩行 ；若 sk , 則交換 s, k 兩列并交換 ts、tk 的值。 （3）消元計(jì)算 同列主元消去法。 3. 回代過程 若ann=0,則系數(shù)矩陣奇異,結(jié)束;否則 計(jì)算 4. 輸出x1 , x2 , , xn ( k = n , n-1, , 1),第三節(jié) 高斯-約當(dāng)消去法(無回代過程的主元素消去法),高斯約當(dāng)法的思想是將方程組化為對(duì)角形Dx=B的形式，其中矩陣

13、D為對(duì)角形矩陣，即 其特點(diǎn)是每次消元時(shí)利用主元將其所在列的冗余元素全部消為0，即在第k次消元時(shí)，不僅把k列中(k,k)位置以下的元素消為0，而且同時(shí)把(k,k)位置上的元素也化為0，消去的行是從第1行到第n行，但主行不進(jìn)行消去，這樣經(jīng)過n次消元后系數(shù)矩陣就成為對(duì)角陣，不需回代就可直接求出方程組的解。,列主元高斯-約當(dāng)消去法求解線性方程組舉例 例 求解方程組Ax=b,其中 解：增廣矩陣為 1 2 3 1 3 4 6 3 A,b = 2 4 5 4 (1) (3) 2 4 5 4 3 4 6 3 1 2 3 1 1 4/3 2 1 (2)-(1)*2 1 4/3 2 1 1 4/3 2 1 (1)

14、*1/3 2 4 5 4 (3)-(2) 0 4/3 1 2 ( 2)*3/4 0 1 3/4 3/2 1 2 3 1 0 2/3 1 0 0 2/3 1 0 (1)-(2)*4/3 1 0 1 -1 1 0 1 -1 (1)-(3) 1 0 0 1 (3)-(2)*2/3 0 1 3/4 3/2 (3)*2 0 1 3/4 3/2 (2)-(3)*3/4 0 1 0 3 0 0 1/2 -1 0 0 1 -2 0 0 1 -2 于是求得方程Ax=b的解為： x1 = 1 , x2 = 3 , x3 = -2,列主元高斯-約當(dāng)消去法求解m個(gè)線性方程組的計(jì)算步驟 (計(jì)算機(jī)實(shí)現(xiàn)),列主元高斯-約當(dāng)

15、消去法通常用來求解逆矩陣或同時(shí)求解系 數(shù)矩陣相同的多個(gè)方程組，下面是列主元高斯-約當(dāng)消去法求解 m個(gè)線性方程組的計(jì)算步驟： 1 . 消元過程 對(duì) k = 1，2， ，n 作下列計(jì)算 (1) 按列選主元以及行交換（同列主元高斯消去法）。 (2) 消元計(jì)算 ) akj= akj/akk j = k , k+1, , n , n+1 , ,n+m ) aij= aij aikakj i = 1, 2, , n (ik) j= k+1 , k+2 , , n+m 2 . 輸出矩陣的n+s列,就是第s個(gè)方程的解(s=1，2， , m)。,第四節(jié) 直接三角分解法(矩陣三角分解法),三角分解法的思想是將系數(shù)

16、矩陣分解為兩個(gè)三角形矩陣之積，即A=LU。其中: L為一個(gè)下三角矩陣,U為一個(gè)上三角矩陣。然后將解方程組Ax=b的過程化為解Ly=b和Ux=y兩個(gè)方程組的過程。,直接三角分解法求解線性方程組Ax=b的出發(fā)點(diǎn),若|A| 0， A = LU 1 U11 U12 U13 U1n L = L21 1 U = U22 U23 U2n Ln1 Ln2 Ln3 Lnn-1 1 Unn 即 1 U11 U12 U13 U1n L21 1 U22 U23 U2n Ln1 Ln2 Ln3 Lnn-1 1 Unn a11 a12 a1n = a21 a22 a2n an1 an2 ann,直接三角分解法求解線性方程

17、組Ax=b的具體過程 1. 三角分解 對(duì) k = 1, 2, , n 計(jì)算U和L的元素 2. 求y值 令 Ux = y , Ly = b y1 = b1,( i = 2, 3, , n ),求x值 根據(jù) Ux = y xn = yn/unn (i=n-1,n-2,1),直接三角分解法求解線性方程組的例子 例: 求 的解 解: 1 2 -1 1 2 -1 1 -1 5 1 -3 6 4 1 2 4 7/3 8 1 0 0 1 2 -1 即 L = 1 1 0 U = 0 -3 6 4 7/3 1 , 0 0 -8 1 0 0 y1 3 3 由 1 1 0 y2 = 0 得 y = -3 4 7/

18、3 1 y3 2 -3 1 2 -1 x1 3 -1/8 再由 0 -3 6 x2 = -3 得 x = 7/4 0 0 8 x3 -3 3/8,直接三角分解法求解線性方程組的計(jì)算機(jī)實(shí)現(xiàn),按直接三角分解法求解線性 方程組Ax=b的具體過程實(shí)現(xiàn)。,第五節(jié) 線性方程組的迭代解法,線性方程組迭代解法的基本思想是構(gòu)造適當(dāng)?shù)木仃囆蛄谢蛳蛄啃蛄?，使其逐步逼近所求問題的精確解，故又稱矩陣迭代法。 適用情況：未知數(shù)n較多(即方程組較大）、系數(shù)矩陣稀疏。,一、簡單迭代法,設(shè)方程組Ax=b的系數(shù)矩陣非奇異，把它化為等價(jià)的方程組 x=Bx+g 其中： b11 b12 b1n g1 x1 B = b21 b22 b2

19、n g = g2 x = x2 bn1 bn2 bnn , gn , xn 按 x=Bx+g 構(gòu)造迭代公式 x(k+1)=Bx(k)+g , k=0, 1, 2, 其中： ( k = 0, 1, 2, ) 任取初始向量x(0),用 x(k+1)=Bx(k)+g 逐次計(jì)算近似解向量 x(1), x(2), , x(k), 這種求解方法稱為簡單迭代法。,簡單迭代法的一些概念,x(k+1)=Bx(k)+g 稱為簡單迭代公式(或迭代格式); 其 中的B稱為迭代矩陣。 如果x(k)的各分量存在極限 , i = 1, 2, , n 則記為： 這時(shí)，稱簡單迭代法 x(k+1)=Bx(k)+g 是收斂的，否則

20、就 是發(fā)散的。 實(shí)際計(jì)算中，一般用 來控制迭代結(jié)束。,二、雅可比迭代法(一種簡單迭代法） 線性方程組的一般形式為 設(shè)從上式中分離出變量xi，將它改寫為 由此可以建立迭代公式 該公式即為雅可比迭代法。,用雅可比迭代法求解線性方程組的例子 例1 求 10 x1 - x3 = 9 -2x1 + 10 x2 - x3 = 7 -x2 +5x3 = 4 精度要求為 =0.005，用5位有效數(shù)字計(jì)算。 解 將方程組寫成等價(jià)的方程組 x1 = 0.1x3 + 0.9 x2 = 0.2x1 + 0.1x3 + 0.7 x3 = 0.2x2 + 0.8 構(gòu)造雅可比迭代公式 k=0,1, 取初始向量x(0)=0=

21、0,0,0T進(jìn)行迭代，計(jì)算結(jié)果如下表：,用雅可比迭代法求解線性方程組的例子(續(xù)） 由于 所以x(5)滿足精度要求，即得： x1 = 0.99980 , x2 = 0.99964 , x3 = 0.99960,用雅可比迭代法求解線性方程組的例子(續(xù)),例2 求 -2x1 + 10 x2 - x3 = 15 （1） -x1 - 2x2 + 5x3 = 10 （2） 10 x1 - 2x2 - x3 = 3 （3） 精度要求為 =0.005。 解 將方程組寫成等價(jià)的方程組 x1 = 5x2 - 0.5x3 - 7.5 x2 = -0.5x1 + 2.5x3 - 5 x3 = 10 x1 - 2x2

22、- 3 其雅可比迭代公式為 x1(k+1) = 5x2(k) - 0.5x3(k) - 7.5 x2(k+1) = -0.5x1(k) + 2.5x3(k) - 5 x3(k+1) = 10 x1(k) - 2x2(k) - 3 ( k = 0, 1, ）,用雅可比迭代法求解線性方程組的例子(續(xù)),取初始向量 x(0)=0=0,0,0T ，按 x1(k+1) = 5x2(k) - 0.5x3(k) - 7.5 x2(k+1) = -0.5x1(k) + 2.5x3(k) - 5 x3(k+1) = 10 x1(k) - 2x2(k) - 3 ( k = 0, 1, ） 計(jì)算，其結(jié)果如下表:,x

23、1(k),x2(k),其結(jié)果的絕對(duì)值越來越大，不可能逼近于任何常數(shù)，這個(gè)迭代格式是發(fā)散得的。該方程組的精確解為1，2，3。,雅可比迭代格式收斂性的判別方法,可以證明，只要滿足下面三個(gè)條件的一個(gè)便可保 證雅可比迭代格式收斂。 (1) (2) (3) 當(dāng)寫出的迭代格式不收斂時(shí)，可適當(dāng)調(diào)整方程組 中各方程的次序或根據(jù)線性代數(shù)知識(shí)將原方程組中的 方程加以重新組合(如將一個(gè)方程的若干倍加到另一個(gè) 方程上進(jìn)行變換等)，再寫出相應(yīng)的迭代格式。如例2， 可將方程組中的方程(3)調(diào)整為(1)、方程(1)調(diào)整為(2)、 方程(2)調(diào)整為(3),便可寫出收斂的迭代格式, 直到滿足 收斂條件。,三、高斯-賽德爾迭代法

24、 雅可比迭代的思想是用前次迭代計(jì)算所得的近似解來計(jì)算下一個(gè)近似解。它沒有充分利用已有的結(jié)果( 雅可比迭代法在求x2(k+1)時(shí)x1(k+1) 已經(jīng)求了出來, 而它仍然用x1(k)來求x2(k+1) ; 在求x3(k+1)時(shí)x1(k+1) 、 x2(k+1)已經(jīng)求了出來，而它仍然用x1(k) 、 x2(k)來求x3(k+1) ) 。 高斯-賽德爾迭代法是對(duì)雅可比迭代法的改進(jìn)，它充分利用了已有的結(jié)果。其迭代公式為： 高斯-塞德爾迭代法由于每算出一個(gè)新近似值 , 立即用它代替 去進(jìn)行下一個(gè)未知量 xi+1(k+1) 的計(jì)算。這樣, 不僅提高了收斂速度（因新值xi(k+1) 比舊值 xi(k) 更準(zhǔn)確 , 達(dá)到某一精度要求所需的計(jì)算量就會(huì)減少，這樣計(jì)算速度就加快了 ）, 而且也節(jié)省了存儲(chǔ)空間