數(shù)值分析與算法_第1講_引論

1、數(shù)值分析與算法數(shù)值分析與算法林玉蘭電子科學(xué)系 1學(xué)習(xí)和了解科學(xué)計算的橋梁學(xué)習(xí)和了解科學(xué)計算的橋梁2數(shù)值分析數(shù)值分析 能夠做什么？Introduction 研究使用計算機求解各種數(shù)學(xué)問題的研究使用計算機求解各種數(shù)學(xué)問題的數(shù)值方法（近似方法），對求得的解的數(shù)值方法（近似方法），對求得的解的精度進行評估，以及如何在計算機上實精度進行評估，以及如何在計算機上實現(xiàn)求解等現(xiàn)求解等3一、一、 計算機解決實際問題的步驟計算機解決實際問題的步驟建立數(shù)學(xué)模型建立數(shù)學(xué)模型選擇數(shù)值方法選擇數(shù)值方法編寫程序編寫程序上機計算上機計算 數(shù)值分析是一門內(nèi)容豐富、研究方法數(shù)值分析是一門內(nèi)容豐富、研究方法深刻、實用性較強的深刻、

2、實用性較強的數(shù)學(xué)課程數(shù)學(xué)課程。 研究對象：研究對象：從科學(xué)與工程問題中抽象歸納從科學(xué)與工程問題中抽象歸納出來的數(shù)學(xué)問題。出來的數(shù)學(xué)問題。4通信衛(wèi)星覆蓋地球面積通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型數(shù)學(xué)模型實際問題實際問題獲取數(shù)據(jù)獲取數(shù)據(jù)數(shù)值方法、程序數(shù)值方法、程序數(shù)據(jù)結(jié)果數(shù)據(jù)結(jié)果將地球考慮成將地球考慮成一個球體一個球體, 設(shè)設(shè)R為地球半為地球半徑徑,h為衛(wèi)星高為衛(wèi)星高度度,D為覆蓋面為覆蓋面在平面的投影在平面的投影 DdxdyyxRR2225舉例1.求下列方程的根或零點：22 sin1 0 xxx （第2章的內(nèi)容：非線性方程求根）Can you solve：100(1)0 x Can you solve

3、：100999897961004950161700392122510010 xxxxxx 62. 怎么求解下列積分？210 xedx（第7章的內(nèi)容：數(shù)值積分與數(shù)值微分）7算法 為了用計算機解決數(shù)學(xué)問題而構(gòu)造的能夠用為了用計算機解決數(shù)學(xué)問題而構(gòu)造的能夠用數(shù)值計算的實施方法。即把對數(shù)學(xué)問題的解法歸數(shù)值計算的實施方法。即把對數(shù)學(xué)問題的解法歸結(jié)為只有加、減、乘、除等基本運算，并有確定結(jié)為只有加、減、乘、除等基本運算，并有確定運算次序的完整而準(zhǔn)確的描述。運算次序的完整而準(zhǔn)確的描述。特點特點 構(gòu)造性構(gòu)造性 能夠通過數(shù)值演算能夠通過數(shù)值演算 一種實施方法一種實施方法8評價標(biāo)準(zhǔn)評價標(biāo)準(zhǔn)(2) 存儲量的大小存儲

4、量的大小評價標(biāo)準(zhǔn)評價標(biāo)準(zhǔn)(3) 邏輯結(jié)構(gòu)是否簡單邏輯結(jié)構(gòu)是否簡單算法的優(yōu)劣9評價標(biāo)準(zhǔn)評價標(biāo)準(zhǔn)(1) 計算量的大小計算量的大小Top ten algorithms of the century“We tried to assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century”Editors of IEEE Computational Science and Engineering, Jan

5、. 2000 (后被后被SIAM轉(zhuǎn)載轉(zhuǎn)載)1.1.1946 1946 Los AlamosLos Alamos國家實驗室的國家實驗室的J. von NeumannJ. von Neumann, , S. VlamS. Vlam和和N. MetropolisN. Metropolis編的編的MetropolisMetropolis算法算法, ,即即Monte CarloMonte Carlo方法方法（“隨機漫步隨機漫步”）2.2.1947 1947 蘭德（蘭德（RANDRAND）公司的）公司的G. DantzigG. Dantzig創(chuàng)造的線性規(guī)劃的單創(chuàng)造的線性規(guī)劃的單純型算法（純型算法（simp

6、lex methodsimplex method）3.3.19501950 美國國家標(biāo)準(zhǔn)局?jǐn)?shù)值分析所的美國國家標(biāo)準(zhǔn)局?jǐn)?shù)值分析所的M. HestenesM. Hestenes, , E. E. StiefelStiefel和和C.C. LanczosLanczos開創(chuàng)的開創(chuàng)的KrylovKrylov子空間迭代法子空間迭代法4.4.19511951 橡樹嶺（橡樹嶺（Oak RidgeOak Ridge）國家實驗室的）國家實驗室的A. House-holderA. House-holder形式化的矩陣計算的分解方法形式化的矩陣計算的分解方法( (矩陣的各種分解矩陣的各種分解) )10Top ten

7、algorithms of the century5.5.19511951 IBM IBM由由J.J. BackusBackus領(lǐng)導(dǎo)的小組研制領(lǐng)導(dǎo)的小組研制FortranFortran最優(yōu)編譯器最優(yōu)編譯器6.6.1959-611959-61 倫敦倫敦Ferranti Ltd.Ferranti Ltd.的的J.G.F. FrancisJ.G.F. Francis發(fā)明發(fā)明QRQR算法，算法，能穩(wěn)定的計算矩陣特征值能穩(wěn)定的計算矩陣特征值7.7.1962 1962 倫敦倫敦Elliot Brothers,Elliot Brothers, Ltd.Ltd.的的Tony HoareTony Hoare提出

8、快速排提出快速排序算法（序算法（QuicksortQuicksort）8.8.19651965 IBM Watson IBM Watson研究中心的研究中心的J. CooleyJ. Cooley與與U. PrincetonU. Princeton及及AT&T Bell Lab.AT&T Bell Lab.的的J. TurkeyJ. Turkey共同提出了的共同提出了的FFTFFT算法算法9.9.19771977 Brigham Young Brigham Young大學(xué)的大學(xué)的H.H. FergusonFerguson和和R. ForcedeR. Forcede提出的提出的整數(shù)

9、關(guān)系偵察算法（整數(shù)關(guān)系偵察算法（integer relation detectioninteger relation detection）10.10.19871987 Yale Yale大學(xué)的大學(xué)的L. GreengardL. Greengard和和V.V. RokhlinRokhlin發(fā)明了快速多發(fā)明了快速多極算法極算法(fast multipole algorithm)(fast multipole algorithm)除了除了No. 5, 7, 9外，都屬于或涉及數(shù)值計算的范疇外，都屬于或涉及數(shù)值計算的范疇!11數(shù)值分析的特點121. 近似：由此產(chǎn)生“誤差” 在計算數(shù)學(xué)和應(yīng)用數(shù)學(xué)中一個有

10、趣的問在計算數(shù)學(xué)和應(yīng)用數(shù)學(xué)中一個有趣的問題：什么是題：什么是零零？2. 與計算機不能分離：上機實習(xí)（掌握一門語言：C語言，會用Matlab）誤差131. 來源與分類來源與分類 ( Source & Classification )u模型誤差模型誤差 (Modeling Error ): 從實際問題中抽象出數(shù)學(xué)模型從實際問題中抽象出數(shù)學(xué)模型 u觀測誤差觀測誤差 (Measurement Error): 通過測量得到模型中參數(shù)的值通過測量得到模型中參數(shù)的值 u方法誤差方法誤差 (截斷誤差截斷誤差 Truncation Error): 求近似解。求近似解。求解數(shù)學(xué)求解數(shù)學(xué)模型時，用簡單代替復(fù)

11、雜模型時，用簡單代替復(fù)雜, ,或者用有限過程代替無限過程所引起或者用有限過程代替無限過程所引起的誤差的誤差u舍入誤差舍入誤差 (Roundoff Error): 機器字長有限，機器字長有限，通常用四舍五入通常用四舍五入的辦法取近似值，由此引起的誤差的辦法取近似值，由此引起的誤差. . 誤差與有效數(shù)字誤差與有效數(shù)字 (Error and Significant Digits)u 絕對誤差絕對誤差 ( absolute error )*( ) e xx x其中其中 x*為精確值，為精確值，x為為x*的近似值。的近似值。 10006074302.dxex例如：例如：*xx工程上常記為工程上常記為|

12、( )|e x的上限記為的上限記為 , , 稱為稱為絕對誤差限絕對誤差限( accuracy ) u 相對誤差相對誤差 ( relative error )*()()re xexx14 稱稱r( (x) )為為相對誤差限相對誤差限。由于精確值 x*一般是未知的 如果存在一個適當(dāng)小的正數(shù)如果存在一個適當(dāng)小的正數(shù)r r ，使得，使得 rrxxxxxexe )()( )|rxxx 的的相對誤差限相對誤差限常定義為常定義為15u有效數(shù)字有效數(shù)字 (significant digits)用科學(xué)計數(shù)法，記用科學(xué)計數(shù)法，記 ( (其中其中 ）若若 （即（即 的截取按四舍五入規(guī)的截取按四舍五入規(guī)則），則稱則）

13、，則稱 為有為有n 位有效數(shù)字，精確到位有效數(shù)字，精確到 。12010mnx.a aa 01 anm.xx 1050|*naxnm 103.1415926535897932;*3.1415例：例：問：問： 有幾位有效數(shù)字？請證明你的結(jié)論。有幾位有效數(shù)字？請證明你的結(jié)論。* 131 40 3141510and*0 5100 510*., | |.證明證明:有有4 位有效數(shù)字位有效數(shù)字,精確到小數(shù)點后第精確到小數(shù)點后第 3 位位.16一個數(shù)有效數(shù)字指從左到右第一位非零數(shù)字開始的所一個數(shù)有效數(shù)字指從左到右第一位非零數(shù)字開始的所有數(shù)字。有數(shù)字。有效數(shù)字有效數(shù)字和相對誤差的關(guān)系和相對誤差的關(guān)系Th1.

14、若近似數(shù)若近似數(shù) x 有有n 位有效數(shù)值，則其相對誤差限為位有效數(shù)值，則其相對誤差限為(1)11|( )|102nrexa反之，若反之，若x 的相對誤差限滿足：的相對誤差限滿足：則則x 至少有至少有n 位有效數(shù)字。位有效數(shù)字。(1)11|( )|102(1)nrexa證：證：記記則則所以所以121210(101010)mnnxaaa 111110|(1) 10mmaxa*1(1)211110|1|( )|10|102m nnrmxxexxaa反之易得。反之易得。17注：注：定理表明，有效數(shù)字的位數(shù)越多，相對誤差越小定理表明，有效數(shù)字的位數(shù)越多，相對誤差越小18200.1%例：要使的近似值的相對

15、誤差限小于，至少要取幾位有效數(shù)字？*1113311102204.4,4,4,0.125 10100.1%2040.1%nrrnaan 解：設(shè)取位有效數(shù)字，由定理 ，。由于知故只要取就有即只要對的近似值取位有效數(shù)字，其相對誤差限就小于。數(shù)值計算的誤差估計191、四則運算、四則運算*1212()()xxxx兩個近似數(shù)與，其誤差分別為及，它們進行加、減、乘、除運算得到的誤差分別為121212122112211222()()();()()();()()()xxxxx xxxxxxxxxxxx20.220530010 , VVRI例 若電壓，電阻求電流并計算其誤差限及相對誤差限。*22200.7333(

16、 ) 300()()()220 10300 50.0411( )900000.73330.0411( )0.0411()6%0.7333rVIARVRRVIRAIAI解：（）所以21. =110 m-0.2 -0.1 lll lmd dmsld已測得某場地長的值為 ，寬d =80m,已知，。試求面積的絕對誤差限與相對誤差限。例2()()( ) 110(0.1)80(0.2)27()()()()27 0.31%8800rslddlmssssl d解：由誤差限乘法公式故222、函數(shù)誤差、函數(shù)誤差 當(dāng)自變量有誤差時計算函數(shù)值也產(chǎn)生誤差，可以利用函數(shù)的泰勒展開式進行估計。2( )()( )( ()(

17、)( )()() ()()2()()()()().f xxxf xf xf xff xf xfxxxfxfxxf xfxx設(shè)是一元函數(shù)， 的近似值為，以近似，其誤差界記作，可用泰勒展開并取絕對值得假定與的比值不太大，可忽略的高階項，于是可得計算函數(shù)的誤差限（）（ ）23 0ln1 (ln ),1 (ln(x )()()rxxxxxxxx例 設(shè), 的相對誤差限為 ，求的誤差限。解：即有24121212121121211212(,),( (,)()()( (,)()( (,)()(,)(,nnnnnkkknnkrrnkknnf xxxxxxxxxff xxxxxf xxxfxf xxxxf xxx

18、f xxx當(dāng)，是多元函數(shù)， ，的近似值為，則誤差限 ，相對誤差限 ，) =110 m-0.2 -0.1 lll lmd dmsld已測得某場地長的值為 ，寬d =80m,已知，。試求面積的絕對誤差限與相對誤差限。例2,()( )() 80(0.2)110(0.1)27()()()27()0.31%8800rssslddlldsssldldmsssl ds解：因由誤差限函數(shù)公式故25210.12sgtgtsts設(shè)，假定 是準(zhǔn)確的，而對的測量有的誤差，證明當(dāng) 增加時， 的絕對誤差增加，而相對誤差卻減少。例2210.1,( )2()( )0.1()0.10.2()1( )2rtsg tsgttgts

19、gtsstg ttt解：由題意知（ ）絕對誤差限相對誤差限由于 增加時，其近似值 也增加，因此結(jié)論成立。26一、病態(tài)問題與條件數(shù)一、病態(tài)問題與條件數(shù)1、病態(tài)問題：對一個數(shù)值問題本身如果輸入數(shù)據(jù)有微小擾動（即誤差），引起輸出數(shù)據(jù)（即問題解）相對誤差很大，就是病態(tài)問題。:( ),( )(),(),( )()( )( )() )( )( )()( )( )ppf xxxxxxf xf xf xxf xf xf xfxxxxfxf xf xxCf xxxCf 2、條件數(shù) 計算函數(shù)稱為值時 若有擾動，其相對誤差為函數(shù)值計算函數(shù)值問題的條件數(shù)。的相對誤差為相對誤差比值 利用條件數(shù)很大情況的問題就是病態(tài)問題

20、。誤差估計定性分析與避免誤差危害27n-1nx nx( ),=.x10,(1)1, (1.02)1.24,1,1.022%24%10npppf xxCnnnffxxCC例如則有它表示相對誤差可能放大倍。如有若取自變量相對誤差為，函數(shù)相對誤差為，這時問題可以認(rèn)為是病態(tài)的。一般情況條件數(shù)就認(rèn)為是病態(tài)，越大病態(tài)越嚴(yán)重。28二、算法的穩(wěn)定性二、算法的穩(wěn)定性1、用一個算法進行計算，由于初始數(shù)據(jù)誤差在計算中傳播使計算結(jié)果誤差增長很快使得數(shù)值不穩(wěn)定。110111100(0,1,)1(1,2,)1nxnnxIex e dxnInInIee dxe 例.計算并估計誤差。解：分部積分公式000n11n0n0000

21、.63210.6321A1(1,2,) (1,2,),1!,n!AnnnnnnnIIIInInEIIEnEnEn EIE IE 當(dāng)初值取為時法一： （ ）方法一分析：計算結(jié)果表明，各步計算的誤差滿足關(guān)系易得（）這說明有誤差就是的倍誤差。它表明計算公式（ ）是數(shù)值不穩(wěn)定的。29199910011(+)=0.06842 10100.0684B(9,8,1)1(1) 1,n!nnnnnnneIIInIInEIIEEEEn當(dāng)初值取為 時法二： （ ）方法二分析：計算結(jié)果表明，各步計算的誤差滿足關(guān)系易得這說明比縮小了倍。30計算結(jié)果：n法一 (A)法二 (B)01234567890.63210.3679

22、0.26420.20740.17040.14800.11200.2160-0.72807.5520.63210.36790.26430.20730.17080.14550.12680.11210.10350.0684例例( (對舍入誤差不敏感算法對舍入誤差不敏感算法) )：有長度為：有長度為100100的數(shù)的數(shù)組，每個數(shù)組元素都是僅有兩位有效數(shù)字的實數(shù)，組，每個數(shù)組元素都是僅有兩位有效數(shù)字的實數(shù)，并且假設(shè)執(zhí)行兩位精度的浮點運算，要求這些元并且假設(shè)執(zhí)行兩位精度的浮點運算，要求這些元素之和。素之和。常規(guī)的算法是按數(shù)組存儲順序依次累加數(shù)值，但它可能導(dǎo)致結(jié)果有很大誤差。例如數(shù)組中的數(shù)依次為:1.0,

23、0.01, 0.01，0.01(共99個相同的0.01),由于浮點計算的舍入誤差，按常規(guī)算法將得到結(jié)構(gòu)為1.0,大大偏離準(zhǔn)確率。怎樣提高準(zhǔn)確率？3132三、避免誤差危害的若干原則三、避免誤差危害的若干原則1、要避免除數(shù)絕對值遠(yuǎn)遠(yuǎn)小于被除數(shù)絕對值的除法。、要避免除數(shù)絕對值遠(yuǎn)遠(yuǎn)小于被除數(shù)絕對值的除法。 用絕對值小的數(shù)作除數(shù)舍入誤差會增大，如計算 x/y，若0|y|x|，則可能對計算結(jié)果帶來嚴(yán)重影響，應(yīng)盡量避免。2、要避免兩相近數(shù)相減、要避免兩相近數(shù)相減 在數(shù)值中兩相近數(shù)相減有效數(shù)字會嚴(yán)重?fù)p失。例如，x=532.65，y=532.52都具有五位有效數(shù)字，但x - y=0.13只有兩位有效數(shù)字。通過改

24、變算法可以避免兩相近數(shù)相減。33222121211(1),11cos(|1)2sin2sin(1) ln(1)()(2)()1(3)lglg (4)arctan(1)arctan() xxxxxxxxxxxxxxxxxxxxxx 例如可改為 可改為例很大很大與接近很大等等，都可以得到比直接計算好的結(jié)果。22121(1) ln(2)(1)sin11(3)lg (4)arctan()1(1)xxxxxxxxx答案343、要防止、要防止“大數(shù)大數(shù)”吃掉小數(shù)吃掉小數(shù) 數(shù)值運算中參加運算的數(shù)有時數(shù)量級相差很大，而計算機位數(shù)有限，如不注意運算次序就可能出現(xiàn)大數(shù)“吃掉”小數(shù)的現(xiàn)象，影響計算結(jié)果的可靠性。 如

25、用六位浮點數(shù)計算某市的工業(yè)總產(chǎn)值，原始數(shù)據(jù)是各企業(yè)的工業(yè)產(chǎn)值，當(dāng)加法進行到一定程度，部分和超過100億元 （0.11011），再加產(chǎn)值不足10萬元的小企業(yè)產(chǎn)值，將再也加不進去。而這部分企業(yè)可能為數(shù)不少，合計產(chǎn)值相當(dāng)大.這種情況應(yīng)將小數(shù)先分別加成大數(shù)，然后相加，結(jié)果才比較正確。這個例子告訴我們，在計算機數(shù)系中，加法的交換律和結(jié)合律可能不成立，這是在大規(guī)模數(shù)據(jù)處理時應(yīng)注意的問題。351110101210( )(1)(1)212(1, 2,1, 0)( )( )()nnnnnkknnkkknnnnnP xa xaxa xaa xn nnnnSaSxSaknP xSP xa xaxaxa xan 例如計算多項式值解：法一：直接計算再逐項相加，一共需要做 次乘法和次加法。 法二：采用秦九韶算法 即 只要計算次乘法和( )nnP x次加法就可算出的值。4、注意簡化計算步驟，減少運算次數(shù)、注意簡化計算步驟，減少運算次數(shù) 減少算術(shù)運算的次數(shù)不但可計算機的計算時間，還能減少誤差的積累效應(yīng)。使參加運算的數(shù)字精度應(yīng)盡量保持一致，否則那些較高精度的量的精度沒有太大意義。教材與參考書36 Numerical Analysis:Mathematics of Scientific Computing (T