第一章數(shù)值計(jì)算方法與誤差分析

1、 數(shù)值計(jì)算方法：研究怎樣利用計(jì)算工具求出數(shù)學(xué)問題的數(shù)值解，并對算法的收斂性、穩(wěn)定性和誤差進(jìn)行分析計(jì)算的全過程。 構(gòu)建一個完整的數(shù)值算法，包含著以下環(huán)節(jié)：構(gòu)建一個完整的數(shù)值算法，包含著以下環(huán)節(jié)： 1. 提出數(shù)值問題（即對對象建立數(shù)學(xué)模型）提出數(shù)值問題（即對對象建立數(shù)學(xué)模型） 2 .構(gòu)思處理數(shù)值問題的基本思想（即提出理論）構(gòu)思處理數(shù)值問題的基本思想（即提出理論） 3 .列出計(jì)算公式列出計(jì)算公式 4 .設(shè)計(jì)程序框圖設(shè)計(jì)程序框圖 5 .編制源程序并調(diào)試編制源程序并調(diào)試 6 .做出算法的誤差分析做出算法的誤差分析 從工程實(shí)際中抽象出來的數(shù)學(xué)問題往往很復(fù)雜，典型的有：從工程實(shí)際中抽象出來的數(shù)學(xué)問題往往很復(fù)

2、雜，典型的有：)(minxfXx1、數(shù)據(jù)點(diǎn)的插值、數(shù)據(jù)點(diǎn)的插值2 、曲線擬和、曲線擬和3、復(fù)雜函數(shù)的微積分運(yùn)算、復(fù)雜函數(shù)的微積分運(yùn)算4、非線性方程、非線性方程f(x)=0的根的求解的根的求解5、當(dāng)、當(dāng)n很大時線性方程組很大時線性方程組AX=B的求解的求解6、常微分方程的求解參考書籍的幾種名稱：參考書籍的幾種名稱：1、數(shù)值分析、數(shù)值分析2、數(shù)值計(jì)算原理、數(shù)值計(jì)算原理3、計(jì)算方法、計(jì)算方法4、算法設(shè)計(jì)、算法設(shè)計(jì)5、計(jì)算機(jī)數(shù)值計(jì)算方法與程序設(shè)計(jì)、計(jì)算機(jī)數(shù)值計(jì)算方法與程序設(shè)計(jì)數(shù)值計(jì)算中的誤差數(shù)值計(jì)算中的誤差 1、誤差的種類和來源、誤差的種類和來源 模型誤差模型誤差 觀測誤差觀測誤差 截斷誤差截斷誤差

3、舍入誤差舍入誤差2、誤差的有關(guān)概念：、誤差的有關(guān)概念： 絕對誤差：絕對誤差： xxx)(真值近似值 絕對誤差限：絕對誤差限： 1*)(xxx 相對誤差相對誤差： xxxxxxxxxr)()( 相對誤差限：相對誤差限： 2)(xr相對誤差限的概念 在實(shí)際計(jì)算中, 由于(x)與x都不能準(zhǔn)確地求得,因此相對誤差 r(x)也不可能準(zhǔn)確地得到, 我們只能估計(jì)它的大小范圍。即指定一個適當(dāng)小的正數(shù)，使 |r(x)|= |(x)|/| x* | 稱為近似值x*的相對誤差限相對誤差限。 當(dāng)|r(x)|較小時，可以用下式來計(jì)算： =/|x*|有效數(shù)字有效數(shù)字 為了既能表示近似數(shù)的大小，又能表示近似數(shù)的精確程度，我

4、們下面介紹有效數(shù)字的概念（注意：有效數(shù)字既能表示近似數(shù)的大小，又能表示近似數(shù)的精確程度）。 半個單位的概念 我們知道，當(dāng)x有很多位數(shù)字時，常常按照“四舍五入”原則取前幾位數(shù)字作為x的近似值x*。 例1 設(shè) x = = 3.1415926 取x1*=3作為的近似值,則|1(x)|=0.1415 0.5100；取x2*=3.14，則|2(x)|=0.00159 0.510-2；取x3*=3.1416, 則|3(x)|=0.0000074 0.510-4 。它們的誤差都不超過末位數(shù)字的半個單位半個單位。 有效數(shù)字的概念 定義3 若近似值x*的絕對誤差限是某一位上的半個單位，該位到x*的第一位非零數(shù)字

5、一共有n位，則稱近似值x*有n位有效數(shù)字，或說x*精確到該位。 準(zhǔn)確數(shù)本身有無窮多位有效數(shù)字，即從第一位非零數(shù)字以后的所有數(shù)字都是有效數(shù)字。 有效數(shù)字舉例 如例1中的x*1，x*2 ,x*3,分別有1,3,5位有效數(shù)字。 實(shí)際上，用四舍五入法取準(zhǔn)確值x 的前n位（不包括第一位非零數(shù)字前面的零）作為它的近似值x*時，x*有n位有效數(shù)字。 例2 設(shè) x = 4.26972，則按四舍五入法，取2位，x1*=4.3有效數(shù)字為2位,取3位，x2*=4.27,有效數(shù)字為3位，取4位，x3*=4.270，有效數(shù)字為4位。 特別注意特別注意 近似值后面的零不能隨便省去，近似值后面的零不能隨便省去， 如如例例2

6、中中4.27和和4.270，前者精確到，前者精確到4.27,有效有效數(shù)字為數(shù)字為3位，取位，取4位，位，x3*=4.270,有效數(shù)字有效數(shù)字為為4位。可見位?？梢?它們的近似程度完全不同它們的近似程度完全不同, 與準(zhǔn)確值的最大誤差也完全不同。與準(zhǔn)確值的最大誤差也完全不同。 有效數(shù)字和絕對誤差的關(guān)系 定義3換一種說法就是：設(shè)x的近似值 x*= 0.a1a2 an 10p若其絕對誤差 |(x)|=|xx*| 0.5 10p-n則稱近似數(shù)x*具有n 位有效數(shù)字。這里p為整數(shù)，a1 , a2 , , an 是0到9中的一個數(shù)字且a10 。 例如，若x*=0.2315610-2是x 的具有五位有效數(shù)字的

7、近似值，則絕對誤差是 |xx*| 0.5 10-2-5 = 0.5 10-7 定義3或式 |(x)|=|xx*| 0.5 10p-n建立了絕對誤差(限)和有效數(shù)字之間的關(guān)系。由于n 越大，10p-n的值越小，所以有效數(shù)字位越多，則絕對誤差有效數(shù)字位越多，則絕對誤差(限限)越小越小。 有效數(shù)字與相對誤差的關(guān)系 定理1 若近似數(shù)x*具有n位有效數(shù)字，則其相對誤差為 |r(x)| 1/(2a1) 10-(n-1)其中a10是x*的第一位有效數(shù)字。 定理1說明有效數(shù)字位越多,相對誤差(限)越小。 定理2 形式如x*= 0.a1a2 an 10p的近似數(shù)x*，若其相對誤差滿足 |r(x)| 1/2(a1

8、+1) 10-(n-1)則x* 至少有n位有效數(shù)字。 由此可知，有效數(shù)字位數(shù)可刻畫近似數(shù)的精確度，相對誤差相對誤差(限限)與有效數(shù)字的位數(shù)有關(guān)與有效數(shù)字的位數(shù)有關(guān)。 有效數(shù)字與相對誤差關(guān)系舉例 注意從并不能保證x*一定具有n位有效數(shù)字。 如 x=sin29020=0.4900 設(shè)其近似值 x*=0.484 , 其相對誤差為我們不能由此推出x*有兩位有效數(shù)字，這是因?yàn)?x-x*=0.4900-0.484=0.00600.005即可知近似值x*并不具有兩位有效數(shù)字。 實(shí)際上, x*只有一位有效數(shù)字。|r(x)| 1/(2a1) 10-(n-1)12(110421104210125. 0012397

9、. 0484. 0484. 04900. 0數(shù)值運(yùn)算中誤差的影響數(shù)值運(yùn)算中誤差的影響 要分析數(shù)值運(yùn)算中誤差的傳播，首先就要估計(jì)數(shù)值運(yùn)算中的誤差。數(shù)值運(yùn)算的誤差估計(jì)情況較復(fù)雜, 通常利用微分來估計(jì)誤差。 二元函數(shù)二元函數(shù) 設(shè)數(shù)學(xué)問題的解y與變量x1 , x2有關(guān), y=f(x1,x2)。若x1,x2的近似值為x1*, x2*,相應(yīng)解為y*,則當(dāng)數(shù)據(jù)誤差較小時解的絕對誤差 (y)=yy*=f(x1,x2 )f(x1*,x2* ) dy=f (x1,x2 )/x1*(x1)+f (x1,x2 )/x2*(x2)解的相對誤差 r(y) dy/y =f (x1,x2 )/xi*xi/ f (x1,x2

10、)*r(xi) (i=1,2) 利用這兩式可得到兩數(shù)和、差、積、商的誤差估計(jì)。算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性 一、算法的數(shù)值穩(wěn)定性概念一、算法的數(shù)值穩(wěn)定性概念 所謂算法算法，是指對一些數(shù)據(jù)按某種規(guī)定的順序進(jìn)行的運(yùn)算序列。在實(shí)際計(jì)算中，對于同一問題我們選用不同的算法, 所得結(jié)果的精度往往大不相同。這是因?yàn)槌跏紨?shù)據(jù)的誤差或計(jì)算中的舍入誤差在計(jì)算過程中的傳播，因算法不同而異，于是就產(chǎn)生了算法的數(shù)值穩(wěn)定性問題。一個算法, 如果計(jì)算結(jié)果受誤差的影響小，就稱這個算法具有較好的數(shù)值穩(wěn)數(shù)值穩(wěn)定性定性。否則，就稱這個算法的數(shù)值穩(wěn)定性不好。算法的數(shù)值穩(wěn)定性概念舉例算法的數(shù)值穩(wěn)定性概念舉例 例1 一元二次方程 X

11、2+2pX +q=0的兩個根分別是： x1= p+(p2q)0.5，x2= p(p2q)0.5 當(dāng)p= 0.5105,q=1時，方程的兩個根取11位有效數(shù)字為： x1=99999.999990 , x2=0.000010000000001 在高精度的計(jì)算機(jī)(進(jìn)制=10,字長t=8,浮點(diǎn)階碼下限L= 50,浮點(diǎn)階碼上限U=50)上直接用上述公式計(jì)算的結(jié)果為： x1=100000.00, x2=0 可見，結(jié)果x1很好，而x2很不理想，這說明直接用上述公式計(jì)算第二個根是不穩(wěn)定的，其原因在于在計(jì)算x2時造成相近兩數(shù)相減，從而使有效數(shù)字嚴(yán)重?fù)p失。請看下面的求解方法。一元二次方程 X2+2pX +q=0的

12、求解方法 根據(jù)根與系數(shù)的關(guān)系可知 x1x2=q=1所以 x2=1/x1因此，如果仍用上述方法算出x1，然后用 x2=1/x1計(jì)算x2，可得 x1=100000.00，x2=0.00001000 該結(jié)果是非常好的。這就說明這種算法有較好的數(shù)值穩(wěn)定性。 一般說來，當(dāng)|p|q|時，用公式x1= psign(p)(p2q)0.5 ,x2=q/x1來求解方程 X2+2pX+q=0 是數(shù)值穩(wěn)定的。 從而可知，算法數(shù)值穩(wěn)定性的討論甚為重要。 二、設(shè)計(jì)算法的若干原則二、設(shè)計(jì)算法的若干原則 為防止誤差使計(jì)算結(jié)果失真(失常）現(xiàn)象發(fā)生，要選用數(shù)值穩(wěn)定的計(jì)算公式，以保證算法的數(shù)值穩(wěn)定性。下面我們給出設(shè)計(jì)算法的若干原則

13、，并給出改善算法的例子，這些原則有助于鑒別算法的可靠性并防止誤差危害的現(xiàn)象產(chǎn)生。 （一）要避免相近兩數(shù)相減（一）要避免相近兩數(shù)相減 下面再舉幾個例說明改善算法的方法。 例x充分大時 1/x 1/(x+1)=1/x(x+1) (1+x)1/2 x1/2=1/(1+x) 1/2+x1/2 例 對于小的正數(shù) sin(x+) sinx=2cos(x+/2)sin(/2) (注： sin(x) sin(y)=2 cos (x+y)/2 sin (x-y)/2 ) 例 對于絕對值小的 x，可利用泰勒級數(shù) ex1= x+x2/2+x3/6+取前n項(xiàng)來計(jì)算。（二）要防止大數(shù)要防止大數(shù)“吃掉吃掉“小數(shù)，注意保護(hù)

14、重要數(shù)據(jù)小數(shù)，注意保護(hù)重要數(shù)據(jù) 在數(shù)值運(yùn)算中，參加運(yùn)算的數(shù)有時數(shù)量級相差很大，而計(jì)算機(jī)位數(shù)有限，如不注意運(yùn)算次序就可能出現(xiàn)大數(shù)“吃掉”小數(shù)的現(xiàn)象，影響計(jì)算結(jié)果的可靠性。 例5 在五位浮點(diǎn)十進(jìn)制計(jì)算機(jī)上，計(jì)算y=54321+0.4+0.3+0.4 如果按從左到右的順序進(jìn)行加法運(yùn)算，后三個數(shù)都在對階過程中被當(dāng)作零，得出含有較大絕對誤差的結(jié)果y=54321。要避免這種大數(shù)“吃掉”小數(shù)的現(xiàn)象，可以調(diào)整計(jì)算順序，采用先小數(shù)后大數(shù)的計(jì)算次序，即先將0.4,0.3,0.4加起來，然后再加上54321，結(jié)果等于54322。 一般情況下，若干數(shù)相加，采用絕對值較小者先加的算法，結(jié)果的相對誤差限較小。 （三）注意

15、簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累（三）注意簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累 同一個計(jì)算問題，如果能減少運(yùn)算次數(shù)，不但可以提高計(jì)算速度，而且能減少誤差的積累。簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累的例子簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累的例子 例6 計(jì)算多項(xiàng)式 P4(x)=0.0625x4+0.425x3+1.215x2+1.912x+2.1296的值。 如果先計(jì)算各項(xiàng)然后相加，需做十次乘法和四次加法。 如改用下式計(jì)算 (0.062 5x+0.425)x+1.215)x+1.912)x+2.129 6則只需做四次乘法和四次加法。 簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累的

16、例子簡化計(jì)算步驟、減少運(yùn)算次數(shù)、避免誤差積累的例子 又如計(jì)算 1/(1*2)+1/(2*3)+1/(1000*1001) 的值。 若一項(xiàng)一項(xiàng)進(jìn)行計(jì)算，不僅計(jì)算次數(shù)多，而且誤差積累也很大。若簡化成 11/1001 進(jìn)行計(jì)算，則整個計(jì)算只要一次求倒數(shù)和一次減法。（四）要避免絕對值小的數(shù)作除數(shù)（四）要避免絕對值小的數(shù)作除數(shù) 由式 (x1/x2)d(d(x1/x2)x2(x1)x1(x2)/ x22 , (x20)可知，當(dāng)除數(shù)x2接近于零時，商的絕對誤差就可能很大。因此 , 在數(shù)值計(jì)算中要盡量避免絕對值小的數(shù)作除數(shù), 避免的方法是把算式變形或改變計(jì)算順序。 例8 當(dāng)x接近于0時 (1-cosx)/si

17、nx的分子、分母都接近0，為避免絕對值小的數(shù)作除數(shù)，可將原式化為 (1-cosx)/sinx=sinx/(1+cosx) 例9 當(dāng)x 很大時，可化 x/(x+1)0.5x0.5=x(x+1)0.5 + x0.5控制誤差傳播的例子控制誤差傳播的例子 例10 計(jì)算積分 In=01 xn ex-1dx，n=0,1, 2, , 9利用分部積分法，可得 In= xn ex-1| 01 01 ex-1dxn =1 n01 xn-1 ex-1dx =1 nIn-1從而有遞推公式 I0= 01 ex-1dx= ex-1 | 01 = 1-1-e-1 0.6321 In= 1 nIn-1 （n=0, 1, 2,

18、 , 9） 計(jì)算積分In=01 xn ex-1dx的過程 如果直接應(yīng)用遞推公式 I0= 01 ex-1dx= ex-1| 01 = 1-1-e-1 0.6321 In= 1 nIn-1 （n=1, 2, , 9）用四位小數(shù)計(jì)算依次得到： 0.6321, 0.3679, 0.2642, 0.2074, 0.1704 0.1480, 0.1120, 0.2160, -0.7280, 7.5520由此看到I8為負(fù)值、 I9 1，顯然與一切0In1（由于 e-1/(n+1)= min(ex-1)01xndxIn (0 x1) max (ex-1)01xndx=1/(n+1) )矛盾。事實(shí)上，從I7開始

19、已經(jīng)連一位有效數(shù)字也沒有了（ I715 |r(I9)|= |(I9) |/I9 1500% (0I91) 這樣求得的結(jié)果是完全不可靠的，因此這個算法是不穩(wěn)定的。計(jì)算積分In=01 xn ex-1dx 的改進(jìn)方法 根據(jù) In= 1 nIn-1 可知 In-1 =(1 In)/n 再由 e-1/10 I9 1/10取 I9 (e-1/10 +1/10)/2 =0.0684按 I9 (e-1/10 +1/10)/2 =0.0684 In-1=(1 In)/n （n=9,8,7,1)計(jì)算，保留四 位小數(shù)依次得I9 , I8 , I7 , I6 , I5 , I4 , I3 , I2 , I1 , I0為： 0.0684, 0.1035, 0.1121, 0.1268, 0.1455, 0.1709, 0.2073, 0.2642, 0.3679, 0.6321I0 = 0.6321全部為有