計算方法全書課件完整版ppt整本書電子教案最全教學(xué)教程ppt課件

1、計算方法計算方法課程組計算方法課程組12第1章 緒論1.1 計算方法概述科學(xué)計算與計算方法數(shù)學(xué)模型與計算方法計算方法的特點及學(xué)習(xí)方法1.2 誤差計算機的浮點表示及算術(shù)運算誤差來源誤差的基本概念誤差分析3應(yīng)用舉例1問：今有問：今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二十六斗。上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？問上、中、下禾實一秉各幾何？ 九章算術(shù)九章算術(shù)3239xyz2334xyz2326xyz例：

2、一個古老的數(shù)學(xué)問題例：一個古老的數(shù)學(xué)問題4應(yīng)用舉例應(yīng)用舉例1 14線性方程組數(shù)值求解線性方程組數(shù)值求解1112111212222211nnnnnnnnaaaxbaaaxbaaaxb Axb 例：人口預(yù)測例：人口預(yù)測表格中是我國表格中是我國1950年到年到2005年的人口數(shù)（見年的人口數(shù)（見中國統(tǒng)計年鑒），試預(yù)測未來的人口數(shù)中國統(tǒng)計年鑒），試預(yù)測未來的人口數(shù)插值與曲線擬合插值與曲線擬合 年份年份人口人口(萬萬)1950551961955614651960662071965725381970829921975924201980987051985105851199011433199512112120

3、001267432005130756應(yīng)用舉例應(yīng)用舉例2 26例：例：鋁制波紋瓦的長度問題鋁制波紋瓦的長度問題建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓建筑上用的一種鋁制波紋瓦是由機器將一塊平整的鋁板壓制而成。假若要求波紋瓦長制而成。假若要求波紋瓦長 4 英尺，每個波紋的高度英尺，每個波紋的高度(從中從中心線心線)為為 1 英寸，且每個波紋以近似英寸，且每個波紋以近似 2 英寸為一個周期。英寸為一個周期。求制做一塊波紋瓦所需鋁板的長度求制做一塊波紋瓦所需鋁板的長度 L。應(yīng)用舉例應(yīng)用舉例3 37這個問題就是要求由函數(shù)這個問題就是要求由函數(shù) f(x)=sin x給定的曲線從給定的曲線從 x=

4、0 到到 x=48 英寸間的弧長英寸間的弧長 L，即，即:數(shù)值積分與數(shù)值微分數(shù)值積分與數(shù)值微分484822001( ) d1(cos ) dLfxxxx上述積分為第二類橢圓積分，無法用普通方法來計算上述積分為第二類橢圓積分，無法用普通方法來計算應(yīng)用舉例應(yīng)用舉例3 38Google 搜索引擎搜索引擎PageRank: 對搜索結(jié)果按重要性排序基本原理“從優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁必定還是優(yōu)質(zhì)網(wǎng)頁”超鏈接AB A 對B 投一票若A的質(zhì)量高，則該投票分數(shù)高1998年，美國斯坦福大學(xué)的Larry Page和Sergey Brin創(chuàng)立了Google公司應(yīng)用舉例應(yīng)用舉例4 49應(yīng)用舉例應(yīng)用舉例4 4由于所有網(wǎng)

5、頁的Pr值可由所有鏈向它的頁面的重要性加和得到MPr = Pr(M-I)Pr = 0 100103/1002/13/12/1003/12/102/10M矩陣特征值計算矩陣特征值計算 線性方程組求解問題線性方程組求解問題 蝴蝶效應(yīng) 洛倫茲吸引子(Lorenz attractor)是由MIT大學(xué)的氣象學(xué)家Edward Lorenz在1963年給出的，他給出第一個混沌現(xiàn)象蝴蝶效應(yīng)。 圖1 蝴蝶效應(yīng)示意圖應(yīng)用舉例應(yīng)用舉例5 511 dxxydtdyrxyxzdtdzbzxydt 洛倫茲方程是大氣流體動力學(xué)模型的一個簡化的常微分方程組：應(yīng)用舉例應(yīng)用舉例5 512數(shù)值計算方法定義線性方程組的解法矩陣特征值

6、與特征向量的計算函數(shù)插值數(shù)值微分與積分非線性方程(組)的解法與最優(yōu)化問題的計算方法常微與偏微分方程的數(shù)值解法有關(guān)計算方法可靠性的理論研究,如方法的收斂性和穩(wěn)定性分析與誤差估計等.131.1.1 科學(xué)計算與計算方法科學(xué)計算與計算方法14計算工具15計算工具16計算工具17計算工具18計算古老年輕與時俱進 計算物理、計算化學(xué)、計算力學(xué)、 數(shù)量經(jīng)濟、計算生物學(xué).19理論研究科學(xué)實驗科學(xué)計算計算數(shù)學(xué)科學(xué)研究20科學(xué)計算風(fēng)洞21科學(xué)計算計算機計算能力的提高，衍生了計算方法這門課程22 數(shù)值計算方法的應(yīng)用極為廣泛，上至國防尖端科技，下至日常生活生產(chǎn)，如火箭和衛(wèi)星的設(shè)計與控制、飛機與汽車的優(yōu)化設(shè)計、尖端數(shù)控

7、機床、地質(zhì)勘探與油氣開發(fā)、天氣預(yù)報、圖像處理、網(wǎng)絡(luò)搜索等方面都有數(shù)值計算方法的應(yīng)用。 它作為一種科學(xué)方法已經(jīng)滲透到許多不同的科學(xué)領(lǐng)域，并形成了一些諸如計算力學(xué)、計算物理、計算化學(xué)、計量經(jīng)濟學(xué)、生物信息學(xué)等交叉學(xué)科。23計算方法與科學(xué)計算科學(xué)計算是人類從事科學(xué)活動和解決科學(xué)技術(shù)問題不可缺少的手段。計算機科學(xué)技術(shù)的發(fā)展，為科學(xué)計算及數(shù)據(jù)處理提供了高速和高精度的計算工具。計算機運算: 只能進行加，減，乘，除等算術(shù)運算和一些邏輯運算。24計算方法與科學(xué)計算實際實際問題問題數(shù)學(xué)數(shù)學(xué)模型模型 數(shù)值數(shù)值方法方法程序程序設(shè)計設(shè)計計算機計算機計算計算解答解答科學(xué)計算的過程科學(xué)計算的過程25三維地圖構(gòu)建26三維地

8、圖構(gòu)建（1）實際問題：空中航測（空中連續(xù)拍照）方法，構(gòu)建某地三維地形圖。（2）數(shù)學(xué)模型：建立一個大型超定線性方程組。（3）數(shù)值方法：采用最小二乘方法求解該方程組的最小二乘解。（4）程序設(shè)計：任何語言。（5）計算機計算（6）問題的解，對解進行解釋。27數(shù)值計算方法定義數(shù)學(xué)的一個分支，它以數(shù)字計算機求解數(shù)學(xué)問題的方法與理論為研究對象，其內(nèi)容包括:28數(shù)值計算方法定義線性方程組的解法矩陣特征值與特征向量的計算函數(shù)插值數(shù)值微分與積分非線性方程(組)的解法與最優(yōu)化問題的計算方法常微與偏微分方程的數(shù)值解法有關(guān)計算方法可靠性的理論研究,如方法的收斂性和穩(wěn)定性分析與誤差估計等.29為什么要學(xué)習(xí)計算方法為什么要

9、學(xué)習(xí)計算方法30舉例說明一311.求解線性方程組Ax=b，其中A為3階可逆方陣X=(x1, x2, x3)T;2.求代數(shù)方程x2+x-6=0在0,4上的根x*3.已知y=p(x)為x0, x1上的直線，滿足p(x0)= y0 ， p(x1)= y1求p(x2)4.計算定積分5.解常微分方程初值問題(0)0yxy 1(1)baIdxabx舉例說明二1.求解線性方程組Ax=B，其中A為20階可逆方陣X=(x1, x2, , x20)T;2.求代數(shù)方程xex=1在0,1上的根x*3.已知y=f(x)為x0, x1上的函數(shù)，滿足f(x0)= y0 ， f(x1)= y1求f(x2)4.計算定積分5.解

10、常微分方程初值問題321(1)lnbaIdxabx2(0)0yxyy線性方程組求解考慮線性代數(shù)方程組Ax=b的求解計算問題。其中系數(shù)矩陣A為一n階方陣，D=det(A)0Cramer法則 xi=Di / D i=1,2,n 33積分求解對于積分由微積分知識可知：只要找到被積函數(shù)f(x)的原函數(shù)F(x)，便有下列牛頓萊布尼茲公式badxxfI)()()()(aFbFdxxfba34積分求解原因一：原函數(shù)不能用初等函數(shù)表示成有限形式原因二：原函數(shù)過于復(fù)雜babadxxxdxxsin,sin232)(22xxxf) 322ln(216916323432)(2223xxxxxxxF35積分求解原因三：

11、f (x)以離散數(shù)據(jù)點形式給出xix0 x1xnyi = f(xi)y0y1yn36積分求解有了數(shù)學(xué)模型，并不一定能夠直接用計算機求解，因此我們需要學(xué)習(xí)計算方法!學(xué)習(xí)計算方法這門課程，能夠讓我們學(xué)會如何構(gòu)造或選擇那些“好”的數(shù)值計算方法。37秦九韶算法考慮對任意給定的x, 計算代數(shù)多項式 (1.1.3) 的值的問題。nkknknnnnnxaaxaxaxaxP01110)(38秦九韶算法考慮對任意給定的x, 計算代數(shù)多項式 的值的問題。顯然，上式等價于nnnaxaxaxaxaxP1210)(nkknknnnnnxaaxaxaxaxP01110)(1.1.3)(1.1.5)391.1.3 計算方法

12、的特點及學(xué)習(xí)方法計算方法的特點及學(xué)習(xí)方法40課程特點計算方法是一門與計算機應(yīng)用緊密結(jié)合、實用性很強的數(shù)學(xué)課程，它所涉及的數(shù)學(xué)問題面很廣、內(nèi)容非常豐富，亦有其自身的體系它既有數(shù)學(xué)的高度概括，又非常講究實用性并具有高度的技巧性41課程特點第一，面向計算機，研究計算機上用的計算方法 （算法最終只可包含四則運算和邏輯運算）第二，要有可靠的理論分析 （算法收斂性、穩(wěn)定性及誤差分析）第三，要注重算法的效率 （計算時間、存儲空間）第四，要重視數(shù)值實驗42本課程的學(xué)習(xí)方法掌握構(gòu)造方法的原理、思想，理解算法，會分析算法精度注重算法的效率和適用范圍，針對不同情況學(xué)會選擇和設(shè)計優(yōu)秀算法要重視實踐，通過算例和動手計算

13、，學(xué)會怎樣使用數(shù)值方法在計算機上解決各類數(shù)學(xué)計算問題431.2 1.2 誤差誤差44誤差計算機的浮點表示及算術(shù)運算誤差來源誤差的基本概念誤差估計451.2.11.2.1計算機的浮點表示及算術(shù)運算計算機的浮點表示及算術(shù)運算46數(shù)的浮點表示實數(shù)x在計算機中被表示為 x = 0.d1d2dk2p d1=1,di為0或1，i=2,3,k, -mpM.零的浮點數(shù)通常表示為 0 = 0.0002-m 47數(shù)的浮點表示實數(shù)x在計算機中被表示為 x = 0.d1d2dk2p d1=1,di為0或1，i=2,3,k, -mpM.零的浮點數(shù)通常表示為 0 = 0.0002-m 尾數(shù)階碼48數(shù)的浮點表示 x = 0

14、.d1d2dk2p (1.2.1)給定的二進制浮點計算機，只能表示所有形如上式的有限數(shù)集S=S(k,m,M)，這是實數(shù)軸上的不等距有限點集。49數(shù)的浮點表示 S=S(3,1,2) k=3， m=1， M=2， -1p2 那么計算機能表示的浮點數(shù)集合是如下的33個點。 0 = 0.0002-1 x= 0.1d2d3 2-1 x= 0.1d2d3 20 x= 0.1d2d3 21 x= 0.1d2d3 2250數(shù)的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.11

15、0 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/851數(shù)的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80152數(shù)的浮點表示 x= 0.1d2d3 2-1 x= 0.1d2d3 20 0.100 2-1=1/4 0.100 20=1/2 0.101 2-1=5/16 0.101 20=5/8 0.110 2-

16、1=3/8 0.110 20=3/4 0.111 2-1=7/16 0.111 20=7/80153數(shù)的浮點表示例如單精度實數(shù)用32位的二進制表示，其中符號位占1位，尾數(shù)占23位，階數(shù)占8位，可以寫成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位階數(shù)中須有1位表示階數(shù)的符號，所以階數(shù)值占7位。54數(shù)的浮點表示例如單精度實數(shù)用32位的二進制表示，其中符號位占1位，尾數(shù)占23位，階數(shù)占8位，可以寫成如下形式 x = 0.d1d2d232p |p| 27-1 (1.2.2)注意上面的8位階數(shù)中須有1位表示階數(shù)的符號，所以階數(shù)值占7位。55浮點數(shù)的四則運算設(shè)是

17、S10由所有形如 0.d1d2d3d4 10p的4位十進制浮點數(shù)的集合，其中1 d19，0 di9，i = 2, 3, 4, 整數(shù)p滿足-9 p10。下面舉例說明S10上的算術(shù)運算。56浮點數(shù)計算特點加減法先對階(將階碼統(tǒng)一為較大者)，后計算，再舍入乘除法先運算再舍入不在計算機數(shù)系中的數(shù)做四舍五入處理57例1.1(1) 0.2015104 + 0.1911102 0.2015104 + 0.0019104 對階 0.2034104 計算(2) 0.2015104 + 0.191110-1 0.2015104 + 0.0000104 對階 0.2015104 計算(3) 0.2015104 -

18、0.2008104 0.0007104 計算 0.7000101 規(guī)范化58例1.1(4) (0.2015104) (0.191110-5) (0.20150.1911) 10-1 對階 (0.3851 10-1) 10-1 計算 0.3851 10-2 規(guī)范化(5) (0.2015104) (0.191110-5) (0.20150.1911) 109 對階 (0.1054 101) 109 計算 0.1054 1010 規(guī)范化59浮點數(shù)計算特點計算過程中應(yīng)該注意絕對值相差懸殊的兩個數(shù)做加減，會造成“大數(shù)吃小數(shù)”的現(xiàn)象；（例2）非常接近的數(shù)相減，會損失掉有效數(shù)字； （例3）相對被除數(shù)來說，絕

19、對值很小的數(shù)做除數(shù)，會產(chǎn)生絕對值很大的數(shù)，甚至溢出； （例5）在運算過程中注意合理安排運算順序，以便提高運算的精度或保護重要的參數(shù)。60例1.2在前面所述的4位十進制浮點計算機（數(shù)集S10）上求解如下一元二次方程 x2 24 x +1 = 0 (1.2.3)按求根公式，此方程的兩個根是在4位十進制浮點計算機上， 0.1196102，于是按照上面求根公式有 x1=0.2396102, x2=0.400010-1143121x143-122x14361下面我們換一種方法進行計算x2，即 (1.2.4)則x2=0.417410-1。事實上，x2的精確解應(yīng)為0.0417393。143121143-12

20、2x62問題631.2.2 1.2.2 誤差來源誤差來源64誤差的來源實際實際問題問題數(shù)學(xué)數(shù)學(xué)模型模型 數(shù)值數(shù)值方法方法程序程序設(shè)計設(shè)計計算機計算機計算計算解答解答模型誤差模型誤差方法誤差方法誤差觀測誤差觀測誤差舍入誤差舍入誤差65例1.3為了計算函數(shù)值ex，| x | 0，并滿足 | e* | = |x* - x| * (1.2.7) 則稱*為近似值x*的絕對誤差限，或簡稱誤差限。69相對誤差定義1.3 設(shè)x為精確值，x*為近似值，則稱比值 (1.2.8)為近似值x*的相對誤差，記作er*（實際應(yīng)用時，常用x*代替上式分母中的x）。xxxxe*70相對誤差限定義1.4 設(shè)*是近似值x*的誤差

21、限，則稱 (1.2.9) 為近似值x*的相對誤差限，此時，有 (1.2.10)*xr*rxxxx71有效數(shù)字定義1.5 如果 | e* | = |x* - x| 0.510-n (1.2.11) 則說x*近似表示x準(zhǔn)確到10-n位（小數(shù)點后第n位），并從此位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。72例1.4取e（e = 2.718281828459 ）的近似值x* = 2.72，則 |2.72 e | 0.001718 0.510-2即x*近似表示e準(zhǔn)確到10-2位，因此具有3位有效數(shù)字。若取e的近似值x* = 2.71828，則 |2.71828

22、 e | 0.0000018 0.510-5即x*近似表示e準(zhǔn)確到10-5位，因此具有6位有效數(shù)字。73有效數(shù)字定義1.6 將x的近似值x*表示為十進制浮點數(shù)的標(biāo)準(zhǔn)形式 x* = 0.d1d2dk 10m (di=0,1,9, d10) (1.2.12)如果 | e* | = |x* - x| 0.510m-n (1.2.13)則說近似值x*具有n位有效數(shù)字。這里n是正整數(shù)，m是整數(shù)。74例若x*=3578.64是x的具有6位有效數(shù)字的近似值，試求x*的誤差限。75有效數(shù)字與相對誤差的關(guān)系定理1.1 若近似值x*具有n位有效數(shù)字，則其相對誤差滿足 (1.2.14)反之，如果x*的相對誤差er*

23、滿足 (1.2.15)則x*至少具有n位有效數(shù)字。*-(1)11102nred*-(1)11102(1)nred761.2.4 1.2.4 誤差分析誤差分析77誤差分析將帶有誤差的數(shù)據(jù)進行計算時，誤差在運算過程中會進行傳播，必然導(dǎo)致計算結(jié)果出現(xiàn)誤差。一般來說，精確值x與近似值x*之間都比較接近，其誤差可以看作是一個小的增量，即可以把誤差看作微分，即 e* = x* - x = dx這表明：x的微分表示x的誤差，ln x的微分表示x的相對誤差xxxxeerlndd*78(1.2.16)(1.2.17)誤差分析根據(jù)上式，可以得到算術(shù)運算的誤差，以x, y兩數(shù)為例 e* (xy) = d (xy)

24、= d x d y = e* (x) e* (y) e* (xy) = d (xy) = y d x + x d y = y e* (x) + x e* (y) er* (xy) = d ln(xy) = d ln(x) + d ln(y) = er*(x) + er*(y)0()()(ddd2*2*yyyxexyeyyxxyyxyxe)0()()()ln(d)ln(dlnd*yyexeyxyxyxerrr79誤差分析而更一般的情況是，當(dāng)自變量有誤差時計算函數(shù)值時也會產(chǎn)生誤差。其誤差可以用函數(shù)的Taylor展開式進行估計。2* *)(2)()()()(xxfxxxfxfxf)()()()()(

25、*xexfxfxfxfe80例1.5已知 由于 的精確值未知，取 1.414進行計算，試問上述3個表達式哪個計算精度最高？f1(x)=(x-1)6f2(x)=99-70 xf3(x)=270991270-991-262281例1.582例1.5830.6320.3680.2640.2080.1680.1600.0400.720例1.6考慮積分 (1.2.25)的近似計算.此積分滿足遞推關(guān)系式 In = 1 nIn-1, (1.2.26)假定我們首先計算出I0的近似值 ，保留3位有效數(shù)字，利用遞推關(guān)系式(1.2.26)依次算出101dxexIxnn0I0I1I2I5I4I6I3I7I84例1.6

26、10=1-1=1-0.632=0.368II21=1-2=1-0.736=0.264II6=0.040I76=1-7=1-0.280=0.720II85例1.6根據(jù)積分公式那么1110100，使得對于一切xRn有214,stxx12stscxxcx21xxn xxxn x（2.5.8）（2.5.9）向量的范數(shù)向量序列收斂性向量序列收斂性定義定義2. 2 設(shè)x(k)= ( x1(k), x2(k), xn(k)T 為Rn 上的一個向量序列(k=1,2,)， x*= ( x1*, x2*, xn*)TRn. 如果對于i=1,2, n 有 則稱向量序列x(k 收斂于向量x*。 215*)(limik

27、ikxx向量的范數(shù)容易證明，x(k) 收斂于向量x*的充要條件是再由(2.5.8)和(2.5.9)式可知，上式成立等價于2160lim*)(xxkk0lim2*)(xxkk0lim1*)(xxkk矩陣范數(shù) 定義定義2.3設(shè)設(shè) 為為A的實值函數(shù)，若它滿足下的實值函數(shù)，若它滿足下列條件列條件（1）正定性）正定性 ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)A=0時等號成立時等號成立（2）齊次性）齊次性（3）三角不等式）三角不等式 則稱則稱 為為 上的一個上的一個矩陣范數(shù)矩陣范數(shù)（或矩陣模）（或矩陣模）, 的值稱為矩陣的值稱為矩陣A的范數(shù)的范數(shù)217n nR0 A ()kAkAkR C ,n nABABA BR ( )n

28、nARN AA()N AAAn nAR 矩陣范數(shù)相容范數(shù)相容范數(shù)218 , ,n nnn nABABA B RAxAxxR A R （ 2.5.13）（ 2.5.14）矩陣范數(shù)算子范數(shù)算子范數(shù)最常用的是利用向量范數(shù)來定義的矩陣范數(shù)矩陣范數(shù)稱之為矩陣A的算子范數(shù)算子范數(shù)，其中2191,2,p 01maxmaxppppxxpAxAAxx（ 2.5.15）矩陣范數(shù)證明：容易證明，由(2.5.15)式所定義的函數(shù)滿足定義2.3的三個條件，故它是矩陣范數(shù)。另外，當(dāng)x=0時， (2.5.14)式顯然成立。對任意的x0,兩邊乘以即為(2.5.14)式。220定理2.3由(2.5.15)式所定義的矩陣范數(shù)為相

29、容范數(shù):nnpRR0maxpppyppAxAyAxypx矩陣范數(shù)再來證(2.5.13)式。注意到由(2.5.14)式有定理證完。221,n nA BRnB xR111m ax m ax m ax pppppxppxppxppABABxABxABxAB矩陣范數(shù)定理2.4對于由(2.5.15)式所定義的矩陣范數(shù)下列等式成立：其中AT表示A的轉(zhuǎn)置矩陣。22211111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2(2.5.16)(2.5.17)(2.5.18)矩陣范數(shù)證明先證(2.5.16)式。首先，對任意滿足 的xRn，因為 ，故有2231x1jx

30、x1111111max ()max max()maxniijji ni njnnijjiji ni njjAXAxa xaxa 矩陣范數(shù)另一方面，設(shè)第k行為元素絕對值和最大的行，即則可令此時，x滿足且有2241x111maxnnkjiji njjaa 11111()()maxnnkkjjkjkjjjnnkjiji njjAxa xa sng aaa sgn()jijxa矩陣范數(shù)再證等式(2.5.18)，注意當(dāng) 時，ATA是對稱非負定矩陣，故ATA有完全正交的特征向量系 ，即其中 為ATA的特征值22512,nv vvn nAR22(,)( ,)TTTAxAx Axx A Axx A Ax0,

31、( ,)1, Tii iijijA Avvv vij10n矩陣范數(shù)對于任意的xRn，借助于特征向量系可表示為且從而有2261niiixv2221( , )niixx x112111(, )(,) =(,)nnTTjji ijinnnjjji iiijiiA Ax xA Avvvv 矩陣范數(shù)227由于故有上式說明 是 的上界，并且這個上界在x=v1時達到。定理證完。2221111nnnniiiiiii 121222(, )TnxA Ax xAxx122A xx矩陣范數(shù)22811111m a xm a xnijinjnijjniAaAa2A(ATA之最大特征值之最大特征值)1/2行和范數(shù)行和范數(shù)列

32、和范數(shù)列和范數(shù)譜范數(shù)譜范數(shù)01maxmaxppppxxpAxAAxx（2.5.15）譜半徑矩陣A的特征值的按模最大值稱為A的譜半徑記作，即其中是A的特征值。定理1.6對任意 ，有2291( )maxii nA ( )Ain nAR( ) 1,2,pAAp譜半徑由譜半徑的定義,矩陣的2范數(shù)可記為當(dāng)A是實對稱矩陣時，由（1.4.18）式有這也就是說，此時A的2范數(shù)與該矩陣的譜半徑相等。2302()TAA A22()()( )TAA AAA第2章 解線性方程組的數(shù)值法2.1 引入2.2 Gauss消元法2.3 矩陣的三角分解2.4 消元法在計算機上的實現(xiàn)2.5 向量和矩陣范數(shù)2.6 矩陣的條件數(shù)與病

33、態(tài)方程組矩陣的條件數(shù)與病態(tài)方程組2.7 迭代法2312.6 矩陣的條件數(shù)與病態(tài)方程組232病態(tài)方程組233例2.2 令 , 并設(shè)123123(,) ,(,)TTxxxxbb bb1/2 1/3 1/41/3 1/4 1/51/4 1/5 1/6A病態(tài)方程組234令Ly = b, 可解得于是，由Ux = y, 可解得112133123121546ybybbybbb11232123312372240180240900720180720600 xbbbxbbbxbbb病態(tài)方程組321332123211600720180 72090024018024072 bbbxbbbxbbbx235),(321b

34、bbb)1500,1860,492( xx病態(tài)方程組236定義 如果矩陣A或常數(shù)項b的微小變化,引起方程組Ax=b的巨大變化,則稱此方程組為“病態(tài)病態(tài)”方程組方程組,矩陣A稱為“病態(tài)”矩陣，否則稱方程組為“良態(tài)”方程組，A稱為“良態(tài)”矩陣。條件數(shù)237設(shè)A為非奇異矩陣,用x表示Ax=b的精確解,而 是擾動方程組的精確解.由Ax=b和(1.5.1)兩式相減,可知解的誤差 滿足方程由此x A xbbA xbxx x 1xAb條件數(shù)238利用矩陣的范數(shù)性質(zhì),有另外,由Ax=b又有由(1.5.2)式和(1.5.3)式,便可得:1pppxAbppppAxAxb1()ppppppxbAAxb條件數(shù)239設(shè)

35、 是下面擾動方程組的精確解。由Ax=b和(1.5.1)兩式相減，可知解的誤差 滿足方程由此x ()AA xb)(-xxAxAxx x )(-1xxAAx條件數(shù)240于是有即pppppxxAAxxAAx-1-1)(-ppppppAAAAxxx1 -條件數(shù)241定義2.5 設(shè) 為可逆矩陣,稱 為矩陣A在范數(shù) 意義下的條件數(shù)條件數(shù).矩陣A的條件數(shù)越大，方程組的擾動誤差對方程組的解的影響越嚴重。因此稱條件數(shù)過大的方程組為病病態(tài)方程組。態(tài)方程組。n nARp1( )pppCondAAA第2章 解線性方程組的數(shù)值法2.1 引入2.2 Gauss消元法2.3 矩陣的三角分解2.4 消元法在計算機上的實現(xiàn)2.

36、5 向量和矩陣范數(shù)2.6 矩陣的條件數(shù)與病態(tài)方程組2.7 迭代法迭代法242 迭代法是求解線性代數(shù)方程組的另一類方法。由于它具有保持迭代矩陣不變的特點，因此迭代法特別適合求解大型稀疏系數(shù)矩陣的方程組。2.7 迭代法243迭代法的一般形式考慮求解線性代數(shù)方程組為了采用迭代法，首先要將方程組（2.7.1）改寫成等價的形式其中 為已知向量， 代表未知向量。244Axb(2.7.1),n nnijMRMmgRnxRxMxg(2.7.2)迭代法的一般形式給定初始近似值 ，定義向量序列稱為迭代序列迭代序列，并稱M為迭代矩陣迭代矩陣。245(0)nxR( )kx(1)( ) 0,1,2.kkxMxgk（2.

37、7.3）迭代法的一般形式如果當(dāng)k時， 有極限，設(shè)為 ,則在等式（2.7.3）兩端取極限可得此式表明迭代序列的極限恰為方程組的解。因此，如果迭代序列收斂，則當(dāng)k充分大時，可將x(k)取作方程組的近似解。246( )kx*nxR(1)( ) 0,1,2.kkxMxgk（2.7.3）( )kx*xMxg（2.7.4）迭代法的收斂性利用迭代公式（2.7.3）構(gòu)造序列 ，以求得方程組（2.7.2）的近似解的算法稱為解（2.7.2）式的簡簡單迭代法單迭代法。若迭代序列 收斂，就稱此迭代法是收斂的。247( )kx( )kxxMxg(1)( ) 0,1,2.kkxMxgk（2.7.3）(2.7.2)迭代法的

38、收斂性顯然，只有收斂的迭代法才能使用，因此必須回答在何種條件下，由公式（2.7.3）所定義的 為收斂的向量序列248( )kx(1)( ) 0,1,2.kkxMxgk（2.7.3）迭代法收斂性為討論迭代法的收斂性，引入誤差向量 (k) = x (k) - x *則利用(2.7.2)和(2.7.4)可得 (k+1) = x (k+1) - x *= Mx (k) + g (Mx* + g) = M (x (k) x*) = M(k)于是可以迭代得出 (k+1) = M(k) = M 2(k-1) = = M k+1(0) (2.7.5)迭代法收斂，即 (k+1)0 (零向量) (k)。由于x(0

39、)是任給的，所以其充要條件是M k+10 (零矩陣) (k)。249迭代法的收斂性( )(1)kkxMxg250(1)( ) 0,1,2.kkxMxgk*xM xgxMxgAxb(2.7.1)(2.7.2)(2.7.4)(2.7.3)迭代法的收斂性根據(jù)上式可以判定，對任意x(0)即 的充分必要條件是 （零矩陣），k，由此得到下面結(jié)果.251( )*kxx( )0kM ( )*0kxx( )*(0)*(), 0,1,2,.kkxxM xxk迭代法的收斂性定理定理2.6 設(shè)M = (mij) R nn, 則M k0(k)的充要條件是(M) 1。定理定理2.7 迭代法(2.7.3)對任何初始近似值x

40、(0)均收斂的充分必要條件是迭代矩陣M的譜半徑(M) 1。推論推論2.1 若|M|1（|允許為任何一種相容范數(shù)）, 則迭代法(2.7.3)收斂。252(1)( ) 0,1,2.kkxMxgk(2.7.3)迭代法的收斂速度定理 當(dāng) 時，由迭代法（2.7.3）式所定義的序列滿足如下估計式：證明略.2531H( )kx( )*( )(1)( )*(1)(0)11kkkkkHxxxxHHxxxxH一般迭代法的求解步驟依據(jù)方程組分離x得到迭代格式判斷迭代格式是否收斂迭代求解滿足終止條件,迭代結(jié)束254xMxg( 1)( )kkxM xg()(1)kkxx()1M1M雅可比迭代法例例2.3 求解方程組若將

41、方程組表示成如下形式2551552218474zyxzyxzyx4782145152xyzyxzzxy7421 481525yzxxzyxyz雅可比迭代法 給出了雅可比迭代格式 如果從初始點(x0, y0, z0) = (1, 2, 2) 開始，即將x0= 1, y0= 2, z0= 2代入（1.6.8）每個方程的右邊，可得到如下新值：256( )( )(1)( )( )(1)( )( )(1)7421 481525kkkkkkkkkyzxxzyxyz(1)(1)(1)72-241.7521 4283.375152253.00 xyz雅可比迭代法考慮方程組 Ax=b 其中 是非奇異的, 為已知

42、向量。將矩陣A寫成如下 A=D-L-U其中 為對角陣, -L, -U分別為A的嚴格下、上三角部分構(gòu)成的三角陣。257n nARnbR11(,)nnDdiag aa雅可比迭代法2131321200000nnaLaaaa 258121312321,00000nnnnaaaaaUa雅可比迭代法當(dāng)D非奇異,即aii0(i=1,2,n)時,可將方程組Ax=b寫成于是可得迭代格式稱此格式為求解方程組Ax=b的雅可比迭代法.注意到L+U=D-A,故(2.7.9)式也可寫成25911()xDLU xD b(2.7.9)(1)1( )1() 0,1,2,.kkxD L U xD bk(2.7.10)11()xI

43、D A xD b雅可比迭代法Jacobi方法的迭代矩陣為Jacobi迭代法的分量形式為26011()HDL UID A 1(1)( )( )111() 1,2, ,1,2, .inkkkiijjijjijj iiixa xa xbin ka (2.7.11)雅可比迭代法例2.4 求解方程組2611552218474zyxzyxzyx雅可比迭代法例2.4 求解方程組2621552218474zyxzyxzyx雅可比迭代法263kx(k)y(k)z(k)01.02.02.01-1.53.3755.026.6872.516.375334.68758.015625-17.254-46.61718817

44、.8125-123.734385-307.929688-36.150391211.281256502.62793-124.9296881202.56836高斯賽德爾迭代法簡單迭代法(2.7.3)的分量形式是可以用這些新值來計算 , 于是可得迭代格式這種方法稱為賽德爾迭代法.2641(1)( )( )1 1,2, , .inkkkiijjijjijj ixh xh xgin(1)kix1(1)(1)( )1 inkkkiijjijjijj ixh xh xg(2.7.12)高斯賽德爾迭代法對雅可比迭代(2.7.11)式運用賽德爾技巧得到稱(2.7.13)式為高斯賽德爾迭代法,其矩陣形式為并可整理

45、成一般迭代法的形式2651(1)(1)( )111() 1,2, .inkkkiijjijjijj iiixa xa xbina (2.7.13)(1)1(1)( )()kkkxDLxUxb(1)1( )1()()kkxDLUxDLb(2.7.14)高斯賽德爾迭代法例例2.5 試用Jacobi迭代法和Gauss-Seidel迭代法求解下面線性方程組，并分析其收斂性266123123123226+4223xxxxxxxxx 高斯賽德爾迭代法例例2.5 試用雅可比迭代法和高斯-賽德爾迭代法求解下面線性方程組，并分析其收斂性解解：雅可比迭代法和高斯-賽德爾迭代法的迭代公式分別為：2671231231

46、23226+4223xxxxxxxxx 111(1)( )( )23(1)( )( )23(1)( )( )326224322kkkkkkkkkxxxxxxxxx 111(1)( )( )23(1)(1)( )23(1)(1)(1)326224322kkkkkkkkkxxxxxxxxx 高斯賽德爾迭代法都將都將 作為初值進行計算，結(jié)果見表2.2。表表2.2 例例2.5計算結(jié)果計算結(jié)果268(0)(0)(0)123(,)(0,0,0)xxx迭代次數(shù)迭代次數(shù)Jacobi迭代法迭代法G-S迭代法迭代法kx(k)y(k)z(k)x(k)y(k)z(k)000000016-4-3621324-11-16

47、-7-49321390372514213-422-175-1197高斯賽德爾迭代法269下面分析其收斂性，設(shè)Jacobi方法和Gauss-Seidel方法的迭代矩陣分別為1022()101220JMDL U1022()021086G SMDLU高斯賽德爾迭代法270下面分析其收斂性，設(shè)雅可比方法和高斯-賽德爾方法的迭代矩陣分別為1022()101220JMDL U1022()021086GMDLU分別計算兩個矩陣的特征值即1 =2 =3=0, 故(MJ) = 00,求開方值的問題就是要解方程 x2-a=0這樣歸結(jié)出的是個非線性方程，從初等數(shù)學(xué)的角度來看它的求解有難度。該如何化難為易呢？2793

48、.1 引入設(shè)給定某個預(yù)報值x0,希望借助于某種簡單方法確定校正量x，使校正值x1=x0+x能夠比較準(zhǔn)確地滿足所給方程x2-a=0，即有280axx203.1 引入設(shè)給定某個預(yù)報值x0,希望借助于某種簡單方法確定校正量x，使校正值x1=x0+x能夠比較準(zhǔn)確地滿足所給方程x2-a=0，即有一般來說，x是一個小量，因此忽略掉x的平方項，上述方程便是一個關(guān)于x 的一次方程，據(jù)此寫出x ，從而對校正值x1=x0+x 有281axx2000121xaxx3.1 引入反復(fù)施行這種預(yù)報校正方法，即可導(dǎo)出開方公式從給定的某個初值x00出發(fā)，利用上式反復(fù)迭代，即可獲得滿足精度要求的開方值282kkkxaxx211

49、a3.1 引入283例例3.1：用開方算法求根號 =？誤差到10-6解：分別取x0=9和x0=20,90kkkxaxx211ixixi09.00000020.00000019.50000012.25000029.4868429.79846939.4868339.49178949.4868339.48683459.4868339.486833第三章 非線性方程（組）的數(shù)值解3.1 引入3.2非線性方程問題非線性方程問題3.3二分法3.4不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法284例例3.2 考慮下面的非線性方程(1) ex+1=0， (2) x6-2x5-8x4+14x3+

50、11x2-28x+12=0,(3) cosx=0;285例例3.2 考慮下面的非線性方程(1) ex+1=0，此方程無解(2) x6-2x5-8x4+14x3+11x2-28x+12=0,(3) cosx=0;(1)式無解；(2)式有三個解，x=1，-2，3，無論x取值的區(qū)間怎樣變化，只要它包含-2,3這個區(qū)間，解的性質(zhì)和個數(shù)不變。但這三個解的性質(zhì)又各不相同，x=3是一個單根，x= -2是兩重根，x=1則是三重根。(3)式隨x的取值范圍不同，解的個數(shù)也不同。事實上，在整個實數(shù)軸上有無窮多個解。在討論非線性問題時，通?？偸且鼜娬{(diào)“ “定義域定義域” ”，往往要求的是自變量在一定范圍內(nèi)的解，道理

51、就在于此。286在科學(xué)研究和工程設(shè)計中, 經(jīng)常會遇到的一大類問題是非線性方程 f(x) =0 的求根問題，其中f(x)為非線性函數(shù)。方程f(x)=0的根, 亦稱為函數(shù)f(x)的零點。 287如果f(x)是多項式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角方程，指數(shù)、對數(shù)方程等）。一般稱n次多項式構(gòu)成的方程 為n次代數(shù)方程，當(dāng)n1時,方程顯然是非線性的288111000 ()nnnnna xaxa xaa 給定如下非線性方程組 i=1,2,n （3.2.1)引入向量、向量函數(shù)記號 (3.2.2)則方程組可改為 F(x)=0 當(dāng)n=1時，方程組(3.2.1)是一個非線性方程式 f(x) = 0 (

52、3.2.3)2890),(21nixxxf12nxxxx12( )( )( )( )nf xfxF xfx000 0定義定義3.1 設(shè)有x*使f(x*)=0則稱x*為方程(3.2.3)的根或根或零點零點。若存在正整數(shù)m,使f(x)=(x-x*)mg(x) (3.2.4)且0g(x*)+，則稱x*為(3.2.3)式的m重根重根。當(dāng)m=1時，x*為單根，這時x*滿足條件f(x*)=0, f(x*) 0;290第三章 非線性方程（組）的數(shù)值解3.1 引入3.2非線性方程問題3.3二分法二分法3.4不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法291292 二分法的基本思想二分法的基本思

53、想: 首先確定有根區(qū)間,將區(qū)間二等分, 通過判斷f(x)的符號, 逐步將有根區(qū)間縮小, 直至有根區(qū)間足夠地小, 便可求出滿足精度要求的近似根。293二分法294例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零實根的近似值，使誤差不超過10-2.解295例3.3 用二分法求方程f(x)=sinx-x2/4=0的非零實根的近似值，使誤差不超過10-2.解nanbnxn+1f(xn+1)01.521.750.21836111.7521.8750.075179621.87521.9375-0.049622831.8751.93751.902650.040420841.906251.937

54、51.9218750.15601451.9218751.93751.92968750.00536340第三章 非線性方程（組）的數(shù)值解3.1 引入3.2非線性方程問題3.3二分法3.4不動點迭代法不動點迭代法3.5牛頓迭代法3.6解非線性方程組的牛頓迭代法2963.4.13.4.1不動點迭代法不動點迭代法不動點迭代法是一種逐次逼近的方法，它的基本思想是通過構(gòu)造一個遞推關(guān)系式 (迭代格式) ，計算出根的近似值序列,并要求該序列收斂于方程的根.將方程f(x)=0改寫成等價形式 x= (x) (3.4.1)定義定義3.2 稱所有滿足方程x = (x)的點x，為此方程的方程的不動點不動點。297取初始

55、迭代值x0，記x1 = (x0), x2 = (x1), , 一般有 (3.4.2)記數(shù)列x0, x1 ,xk,為xk，當(dāng)k充分大時，如果xk有極限x*存在，即 (3.4.3)則對(2.1.6)式兩邊同時取極限，得 (3.4.4)這表明x*為等價方程x = (x)的不動點，即x*為方程f(x)=0的根。298kkxx1*kkxx lim *kkkk*xxxxlimlim1 上述求解方程f(x)=0的根的近似值的過程，稱為不動點迭代不動點迭代法法，其中(3.4.2)式中的(x)稱為迭代函數(shù)迭代函數(shù)，x0稱為迭代的初迭代的初始值始值，公式(3.4.2)稱為迭代格式迭代格式或迭代過程迭代過程，xk稱

56、為根x*的第k次近似值，xk稱為迭代數(shù)列迭代數(shù)列。若極限式(3.4.3)成立，則稱此迭代法為收斂的收斂的，否則稱為發(fā)散的發(fā)散的。 應(yīng)用迭代法求方程根的基本問題是：1）化等價方程，構(gòu)造迭代函數(shù)；2）研究迭代數(shù)列xk的收斂性、收斂速度及誤差估計。2993.4.2迭代法的幾何解釋迭代法的幾何解釋 通常將方程f(x)=0化為與它同解的方程x = (x)的方法不止一種,有的收斂,有的不收斂,這取決于(x)的性態(tài),方程x = (x)的求根問題在幾何上就是確定曲線y= (x)與直線y=x的交點P*的橫坐標(biāo)。(a)(b)300迭代法的幾何意義迭代法的幾何意義 3013023.4.3 3.4.3 迭代法的收斂迭

57、代法的收斂定理定理3.1（收斂性定理收斂性定理）假定方程x = (x)滿足： 1) (x)在a,b上連續(xù)；2)當(dāng)xa,b時, (x) a,b；3) (x)存在，且對任取xa,b有 (3.4.6)則方程x=(x) 在a,b上存在唯一不動點x*，且對任取x0a,b，由迭代格式 xk+1=(xk) , k=0,1,2,所定義xk收斂于唯一不動點x* ，即 同時下列誤差估計式成立 1L x*kkxx limkkkxxLxx1*11(3.4.7)01*1xxLLxxkk(3.4.8)證明證明：令h(x)=x-(x)，則h(x)在a,b上連續(xù)且可微。根據(jù)定理3.1的條件(2)知h(a)0, h(b)0，由

58、連續(xù)函數(shù)的介值定理，必有x*a,b，使h(x*)=0，即x*=(x*)。因此x*便為方程x=(x)于a,b內(nèi)的不動點。假設(shè)另有 ，且 ，使 ，則由拉格朗日中值定理，得 其中 介于x*和 之間，因x*= ，故只有 ，這與定理3.1中|(x)|L1矛盾303,bax*xx )(xx)()()(*xxxxxxx0)(1)(*xxx1)(對任xa,b，由|(x)|L1得即對任xa,b， 。注意及304*111*2*120()()()()0kkkkkkkxxxxxxL xxL xxL xxk *limxxkkkkxxLxx*1*kkkkxxxxxx11*kkkxxxx11*得即(3.4.7)式成立，由于

59、再利用已證(3.4.7)式，即知(3.4.8)式成立。3051*1kkkkxxxxxxkkxxLxx*(1)kL xx111)()(kkkkkkxxLxxxx01212xxLxxLkkk306定理3.1給出了迭代法收斂的充分條件且十分適用。首先，對有根區(qū)間a,b并沒有限制其范圍大小，只要滿足條件1）2）3）即可，故a,b可取為任意有限大小的區(qū)間。因此，可視此定理為大范圍收斂定理大范圍收斂定理。其次，在收斂性的證明過程中可以看出，迭代序列收斂速度的快慢取決于L的大小，L越小，收斂越快。結(jié)論中的第一個誤差估計式可以作為上機控制迭代中止的一個條件；第二個誤差估計式可用于估計滿足指定誤差精度所需的迭代

60、次數(shù)k.307事實上，由定理的證明過程可知，定理的條件(3)可放寬為：若(x) 在a, b滿足Lipschitz條件，即對a, b 上的任意兩點x1, x2, 有且Lipschitz常數(shù)L1，則定理依然成立。 2121Lxxxx例3.4求方程 f(x)=xex-1=0 (或x=e-x) 在1/2,ln2中的解。若要求迭代次數(shù)k至少應(yīng)為多少？3086*10kxx解：取迭代函數(shù) ，當(dāng)x1/2,ln2時， (x)連續(xù)可微，又 ，故(x)為單調(diào)下降函數(shù)，且有又可見，(x)滿足定理2.1的全部條件，因此x=e-x于1/2,ln2有唯一不動點，且由 所定義的迭代序列xk收斂到此不動點。取初值x0=1/2，