1、.第五章 線性代數(shù)方程組的數(shù)值解法線性方程求解問題是科學(xué)研究和工程計(jì)算中最常見的問題。如電學(xué)中的網(wǎng)絡(luò)問題、工程力學(xué)中求解連續(xù)力學(xué)體（微分方程）問題的差分方法、有限元法、邊界元法及函數(shù)的樣條插值、最小二乘擬合等，都包含了解線性方程組問題。因此，線性方程組的解法在數(shù)值計(jì)算中占有極其重要的地位。對(duì)于階線性方程組，若，則方程組有惟一解。由克萊姆（Cramer）法則，其解為其中為用向量代替中第列向量所得矩陣。每個(gè)階行列式共有項(xiàng)，每項(xiàng)都有個(gè)因子，所以計(jì)算一個(gè)階行列式需做次乘法，我們共需要計(jì)算個(gè)行列式，要計(jì)算出，還要做次除法，因此用Cramer法則求解要做次乘除法（不計(jì)加減法），計(jì)算量十分驚人。如時(shí)，就需作

2、約次乘法?？梢奀ramer法則在理論上是絕對(duì)正確的，但當(dāng)較大時(shí)，在實(shí)際計(jì)算中卻是不可行的。因此尋求有效的數(shù)值計(jì)算方法就成為非常必要的課題。線性方程組的類型很多，若按其系數(shù)矩陣階數(shù)的高低和含零元素多少，大致可分為兩類：一類是低階稠密線性方程組，即系數(shù)矩陣階數(shù)不高（例如，），含零元素很少。另一類是高階稀疏線性方程組，即系數(shù)矩陣階數(shù)高，零元素占絕對(duì)優(yōu)勢(shì)（比如占以上）。線性方程組的數(shù)值解法也可分為兩大類：直接法和迭代法。直接法是在沒有舍入誤差的情況下，通過有限步運(yùn)算可以得到方程組精確解的方法。但是，在實(shí)際計(jì)算時(shí)，由于初始數(shù)據(jù)變?yōu)闄C(jī)器數(shù)而產(chǎn)生的誤差以及計(jì)算過程中所產(chǎn)生的舍入誤差等都要對(duì)解的精確度產(chǎn)生影響

3、，因此直接法實(shí)際上也只能算出方程真解的近似值。目前常用的有效算法是Gauss消去法和矩陣的三角分解法。迭代法是用某種極限過程去逼近準(zhǔn)確解的方法。如對(duì)任意給定的初始近似解向量，按照某種方法逐步生成近似解序列使極限為方程組的解。因?yàn)樵趯?shí)際計(jì)算時(shí)，只能做到有限步，所以得到的也是近似解。常用的迭代法主要有Jacobi迭代法、Gauss-Seidel迭代法、逐次超松弛法及共軛斜量法等。直接法的優(yōu)點(diǎn)是運(yùn)算次數(shù)固定，并且可以事先估計(jì)。它的缺點(diǎn)是通常需要存儲(chǔ)系數(shù)矩陣和常數(shù)項(xiàng)的所有元素，因而所需存貯單元較多，編寫程序較復(fù)雜，一般適用于求解低階線性方程組；迭代法的優(yōu)點(diǎn)是原始系數(shù)矩陣始終不變，且只需存儲(chǔ)原方程組系數(shù)

4、矩陣中的非零元素，因而算法簡(jiǎn)單，編寫程序較方便，且所需存貯單元也較少，所以被廣泛用于求解高階稀疏線性方程組。缺點(diǎn)是存在收斂性和收斂速度問題，因而只能對(duì)具有某些性質(zhì)的方程組才適用。§1 消元法1。1 三角方程組的解法形如 (5-1)的方程組稱為上三角形方程組。寫成矩陣形式為。若，則(5-1)有惟一解我們稱求解上三角方程組(5-1)的過程為回代過程。同時(shí)也看到求解這類方程組是件容易的事，所以對(duì)一般形式的方程組，應(yīng)設(shè)法將它化為(5-1)式的形式，然后再求解。1。2 Gauss消去法考慮方程組 (5-2)其矩陣形式為其中化線性方程組(5-2)為等價(jià)的三角形方程組的方法有多種，由此導(dǎo)出不同的直

5、接方法，其中Gauss消去法是最基本的一種方法。Gauss消去法分消元計(jì)算和回代求解兩個(gè)過程。為后面的符號(hào)統(tǒng)一起見，記方程組(5-2)為其中。消元計(jì)算第一步：就是要將的第一列主對(duì)角元以下的元素全約化為0。設(shè)，計(jì)算用乘(5-2)的第1個(gè)方程，加到第個(gè)方程上，完成第一步消元，得(5-2)的同解方程組 (5-3)簡(jiǎn)記為，其中的元素的計(jì)算公式為假設(shè)前步消元完成后，得(5-2)的同解方程組為 (5-4)簡(jiǎn)記為。第步：就是要將的第列主對(duì)角元以下的元素全約化為0。設(shè)，計(jì)算用乘(5-4)的第個(gè)方程加到第個(gè)方程上，完成第步消元。得同解方程組其中元素的計(jì)算公式為完成步消元后，(5-2)化成同解的上三角方程組 (5

6、-5)簡(jiǎn)記為回代求解因，故，于是 (5-6)Gauss消去步驟能順利進(jìn)行的條件是，現(xiàn)在的問題是矩陣應(yīng)具有什么性質(zhì)，才能保證此條件成立。若用表示的順序主子式，即有下面定理定理1 約化的主元素的充要條件是矩陣的順序主子式。證明 必要性。因主元素，可進(jìn)行步消元，每步消元過程不改變順序主子式的值，于是必要性得證。用歸納法證明充分性。時(shí)命題顯然成立。假設(shè)命題對(duì)成立。設(shè)。由歸納法假設(shè)有，Gauss消去法可以進(jìn)行步，約化為其中是對(duì)角元為的上三角陣。因是通過步消去法得到的，每步消元過程不改變順序主子式的值，所以的階順序主子式等于的，即由知，充分性得證。1。3 Gauss消去法的計(jì)算量1）消元過程的工作量第步消

7、元過程：計(jì)算乘子需作次除法運(yùn)算；第行乘加到第行，需要乘法和減法各次（第列元素?zé)o需計(jì)算），共行（），所以需要乘法次，故消元過程中的乘、除和減法運(yùn)算量為乘除法次數(shù)：加減法次數(shù)：2）回代過程的工作量計(jì)算需要次乘除法和次加減法運(yùn)算，整個(gè)回代過程的運(yùn)算量為：乘除法：減法：所以Gauss 消去法的總運(yùn)算量為乘除法：（當(dāng)較大時(shí)）加減法：（當(dāng)較大時(shí)）當(dāng)時(shí)，用Gauss消去法約需430次乘除法運(yùn)算，而用Gramer法則約需次乘除法。1。4 Gauss消去法的矩陣形式如果用矩陣形式表示，Gauss消去法的消元過程是對(duì)方程組(5-2)的增廣矩陣進(jìn)行一系列初等變換，將系數(shù)矩陣化成上三角形矩陣的過程，也等價(jià)于用一串初等

8、矩陣去左乘增廣矩陣，因此消元過程可以通過矩陣運(yùn)算來表示。第一次消元等價(jià)于用初等矩陣左乘矩陣，其中，即一般地，第次消元等價(jià)于用初等矩陣左乘矩陣，其中，經(jīng)過次消元后得到即將上三角矩陣記為，得到其中為單位下三角陣。這說明，消元過程實(shí)際上是把系數(shù)矩陣分解為單位下三角陣與上三角矩陣的乘積的過程。這種分解稱為杜利特爾（Doolittle）分解，也稱為分解。定理2 設(shè)為階方陣，如果的順序主子式，則存在惟一的單位下三角陣和上三角陣，使。證明 以上的分析已證明了可作分解。下面證明分解的惟一性。如果非奇異，設(shè)有兩個(gè)分解式其中都是單位下三角陣，都是上三角陣。因非奇異，所以都可逆。于是上式左邊為單位下三角陣，右邊為上

9、三角陣，所以即有，惟一性得證。若為奇異陣，因其階順序主子式不等于零，故可記其中均為階方陣，且非奇異。由，得由已證明的結(jié)果知的分解是惟一。所以亦是惟一確定的。進(jìn)而，也是惟一確定的。定畢。定理2的逆命題是定理3 設(shè)階方陣非奇異，若有惟一的分解（其中為單位下三角陣，為上三角陣），試證的順序主子式。（證明留給讀者）§2 主元素法前面已指出Gauss消去法必須在各個(gè)約化主元素下才能進(jìn)行?，F(xiàn)在還需指出的是：即使，但當(dāng)很小時(shí)，也不能做主元素的，因?yàn)樽鞯诖蜗獣r(shí)，需將第個(gè)方程乘以，因此當(dāng)很小時(shí)，乘數(shù)很大，用去乘第行的元素，將導(dǎo)致的數(shù)量級(jí)迅速增長(zhǎng)，這樣在消元計(jì)算 時(shí)，會(huì)出現(xiàn)大數(shù)吃掉小數(shù)的現(xiàn)象，因而導(dǎo)致

10、最后計(jì)算結(jié)果的精度很差甚至失真。例1 解方程組(1) 求精確解；(2) 在的浮點(diǎn)機(jī)上用Gauss消去法求解。解 (1) 容易求得方程組的精確解為。(2) 在所給浮點(diǎn)機(jī)上原方程組為由于消去第二式的，得對(duì)階，出現(xiàn)大數(shù)“吃掉”小數(shù)，結(jié)果有解得，回代第一式得。與精確解相比較，已無精確度可言。產(chǎn)生不準(zhǔn)確的原因是主元素太小，致使很大。改變上述狀況的辦法是將方程組的一、二兩式對(duì)換，得然后再使用Gauss消去法，此時(shí)于是得近似解。此例表明，高斯消去法解方程組時(shí)，小主元可能帶來嚴(yán)重的后果，因此應(yīng)盡量避免小主元的出現(xiàn)；另一方面，通過對(duì)換方程組中方程的次序或改動(dòng)變量次序，選擇絕對(duì)值大的元素做主元，可減少舍入誤差，提

11、高計(jì)算精度。1 列主元與全主元消去法1列主元素消去法。在第步消元時(shí)，在的第列元素中選取絕對(duì)值最大者作為主元，并將其對(duì)換到位置上，然后再進(jìn)行消元計(jì)算。用方程組(5-2)的增廣矩陣 (5-7)表示它，并直接在增廣矩陣上進(jìn)行計(jì)算。具體步驟如下：第一步：首先在上述矩陣的第一列中選取絕對(duì)值最大的，比如，則。將(5-7)中第一行與第行互換。為方便起見，記行互換后的增廣矩陣為，然后進(jìn)行第一次消元，得矩陣假設(shè)已完成步的主元素消去法，約化為第步：在矩陣的第列中選主元，如，使。將的第行與第行互換，進(jìn)行第次消元。經(jīng)過步，增廣矩陣(5-7)被化成上三角形算法1（Gauss列主元素消去法）說明：消元結(jié)果沖掉，行乘數(shù)沖掉

12、，det存放行列式值。輸入，置，1。 消元過程對(duì)(1) 選主元：(a) 按列選主元，即確定，使(b) 若，停機(jī)；(c) 若（進(jìn)行行交換）(2) 對(duì)（）對(duì)(3) 回代過程(a) 若，輸出失敗信息，停機(jī)(b) (c) 對(duì)注：計(jì)算程序中對(duì)的判斷可以用或（是預(yù)選的很小正數(shù)）。2完全主元素法。在第步消元時(shí)，在的右下方階矩陣的所有元素中，選取絕對(duì)值最大者作為主元，并將其對(duì)換到位置上，再做消元計(jì)算。全主元消去法和列主元消去法相比，每步消元過程所選主元的范圍更大，故它對(duì)控制舍入誤差更有效，求解結(jié)果更加可靠。但全主元法在計(jì)算過程中，需同時(shí)作行與列的互換，因而程序比較復(fù)雜，計(jì)算時(shí)間較長(zhǎng)。列主元法的精度雖稍低于全主

13、元法，但其計(jì)算簡(jiǎn)單，工作量大為減少，且計(jì)算經(jīng)驗(yàn)與理論分析均表明，它與全主元法同樣具有良好的數(shù)值穩(wěn)定性，故列主元法是求解中小型稠密線性方程組的最好方法之一。2 列主元消去法的矩陣形式第步消元時(shí)，需先交換的第行與第行，然后再做消元計(jì)算，相當(dāng)于對(duì)進(jìn)行如下的矩陣計(jì)算：(1) 用初等排列矩陣左乘，即其中由交換單位矩陣的第與兩行所得。顯然。(2) 用初等排列矩陣左乘，即于是對(duì)施行帶行交換的步消元過程，可用矩陣表示為從而有因?yàn)椋陨鲜娇筛膶憺榭梢宰C明，若是指標(biāo)為的單位下三角陣，則仍是一個(gè)指標(biāo)為的單位下三角陣。若令則是排列陣。又設(shè)于是即注意到仍為單位下三角陣，若令則有上式表明，帶行交換的Gauss消去過程所

14、產(chǎn)生的矩陣分解，相當(dāng)于對(duì)系數(shù)矩陣先施行每步消元時(shí)所做行交換后，再將所得矩陣進(jìn)行分解。以上討論可敘述為定理4（列主元三角分解定理）如果為非奇異矩陣，則存在排列矩陣，使其中為單位下三角矩陣，為上三角矩陣。3 Gauss-Jordan消去法高斯消去法始終是消去對(duì)角線下方的元素，現(xiàn)考慮高斯消去法的一種修正，即消去對(duì)角線下方和上方的元素，這種方法稱為Gauss-Jordan消去法。設(shè)用高斯-若當(dāng)消去法已完成步，于是化為等價(jià)方程組，其中在第步計(jì)算時(shí)，考慮對(duì)上述矩陣的第行上、下都進(jìn)行消元計(jì)算。1。 按列選主元元素，即確定使換行（時(shí)）交換第行與第行元素3。 計(jì)算乘數(shù)（，且），（可保存在存放的單元中）。4。 消

15、元計(jì)算（，且，）（，且）計(jì)算主元（）經(jīng)過步消元后，可得說明用高斯-若當(dāng)方法將約化為單位矩陣，常數(shù)項(xiàng)位置就是計(jì)算解，無需回代過程。用高斯-若當(dāng)方法解方程組計(jì)算量大約需要次乘除法，要比高斯消去法大，但用高斯-若當(dāng)方法求一個(gè)矩陣的逆矩陣還是比較合適的。定理2（高斯-若當(dāng)法求逆矩陣）設(shè)為非奇異矩陣，方程組的增廣矩陣為。如果對(duì)應(yīng)用高斯-若當(dāng)方法化為，則。事實(shí)上，為非奇異矩陣，若我們已通過左乘一系列初等矩陣把它化成了一個(gè)單位矩陣，即則說明用同樣的初等陣左乘單位矩陣，即得到的逆矩陣。§3 直接三角分解法3。1 不選主元的直接三角分解法設(shè)為如下形式由矩陣的乘法規(guī)則，得由此可得計(jì)算和的公式 (5-8)

16、具體步驟如下：1 計(jì)算的第1行，的第1列2 計(jì)算的第行，的第列例2 求矩陣的三角分解。解 按式(5-8)所以緊湊格式：例2中矩陣的三角分解按緊湊格式計(jì)算，結(jié)果見下表如果線性方程組的系數(shù)矩陣已進(jìn)行三角分解，則解方程組等價(jià)于求解兩個(gè)三角形方程組。第一步：先求解下三角方程組得解第二步：再求解上三角方程組得解3。2選主元的直角三角分解法不選主元的直接三角分解過程能進(jìn)行到底的條件是，實(shí)際上，即使非奇異，也可能出現(xiàn)某個(gè)的情況，這時(shí)分解過程將無法進(jìn)行下去。另外，如果但很小，會(huì)使計(jì)算過程中的舍入誤差急劇增大，導(dǎo)致解的精度很差。但如果非奇異，我們可通過交換的行實(shí)現(xiàn)矩陣的分解，實(shí)際上是采用與列主元消去法等價(jià)的選主

17、元的三角分解法，即只要在直接三角分解法的每一步引進(jìn)選主元的技術(shù)即可。設(shè)步分解已經(jīng)完成，這時(shí)有考慮步分解，對(duì)于做到(4)(1) 計(jì)算輔助量，沖掉(2) 選主元。即確定行號(hào)，使，并記錄主行號(hào)：（為一維數(shù)組）(3) 交換的行與行元素(4) 計(jì)算的行與的第列元素（這里）上述計(jì)算過程完成后，就實(shí)現(xiàn)了的分解，保存在的上三角部分，保存在的嚴(yán)格下三角部分，排列陣由的最后記錄可得。例如，設(shè)，則于是方程組的求解等價(jià)于解，即，可通過及完成。例3 用選主元的直接三角分解法解方程組，其中，解(1) 對(duì)作選主元的分解，中間結(jié)果沖掉相應(yīng)位置元素，數(shù)組記錄主行號(hào)。第一步分解：，因?yàn)?，于是有第二步分解：，因?yàn)?，故有于是由選主元

18、過程，。，(2) 解，得；解，得3。3 解三對(duì)角方程組的追趕法在數(shù)值計(jì)算中，如三次樣條插值或用差分方法解常微分方程邊值問題，常常會(huì)遇到求解以下形式的方程組其中，系數(shù)矩陣 (5-9)是一種特殊的稀疏矩陣，它的非零元素集中分布在主對(duì)角線及其相鄰兩條次對(duì)角線上，稱為三對(duì)角矩陣。方程組稱為三對(duì)角方程組。Gauss消去法用于三對(duì)角方程組時(shí)過程可以大大簡(jiǎn)化。由于第次消元時(shí)，只需消去，所以消元過程就是用單位下二對(duì)角矩陣左乘矩陣。由于每個(gè)以上的列元素為零，不難看出具有形式定理5 設(shè)矩陣(5-9)滿足下列條件 (5-10)則它可分解為 (5-11)其中為矩陣(5-9)中所給出，且分解是惟一的。證明 將式(5-1

19、1)右端按乘法法則展開，并與的元素進(jìn)行比較，得如果，那么我們可計(jì)算，即 (5-12)從以上的公式和消元過程我們可看出，要使得分解得以實(shí)施，必須滿足現(xiàn)在我們用歸納法證明：。當(dāng)時(shí)，顯然成立。假定成立，即，我們將證明時(shí)也成立。有當(dāng)矩陣(5-9)按式(5-12)計(jì)算進(jìn)行分解后，求解方程組可化為求解方程組及。解得 (5-13)再解，得 (5-14)按上述過程求解三對(duì)角方程組成為追趕法。式(5-12)，(5-13)結(jié)合稱為“追”的過程，相當(dāng)于Gauss消去法中的消元過程。式(5-14)稱為“趕”的過程，相當(dāng)于回代過程。算法21）輸入2）對(duì) 3）4）對(duì) 5）輸出，停機(jī)。追趕法的基本思想與Gauss消去法及三

20、角分解法相同，只是由于系數(shù)中出現(xiàn)了大量的零，計(jì)算中可將它們撇開，從而使得計(jì)算公式簡(jiǎn)化，也大大地減少了計(jì)算量。為節(jié)省計(jì)算機(jī)存貯單元，計(jì)算得到的分別存放在的存貯單元內(nèi)，而存放在的存貯單元內(nèi)。可以證明，當(dāng)系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)時(shí)，此方法具有良好的數(shù)值穩(wěn)定性。§4 平方根法與改進(jìn)的平方根法工程技術(shù)中的許多實(shí)際問題所歸結(jié)的線性方程組，其系數(shù)矩陣常具有對(duì)稱正定性，對(duì)于具有此類特性的系數(shù)矩陣，利用矩陣的三角分解法求解是一種較好的有效方法，這就是對(duì)稱正定矩陣方程組的平方根法及改進(jìn)的平方根法，這種方法目前在計(jì)算機(jī)上已被廣泛應(yīng)用。4。1平方根法（Cholesky分解法）定理6（對(duì)稱陣的三角分解定理）設(shè)是

21、對(duì)稱陣，且的所有順序主子式均不為零，則存在惟一的單位下三角陣和對(duì)角陣，使 (5-15)證明 因?yàn)榈母麟A順序主子不為零，由定理2，存在惟一的Doolittle分解其中為單位下三角矩陣，為上三角矩陣。令，將再分解為其中為單位上三角矩陣。于是又由分解的惟一性即得，式(5-15)得證。定理7（對(duì)稱正定陣的Cholesky分解）設(shè)是對(duì)稱正定矩陣，則存在惟一的對(duì)角元素為正的下三角陣，使 (5-16)證明 因?yàn)閷?duì)稱性，由定理6知，其中為單位下三角陣，。若令，則為的Doolittle分解，的對(duì)角元即的對(duì)角元。不難驗(yàn)證，的 ()階順序主子式為對(duì)應(yīng)的與的階順序主子陣的乘積，因此的順序主子式。因?yàn)檎?，有，由此可?/p>

22、出。記則有其中，它為對(duì)角元為正的下三角陣，所以(5-16)成立。由分解的惟一性，可得分解(5-16)的惟一性。證畢。分解式稱為正定矩陣的喬列斯基（Cholesky）分解。利用Cholesky分解來求系數(shù)矩陣為對(duì)稱正定矩陣的方程組的方法稱為平方根法。用比較法可以導(dǎo)出的計(jì)算公式。設(shè)比較與的對(duì)應(yīng)元素，可得 (5-17)這里規(guī)定。計(jì)算順序是按列進(jìn)行的，即。當(dāng)矩陣完成Cholesky分解后，求解方程組就轉(zhuǎn)化為依次求解方程組它們的解分別為 (5-18)當(dāng)?shù)脑厍蟪龊?，的元素也就求出，所以平方根法約需次乘除法，大約為一般分解法計(jì)算量的一半。同時(shí)還節(jié)省存貯，只需存系數(shù)矩陣的下三角部分和右端項(xiàng)，中間結(jié)果沖掉，計(jì)

23、算解沖掉。此外，由式(5-17)的第一式得所以上式表明，在矩陣的喬列斯基分解過程中的平方不會(huì)超過的最大對(duì)角元，舍入誤差的放大受到了控制，且對(duì)角元素恒為正數(shù)，于是不選主元素的平方根法是數(shù)值穩(wěn)定的，計(jì)算實(shí)踐也表明了不選主元已有足夠的精度，所以平方根法是目前計(jì)算機(jī)上解決這類問題的最有效的方法之一。4。2改進(jìn)的平方根法（法）利用平方根法解對(duì)稱正定線性方程組時(shí)，計(jì)算矩陣的元素時(shí)需要用到開方運(yùn)算。另外，當(dāng)我們解決工程問題時(shí)，有時(shí)得到的是一個(gè)系數(shù)矩陣為對(duì)稱但不一定是正定的線性方程組，為了避免開方運(yùn)算和求解對(duì)稱（未必正定）方程組，我們可以引入下面改進(jìn)平方根法。由定理6我們知道，為對(duì)稱矩陣時(shí)，它可分解成其中為單

24、位下三角矩陣，為對(duì)角矩陣。記，由矩陣乘法運(yùn)算，并注意到，得于是導(dǎo)出分解的計(jì)算公式：對(duì) (5-19)計(jì)算順序?yàn)椋?。按?5-19)進(jìn)行分解，雖然避免了開方運(yùn)算，但在計(jì)算每個(gè)元時(shí)多了相乘的因子，故乘法運(yùn)算次數(shù)比Cholesky分解約增多一倍，乘法總運(yùn)算量又變成數(shù)量級(jí)。仔細(xì)分析式(5-19)可以看出，式中有許多計(jì)算是重復(fù)的，如為此我們將引進(jìn)輔助量，于是式(5-19)可改寫成 (5-20)具體計(jì)算過程是：對(duì)矩陣作分解后，解方程組可分兩步進(jìn)行：首先解方程組，再由求出。具體公式為 (5-21)例4 用改進(jìn)平方根法求解方程組解 容易驗(yàn)證，系數(shù)矩陣為對(duì)稱正定陣。按式(5-20)計(jì)算分解式，得按式(5-21)計(jì)

25、算方程組的解，得所以方程組的解為。5 向量和矩陣的范數(shù)為了研究線性代數(shù)方程組近似解的誤差估計(jì)和迭代法的收斂性，我們需要引入衡量向量和矩陣“大小”的度量概念向量和矩陣的范數(shù)概念。1 向量范數(shù)定義1 設(shè)對(duì)任意向量，按一定的規(guī)則有一實(shí)數(shù)與之對(duì)應(yīng)，記為，若滿足正定性：，而且當(dāng)且僅當(dāng)；齊次性：對(duì)任意實(shí)數(shù)，都有；三角不等式：對(duì)任意，都有則稱為向量的范數(shù)。以上三個(gè)條件刻劃了“長(zhǎng)度”、“大小”及“距離”的本質(zhì)，因此稱為范數(shù)公理。對(duì)上的任一種范數(shù)，顯然有。向量空間上可以定義多種范數(shù)，常用的幾種范數(shù)：1）向量的1-范數(shù)：；2）向量的5-范數(shù)：；3）向量的-范數(shù)：；4）更一般的-范數(shù)：。容易證明，及確實(shí)滿足向量范數(shù)

26、的三個(gè)條件，因此它們都是上的向量范數(shù)。此外，前三種范數(shù)是-范數(shù)的特殊情況（）。事實(shí)上，我們只需表明3）。事實(shí)上，由于及，故由數(shù)學(xué)分析的夾逼定理有。定理8 設(shè)給定，則對(duì)上每一種向量范數(shù)都是的元連續(xù)函數(shù)。證明 對(duì)于給定的，設(shè)為的列向量，將寫成分塊形式對(duì)，由三角不等式有其中，所以對(duì)任意的，當(dāng)時(shí)，有這就證明了的連續(xù)性。推論 是的元連續(xù)函數(shù)。下面討論范數(shù)的等價(jià)性問題定義2線性空間上定義了兩種范數(shù)和，如果存在常數(shù)，使 (5-22)則稱和是上等價(jià)的范數(shù)。顯然，范數(shù)的等價(jià)性具有傳遞性，即若與等價(jià)，與等價(jià)，則有與。定理9 上所有范數(shù)是彼此等價(jià)的。證明 只要證明上任一種范數(shù)都與等價(jià)。設(shè)是上定義的任一范數(shù)，記它是上

27、的有界閉集。由定理8的推論，是上的元連續(xù)函數(shù)，故在上有最大值和最小值，且?，F(xiàn)在考慮，且，則有，所以有從而而當(dāng)時(shí)上式自然成立，這就證明了與的等價(jià)性。2 矩陣的范數(shù)這里主要討論中的范數(shù)及其性質(zhì)（的可類似討論），其范數(shù)要符合一般線性空間范數(shù)的定義1，為了考慮矩陣乘法運(yùn)算的性質(zhì)，我們?cè)诰仃嚪稊?shù)的條件中多加一個(gè)條件。定義3 如果對(duì)上任一矩陣，按一定的規(guī)則有一實(shí)數(shù)與之對(duì)應(yīng)，記為。若滿足 ，且當(dāng)且僅當(dāng)； 對(duì)任意實(shí)數(shù)，都有； 對(duì)任意的兩個(gè)階方陣，都有； （相容性條件）。則稱為矩陣的范數(shù)。這里與向量范數(shù)是一致的，條件則使矩陣范數(shù)在數(shù)值計(jì)算中使用更為方便。例5（矩陣的Frobenius范數(shù)）證明滿足矩陣范數(shù)定義3

28、。它可以看成維向量的5-范數(shù)，所以滿足定義3的前三個(gè)條件，可驗(yàn)證條件也成立。記，利用矩陣的乘積及Cauchy不等式有即得證。由于在實(shí)際中，經(jīng)常用到矩陣與向量的乘積運(yùn)算，為了估計(jì)矩陣與向量相乘積的范數(shù)，那么在矩陣范數(shù)與向量范數(shù)之間具有某種協(xié)調(diào)關(guān)系是有好處的。為此，我們先引入相容性的概念，再由一種向量范數(shù)導(dǎo)出對(duì)應(yīng)的矩陣范數(shù)。定義4 對(duì)于給定的上一種向量范數(shù)和上一種矩陣范數(shù)，若有 (5-23)則稱上述矩陣范數(shù)與向量范數(shù)相容。不難驗(yàn)證如下不等式：對(duì)于上的一種向量范數(shù)，對(duì)任一，對(duì)應(yīng)一個(gè)實(shí)數(shù)，下面我們定理表明它定義了上的一種矩陣范數(shù)。不難驗(yàn)證它有等價(jià)的形式 (5-24)定理10 設(shè)是上任一種向量范數(shù)，則對(duì)

29、一切，由式(5-23)確定的實(shí)數(shù)定義了上的一種范數(shù)，把它記為，且有 (5-25)證明 首先證明(5-23)中的可以寫成。因?yàn)橛啥ɡ?，是中有界閉集上的連續(xù)函數(shù)，故在上有最大值，即存在，使，所以式(5-24)中的上確界就是最大值。記為，有式(5-25)，并且由此可以得到 (5-26)余下將驗(yàn)證以上確定的滿足范數(shù)定義3。條件，是明顯的。對(duì)任意，有即得證，同理可證。定義5 對(duì)于上任意一種向量范數(shù)，由(5-25)所確定的矩陣范數(shù)，稱為從屬于給定向量范數(shù)的矩陣范數(shù)，簡(jiǎn)稱從屬范數(shù)（也稱由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)，自然范數(shù)或算子范數(shù)）。顯然，單位矩陣的任一種從屬范數(shù)。所以當(dāng)時(shí)，不是從屬范數(shù)。顯然從屬范數(shù)與所

30、給定的向量范數(shù)相容，但是矩陣范數(shù)與向量范數(shù)相容，卻未必有從屬關(guān)系。例如可以證明與相容，即但不從屬于。我們把從屬于向量-范數(shù)、1-范數(shù)及5-范數(shù)誘導(dǎo)的矩陣范數(shù)，并分別稱為矩陣的-范數(shù)、1-范數(shù)及5-范數(shù)。定理11 設(shè)，則1（稱為的行范數(shù)）2（稱為的列范數(shù)）3（稱為的5-范數(shù)）其中是矩陣的最大特征值。證明 只就1，3給出證明，2同理。設(shè)，則所以有另一方面，設(shè)整數(shù)滿足令，其中顯然有，而且3對(duì)任意，從而為非負(fù)定的對(duì)稱陣，其特征值為非負(fù)實(shí)數(shù)，依次排列為，對(duì)應(yīng)一組規(guī)范正交的特征向量，對(duì)任意的，可表示為如果，則有，特別地，取，上式等號(hào)成立，故。定義6 設(shè)的特征值為，稱為的譜半徑。引理1 設(shè)為上任一種向量范數(shù)

31、，從屬于它的矩陣范數(shù)記為，為非奇異階方陣，證明(1) 定義了上一種范數(shù)。(2) 從屬于的矩陣范數(shù)，記為，有（證明留給讀者）定理12 (1)設(shè)為上任一種（從屬或非從屬）矩陣范數(shù)，則對(duì)任意的，有 (5-27)(2)對(duì)任意的及實(shí)數(shù)，至少存在一種從屬范數(shù)，使 (5-28)證明 (1)設(shè)滿足，且。必存在向量，使不是零矩陣。對(duì)于任意一種矩陣范數(shù)，由矩陣范數(shù)定義可得即可推出(5-27)。(2) 對(duì)任意的，總存在非奇異的，使為Jordan標(biāo)準(zhǔn)形，即是對(duì)角塊形式的矩陣，其中的Jordan塊為對(duì)于實(shí)數(shù)，定義對(duì)角陣容易驗(yàn)證仍為塊對(duì)角形式，其分塊與J相同，即其中它的階數(shù)與相同。取的范數(shù)，可得而為非奇異陣，由引理1知，

32、定義了上一種向量范數(shù)，從屬于此向量范數(shù)的矩陣范數(shù)為定理13 設(shè)是上一種從屬范數(shù)，矩陣，滿足，則為非奇異矩陣，且 (5-29)證明 若奇異，存在非零向量，使，所以有一個(gè)特征值1，故有。根據(jù)定理12，有，這和定理假設(shè)條件矛盾，所以非奇異。記，則于是。同理可證的情形。6 誤差分析6。1 方程組的性態(tài)與條件數(shù)在用數(shù)值計(jì)算方法解線性方程組時(shí)，計(jì)算結(jié)果有時(shí)不準(zhǔn)確，這可能有兩種原因：第一是計(jì)算方法不合理；另外一種情況可能是線性方程組本身的問題。判斷一個(gè)計(jì)算方法的好壞，可用方法是否穩(wěn)定、解的精確度高低以及計(jì)算量、存貯量大小等來衡量。然而，對(duì)于不同的問題，同一方法卻可以產(chǎn)生完全不同的效果，這就涉及所提問題的性態(tài)

33、，即“好、壞”。例6 容易看出，方程組的解為。而方程組的解為。比較這兩個(gè)方程組可以看出，只是右端項(xiàng)有微小的差別，最大相對(duì)誤差為，竟使解的結(jié)果面目全非。如果我們把第二個(gè)方程組看作是第一個(gè)方程組的常數(shù)項(xiàng)經(jīng)微小擾動(dòng)得到的，所以也可稱第二個(gè)是第一個(gè)的擾動(dòng)方程組。可見方程組的解對(duì)方程組的初始數(shù)據(jù)的擾動(dòng)十分敏感，這種性質(zhì)與求解方法無關(guān)，是方程組本身固有的性質(zhì)，即方程組的性態(tài)決定的。定義7 如果矩陣或常數(shù)項(xiàng)的微小變化，引起方程組解的巨大變化，則稱此方程組為“病態(tài)”方程組，矩陣稱為“病態(tài)”矩陣（相對(duì)于方程組而言），否則稱方程組為“良態(tài)”方程組，稱為“良態(tài)”矩陣。一般地說，在計(jì)算機(jī)上解方程組，實(shí)際上都是解所給方

34、程的擾動(dòng)方程，因?yàn)橹辽僭趯?duì)輸入的數(shù)據(jù)作十進(jìn)制與二進(jìn)制轉(zhuǎn)換時(shí)就要產(chǎn)生舍入誤差。對(duì)于良態(tài)問題，由于它的解與其擾動(dòng)方程的解差別不大，所以只要算法是數(shù)值穩(wěn)定的，就可以得到較好的結(jié)果，而對(duì)于病態(tài)問題，即使算法是穩(wěn)定的，其計(jì)算結(jié)果依然會(huì)很壞。以下我們研究方程組的系數(shù)矩陣和向量的微小誤差（擾動(dòng)）對(duì)解的影響。設(shè)為任何一種向量范數(shù)，矩陣范數(shù)是從屬范數(shù)。設(shè)為非奇異且有微小擾動(dòng)，有微小擾動(dòng)，則的擾動(dòng)方程為 (5-30)由，得由于非奇異，所以矩陣存在，因此為了估計(jì)，對(duì)上式兩端取范數(shù)，則有移項(xiàng)得假定足夠下，使得，則相對(duì)誤差為利用，得到 (5-31)式(5-31)表示了解的相對(duì)誤差與系數(shù)矩陣的相對(duì)誤差與右端向量的相對(duì)誤差

35、之間的關(guān)系。由此得到：定理14 設(shè)是非奇異陣，。若系數(shù)矩陣及右端項(xiàng)分別有微小誤差及，引起解的誤差，當(dāng)時(shí)，它們的相對(duì)誤差間有如下關(guān)系推論1 若，則 (5-32)推論2 若，且充分小，則 (5-33)事實(shí)上，記，對(duì)于給定的，為確定的數(shù)，擾動(dòng)充分小，可使，于是，所以(5-31)可以寫成不等式(5-31)、(5-32)及(5-33)式給出的都是解的相對(duì)誤差的上界。推論1、推論2分別指出了當(dāng)只有或的誤差時(shí)，解的相對(duì)誤差都不超過它們的相對(duì)誤差的倍數(shù)?？虅澚司€性方程組的解對(duì)初始數(shù)據(jù)誤差的敏感度，此數(shù)越大則在很小的或下可能使解的相對(duì)誤差很大，從而大大破壞了解的準(zhǔn)確性，而且是方程組本身一個(gè)固有的屬性，它與如何求

36、解方程組的方法無關(guān)。因此可以用它來表示方程組的性態(tài)。定義8 設(shè)是非奇異陣，稱數(shù)為矩陣的條件數(shù)，用表示，即矩陣條件數(shù)與范數(shù)有關(guān)，通常使用的條件數(shù)有：(1) ；(2) 的譜條件數(shù)當(dāng)是對(duì)稱矩陣時(shí)其中與為的絕對(duì)值最大和最小的特征值下面定理給出條件數(shù)的一些性質(zhì)，證明留給讀者。定理15 設(shè)，非奇異，則有（1），。（2）為正交陣，則；若為正交陣，則（3）設(shè)與為按絕對(duì)值最大和最小的特征值，則若對(duì)稱，則。定理15表明，矩陣的條件數(shù)不小于1，當(dāng)條件數(shù)接近1時(shí)，矩陣稱為“良態(tài)”的；當(dāng)條件數(shù)比1大得多，矩陣是“病態(tài)”的。正交矩陣是最穩(wěn)定的一類矩陣。例7 計(jì)算例6方程組系數(shù)矩陣的條件數(shù)。解 系數(shù)矩陣為其逆矩陣為于是有條

37、件數(shù)很大，所以方程組是“病態(tài)”的。例8 已知希爾伯特（Hilbert）矩陣計(jì)算的條件數(shù)。解 的逆矩陣的元素是所以（1）計(jì)算條件數(shù)，所以。同樣，可計(jì)算，。當(dāng)愈大時(shí)，病態(tài)愈嚴(yán)重。（2）考慮方程組的擾動(dòng)方程（及的元素取3位有效數(shù)字）有簡(jiǎn)記為。方程與它的擾動(dòng)方程的解分別為：，。于是，而，有，所以，這表明與的相對(duì)誤差不超過，而引起解的相對(duì)誤差超過50%。Turing在1948年第一個(gè)使用了“條件數(shù)”這一術(shù)語，接著不少數(shù)學(xué)工作者相繼提出用“矩陣條件數(shù)”來度量方程組求解等問題的病態(tài)程度，但是矩陣條件數(shù)大到怎樣才算大，并沒有一個(gè)客觀的衡量標(biāo)準(zhǔn)。另外，當(dāng)較大時(shí)， 的計(jì)算也并非易事。在實(shí)際計(jì)算中，如果遇到下列幾種

38、情況，就應(yīng)當(dāng)考慮方程組可能是病態(tài)的。(1) 用主元素消去法解方程組時(shí)，出現(xiàn)小主元；(2) 系數(shù)矩陣某兩行（列）幾乎線性相關(guān)；(3) 系數(shù)矩陣的元素間數(shù)量級(jí)相差很大，且無規(guī)律；(4) 近似解向量已使剩余向量的范數(shù)很小，但解仍不符合客觀規(guī)律。在求得方程組的一個(gè)近似解后，檢驗(yàn)精度的一個(gè)簡(jiǎn)單方法是將代入方程組求得殘量（余量）。如果很小，就認(rèn)為解比較準(zhǔn)確。但對(duì)“病態(tài)”嚴(yán)重的方程組，可能即使殘量很小，近似解與準(zhǔn)確解的差仍很大。如例6中，方程組的準(zhǔn)確解為。若以作為它的近似解，其殘量很小，但解的誤差卻不小。事實(shí)上，由和得于是可推出上式說明，盡管已很小，如果很大，近似解得相對(duì)誤差也會(huì)很大，所以方程組還是病態(tài)的。

39、6.2 病態(tài)方程組的解法病態(tài)方程組的求解問題是計(jì)算方法的一個(gè)重要的課題。在這里我們僅就不是過分病態(tài)的方程組，討論改善解的精度，有如下幾種方法：（1）采用高精度的算術(shù)運(yùn)算（如采用雙倍字長(zhǎng)進(jìn)行運(yùn)算），以便改善和減輕病態(tài)矩陣的影響；（2）當(dāng)方程組的系數(shù)矩陣元素的數(shù)量級(jí)相差懸殊時(shí)，計(jì)算經(jīng)驗(yàn)表明，即使使用主元素消去法，求解過程中有效數(shù)字也會(huì)嚴(yán)重?fù)p失，影響解的精度。為避免這一現(xiàn)象發(fā)生，可將系數(shù)矩陣元素的數(shù)量級(jí)大體均衡一下，比如先用系數(shù)矩陣每行元素的最大模除遍行或列各元素，稱為行或列標(biāo)度化過程，然后施行主元素消去法。適當(dāng)選擇非奇異對(duì)角陣，使求解的問題轉(zhuǎn)化為求解等價(jià)方程組其中的條件數(shù)得到改善。記。多數(shù)場(chǎng)合，選

40、擇的原則是使的元素滿足和常常，為了簡(jiǎn)單，只對(duì)方程組進(jìn)行行標(biāo)度化，即只選擇。例9 設(shè)簡(jiǎn)記為，計(jì)算。解 ，有當(dāng)用列主元消去法求解時(shí)（計(jì)算到三位有效數(shù)字）于是得到很壞的結(jié)果：。取，考察等價(jià)方程組的系數(shù)矩陣的條件數(shù)。則，大大改善了系數(shù)矩陣的條件數(shù)。再用列主元消去法求解，得到從而得到較好的計(jì)算解：。以上對(duì)方程組的系數(shù)矩陣進(jìn)行預(yù)處理的過程，稱為顯式標(biāo)度化方法。它在計(jì)算時(shí)，會(huì)引進(jìn)新的誤差，實(shí)踐中使用如下的隱式標(biāo)度化法比較普遍。隱式法與顯式法的不同之處在于它不算出，列主元素消去法在本質(zhì)上依舊對(duì)，而不是，只不過在第高斯消去法時(shí)，用選擇列主元。例10 解方程組用舍入的三位浮點(diǎn)數(shù)計(jì)算。解 方程組的系數(shù)矩陣元素之間的

41、數(shù)量級(jí)相差很大，我們將用隱式標(biāo)度化法求解。方程組的增廣矩陣為1消元計(jì)算(1) 計(jì)算(2) 按列選主元，即確定，使于是，即應(yīng)為主元素，所以對(duì)換的兩行：(3) 消元計(jì)算：2回代求解通過此例看到，標(biāo)度化的目的是找到真正的主元，它只影響主元素的選取。本例的準(zhǔn)確解是。(3) 迭代改善法。設(shè)有方程組，其中為非奇異矩陣，且若用Gauss消去法（或直接三角分解法或）求得計(jì)算解（精度不高），為獲得方程組高精度的解，一般可采用下述方法改善解的精度。(1) 計(jì)算剩余（用雙倍字長(zhǎng)計(jì)算，再舍入成單字長(zhǎng)的數(shù)）(2) 求解（用單字長(zhǎng)運(yùn)算）。求出修正量。(3) 計(jì)算改善解。(4) 如果（指定的精度），則就是滿足精度要求的近似

42、解；否則對(duì)重復(fù)上述過程(1)(4)，就得及，如此做下去，即可求得方程組的一個(gè)近似解序列。當(dāng)方程組不是過分病態(tài)時(shí)，通常會(huì)很快收斂到準(zhǔn)確解。稱上述方法為迭代改善法。例1 用直接三角分解法解方程組解 因方程組的系數(shù)矩陣的兩行（列）幾乎線性相關(guān)，所以方程組可能是病態(tài)的。事實(shí)上方程組的確是病態(tài)的。利用迭代改善法：（1）實(shí)現(xiàn)分解得（2）解及得（3）計(jì)算（用雙倍字長(zhǎng)計(jì)算）（4）求解得（5）計(jì)算改善解（6）計(jì)算。重復(fù)（3）（6）步做法，得上述迭代改善過程還可以繼續(xù)下去，如果給定，則就是滿足精度要求的近似解。方程組的準(zhǔn)確解。7 矩陣的正交三角化及應(yīng)用7。1 初等反射陣定義9 設(shè)滿足，則稱為Housholder矩

43、陣（變換），或初等反射矩陣。定理16 Housholder矩陣具有以下性質(zhì)：（1）是實(shí)對(duì)稱的正交矩陣，即。（2）。（3）僅有兩個(gè)不等的特征值，其中是重特征值，是單重特征值，為其相應(yīng)的特征向量。圖5.1（4）對(duì)任意的，有從圖5。1可以看出，與關(guān)于超平面對(duì)稱，反射變換的名稱由此而來。證明 （1）顯然是實(shí)對(duì)稱矩陣，又所以是實(shí)對(duì)稱的正交矩陣，且。（2）（3） （4）定理17 設(shè)為兩個(gè)不相等的維向量，且，則存在一個(gè)初等反射矩陣，使。證明 令，則得到一個(gè)初等反射陣而且因所以定理17表明，一個(gè)向量經(jīng)某一個(gè)反射變換后可變成任何方向的等長(zhǎng)向量。定理18（約化定理）設(shè)，則存在初等反射陣使，其中證明 記，設(shè)，取，則

44、有，于是由定理17知，存在變換其中，使。記，于是其中，。顯然如果和異號(hào)，哪么計(jì)算時(shí)有效數(shù)字可能損失，我們?nèi)『陀邢嗤姆?hào)，即取在計(jì)算時(shí)，可能上溢或下溢，為了避免溢出，將規(guī)范化（設(shè)）則有使，其中算法6 設(shè)，本算法計(jì)算及使，分量沖掉的分量。計(jì)算 關(guān)于的計(jì)算，設(shè)其中為的第列向量，則，因此計(jì)算就是要計(jì)算于是計(jì)算只需計(jì)算兩向量的數(shù)量積和兩向量的加法。計(jì)算只需作次乘法運(yùn)算。7.2 平面旋轉(zhuǎn)矩陣設(shè)，則變換其中為正交矩陣。是平面上向量的一個(gè)旋轉(zhuǎn)變換。中變換：，其中 ，及稱為中平面的旋轉(zhuǎn)變換（或Givens變換），稱為平面旋轉(zhuǎn)矩陣。顯然，具有如下性質(zhì)：(1) 與單位陣只是在位置元素不一樣，其他相同。(2) 為正

45、交矩陣（）。(3) （左乘）只需計(jì)算第行與第行元素，即對(duì)有 其中。（4）（右乘）只需計(jì)算第列與第列元素 利用平面旋轉(zhuǎn)變換，可使向量中的指定元素變?yōu)榱?。定?9（約化定理）設(shè)，其中不全為零，則可選擇平面旋轉(zhuǎn)陣，使其中, 。證明 由，知只要選擇滿足可使。評(píng)注：實(shí)際應(yīng)用中，我們只關(guān)心之值，并不需要算得。保證是目的，因此可同時(shí)取以上值的相反數(shù)，相應(yīng)得。7.3 矩陣的分解以下我們討論如何用正交矩陣來約化矩陣。設(shè)為非零矩陣，將矩陣按列分塊(1) 第1步約化：若，取，即這一步不需要約化。不妨設(shè)，于是可選取初等反射陣，使,于是其中是維零列向量，。(2) 第步約化：假設(shè)已對(duì)完成上述前步的約化，即存在初等反射陣使

46、其中為階上三角陣，是階零矩陣，。將寫成按列分塊的形式，則有 不妨設(shè)，否則這一步不需要約化（如果列滿秩，則）。于是，可選取階初等反射陣，使根據(jù)構(gòu)造階矩陣就有而其中，是行的零列向量, 。因此其中為階上三角陣。令，繼續(xù)上述過程，最后有 (上梯形)第步約化大約需要次乘法運(yùn)算。以上討論可歸結(jié)為如下結(jié)果：定理20（矩陣的正交約化）設(shè)且，則存在初等反射陣，使為上梯形陣。約化過程大約需要（）次乘法運(yùn)算。定理21（矩陣的分解）(1) 設(shè)且的秩為，則存在初等反射陣使其中為階非奇異上三角陣。(2) 設(shè)為非奇異矩陣，則有分解其中為正交矩陣，為上三角矩陣。且當(dāng)具有正對(duì)角元時(shí)，分解唯一。證明 (1) 由定理20可得。(2) 由假設(shè)及定理20存在初等反射陣使記，則上式為，即其中為正交矩陣，為上三角矩陣。唯一性。設(shè)有，其中為正交陣，為非奇異上三角陣，且具有正對(duì)角元素，則由假設(shè)及對(duì)稱正定矩陣的Cholesky分解的唯一性，則，從而可得。下面考慮用平面旋轉(zhuǎn)變換來約化矩陣。定理22 （用Givens變換計(jì)算矩陣的分解）設(shè)為非奇異矩陣，則(1) 存在正交矩陣，使為非奇異上三角矩陣