1、第3章 線性方程組的解法,3.1 問題綜述,在自然科學與社會科學的研究中，常常需要求解線性代數(shù)方程組，這些方程組的系數(shù)矩陣大致分為兩種：一種是低階稠密矩陣（例如：階數(shù)大約為小于等于150），另一種是大型稀疏矩陣（即矩陣階數(shù)高且零元素較多）。,在計算機上求解線性代數(shù)方程組 ax=b 的常用的數(shù)值解法： 1、直接法：就是經過有限次算術運算，可求得方程組精確解的方法（若計算過程中沒有舍入誤差）。但實際計算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。 這類方法是解低階稠密矩陣及大型帶狀方程組的有效方法。,2、迭代法：就是用某種極限過程去逐步逼近線性方程組精確解的方法，迭代法具有需

2、要計算機的存貯單元較少，程序設計簡單，原始系數(shù)矩陣在計算機中始終不變等優(yōu)點，但存在收斂性和收斂速度等問題。 迭代法是解大型稀疏矩陣方程組的重要方法。,注:直接法求解n元線性代數(shù)方程組所需乘法次數(shù) 1、cramer（克萊姆）法則：(n+1)！，當n=10時，(n+1)!=39916800次 2、gauss消去法： 當n=10時，約為430次,3.2 線性方程組的直接解法,n元線性方程組,簡記為,設a非奇異，則方程組有唯一解。,方程組的矩陣形式,gauss消去法,高斯消去法步驟： (1) 首先將增廣陣 a, b 化為上三角陣； (2) 用三角方程組，回代求解 。,gauss消去法是一個古老的求解線

3、性代數(shù)方程組的方法（早在公元前250年我國就掌握了解三元一次聯(lián)立方程組的方法）。但由于它改進、變形得到的主元素消去法、三角分解法仍然是目前計算機上常用的有效方法。,用一個簡單的例子說明消去法的基本思想。,解 (1) 化上三角方程組, , , , ,(2)回代過程. 得到下同解方程組后,如下處理,從下向上逐步求解,把x3的值代入求x2,用x3, x2的值求x1,對應的增廣矩陣的變化,(-2)r1 + r3r3,r2 + r3 r3,1.基本思想,將原方程組逐次消去未知元， 變?yōu)榕c之同解的上三角方程組， 再回代求解 。,用矩陣語言敘述，上述過程是使用初等行變換把增廣陣約化為上三角陣，使用上三角方程

4、組，回代求解 。,2.算法構造,根據(jù)下面的上三角方程組,逐次回代求解 xk,22,n-1,n-1,定義：在使用高斯消去法的過程中，僅對方程組做倍加變換，就形成了順序高斯消去法。,順序高斯消去法求解n 元線性方程組的乘除運算總次數(shù)為：,順序高斯消去法計算過程中出現(xiàn)的 稱為主元素. 出現(xiàn) ，消元過程就進行不下去了。,定理: 順序高斯消去法的前 n -1 個主元素 均不為零的充要條件是方程組的系數(shù)矩陣a的前n -1個順序主子式,順序gauss消去法計算過程中的 akk(k) 稱為主元素，在第k步消元時要用它作除數(shù),則可能會出現(xiàn)以下幾種情況,1、若出現(xiàn) akk(k) 0，消元過程就不能進行下去。,2、

5、akk(k) 0 ，消去過程能夠進行，但若|akk(k)| 過小，也會造成舍入誤差積累很大導致計算解的精度下降。,順序高斯消去法的數(shù)值穩(wěn)定性是沒有保證的!,順序主元素消去法可能計算失敗之例,例：單精度解方程組,用順序主元素消去法計算：,8個,小主元 /* small pivot element */可能導致計算失敗。,例： 在四位十進制的限制下，試用順序gauss消去法求解如下方程組,此方程組具有四位有效數(shù)字的精確解為,x117.46，x245.76，x35.546,解 用順序gauss消去法求解，消元過程如下,經回代求解得 x35.546，x2100.0，x1104.0,和此方程組的精確解相

6、比,x35.546 ，x245.76， x117.46,有較大的誤差。,對于此例，由于順序gauss消去法中的主元素絕對值非常小，使消元乘數(shù)絕對值非常大，計算過程中出現(xiàn)大數(shù)吃掉小數(shù)現(xiàn)象，產生較大的舍入誤差，最終導致計算解 x1104.0 和 x2100.0 已完全失真。,為避免這種現(xiàn)象發(fā)生，可以對原方程組作等價變換，再利用順序gauss消去法求解。,寫出原方程組的增廣矩陣：,針對第一列找出絕對值最大的元素，進行等價變換：,求得方程的解為：x35.546，x245.76，x117.46,精確解為： x35.546 ，x245.76， x117.46,由此可見，第二種gauss消去法的精度明顯高于

7、順序gauss消去法，我們稱它為列主元gauss消去法。,列主元gauss消去法與順序gauss消去法的不同之處在于：,后者是按自然順序取主元素進行消元,前者在每步消元之前先選取主元素然后再進行消元,3.列主元高斯消去法,定義 使用高斯消去法的過程中，在第 k 次消元前，先對第 k 個增廣陣 a(k), b(k) 做交換二行的變換，把 中絕對值最大的元素換到 (k, k) 位置，再消元。此方法叫列主元素高斯消去法。,1.消元過程 對于k =1,2,n -1執(zhí)行 (1)選行號ik，使 (2)交換第 k 行與第 ik 行。,(3)對于 i = k +1,k +2,n 計算,2.回代過程,評論：列主

8、元素消去法，所需條件較少，僅僅要求方程組的系數(shù)矩陣 a 非奇異。 而且，對一般的方程組，它還具有良好的數(shù)值穩(wěn)定性，其計算量與順序消去法的計算量相當。,3.3 矩陣的直接分解法,從3.2中討論可知，順序gauss消去法的消元過程是將增廣矩陣a，ba（1），b（1）逐步化為矩陣a（n），b（n）。,可見，在順序gauss消去法的過程中，系數(shù)矩陣aa（1）經過一系列單位下三角矩陣的左乘運算化為上三角矩陣a（n），即,1.矩陣的三角分解法,這時,令,容易驗證,從順序gauss消去法的矩陣運算表示式可知，系數(shù)矩陣a可分解為一個單位下三角矩陣l和一個上三角矩陣u的乘積，即,其中,定義 a = lu 叫做

9、a 的三角分解。 l，u 是下、上三角陣. 若 l 是單位下三角矩陣， u 是上三角矩陣，則 a =lu 叫 a 的doolittle 分解； 若 l 是下三角矩陣，u 是單位上三角矩陣， a =lu 叫 a 的 crout 分解。,如果方程組 ax =b 的系數(shù)陣 a 能分解為 a =lu, 其中，l 是下三角矩陣，u 是上三角矩陣.,這時解方程組 ax=b， 可化為求解兩個三角方程組 ly =b, ux =y . 先由 ly =b 解出向量 y，再由 ux =y 解出向量 x， 則 x 是原方程組 ax=b 的解向量。,三角分解用處,對于,由,解得,ly =b,對于,由,求得,ux =y,

10、可以看出對于方程組：,只要對系數(shù)矩陣作了三角分解：,由這個簡單的計算過程可知，系數(shù)矩陣的三角分解很關鍵。,通過如下兩組公式很容易求解：,ax =b,a =lu,以doolittle（杜利特爾）分解為例,在順序gauss消去法的過程中，若每步消元的主元素 akk(k)0，則矩陣a 可分解。而 akk(k) 0 的充要條件是a 的各階順序主子式不為零。,單位下三角陣,上三角陣, 矩陣 arnn 的 doolittle 分解,例： 利用doolittle三角分解法分解矩陣,解：,1,2,3,4,1,1,1,2,6,12,3,7,6,24,6,24,矩陣的三角分解,如果我們要求解方程組,則由,得到,由

11、,解得,再由,求得方程組的解：,解：設,比較兩邊系數(shù)得:,例 用矩陣的杜利脫爾（doolittle）分解解方程組,練習1：利用doolittle三角分解方法解線性方程,解: 進行三角分解alu，對增廣矩陣a,b作三角分解:,1 2 3 -2,-3,2,2,-3,-1,3,3,17,得到,1 2 3 -2,-3,2,2,-3,-1,3,3,17,這時，相應的方程組為：,練習2：利用doolittle三角分解方法解線性方程組,解：對增廣矩陣進行三角分解,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,1 2 3 -4 -2,-3,2,4,2,-3,

12、1,3,3,3,2,2,-4,-1,17,-16,解得,等價方程組通過分解式容易寫出為：,練習： 用矩陣的杜利脫爾（doolittle）分解 a=lu 解方程組：,答案：,2.列主元三角分解法,與列主元高斯消去法相對應的是列主元三角分解法。,選主元 d-分解的實施方法 采取與列主元類似的方法，在 d -分解中也選主元素。設使用 d-分解公式 已進行了 k -1 步，第 k -1 次分解矩陣為,(1)進行第 k 步分解， 先尋找主元素，計算中間量,(2) 再按公式進行第 k 步的d-分解運算。,滿足 的 就是第 k 步的主元素，以 的值作為 。為此，交換矩陣 a(k-1) 的第 k 行與第 ik

13、 行。此時：,例：用選主元的杜利脫爾（doolittle）分解解方程組,解：對增廣矩陣進行變換，有,等價的三角方程組為：,回代求解，得,3.4 特殊線性方程組解法,1.追趕法,追趕法是專門用于求解三對角方程組的。這類方程組經常出現(xiàn)于用差分方法或有限元方法求解二階常微分方程邊值問題、熱傳導問題及三次樣條函數(shù)插值等問題，三對角方程組axb的系數(shù)矩陣具有如下形式：,并且滿足,條件(i)保證方程組不能降階，條件(ii)保證三角分解可做到底。,在此條件下，可對a進行三角分解，設,a=,根據(jù)矩陣乘法及矩陣相等的定義，有：,則根據(jù)該組公式可以對三對角矩陣進行三角分解，對于三對角方程組axb，設a的三角分解為

14、alu，則原方程組等價于,lyb，uxy,由lyb求y；再由uxy求x。,注 追趕法的存貯與計算量都很小，乘除運算總次數(shù)為 5n-4。,練習 試用“追趕法”求解線性代數(shù)方程組：,2.改進的平方根法,改進的平方根法一般用于求解對稱線性方程組。,因為a對稱，則有：,推導得到：,3.6 線性方程組的迭代解法,1.問題的提出,1直接方法的缺陷(以gauss消去法為代表)：,對于低中階數(shù)（n100）的線性方程組十分有效，但n很大時，特別是由某些微分方程數(shù)值解所提出來的線性方程組，由于舍入誤差的積累以及計算機的存貯困難，直接方法卻無能為力。,2解決方法：（利用迭代方法）,迭代方法：把線性方程組的數(shù)值求解問

15、題化為一個迭代序列來實現(xiàn)。,具體做法,(2) 取任意初始向量 x(0) 構成迭代序列:,由于迭代方法能避免系數(shù)矩陣中零元的存貯與計算，特別適用于解系數(shù)矩陣階數(shù)很高而非零元極少（即大型稀疏）的線性方程組。,迭代格式：,定義：,迭代矩陣：,迭代過程收斂：,若序列x(k)極限存在，稱此迭代過程收斂，否則稱為發(fā)散。,3. 需要討論的問題：,怎樣建立迭代格式；迭代過程是否收斂，誤差分析；如何加快收斂速度等等。,迭代法計算精度可控，特別適用于求解系數(shù)為大型的方程組。,2.雅可比迭代法,迭代格式：,縮寫為：,按此格式迭代求解的方法稱為雅可比迭代法,簡稱j法。,寫成矩陣形式：,l,u,d,分裂 a = d+

16、l+u,拆分a為三個部分。,jacobi 迭代矩陣,那么，原方程組與下面的迭代方程組同解：,d,l,u 的具體形式,j,j,例： 用雅可比迭代法解線性方程組,解 生成雅可比迭代格式：,從此表可以看出，迭代序列收斂于x*，若取x(12)作為近似解，則誤差不超過 10-5,3.高斯-賽德爾迭代法, ,矩陣形式：,gauss-seidel 迭代陣，簡記為g,g-s迭代,jacobi迭代、g-s迭代計算式：,解,原方程等價于,建立jacobi迭代格式如下,建立gauss-seidel迭代格式如下,4.逐次超松弛迭代法,sor是gs迭代法的一種加速方法，是解大型稀疏矩陣方程組的有效方法之一。它具有計算公式簡單、程序設計容易、占用計算機內存較少等優(yōu)點，但需要選擇好的加速因子（最佳松馳因子）。 首先用gs法定義輔助量：,加入松弛因子 ：,注：顯然，當 =1，sor方法即為gs迭代法。 sor方法每迭代一次主要運算量是計算一次矩陣與向量的乘法。 當 1時，稱為超松馳法； 當1時，稱為低松馳法。,sor迭代的矩陣形式：,fw,sor 迭代矩陣,5.迭代法的收斂性,2. gauss-seidel方法收斂的條件,（充分條件）若a 為嚴格對角占優(yōu)陣