線性方程組的數(shù)值解法課件

1、第2章 線性方程組的數(shù)值解法天津大學(xué)理學(xué)院數(shù)學(xué)系劉東毅2022/8/71線性方程組的數(shù)值解法第2章 線性方程組的數(shù)值解法主要目的：掌握線性方程組的數(shù)值解法2022/8/72線性方程組的數(shù)值解法主要內(nèi)容：直接法Gauss消去法直接三角分解法：追趕法，平方根法等方程組的性態(tài)與誤差分析迭代法Jacobi，Gauss-Seidel，SOR迭代法迭代法的收斂性分析2022/8/73線性方程組的數(shù)值解法2.1 Gauss 消去法Gauss 消去法是計算機(jī)上常用的解線性方程組的有效方法。此方法分為消元過程-把原方程組化為上三角形方程組的過程?；卮^程-求解上三角形方程組的過程。 其他的衍生方法Gauss-J

2、ordan消去法Gauss主元素法列主元素法全主元素法2022/8/74線性方程組的數(shù)值解法2.1.1 Gauss 消去法 設(shè)有線性方程組 Ax = b , (2.1.1)其中A = (ai,j)nn 非奇異，x = (x1 , x2 , , xn)T , b = (b1 , b2 , , bn)T 為方便起見，將 (2.1.1) 記為 A(1)x = b(1),(2.1.2)即2022/8/75線性方程組的數(shù)值解法 設(shè) 記乘數(shù)以-li1乘 (2.1.2) 的第一個方程, 加到第 i (i = 2 , 3 , , n) 個方程上去,(2.1.3)其中：第一次消元：(2.1.2)得 A(2) x

3、 = b(2), 即2022/8/76線性方程組的數(shù)值解法 設(shè) 記乘數(shù)以-li2乘 (2.1.3) 的第二個方程, 然后加到第 i個(i = 3 , 4 , , n) 方程上去,其中：第二次消元：(2.1.3)得 A(3)x = b(3), 即2022/8/77線性方程組的數(shù)值解法設(shè)第k-1次消元后的等價方程組A(k)x = b(k)Goto 列主元素法2022/8/78線性方程組的數(shù)值解法第k次消元： 設(shè) 記乘數(shù)以-li k乘 (2.1.5) 的第k個方程,然后加到第 i (i = k+1 , , n) 個方程上,得到與(2.1.1)等價方程組 A(k+1)x = b(k+1 ), 即202

4、2/8/79線性方程組的數(shù)值解法第k次消元后的等價方程組A(k+1)x = b(k+1)其中A(k+1)與 b(k+1)中的元素的計算公式為：2022/8/710線性方程組的數(shù)值解法第n-1次消元得到的等價上三角形方程組A(n)x = b(n)分別求得 xn , xn-1 , , x2 , x1 ,其計算公式如下： 回代過程消元與回代過程合起來稱為Gauss消去法的全過程,它大概需要n3/3次乘除法.2022/8/711線性方程組的數(shù)值解法例1.用Guass消去法解線性方程組：解：為了書寫方便，寫出此方程組的增廣矩陣，并用矩陣變換來描述消元過程。2022/8/712線性方程組的數(shù)值解法消元過程

5、如下：l21= 2l31= -1l32= 1/3寫成與原方程組等價的線性方程組為2022/8/713線性方程組的數(shù)值解法等價的線性方程組為回代求得原方程組的解為2022/8/714線性方程組的數(shù)值解法 若n階矩陣A = A(1) 的第一階至第k階順序主子式均不為零，即定理2.1.1則反之亦真。否則將溢出停機(jī).那么系數(shù)矩陣A滿足什么條件才會使這些元素全不為零呢？ 通過前面的討論可知，Gauss消去法要求主元素 此定理利用歸納法很容易證明。P172022/8/715線性方程組的數(shù)值解法由于Guass-Jordan消去法在線性代數(shù)中已經(jīng)討論過，并且與前面討論的Guass消去法相類似，故這里只用一個示

6、例來簡述一下。2.1.2 Guass-Jordan消去法用Guass-Jordan法解方程組：2022/8/716線性方程組的數(shù)值解法l13= 2/3l23= -5/3l21= 2l31= -1l12= 1l32= -1用Guass-Jordan法解方程組：得方程組的解為(1,2,0)T2022/8/717線性方程組的數(shù)值解法Gauss消去法的缺點(diǎn)：(1) 則消元不能進(jìn)行。(2) 若 但與 比較, 其絕對值甚?。ㄐ≈髟? 此時消元乘數(shù)li k的絕對值很大，勢必造成誤差的嚴(yán)重擴(kuò)散，使得計算結(jié)果失真。在此我們舉一個例子：2022/8/718線性方程組的數(shù)值解法例2.1.3. 用Guass消去法解

7、下列方程組（采用三位十進(jìn)制浮點(diǎn)運(yùn)算） 解：記增廣矩陣為，采用三位十進(jìn)制浮點(diǎn)運(yùn)算，消元過程用矩陣變換表示如下：該方程組的精確解為： 2022/8/719線性方程組的數(shù)值解法回代后求得 與精確解相差較大，原因在于兩次消元過程中均使用了小主元的結(jié)果。精確解下面詳細(xì)分析第二次消元2022/8/720線性方程組的數(shù)值解法詳細(xì)分析第二次消元如果精確計算，消元后方程組變成最后一個方程x3的系數(shù)為-1224.5，常數(shù)項(xiàng)為-2459.但由于計算精度的限制，1224.5只能取1.22103 ， 2459只能取2.46103。消元后最后一個方程變成這樣不是精確值2。2022/8/721線性方程組的數(shù)值解法2.1.3

8、 Gauss主元素法How to solve it ?Gauss主元素法： Gauss列主元素法 Gauss全主元素法所謂主元素法就是在消元前，首先選取此次消元的主元素。2022/8/722線性方程組的數(shù)值解法在第k次消元前，首先選取此次的主元素，若 則選取 為列主元素。交換增廣矩陣A(k),b(k)的第l行和第k行（若l=k則不必交換），然后進(jìn)行消元。 例2.1.4：用Guass列主元素法解例2.1.3. （采用三位十進(jìn)制浮點(diǎn)運(yùn)算）2.1.3.1.Guass列主元素法2022/8/723線性方程組的數(shù)值解法解為：x = (-2.60, 1.00, 2.00) T2.1.3.1.Guass列主

9、元素法精確解2022/8/724線性方程組的數(shù)值解法2.1.3.2 Guass全主元素法在第k次消元前，首先選取此次的主元素，若 則選取 為主元素。交換A(k),b(k)的第i1行和第 j1列，同時將自變量的 xk和 xj1的位置交換并記錄自變量的排列次序，直到整個消去法完成之后，再按記錄恢復(fù)自變?yōu)樽匀淮涡颉Ｏ旅媸堑趉次消元的示意圖2022/8/725線性方程組的數(shù)值解法Guass全主元素法（續(xù)）2022/8/726線性方程組的數(shù)值解法2022/8/727線性方程組的數(shù)值解法2.2 矩陣的三角分解及應(yīng)用若方程組的系數(shù)矩陣A為兩個三角形矩陣的乘積，則會對解線性方程組帶來很大的方便。本節(jié)將討論矩陣

10、的三角分解與方程組的解法的關(guān)系。本節(jié)的主要內(nèi)容：矩陣A 的LU分解。追趕法，平方根法與改進(jìn)的平方根法。重點(diǎn)掌握方程組的直接三角分解法的基本思想用矩陣的理論來解釋消元法2022/8/728線性方程組的數(shù)值解法2.2.1 Gauss 消去法與矩陣的三角分解首先討論矩陣的三角分解的概念。2022/8/729線性方程組的數(shù)值解法2.2.1.1 矩陣的三角分解定義1 設(shè) ARnn ，若A 能分解為一個下三角矩陣L與一個上三角矩陣U的乘積，即 A = LU， (2.2.1) 則稱這種分解為矩陣A的三角分解。 若L為單位下三角矩陣（主對角元素皆為1的下三角矩陣），U為上三角矩陣，則稱(2.2.1) 為A的D

11、oolittle分解。若L為下三角矩陣，U為單位上三角矩陣（主對角元素皆為1的上三角矩陣），則稱(2.2.1) 為A的Crout分解。下面討論Gauss消去法與三角分解的關(guān)系。2022/8/730線性方程組的數(shù)值解法2.2.1.2 Gauss 順序消去法與矩陣的三角分解 第一次消元將A(1) x = b(1) 化為 A(2) x = b(2)，這相當(dāng)于對增廣矩陣 A(1) , b(1) 作矩陣的初等變換 F1 A(1) , b(1) = A(2) , b(2) , 其中 F1為單位下三角矩陣，lk1（k=2,n）為第一次消元時的乘數(shù)。2022/8/731線性方程組的數(shù)值解法分析Gauss消去法

12、的消元過程記I為n階單位矩陣，m1 =(0, l2 1, l31, ，ln, 1)T，e1為I的第一列元素構(gòu)成的n維向量，則F1 = Im1 e1T。一般地，第k次消元將A(k) x = b(k ) 化為 A(k +1) x = b(k+1)，這相當(dāng)于對增廣矩陣 A(k) , b(k ) 作矩陣的初等變換 F k A(k) , b(k) = A(k+1) , b(k+1) ，其中F k 如下：2022/8/732線性方程組的數(shù)值解法分析Gauss消去法的消元過程其中l(wèi)i k（i = k+1,n）為第k次消元時的乘數(shù)。2022/8/733線性方程組的數(shù)值解法分析Gauss消去法的消元過程記mk

13、=(0,0, lk+1,k, lk+2,k, ，ln k)T，ek為n階單位矩陣I 的 第k列元素構(gòu)成的n維向量，則Fk = Imk ekT , k = 2, 3, , n-1。第n-1次消元將 A(n-1) x = b(n-1) 化為 A(n) x = b(n)，這相當(dāng)于對增廣矩陣 A(n) , b(n) 作矩陣的初等變換 ： Fn-1 A(n-1) , b(n-1) = A(n) , b(n) ，其中 Fn-1由 (2.2.2) 求得。 綜上所述，有 Fn-1 Fn-2 F1 A(1) , b(1) = A(n) , b(n) 。(2.2.3)2022/8/734線性方程組的數(shù)值解法分析G

14、auss消去法的消元過程令F = Fn-1 Fn-2 F1 , (2.2.4)由式 (2.2.3) 有FA(1) = A(n) ，F(xiàn)b(1) = b(n) (2.2.5) 設(shè)2022/8/735線性方程組的數(shù)值解法分析Gauss消去法的消元過程由式 (2.2.5) 可知：b = b(1) = F -1b(n) = Lb (n) ，A = A(1) =F -1A(n)=F1-1F2-1Fn-1-1U = LU ，其中2022/8/736線性方程組的數(shù)值解法分析Gauss消去法的消元過程定理2.2.1 設(shè) n 階矩陣 A 的各階順序主子式皆不為零，則A存在惟一的Doolittle分解。推論1 設(shè)

15、n 階矩陣 A 的各階順序主子式皆不為零，則A存在惟一的 Crout 分解。推論2 設(shè) n 階矩陣 A 的各階順序主子式皆不為零，則A存在惟一的分解A=LDU，其中L為單位下三角矩陣，D為對角矩陣，U為單位上三角矩陣。由式（2.2.6）可知，把A分解成了一個單位下三角矩陣L與一個上三角矩陣U的乘積，即實(shí)現(xiàn)了A的Doolittle分解?？梢?，若Gauss消去法能進(jìn)行到底，則一定能實(shí)現(xiàn)矩陣A的Doolittle分解。于是，有如下定理：2022/8/737線性方程組的數(shù)值解法定理2.2.1的證明證明：存在性由上面的論述已經(jīng)證明，下面只需證明惟一性。采用反證法。假設(shè)分解不惟一，則存在兩種不同的分解其中

16、L與 為單位下三角矩陣，U與 為上三角矩陣，則有 。由于A非奇異，所以detA = detLdetU = detU 0,即U非奇異。于是 。2022/8/738線性方程組的數(shù)值解法 仍為單位下三角矩陣，定理2.2.1的證明而 為兩個單位下三角矩陣的乘積，于是 ， 。為兩個上三角矩陣之積，仍為上三角矩陣。由它們相等知，必有這與假設(shè)矛盾，故分解惟一。 2022/8/739線性方程組的數(shù)值解法2.2.1.3 Gauss列主元素法與矩陣的三角分解 對于一般的非奇異矩陣也有類似的分解，為此要引入排列矩陣的概念。在上述定理中，將Doolittle分解改為Crout分解或LDU分解也是成立的。為什么？定義2

17、.2.2 交換單位矩陣的i，j兩行所得到的矩陣稱為初等(行)置換矩陣，初等(行)置換矩陣的乘積稱為(行)排列矩陣。引理2.2.1 設(shè)ARnn非奇異，則存在排列矩陣，PRnn使得PA的各階順序主子陣皆非奇異。定理2.2.2 設(shè) ARnn非奇異，則存在排列矩陣，PRnn 使得PA 有惟一的Doolittle分解 PA=LU，其中L為單位下三角矩陣，U為上三角矩陣。 2022/8/740線性方程組的數(shù)值解法 Gauss消去法與矩陣的三角分解 由前面的討論，我們看到解方程組的Gauss法對應(yīng)一種矩陣的分解。矩陣的分解可以利用矩陣的乘法實(shí)現(xiàn)！Gauss消去法矩陣LU分解反過來想一想，由矩陣的分解是否可以

18、找到一種解方程組的方法？2022/8/741線性方程組的數(shù)值解法2.2.2 直接三角分解法解方程組Ax = b首先考慮Doolittle分解 A=LU2022/8/742線性方程組的數(shù)值解法直接三角分解法 Doolittle分解設(shè)矩陣A存在唯一的Doolittle分解A=LU :利用矩陣乘法可以推出：( k = 1,2,n)和規(guī)定2022/8/743線性方程組的數(shù)值解法第 1 步第 n 步計算過程如下：先確定U的第一行，L的第一列（k=1），然后是U第二行、L第二列，一直下去，最后計算 unn。第 2 步2022/8/744線性方程組的數(shù)值解法直接三角分解法Doolittle分解法這樣方程組

19、Ax = b 等價于方程組 LUx = b。令 Ux = y，則解 Ax = b 等價于解 Ly = b (2.2.14)和 U x = y。 (2.2.15)這是兩個三角形方程組，它們很容易求解。 這種方法稱為直接三角分解法，其計算量大致與Guass消去法相同，約為 次乘除法運(yùn)算。（這里包含了計算L和U的計算量）2022/8/745線性方程組的數(shù)值解法求解(2.2.14) Ly = b，即其遞推公式為：2022/8/746線性方程組的數(shù)值解法求解(2.2.15) U x = y，即其遞推公式為：規(guī)定2022/8/747線性方程組的數(shù)值解法于是，求解(2.2.14) Ly = b 的遞推公式為

20、：求解(2.2.15) U x = y 的遞推公式為：注意：直接三角分解法計算量大致與Guass法相同（包含了計算L 和U 的計算量）2022/8/748線性方程組的數(shù)值解法2.2.3追趕法 考慮如下線性方程組，簡記為Ax=f, 稱為三對角方程組，其系數(shù)矩陣A稱為三對角矩陣。2022/8/749線性方程組的數(shù)值解法追趕法(矩陣分解定理2.2.3) 定理2.2.3 設(shè)三對角矩陣A滿足（1）ai 0 (i=2,3,n), ci 0 (i = 1,2,n-1)（2）|b1| |c1|，|bn| |cn| ，|bi| |ai| + |ci| (i=2,3,n-1) 。則A存在惟一的Crout分解。A

21、= LUBack追趕法的優(yōu)點(diǎn)2022/8/750線性方程組的數(shù)值解法追趕法由于A的特殊形式，它有如下分解形式：（2.2.22）2022/8/751線性方程組的數(shù)值解法追趕法利用矩陣乘法，比較等式兩邊的對應(yīng)元素有：利用式（2.2.23）便可實(shí)現(xiàn)A的Crout分解。2022/8/752線性方程組的數(shù)值解法追趕法這樣，方程組 A x = f 即為 LU x = f 。 令 Ux = y ，則原問題化為解兩個更簡單的方程組 L y = f 和 Ux = y。綜合分解與求解的過程，可得解三對角方程組的追趕法公式如下：2022/8/753線性方程組的數(shù)值解法追趕法公式2. 解 L y = f 的遞推公式：

22、 3. 解Ux = y 的計算公式：1. 計算ui的遞推公式： 2022/8/754線性方程組的數(shù)值解法追趕法的優(yōu)點(diǎn)： 計算量小，大約需要5n-4次乘除法。 存儲量小，只需用三個一維數(shù)組存放對角線與次對角線上的數(shù)據(jù)，及兩組工作單元保存計算的中間結(jié)果和計算解。 在定理2.2.3的條件下（主對角占優(yōu)），可以證明L與U中的元素有界，而且沒有用很小的數(shù)作除數(shù)，因此避免了中間結(jié)果數(shù)量級的巨大增長和舍入誤差的嚴(yán)重累積，不必選主元。 2022/8/755線性方程組的數(shù)值解法例題:用追趕法求解下面的方程組 解：利用追趕法，解法分為三步：Step 1. 計算ui。由遞推公式 2022/8/756線性方程組的數(shù)值

23、解法Step 2. 求解Ly = f ?？傻糜蛇f推公式： 2022/8/757線性方程組的數(shù)值解法Step 3. 求解Ux = y 。由遞推公式：，可得到2022/8/758線性方程組的數(shù)值解法2.2.4 平方根法 系數(shù)矩陣為對稱正定矩陣的線性方程組稱為對稱正定方程組，所謂平方根法是用來求解對稱正定方程組的方法。定理2.2.4（對稱正定矩陣的Cholesky分解）設(shè) ARnn 為對稱正定矩陣，則存在一個實(shí)的非奇異下三角矩陣 L 使得A = LLT，當(dāng)限定 L 的對角元素為正時，這種分解是惟一的。2022/8/759線性方程組的數(shù)值解法2.2.4.1 平方根法設(shè) 其中 A = (aij)nn 對

24、稱正定且 lii 0,（i = 1,2,n）, 利用矩陣乘法可得：2022/8/760線性方程組的數(shù)值解法平方根法利用（2.2.25）式便可實(shí)現(xiàn)A的LLT分解，這種分解稱為A的Cholesky分解。到改進(jìn)的平方根法2022/8/761線性方程組的數(shù)值解法平方根法于是，求解Ax = b等價于解 LLTx = b，它可化為解Ly = b 和 LT x = y這兩個三角形方程組。它們的求解如下：2022/8/762線性方程組的數(shù)值解法求解Ly = b：2022/8/763線性方程組的數(shù)值解法求解LTx = y2022/8/764線性方程組的數(shù)值解法于是，求解Ax = b等價于解 LLTx = b，它

25、可化為解Ly = b 和 LT x = y 這兩個三角形方程組。它們的求解公式為利用A的Cholesky分解求解對稱正定方程組的方法稱為平方根法，這是因?yàn)樵冢?.2.25）的第一式中含有開平方運(yùn)算的緣故。2022/8/765線性方程組的數(shù)值解法2.2.4.2 改進(jìn)的平方根法在平方根法的計算公式中，用到開方運(yùn)算，這是不理想的，為了避免開方可采用改進(jìn)的平方根法。定理2.2.5 設(shè) ARnn 為對稱正定矩陣，則存在唯一的分解A = LDLT。 （2.2.28）其中L為單位下三角矩陣，D為對角矩陣，且D的對角元素都為正數(shù)。2022/8/766線性方程組的數(shù)值解法 改進(jìn)的平方根法由分解式（2.2.28）

26、 A = LDLT ，利用矩陣乘法，不難導(dǎo)出下面的分解公式令和2022/8/767線性方程組的數(shù)值解法分解公式這樣便實(shí)現(xiàn)了A的LDLT分解，此時分解式中不再含有開方運(yùn)算。據(jù)此可按順序計算 2022/8/768線性方程組的數(shù)值解法改進(jìn)的平方根法 這樣求解對稱正定方程組Ax = b等價于解LDLTx = b，它可化為解Ly = b 和 LT x = D-1y。它們的求解公式分別計算如下：2022/8/769線性方程組的數(shù)值解法解Ly = b即得2022/8/770線性方程組的數(shù)值解法解LT x = D-1y即得2022/8/771線性方程組的數(shù)值解法改進(jìn)的平方根法 這樣求解對稱正定方程組Ax =

27、b等價于解LDLTx = b，它可化為解Ly = b 和 LT x = D-1y。它們的求解公式分別為2022/8/772線性方程組的數(shù)值解法2022/8/773線性方程組的數(shù)值解法2.3 向量和矩陣的范數(shù)（賦范線性空間理論初步）2022/8/774線性方程組的數(shù)值解法2.3.1 線性空間定義2.3.1 數(shù)域K上的線性空間X。設(shè)X是一個非空集合， K是個數(shù)域，若對X中的元素定義兩種運(yùn)算：加法“+”，滿足 x,y X，有x + y X(這稱為X對加法封閉)。數(shù)乘“”，滿足 K以及 x X，有 x X (這稱為X對數(shù)乘封閉)。2022/8/775線性方程組的數(shù)值解法并且 x,y,z X， , K，

28、滿足下列運(yùn)算規(guī)則： x + y = y + x;(x + y)+z = x+(y+z);存在零元素O X, x X,有x+O = x; x X,存在x的逆元素，記為-x, 使得x+(- x) = O;（也叫負(fù)元素）2022/8/776線性方程組的數(shù)值解法1 x = x，其中1 K ; ( x) = ( ) x; (x + y) = x+ y;( + ) x= x+ x;則稱X為數(shù)域K上的線性空間（或向量空間）；當(dāng)K為實(shí)數(shù)域時，稱X為實(shí)線性空間；當(dāng)K為復(fù)數(shù)域時，稱X為復(fù)線性空間。2022/8/777線性方程組的數(shù)值解法例如：Rn (或Cn)表示n維實(shí)（或復(fù)）向量的全體組成的集合,按照向量的加法技

29、術(shù)與向量的數(shù)量乘法，易證它是線性空間。再如 Rnn（或Cnn），Ca, b。定義2.3.2 稱Y是線性空間X的子空間 （簡稱Y為X的子空間），是指YX，Y非空，若 x,y Y， K，有x + y Y， x Y。2022/8/778線性方程組的數(shù)值解法2.3.1 線性空間定義2.3.3 由 M 張成（或生成）的子空間，記為 span M 2022/8/779線性方程組的數(shù)值解法2.3.1 線性空間定義2.3.4 設(shè)X為數(shù)域K上的線性空間，M = x1,x2,xn X，若對于i K (i = 1,n)， 1x1 + 2x2 + + nxn = 0, (2.3.1)僅當(dāng)1= 2 = = n = 0

30、時才成立，則稱集合M是線性無關(guān)的。若M不線性無關(guān)，則稱M是線性相關(guān)的。此時必存在不全為零的1，2，n 使（2.3.1）成立。2022/8/780線性方程組的數(shù)值解法2.3.1 線性空間 一般地，設(shè)M是線性空間X的非空集合（不一定是有限集合）。若M的每個有限子集均線性無關(guān)，則稱M線性無關(guān)。若M不線性無關(guān)，則稱M線性相關(guān)。2022/8/781線性方程組的數(shù)值解法2.3.2 內(nèi)積與內(nèi)積空間 定義2.3.5 設(shè)X為實(shí)數(shù)域R上的線性空間， x,y X，定義一個二元實(shí)函數(shù)，記為 (x, y)，滿足 (x, x) 0，并且(x, x) = 0，當(dāng)且僅當(dāng) x = 0； (x, y) = (y, x)； R 有

31、( x, y) = (x, y)； x, y, zX，有 (x+y, z) = (x, z) + (y, z)。則稱 (x, y) 為x 與 y 的內(nèi)積，X 稱為內(nèi)積空間（實(shí)內(nèi)積空間）。2022/8/782線性方程組的數(shù)值解法 2.3.2 內(nèi)積與內(nèi)積空間例2.3.1 在線性空間Rn中， x,y Rn ，規(guī)定：不難驗(yàn)證按上述規(guī)定(x, y)是Rn上的一種內(nèi)積，按此內(nèi)積Rn成為內(nèi)積空間。2022/8/783線性方程組的數(shù)值解法例2.3.2 在Ca, b上， f, g Ca, b，規(guī)定其中 (x) 稱為權(quán)函數(shù)，它滿足：(1) (x) 0， x a, b；(2) ；(3) 積分存在，n = 0,1,2

32、,。不難驗(yàn)證 (2.3.3) 滿足內(nèi)積定義2.3.5，按此內(nèi)積，Ca, b成為內(nèi)積空間。2022/8/784線性方程組的數(shù)值解法2.3.2 內(nèi)積與內(nèi)積空間特別地，當(dāng) (x) = 1 時，(2.3.3) 成為2022/8/785線性方程組的數(shù)值解法2.3.3 向量的范數(shù)定義2.3.6 設(shè)X為實(shí)數(shù)域R上的線性空間，N(x) = | x | 是定義在X上的非負(fù)實(shí)值函數(shù)，并滿足(1) 非負(fù)性。 對任意 x X，| x | 0；并且 | x | = 0， 當(dāng)且僅當(dāng)x = 0；(2) (正)齊次性。 對任意x X， R，有 | x | = | | x |；(3) 三角不等式。對任意 x, y X，有 |

33、x + y | | x | + | y | （2.3.7）。則|x|稱為X中向量x的范數(shù)，X為賦范線性空間。2022/8/786線性方程組的數(shù)值解法2.3.3 向量的范數(shù) 很顯然，在線性空間X中，由內(nèi)積定義的非負(fù)實(shí)值函數(shù)： 滿足范數(shù)的定義2.3.6，稱此范數(shù)為X中向量x的內(nèi)積范數(shù)（或2范數(shù)）?？挛?施瓦茲不等式 (Cauchy-Schwartz) ( x, y ) | x | | y |, 或 ( x, y )2 | x |2 | y |2 ,或 | ( x, y ) |2 ( x, x ) ( y, y )2022/8/787線性方程組的數(shù)值解法2.3.3 向量的范數(shù)證明：考慮內(nèi)積 (x+t

34、y, x+ty)。 實(shí)數(shù) t， (x+t y, x+t y) = (x, x) +2t (x, y) + t2 (y, y) 0.當(dāng)(y, y) = 0 時，y = 0，不等式顯然成立。當(dāng)(y, y) 0時，取t = -(x, y)/ (y, y)，得(x, x) -2(x, y)2/ (y, y)+ (x, y)2/ (y, y) 0，所以 (x, x) -(x, y)2/ (y, y) 0.綜上，即得柯西-施瓦茲不等式成立。 (x, y) | x | | y |2022/8/788線性方程組的數(shù)值解法2.3.3 向量的范數(shù)例2.3.3 在線性空間Rn中， x = (x1,x2, , xn)

35、TRn ，可以證明:均滿足范數(shù)定義，故分別稱為Rn中n元向量x的 范數(shù)，1范數(shù)，2范數(shù)（又稱為Euclid范數(shù)，簡稱歐氏范數(shù)）。2022/8/789線性方程組的數(shù)值解法R2中, 三種范數(shù)的幾何解釋x軸y 軸O2022/8/790線性方程組的數(shù)值解法2.3.3 向量的范數(shù)例2.3.4 在線性空間Ca, b 中， f Ca, b，容易證明：滿足范數(shù)的定義，故它們是Ca, b上范數(shù)，分別稱為 f 的 范數(shù)，f 的 2范數(shù)（又稱Euclid范數(shù)，簡稱歐氏范數(shù)）。2022/8/791線性方程組的數(shù)值解法2.3.3 向量的范數(shù)例2.3.5 在線性空間Rnn中，設(shè)（Rnn中的向量）矩陣A = (ai j)

36、Rnn ，可以驗(yàn)證是線性空間 Rnn 中矩陣 A 的范數(shù)，稱為Frobenius（弗羅賓紐斯）范數(shù)，簡稱F范數(shù)。2022/8/792線性方程組的數(shù)值解法矩陣的算子范數(shù)（P范數(shù)）例2.3.6 設(shè)xRn，A Rnn ，給定 Rn 中一種向量范數(shù) |x|P (P = 1，2，)，相應(yīng)地可以定義一個以矩陣為自變量的非負(fù)函數(shù)則|A|P為矩陣A的范數(shù)，稱此范數(shù)為由Rn中向量范數(shù)導(dǎo)出的矩陣范數(shù)（矩陣的P范數(shù)），又稱A的算子范數(shù)。（證明略）2022/8/793線性方程組的數(shù)值解法矩陣的算子范數(shù)易知關(guān)系式 |Ax|P |A|P|x|P (P=1，2，) (2.3.19)成立，我們稱矩陣的P范數(shù)與向量的P范數(shù)滿足

37、相容性。即有如下定義: 定義2.3.9 若A Rnn 及 x Rn 有 |Ax| |A|x| ，則稱矩陣范數(shù)| |與向量范數(shù) | | 相容。由 (2.3.17)2022/8/794線性方程組的數(shù)值解法 根據(jù)矩陣范數(shù)與向量范數(shù)的相容性，我們很容易得到所謂算子范數(shù)的乘法性質(zhì)： 設(shè) ，則 。實(shí)際上， 所以，根據(jù)算子范數(shù)的定義即可得到： 2022/8/795線性方程組的數(shù)值解法矩陣的算子范數(shù)例2.3.7 設(shè) A = (ai j) Rnn ，則其中max (ATA)表示ATA的最大特征值。它們分別稱為A的行范數(shù)、列范數(shù)、譜范數(shù)，又分別稱為 A 的 范數(shù)，1范數(shù)，2范數(shù)。它們就是分別由向量范數(shù)，1范數(shù)和2

38、范數(shù)導(dǎo)出的矩陣范數(shù)。這些就是由 (2.3.17)定義的矩陣P-范數(shù)的具體計算式2022/8/796線性方程組的數(shù)值解法攝動定理定理2.3.7 （矩陣攝動定理）設(shè) , I 為單位矩陣，若| B| 1，則 非奇異，且有 ,其中“|” 指矩陣的算子范數(shù)。 2022/8/797線性方程組的數(shù)值解法定義2.3.7 設(shè)X為賦范線性空間，x(k) 為X中一向量序列，x* X，若賦范線性空間X中的極限概念否則稱向量序列x(k) 不收斂（或發(fā)散）。則稱x(k) 依X中范數(shù) | | 收斂于x* ，簡稱x(k) 收斂于x*，記為2022/8/798線性方程組的數(shù)值解法向量范數(shù)的等價性定理2.3.3（有限維空間的范數(shù)

39、等價性定理）設(shè)X為有限維線性空間，|x|與|x|為X上任何兩種范數(shù)，則|x|與|x| 是等價的，即 x X，存在與x無關(guān)的正數(shù)c1，c2 使得c1 |x| |x| c2 |x|成立。2022/8/799線性方程組的數(shù)值解法矩陣范數(shù)等價性定理2.3.6（矩陣范數(shù)等價性定理）Rnn上任何兩種矩陣范數(shù)是等價的。即|A|與|A|為Rnn任何兩種矩陣范數(shù)，則存在與A無關(guān)的正數(shù)c1，c2 使得 c1 |A| |A| c2 |A| 成立。 2022/8/7100線性方程組的數(shù)值解法例2.3.8 設(shè)x*Rn，x(k)Rn 為一向量序列，記 和 ，可以證明x(k)在Rn中依任何范數(shù)收斂于x*都等價于n元向量按其

40、分量收斂，即： 2.3.3 向量的范數(shù)2022/8/7101線性方程組的數(shù)值解法例2.3.9 設(shè)A(k) Rnn為一矩陣序列，A = (ai j) Rnn ，記 ?？梢宰C明A(k)在Rnn中依任何范數(shù)收斂于A 都等價于矩陣按其分量（即它的元素或坐標(biāo)）收斂，即這兩個例子可以由有限維空間的范數(shù)等價性定理 2.3.3來證明。它們說明在Rn和 Rnn中，依任何范數(shù)收斂，都等價于按分量（元素或坐標(biāo)）收斂。 2022/8/7102線性方程組的數(shù)值解法 2.3.3 向量的范數(shù)定義2.3.12 設(shè)A Rnn（或A Cnn），其特征值為 i （i =1,2,n），則稱為A的譜半徑。 定理2.3.9 設(shè)A Rnn

41、（或A Cnn），則對于任何一種矩陣的算子范數(shù)|，都有 (A) |A|。定理2.3.10 設(shè) A Rnn為實(shí)對稱矩陣，則有 |A|2 = (A)。2022/8/7103線性方程組的數(shù)值解法2.4 方程組的性態(tài)與誤差分析 前面討論了解線性方程組的直接法。當(dāng)我們用某種方法求解一個線性方程組時，求得的解有時是不準(zhǔn)確的，其原因可能是：方法不合理，使得誤差較大；方程組本身的性態(tài)不夠好。在這節(jié)中，我們將討論方程組的性態(tài)問題。首先給出一個例子。 2022/8/7104線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析例2.4.1 設(shè)方程組 和 它們的特征如下： 系數(shù)矩陣相同，右端常數(shù)項(xiàng)不同，誤差向量為0，0.

42、01T。（2.4.1）的解是x = 100，-100T（2.4.2）的解為x = 1，0T2022/8/7105線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析我們假設(shè)方程組 (2.4.1) 的右端常數(shù)項(xiàng)是精確的，即（2.4.2）可以看作是由 (2.4.1) 的右端項(xiàng)作微小的擾動（0.01）而得到的方程組。由此我們看出，方程組右端項(xiàng)微小的擾動就使得其解變化很大。對于這樣的方程組，用Gauss法很難求得較精確的解。為分析其中原因，用Gauss法求解之。 2022/8/7106線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析只有當(dāng) = 0 時，得到真解x = 100，-100T。誤差向量為x =

43、-9900 ，104 T，要想使誤差 | x | 10 3 ，必須有 10 7。這表明該方程組對誤差相當(dāng)敏感，類似這樣的方程組，我們稱之為“病態(tài)” 方程組。，得到 ，。2022/8/7107線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析定義2.4.1 若方程組Ax = b的系數(shù)矩陣A或常數(shù)項(xiàng)b有微小變化，會引起方程組解的巨大變化，這樣的方程組稱為“病態(tài)” 方程組，矩陣A稱為“病態(tài)” 矩陣；否則稱為“良態(tài)” 方程組，A稱為“良態(tài)” 矩陣。 2022/8/7108線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析定理2.4.1 設(shè)Ax = b 0，A非奇異，僅方程組的右端項(xiàng)b有擾動（或誤差）b 0

44、，相應(yīng)的解x 有擾動x，即下式成立： A(x+x) = b+b (2.4.3)則有2022/8/7109線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析證： 由（2.4.3）有 Ax+Ax = b+b ，由于Ax = b，所以 A x = b，從而 x = A-1b。 兩邊取范數(shù)且利用相容性得 |x| | A-1|b|。另一方面，由| Ax | | A | | x |，有 所以 ，2022/8/7110線性方程組的數(shù)值解法注1：記cond(A) = | A-1| |A|，cond(A) 稱為矩陣A的條件數(shù)，其中| |指的是矩陣的算子范數(shù)，于是 cond(A) = | A-1| |A| | A-

45、1A| = |I| =1（算子范數(shù)）。 cond(A) = cond(A)，0。上述定理可以推廣到A和b均有誤差的情況，有如下定理：2022/8/7111線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析定理2.4.2 設(shè)Ax = b 0，A非奇異，僅方程組的系數(shù)矩陣A有擾動（或誤差）A，相應(yīng)的解x 有擾動x，即下式成立：(A+A)(x+x) = b。 (2.4.7)則當(dāng)| A-1|A| 1時，有2022/8/7112線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析定理2.4.3 設(shè)Ax = b 0，A非奇異，方程組的系數(shù)矩陣A有擾動A，右端項(xiàng)b有擾動b 0 ，相應(yīng)的解x 有擾動x，即下式成立：

46、 (A+A)(x+x) = b+b (2.4.9)當(dāng)| A-1| |A|1時，有 (2.4.10)2022/8/7113線性方程組的數(shù)值解法(2) 當(dāng)擾動A充分小時， ，所以解的相對誤差 可以很好地由條件數(shù)cond(A) 來描述，即大約不超過A與b的相對誤差 的cond(A) 倍，即 注2： (1) 條件 | A-1| |A| 1（或相對較大，根據(jù)具體問題的特征來判斷）時，解的相對誤差可能很大。所以，當(dāng)條件數(shù)相對大時，稱 Ax =b為病態(tài)方程組，系數(shù)矩陣A稱為病態(tài)矩陣，否則稱 Ax=b為良態(tài)方程組，A稱為良態(tài)矩陣。矩陣的病態(tài)性質(zhì)是矩陣本身的特征。所謂的“病態(tài)” 現(xiàn)象在自然界普遍存在，病態(tài)問題已

47、經(jīng)成為一項(xiàng)重要的研究課題，同時也是難題。對此問題，人們業(yè)已取得一些成果。這些內(nèi)容超過了本課程的要求,請同學(xué)們參考有關(guān)的文獻(xiàn)。2022/8/7115線性方程組的數(shù)值解法(4) 條件數(shù)的計算依賴于矩陣所取的范數(shù)，常用的條件數(shù)為： (a) cond(A)=|A-1|A|，條件數(shù) (b) cond1(A) = |A-1| 1|A|1，1條件數(shù) (c) cond2(A) = |A-1| 2|A|2，2條件數(shù) 當(dāng)A為實(shí)對稱矩陣時， 或 2022/8/7116線性方程組的數(shù)值解法(5) 但由于范數(shù)的等價性，各種條件數(shù)在誤差估計中不會引起本質(zhì)的差別。 (6) 利用定理2.4.1、2.4.2和2.4.3進(jìn)行誤差

48、分析時，事先不必知道方程組的解，這種誤差的分析方法稱為事先估計法（在計算解之前就可估計誤差）。2022/8/7117線性方程組的數(shù)值解法2.4方程組的性態(tài)與誤差分析在前面例2.4.1中，系數(shù)矩陣A的逆矩陣為 它的條件數(shù) cond(A)=|A-1|A|=199001.99=39601，此值很大，故該方程組是一個“病態(tài)” 方程組。2022/8/7118線性方程組的數(shù)值解法著名的Hilbert矩陣Hn就是一個病態(tài)矩陣，且當(dāng)n越大時，“病態(tài)”越嚴(yán)重。 2022/8/7119線性方程組的數(shù)值解法 雖然可以用線性方程組的系數(shù)矩陣的條件數(shù)來判斷方程組是否病態(tài)，但由于在計算條件數(shù)時，要先算出系數(shù)矩陣的逆矩陣，

49、這也就相當(dāng)于求解方程組了，顯然不可行。所以，在實(shí)際的計算中，往往通過系數(shù)矩陣元素之間的關(guān)系來分析。若系數(shù)矩陣某些行（或列）接近線性相關(guān)，矩陣元素之間數(shù)量級相差很大且分布沒有一定規(guī)律，用主元素法求解時出現(xiàn)小主元，則該線性方程組很可能是病態(tài)的。 2022/8/7120線性方程組的數(shù)值解法2022/8/7121線性方程組的數(shù)值解法2.5 解線性方程組的迭代法 本節(jié)的主要內(nèi)容Jacobi 迭代法Guass-Seidel 迭代法SOR方法2022/8/7122線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法 設(shè)有線性方程組 Ax = b , 即其中A非奇異, 且 aii 0, (i = 1, 2,

50、, n )。2022/8/7123線性方程組的數(shù)值解法將(2.5.1) 改寫成其等價形式2022/8/7124線性方程組的數(shù)值解法構(gòu)造如下的迭代公式（格式）(k表示迭代次數(shù))返回矩陣形式2022/8/7125線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法任取初始向量 ，代入(2.5.3)的右端，可得 ，稱x(1)為第一次近似解，然后把 x(1)代入(2.5.3)的右端，得第二次近似解 ，如此下去可得到一向量序列x(k)Rn，若此序列收斂，即 成立，則稱此迭代法收斂（否則稱此迭代法是發(fā)散的）。在2.6中，我們將證明x* 即為原方程組的解。 2022/8/7126線性方程組的數(shù)值解法2.5.

51、1 Jacobi 迭代法因此，當(dāng) k 充分大時，可以取 x(k) 作為原方程組(2.5.1) 的近似解。這種方法稱為 Jacobi 迭代法，式（2.5.3）稱為 Jacobi 迭代公式（分量形式），或稱Jacobi 迭代格式的分量形式，或稱計算公式的分量形式，它可以簡記為： 2022/8/7127線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法例2.5.1 用Jacobi迭代法解如下方程組，初始向量x(0) = (0, 0, 0)T 。 解：其迭代公式為 2022/8/7128線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法取初始向量 x(0) = (0, 0, 0)T ，計算結(jié)果如下

52、： 2022/8/7129線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法 k x1(k) x2(k) x3(k) 11.200001.500002.0000020.75000 1.100002.1400030.769001.138752.1200040.768131.138882.125225 0.767331.138332.1253660.767361.138412.1253670.767361.138412.125372022/8/7130線性方程組的數(shù)值解法2.5.1 Jacobi 迭代法可見當(dāng)?shù)螖?shù)k不斷增大時，迭代結(jié)果越來越逼近于一個確定的向量，我們可取x(7) = (0.7

53、6736，1.13841，2.12537)T作為方程組的近似解。 2022/8/7131線性方程組的數(shù)值解法Jacobi 迭代法的矩陣形式 為討論迭代法的收斂性，常常要用到迭代公式的矩陣形式，為此將(2.5.1) 的系數(shù)矩陣 A作如下分解 (裂解)：2022/8/7132線性方程組的數(shù)值解法Jacobi 迭代法矩陣形式其中2022/8/7133線性方程組的數(shù)值解法Jacobi 迭代法矩陣形式2022/8/7134線性方程組的數(shù)值解法Jacobi 迭代法矩陣形式2022/8/7135線性方程組的數(shù)值解法Jacobi 迭代法矩陣形式于是式（2.5.1）成為 ( D-L-U ) x = b。由上式可

54、得 Dx = ( L+U ) x + b。由于aii 0 ，（i=1，2，n），故D可逆，從而有 x = D-1( L+U ) x + D-1 b。將上式寫成迭代形式，即為x(k+1) = D-1( L+U ) x(k)+ D-1 b。 (2.5.6) 上式即為Jacobi迭代法的矩陣形式。2022/8/7136線性方程組的數(shù)值解法若令 M1 = D-1( L+U )，f 1 = D-1b，則 (2.5.6)x(k+1) = D-1( L + U ) x(k) + D-1b?？杀硎緸閤(k+1) = M1 x(k) + f 1，其中M1稱為 Jacobi 迭代法的迭代矩陣。2022/8/713

55、7線性方程組的數(shù)值解法2.5.2 Guass-Seidel 迭代法 為了加速收斂，我們構(gòu)造如下的迭代公式 2022/8/7138線性方程組的數(shù)值解法Jacobi 迭代法與Gauss-Seidel迭代法的比較2022/8/7139線性方程組的數(shù)值解法Gauss-Seidel迭代公式返至G-S矩陣形式2022/8/7140線性方程組的數(shù)值解法2.5.2 Guass-Seidel 迭代法這樣，當(dāng)計算xi(k+1)時，總是起用前面最新計算出的 x1(k+1)，x2(k+1)，xi-1(k+1)，如果方法收斂，它們一般比xj(k) ( j = 1,2,i-1) 要精確，這種方法稱為Guass-Seide

56、l迭代法，式（2.5.8）稱為Guass-Seidel迭代公式，它可以簡記為返至G-S矩陣形式2022/8/7141線性方程組的數(shù)值解法2.5.2 Guass-Seidel 迭代法例2.5.2 用Guass-Seidel迭代法解例2.5.1中的方程組。解：此方程組的Guass-Seidel法迭代公式為：2022/8/7142線性方程組的數(shù)值解法解此方程組的Guass-Seidel法迭代公式：取初始向量x(0)=(0, 0, 0)T，進(jìn)行迭代，2022/8/7143線性方程組的數(shù)值解法計算結(jié)果如下：k x1(k) x2(k) x3(k) 1 1.20000 1.35000 2.110002 0.

57、748501.14269 2.128763 0.766421.13811 2.125434 0.767381.13840 2.125395 0.767351.13841 2.125386 0.767361.13841 2.12537 只迭代了6次，得到的x(6)與用Jacobi迭代法迭代7次的結(jié)果相同。2022/8/7144線性方程組的數(shù)值解法下面給出Guass-Seidel迭代法的矩陣形式。由上式可得 (D-L)x = U x + b。將上式寫成迭代形式，即為(D-L) x(k+1) = U x(k) + b。 (2.5.10)因?yàn)?(D-L) 非奇異，利用（2.5.10）可得x(k+1)

58、= (D-L)-1U x(k)+ (D-L)-1 b。 (2.5.12)上式即為Gauss-Seidel迭代法的矩陣形式（式(2.5.8或2.5.9) 為分量形式）。 利用(2.5.5)，(2.5.1) 成為( D-L-U ) x = b。2022/8/7145線性方程組的數(shù)值解法2.5.2 Guass-Seidel 迭代法 若令M2 = (D - L)-1U，f 2 = (D - L)-1b，則(2.5.12) x(k+1) = (D - L)-1U x(k)+ (D - L)-1 b?？杀硎緸閤(k+1) = M2 x(k) + f 2，其中M2稱為Gauss-Seidel迭代法的迭代矩陣

59、。2022/8/7146線性方程組的數(shù)值解法 為了進(jìn)一步使生成的迭代點(diǎn)列x(k)快速收斂到原問題的解，我們研究所謂的 SOR法，全稱 Successive Over Relaxation method，逐次超松弛迭代法。2022/8/7147線性方程組的數(shù)值解法2.5.3 SOR方法 逐次超松弛迭代法（Successive Over Relaxation method），簡稱SOR法，此方法是Gauss-Seidel迭代格式的一種加速方法，或看成是Gauss-Seidel迭代格式的一種推廣。SOR法是解大型稀疏方程組（系數(shù)矩陣有大量零元素）的有效算法之一。 將Gauss-Seidel迭代法的分

60、量形式(2.5.9) 加以變形得到 2022/8/7148線性方程組的數(shù)值解法2.5.3 SOR方法 即第k+1次迭代的結(jié)果看成是第k次迭代的結(jié)果加上一個校正值。我們希望校正值乘上一個適當(dāng)?shù)膮?shù)，使得改進(jìn)后的迭代方案收斂的速度得到加快，即有如下迭代格式，稱之為SOR迭代格式（或SOR方法）。上式可理解為校正值， 2022/8/7149線性方程組的數(shù)值解法2.5.3 SOR方法 稱為松弛因子。當(dāng) 1時稱為超松弛迭代法，當(dāng) 1時稱為低松弛迭代法， = 1時，(2.5.14) 就是Gauss-Seidel迭代法。為了加速收斂，常常采用超松弛迭代法。2022/8/7150線性方程組的數(shù)值解法2.5.3