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

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

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

3、線性方程組求解線性方程組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上的直線，滿足上的直線，滿足P(x0)=y0, P(x1)=y1, x2 (x0, x1), 求求P(x2)；(4) 計算定積分計算定積分 (1ab)；(5) 解常微分方程初值問題解常微分方程初值問題 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) 求解線性方程組求解線性方程組AX=B, 其中其中A為為30階可逆方階可逆方陣，陣，X=(x1, x2, x30)T;(2) 求超越方程求超越方程xex =1在在0,1上的根上的根x*；(3) 已知已知y=f(x)為為x0, x1上的函數(shù)，滿足上的函數(shù)，滿足f(x0)=y0, f(x1)=y1, x2 (x0, x1), 求求f(x2)；(4) 計算定積分計算定積分 (

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

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

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

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

9、 10 k (1.2)即即x的誤差不超過的誤差不超過10-k位的位的單位單位則稱近似數(shù)則稱近似數(shù)x準確到第準確到第k位小數(shù)位小數(shù)，并說，并說x有有m+k位位有效數(shù)字有效數(shù)字。 等價定義：如果近似值等價定義：如果近似值x的絕對誤差限不超過它某一位的半個的絕對誤差限不超過它某一位的半個單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的所有數(shù)字都稱為所有數(shù)字都稱為有效數(shù)字有效數(shù)字。并說。并說x“準確準確”到這一位。到這一位。圓周率圓周率 =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ù)字。 設設x*是某量的準確值，是某量的準確值，x是是x*的近似值，如果的近似值，如果在從第一個非零數(shù)字開始的第在從第一個非零數(shù)字開始的第n位進行四舍位進行四舍五入五入( (即考慮

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

12、似計算產生的誤差。近似計算產生的誤差。 例（無限）例（無限）近似計算（近似計算（有限有限）截斷誤差（余項公式）截斷誤差（余項公式） 在在0與與x之間之間 212!nxxxexn 2( )12!nxnxxeSxxn 1( )( )(1)!nxnnxeSxRxen 算法的算法的收斂性收斂性：該算法總可以通過提高計算該算法總可以通過提高計算量使得截斷誤差任意小。即量使得截斷誤差任意小。即 余項余項0 0 舍入誤差舍入誤差: 由于機器字長的限制而產生的誤差由于機器字長的限制而產生的誤差機器數(shù)機器數(shù)( (二進制二進制0-1,0-1,離散離散) )規(guī)格化浮點式規(guī)格化浮點式: : 階碼階碼m,m,字長字長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, 符號符號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, 符號符號2 2位位, ,表示表示范圍范圍 5.56 5.56 1010 309309 1.791.79 101

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

15、 計算過程中舍入誤差不計算過程中舍入誤差不會被嚴重放大會被嚴重放大線性情形用嚴格估計線性情形用嚴格估計非線性情形用線性近似非線性情形用線性近似絕對誤差傳播主要取決于絕對誤差傳播主要取決于條件數(shù)條件數(shù) 相對傳播主要取決于相對傳播主要取決于條件數(shù)條件數(shù) 條件數(shù)很大條件數(shù)很大 病態(tài)問題病態(tài)問題 *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估計估計 101dxexIxnn11(1)1nInen 算法一算法一: 分部積分分部積分遞推公式遞推公式 In=1 nIn-1, n=1,20 I0=1-1/e I1 I2 I20 誤差很大誤差很大(見書見書P8) ， n = n n-1, 20 =(20!) 0 ，不穩(wěn)定，不穩(wěn)定算法二：遞推公式算法二：遞推公式 In-1=(1 In)/n, n= 20 ,1I20 估計式中點估計式中點 I19 I1 I0 誤差很小誤差

17、很小 n-1 = n /n, 0 = 20 /(20!)，穩(wěn)定，穩(wěn)定*11,nnInI 例例1.6 (病態(tài)問題病態(tài)問題)（保留（保留4位有效數(shù)字）位有效數(shù)字）x1=x2=x3=1 x1=1.1650, x2= 0.0003, x3= 2.0004. 病態(tài)問題病態(tài)問題: 很小的變化數(shù)據(jù)卻導致解產生了很大的很小的變化數(shù)據(jù)卻導致解產生了很大的變化。變化。區(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 設計算法基本原則設計算法基本原則計算精度：收斂性、穩(wěn)定性計算精度：收斂性、穩(wěn)定性計算速度：計算量、收斂速度、多個計算速度：計算量、收斂速度、多個CPU通信通信計算空間：存儲量計算空間：存儲量注意事項注意事項病態(tài)問題病態(tài)問題速度細節(jié)速度細節(jié)(加法、乘法，函數(shù)加法、乘法，函數(shù)) 計算多項式的值計算多項式的值存儲細節(jié)存儲細節(jié)(降維降維) 計算多項式的值計算多項式的值穩(wěn)定性細節(jié)穩(wěn)定性細節(jié)(相

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

20、 即是多項式即是多項式 p(x) 的值，算法過程只需的值，算法過程只需n次乘法次乘法和和n次加法，此算法稱為秦九韶算法次加法，此算法稱為秦九韶算法.0121)()(axaxaxaxaxpnnn p=an, p=px + an-k ( k =1,n)存儲細節(jié)存儲細節(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ù)字計算：位有效數(shù)字計算：(1234 + 0.4) + 0.3=1234問題：問題：(x+y)+z 和和 x+(y+z) 相等嗎？相等嗎？改進方法：先加小的數(shù)改進方法：先加小的數(shù)分母接近于分母接近于 問題：當問題：當 x充分大時充分大時, 計