數(shù)值分析NumericalAnalysis

1、數(shù)值分析NumericalAnalysis&教材教材 (Text Book) 數(shù)值計(jì)算方法數(shù)值計(jì)算方法 李維國(guó)、黃炳家、同登科、王子亭李維國(guó)、黃炳家、同登科、王子亭 編著編著 2004& 參考書目參考書目 (Reference) 數(shù)值計(jì)算方法數(shù)值計(jì)算方法 () 林成森林成森 編著編著 （科學(xué)出版社（科學(xué)出版社 1998 Principle of Numerical Analysis 數(shù)值分析原理數(shù)值分析原理 封建湖、車剛明、聶玉峰封建湖、車剛明、聶玉峰 編著編著 （科學(xué)出版社，（科學(xué)出版社，2001 課程評(píng)分方法課程評(píng)分方法 (Grading Policies) 平時(shí)成績(jī)和上機(jī)

2、實(shí)驗(yàn)平時(shí)成績(jī)和上機(jī)實(shí)驗(yàn) (25%左右左右) 期末考試成績(jī)期末考試成績(jī) (75%左右左右) 提問：數(shù)值計(jì)算方法是做什么用的？提問：數(shù)值計(jì)算方法是做什么用的？研究對(duì)象研究對(duì)象：數(shù)值問題數(shù)值問題有限個(gè)輸入數(shù)據(jù)（問題的自有限個(gè)輸入數(shù)據(jù)（問題的自變量、原始數(shù)據(jù)）與有限個(gè)輸出數(shù)據(jù)（待求解數(shù)據(jù)）之變量、原始數(shù)據(jù)）與有限個(gè)輸出數(shù)據(jù)（待求解數(shù)據(jù)）之間函數(shù)關(guān)系的一個(gè)明確無歧義的描述。間函數(shù)關(guān)系的一個(gè)明確無歧義的描述。如一階微分方程初值問題如一階微分方程初值問題2(0)1dyxdxy求函數(shù)解析表達(dá)式求函數(shù)解析表達(dá)式( )yy x數(shù)學(xué)問題數(shù)學(xué)問題求函數(shù)求函數(shù) 在某些點(diǎn)在某些點(diǎn)( )yy x 1niix的近似函數(shù)值的近

3、似函數(shù)值數(shù)值問題數(shù)值問題程序程序設(shè)計(jì)設(shè)計(jì)上機(jī)上機(jī)計(jì)算計(jì)算設(shè)計(jì)高效、可設(shè)計(jì)高效、可靠的數(shù)值方法靠的數(shù)值方法數(shù)值數(shù)值問題問題求解求解近似結(jié)果近似結(jié)果輸出輸出重點(diǎn)討論重點(diǎn)討論數(shù)值問題的來源：數(shù)值問題的來源：實(shí)際實(shí)際問題問題建立數(shù)學(xué)模型建立數(shù)學(xué)模型數(shù)值數(shù)值問題問題數(shù)值方法的設(shè)計(jì)原數(shù)值方法的設(shè)計(jì)原則則收斂性：方法的可行性收斂性：方法的可行性穩(wěn)定性：初始數(shù)據(jù)等產(chǎn)生的誤差對(duì)結(jié)果的影響穩(wěn)定性：初始數(shù)據(jù)等產(chǎn)生的誤差對(duì)結(jié)果的影響便于編程實(shí)現(xiàn)：邏輯復(fù)雜度要小便于編程實(shí)現(xiàn)：邏輯復(fù)雜度要小計(jì)算量要?。簳r(shí)間復(fù)雜度要小，運(yùn)行時(shí)間要短計(jì)算量要?。簳r(shí)間復(fù)雜度要小，運(yùn)行時(shí)間要短存貯量要盡量?。嚎臻g復(fù)雜度要小存貯量要盡量?。嚎臻g復(fù)

4、雜度要小可可靠靠性性分分析析計(jì)算復(fù)雜性計(jì)算復(fù)雜性誤差估計(jì)：運(yùn)算結(jié)果不能產(chǎn)生太大的偏差且誤差估計(jì)：運(yùn)算結(jié)果不能產(chǎn)生太大的偏差且能夠控制誤差能夠控制誤差1 誤誤 差差 /* Error */一、一、 誤差的來源與分類誤差的來源與分類 /* Source & Classification */ 1、從實(shí)際問題中抽象出數(shù)學(xué)模型、從實(shí)際問題中抽象出數(shù)學(xué)模型 模型誤差模型誤差 /* Modeling Error */ 2、通過觀測(cè)得到模型中某些參數(shù)（或物理量）的值、通過觀測(cè)得到模型中某些參數(shù)（或物理量）的值 觀測(cè)誤差觀測(cè)誤差 /* Measurement Error */ 3、數(shù)學(xué)模型與數(shù)值算法之

5、間的誤差求近似解、數(shù)學(xué)模型與數(shù)值算法之間的誤差求近似解 方法誤差方法誤差 (截?cái)嗾`差截?cái)嗾`差 /* Truncation Error */ ) 4、由于機(jī)器字長(zhǎng)有限，原始數(shù)據(jù)和計(jì)算過程會(huì)產(chǎn)生新的誤差、由于機(jī)器字長(zhǎng)有限，原始數(shù)據(jù)和計(jì)算過程會(huì)產(chǎn)生新的誤差 舍入誤差舍入誤差 /* Roundoff Error */二、二、 誤差分析的基本概念誤差分析的基本概念 /* Basic Concepts */ 設(shè)設(shè) 為真值（精確值），為真值（精確值）， 為為 的一個(gè)近似值的一個(gè)近似值 稱稱 為近似值為近似值 的絕對(duì)誤差，簡(jiǎn)稱誤差。的絕對(duì)誤差，簡(jiǎn)稱誤差。 xxx x exx 注：注：誤差可正可負(fù)，常常是無限位

6、的誤差可正可負(fù)，常常是無限位的絕對(duì)絕對(duì)誤差限誤差限/* accuracy */ 絕對(duì)值的上界絕對(duì)值的上界 exx 如：如：5314159110314159262.(.) 絕對(duì)絕對(duì)誤差還不能完全表示近似值的好壞誤差還不能完全表示近似值的好壞（絕對(duì)誤差（絕對(duì)誤差/* absolute error */）1 1 .Def近似值近似值 的誤差的誤差 與準(zhǔn)確值與準(zhǔn)確值 的比值：的比值：x e xexxxx 稱為近似值稱為近似值 的相對(duì)誤差，記作的相對(duì)誤差，記作reex x 注：注：實(shí)際計(jì)算時(shí)，相對(duì)誤差通常取實(shí)際計(jì)算時(shí)，相對(duì)誤差通常取rexxexx 因?yàn)橐驗(yàn)?21()()()()eeeexxexexxxx

7、xxex 1 2 .Def（相對(duì)誤差（相對(duì)誤差/* relative error */ ）相對(duì)相對(duì)誤差也可正可負(fù)誤差也可正可負(fù)rexxxx 1 3 .Def（有效數(shù)字有效數(shù)字/*Significant Digits*/ ）相對(duì)相對(duì)誤差限誤差限相對(duì)相對(duì)誤差的絕對(duì)值的上界誤差的絕對(duì)值的上界r /* relative accuracy */如：如：31415926. 314. 3141592. 3位位21102e 6位位51102e 若近似值若近似值 與準(zhǔn)確值的誤差與準(zhǔn)確值的誤差絕對(duì)絕對(duì)值不超過某一位的值不超過某一位的半個(gè)單位，該位到半個(gè)單位，該位到 的第一位非零數(shù)字共有的第一位非零數(shù)字共有 位，則

8、位，則x x nx n稱稱 有有 位有效數(shù)字位有效數(shù)字 有效數(shù)字有效數(shù)字(另外一種定義形式另外一種定義形式)用科學(xué)計(jì)數(shù)法，記用科學(xué)計(jì)數(shù)法，記 其中其中 ， 若若 （即（即 的截取按四舍五入規(guī)則），則稱的截取按四舍五入規(guī)則），則稱 為有為有 位有效位有效數(shù)字，精確到數(shù)字，精確到 。12010mnx.a aa 01 a| 0 5 10m nxx. nax nm 10 120 19, ,nmZ a aa n3.1415926535897932;3.1415 例例1：?jiǎn)枺簡(jiǎn)枺?有幾位有效數(shù)字？請(qǐng)證明你的結(jié)論。有幾位有效數(shù)字？請(qǐng)證明你的結(jié)論。 *10501050*and103141504131 .| ,

9、.*證明：證明：有有 位有效數(shù)字，精確到小數(shù)點(diǎn)后第位有效數(shù)字，精確到小數(shù)點(diǎn)后第 位。位。43規(guī)格化形式規(guī)格化形式注：注：若若 的每一位都是有效數(shù)字，則的每一位都是有效數(shù)字，則 稱是稱是有效數(shù)有效數(shù)x x 特別，經(jīng)特別，經(jīng)“四舍五入四舍五入”得到的數(shù)均為有效數(shù)得到的數(shù)均為有效數(shù)1 1 .Th1 2010mknx.aaaa 將將 的近似值的近似值 表示為表示為 ，若若 是有效數(shù)字，則相對(duì)誤差不超過是有效數(shù)字，則相對(duì)誤差不超過 ；反之，若已知相對(duì)誤差反之，若已知相對(duì)誤差 ，且有，且有 ，11102()k xre 1102kre x kaka則則 必為有效數(shù)字。必為有效數(shù)字。證明：證明：一方面，一方面

10、， 是有效數(shù)字，是有效數(shù)字， ka則則1102m kxx 且且111 101010mmx 111101210102()m kkmrxxex 另一方面，另一方面，11101022km kxxx 1102krxxex 10mx 必為有效數(shù)字，必為有效數(shù)字， ka即即 至少有至少有 位有效數(shù)字位有效數(shù)字x k注注: :定理定理1說明了說明了有效數(shù)字與相對(duì)誤差限的關(guān)系有效數(shù)字與相對(duì)誤差限的關(guān)系. 有效數(shù)字有效數(shù)字 相對(duì)誤差限相對(duì)誤差限1212110 51010010201102mnnrmnnne.ex.a aa.a aaa 已知已知 x* 有有 n 位有效數(shù)字，則其相對(duì)誤差限為位有效數(shù)字，則其相對(duì)誤差

11、限為 相對(duì)誤差限相對(duì)誤差限 有效數(shù)字有效數(shù)字112111111001021101100 51021|()()()nmrnmmnxxex.a aaa.a 1111021()nrea 已知已知 x* 的相對(duì)誤差限可寫為的相對(duì)誤差限可寫為則則可見可見 x* 至少有至少有 n 位有效數(shù)字。位有效數(shù)字。例例2 2：為使：為使 的相對(duì)誤差小于的相對(duì)誤差小于0.001%, ,至少應(yīng)取幾位有至少應(yīng)取幾位有效數(shù)字？效數(shù)字？*解：解：假設(shè)假設(shè) * 取到取到 n 位有效數(shù)字，則其相對(duì)誤差上限為位有效數(shù)字，則其相對(duì)誤差上限為111102nrea 要保證其相對(duì)誤差小于要保證其相對(duì)誤差小于0.001%，只要保證其上限滿足

12、，只要保證其上限滿足111100 0012.%nrea 已知已知 a1 = 3，則從以上不等式可解得，則從以上不等式可解得 n 6 log6，即即 n 6，應(yīng)取，應(yīng)取 * 。例例3 3 計(jì)算下列多項(xiàng)式的值計(jì)算下列多項(xiàng)式的值nnnaxaxaxp10)(為已知數(shù)據(jù)為已知數(shù)據(jù)01,na aax分析：分析：輸入數(shù)據(jù)為輸入數(shù)據(jù)為 ，輸出數(shù)據(jù)為，輸出數(shù)據(jù)為 ，若直接由，若直接由 算出算出 ，再乘相應(yīng)的系數(shù)，再乘相應(yīng)的系數(shù) 并并相加，則要做次相加，則要做次 乘法和乘法和 次加法，占用個(gè)次加法，占用個(gè) 存儲(chǔ)單元。存儲(chǔ)單元。 0,naaxx)(xpnxx,2021,aaann12()nn n12 n秦九韶方法，

13、也稱為秦九韶方法，也稱為HornerHorner算法算法 用遞推公式表示為用遞推公式表示為nnaxaxaxaxp)()(11000ab xbabiii1ni, 2 , 1)(xpbnn只用只用 次乘法和次乘法和 次加法，并占用次加法，并占用 個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元 n2nn三、數(shù)值算法及穩(wěn)定性三、數(shù)值算法及穩(wěn)定性 /* Numerical Algorithm and Stability */大家一起猜？大家一起猜？ dxe2x1011 / e解法之一解法之一：將將 作作Taylor展開后再積分展開后再積分2xe 91!4171!3151!21311)!4!3!21(10864210dxxxxxd

14、xe2xS4R4 /* Remainder */,104 Sdxe2x取取則則 111!5191!414R稱為截?cái)嗾`差稱為截?cái)嗾`差 /* Truncation Error */005091!414.R 這這里里7430024010333014211013114.S 0010200050. | 舍入誤差舍入誤差 /* Roundoff Error */ |006000100050102.dxe-x 的的總總體體誤誤差差計(jì)計(jì)算算= 0.747 由截去部分由截去部分/* excluded terms */引起引起由留下部分由留下部分/* included terms */引起引起例例4 4 近似計(jì)算

15、近似計(jì)算210 xedx 10 333333. 10 0238042. 一個(gè)算法如果輸入數(shù)據(jù)有擾動(dòng)（即誤差），而計(jì)算一個(gè)算法如果輸入數(shù)據(jù)有擾動(dòng)（即誤差），而計(jì)算過程中舍入誤差不增長(zhǎng)過程中舍入誤差不增長(zhǎng), ,則稱此算法是數(shù)值穩(wěn)定的，否則則稱此算法是數(shù)值穩(wěn)定的，否則此算法就稱為不穩(wěn)定的。此算法就稱為不穩(wěn)定的。 1 4 .Def（數(shù)值穩(wěn)定性（數(shù)值穩(wěn)定性/ /* Numerical Stability */） 對(duì)數(shù)學(xué)問題本身如果輸入數(shù)據(jù)有微小擾動(dòng)，引起對(duì)數(shù)學(xué)問題本身如果輸入數(shù)據(jù)有微小擾動(dòng)，引起輸出數(shù)據(jù)（即問題真解）的很大擾動(dòng)，這就是病態(tài)問輸出數(shù)據(jù)（即問題真解）的很大擾動(dòng)，這就是病態(tài)問題。題。1 5 .

16、Def（病態(tài)問題（病態(tài)問題/ /* ill-posed problem */） 它是數(shù)學(xué)問題本身性質(zhì)所決定的，與算法無關(guān)，它是數(shù)學(xué)問題本身性質(zhì)所決定的，與算法無關(guān)，也就是說對(duì)病態(tài)問題，用任何算法（或方法）直接計(jì)也就是說對(duì)病態(tài)問題，用任何算法（或方法）直接計(jì)算都將產(chǎn)生不穩(wěn)定性。算都將產(chǎn)生不穩(wěn)定性。 此公式精確成立此公式精確成立80001050 .IIE記為記為*0I632120560111100.edxeeIx 則初始誤差則初始誤差111111110010 nI)e(ndxexeIdxexennnn10109111012111312141315141 10 36787944.1 100 0881

17、28001 110 030592001 120 632896001 137 22764801 1494 9594241 151423 3914II.II.II.II.II.II.II. ? ! !What happened?!例例5 5 計(jì)算計(jì)算1010 1 2, , ,.nxnIx e dxne 11101011nxnxnnIx enxe dxn Ie 公式一：公式一：考察第考察第n步的誤差步的誤差nE11|(1)(1)|nnnnnEIInInI | !01En|Enn 我們有責(zé)任改變。我們有責(zé)任改變。造成這種情況的是不穩(wěn)定的算法造成這種情況的是不穩(wěn)定的算法 /* unstable algo

18、rithm */迅速積累，誤差呈遞增趨勢(shì)。迅速積累，誤差呈遞增趨勢(shì)。初始的小擾動(dòng)初始的小擾動(dòng)801050| .E)1(1111nnnnInIInI 公式二：公式二：注意此公式與公式一注意此公式與公式一在理論上等價(jià)。在理論上等價(jià)。方法：先估計(jì)一個(gè)方法：先估計(jì)一個(gè)IN , ,再反推要求的再反推要求的In ( n N )。11)1(1 NINeN1112(1)1NNIIe NN 可取可取0* NNNIIEN, ,時(shí)時(shí)當(dāng)當(dāng)()()()()()()1514151314121311121011121110 04274623321616110 06381691815110 06687022014110 07

19、177921413110 07735173212110 08387711511110 367879442I.eII.II.II.II.II.II. ()01110 632120561II.取取考察反推一步的誤差：考察反推一步的誤差：()()1111|11|NNNNEIIENNN 以此類推，對(duì)以此類推，對(duì) n N 有：有：|) 1(.) 1(1|NnEnNNE 誤差逐步遞減誤差逐步遞減, 這樣的算法稱為穩(wěn)定的算法這樣的算法稱為穩(wěn)定的算法 /* stable algorithm */ 在我們今后的討論中，誤差將不可回避，在我們今后的討論中，誤差將不可回避， 算法的穩(wěn)定性將會(huì)是一個(gè)非常重要的話題。算

20、法的穩(wěn)定性將會(huì)是一個(gè)非常重要的話題。例例6：蝴蝶效應(yīng)：蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日紐約的一只蝴蝶翅膀一拍，風(fēng)和日 麗的北京就刮起臺(tái)風(fēng)來了？！麗的北京就刮起臺(tái)風(fēng)來了？！紐約紐約北京北京這是一個(gè)病態(tài)問題這是一個(gè)病態(tài)問題2 誤差分析的方法和原則誤差分析的方法和原則 /* Error Analysis */一、誤差分析的方法一、誤差分析的方法1、向前誤差分析法：利用誤差限，、向前誤差分析法：利用誤差限，隨著計(jì)算過程隨著計(jì)算過程 逐步向前進(jìn)行分析，直至估計(jì)出最后的結(jié)果。（例逐步向前進(jìn)行分析，直至估計(jì)出最后的結(jié)果。（例4 4） 1212()()()xxxx 121221()()()xxxxxx

21、 12211222()()()xxxxxxx 注：注：兩個(gè)近似數(shù)兩個(gè)近似數(shù) ，四則運(yùn)算得到的誤差限分別為，四則運(yùn)算得到的誤差限分別為12,xx（1 1）（2 2）對(duì)于函數(shù)對(duì)于函數(shù) y = f (x)，若用，若用 x* 取代取代 x，將對(duì)，將對(duì)y 產(chǎn)生什產(chǎn)生什 么影響么影響？分析：分析：e*(y) = f (x*) f (x) e*(x) = x* xMean Value Theorem( )()fxx x* 與與 x 非常接近時(shí)，可認(rèn)為非常接近時(shí)，可認(rèn)為 ，則有：，則有：( )()ffx ( )()( )e yf xe x 即：即： 產(chǎn)生的誤差經(jīng)過產(chǎn)生的誤差經(jīng)過 作用后被放大作用后被放大/ /

22、縮小了縮小了 倍。倍。故稱故稱 為放大為放大/縮小縮小因子因子 /* amplification factor */ 或或 絕對(duì)絕對(duì)條件數(shù)條件數(shù) /* absolute condition number */.x f()f x ()f x ( )|( )|()reyeyf x ( )|( )|rexexx ()( )( )()()( )()rrf xf xxxxeyxxf xxxfxexf x 相對(duì)誤差條件數(shù)相對(duì)誤差條件數(shù) /* relative condition number*/ f 的條件數(shù)在某一點(diǎn)是小的條件數(shù)在某一點(diǎn)是小 大，則稱大，則稱 f 在該點(diǎn)是好條在該點(diǎn)是好條件的件的 /* w

23、ell-conditioned */ 壞條件的壞條件的 /* ill-conditioned */。注：關(guān)于多元函數(shù)注：關(guān)于多元函數(shù) 可類似討論，可類似討論，理論工具：理論工具：Taylor公式公式 (教材第教材第6頁頁).,(21nx,x,xfy ()( )()fxexf x 例例7 7105%x 設(shè)設(shè) ,試求函數(shù)試求函數(shù) 的相對(duì)誤差限的相對(duì)誤差限. ( )nf xx 解：解：由題設(shè)知由題設(shè)知:近似值為近似值為 ,絕對(duì)誤差限為絕對(duì)誤差限為 10 x ()5%x 1111()()nnfxxxnnx re ffx e xe xeff xf xnxn()() ()()0.005()()() 2、向

24、后誤差分析法：把舍入誤差的累積與導(dǎo)出、向后誤差分析法：把舍入誤差的累積與導(dǎo)出 的已的已知知 量量 的某種攝動(dòng)（微小誤差）等價(jià)起來，的某種攝動(dòng)（微小誤差）等價(jià)起來， A 12,nx xx即令即令1122(,)nnAf xxx 利用攝動(dòng)理論，由利用攝動(dòng)理論，由 的界估計(jì)出最后的舍入誤差界。的界估計(jì)出最后的舍入誤差界。i 3、區(qū)間分析法：把參加運(yùn)算的數(shù)都看成區(qū)間量，、區(qū)間分析法：把參加運(yùn)算的數(shù)都看成區(qū)間量，根根據(jù)區(qū)間運(yùn)算規(guī)則求得最后結(jié)果的近似值和誤差限。據(jù)區(qū)間運(yùn)算規(guī)則求得最后結(jié)果的近似值和誤差限。4、概率分析法：利用概率統(tǒng)計(jì)方法，將、概率分析法：利用概率統(tǒng)計(jì)方法，將數(shù)據(jù)和運(yùn)算中數(shù)據(jù)和運(yùn)算中 的舍入誤

25、差視為適合某種分布的隨機(jī)變量，然后確定計(jì)的舍入誤差視為適合某種分布的隨機(jī)變量，然后確定計(jì)算結(jié)果的誤差分布。算結(jié)果的誤差分布。 二、幾點(diǎn)注意事項(xiàng)二、幾點(diǎn)注意事項(xiàng) /* Remarks */1、 避免相近二數(shù)相減避免相近二數(shù)相減例：例：a1，a2，各有，各有5位有效數(shù)字。位有效數(shù)字。 而而 a2 a1，只剩下，只剩下1位有效數(shù)字位有效數(shù)字。 幾種經(jīng)驗(yàn)性避免方法：幾種經(jīng)驗(yàn)性避免方法：;xxxx ;1lnlnln xxx當(dāng)當(dāng) | x | 1 時(shí)：時(shí)：;2sin2cos12xx .6121112xxxex2、 避免小分母避免小分母 : 分母小會(huì)造成浮點(diǎn)溢出分母小會(huì)造成浮點(diǎn)溢出 /* over flow

26、*/3、避免大數(shù)吃小數(shù)、避免大數(shù)吃小數(shù)例：用單精度計(jì)算例：用單精度計(jì)算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242 在計(jì)算機(jī)內(nèi)，在計(jì)算機(jī)內(nèi)，109存為存為 1010，1存為存為 101。做加法時(shí)，兩加做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1 的指的指數(shù)部分須變?yōu)閿?shù)部分須變?yōu)?010，則：，則：1 = 0.01 1010，取單精度時(shí)就成為：，取單精度時(shí)就成為： 109 1010+0.00000000 1010=0.10000000 1010大數(shù)吃小數(shù)大數(shù)吃小數(shù)024,102422921 aacbbxaacbbx算法算法2：先解出：先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx求和時(shí)從小到大相加，可使和的誤差