線性方程組直接方法

1、關(guān)于線性方程組的直接方法第一張，PPT共一百零七頁，創(chuàng)作于2022年6月解線性方程組的直接法簡記為 Ax=b，其中 ( 6.1 ) 常見的線性方程組是方程個數(shù)和未知量個數(shù)相同的n階線性方程組，一般形式為 第二張，PPT共一百零七頁，創(chuàng)作于2022年6月線性方程組的數(shù)值解法一般有兩類：直接法：就是經(jīng)過有限步算術(shù)運算，可求得方程組精確解的方法（若計算過程中沒有舍入誤差），如克萊姆法則就是一種直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法: 就是用某種極限過程去逐步逼近線性方程組的精確解的方法。也就是從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法。(一般有限步內(nèi)得不

2、到精確解)第三張，PPT共一百零七頁，創(chuàng)作于2022年6月三、特殊矩陣對角矩陣三對角矩陣上三角矩陣上海森伯(Hessenberg)陣對稱矩陣埃爾米特矩陣對稱正定矩陣正交矩陣酉矩陣初等置換陣置換陣第四張，PPT共一百零七頁，創(chuàng)作于2022年6月定理1 設(shè)ARnn, A非奇異?定理2 若ARnn對稱正定矩陣，則?定理3 若ARnn對稱矩陣，則對稱正定矩陣0, i=1,2,n 因此存在惟一的分解 A=LU 第五十八張，PPT共一百零七頁，創(chuàng)作于2022年6月L是單位下三角陣, U是上三角陣, 將U再分解 其中D為對角陣, U0為單位上三角陣，于是 A = L U = L D U0 又 A = AT

3、= U0TD LT由分解惟一性, 即得 U0T=L A=L D LT 第五十九張，PPT共一百零七頁，創(chuàng)作于2022年6月記 又因為det(Ak)0,(k=1,2,n), 故于是對角陣D還可分解 其中 為下三角陣,令L=L1，定理得證。 第六十張，PPT共一百零七頁，創(chuàng)作于2022年6月將A=LLT展開，寫成 按矩陣乘法展開，可逐行求出分解矩陣L的元素，計算公式是對于i=1,2,n j=i+1, i+2,n 這一方法稱為平方根法,又稱喬累斯基(Cholesky)分解,它所需要的乘除次數(shù)約 為數(shù)量級,比LU分解節(jié)省近一般的工作量。 第六十一張，PPT共一百零七頁，創(chuàng)作于2022年6月例6.9 平

4、方根法求解方程組 解: 因方程組系數(shù)矩陣對稱正定,設(shè)A= ,即： 由Ly=b解得 由 解得 由此例可以看出，平方根法解正定方程組的缺點是需要進(jìn)行開方運算。為避免開方運算，我們改用單位三角陣作為分解陣，即把對稱正定矩陣A分解成 的形式，其中 第六十二張，PPT共一百零七頁，創(chuàng)作于2022年6月為對角陣，而 是單位下三角陣,這里分解公式為 第六十三張，PPT共一百零七頁，創(chuàng)作于2022年6月?lián)丝芍鹦杏嬎?運用這種矩陣分解方法,方程組Ax=b即可歸結(jié)為求解兩個上三角方程組 和其計算公式分別為 和 求解方程組的上述算法稱為改進(jìn)的平方根法。這種方法總的計算量約為 ，即僅為高斯消去法計算量的一半。 第六

5、十四張，PPT共一百零七頁，創(chuàng)作于2022年6月記筆記5.7 向量和矩陣的范數(shù) 為了研究線性方程組近似解的誤差估計和迭代法的收斂性, 有必要對向量及矩陣的“大小”引進(jìn)某種度量-范數(shù)的概念。向量范數(shù)是用來度量向量長度的,它可以看成是二、三維解析幾何中向量長度概念的推廣。用Rn表示n維實向量空間。第六十五張，PPT共一百零七頁，創(chuàng)作于2022年6月記筆記5.7 向量和矩陣的范數(shù)定義5.2 對任一向量XRn, 按照一定規(guī)則確定一個實數(shù)與它對應(yīng), 該實數(shù)記為|X|, 若|X|滿足下面三個性質(zhì):(1) |X|0；|X|=0當(dāng)且僅當(dāng)X=0；(2) 對任意實數(shù)， | X|=| | |X|； 對任意向量YRn

6、，|X+Y| |X|+|Y| 則稱該實數(shù)|X|為向量X的范數(shù)第六十六張，PPT共一百零七頁，創(chuàng)作于2022年6月在Rn中，常用的幾種范數(shù)有：記筆記其中x1,x2, ,xn分別是X的n個分量。以上定義的范數(shù)分別稱為1-范數(shù)，2-范數(shù)和-范數(shù)可以驗證它們都是滿足范數(shù)性質(zhì)的，其中 是由內(nèi)積導(dǎo)出的向量范數(shù)。5.7 向量和矩陣的范數(shù)第六十七張，PPT共一百零七頁，創(chuàng)作于2022年6月當(dāng)不需要指明使用哪一種向量范數(shù)時，就用記號|.|泛指任何一種向量范數(shù)。有了向量的范數(shù)就可以用它來衡量向量的大小和表示向量的誤差。設(shè)x*為Ax=b的精確解，x為其近似解，則其絕對誤差可表示成|x- x* |，其相對誤差可表示成

7、記筆記5.7 向量和矩陣的范數(shù)或第六十八張，PPT共一百零七頁，創(chuàng)作于2022年6月第六十九張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.10 證明對任意同維向量x , y 有 證： 即 第七十張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.11 設(shè)x=(1, 0, -1, 2)T, 計算 解: =1+0+|-1|+2=4第七十一張，PPT共一百零七頁，創(chuàng)作于2022年6月定理7.1 對于任意向量x ,有證: 即 當(dāng) p， 第七十二張，PPT共一百零七頁，創(chuàng)作于2022年6月定義5.4 ( 向量序列的極限 ) 設(shè) 為 中的一向量序列， , 記 。如果 (i =1,2, n)，則稱 收斂于

8、向量 ，記為 定理7 .2（向量范數(shù)的等價性）設(shè) 為 上任意兩種向量范數(shù), 則存在常數(shù)C1, C20,使得對任意 恒有（證:略） 第七十三張，PPT共一百零七頁，創(chuàng)作于2022年6月定理7 其中 為向量中的任一種范數(shù)。 證 由于 而對于 上的任一種 范數(shù), 由定理3.7知存在常數(shù)C1，C2，使 于是可得 從而定理得證。 第七十四張，PPT共一百零七頁，創(chuàng)作于2022年6月定義5.5（矩陣的范數(shù)）如果矩陣 的某個非負(fù)的實值函數(shù) ，滿足則稱 是 上的一個矩陣范數(shù)(或模) 第七十五張，PPT共一百零七頁，創(chuàng)作于2022年6月矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗證。(1) 設(shè)A0, x0, 使Ax0,

9、 根據(jù)向量范數(shù)的性 質(zhì)Ax 0, 所以0 x0, 使Ax =0, 則=0當(dāng)A=0時, 第七十六張，PPT共一百零七頁，創(chuàng)作于2022年6月矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗證(2)根據(jù)向量范數(shù)的性質(zhì)第七十七張，PPT共一百零七頁，創(chuàng)作于2022年6月矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗證(3)第七十八張，PPT共一百零七頁，創(chuàng)作于2022年6月矩陣范數(shù)定義的另一種方法是這是由于同樣，矩陣范數(shù)和向量范數(shù)密切相關(guān)，向量范數(shù)有相應(yīng)的矩陣范數(shù)，即第七十九張，PPT共一百零七頁，創(chuàng)作于2022年6月第八十張，PPT共一百零七頁，創(chuàng)作于2022年6月定義5.7（矩陣的譜半徑）設(shè) 的特征 值為 , 稱 為

10、A的譜半徑。例 5.12 計算方陣 的三種常用范數(shù) 第八十一張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.12 計算方陣 的三種范數(shù) 解 先計算 所以 ,從而 第八十二張，PPT共一百零七頁，創(chuàng)作于2022年6月定理5.8.1 設(shè)A為n階方陣, 則對任意矩陣范數(shù)都有證: 設(shè) 為A的特征值，x是 對應(yīng)于的特征向 量,則 x=Ax。兩端取范數(shù)并依據(jù)其性質(zhì) 得由于x0，故 ，所以第八十三張，PPT共一百零七頁，創(chuàng)作于2022年6月第八十四張，PPT共一百零七頁，創(chuàng)作于2022年6月5.8 誤差分析5.8.1 方程組的性態(tài) 在建立方程組時，其系數(shù)往往含有誤差（如觀測誤差或計算誤差），就是說，所要求

11、解的運算是有擾動的方程組，因此需要研究擾動對解的影響。 第八十五張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.13 考察方程組 和 上述兩個方程組盡管只是右端項有微小擾動, 但解大不相同, 第1個方程組的解是第2個方程組的解是 。這類方程組稱為病態(tài)的。第八十六張，PPT共一百零七頁，創(chuàng)作于2022年6月定義5.8 A或b的微小變化(又稱擾動或攝動)引起方程組Ax=b解的巨大變化，則稱方程組為病態(tài)方程組，矩陣A稱為病態(tài)矩陣。否則方程組是良態(tài)方程組，矩陣A也是良態(tài)矩陣 為了定量地刻畫方程組“病態(tài)”的程度，要對方程組Ax=b進(jìn)行討論，考察A（或b）微小誤差對解的影響。為此先引入矩陣條件數(shù)的概念。

12、 定義5.9 （矩陣條件數(shù)）設(shè)A為非奇異矩陣，稱 為矩陣A條件數(shù)。 第八十七張，PPT共一百零七頁，創(chuàng)作于2022年6月第八十八張，PPT共一百零七頁，創(chuàng)作于2022年6月第八十九張，PPT共一百零七頁，創(chuàng)作于2022年6月 我們先來考察常數(shù)項b的微小誤差對解的影響。設(shè)A是精確的, b有誤差 (或擾動)b, 顯然,方程組 的解與x有差別, 記為即有即 （由設(shè)Ax=b0）于是 （6.18）又 Ax=b0，則有 由（6.18）式及（6.19）式即得如下定理 （6.19）或第九十張，PPT共一百零七頁，創(chuàng)作于2022年6月定理 5.12 (b的擾動對解的影響) 設(shè)A非奇異， Ax=b0，且 則有 證

13、:設(shè)A精確且非奇異,b有擾動b,使解x有擾動x, 則 消去Ax=b，有又相比較可得 第九十一張，PPT共一百零七頁，創(chuàng)作于2022年6月定理 5.13 (A的擾動對解的影響) 設(shè)A非奇異，Ax=b0，且若 ,則 證 ：略第九十二張，PPT共一百零七頁，創(chuàng)作于2022年6月我們還可證明更為一般的結(jié)論： 當(dāng)方程組的系數(shù)矩陣A非奇異和常數(shù)項b為非零向量時，且同時有擾動A，b，滿足 ，若x和x+x分別是方程組Ax=b 及 的解則第九十三張，PPT共一百零七頁，創(chuàng)作于2022年6月例6.13 線性方程組 的系數(shù)矩陣帶誤差，成為如下方程組 求方程組系數(shù)矩陣的條件數(shù), 并說明方程組的性態(tài) 解 因為 所以 因

14、此方程組是良態(tài)的 第九十四張，PPT共一百零七頁，創(chuàng)作于2022年6月5.7.2 精度分析求得方程組Ax=b的一個近似解以后,希望判斷其精度，檢驗精度的一個簡單辦法是將近似解再回代到原方程組去求出余量r. r = b-A 如果r很小，就認(rèn)為解是相當(dāng)精確的。定理6.14 設(shè) 是方程組Ax=b的一個近似解,其精確解記為 ,r為 的余量。則有 證明見P172第九十五張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.14 設(shè)A為正交矩陣，證明：cond2(A)=1分析：由正交矩陣和條件數(shù)的定義便可推得解：因為A是正交矩陣， 故ATA= AAT=I， A-1= AT，從而第九十六張，PPT共一百零七頁，

15、創(chuàng)作于2022年6月例5.15 設(shè)A，B為n階矩陣，證明： cond(AB) cond(A) cond(B)分析: 由矩陣范數(shù)性質(zhì)和條件數(shù)定義 便可證明證： cond (AB) = | AB | | (AB)-1 | |A| |B| |A-1| |B-1| = |A| |A-1| |B| |B-1| = cond (A) cond (B) 第九十七張，PPT共一百零七頁，創(chuàng)作于2022年6月例5.16 設(shè)A，B為n階非奇異矩陣，|表示 矩陣的任一種范數(shù)，證明： | A-1-B-1 | | A-1 | | B-1 | | A-B | cond(AB) cond(A) cond(B)分析: 由矩陣

16、范數(shù)的基本性質(zhì)即可推證證： A-1-B-1 = A-1(B-A)B-1 ,從而 | A-1-B-1 | A-1(B-A)B-1 | |A-1| |B-A| |B-1| | A-1-B-1 | |A-1| |B-A| |B-1| 第九十八張，PPT共一百零七頁，創(chuàng)作于2022年6月例9 求Hilbert矩陣H3的條件數(shù).第九十九張，PPT共一百零七頁，創(chuàng)作于2022年6月如何發(fā)現(xiàn)判斷矩陣是病態(tài)的?如何解決和處理?預(yù)處理方法.第一百張，PPT共一百零七頁，創(chuàng)作于2022年6月例10 設(shè)則化為則第一百零一張，PPT共一百零七頁，創(chuàng)作于2022年6月二、迭代改善法(略去)第一百零二張，PPT共一百零七

17、頁，創(chuàng)作于2022年6月本章小結(jié) 本章介紹了解線性方程組的直接法。直接法是一種計算量小而精度高的方法。直接法中具有代表性的算法是高斯（Gauss）消去法（在第一章提到的克萊姆算法也是一種直接法，但該算法用于高階方程組時計算量太大而不實用），其它算法大都是它的變型，這類方法是解具有稠密矩陣或非結(jié)構(gòu)矩陣（零元分布無規(guī)律）方程組的有效方法。 第一百零三張，PPT共一百零七頁，創(chuàng)作于2022年6月 選主元的算法有很好的數(shù)值穩(wěn)定性。從計算簡單出發(fā)實際中多選用列主元法。 解三對角矩陣方程組（A的對角元占優(yōu)）的追趕法，解對稱正定矩陣方程組的平方根法都是三角分解法，且都是數(shù)值穩(wěn)定的方法，這些方法不選主元素，也具有較高的精度。 向量、矩陣的范數(shù)、矩陣的條件數(shù)和病態(tài)方程組的概念，是數(shù)值計算中一些基本概念。線性方程組的病態(tài)程度是其本身的固有特性，因此即使用數(shù)值穩(wěn)定的方法求解，也難以克服嚴(yán)重病態(tài)導(dǎo)致的解的失真。在病態(tài)不十分嚴(yán)重時，用雙精度求解可減輕病態(tài)的影響 第一百零四張，PPT共一百零七