數(shù)值分析教材

1、                                 第一章 緒論與誤差                 &

2、#160;              第一節(jié) 數(shù)值分析研究對象及特點(diǎn)  一、數(shù)值分析課的地位:    數(shù)值分析是計(jì)算數(shù)學(xué)的一個主要部分，計(jì)算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個分支。它研究用計(jì)算機(jī)求解各種數(shù)學(xué)問題的數(shù)值計(jì)算方法及其理論與軟件實(shí)現(xiàn)。    用計(jì)算機(jī)解決科學(xué)技術(shù)和工程問題的步驟:     實(shí)際問題建立數(shù)學(xué)模型研究計(jì)算方法程序設(shè)計(jì)上機(jī)計(jì)算求出結(jié)果。

3、60;例如:  某一地區(qū)的地形圖,用空中航測方法,空中連續(xù)拍照。  為形成三維地形圖,建立了一個大型超定線性方程組。  采用最小二乘方法求解該方程組的最小二乘解, 然后再整體平滑。  編程序,形成一個大型程序,上機(jī)進(jìn)行計(jì)算。   二、數(shù)值分析課的主要內(nèi)容:   計(jì)算機(jī)只能進(jìn)行加減乘除四則運(yùn)算和一些簡單的函數(shù)計(jì)算(即使是函數(shù)也是通過數(shù)值分析方法處理,轉(zhuǎn)化為四則運(yùn)算而形成了的一個小型軟件包)。   1.數(shù)值代數(shù):      求解線性和非線性方程的解法

4、, 分直接方法和間接方法。    2.插值和數(shù)值逼近。   3.數(shù)值微分和數(shù)值積分。    4.常微分方程和偏微分方程數(shù)值解法。  三、數(shù)值分析具有的特點(diǎn)    1. 面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)的特點(diǎn)提供切實(shí)可行的有效算法,即算法只能包含加、減、乘、除和邏輯運(yùn)算,這些運(yùn)算是計(jì)算機(jī)能直接處理的運(yùn)算。   2. 有可靠的理論分析，能任意逼近并達(dá)到精度要求，對近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對誤差進(jìn)行分析。   3. 要有好的計(jì)算復(fù)雜性。

5、時間復(fù)雜性好是指節(jié)省時間，空間復(fù)雜性好是指節(jié)省存儲量，這也是建立算法要研究的問題,它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。   4. 要有數(shù)值試驗(yàn)，即任何一個算法除了從理論上要滿足上述三點(diǎn)外還要通過數(shù)值試驗(yàn)證明是行之有效的。  四、對算法所要考慮的問題:   1. 計(jì)算速度   1 例如：求解一個20階線性方程組,用加減消元法需3000次乘法運(yùn)算,而用克萊姆法則要進(jìn)行次運(yùn)算,如用每秒1億次乘法運(yùn)算的計(jì)算機(jī)要30萬年。   2. 存儲量。 大型問題有必要考慮。   3. 數(shù)值穩(wěn)定性。在

6、大量計(jì)算中,舍入誤差是積累還是能控制,這與數(shù)值穩(wěn)定性算法有關(guān)。   例 一元二次方程 其精確解為               如用求根公式:    以及字長為8位的計(jì)算器求解有：                      

7、;  則:, 那么: 的值與精確解有天壤之別。若改用:  因此, 算法的選用很重要。  五、學(xué)習(xí)本課程應(yīng)注意的問題   (1) 要注意掌握方法的基本原理和思想,要注意方法處理的技巧其與計(jì)算機(jī)的結(jié)合，要重視誤差分析、收斂性及穩(wěn)定性的基本理論。   (2) 要通過例子，學(xué)習(xí)使用各種數(shù)值方法解決實(shí)際計(jì)算問題。   (3) 要做一定數(shù)量的理論分析與計(jì)算練習(xí)。            &#

8、160;     第二節(jié) 絕對誤差、相對誤差和有效數(shù)字    一、誤差的來源    數(shù)值計(jì)算,概括地講是“研究用于求得數(shù)學(xué)問題近似解的方法和過程”。因此,在計(jì)算過程中,誤差是不可避免。引起誤差的因素很多,主要有以下幾種：    1.模型誤差:在建立數(shù)學(xué)模型過程中,不可能將所有因素均考慮, 必然要進(jìn)行必要的簡化, 這就帶來了與實(shí)際問題的誤差。    2.觀測誤差: 在數(shù)學(xué)模型中,往往還有一些根據(jù)觀測得到的物理量，如溫度、長度、電壓等,這些

9、參量顯然也包含誤差。這種由觀測產(chǎn)生誤差稱為觀測誤差。    3.截?cái)嗾`差: 在數(shù)學(xué)模型不能得到精確解時，通常用數(shù)值方法求它的近似解，其近似解與精確解之間的誤差稱為截?cái)嗾`差或方法誤差。    4.舍入誤差: 計(jì)算機(jī)的字長是有限的,每一步運(yùn)算均需四舍五入,由此產(chǎn)出的誤差稱舍入誤差。    二、絕對誤差、相對誤差和有效數(shù)字?jǐn)?shù)值分析主要討論截?cái)嗾`差。觀測誤差看作初始的舍入誤差,數(shù)值分析也要從整體來討論舍入誤差的影響,但這兒不討論模型誤差。     1.誤差和誤差限 

10、;   設(shè)是精確值x的一個近似值, 稱是近似值的絕對誤差。簡稱誤差。 誤差是有量綱的,可正可負(fù)。誤差是無法計(jì)算的, 但可估計(jì)出它的一個上界。即, 稱是近似值的誤差限,其精確值的范圍 也可表示成    2.相對誤差和相對誤差限    誤差限的大小還不能完全表示即似值的好壞，例如有兩個量      x = 10±1， y = 1000±5 則     雖然比大四倍，但是比要小得多，這說明近似

11、y的程度比近似x的程度要好得多。所以,除考慮誤差的大小外，還應(yīng)考慮準(zhǔn)確值x本身的大小。為此我們引入相對誤差：稱           為近似值的相對誤差, 記作。相對誤差是個相對數(shù), 是無量綱的, r 也可正可負(fù)。相對誤差的估計(jì), 稱為相對誤差限, 即:實(shí)際計(jì)算中, x是未知的, 用來代替。兩者的差為:    3. 有效數(shù)字    定義: 如果近似值的誤差限是某一數(shù)位的半個單位, 從該位起向左到最前面第一個非零數(shù)字共有n位, 就說有n位有

12、效數(shù)字，它可表示其中(i=1,n)是0到9中的一個數(shù)字，,m為整數(shù)，且例如 =3.1415926535 ,3.14有三位有效數(shù)字,誤差限=0.005; 3.1416有五位有效數(shù)字, 誤差限為0.00005。又如0.003529是四位有效數(shù)字, 誤差限為, 0.00352900是六位有效數(shù)字,前者的誤差限為 。定理1: 設(shè)近似值有n位有效數(shù)字,則其相對誤差限 . 反之，若近似值的相對誤差限為則至少有n位有效數(shù)字。證明:因?yàn)椋汗?所以 反之，由故至少有n位有效數(shù)字。本定理說明，有效數(shù)字越多，相對誤差越小。    例1 重力加速度常數(shù),&#

13、160;兩者均有三位有效數(shù)字. , , 后者的絕對誤差大。而由定理1, 相對誤差分別為:       兩者相等, 與量綱的選取無關(guān)。例2 預(yù)使的近似值的相對誤差限小于0.1%,要取幾位有效數(shù)字。解 設(shè)取n位有效數(shù)字，由于=4.4, 由定理1        只要n=4, 就有例3 用四位浮點(diǎn)數(shù)計(jì)算 。 解:結(jié)果只有一位有效數(shù)字, 有效數(shù)字大量損失, 造成相對誤差擴(kuò)大。這是由兩個比較接近的數(shù)相減造成的。  結(jié)果仍然有四位

14、有效數(shù)字這說明了算法設(shè)計(jì)的重要性。                         第三節(jié) 數(shù)值計(jì)算中誤差的傳播    1.四則運(yùn)算中誤差的傳播 四則運(yùn)算誤差限的公式:           這是因?yàn)?   &#

15、160; 故         2.基本運(yùn)算(對函數(shù))中的誤差估計(jì)    設(shè)數(shù)值計(jì)算中求得的解與參量x有關(guān)，記為 y=f(x), 即y是x的函數(shù)。設(shè)是x的近似值,相應(yīng)的解(函數(shù))的近似值。其解的絕對誤差    , 誤差限記作，如果f(x)是可微的, 則：    取絕對值得：    假定f'(x )與f"(x )的比值不大, 可忽略() 的高階項(xiàng), 于是  

16、60;  和 其解的相對誤差為     于是    一般地，設(shè)數(shù)值計(jì)算中求得的解與參量有關(guān),記為y=f(), 即y是多元函數(shù),若分別是 ,的近似值, 類似地有：    于是                     例4 已側(cè)得某場地長的值為=110m, 寬d的值為=80m, 已知 |l-|0.2m, |d-|

17、0.1m, 試求面積s=ld的絕對誤差限和相對誤差限。解 s=ld, , 所以            3.算法的數(shù)值穩(wěn)定性。    一個程序往往要進(jìn)行大量的四則運(yùn)算才能得出結(jié)果,每一步的運(yùn)算均會產(chǎn)生舍入誤差。在運(yùn)算過程中,舍入誤差能控制在某個范圍內(nèi)的算法稱之為數(shù)值穩(wěn)定的算法,否則就稱之為不穩(wěn)定的算法。在大量計(jì)算中, 舍入誤差的積累還是能控制,這與算法有關(guān)。    例5 一元二次方程 其精確解為    

18、60;    。如用求根公式:     以及字長為8位的計(jì)算器求解有：             那么: 的值與精確解有天壤之別。若改用:    因此, 算法的選用很重要。                   &

19、#160;    第四節(jié) 數(shù)值計(jì)算中應(yīng)注意的問題     1. 避免兩個相近的數(shù)相減    兩個相近的數(shù)相減,有效數(shù)字會大大損失。前面一個例子已說明問題,這里再舉一例:           如用四位有效數(shù)字計(jì)算:          結(jié)果只有一位有效數(shù)字; 如改為:    

20、;      有四位有效數(shù)字。新算法避免了兩個相近數(shù)的相減。    2. 避免大數(shù)吃小數(shù)的現(xiàn)象    例如: a=1010 ,b=10, c=-a ,|a+c|<<b用八位計(jì)算機(jī)進(jìn)行計(jì)算:         (a+b)+c = (1010 +10)-1010 1010 -1010 = 0b被大數(shù)吃掉了。如按(a+c)+b=0+b=b,b 就沒有被吃掉。這也是構(gòu)造算法時要注意的問題。 &#

21、160;  3. 避免分母的絕對值遠(yuǎn)小于分子的絕對值    由公式         故當(dāng)|x2* |<<|x1* |, 舍入誤差可能會增大。    4. 要簡化計(jì)算，減少運(yùn)算次數(shù)，提高效率    例如計(jì)算ln2，若用公式        -1<x1取x=1, 前n項(xiàng)部分和來計(jì)算ln2的近似值，截?cái)嗾`差為。如果利用級數(shù) &#

22、160;      -1<x<1.來計(jì)算，當(dāng)時，代入上面的展開式得        取前5項(xiàng)之和作為近似值，參數(shù)的截?cái)嗾`差為        顯然，第二算法比第一算法有效。    又如計(jì)算多項(xiàng)式的值:  ,每取akxk有k次乘法運(yùn)算,因此計(jì)算Pn(x)共需  次乘法和n次加法運(yùn)算。    如將Pn(x)寫成: 

23、      Pn(x)=(anx+an-1)x+an-2)x+a1)x+a0用秦九韶算法:u0=an, uk=uk-1x + an-k,k=1,2,n 。最終Pn(x)=un,共需 n次乘法和n次加法運(yùn)算。一般地要注意,能在循環(huán)外計(jì)算,就不要放在循環(huán)內(nèi)計(jì)算。    5. 選用數(shù)值穩(wěn)定性的算法    例:In=e-1xnexdx ,n=0,1,2,用分部積分公式得遞推式:      In=1-nIn-1,I0=1-e-1用四位有效數(shù)字計(jì)算

24、:      I0=0.6321 ,I1=1-I0=0.3679 ,I2=1-2I1=0.2642      I3=1-3I2=0.2074 ,I4=1-4I3=0.1704       I5=1-5I4=0.1480 ,I6=1-6I5=0.1120       I7=1-7I6=0.2160 ,I8=1-8I7=-0.7280  可以估計(jì)出: 

25、     故: 0.0460<I7<0.1250 , 0.0409<I8<0.1111于是I7與I8精確值已經(jīng)面目全非,一位有效數(shù)字也沒有。這是由于如果I0有誤差e=0.5×10-4,不計(jì)中間再產(chǎn)生的舍入誤差,該誤差隨著計(jì)算過程分別乘以2,3,7,8到時已經(jīng)變成了8!e , 誤差擴(kuò)大了4萬倍。因而該算法不是穩(wěn)定的。如果遞推式改為,由I7=0.1124,逐步計(jì)算I6 ,I5 ,直到I0=0.6321。計(jì)算結(jié)果有四位有效數(shù)字,如果I7有誤差e, 其傳播到I0所引起的誤差僅為。故該算法是穩(wěn)定的。  

26、;                                  緒論與誤差    1 誤差和誤差限          x*-*x x*+*或 x

27、 = x* ±*    *誤差限    2 相對誤差和相對誤差限              3 有效數(shù)字    1) 有效數(shù)字        x*=±10m(a1+a2×10-1+ + an×10-n+1)其中ai(i=1,n)是0到9中的一個數(shù)字，a10,m為整數(shù)，且 

28、;       |e*|=|x*-x|=0.5×10m-n+1    2) 設(shè)近似值x*=±0.a1a2 an ×10m, 有n位有效數(shù)字, a10,則其相對誤差限. 反之，若近似值的相對誤差限為        則x*至少有n位有效數(shù)字。    4 數(shù)值計(jì)算中誤差的傳播    1) 四則運(yùn)算中誤差的傳播    

29、;    ,            2) 基本運(yùn)算(對函數(shù))中的誤差估計(jì)       e(f(x*) = f(x) - f(x*), 誤差限記作(f(x*)，如果f(x)是可微的, 則：      若f(x*)與f(x*)的比值不大, 可忽略(x*) 的高階項(xiàng),       (f(x*)|f(x*)

30、|(x*)和      e(f(x*)f(x* )e(x*) 相對誤差為                 習(xí) 題 一    1. 按四舍五入原則，求下列各數(shù)的具有四位有效數(shù)字的近似值：      168.957, 3.00045, 73.2250, 0.00152632 解   

31、    169.0, 3.000, 73.23, 0.001526    2. 設(shè)下列各數(shù)均未經(jīng)過四舍五入后的道的近似值，試求各數(shù)的絕對誤差限和相對誤差限。      a=3580, b=0.00476, c=2958×10-2, d=0.1430×10-2 解        a= 3580 = 0.3580×104, 絕對誤差限: 104-4=0.5, 相對誤差限 10-4&

32、#160;     b= 0.00476 = 0.476×10-2絕對誤差限: 10-2-3= 0.5×10-5, 相對誤差限 10-3+1=0.00125      c=2958×10-2= 0.2958×102絕對誤差限: 102-4= 0.5×10-2, 相對誤差限10-4+1=0.00025      d=0.1430×10-2 絕對誤差限: 10-2-4=0.5×10

33、-6, 相對誤差限 10-4+1=0.0005    3. 已知a=1.2031,b=0.978是經(jīng)過四舍五入后得到的近似值，問a+b,a×b有幾位有效數(shù)字。解        e(a+b)=e(a)+e(b)<0.00005+0.0005=0.00055 2有效數(shù)字      e(a×b)=e(a)b+ae(b)=0.00005×0.978+1.2031×0.0005   

34、;          0.000049+0.0006=0.00064 2 有效數(shù)字    4. 設(shè) x>0, x的相對誤差為, 求lnx的絕對誤差。解       e (lnx) = e(x) = er(x) = .     5. 求的近似值x*, 使其相對誤差不超過0.1%。解        

35、0;  1.414 = 0.1414×101    6. 要使的近似值小于0.1%的相對誤差，要取幾位有效數(shù)字。解      只要 er(x*)<0.008      4.472     7. 正方形的邊長約100cm,問測量邊長時誤差應(yīng)多大，才能保證面積的誤差不超過1cm2?解      e(x2)* = 2x*e(x*)<1, e(x*)&l

36、t;1/200=0.005      8. 計(jì)算球體的體積，為使其相對誤差限為1%，設(shè)測量半徑R, 相對誤差最大為多少？解             9. 設(shè)s=gt , 假定g是準(zhǔn)確的，而對t的測量有±0.1秒的誤差，試證當(dāng)t增大時，s的絕對誤差增大而相對誤差卻減少。解             10. 已知12.961有五位有效數(shù)字，試求

37、方程x2- 26x + 1 = 0的兩個根及它們的誤差限和相對誤差限。解        x1,2= 13±      x1=13+13+12.961=25.961=0.259612      e(x1)<×102-5=×10-3 , er(x1)<10-5+1= 10-4      x2=13-=1/(13+)0.038519=0.38

38、519×10-1       e(x1)<×10-1-5=×10-6 , er(x1)<10-5+1= 10-4    11. 已知27.983有五位有效數(shù)字，試求方程x2- 66x + 1 = 0的兩個根, 使它們至少有四位有效數(shù)字。解       x1,2= 28±      x1=28+28+27.983=55.983  

39、;     x2=28-=1/(28+)0.01786=0.1786×10-1    12. 設(shè)求證：    1) In= 1 -nIn-1 (n=0,1,2,)    2) 利用(1)中的公式正向遞推計(jì)算時誤差逐步增大；反向遞推計(jì)算時誤差逐步減少。解          In= 1-nIn-1=1-n1-(n-1)In-2=-(n-1)In-2=(-1)n(n-1)!I0誤差擴(kuò)

40、大(n-1)!倍。     I0= (1-I1)= (1-I2)=(1-I3)=(1-In)誤差縮小n!倍。             第二章 解線性方程組的直接方法    在自然科學(xué)和工程技術(shù)中很多問題的解決常常歸結(jié)為解線性代數(shù)方程組，而這些方程組的系數(shù)矩陣大致分為兩種，一種是低階稠密矩陣(例如，階數(shù)不超過150),另一種是大型性（即稀疏矩陣矩陣階數(shù)較高且零元素較多）。關(guān)于線方程組的數(shù)值解法一般有

41、兩類：    1.直接法:經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組精確解 (若計(jì)算過程中沒有舍入誤差) 的方法。但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。本章將闡述這類算法中最基本的高斯消去法及其某些變形。這類方法是解低階稠密矩陣方程組及某些大型稀疏矩陣方程組（例如，大型帶狀方程組）的有效方法。    2.迭代法: 用某種極限過程去逐步逼近線性方程組精確解的方法。迭代法具有需要計(jì)算機(jī)的存貯單元較少程序設(shè)計(jì)簡單、原始系數(shù)矩陣在計(jì)算過程中始終不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度問題。迭代法是解大型稀疏矩陣

42、方程組(尤其是由微分方程離散后得到的大型方程組)的重要方法(見第三章）。                            第一節(jié) 高斯消去法     一、高斯消去法的基本思想    例1. 解方程組：    

43、60;           解 方程組矩陣形式為:AX=b,其中:             第一步，消元過程：對增廣矩陣進(jìn)行消元   即得方程組   第二步, 回代過程:             此方法就是高斯消去法。 

44、   二、高斯順序消去法的計(jì)算流程及公式設(shè)有線性方程組：                        (2.1) 或?qū)懗删仃嚨男问?            簡記為Ax=b      

45、60;   記初始方程組AX=b 為A(1)X=b(1)。    1) 第一次消元(k=1),即消去第2到第n個方程中的x1 ,假定 0, 目標(biāo)是:                    第i個方程-第1個方程 ,這時=0,i=2,3,m, 而其它系數(shù)和右端有:        &

46、#160;       2) 第k次消元(k=1,2,s=min(m-1,n), 設(shè)上述第一步，第k步消元過程計(jì)算已經(jīng)完成，即以計(jì)算好與(2.1)等價的方程組：     簡記為：A(k)x=b(k) , 若0 第i個方程-第k個方程             A(k+1)x = b(k+1)A(k+1)與b(k+1)元素的計(jì)算公式為：      &#

47、160;       3) 繼續(xù)上述過程，且設(shè)a 0(k=1,2,s）,直到完成第s步 消元計(jì)算。最后得到與原方程組等價的方程組                    A(s+1)x = b(s+1)其中A(s+1)為上梯形。特別當(dāng)m=n時，與原方程組等價的方程組         

48、0;           A(s)x = b(s),即：           由(2.1)約化為(2.3)的過程稱為消元過程。如果ARn×n是非奇異矩陣，且0(k=1,2,n),求解(2.3) 得到求解公式：          (2.3)的求解過程(2.4)稱為回代過程。綜上可得：定理1

49、設(shè)Ax=b,其中 ARn×n 。    1) 如果0 (k=1,2,n), 則可通過高斯消去法將Ax=b約化為等價的三角形方程組(2.3), 且計(jì)算公式為：    a) 消元計(jì)算(k=1,2,n-1)            b) 回代計(jì)算            2) 如果A為非奇異矩陣，則可通過高斯消去法（即交換兩行的初等變換)

50、將方程組Ax=b約化為(2.3)。    定理2: 高斯消去法能進(jìn)行到底的充要條件是系數(shù)矩陣A的各階順序主子式不為零。（證明略）可以證明, 階順序主子式不為零的充要條件是0。這說明了高斯順序消元法的缺點(diǎn), 特殊地a11=0, 方程組未必?zé)o解, 但高斯順序消元法的第一步就無法進(jìn)行。這就需要用下一節(jié)的列主元消去法。    三、矩陣的三角分解設(shè)(2.1)的系數(shù)矩陣ARn×n 的各順序主子式均不為零。由于對實(shí)矩陣的初等行變換相當(dāng)于用初等矩陣左乘A, 對(2.1)實(shí)行第一次消元后，這時A(1) 化為A(2) = L1 A(1) , b

51、(1)化為b(2)= L1b(1), 其中                   一般地第k次消元后，A(k)化為A(k+1)= LkA(k) , b(k)化為b(k+1) = Lk b(k) , 其中                   重復(fù)這些過程，最后得到

52、：           將上三角矩陣A(n)記為U, 由(2.5)得到                    其中          為單位下三角矩陣。    定理3（矩陣的LU分解）設(shè)A為n階矩陣，

53、如果A的順序主子式Di 0,(i=1,2,n-1) , 則A可分解為一個單位下三角矩陣L和一個上三角矩陣U的乘積，且這種分解是唯一的。    證明：存在性已顯然，下面僅證唯一性。設(shè)A=LU=L1U1, 其中L,L1為單位下三角矩陣,U和U1 為上三角矩陣。由于存在，故         L-1L1 = U上式右邊為上三角矩陣，左邊為單位下三角矩陣，從而上式兩邊必須等于單位矩陣，故 U=U1 , L=L1 .    例2：解方程組    &

54、#160;           解 用LU分解在求解。      令 Ly=b,Ux=y, 求得y和x見上圖。                         第二節(jié) 高斯主元素消去法   

55、  問題的提出：由高斯消去法知道，在消元過程中可能出現(xiàn)=0的情況, 這時消去法將無法進(jìn)行；即使主元素0，但很小時，用其作除數(shù),會導(dǎo)致其他元素?cái)?shù)量級的嚴(yán)重增長和舍入誤差的擴(kuò)散, 最后也使得計(jì)算解不可靠。     引例 求解方程組             用4位浮點(diǎn)數(shù)進(jìn)行計(jì)算。   解： 方法1 用高斯消去法求解。         

56、                                      其中         計(jì)算解為:     &

57、#160;   顯然計(jì)算解 是一個很壞的結(jié)果，不能作為方程的近似解。    方法2 交換行，避免絕對值小的主元做除數(shù)。               得計(jì)算解為：         x=(-0.4900,-0.05113,0.3678)T x*.這個例子告訴我們，在采用高斯消去法解方程組時,小主元可能產(chǎn)生麻煩,故應(yīng)避免采用絕對值小的

58、主元素a 。對一般矩陣來說，最好每一步選取系數(shù)矩陣(或消元后的低價矩陣)中絕對值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)值穩(wěn)定性, 這就是全主元素消去法, 在選主元時要花費(fèi)較多機(jī)器時間，目前主要使用的是列主元消去法。 本節(jié)主要介紹列主元消去法,并假定(2.1)的ARn×n為非奇異的。   1. 列主元素消去法設(shè)方程組（2.1）的增廣矩陣為：                   首

59、先在A的第一列中選取絕對值最大的元素作為主元素，例如:          |ai1,1|= max |ai1|0， 1in 然后交換B的第一行與第i1 行，經(jīng)第一次消元計(jì)算得         (A|b)(A(2)|b(2) )  重復(fù)上述過程,設(shè)已完成第k-1步的選主元素,交換兩行及消元計(jì)算，(A|b)約化為:          

60、0;  (2.2)其中A(k) 的元素仍記為aij ，b(k) 的元素仍記為bi 。第k步選主元素(在A(k) 右下角方陣的第一列內(nèi)選)，即確定ik ，使              交換(A(k) |b(k) ) 第k行與ik 列的元素，再進(jìn)行消元計(jì)算,最后將原方程組化為(k=1，2，n-1):             

61、;     回代求解             2. 高斯-若當(dāng)消去法高斯消去法始終是消去對角線下方的元素,現(xiàn)考察高斯消去法的一種修正，即消去對角線下方和上方的元素，這種方法稱為高斯-若當(dāng)(GaussJordan)消去法。通過選主元，消元等過程最終化為：                 說明：用高斯-

62、若當(dāng)方法將A約化為單位矩陣,計(jì)算解就在常數(shù)位置得到,因此用不著回代求解,用高斯-若當(dāng)方法解方程組其計(jì)算量要比高斯消去法大,但用高斯若當(dāng)方法求一個矩陣的逆矩陣還是比較合適的。    定理4（高斯-若當(dāng)法求逆矩陣）設(shè)A為非奇異矩陣，C=(A|In ), 如果對C應(yīng)用高斯若當(dāng)方法化為（In|T），則A-1=T 。    例4 用高斯-若當(dāng)方法求 的逆矩陣以及的解。解：               

63、60;                             第三節(jié) 矩陣三角分解法    1 直接三角分解法    將高斯消去法改寫為緊湊形式,可以直接從矩陣A的元素得到計(jì)算L,U元素的遞推公式,而不需任何中間步驟,這就是所謂直接三角分解法。一旦實(shí)現(xiàn)了矩陣LU分解，

64、那么求解Ax=b 的問題就等價于要求解兩個三角形方程組  Ly=b,求y;        Ux=y,求x.設(shè)A為非奇異矩陣,且有分解式A=LU, L為單位下三角陣,U為上三角陣,即：    由(3.1)有:     a1i =U1i (i=1,2,n),得U的第1行元素;     ai1 =Li1 U11 ，Li1 =ai1 /U11 (i=2, ,n),得L的第1列元素.設(shè)已經(jīng)定出U的第1行到第r-1行元

65、素與L的第1列到第r-1列元素。由(3.1),利用矩陣乘法(注意當(dāng)rk時,Lrk =0),有         故        又由(3.1)有     總結(jié)上述討論，得到用直接三角分解法解Ax=b（要求A的所有順序主子式都不為零）的計(jì)算公式。    u1i =a1i (i=1,2,n), li1 =ai1 /u11 (i=2,3,n),計(jì)算U的第r行，L的第r列元素(i=2,

66、3,n)。    (2)    (3)求解Ly=b，Ux=y的計(jì)算公式；   (4)   (5) 例5 用直接三角分解法解 解:用分解公式        求解        矩陣A的分解公式(3.2),(3.3)又稱為杜利特爾(Doolittle)分解。   2. 追趕法在一些實(shí)際問題中，例如解常微分方程邊值問題，解熱傳導(dǎo)方程等

67、，都會要求解系數(shù)矩陣為對角占優(yōu)的三對角方程組：   簡記為Ax=f 。其中，當(dāng)|i-j|>1時，aij =0,且：       (a) |b1 |>|c1 |0       (b) |bi |ai |+|ci |,ai ,ci 0 (i=2,3,n-1)       (c) |bn |>|an |0 下面利用矩陣的直接分解發(fā)來推到接單對角線方程組(3.12)的計(jì)算公式。

68、 設(shè)A=LU ,其中L為下三角矩陣，U為單位上三角矩陣。即：         其中l(wèi)i ,ui ,di 為待定系數(shù)。比較(3.13)兩邊得：    由(3.14)得到：    這樣就確定了li ，ui ，di , 實(shí)現(xiàn)了A的LU分解。求解Ax=f等價于解兩個三角方程組：    （1）Ly=f,求y; （2）Ux=y,求x從而得到解三對角線方程組的追趕法公式：      

69、0;   1. 計(jì)算Li ,ui 的遞推公式：                            2. 解 Ly=f 3. 解Ux=y   計(jì)算系數(shù)L1 L2 Ln-1 及 y1 y2 yn 的過程稱為追的過程,計(jì)算方程組的解xn xn-1 &x1 

70、;的過程稱為趕的過程。                    第四節(jié) 平方根法    1. 平方根法    所謂平方根法,就是利用對稱正定矩陣的三角分解得到的求解對稱正定方程組的一種有效方法。設(shè)A為對稱矩陣，且A的所有順序主子式均不為零，由本章定理3知，A可唯一分解為如(3.1)的形式 A = LU為了利用A的對稱性，將U再分解為:

71、60;    其中D為對角陣，U0 為單位上三角陣，于是A=LU=LDU0 (4.1)     由分解的唯一性即得：         U0 = LT 代入(4.1)得到對稱矩陣A的分解式A = LDLT ?？偨Y(jié)上述討論有    定理5(對稱陣的三角分解定理) 設(shè)A為n階對稱陣，且A的所有順序主子式均不為零，則A可唯一分解為：       

72、  A = LDLT , (4,2)其中L為單位下三角陣，D為對角陣。 將D寫成, LD1 換成L得 ：    定理6（對稱正定矩陣的三角分解或Cholesky分解）如果A為n階對稱正定矩陣，則存在一個實(shí)的非奇異下三角陣L使         A = LLT , (4.3)當(dāng)限定L的對角元素為正時，這種分解是唯一的。 下面我們用直接分解方法來確定計(jì)算L的遞推公式。因?yàn)?#160;      其中Lii 0（i

73、=1，2,n）。由矩陣乘法及Ljk =0（當(dāng)jk時），得         于是得到解對稱正定方程組Ax=b的平方根法計(jì)算公式：對于 j=1,2,n    求解Ax=b，即求解兩個三角形方程組：   (1)Ly = b, 求y; (2) LT x = y, 求x.    例3.用平方根法求解方程組:  解 對于j=1,2,3    解Ly=b得：   

74、60;   2. 改進(jìn)的平方根法(LDLT 法)由定理5的分解公式(4.2)         由此可得到如下的計(jì)算公式           例4.用改進(jìn)平方根法求解方程組: 解：運(yùn)行過程見右圖。結(jié)果如下     (1) Ly = b, 求y; (2) Dz = y,求z; (3) LT x = z, 求x. 即    (1) L

75、y = b, 求y; (2) L Tx = D-1 y, 求x.               第五節(jié) 向量和矩陣的范數(shù)    一、向量的范數(shù)     定義1 設(shè)x=(x1 ,x2 ,xn )n ,y=(y1 ,y2 ,yn )n Rn (或Cn )。將實(shí)數(shù)       (或復(fù)數(shù)), 稱為向量x,y的數(shù)量積。將非負(fù)實(shí)數(shù) 

76、     或      稱為向量x的歐氏范數(shù)。 對向量x,y的數(shù)量積有：     1. (x,y)=(x,y).為實(shí)數(shù)(或(x,y)=(x,y),為復(fù)數(shù));    2. (x,y)=(y,x)(x,y)=(,);    3. (x1 +x2 ,y)=(x1 ,y)+(x2 ,y);    4. (Cauchy-Schwarz不等式)   

77、   (5.1)等式當(dāng)且僅當(dāng)x與y線形相關(guān)時成立。對向量x的歐氏范數(shù)有：     1. x2 0, x2 =0當(dāng)且僅當(dāng)x=0時成立;    2. x2 =|x2 ，任意的R(或C),    3. x+y2 x2 +y2 (三角不等式)， (5.2)注 (5.1)和(5.2)有下面的事實(shí)得到(x+ty,x+ty)=(x,x)+2(x,y)t+(y,y)t2 0由一元二次方程根的判別定理可知(5.1)成立；取t=1,再利用(5.1)得   即得(5.2)。定義

78、2(向量的范數(shù)) 如果向量xRn (或Cn )的某個實(shí)值函數(shù)N(x)=x, 滿足條件：   (1) x0(x=0當(dāng)且僅當(dāng)x=0)(正定條件)，   (2)  x=|·x，任意的R(或C),   (3)   x+yx+y(三角不等式)，則稱N(x)是Rn (或Cn )上的一個向量范數(shù)(或模)。 由(3)可推出不等式:  (4)| x-y |x-y。下面我們給出幾種常用的向量范數(shù)。   1. 向量的-范數(shù)(最大范數(shù))：   (5.

79、3)   2. 向量的1-范數(shù)：      3. 向量的2-范數(shù)：             (5.4)   4. 向量的p-范數(shù)：       (5.5)    例6 計(jì)算向量x=(1,-2,3)T 的各種范數(shù)。解：     定理6(N(x)的連續(xù)性) 設(shè)非負(fù)函數(shù)N(x)=x為R

80、n 上任一向量范數(shù)，則N(x)是x的分量x1 ,x2 ,xn 的連續(xù)函數(shù)。證明 設(shè)其中ei =(0,1,0,0)T, .只須證明當(dāng)xy時N(x)N(y)即成。事實(shí)上            即     |N(x)-N(y)|cx-y 0 (當(dāng)xy時),其中           定理7 (向量范數(shù)的等價性)設(shè)xs ,xt , 為Rn 上向量的任意兩種范

81、數(shù)，則存在常數(shù)c1 ,c2 0，使得對一切xRn 有         c1 xs xt c 2xs (5.6) 證明略    二、矩陣的范數(shù)   類似向量的范數(shù)的定義，我們將向量范數(shù)概念推廣到矩陣，給出矩陣范數(shù)的定義。    定義4(矩陣的范數(shù)) 如果矩陣ARn×n 的某個非負(fù)的實(shí)值函數(shù)N(A)=A,滿足條件  (1) A0(A=0 A=0) (正定條件)  (2)  cA=|c|

82、83;A, c為實(shí)數(shù)(齊次條件)  (3)   A+BA+B) (三角不等式)  (4)    ABA·B 則稱N(A)是Rn×n 上的一個矩陣范數(shù)(或模)。定義實(shí)值函數(shù)如下     (5.7)顯然F(A)滿足定義4，所以F(A)是Rn×n 上的一個矩陣范數(shù)，稱其為A的Frobenius范數(shù)。由于在大多數(shù)與估計(jì)有關(guān)的問題中，矩陣和向量會同時參與討論,所以希望引進(jìn)一種與向量范數(shù)相關(guān)矩陣的范數(shù)，且滿足范數(shù)相容條件,即對任何向量xRn 及ARn

83、5;n 都有      AxA·x (5.8)為此我們再引進(jìn)一種矩陣的范數(shù)。    定義5(矩陣的算子范數(shù)) 設(shè)XRn ,ARn×n , 給出一種向量范數(shù)Xv (如v=1,2 或)，相應(yīng)地定義一個矩陣的非負(fù)函數(shù)       可驗(yàn)證Av 滿足定義4(見下面定理)，所以Av 是Rn×n 上矩陣的一個范數(shù)，稱為A的算子范數(shù)。     定理8 設(shè)xv 是R 上一個向量范數(shù)，則Av 是Rn

84、5;n 上矩陣的范數(shù)，且滿足相容條件          Axv Av xv (5.10)證明 由(5.9)相容性條件(5.10)是顯然的. 現(xiàn)只驗(yàn)證定義4中條件(4),由(5.10),有          ABxv Av Bxv Av Bv xv當(dāng)x0時，有          ABxv /xv Av Bv ,故 

85、60;    ABv = max (ABxv /xv )Av Bv               x0      定理9 設(shè)xRn , ARn×n , 則       1)       (稱為A的行范數(shù))     

86、;  2)         (稱為A的列范數(shù))       3)     (稱為A的2-范數(shù))其中max (AT A)表示AT A的最大特征值.證明 只證1)。      設(shè)i0 使得         取 則      例7 設(shè) 計(jì)算A的各

87、種范數(shù)。解             定義6 設(shè)ARn×n 的特征值為i (i=1,2,n), 稱         為A的譜半徑。    定理10(特征值上界) 設(shè)ARn×n , 則(A)A, 即A的譜半徑不超過A的任何一個范數(shù)。證明：設(shè)是A的任一特征值，x為相應(yīng)的特征向量, 則Ax=x,由(5.7)得     

88、;  |X=X=AXAX ,注意到x0 , 即得|A     定理11 如果ARn×n 為對稱矩陣, 則A2 =(A) 證明留作習(xí)題(提示只需證明)    定理12 如果 B<1,則I±B為非奇異矩陣,且         (I±B) 1/(1-B), 其中·是指矩陣的算子范數(shù).證明 用反證法. 若det(I-B)=0, 則(I-B)X=0有非零解, 即存在X00使BX0

89、=X0 , BX0/X0=1,故B1, 與假設(shè)矛盾。 又由(I-B)(I-B)-1 = I. 有      (I-B)-1 = I + B(I-B)-1 , 從而    (I±B)-1 I+B (I±B)-1 ,     (I±B)-1 1/(1-B)               

90、0;   第六節(jié) 誤差分析    1. 方程組的狀態(tài)與條件數(shù)考慮線性方程組    Ax = b (6.1)其中設(shè)A為非奇異矩陣，x為方程組的精確解。由于A(或b)元素是測量得到的，或者是計(jì)算的結(jié)果，在第一種情況A(或b)常帶有某些觀測誤差，在后一種情況A(或b)又包含有舍入誤差。因此我們處理的實(shí)際矩陣是A+A (或b+b),下面我們來研究據(jù)A(或b)的微小誤差對解的影響。即考慮估計(jì)X-Y, 其中Y是   (A+A)Y = b+b的解。    例8 設(shè)有方程組 . 記

91、為Ax=b, 它的精確解為x=(2,0)T .現(xiàn)在考慮常數(shù)項(xiàng)的微小變化對方程組解的影響，考察方程組  也可表示為A(x+x)=b+b, 其中 b=(0,0.0001)T ,y=x+x, 它的精確解為y=x+x=(1,1)T .從這個例子看到常數(shù)項(xiàng)b的第2個分量只有1/1000的微小變化, 方程組的變化卻很大。這樣的方程組稱為病態(tài)方程組。    定義7 如果矩陣A或常數(shù)項(xiàng)b的微小變化,引起方程組Ax=b 的解的巨大變化,則稱此方程組為“病態(tài)方程組”，矩陣A稱為“病態(tài)”矩陣 (相對于方程組而言)，否則稱方程組為“良態(tài)”

92、矩陣。以下我們研究方程組(6.1)的系數(shù)矩陣A(或b)的微小誤差(擾動)對解的影響。現(xiàn)設(shè)A是精確的，b有誤差b, 解為x+x, 則          A(x+x)=b+b => x=A-1 b,         xA-1 b. (6.2)由于         b=AxAx,所以           (6.3)于是           這樣我們有下面的定理：    定理13 設(shè)A是非奇異矩陣，Ax=b0, 且A(x+x) = b+b，則