3線性方程組解法

1、第3章 線性方程組的解法本章討論線性方程組的求解問(wèn)題.線性方程組的矩陣表示式中A稱為系數(shù)矩陣，b稱為右端項(xiàng)。數(shù)值分析中，線性方程組的數(shù)值解法主要分為直接法和迭代法兩大類。直接法是用有限次計(jì)算就能求出線性方程組“準(zhǔn)確解”的方法（不考慮舍入誤差）；迭代法是由線性方程組構(gòu)造出迭代計(jì)算公式，然后以一個(gè)猜測(cè)的向量作為迭代計(jì)算的初始向量逐步迭代計(jì)算，來(lái)獲得滿足精度要求的近似解。迭代法是一種逐次逼近的方法。1 線性方程組的迭代解法線性方程組迭代解法有Jocobi迭代法、Gauss-Seidel迭代法及SOR法等基本思想（與簡(jiǎn)單迭代法類比）將線性方程組等價(jià)變形為以構(gòu)造向量迭代格式用算出的迭代向量序列去逼近解。

2、1. 構(gòu)造原理（1） Jacobi迭代法將線性方程組的第i個(gè)變?cè)闷渌鹡-1個(gè)變?cè)沓觯傻?Jacobi迭代格式: （3）取定初始向量，代入，可逐次算出向量序列，這里。（2）Gauss-Seidel迭代法Seidel迭代格式:例1對(duì)線性方程組寫(xiě)出Jacobi迭代格式和Gauss-Seidel迭代格式.3）SOR法SOR法的迭代格式式中參數(shù)w稱為松弛因子，當(dāng)w =1時(shí)，SOR法就是Seidel迭代法.2.迭代分析及向量收斂 1） 三種迭代法的向量迭代格式對(duì) Ax=b，將系數(shù)矩陣A作如下分解則Ax=b可以寫(xiě)成Jacobi迭代的向量迭代格式，. 為Jacobi迭代法的迭代矩陣.Seidel向量迭代

3、格式，.為Seidel迭代法的迭代矩陣.SOR法的向量迭代格式，.為超松弛迭代法的迭代矩陣。三種迭代格式可寫(xiě)成迭代格式2）向量收斂定義定義1 設(shè)向量序列及向量都是中的向量，如果有 成立,則稱收斂于.簡(jiǎn)記為。3）范數(shù)定義與科學(xué)計(jì)算中的常用范數(shù)定義2 設(shè)L是數(shù)域K上的一個(gè)線性空間，如果定義在L上的實(shí)值函數(shù)滿足1) ，有, 且；2) ，有；3) ，有,則稱是L上的一個(gè)范數(shù)，稱為x的一個(gè)范數(shù)。范數(shù)的定義很象絕對(duì)值函數(shù)，故常用或表示范數(shù)，而范數(shù)常記為或。這樣，上面范數(shù)定義中的3個(gè)條件常寫(xiě)為1），有, 且；2），有；3），有將其與絕對(duì)值比較，是否很象？實(shí)際上，很多有關(guān)絕對(duì)值的運(yùn)算和結(jié)論可以平行引進(jìn)到有關(guān)范

4、數(shù)的運(yùn)算和證明問(wèn)題中。數(shù)值分析中常用的線性空間有l(wèi) n維向量空間l 矩陣空間連續(xù)函數(shù)空間函數(shù)空間是由閉區(qū)間上所有連續(xù)函數(shù)組成的集合，其線性運(yùn)算定義為加法數(shù)乘 ，為數(shù)在這些空間上，數(shù)值分析中常用的范數(shù)有(1)的向量范數(shù)1) 2) 3) 式中向量.例2 計(jì)算向量的各種范數(shù).(2) 的矩陣范數(shù)矩陣范數(shù)要滿足如下四條1），有,且；2），有；3），有；4），有.由于線性方程組求解問(wèn)題中，系數(shù)矩陣總是與向量聯(lián)系在一起的，為描述這種聯(lián)系，引入如下的算子范數(shù)概念.定義3 設(shè)矩陣，稱為矩陣A的算子范數(shù)。容易證明，矩陣A的算子范數(shù)也是矩陣范數(shù)，且滿足不等式關(guān)系.例3設(shè)為矩陣的算子范數(shù)，證明若，則為非奇異矩陣，且證

5、：用反證法。若為奇異矩陣，則其對(duì)應(yīng)的方程組有非零解，即有，使，得出兩邊取范數(shù)并作范數(shù)運(yùn)算，矛盾，得非奇異。常用的矩陣范數(shù)有如下4種1）列范數(shù)：2）行范數(shù)：3）F范數(shù)：4）2范數(shù)：，是最大特征值。以上4個(gè)矩陣范數(shù)中，是算子范數(shù)，不是算子范數(shù)。例4 計(jì)算矩陣的各種范數(shù).3）范數(shù)等價(jià)與向量極限定義4 設(shè)是線性空間L上的兩個(gè)范數(shù)，若存在正常數(shù)m和M，成立則稱范數(shù)是等價(jià)范數(shù)。定理1 上的所有范數(shù)都是等價(jià)的。定理2 。式中是上任何一種范數(shù)。4）譜半徑及其與范數(shù)的關(guān)系定義5 設(shè)，是A的n個(gè)特征值，稱為矩陣A的譜半徑。注意如果是復(fù)數(shù)，表示復(fù)數(shù)模。定理3 設(shè)表示的某種算子范數(shù)，則有 引理4 設(shè)，則 3. 迭代法

6、的收斂條件與誤差估計(jì)1）收斂條件定理5：對(duì)任意初始向量，由迭代格式產(chǎn)生的向量序列都收斂的充要條件是.證明 必要性設(shè)，在中令，得,于是有由及的任意性，有.再由引理，可得.充分性因?yàn)?，則有I-B非奇異（這里I為單位矩陣），從而線性方程組有唯一解，即有展開(kāi)有.類似必要性處理，有由引理，由有，上式取極限，得.l 判別條件若，則迭代法收斂.是矩陣B的某種算子范數(shù).定義6設(shè)，1）如果A的主對(duì)角元素滿足 則稱矩陣A是嚴(yán)格行對(duì)角占優(yōu)陣；2）如果A的主對(duì)角元素滿足 則稱矩陣A是嚴(yán)格列對(duì)角占優(yōu).嚴(yán)格行對(duì)角占優(yōu)陣和嚴(yán)格列對(duì)角占優(yōu)陣統(tǒng)稱為嚴(yán)格對(duì)角占優(yōu)陣.定理 嚴(yán)格對(duì)角占優(yōu)陣是非奇異矩陣。證明 不妨設(shè)矩陣是嚴(yán)格行對(duì)角占

7、優(yōu)陣. 用反證法證明.若A是奇異的，則由矩陣?yán)碚摽芍?，齊次線性方程組有非零解，即存在，滿足.記，有將的第m個(gè)等式寫(xiě)為等式兩邊取絕對(duì)值有因?yàn)椋鲜酵?，有此與A是嚴(yán)格行對(duì)角占優(yōu)陣矛盾. 故若A是非奇異的.l 判別條件設(shè)矩陣A是嚴(yán)格對(duì)角占優(yōu)陣，則解線性方程組的Jacobi迭代法和Seidel迭代法均收斂.證明 只對(duì)A是行對(duì)角占優(yōu)情況證之. 設(shè)矩陣A是嚴(yán)格行對(duì)角占優(yōu)陣，則有， Jacobi迭代矩陣，故有由判別條件，可得Jacobi迭代的收斂性.對(duì)Seidel迭代，其迭代矩陣，設(shè)是矩陣的任一特征值，則有特征方程因，故矩陣的特征方程變?yōu)檫@個(gè)行列式方程對(duì)應(yīng)的矩陣如果，利用矩陣A的行對(duì)角占優(yōu)定義，可以得出如

8、下不等式這說(shuō)明矩陣也是行嚴(yán)格對(duì)角占優(yōu)陣，由定理，有, 矛盾，故應(yīng)有成立. 由的任意性有譜半徑，于是可得Seidel迭代的收斂性.定理7 SOR法收斂的必要條件是松弛因子w滿足0<w<2.證明 因?yàn)镾OR法的迭代矩陣為有 設(shè)是的n個(gè)特征值，則有，若SOR收斂，必有，注意到，得. 解之得.l 判別條件III設(shè)，如果（1）對(duì)稱正定，（2），則解的SOR迭代法收斂.設(shè)A是對(duì)稱正定矩陣，則解的Seidel迭代法收斂.l 判別條件IV設(shè)，如果（1）為嚴(yán)格對(duì)角占優(yōu)陣，（2），則解的SOR迭代法收斂.2）誤差估計(jì)定理8 設(shè)矩陣B的某種算子范數(shù)，則由式算出的序列與線性方程組的準(zhǔn)確解有如下的誤差估計(jì)1

9、） 2） 證明可以參照非線性方程求根定理的證明，注意將那里的絕對(duì)值換成這里的范數(shù)，那里的函數(shù)換成這里的矩陣，并注意范數(shù)關(guān)系的使用即可。練習(xí)1 設(shè)方程組為寫(xiě)出Jacobi迭代格式和Gauss-Seidel迭代格式，判別這兩種迭代法的收斂性.練習(xí)2 設(shè)方程組為判別Jacobi迭代法和Gauss-Seidel迭代法的收斂性.練習(xí)3 設(shè)方程組為判別Jacobi迭代法和Gauss-Seidel迭代法的收斂性.練習(xí)4 方程組，其中確定使Jacobi迭代法和Gauss-Seidel迭代法均收斂的的取值范圍.練習(xí)5 證明矩陣正定的充要條件是而Jacobi迭代只對(duì)是收斂的.3.4 線性方程組的直接解法 解線性方

10、程組的直接法有Gauss消元法，LU分解法及一些特殊線性方程組的解法等，其中Gauss消元法是直接法的基礎(chǔ).本章的重點(diǎn)是在一般公式推導(dǎo)上，要注意學(xué)習(xí)和體會(huì).1. Gauss消元法基本思想先將線性方程組通過(guò)消元方法化為同解的上三角方程組，然后從該三角方程組中按第n個(gè)方程、第n-1個(gè)方程、第1個(gè)方程的順序，逐步回代求出線性方程組的解.1) 構(gòu)造原理Gauss消元法的求解過(guò)程分為兩個(gè):“消元”：把原方程組化為上三角方程組；“回代”：求上三角方程組的解.為推導(dǎo)公式的方便，記要求解的原方程組為Gauss消元法的算法構(gòu)造如下一、消元過(guò)程1）設(shè),令乘數(shù) , 做(消去第i個(gè)方程組的x1)操作第1個(gè)方程+第i個(gè)

11、方程（i =2,3,n）則第i個(gè)方程變?yōu)檫@樣消去第2，3，n個(gè)方程的變?cè)獂1后，原線性方程組變?yōu)?式中的計(jì)算公式為這樣就完成了第1步消元.2) 對(duì)所得線性方程組中由第2，3，n個(gè)方程組成的n-1元線性方程組做同樣的處理，可得到第2步消元后的線性方程組式中的計(jì)算公式為3)第k步消元過(guò)程的計(jì)算公式當(dāng)做到第n-1步消元后，就完成了Guass消元過(guò)程，得到上三角方程組 二、回代過(guò)程1）在上三角方程組的最后一個(gè)方程中解出，得2）將的值代入倒數(shù)第2個(gè)方程，再解出，得3）依次回代，得計(jì)算的公式為當(dāng)時(shí)，就完成了回代過(guò)程，從而完成了Gauss消元法的全過(guò)程，得到所求解.要注意的是，計(jì)算公式中分母不能為零，于是可

12、以得到如下Gauss消元法計(jì)算公式。三、Gauss消元法計(jì)算公式1. 對(duì)，計(jì)算2.對(duì)，計(jì)算2）分析（1）Gauss消元法的計(jì)算量Gauss消元法由消元過(guò)程和回代過(guò)程兩部分組成，消元過(guò)程的計(jì)算量來(lái)自計(jì)算，所用的乘法和計(jì)算所用的除法。容易得出Gauss消元法的消元過(guò)程計(jì)算量為因此消元過(guò)程計(jì)算量為類似地可算出Gauss消元法的回代過(guò)程的計(jì)算量，于是得Gauss消元法的計(jì)算量為當(dāng)n很大時(shí)，. 由于科學(xué)計(jì)算中，變?cè)獋€(gè)數(shù)n都很大，因此也常說(shuō)Gauss消元法的計(jì)算量為.（2）Gauss消元法的矩陣解釋借助矩陣的理論，能更清楚地看到Gauss消元法的本質(zhì)，也可得出易于推廣的內(nèi)容。Gauss消元法過(guò)程實(shí)際是對(duì)的

13、增廣矩陣（A，b）做第三種行初等變換，它對(duì)應(yīng)著用第三種初等矩陣左乘要變換的增廣矩陣.Gauss消元過(guò)程的第一步消元的矩陣描述為式中與是消元后的線性方程組的系數(shù)矩陣和常數(shù)項(xiàng)。記利用矩陣運(yùn)算與相等定義，有和類似地，經(jīng)過(guò)第n-1步消元后，可以得出式中是變換后的上三角方程組的系數(shù)矩陣，若記，有和，可以證明是單位下三角矩陣，且注意到是上三角矩陣. 若令，則有（矩陣的一種分解形式）這種矩陣分解為尋找新的線性方程組解法創(chuàng)造了條件.（3）Gauss消元法可使用的條件Gauss消元法要求，什么樣的線性方程組滿足這個(gè)要求顯得很重要，下面不加證明地給出兩個(gè)結(jié)果.定理 9 的充要條件是矩陣A的所有順序主子式不為零.定

14、理10 若線性方程組的系數(shù)矩陣A的順序主子式都不為零，則可用Gauss消元法求解此方程組.（4）Gauss消元法的改進(jìn)缺點(diǎn)1：必須在都成立時(shí)才能使用，這不能令人滿意；缺點(diǎn)2：在使用Gauss消元法進(jìn)行計(jì)算機(jī)求解時(shí)，人們發(fā)現(xiàn)有時(shí)求出的解是錯(cuò)誤的.例5 設(shè)線性方程組試用Gauss消元法求解之.例6 研究下面線性方程組的Gauss消元法求解結(jié)果，假設(shè)計(jì)算在4位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上求解.通常稱消元法中用作分母的數(shù)為主元. 列主元消元法全主元消元法2. LU分解法基本思想將方程組的系數(shù)矩陣A分解為下三角矩陣L與上三角矩陣U的乘積，即，使求解的問(wèn)題變?yōu)榍蠼鈨蓚€(gè)系數(shù)矩陣為三角矩陣的和的問(wèn)題. 1) 構(gòu)造原

15、理Gauss消元法的矩陣解釋說(shuō)明矩陣A可以分解為下三角矩陣與上三角矩陣相乘的形式. 知道矩陣有這種三角分解的結(jié)構(gòu)后，我們可以利用矩陣運(yùn)算及相等的概念直接由A求出其分解矩陣L和U.具體做法為先設(shè)出L 和U的形式，再由求出L和U的元素.矩陣的三角分解有如下幾種常用形式(1) Doolittle分解分解后，L和U的結(jié)構(gòu)為，(2) Grout分解分解后，L和U的結(jié)構(gòu)為(3) LDU分解分解后，L、D和U的結(jié)構(gòu)為Doolittle分解算法構(gòu)造過(guò)程由及矩陣乘積和相等概念，有得計(jì)算公式當(dāng) 時(shí)，有從而得到矩陣U的計(jì)算公式同理有當(dāng)時(shí)，可得到矩陣L的計(jì)算公式若規(guī)定式中求和項(xiàng)在時(shí)表示不求和，則計(jì)算Doolittle分解的L和U元素的公式用后兩個(gè)表示：用算出的，回代求出的解；用算出的及，回代求出的解.用上述過(guò)程求解的方法稱為Doolittle分解方法.2) 分析(1)A可以進(jìn)行Doolittle分解的條件定理11 若非奇異矩陣A有Doolittle分解，分解具有唯一性.定理12 設(shè)，且A的各階順序主子式，則A有唯一的Doolittle分解.能進(jìn)行Gauss消元法就能做Doolittle分解.（2）Doolittle分解的緊湊格式按下圖方式存貯和計(jì)算的格式稱為Doolittle分解的緊湊格式.例7 用LU分解