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

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

3、三角陣； (2) 用三角方程組，回代求解 。,Gauss消去法是一個古老的求解線性代數(shù)方程組的方法（早在公元前250年我國就掌握了解三元一次聯(lián)立方程組的方法）。但由于它改進、變形得到的主元素消去法、三角分解法仍然是目前計算機上常用的有效方法。,5,PPT學習交流,用一個簡單的例子說明消去法的基本思想。,6,PPT學習交流,解 (1) 化上三角方程組, , , ,7,PPT學習交流, ,(2)回代過程. 得到下同解方程組后,如下處理,從下向上逐步求解,把x3的值代入求x2,用x3, x2的值求x1,8,PPT學習交流,對應的增廣矩陣的變化,(-2)r1 + r3r3,r2 + r3 r3,9,P

4、PT學習交流,1.基本思想,將原方程組逐次消去未知元， 變?yōu)榕c之同解的上三角方程組， 再回代求解 。,用矩陣語言敘述，上述過程是使用初等行變換把增廣陣約化為上三角陣，使用上三角方程組，回代求解 。,10,PPT學習交流,2.算法構造,根據(jù)下面的上三角方程組,逐次回代求解 xk,22,n-1,n-1,11,PPT學習交流,定義：在使用高斯消去法的過程中，僅對方程組做倍加變換，就形成了順序高斯消去法。,順序高斯消去法求解n 元線性方程組的乘除運算總次數(shù)為：,順序高斯消去法計算過程中出現(xiàn)的 稱為主元素. 出現(xiàn) ，消元過程就進行不下去了。,12,PPT學習交流,定理: 順序高斯消去法的前 n -1 個

5、主元素 均不為零的充要條件是方程組的系數(shù)矩陣A的前n -1個順序主子式,13,PPT學習交流,順序Gauss消去法計算過程中的 akk(k) 稱為主元素，在第k步消元時要用它作除數(shù),則可能會出現(xiàn)以下幾種情況,1、若出現(xiàn) akk(k) 0，消元過程就不能進行下去。,2、akk(k) 0 ，消去過程能夠進行，但若|akk(k)| 過小，也會造成舍入誤差積累很大導致計算解的精度下降。,順序高斯消去法的數(shù)值穩(wěn)定性是沒有保證的!,14,PPT學習交流,順序主元素消去法可能計算失敗之例,例：單精度解方程組,用順序主元素消去法計算：,8個,小主元 /* Small pivot element */可能導致計

6、算失敗。,15,PPT學習交流,例： 在四位十進制的限制下，試用順序Gauss消去法求解如下方程組,此方程組具有四位有效數(shù)字的精確解為,x117.46，x245.76，x35.546,16,PPT學習交流,解 用順序Gauss消去法求解，消元過程如下,17,PPT學習交流,經(jīng)回代求解得 x35.546，x2100.0，x1104.0,和此方程組的精確解相比,x35.546 ，x245.76， x117.46,有較大的誤差。,對于此例，由于順序Gauss消去法中的主元素絕對值非常小，使消元乘數(shù)絕對值非常大，計算過程中出現(xiàn)大數(shù)吃掉小數(shù)現(xiàn)象，產(chǎn)生較大的舍入誤差，最終導致計算解 x1104.0 和 x

7、2100.0 已完全失真。,為避免這種現(xiàn)象發(fā)生，可以對原方程組作等價變換，再利用順序Gauss消去法求解。,18,PPT學習交流,寫出原方程組的增廣矩陣：,針對第一列找出絕對值最大的元素，進行等價變換：,19,PPT學習交流,求得方程的解為：x35.546，x245.76，x117.46,精確解為： x35.546 ，x245.76， x117.46,由此可見，第二種Gauss消去法的精度明顯高于順序Gauss消去法，我們稱它為列主元Gauss消去法。,列主元Gauss消去法與順序Gauss消去法的不同之處在于：,后者是按自然順序取主元素進行消元,前者在每步消元之前先選取主元素然后再進行消元,

8、20,PPT學習交流,3.列主元高斯消去法,定義 使用高斯消去法的過程中，在第 k 次消元前，先對第 k 個增廣陣 A(k), b(k) 做交換二行的變換，把 中絕對值最大的元素換到 (k, k) 位置，再消元。此方法叫列主元素高斯消去法。,1.消元過程 對于k =1,2,n -1執(zhí)行 (1)選行號ik，使 (2)交換第 k 行與第 ik 行。,21,PPT學習交流,(3)對于 i = k +1,k +2,n 計算,2.回代過程,22,PPT學習交流,評論：列主元素消去法，所需條件較少，僅僅要求方程組的系數(shù)矩陣 A 非奇異。 而且，對一般的方程組，它還具有良好的數(shù)值穩(wěn)定性，其計算量與順序消去法

9、的計算量相當。,23,PPT學習交流,3.3 矩陣的直接分解法,從3.2中討論可知，順序Gauss消去法的消元過程是將增廣矩陣A，bA（1），b（1）逐步化為矩陣A（n），b（n）。,可見，在順序Gauss消去法的過程中，系數(shù)矩陣AA（1）經(jīng)過一系列單位下三角矩陣的左乘運算化為上三角矩陣A（n），即,1.矩陣的三角分解法,24,PPT學習交流,這時,令,容易驗證,25,PPT學習交流,從順序Gauss消去法的矩陣運算表示式可知，系數(shù)矩陣A可分解為一個單位下三角矩陣L和一個上三角矩陣U的乘積，即,其中,26,PPT學習交流,定義 A = LU 叫做 A 的三角分解。 L，U 是下、上三角陣. 若

10、 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 的解向量。,三角分解用處,27,PPT學習交流,對于,由,解得,Ly =b,28,PPT學習交流,對于,由,求得,Ux =y,2

11、9,PPT學習交流,可以看出對于方程組：,只要對系數(shù)矩陣作了三角分解：,由這個簡單的計算過程可知，系數(shù)矩陣的三角分解很關鍵。,通過如下兩組公式很容易求解：,Ax =b,A =LU,30,PPT學習交流,以Doolittle（杜利特爾）分解為例,在順序Gauss消去法的過程中，若每步消元的主元素 akk(k)0，則矩陣A 可分解。而 akk(k) 0 的充要條件是A 的各階順序主子式不為零。,單位下三角陣,上三角陣, 矩陣 ARnn 的 Doolittle 分解,31,PPT學習交流,例： 利用Doolittle三角分解法分解矩陣,解：,1,2,3,4,1,1,1,2,6,12,3,7,6,24

12、,6,24,矩陣的三角分解,32,PPT學習交流,如果我們要求解方程組,則由,得到,33,PPT學習交流,由,解得,再由,求得方程組的解：,34,PPT學習交流,解：設,比較兩邊系數(shù)得:,例 用矩陣的杜利脫爾（Doolittle）分解解方程組,35,PPT學習交流,練習1：利用Doolittle三角分解方法解線性方程,解: 進行三角分解ALU，對增廣矩陣A,b作三角分解:,1 2 3 -2,-3,2,2,-3,-1,3,3,17,36,PPT學習交流,得到,1 2 3 -2,-3,2,2,-3,-1,3,3,17,這時，相應的方程組為：,37,PPT學習交流,練習2：利用Doolittle三角

13、分解方法解線性方程組,解：對增廣矩陣進行三角分解,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,38,PPT學習交流,1 2 3 -4 -2,-3,2,4,2,-3,1,3,3,3,2,2,-4,-1,17,-16,解得,等價方程組通過分解式容易寫出為：,39,PPT學習交流,練習： 用矩陣的杜利脫爾（Doolittle）分解 A=LU 解方程組：,答案：,40,PPT學習交流,2.列主元三角分解法,與列主元高斯消去法相對應的是列主元三角分解法。,選主元 D-分解的實施方法 采取與列主元類似的方法，在 D -分解中也選主元素。設使用 D-分解

14、公式 已進行了 k -1 步，第 k -1 次分解矩陣為,41,PPT學習交流,(1)進行第 k 步分解， 先尋找主元素，計算中間量,42,PPT學習交流,(2) 再按公式進行第 k 步的D-分解運算。,滿足 的 就是第 k 步的主元素，以 的值作為 。為此，交換矩陣 A(k-1) 的第 k 行與第 ik 行。此時：,43,PPT學習交流,例：用選主元的杜利脫爾（Doolittle）分解解方程組,解：對增廣矩陣進行變換，有,44,PPT學習交流,45,PPT學習交流,等價的三角方程組為：,回代求解，得,46,PPT學習交流,3.4 特殊線性方程組解法,1.追趕法,追趕法是專門用于求解三對角方程

15、組的。這類方程組經(jīng)常出現(xiàn)于用差分方法或有限元方法求解二階常微分方程邊值問題、熱傳導問題及三次樣條函數(shù)插值等問題，三對角方程組Axb的系數(shù)矩陣具有如下形式：,47,PPT學習交流,并且滿足,條件(i)保證方程組不能降階，條件(ii)保證三角分解可做到底。,在此條件下，可對A進行三角分解，設,A=,48,PPT學習交流,根據(jù)矩陣乘法及矩陣相等的定義，有：,則根據(jù)該組公式可以對三對角矩陣進行三角分解，對于三對角方程組Axb，設A的三角分解為ALU，則原方程組等價于,Lyb，Uxy,由Lyb求y；再由Uxy求x。,注 追趕法的存貯與計算量都很小，乘除運算總次數(shù)為 5n-4。,49,PPT學習交流,練習

16、 試用“追趕法”求解線性代數(shù)方程組：,50,PPT學習交流,2.改進的平方根法,改進的平方根法一般用于求解對稱線性方程組。,因為A對稱，則有：,推導得到：,51,PPT學習交流,3.6 線性方程組的迭代解法,1.問題的提出,1直接方法的缺陷(以Gauss消去法為代表)：,對于低中階數(shù)（n100）的線性方程組十分有效，但n很大時，特別是由某些微分方程數(shù)值解所提出來的線性方程組，由于舍入誤差的積累以及計算機的存貯困難，直接方法卻無能為力。,2解決方法：（利用迭代方法）,迭代方法：把線性方程組的數(shù)值求解問題化為一個迭代序列來實現(xiàn)。,52,PPT學習交流,具體做法,(2) 取任意初始向量 x(0) 構

17、成迭代序列:,由于迭代方法能避免系數(shù)矩陣中零元的存貯與計算，特別適用于解系數(shù)矩陣階數(shù)很高而非零元極少（即大型稀疏）的線性方程組。,53,PPT學習交流,迭代格式：,定義：,迭代矩陣：,迭代過程收斂：,若序列x(k)極限存在，稱此迭代過程收斂，否則稱為發(fā)散。,3. 需要討論的問題：,怎樣建立迭代格式；迭代過程是否收斂，誤差分析；如何加快收斂速度等等。,迭代法計算精度可控，特別適用于求解系數(shù)為大型的方程組。,54,PPT學習交流,2.雅可比迭代法,迭代格式：,縮寫為：,按此格式迭代求解的方法稱為雅可比迭代法,簡稱J法。,55,PPT學習交流,寫成矩陣形式：,L,U,D,分裂 A = D+ L+U,

18、拆分A為三個部分。,56,PPT學習交流,Jacobi 迭代矩陣,那么，原方程組與下面的迭代方程組同解：,D,L,U 的具體形式,57,PPT學習交流,J,58,PPT學習交流,J,59,PPT學習交流,例： 用雅可比迭代法解線性方程組,解 生成雅可比迭代格式：,從此表可以看出，迭代序列收斂于x*，若取x(12)作為近似解，則誤差不超過 10-5,60,PPT學習交流,3.高斯-賽德爾迭代法, ,矩陣形式：,Gauss-Seidel 迭代陣，簡記為G,61,PPT學習交流,G-S迭代,Jacobi迭代、G-S迭代計算式：,62,PPT學習交流,解,原方程等價于,63,PPT學習交流,建立Jacobi迭代格式如下,建立Gauss-Seidel迭代格式如下,64,PPT學習交流,4.逐次超松弛迭代法,SOR是GS迭代法的一種加速方法，是解大型稀疏矩陣方程組的有效方法之一。它具