數(shù)值分析第一章

數(shù)值分析第一章1.認(rèn)識建立算法和對每個算法進(jìn)行理論分析是基本任務(wù)，主動適應(yīng)“公式多”的特點(diǎn)；

2.注重各章建立算法的問題的提法，搞清問題的基本提法，逐步深入；

3.理解每個算法建立的數(shù)學(xué)背景，數(shù)學(xué)原理和基本線索，對最基本的算法要非常熟悉；

4.認(rèn)真進(jìn)行數(shù)值計(jì)算的訓(xùn)練，學(xué)習(xí)各章算法完全是為用于實(shí)際計(jì)算，必須真會算。如何進(jìn)行學(xué)習(xí)？第2頁,共58頁，星期六，2024年，5月數(shù)值分析簡史1955周恩來領(lǐng)導(dǎo)10年科技規(guī)劃，提出發(fā)展幾個新技術(shù)，包括計(jì)算技術(shù)（計(jì)算機(jī)，程序設(shè)計(jì)，計(jì)算數(shù)學(xué)），半導(dǎo)體技術(shù)，自動化技術(shù)。1956成立計(jì)算技術(shù)研究所籌備處，主任華羅庚，手下有兩個組（計(jì)算機(jī)與計(jì)算數(shù)學(xué)）。在其領(lǐng)導(dǎo)下于數(shù)學(xué)所成立計(jì)算方法討論班。1958計(jì)算所成立，帶半軍事性質(zhì)，并且與蘇聯(lián)合作在中科院計(jì)算研究所造出104機(jī)。北大，吉大，復(fù)旦，南大相繼成立計(jì)算數(shù)學(xué)專業(yè)。57－59年吉大聘請?zhí)K聯(lián)梅索夫斯基開辦講義班，其中參與者有李榮華，馮果忱，李岳生，李慶揚(yáng)，蔣爾雄，康立山，徐翠薇等。第3頁,共58頁，星期六，2024年，5月數(shù)值分析簡史1977年開始寫國內(nèi)的教材李榮華，馮果忱《微分方程數(shù)值解》李岳生等《數(shù)值逼近論》曹志浩等《數(shù)值代數(shù)》和《矩陣計(jì)算與方程求根》這三門課程為1984年在國內(nèi)幾所重點(diǎn)大學(xué)開設(shè)的“計(jì)算數(shù)學(xué)及其應(yīng)用軟件"專業(yè)主干課程。第4頁,共58頁，星期六，2024年，5月信息與計(jì)算科學(xué)簡史1958年計(jì)算數(shù)學(xué)專業(yè)1984年“計(jì)算數(shù)學(xué)及其應(yīng)用軟件”

加強(qiáng)計(jì)算機(jī)課程的分量1998年“信息與計(jì)算科學(xué)”

加強(qiáng)信息課程的分量

第5頁,共58頁，星期六，2024年，5月數(shù)值分析又稱計(jì)算方法或數(shù)值計(jì)算方法，是一門與計(jì)算機(jī)應(yīng)用密切結(jié)合的實(shí)用性很強(qiáng)的數(shù)學(xué)課程，它研究的是各種數(shù)學(xué)問題的一類近似解法——數(shù)值方法，即從一組原始數(shù)據(jù)（如模型中的某些參數(shù)）出發(fā)，按照確定的運(yùn)算規(guī)則進(jìn)行有限步運(yùn)算，最終獲得數(shù)學(xué)問題數(shù)值形式的滿足精度要求的近似解。1.1研究對象第6頁,共58頁，星期六，2024年，5月通信衛(wèi)星覆蓋地球面積數(shù)學(xué)模型實(shí)際問題獲取數(shù)據(jù)數(shù)值方法、程序數(shù)據(jù)結(jié)果將地球考慮成一個球體,設(shè)R為地球半徑,h為衛(wèi)星高度,D為覆蓋面在平面的投影第7頁,共58頁，星期六，2024年，5月

數(shù)值分析方法課程主要討論如何構(gòu)造求數(shù)學(xué)模型近似解的算法，討論算法的數(shù)學(xué)原理、誤差和復(fù)雜性，配合程序設(shè)計(jì)進(jìn)行計(jì)算試驗(yàn)并分析試驗(yàn)結(jié)果。

與純數(shù)學(xué)的理論方法不同，用數(shù)值分析所求出的結(jié)果一般不是解的精確值或者準(zhǔn)確的解析表達(dá)式，而是所求真解的某些近似值或近似曲線。第8頁,共58頁，星期六，2024年，5月實(shí)際問題數(shù)學(xué)模型數(shù)值計(jì)算方法程序設(shè)計(jì)上機(jī)計(jì)算數(shù)值結(jié)果根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計(jì)算方法直到編出程序上機(jī)算出結(jié)果，這一過程便是數(shù)值分析研究的對象數(shù)值計(jì)算方法的任務(wù)第9頁,共58頁，星期六，2024年，5月數(shù)值計(jì)算方法的主要特點(diǎn)借助計(jì)算機(jī)提供切實(shí)可行的數(shù)學(xué)算法.想的精確度;收斂且穩(wěn)定;誤差可以分析或估計(jì).所提出的算法必須具有：可靠的理論分析;理時間復(fù)雜性好__指節(jié)省時間；空間復(fù)雜性好__指節(jié)省存儲量。計(jì)算復(fù)雜性好

通過數(shù)值實(shí)驗(yàn)證明算法行之有效.第10頁,共58頁，星期六，2024年，5月采用“近似替代”方法→逼近采用“構(gòu)造性”方法采用“離散化”方法

把求連續(xù)變量的問題轉(zhuǎn)化為求離散變量的問題采用“遞推化”方法

復(fù)雜的計(jì)算歸結(jié)為簡單過程的多次重復(fù)，易于用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)（迭代法）。采用各種搜索方法構(gòu)造數(shù)值算法主要手段第11頁,共58頁，星期六，2024年，5月1、數(shù)值逼近

插值與擬合、數(shù)值積分與微分2、數(shù)值代數(shù)線性代數(shù)方程組的解法、非線性代數(shù)方程（組）的解法3、微分方程數(shù)值解

ODEPDE1.2研究內(nèi)容第12頁,共58頁，星期六，2024年，5月1.3.1誤差的來源與分類從實(shí)際問題中抽象出數(shù)學(xué)模型

——模型誤差例:質(zhì)量為m的物體，在重力作用下,自由下落，其下落距離s

與時間t的關(guān)系是：

其中g(shù)

為重力加速度。1.3

誤差第13頁,共58頁，星期六，2024年，5月通過測量得到模型中參數(shù)的值

——觀測誤差求近似解——方法誤差（截?cái)嗾`差）例如，當(dāng)函數(shù)用maclaurin多項(xiàng)式

近似代替時，數(shù)值方法的截?cái)嗾`差是與0之間。在第14頁,共58頁，星期六，2024年，5月機(jī)器字長有限——

舍入誤差

用計(jì)算機(jī)、計(jì)算器和筆算，都只能用有限位

=3.1415926…

小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：第15頁,共58頁，星期六，2024年，5月四舍五入后……在數(shù)值計(jì)算方法中，主要研究截?cái)嗾`差和舍入誤差（包括初始數(shù)據(jù)的誤差）對計(jì)算結(jié)果的影響！第16頁,共58頁，星期六，2024年，5月1.3.2誤差與有效數(shù)字1、絕對誤差與絕對誤差限例:若用以厘米為最小刻度的尺去量桌子的長，大約為1.45米，求1.45米的絕對誤差。1.45米的絕對誤差=？不知道！定義：設(shè)是準(zhǔn)確值，為

的一個近似值，稱是近似值的絕對誤差,簡稱為誤差。

第17頁,共58頁，星期六，2024年，5月但實(shí)際問題往往可以估計(jì)出不超過某個正數(shù)，即則稱為絕對誤差限，有了絕對誤差限就可以知道的范圍為即落在內(nèi)。在應(yīng)用上，常常采用下列寫法來刻劃的精度。第18頁,共58頁，星期六，2024年，5月例1設(shè)x=

=3.1415926…近似值x*=3.14,它的絕對誤差是0.0015926…，有 ??

x-x*=0.0015926…0.002=0.210-2例2又近似值x*

=3.1416，它的絕對誤差是0.0000074…，有

x-x*=0.0000074…0.000008=0.810-5例3而近似值x*=3.1415，它的絕對誤差是0.0000926…，有

x-x*=0.0000926…0.0001=0.110-3可見，絕對誤差限

*不是唯一的，但*越小越好第19頁,共58頁，星期六，2024年，5月2、相對誤差與相對誤差限定義：設(shè)是準(zhǔn)確值，是近似值，是近似值的誤差，通常取為近似值的相對誤差，記作，稱一般情況下是不知道的，怎么辦？第20頁,共58頁，星期六，2024年，5月事實(shí)上，當(dāng)較小時是的二次方項(xiàng)級,故可忽略不計(jì).相應(yīng)地，若正數(shù)滿足

則稱為的相對誤差限。第21頁,共58頁，星期六，2024年，5月例4.甲打字每100個錯一個，乙打字每1000個錯一個，求其相對誤差限解：根椐定義:甲打字時的相對誤差限

乙打字時的相對誤差限第22頁,共58頁，星期六，2024年，5月3、有效數(shù)字定義：如果則說近似表示準(zhǔn)確到小數(shù)后第位，并從這由上述定義第位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。第23頁,共58頁，星期六，2024年，5月定義:若近似值的誤差限是某一位的半個單位,也即，若有位有效數(shù)字。則稱其中，是1到9中的一個數(shù)字；是0到9中一個數(shù)字；為整數(shù)，且該位到的左邊第一位非零數(shù)字共有位,就說有位有效數(shù)字。第24頁,共58頁，星期六，2024年，5月取作的近似值，就有三位有效數(shù)字；取作的近似值，就有五位有效數(shù)字。例如：

x-x*=0.0015926…0.002=0.210-20.510-2前面例1前面例2

x-x*=0.0000074…0.000008=0.810-50.510-4

第25頁,共58頁，星期六，2024年，5月關(guān)于有效數(shù)字說明①用四舍五入取準(zhǔn)確值的前n位x*作為近似值,則x*必有n位有效數(shù)字。如3.142作為的近似值有4位有效數(shù)字，而3.141為3位有效數(shù)字②有效數(shù)字相同的兩個近似數(shù)，絕對誤差不一定相同。例如，設(shè)x1*=12345,設(shè)x2*=12.345,兩者均有5位有效數(shù)字但絕對誤差不一樣x-x1*=x-12345≤0.5=1/2100

x-x2*=x-12.345≤0.0005=1/210-3③把任何數(shù)乘以10p(p=0,1,…)不影響有效位數(shù)④準(zhǔn)確值具有無窮多位有效數(shù)字,如三角形面積S=1/2ah=0.5ah因?yàn)?.5是真值,沒有誤差

*=0,因此n,準(zhǔn)確值具有無窮位有效數(shù)字第26頁,共58頁，星期六，2024年，5月4、誤差限與有效數(shù)字的關(guān)系

則

至少具有位有效數(shù)字。Th1：

對于用式表示的近似數(shù)，若具有位有效數(shù)字，則其相對誤差限為反之，若的相對誤差限為第27頁,共58頁，星期六，2024年，5月例5已知近似數(shù)x*有兩位有效數(shù)字，試求其相對誤差限解：已知n=2代入公式r*=1/2x110-(n-1)得

r*=1/2x110-1

x*的第一位有效數(shù)字x1沒有給出，可進(jìn)行如下討論：當(dāng)x1=1r*=1/2x110-1=1/2*110-1=5%x1=9r*=1/2x110-1=1/2*910-1=0.56%取x1=1時相對誤差為最大，即5%第28頁,共58頁，星期六，2024年，5月例6已知近似數(shù)x*的相對誤差限為0.3%，問x*有幾位有效數(shù)字？解：由得ⅰ當(dāng)x1=1時,310-3=1/410-(n-1)1210-3=10-(n-1)

上式兩邊取以10為底的對數(shù)得lg22+lg3+(-3)=-n+1∵lg2=0.3010lg3=0.477120.3010+0.4771-4=-n∴n=2.9209ⅱ當(dāng)x1=9時,310-3=1/2010-(n-1)610-3=10-n上式兩邊取以10為底的對數(shù)得lg2+lg3+(-3)=-n∴n=2.2219∴x*至少有3位有效數(shù)字

第29頁,共58頁，星期六，2024年，5月例7為使的近似數(shù)的相對誤差小于0.1%，問查開方表時，要取幾位有效數(shù)字？解：∵8<<9∴x1=8

∴-(n-1)<lg2+2lg3+(-3)-n<1.2552-4-n<-2.7448∴n>2.7448取n=3即查平方表時

8.37取三位有效數(shù)字

∴第30頁,共58頁，星期六，2024年，5月1.3.3數(shù)值運(yùn)算的誤差估計(jì)1、四則運(yùn)算的誤差估計(jì)兩個近似數(shù)與,其誤差限分別為及,它們進(jìn)行加減乘除運(yùn)算得到的誤差限分別為第31頁,共58頁，星期六，2024年，5月從而有

的相對誤差

對于近似值，函數(shù)在舍去右邊第二項(xiàng)得到即的絕對誤差可以得到附近按泰勒展式展開得到2、函數(shù)誤差估計(jì)當(dāng)自變量有誤差時，計(jì)算函數(shù)值也會產(chǎn)生誤差，其誤差限可利用函數(shù)的Taylor展開式進(jìn)行估計(jì)。

第32頁,共58頁，星期六，2024年，5月對絕對誤差式兩邊取絕對值得

故的相對誤差限的誤差限而解釋：第33頁,共58頁，星期六，2024年，5月

當(dāng)為多元函數(shù)時計(jì)算,如果的近似值為,則的近似為于是函數(shù)值的誤差由Taylor展開,得：多元函數(shù)的情況第34頁,共58頁，星期六，2024年，5月于是誤差限為而的相對誤差限為式(1)第35頁,共58頁，星期六，2024年，5月第36頁,共58頁，星期六，2024年，5月第37頁,共58頁，星期六，2024年，5月例8:已測得某場地長的值為,寬的值為,已知,.試求面積的絕對誤差限與相對誤差限.解:因

其中由式(1)得第38頁,共58頁，星期六，2024年，5月而于是絕對誤差限為相對誤差限為第39頁,共58頁，星期六，2024年，5月3、算法的數(shù)值穩(wěn)定性

數(shù)值計(jì)算在設(shè)計(jì)算法時首先關(guān)心的是由它產(chǎn)生的計(jì)算結(jié)果的穩(wěn)定性，而算法的穩(wěn)定性與舍入誤差是否增長密切相關(guān)。一個算法如果輸入數(shù)據(jù)有微小擾動（即誤差），而在計(jì)算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱其為數(shù)值不穩(wěn)定。

第40頁,共58頁，星期六，2024年，5月例9：求定積分的值.解：直接積分可產(chǎn)生遞推公式若取初值第41頁,共58頁，星期六，2024年，5月可得遞推公式按公式就可以逐步算出Whathappened?!不穩(wěn)定的算法！這就是誤差傳播所引起的危害!

注意此公式精確成立，且第42頁,共58頁，星期六，2024年，5月由題設(shè)中的遞推公式（1）可看出，

的誤差擴(kuò)大了5倍后傳給

，因而初值

的誤差對以后各步這就造成的計(jì)算結(jié)果嚴(yán)重失真。計(jì)算結(jié)果的影響，隨著

的增大愈來愈嚴(yán)重。要怎么做才能解決這個問題呢?第43頁,共58頁，星期六，2024年，5月可求得I9

0.017，按改寫后的公式可逐次求得不妨設(shè)I9

I10，于是由將公式變?yōu)?2)第44頁,共58頁，星期六，2024年，5月

I8

0.019I7

0.021 I6

0.024I5

0.028 I4

0.034I3

0.043 I2

0.058I1

0.088 I0

0.182穩(wěn)定的算法！

在我們今后的討論中，誤差將不可回避，算法的穩(wěn)定性會是一個非常重要的話題。第45頁,共58頁，星期六，2024年，5月注：遞推公式(1)的舍入誤差以5的冪次增長進(jìn)行傳播，因此是數(shù)值不穩(wěn)定的，而遞推公式(2)的舍入誤差在一定范圍內(nèi)以0.2的冪次進(jìn)行傳播，隨著n的增大，誤差逐步減少，因此該算法是數(shù)值穩(wěn)定的。

因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實(shí)際計(jì)算中對任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱為無條件穩(wěn)定。而對某些數(shù)據(jù)數(shù)值穩(wěn)定，對其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱為條件穩(wěn)定。第46頁,共58頁，星期六，2024年，5月病態(tài)問題和條件數(shù)

如果問題的輸入數(shù)據(jù)有微小擾動，就會引起輸出結(jié)果數(shù)據(jù)（即解）的很大擾動，稱這樣的問題為病態(tài)問題。相反的情形稱為良態(tài)問題。對于病態(tài)的數(shù)學(xué)問題，用通常的算法求數(shù)值解都是不穩(wěn)定的。病態(tài)和良態(tài)是相對的，沒有嚴(yán)格的界限，通常用條件數(shù)大小來衡量問題的病態(tài)程度，條件數(shù)越大病態(tài)可能越嚴(yán)重。

條件數(shù)c(x)越大，f(x)的相對誤差越大，通常認(rèn)為時，問題是病態(tài)的。第47頁,共58頁，星期六，2024年，5月1.3.4數(shù)值計(jì)算中應(yīng)該注意的一些原則1.要選擇數(shù)值穩(wěn)定的計(jì)算公式

定義一種數(shù)值方法，若原始數(shù)據(jù)有誤差，而在計(jì)算的過程中，由于舍入誤差的傳播，使得近似計(jì)算結(jié)果與準(zhǔn)確值相差很大，則稱這種數(shù)值方法是不穩(wěn)定的。否則，在計(jì)算的過程中，若舍入誤差得到控制，近似計(jì)算結(jié)果能逼近準(zhǔn)確值，則稱這種數(shù)值方法是穩(wěn)定的。第48頁,共58頁，星期六，2024年，5月，試問用遞推公式例10給定采用正向遞推和逆向遞推求的值是否穩(wěn)定？解設(shè)的近似值為則有從而有

對上式兩邊求絕對值得按給定的遞推公式采用正向遞推計(jì)算的值是不穩(wěn)定的。第49頁,共58頁，星期六，2024年，5月2.要避免兩個相近的數(shù)相減在數(shù)值計(jì)算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。例11:求當(dāng)x=1000，y的準(zhǔn)確值為0.01580

的值。第50頁,共58頁，星期六，2024年，5月類似地

(2)若將原式改寫為則y=0.01581(1)直接相減有3位有效數(shù)字！只有1位有效數(shù)字第51頁,共58頁，星期六，2024年