解線性方程組的直接法教學設計教案

1、解線性方程組的直接法許多科學技術問題要歸結為解含有多個未知量x1, x2, , xn的線性方程組（3.1）這里aij (i, j = 1, 2, , n)為方程組的系數(shù)，bi（i = 1, 2, , n）為方程組自由項。方程組（3.1）的矩陣形式為：AX = b其中線性方程組的數(shù)值解法可以分為直接法和迭代法兩類。所謂直接法，就是不考慮舍入誤差，通過有限步驟四則運算即能求得線性方程組（3.1）準確解的方法。如克萊姆法則，但通過第一章的分析，我們知道用克萊姆法則來求解線性代數(shù)方程組并不實用，因而尋求線性方程組的快速而有效的解法是十分重要的。本章討論計算機上常用而有效的直接解法高斯消去法和矩陣的三角

2、分解等問題。為方便計，設所討論的線性方程組的系數(shù)行列式不等于零。1 高斯消去法高斯（Gauss）消去法是解線性方程組最常用的方法之一，它的基本思想是通過逐步消元，把方程組化為系數(shù)矩陣為三角形矩陣的同解方程組，然后用回代法解此三角形方程組得原方程組的解。下面先討論三角形方程組的解法。1三角形方程組的解法三角形方程組是指下面兩種形式的方程組（3.2）和（3.3）方程組（3.2）叫做下三角形方程組，方程組（3.3）叫做上三角形方程組，三角形方程組的求解是很簡單的。如果aii 0，i = 1, 2, n，則（3.2）的解為k = 2, 3, n（3.4）此過程稱為前推過程。同樣地，若aii 0, i

3、= 1, 2, n，則（3.3）的解為（3.5）此過程稱為回代過程。從上面的公式來看，求出xk，需要作k 1次乘法和加減法及一次除法，總共完成次乘法、加法及n次除法。從（3.4）、（3.5）可以看出，求解三角形方程組是很簡單的，只要把方程組化成了等價的三角形方程組，求解過程就很容易完成。2高斯消去法為便于敘述，先以一個三階線性方程組為例來說明高斯消去法的基本思想。把方程（I）乘（）后加到方程（II）上去，把方程（I）乘（）后加到方程（III）上去，即可消去方程（II）、（III）中的x1，得同解方程組將方程（II）乘（）后加于方程（III），得同解方程組：由回代公式（3.5）得 x3 = 2

4、x2 = 8 x1 = -13下面考察一般形式的線性方程組的解法，為敘述問題方便，將bi寫成ai, n+1，i = 1, 2,n。（3.6）如果a11 0，將第一個方程中x1的系數(shù)化為1，得 其中 j = 1, , n + 1（記 i = 1, 2, , n; j = 1, 2, , n + 1）從其它n 1個方程中消x1，使它變成如下形式（3.7）其中 由方程（3.6）到（3.7）的過程中，元素起著重要的作用，特別地，把稱為主元素。如果（3.7）中，則以為主元素，又可以把方程組（3.7）化為： （3.8）針對（3.8） 繼續(xù)消元，重復同樣的手段，第k步所要加工的方程組是：設，第k步先使上述方

5、程組中第k個方程中xk的系數(shù)化為1：然后再從其它（n - k）個方程中消xk，消元公式為： (3.9)按照上述步驟進行n次后，將原方程組加工成下列形式：回代公式為：（3.10）綜上所述，高斯消去法分為消元過程與回代過程，消元過程將所給方程組加工成上三角形方程組，再經回代過程求解。由于計算時不涉及xi, i = 1, 2, , n，所以在存貯時可將方程組AX = b，寫成增廣矩陣（A, b）存貯。下面，我們統(tǒng)計一下高斯消去法的工作量；在（3.9）第一個式子中，每執(zhí)行一次需要次除法，在（3.9）第二個式子中，每執(zhí)行一次需要次除法。因此在消元過程中，共需要次乘作法。此外，回代過程共有次乘法。匯總在一

6、起，高斯消去法的計算量為：次乘除法。3主元素消去法前述的消去過程中，未知量是按其出現(xiàn)于方程組中的自然順序消去的，所以又叫順序消去法。實際上已經發(fā)現(xiàn)順序消去法有很大的缺點。設用作除數(shù)的為主元素，首先，消元過程中可能出現(xiàn)為零的情況，此時消元過程亦無法進行下去；其次如果主元素很小，由于舍入誤差和有效位數(shù)消失等因素，其本身常常有較大的相對誤差，用其作除數(shù)，會導致其它元素數(shù)量級的嚴重增長和舍入誤差的擴散，使得所求的解誤差過大，以致失真。我們來看一個例子：例它的精確解為：用順序消去法，第一步以0.0001為主元，從第二個方程中消x1后可得：回代可得 x1 = 0.00顯然，這不是解。造成這個現(xiàn)象的原因是：

7、第一步主元素太小，使得消元后所得的三角形方程組很不準確所致。如果我們選第二個方程中x1的系數(shù)1.00為主元素來消去第一個方程中的x1，則得出如下方程式：1.00 x1 = 1.00 x1 = 1.00這是真解的三位正確舍入值。從上述例子中可以看出，在消元過程中適當選取主元素是十分必要的。誤差分析的理論和計算實踐均表明：順序消元法在系數(shù)矩陣A為對稱正定時，可以保證此過程對舍入誤差的數(shù)值穩(wěn)定性，對一般的矩陣則必須引入選取主元素的技巧，方能得到滿意的結果。列主元消去法在列主元消去法中，未知數(shù)仍然是順序地消去的，但是把各方程中要消去的那個未知數(shù)的系數(shù)按絕對值最大值作為主元素，然后用順序消去法的公式求解

8、。例：用列主元高斯消去法求解方程由于解方程組取決于它的系數(shù)，因此可用這些系數(shù)（包括右端項）所構成的“增廣矩陣”作為方程組的一種簡化形式。對這種增廣矩陣施行消元手續(xù)：第一步將4選為主元素，并把主元素所在的行定為主元行，然后將主元行換到第一行得到消元過程的結果歸結到下列三角形方程組：回代，得列主元消去法計算步驟：輸入矩陣階數(shù) ，增廣矩陣 對 按列選主元：選取 使 如果 ，交換 的 第k行與底l 行元素消元計算 ：回代計算： 4、輸出解向量 。4無回代過程的主元消去法設有線性代數(shù)方程組AX = b其中A為n n階非奇異矩陣，b為n 1階矩陣（列向量），由A-1AX = A-1b得X = A-1b。因

9、此，只要求出A-1就可以得到解X。另外，有許多問題需要求矩陣的逆，例如常用的回歸分析方法中，要求出相關矩陣的逆，因此，有必要討論在計算機上常用的求逆方法。步驟：第一步選主元，在第一列中選絕對值最大的元素，設第k行為主元行，將主元行換至第一行，將第一個方程中x1的系數(shù)變?yōu)?，并從其余n 1個方程中消去x1。第二步：在第二列后n 1個元素中選主元，將第二個方程中x2的系數(shù)變?yōu)?，并從其它n 1個方程中消去x2。依此類推，直到每個方程中僅有一個變量為止。此過程進行到第k 1步后，方程組將變成如下形式：第k步：在第k列后n k個元素中選主元，換行，將第k個方程xk的系數(shù)變?yōu)?，從其它方程中消去變量xk

10、，消元公式為：（3.11）對k = 1, 2, , 按上述步驟進行到第n步后，方程組變?yōu)椋杭礊樗蟮慕?無回代消去法的應用（1）解線性方程組系設要解的線性方程組系為：AX = b1, AX = b2, AX = bm其中上述方程組系可以寫為AX = B = (b1, , bm)因此X = A-1B即為線性方程組系的解。在計算機上只需要增加幾組右端常數(shù)項的存貯單元，其結構解一個方程組時一樣。行 系數(shù) （2）求逆矩陣設A = (aij)nn是非奇矩陣，|A| 0，且令由于 AA-1 = AX = I因此，求A-1的問題相當于解下列線性方程組也就是相當于（I）中m = n, B = I的情形。（3）

11、求行列式的值由于行列式任意一行(列)的元素乘以同一個數(shù)后，加到另一行（列）的對應元素上，其行列式的值不變；任意對換兩行（列）的位置其值反號；三角矩陣的行列式之值等于其主對角元素的乘積。因此，可用高斯消去法將 |A|化成2 解三對角方程組的追趕法在實際問題中，經常遇到以下形式的方程組（3.12）這種方程組的系數(shù)矩陣稱為三對角矩陣以下針對這種方程組的特點提供一種簡便有效的算法追趕法。追趕法實際上是高斯消去法的一種簡化形式，它同樣分消元與回代兩個過程。先將（3.12）第一個方程中x1的系數(shù)化為1記 （3.13）有 注意到剩下的方程中，實際上只有第二個方程中含有變量x1，因此消元手續(xù)可以簡化。利用（3

12、.13）可將第二個方程化為這樣一步一步地順序加工（3.12）的每個方程，設第k 1個方程已經變成（3.14）再利用（3.14）從第k個方程中消去xk-1，得：同除，得記則有 這樣做n 1步以后，便得到：將上式與（3.12）中第11個方程聯(lián)立，即可解出xn = yn這里于是，通過消元過程，所給方程組（3.12）可歸結為以下更為簡單的形式：（3.15）這種方程組稱作二對角型方程組，其系數(shù)矩陣中的非零元素集中分步在主對角線和一條次主對角線上對加工得到的方程組（3.15）自下而上逐步回代，即可依次求出xn，xn-1，x1，計算公式為：（3.16）上述算法就是追趕法，它的消元過程與回代過程分別稱作“追”

13、過程與“趕”過程。綜合追與趕的過程，得如下計算公式：（3.17）（3.18）3 矩陣的三角分解及其在解方程組中的應用下面我們進一步用矩陣理論來分析高斯消去法，從而建立矩陣的三角分解定理，而這個定理在解方程組的直接解法中起著重要作用，我們將利用它來推導某些具有特殊的系數(shù)矩陣方程組的數(shù)值解法?？紤]線性方程組AX = b ARnn 設解此方程組用高期消去法能夠完成（不進行變換兩行的初等變換），由于對A施行初等變換相當于用初等矩陣左乘A，于是，高斯消去法的求解過程用矩陣理論來敘述如下：記：其中 記 于是如此繼續(xù)下去，到n 1步時有：也就是說記則有 A = LU其中L為單位下三角矩陣，U為上三角矩陣?？?/p>

14、結上述討論得到重要性定理定理1：（矩陣的三角分解）設A為n n實矩陣，如果解AX = b用高斯消去法能夠完成（限制不進行行的交換，即），則矩陣A可分解為單位下三角矩陣L與上三角知陣U的乘積。A = LU且這種分解是唯一的。證明：由上述的討論，存在性已得證，現(xiàn)在證唯一性。設 A = L1 U1 = LU其中L1，L1為單位下三角陣，U1，U為上三角陣，設存在，于是有上式右端為上三角矩陣，左邊為單位下三角陣，故應為單位矩陣。即 L1 = L U1 = U 證完那么矩陣A在什么條件下才能保證約化主元素 （k = 1, 2, , n）？為此給出以下定理2：約化主元素（i = 1, 2, , k）充要條

15、件是矩陣A的順序主子式由上述討論知，解 AX = b的高斯消去法相當于實現(xiàn)了A的三角分解，如果我們能直接從矩陣A的元素得到計算L，U的元素的公式，實現(xiàn)A的三角分解，而不需要任何中間步驟，那么求解AX = b的問題就等價于求解兩個三角形矩陣方程組（1）Ly = b 求y（2）UX = y 求x下面來說明L、U的元素可以由A的元素直接計算確定。顯然，由矩陣乘法。得到U的第一行元素；由得即L的第一列元素。設已經求出U的第1行第r 1行元素，L的第1列第r 1列元素，由矩陣乘法可得：即可計算出U的第r行元素，L的第r列元素。綜上所述，可得到用直接三角分解法解AX = b的計算公式。（1） （3.19）

16、（3.20）對于r = 2, 3, , n計算（2）計算U的第r行元素（3.21）（3）計算L的第r列元素 (r n) （3.22）（4） （3.23）（5）（3.24）（1）、（2）、（3）是矩陣A的LU分解公式,稱為杜利特爾（Doolitte）分解。同理，可推出矩陣A = LU分解的另一種計算公式，其中L為下三角，U為單位上三角，這種矩陣的分解公式稱為矩陣的克勞特（Crout）分解。例：用直接三角分解法解解：（1）對于r = 1，利用公式（3.19）、（3.20）計算 l21 = 2 l 31 = 3（2）對于r = 2，利用（3.21）計算= 5 2 2 = 1= 2 2 3 = -4（

17、3）r = 3于是（4）求解：Ly = b 得到y(tǒng)1 = 14y2 = b2 l21y1 = 18 2 14 = -10y3 = b3 (l31y1 + l32y2) = 20 (3 14 + (-5)(-10) = - 72從而 y = (14, -10, -72)T由Ux= y 得到4 平方根法1矩陣的LDR分解以上介紹了矩陣的三角分解及唯一性定理，為使分解式規(guī)范化，我們給出矩陣LDR分解。定理3：如果n階方程A的所有順序主子式均不等于零，則矩陣A存在唯一的分解式A = LDR其中L和R分別是n階單位下三角陣和單位上三角陣，D是n階對角元素的不為零的對角陣，上述分解也稱為A的LDR分解。證

18、明：充分性：因為A的順序主子式均不為零，Gauss消去法得以完成，即實現(xiàn)了一個Doolittle分解A = LU（或Crout分解）U的對角元素 ，這時，令 則其中 存在性得證。唯一性：當A非奇時，L、D、R皆非奇，若還存在另一個LDR分解A = L1D1R1，這里L1, D1, R1也非奇，則有LDR = L1D1R1即 上式左端是單位下三角矩陣，右端是上三角矩陣，所以應該是單位矩陣，即 從而必有也即R1 = R D1 = D 唯一性得證。必要性：假定A有唯一的LDR分解，且L, D, R均非奇，從而LiDiRi均非奇i = 1, 2, n，而Ai = LiDiRi，所以Ai (i = 1,

19、 2, n)也非奇。 證完2平方根法在科學研究和工程技術的實際計算中遇到的線性代數(shù)方程組，其系數(shù)矩陣往往具有對稱正定性。對于系數(shù)矩陣具有這種特殊性質的方程組，上面介紹的直接三角分解還可以簡化。得到“平方根法”。這是計算機上常用的有效方法之一。下面討論對稱正定矩陣的三角分解。設A是n階實矩陣，由線性代數(shù)知識知A是對稱矩陣，即A = AT，A是正定矩陣，即對于任意n維非零列向量X 0，X R n，恒有XTAX 0，對稱正定矩陣有以下性質：若A為對稱正定矩陣，則A的各階順序主子式Dk 0 (k = 1, 2, n)。根據(jù)這條性質，我們就可以來討論對稱正定矩陣的三角分解，從而給出求解方程組的平方根法。

20、定理4：（對稱正定矩陣的三角分解）如果A為對稱正定矩陣，則存在一個實的非奇異下三角矩陣，使，且當限定的對角元素為正時，這種分解是唯一的。證明：由A的對稱正定性，則A的順序主子式Dk 0 (k = 1, 2, n)，于是由定理3可知，A總存在唯一的LDR分解。即A = LDR。其中L是單位下三角陣，D是非奇異的對角陣，R是單位上三角陣。又由A的對稱性，AT = A，則(LDR)T = RTDLT = LDR，由分解唯一性，于是有L = RT，從而得A = LDLT，這表明對稱正定矩陣A的LDR分解具有特殊形式。A = LDLT設 D = diag (d1, d2, dn), dj 0 (j =

21、1, 2, n)下面我們進一步證明D的對角元素均為正數(shù)，即dj 0。由于L是單位下三角陣，所以對于單位坐標向量ej = (0, 0, 1, 0, 0)T存在非零向量Xj，使LTXj = ej (j = 1, 2, n)。因此， 根據(jù)A是對稱正定陣的定義，有，從而dj 0 (j = 1, 2, n)這就證明了D的對角元皆為正數(shù)。現(xiàn)設 注意，在這里我們將的對角元素全取為正數(shù)，即則其中，顯然是對角元全為正的非奇異的下三角陣。由于分解式A = LDLT是唯一的，又限定的對角元為正數(shù)，從而分解D =、也是唯一的，所以說在限定L的對角線元素皆為正時，三角分解是唯一的。對稱正定矩陣A的三角分解稱為正定矩陣A

22、的喬列斯基（Cholesky）分解，又稱LLT分解。將記為A = LLT那么解線代數(shù)方程組AX = b 解 Ly = b, LTx = y下面給出用平方根法解線性代數(shù)方程組的公式（1）對矩陣A進行Cholesky分解，即A=LLT，由矩陣乘法：對于 i = 1, 2, n 計算 (3.25) (3.26) （2）求解下三角形方程組 (3.27)（3）求解LTX = y (3.28)由于此法要將矩陣A作LLT三角分解，且在分解過程中含有開方運算，故稱該稱為LLT分解法或平方根法。由于LT是L的轉置，所以計算量只是一般直接三角分解的一半多一點。另外，由于A的對稱性，計算過程只用到矩陣A的下三角部分

23、的元素，而且一旦求出lij后，aij就不需要了，所以L的元素可以存貯在A的下三角部分相應元素的位置，這樣存貯量就大大節(jié)省了，在計算機上進行計算時，只需用一維數(shù)組A n (n+1)/2對應存放A的對角線以下部分相應元素。且由可知 這表明L的元素的絕對值一般不會很大，所以計算是穩(wěn)定的，這是Cholesky分解的又一個優(yōu)點。其缺點是需要做一些開方運算。3改進平方根法由于用平方根法解對稱正定方程組時，計算L的對角元素時需要用到開方運算，為了避免開方運算，我們也可以直接采用對稱正定矩陣的A = LDLT分解式，即 其中由矩陣乘法和比較對應元素得dii, lij的計算應按上列順序進行由LDLT分解法先求得

24、單位下三解陣L和對角陣D，因為A = LDLT，所以對稱方程組AX = b成為LD (LTX) = b令LTX = y，先解下三角形方程組LDY = b得 (3.29)最后解上三角形方程組LTX = Y得 (3.30)LDLT分解法解對稱方程組所含的乘除法運算約為n3/4次，LLT分解法解對稱正定方程組約需乘除法n3/6次。LDLT法雖然增加了計算量，但避免了開方運算且擴大了使用范圍，優(yōu)點是明顯的。例：用改進平方根法解解：i = 1 = 1i = 2 S21 = a21 = 2l21 = S21/d11 = 2/1 = 2= a22 S21/ l21 = 5 - 2 2 = 1i = 3l32

25、 = -2i = 2= 1求解 由公式得y1 = b1 = 1, y2 = b1 l12y1 = 0 y3 = 15 y4 = 1再由公式得：x4 = 1 x3 = 1 x2 = 1 x1 = 15 向量和矩陣的范數(shù)在線性代數(shù)方程組的數(shù)值解法中，經常需要分析解向量的誤差，需要比較誤差向量的“大小”或“長度”。那么怎樣定義向量的長度呢？我們在初等教學里知道，定義向量的長度，實際上就是對每一個向量按一定的法則規(guī)定一個非負實數(shù)與之對應，這一思想推廣到維線性空間里，就是向量的范數(shù)或模。1向量的范數(shù)范數(shù)的最簡單的例子，是絕對值函數(shù)。并且有三個熟知的性質：（1）x 0 | x | 0 | x | = 0當

26、且僅當x = 0（2）|ax| = | a | | x | a為常數(shù)（3）| x+ y | | x | + | y | 范數(shù)的另一個簡單例子是二維歐氏空間的長度 （勾股定理）歐氏范數(shù)也滿足三個條件：設x = (x1, x2)（1）x 0 | x | 0（2）| ax | = | a | | x |2 a為常數(shù)（3）| x+ y |2 | x |2 + | y |2前兩個條件顯然，第三個條件在幾何上解釋為三角形一邊的長度不大于其它兩邊長度之和。因此，稱之三角不等式。下面我們給出維空間中向量范數(shù)的概念：設X = (x1, x2, , xn)T，記為X R n定義1：設X R n，| 表示定義在Rn

27、上的一個實值函數(shù)，稱之為X的范數(shù)，它具有下列性質：1）非負性：即對一切X R n，X 0, | 02）齊次性：即為任何實數(shù)a R，X R n，3）三角不等式：即對任意兩個向量X、Y R n，恒有從以上規(guī)定范數(shù)的三種基本性質、立即可以推出Rn中向量的范數(shù)必具有下列性質：4）| 0 | = 05）6）對任意的X、Y R n，恒有：證明：根據(jù)范數(shù)的三角不等式所以 同理可證 因此必有： 證完三個常用的范數(shù)：設X = (x1, x2, xn)T，則有（）；（）（）不難驗證，上述三種范數(shù)都滿足定義的條件。定理5：定義在Rn上的向量范數(shù)是變量X分量的一致連續(xù)函數(shù)。（）證明：設HRn為任意向量，e1, e2,

28、 en為Rn中的一個基底，且再假設顯然N為定常數(shù)，則當 時，由三角不等式得任給正數(shù)e 0，取，則有：證畢定理6：在Rn上定義的任一向量范數(shù)都與范數(shù)等價，即存在正數(shù)M與m(Mm)對一切XRn，不等式成立。證明：設xRn，則的連續(xù)函數(shù)在有界閉區(qū)域 （單位球面）上有界，且一定能達到最大值及最小值。設其最大值為M，最小值為m，則有（3.31）考慮到在G上大于零，故m 0設XRn為任意非零向量，則代入（3.31）得所以 證完由此定理可得推論：Rn上定義的任何兩個范數(shù)都是等價的。對常用范數(shù)，容易驗證下列不等式：有了范數(shù)的概念，我們就可以討論向量序列的收斂性問題。定義2：設給定Rn中的向量序列，即,其中若對

29、任何i (i = 1, 2, n)都有則向量稱為向量序列的極限，或者說向量序列依坐標收斂于向量X*，記為定理7：向量序列Xk依坐標收斂于 的充分條件是如果一個向量序列與向量，滿足上式，就說向量序列依范數(shù)收斂于，于是便得：向量序列依范數(shù)收斂與依坐標收斂是等價的。2矩陣的范數(shù)定義3：設A為n階方陣，Rn中已定義了向量范數(shù)，則稱為矩陣A的范數(shù)或模，記為。矩陣范數(shù)有下列基本性質：（1）當A = 0時，0，當A 0時， 0（2）對任意實數(shù)和任意A，有（3）對任意兩個n階矩陣A、B有（4）對任意向量XRn，和任意矩陣A，有（5）對任意兩個n階矩陣A、B，有前三個性質可對照向量范數(shù)，下面來證明（4）：設，當XRn時，根據(jù)定義3，（4）顯然成立，當R