第一章_數(shù)值的基本概念(刪減版)

1、上課上課(2-17周周)每周三每周三 8:15-9:45 第二教學(xué)樓第二教學(xué)樓121室室每個(gè)單每個(gè)單周三周三 10:05-11:35 圖文圖文3號(hào)機(jī)房號(hào)機(jī)房(圖文信息中心三樓圖文信息中心三樓319室室) 教師：吳笑千教師：吳笑千2號(hào)學(xué)院樓理學(xué)院四樓號(hào)學(xué)院樓理學(xué)院四樓449室室答疑時(shí)間：每周二下午答疑時(shí)間：每周二下午3:00-5:00 1. 中秋節(jié)期間中秋節(jié)期間 2010年年9月月22日至日至24日放假日放假，共共3天。天。9月月19日日(星期日星期日)上星期四（雙周）上星期四（雙周）的課程，的課程，9月月25日日(星期六星期六)上星期五（雙周）上星期五（雙周）的課程。的課程。2. 國(guó)慶節(jié)期間國(guó)

2、慶節(jié)期間2010年年10月月1日至日至7日放假，日放假，共共7天。天。9月月26日日(星期日星期日)上星期三（雙周）上星期三（雙周）的課程的課程，10月月9日日(星期六星期六)上星期四（雙周）上星期四（雙周）的課程。的課程。 數(shù)值分析（數(shù)值分析（numerical analysis），），是數(shù)學(xué)的一個(gè)分支，以數(shù)字計(jì)算機(jī)是數(shù)學(xué)的一個(gè)分支，以數(shù)字計(jì)算機(jī)求解數(shù)學(xué)問(wèn)題的理論和方法為研究求解數(shù)學(xué)問(wèn)題的理論和方法為研究對(duì)象。對(duì)象。- 1.1 數(shù)值算法的研究對(duì)象 1.2 誤差分析的概念1.3 數(shù)值算法設(shè)計(jì)的一些要點(diǎn) 工程問(wèn)題上機(jī)計(jì)算數(shù)學(xué)模型結(jié)果分析問(wèn)題解答設(shè)計(jì)算法(1) 求解

3、線(xiàn)性方程組求解線(xiàn)性方程組AX=b, 其中其中A為為3階可逆方階可逆方陣，陣，X=(x1, x2, x3)T;(2) 求代數(shù)方程求代數(shù)方程x2+x 6=0在在0,4上的根上的根x*；(3) 已知已知y=P(x)為為x0, x1上的直線(xiàn)，滿(mǎn)足上的直線(xiàn)，滿(mǎn)足P(x0)=y0, P(x1)=y1, x2 (x0, x1), 求求P(x2)；(4) 計(jì)算定積分計(jì)算定積分 (1ab)；(5) 解常微分方程初值問(wèn)題解常微分方程初值問(wèn)題 1baIdxx 00( )yxy(1) Cramer法則法則 , 其中其中D=|A|, Dj為由為由b置換置換D的第的第j列所得。列所得。 (2)根據(jù)求根公式得根據(jù)求根公式得

4、x*=2;(3) P(x2)= ;(4) 根據(jù)積分公式得到根據(jù)積分公式得到 ;(5) 根據(jù)常微分方程求解公式得根據(jù)常微分方程求解公式得,1,2,3jjDxjD1002010()yyyxxxx lnbIa212( )y xx(1) 求解線(xiàn)性方程組求解線(xiàn)性方程組AX=B, 其中其中A為為30階可逆方階可逆方陣，陣，X=(x1, x2, x30)T;(2) 求超越方程求超越方程xex =1在在0,1上的根上的根x*；(3) 已知已知y=f(x)為為x0, x1上的函數(shù)，滿(mǎn)足上的函數(shù)，滿(mǎn)足f(x0)=y0, f(x1)=y1, x2 (x0, x1), 求求f(x2)；(4) 計(jì)算定積分計(jì)算定積分 (

5、1ab)；(5) 解常微分方程初值問(wèn)題解常微分方程初值問(wèn)題 1lnbaIdxx( )200yxyy (1) 計(jì)算量非常大；計(jì)算量非常大；(2) 無(wú)法求得無(wú)法求得x*的解析形式，只能求近似值；的解析形式，只能求近似值；(3) f(x2) 試試；試試；(4) 無(wú)法找到原函數(shù)，考慮近似方法；無(wú)法找到原函數(shù)，考慮近似方法；(5) 沒(méi)有解析解，數(shù)值解法求取近似解。沒(méi)有解析解，數(shù)值解法求取近似解。1002010()yyyxxxx 計(jì)算機(jī)的認(rèn)識(shí)能力是有限的計(jì)算機(jī)的認(rèn)識(shí)能力是有限的 計(jì)算機(jī)的計(jì)算能力也是有限的計(jì)算機(jī)的計(jì)算能力也是有限的！計(jì)算機(jī)算法計(jì)算機(jī)算法對(duì)于給定的問(wèn)題和設(shè)備（計(jì)算機(jī)），一個(gè)算法是對(duì)于給定的問(wèn)

6、題和設(shè)備（計(jì)算機(jī)），一個(gè)算法是用該設(shè)備可理解的語(yǔ)言表示的，對(duì)解決這個(gè)問(wèn)題用該設(shè)備可理解的語(yǔ)言表示的，對(duì)解決這個(gè)問(wèn)題的一種方法的精確刻畫(huà)。的一種方法的精確刻畫(huà)。計(jì)算機(jī)算法主要包含計(jì)算機(jī)算法主要包含數(shù)值算法、非數(shù)值算法數(shù)值算法、非數(shù)值算法和和軟計(jì)算方法軟計(jì)算方法三類(lèi)。三類(lèi)。 數(shù)值算法數(shù)值算法主要指與連續(xù)數(shù)學(xué)模型有關(guān)的算法，主要指與連續(xù)數(shù)學(xué)模型有關(guān)的算法，如數(shù)值線(xiàn)性代數(shù)、方程求解、數(shù)值逼近、數(shù)如數(shù)值線(xiàn)性代數(shù)、方程求解、數(shù)值逼近、數(shù)值微積分、微分方程數(shù)值解和最優(yōu)化計(jì)算方值微積分、微分方程數(shù)值解和最優(yōu)化計(jì)算方法等；法等；( (本課程內(nèi)容本課程內(nèi)容) ) 非數(shù)值算法非數(shù)值算法主要指與離散數(shù)學(xué)模型有關(guān)的算主

7、要指與離散數(shù)學(xué)模型有關(guān)的算法，如排序、搜索、分類(lèi)、圖論算法等；法，如排序、搜索、分類(lèi)、圖論算法等；軟計(jì)算方法軟計(jì)算方法是近來(lái)發(fā)展的不確定性算法的總是近來(lái)發(fā)展的不確定性算法的總稱(chēng)，包括神經(jīng)網(wǎng)絡(luò)計(jì)算、模糊邏輯、遺傳算稱(chēng)，包括神經(jīng)網(wǎng)絡(luò)計(jì)算、模糊邏輯、遺傳算法、螞蟻算法等。法、螞蟻算法等。 有窮性有窮性 數(shù)值性數(shù)值性 近似性近似性 Fortran C+Matlab誤差限和有效數(shù)字誤差限和有效數(shù)字 截?cái)嗾`差與收斂性截?cái)嗾`差與收斂性 舍入誤差和數(shù)值穩(wěn)定性舍入誤差和數(shù)值穩(wěn)定性 數(shù)據(jù)誤差和病態(tài)問(wèn)題數(shù)據(jù)誤差和病態(tài)問(wèn)題 誤差和相對(duì)誤差誤差和相對(duì)誤差(定義定義1.1) 設(shè)設(shè)x*是某量的準(zhǔn)確值，是某量的準(zhǔn)確值，x是是

8、x*的近似值的近似值稱(chēng)稱(chēng) x = x*-x 為為x的的誤差誤差或或絕對(duì)誤差絕對(duì)誤差。| x*-x | , 稱(chēng)稱(chēng) 為為x的的(絕對(duì)絕對(duì))誤差限誤差限或或精度精度， rx = (x*-x)/x*稱(chēng)為稱(chēng)為x的的相對(duì)誤差相對(duì)誤差|(x*- x)/ x *| r, 稱(chēng)稱(chēng) r為為x的的相對(duì)誤差限相對(duì)誤差限。當(dāng)當(dāng) r 很小時(shí)，很小時(shí)， r /| x |。 誤差的四則運(yùn)算見(jiàn)后誤差的四則運(yùn)算見(jiàn)后準(zhǔn)確位數(shù)和有效數(shù)字準(zhǔn)確位數(shù)和有效數(shù)字(定義定義1.2)設(shè)設(shè)x = 0.a1 a 2an 10m (m為整數(shù)為整數(shù)) (1.1)其中其中a 1an為為09中一個(gè)數(shù)字且中一個(gè)數(shù)字且a 1 0。如果如果 | x*-x| 0.5

9、 10 k (1.2)即即x的誤差不超過(guò)的誤差不超過(guò)10-k位的位的單位單位則稱(chēng)近似數(shù)則稱(chēng)近似數(shù)x準(zhǔn)確到第準(zhǔn)確到第k位小數(shù)位小數(shù)，并說(shuō)，并說(shuō)x有有m+k位位有效數(shù)字有效數(shù)字。 等價(jià)定義：如果近似值等價(jià)定義：如果近似值x的絕對(duì)誤差限不超過(guò)它某一位的半個(gè)的絕對(duì)誤差限不超過(guò)它某一位的半個(gè)單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的所有數(shù)字都稱(chēng)為所有數(shù)字都稱(chēng)為有效數(shù)字有效數(shù)字。并說(shuō)。并說(shuō)x“準(zhǔn)確準(zhǔn)確”到這一位。到這一位。圓周率圓周率 =3.1415926。x1=3.14; x 2=3.141; x 3=3.142; x 4=3.1414解解(

10、1) x1=0.314 101 , x1=0.1592610 2, | x1| 0.5 10 2,有有3位有效數(shù)字；位有效數(shù)字；(2) x2=0.592610 3, |x2| 0.5 10 2,有有3位位有效數(shù)字；有效數(shù)字；(3) x3= 0. 407310 3, | x3| 0.5 10 3,有有4位有效數(shù)字；位有效數(shù)字； (4) x4=0.192610 3, |x4| 0.5 10 3, 有有4位位有效數(shù)字。有效數(shù)字。 設(shè)設(shè)x*是某量的準(zhǔn)確值，是某量的準(zhǔn)確值，x是是x*的近似值，如果的近似值，如果在從第一個(gè)非零數(shù)字開(kāi)始的第在從第一個(gè)非零數(shù)字開(kāi)始的第n位進(jìn)行四舍位進(jìn)行四舍五入五入( (即考慮

11、第即考慮第n+1n+1位是舍還是入？位是舍還是入？) )，x*和和x的結(jié)果完全一致，則稱(chēng)的結(jié)果完全一致，則稱(chēng)x有有n位有效數(shù)字。位有效數(shù)字。 與定義與定義1.2的區(qū)別的區(qū)別x* 未知，從而在數(shù)值分析中無(wú)法應(yīng)用。按照通俗定義，未知，從而在數(shù)值分析中無(wú)法應(yīng)用。按照通俗定義， 只有只有三位有效數(shù)字，但實(shí)際上三位有效數(shù)字，但實(shí)際上 的誤差比的誤差比 的誤差小，因此是的誤差小，因此是 的更好的近似值。的更好的近似值。通俗定義并不合理。通俗定義并不合理。*343.1415926, 3.142, .,3 1414xxx 截?cái)嗾`差截?cái)嗾`差：一個(gè)無(wú)限的數(shù)學(xué)極限過(guò)程用有限次運(yùn)算一個(gè)無(wú)限的數(shù)學(xué)極限過(guò)程用有限次運(yùn)算近

12、似計(jì)算產(chǎn)生的誤差。近似計(jì)算產(chǎn)生的誤差。 例（無(wú)限）例（無(wú)限）近似計(jì)算（近似計(jì)算（有限有限）截?cái)嗾`差（余項(xiàng)公式）截?cái)嗾`差（余項(xiàng)公式） 在在0與與x之間之間 212!nxxxexn 2( )12!nxnxxeSxxn 1( )( )(1)!nxnnxeSxRxen 算法的算法的收斂性收斂性：該算法總可以通過(guò)提高計(jì)算該算法總可以通過(guò)提高計(jì)算量使得截?cái)嗾`差任意小。即量使得截?cái)嗾`差任意小。即 余項(xiàng)余項(xiàng)0 0 舍入誤差舍入誤差: 由于機(jī)器字長(zhǎng)的限制而產(chǎn)生的誤差由于機(jī)器字長(zhǎng)的限制而產(chǎn)生的誤差機(jī)器數(shù)機(jī)器數(shù)( (二進(jìn)制二進(jìn)制0-1,0-1,離散離散) )規(guī)格化浮點(diǎn)式規(guī)格化浮點(diǎn)式: : 階碼階碼m,m,字長(zhǎng)字長(zhǎng)t

13、 ,t ,尾數(shù)尾數(shù) ( ( 1 1=1)=1) 2 2m m 0.0. 1 1 2 2 t t, , m=m=1 1 2 2s s 單精度單精度3232位位(4(4字節(jié)字節(jié)): t=23,s=7, ): t=23,s=7, 符號(hào)符號(hào)2 2位位, , 表示范表示范圍圍 2.9 2.9 1010 3939 3.43.4 10103838 (2 (2-128 -128 2 2128128) )雙精度雙精度6464位位(8(8字節(jié)字節(jié)) : t=52,s=10, ) : t=52,s=10, 符號(hào)符號(hào)2 2位位, ,表示表示范圍范圍 5.56 5.56 1010 309309 1.791.79 101

14、0308308 (2 (2-1024 -1024 2 210241024) )上溢出上溢出和下溢出和下溢出0 00誤差傳播問(wèn)題誤差傳播問(wèn)題: 設(shè)函數(shù)設(shè)函數(shù)y=f(x1, x2, , xn)是一是一個(gè)算法或模型，個(gè)算法或模型， 是變量是變量xi的準(zhǔn)確值，而的準(zhǔn)確值，而 是變量是變量xi的近似值。如果的近似值。如果 , 且且f的計(jì)算過(guò)程中沒(méi)有新的誤差產(chǎn)生，那么計(jì)的計(jì)算過(guò)程中沒(méi)有新的誤差產(chǎn)生，那么計(jì)算結(jié)果算結(jié)果 具有怎樣的精度？具有怎樣的精度？即即*ixix *| |iiiixxx12( ,)nyf x xx*1212| |(,)(,)| ?nnyf xxxf x xx算法的數(shù)值穩(wěn)定算法的數(shù)值穩(wěn)定:

15、 計(jì)算過(guò)程中舍入誤差不計(jì)算過(guò)程中舍入誤差不會(huì)被嚴(yán)重放大會(huì)被嚴(yán)重放大線(xiàn)性情形用嚴(yán)格估計(jì)線(xiàn)性情形用嚴(yán)格估計(jì)非線(xiàn)性情形用線(xiàn)性近似非線(xiàn)性情形用線(xiàn)性近似絕對(duì)誤差傳播主要取決于絕對(duì)誤差傳播主要取決于條件數(shù)條件數(shù) 相對(duì)傳播主要取決于相對(duì)傳播主要取決于條件數(shù)條件數(shù) 條件數(shù)很大條件數(shù)很大 病態(tài)問(wèn)題病態(tài)問(wèn)題 *12121| |(,)(,)|nnniiiyf xxxf xxxa *1(),niiifyxx *1( )()()nirriiixfyxxy *|() |ifx *|()|iixfxy (a b)= a b, r(a b)= a/(a b) ra b/(a b) rb(相近數(shù)相減相近數(shù)相減不穩(wěn)定不穩(wěn)定) (

16、ab) b a+a b r(ab) ra+ rb (a/b) (1/b) a (a/b2) b (分母分母b 0不穩(wěn)定不穩(wěn)定) r(a/b) rarb n=0, 1, , 20估計(jì)估計(jì) 101dxexIxnn11(1)1nInen 算法一算法一: 分部積分分部積分遞推公式遞推公式 In=1 nIn-1, n=1,20 I0=1-1/e I1 I2 I20 誤差很大誤差很大(見(jiàn)書(shū)見(jiàn)書(shū)P8) ， n = n n-1, 20 =(20!) 0 ，不穩(wěn)定，不穩(wěn)定算法二：遞推公式算法二：遞推公式 In-1=(1 In)/n, n= 20 ,1I20 估計(jì)式中點(diǎn)估計(jì)式中點(diǎn) I19 I1 I0 誤差很小誤差

17、很小 n-1 = n /n, 0 = 20 /(20!)，穩(wěn)定，穩(wěn)定*11,nnInI 例例1.6 (病態(tài)問(wèn)題病態(tài)問(wèn)題)（保留（保留4位有效數(shù)字）位有效數(shù)字）x1=x2=x3=1 x1=1.1650, x2= 0.0003, x3= 2.0004. 病態(tài)問(wèn)題病態(tài)問(wèn)題: 很小的變化數(shù)據(jù)卻導(dǎo)致解產(chǎn)生了很大的很小的變化數(shù)據(jù)卻導(dǎo)致解產(chǎn)生了很大的變化。變化。區(qū)別：收斂性和數(shù)值穩(wěn)定性主要源于算法，區(qū)別：收斂性和數(shù)值穩(wěn)定性主要源于算法，病態(tài)性病態(tài)性主要是模型本身的原因主要是模型本身的原因 。 1231231234932194936440360361310614144107202137693739401036

18、003600 xxxxxxxxx 1231231230.75000.52502.63610.75000.42360.1.3630001.47360.52500.30000.21361.10386xxxxxxxxx 設(shè)計(jì)算法基本原則設(shè)計(jì)算法基本原則計(jì)算精度：收斂性、穩(wěn)定性計(jì)算精度：收斂性、穩(wěn)定性計(jì)算速度：計(jì)算量、收斂速度、多個(gè)計(jì)算速度：計(jì)算量、收斂速度、多個(gè)CPU通信通信計(jì)算空間：存儲(chǔ)量計(jì)算空間：存儲(chǔ)量注意事項(xiàng)注意事項(xiàng)病態(tài)問(wèn)題病態(tài)問(wèn)題速度細(xì)節(jié)速度細(xì)節(jié)(加法、乘法，函數(shù)加法、乘法，函數(shù)) 計(jì)算多項(xiàng)式的值計(jì)算多項(xiàng)式的值存儲(chǔ)細(xì)節(jié)存儲(chǔ)細(xì)節(jié)(降維降維) 計(jì)算多項(xiàng)式的值計(jì)算多項(xiàng)式的值穩(wěn)定性細(xì)節(jié)穩(wěn)定性細(xì)節(jié)(相

19、近數(shù)相減相近數(shù)相減，大數(shù)吃小數(shù)，大數(shù)吃小數(shù)，分母接近分母接近0)死循環(huán)死循環(huán) 設(shè)置循環(huán)的上界。設(shè)置循環(huán)的上界。實(shí)數(shù)相等比較實(shí)數(shù)相等比較中間結(jié)果（要少顯示和輸出）中間結(jié)果（要少顯示和輸出）速度細(xì)節(jié)速度細(xì)節(jié)使用秦九韶算法(Horners rule)0111)(axaxaxaxpnnnn 0121)()(axaxaxaxaxpnnn 計(jì)算多項(xiàng)式的值可大大減少計(jì)算量直接計(jì)算，乘法的運(yùn)算次數(shù): n+(n-1)+1+0=n(n+1)/2乘的運(yùn)算次數(shù)：n次算法過(guò)程設(shè)計(jì)可使用遞推計(jì)算公式：算法過(guò)程設(shè)計(jì)可使用遞推計(jì)算公式： p0=an, pk=pk-1x + an-k ( k =1,n)最后得到的最后得到的 p

20、 即是多項(xiàng)式即是多項(xiàng)式 p(x) 的值，算法過(guò)程只需的值，算法過(guò)程只需n次乘法次乘法和和n次加法，此算法稱(chēng)為秦九韶算法次加法，此算法稱(chēng)為秦九韶算法.0121)()(axaxaxaxaxpnnn p=an, p=px + an-k ( k =1,n)存儲(chǔ)細(xì)節(jié)存儲(chǔ)細(xì)節(jié)求求 的小正根的小正根( (取取3 3位有效數(shù)字位有效數(shù)字). ). 01162xx 解解1863 ,x 只有一位有效數(shù)字只有一位有效數(shù)字. . *2x2863x 則具有則具有3 3位有效數(shù)字位有效數(shù)字. . 若改用若改用由求根公式由求根公式2863x *287.940.06,x (863 )(863 )110.062715.94863863 相近數(shù)相減相近數(shù)相減 大數(shù)吃小數(shù)大數(shù)吃小數(shù) 1234 + (0.4 + 0.3) =1235取取4位有效數(shù)字計(jì)算：位有效數(shù)字計(jì)算：(1234 + 0.4) + 0.3=1234問(wèn)題：?jiǎn)栴}：(x+y)+z 和和 x+(y+z) 相等嗎？相等嗎？改進(jìn)方法：先加小的數(shù)改進(jìn)方法：先加小的數(shù)分母接近于分母接近于 問(wèn)題：當(dāng)問(wèn)題：當(dāng) x充分大時(shí)充分大時(shí), 計(jì)