第1章數(shù)值分析-緒論

第1章緒論基礎(chǔ)部數(shù)學(xué)教研室

彭曉華數(shù)值分析參考教材(TextBook)*《數(shù)值分析》，曾繁慧主編，中國(guó)礦業(yè)大學(xué)出版社*《數(shù)值分析》，李慶揚(yáng)王能超易大義編，清華大學(xué)出版社基礎(chǔ)知識(shí)微積分、線性代數(shù)、常微分方程數(shù)值分析——緒論1.1

數(shù)值分析的研究對(duì)象與特點(diǎn)數(shù)值分析(NumericalAnalysis):

數(shù)值分析也稱計(jì)算數(shù)學(xué)，是數(shù)學(xué)科學(xué)的一個(gè)分支，它研究用計(jì)算機(jī)求解各種數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法、理論與軟件實(shí)現(xiàn)。本課程的主要內(nèi)容：誤差與誤差分析非線性代數(shù)方程組求解線性代數(shù)方程組求解插值最佳逼近數(shù)值微分與數(shù)值積分常微分方程初值問(wèn)題的數(shù)值解法數(shù)值分析的算法要求：（1）面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)的特點(diǎn)提供切實(shí)可行的有效算法，即算法只能包括加、減、乘、除運(yùn)算和邏輯運(yùn)算，這些計(jì)算是計(jì)算機(jī)能直接處理的運(yùn)算（2）有可靠的理論分析，能任意逼近并達(dá)到精度要求，對(duì)近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對(duì)誤差進(jìn)行分析，這些都建立在相應(yīng)數(shù)學(xué)理論的基礎(chǔ)上數(shù)值分析的算法要求：（4）要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上滿足上述三點(diǎn)外，還要通過(guò)數(shù)值實(shí)驗(yàn)證明是行之有效的。（3）要有好的計(jì)算復(fù)雜性，時(shí)間復(fù)雜性好是指節(jié)省計(jì)算時(shí)間，空間復(fù)雜性好是指節(jié)省存儲(chǔ)空間，這也是建立算法要研究的問(wèn)題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)一個(gè)面向計(jì)算機(jī)，有可靠理論分析、計(jì)算復(fù)雜性好并且通過(guò)數(shù)值實(shí)驗(yàn)?zāi)軌蝌?yàn)證算法是行之有效的算法就是一個(gè)好的數(shù)值算法。如何學(xué)好這門(mén)課掌握微積分、線性代數(shù)、常微分方程的基本內(nèi)容注意掌握基本原理和基本方法，要注意方法處理的技巧及其與計(jì)算機(jī)的結(jié)合要重視誤差分析、收斂性及穩(wěn)定性的基本理論注意用所學(xué)數(shù)值方法解決實(shí)際計(jì)算問(wèn)題基本要求:確保出勤，有事請(qǐng)假認(rèn)真完成習(xí)題的演練一定數(shù)量的數(shù)值實(shí)驗(yàn)（利用MATLAB用數(shù)值方法解決實(shí)際問(wèn)題）結(jié)合自己的專業(yè)解決實(shí)際問(wèn)題數(shù)值分析——緒論1.2.1誤差的來(lái)源（1）模型誤差：在建立數(shù)學(xué)模型時(shí)對(duì)被描述的實(shí)際問(wèn)題進(jìn)行抽象簡(jiǎn)化而產(chǎn)生的模型與實(shí)際問(wèn)題之間的誤差稱為模型誤差（2）觀測(cè)誤差（測(cè)量誤差）：在數(shù)學(xué)模型中，根據(jù)實(shí)驗(yàn)觀測(cè)得到的數(shù)據(jù)誤差稱為觀測(cè)誤差或測(cè)量誤差1.2數(shù)值計(jì)算的誤差數(shù)值分析——緒論（3）方法誤差(截?cái)嗾`差)：當(dāng)數(shù)學(xué)模型不能得到精確解時(shí)，通常用數(shù)值方法求它的近似解，其近似解與精確解之間的誤差稱為方法誤差或截?cái)嗾`差。由Taylor多項(xiàng)式求的近似值。截?cái)嗾`差:例1數(shù)值分析——緒論由Taylor公式求ex的近似值。取n項(xiàng)近似:截?cái)嗾`差:例2數(shù)值分析——緒論由于計(jì)算機(jī)的字長(zhǎng)有限，原始數(shù)據(jù)在計(jì)算機(jī)上表示時(shí)要產(chǎn)生誤差，計(jì)算過(guò)程又有可能產(chǎn)生新的誤差，這種誤差稱為舍入誤差（4）舍入誤差：用0.3333近似代替1/3.例3舍入誤差:1/3-0.3333=0.000033….【注】（1）

數(shù)值分析中主要關(guān)心方法誤差和舍入誤差。不研究模型誤差和觀測(cè)誤差。（2）方法誤差將結(jié)合具體算法討論。（3）下面介紹舍入誤差，的基本概念和研究方法。數(shù)值分析——緒論1.2.2誤差的概念設(shè)x為精確值,a為x的一個(gè)近似數(shù)?！径x1】如果一、絕對(duì)誤差例如，用毫米刻度的米尺測(cè)量一長(zhǎng)度的近似值，它的誤差限是0.5mm.如讀出的長(zhǎng)度是765mm，則讀出和該長(zhǎng)度接近的刻度則稱δ為a的絕對(duì)誤差限(誤差限)近似數(shù)a的絕對(duì)誤差(誤差):是數(shù)值分析——緒論對(duì)于一般情形例4

絕對(duì)誤差的局限性例子?！咀ⅰ拷^對(duì)誤差（或誤差限）不能充分說(shuō)明近似數(shù)的精確程度。則即但有時(shí)記為二、相對(duì)誤差【定義2】(相對(duì)誤差限)實(shí)際運(yùn)算a=3.14是π的近似值。取5位,a=3.1416,δ≤0.000008三、有效數(shù)字例如【注】四舍五入后得到的近似數(shù)，從第一位非零數(shù)開(kāi)始直到最末位，有幾位就稱該近似數(shù)有幾位有效數(shù)字取3位,a=3.14,δ≤0.002誤差數(shù)值分析——緒論誤差近似數(shù)a的相對(duì)誤差:例5

若近似值

且a1是1到9中的一個(gè)整數(shù)，意整數(shù)。m為整數(shù)，a2,…,an為0到9中的任【定義3】【注】

近似數(shù)的有效數(shù)字不但給出了近似值的大小,而且還指出了它的絕對(duì)誤差限。數(shù)值分析——緒論成立,則稱a近似x有n位有效數(shù)字。的誤差限是某一位的半個(gè)單位，該位到的第一位非零數(shù)字共有n位，就說(shuō)有n位有效數(shù)字。它可以表示為則a=8.0000具有5位有效數(shù)字。設(shè)則例6因?yàn)閙=-2,所以n=2，即a有2位有效數(shù)字。設(shè)x

=8.00001，例7數(shù)值分析——緒論若則因?yàn)閙=-2,所以n=3，即a有3位有效數(shù)字。因?yàn)閙=1,所以n=5，即a有5位有效數(shù)字。如果以為單位,重力常數(shù)例8它們都有3位有效數(shù)字，因?yàn)榘吹谝环N寫(xiě)法數(shù)值分析——緒論根據(jù)前面的式子，這里如果以為單位，這里按第二種寫(xiě)法3位有效數(shù)字，絕對(duì)誤差限由于單位不同而不同盡管寫(xiě)法不同，但都具而相對(duì)誤差限相同，因?yàn)樽ⅲ海?）相對(duì)誤差和相對(duì)誤差限是無(wú)量綱的，

（3）有效位數(shù)與小數(shù)點(diǎn)后有幾位無(wú)關(guān)，

具有n位有效數(shù)字的近似數(shù)數(shù)值分析——緒論的絕對(duì)誤差限為越小在m相同的情況下，n越大，則（4）有效位數(shù)越多，絕對(duì)誤差限越小。（2）絕對(duì)誤差和絕對(duì)誤差限是有量綱的四、有效數(shù)字與相對(duì)誤差的關(guān)系設(shè)x的近似數(shù)為數(shù)值分析——緒論則a的相對(duì)誤差限為如果a具有n位有效數(shù)字，【定理1】反之，若a的相對(duì)誤差限則a至少具有n位有效數(shù)字四、有效數(shù)字與相對(duì)誤差的關(guān)系或證明：數(shù)值分析——緒論當(dāng)a具有n位有效數(shù)字時(shí)反之，由故a至少具有n位有效數(shù)字注：（5）有效位數(shù)越多，相對(duì)誤差限越小數(shù)值分析——緒論例9要使的近似值的相對(duì)誤差限小于0.1%要取幾位有效數(shù)字？設(shè)取n位有效數(shù)字,由定理1，由于知所以取只要取所以的近似值取4位有效數(shù)字，其相對(duì)誤差限小于0.1%。1.2.3

函數(shù)值的誤差估計(jì)一、一元函數(shù)的誤差估計(jì)設(shè)a、b分別為精確值x、y的近似值；δa

、δb分別為a、b的誤差限。

f(a)為f(x)的近似函數(shù)值。

數(shù)值分析——緒論二、二元函數(shù)的誤差估計(jì)f(a,b)為f(x,y)的近似函數(shù)值。

數(shù)值分析——緒論三、n元函數(shù)的誤差估計(jì)的近似函數(shù)值。于是由泰勒

數(shù)值分析——緒論為展開(kāi)得函數(shù)值的誤差為為的近似值，設(shè)試求面積

數(shù)值分析——緒論已知的絕對(duì)誤差限和相對(duì)誤差限。解：因?yàn)榈闹禐槠渲欣?0已測(cè)得某場(chǎng)地長(zhǎng)的值為寬四、簡(jiǎn)單算術(shù)運(yùn)算的誤差限和相對(duì)誤差限兩個(gè)數(shù)的加、減、乘、除算術(shù)運(yùn)算得到的誤差限和相對(duì)誤差限分別為：應(yīng)避免用高精度數(shù)據(jù)和低精度數(shù)據(jù)作混合運(yùn)算。作加減法時(shí)，盡量避免接近的兩個(gè)數(shù)相減?！咀ⅰ繑?shù)值分析——緒論作乘除法時(shí)計(jì)算結(jié)果的精度也不會(huì)比原始數(shù)據(jù)的高。1.3

誤差定性分析與避免誤差危害1.3.1算法的數(shù)值穩(wěn)定性用一個(gè)算法進(jìn)行計(jì)算，初始數(shù)據(jù)誤差（舍入誤差造成）在計(jì)算中傳播使計(jì)算結(jié)果誤差增長(zhǎng)很快，則稱該算法是數(shù)值不穩(wěn)定的，否則是數(shù)值穩(wěn)定的。計(jì)算積分得兩個(gè)遞推算法:算法2算法1例11數(shù)值分析——緒論利用MATLAB程序遞推計(jì)算，結(jié)果見(jiàn)表MATLAB計(jì)算程序：E0=0.09531;%初始值E(1)=1-10*E0;forn=2:8E(n)=1/n-10*E(n-1);%遞推計(jì)算endE%用quadl計(jì)算積分值E8E8=quadl('x.^8./(x+10)',0,1)兩算法計(jì)算值與精確值比較

(算法1)(算法2)(精確值)算法2是穩(wěn)定的算法1是不穩(wěn)定的數(shù)值分析——緒論【定義4】對(duì)于某個(gè)算法，若輸入數(shù)據(jù)的誤差在計(jì)算過(guò)程中迅速增長(zhǎng)而得不到控制，則稱該算法是數(shù)值不穩(wěn)定的，否則是數(shù)值穩(wěn)定的。算法1誤差分析數(shù)值不穩(wěn)定

算法2誤差分析數(shù)值穩(wěn)定數(shù)值分析——緒論1.3.2病態(tài)數(shù)學(xué)問(wèn)題與條件數(shù)條件數(shù)C衡量問(wèn)題的病態(tài)程度：數(shù)值穩(wěn)定性是對(duì)算法而言的。病態(tài)是數(shù)學(xué)問(wèn)題即數(shù)學(xué)模型本身的性質(zhì),與算法無(wú)關(guān)。病態(tài)數(shù)學(xué)問(wèn)題：對(duì)一個(gè)數(shù)值問(wèn)題本身，當(dāng)輸入數(shù)據(jù)有微小擾動(dòng)（即誤差）時(shí)，引起輸出數(shù)據(jù)（即問(wèn)題解）的相對(duì)誤差很大，這就是病態(tài)問(wèn)題。相反的問(wèn)題為良態(tài)數(shù)學(xué)問(wèn)題。C越大病態(tài)可能越嚴(yán)重。數(shù)值分析——緒論計(jì)算函數(shù)值y=f(x)時(shí)，若例如有擾動(dòng)相對(duì)誤差的比值

稱為計(jì)算函數(shù)值問(wèn)題的條件數(shù)。其相對(duì)誤差為函數(shù)值y=f(a)的相對(duì)誤差為y=f(x)的條件數(shù)定義為：即例12取對(duì)數(shù)函數(shù)

x越接近1條件數(shù)越大，求對(duì)數(shù)函數(shù)值的相對(duì)誤差越大。自變量的相對(duì)誤差一般不會(huì)太大，如果條件數(shù)很大，將引起函數(shù)值相對(duì)誤差很大，出現(xiàn)這種情況的問(wèn)題就是病態(tài)問(wèn)題。則例13如

有這問(wèn)題可以認(rèn)為是病態(tài)的。一般情況它表示相對(duì)誤差可能放大n倍。自變量的相對(duì)誤差函數(shù)值的相對(duì)誤差就認(rèn)為是病態(tài)的。條件數(shù)越大病態(tài)越嚴(yán)重。1.3.3避免誤差危害的若干原則一、避免兩相近的數(shù)相減例14計(jì)算只有一位有效數(shù)字利用三角恒等式具有三位有效數(shù)字如果無(wú)法改變算式，則采用增加有效位數(shù)進(jìn)行運(yùn)算。在計(jì)算機(jī)上則采用雙倍字長(zhǎng)的高精度運(yùn)算。二、注意簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)數(shù)值分析——緒論計(jì)算多項(xiàng)式例15(1)若直接計(jì)算akxk再逐項(xiàng)相加(2)秦九韶算法乘法：n次用克萊姆（Cramer）法則求解線性方程組Ax=b例16當(dāng)n=20時(shí)總計(jì)算量≈21×19×20！約307816年

天啊，30多萬(wàn)年的時(shí)間?。僭O(shè)計(jì)算機(jī)每秒可做1億次乘除法運(yùn)算）乘法：加法：n數(shù)值分析——緒論【注】算法復(fù)雜度包括空間的復(fù)雜度和時(shí)間復(fù)雜度。高斯消元法：2千多次乘除運(yùn)算加法：n次的值。三、要避免用絕對(duì)值很小的數(shù)做除數(shù)數(shù)值分析——緒論用絕對(duì)值很小的數(shù)做除數(shù)，舍入誤差會(huì)增大，甚至?xí)谟?jì)算機(jī)中造成“溢出”錯(cuò)誤。如計(jì)算分母的絕對(duì)值很小，此算法是數(shù)值不穩(wěn)定的。四、兩數(shù)相加要防止大數(shù)“吃”掉小數(shù)12346+0.6+0.6-12345數(shù)值分析——緒論=0.12346×105-0.12345×105=1=0.12346×105+0.000006×105+0.000006×105-0.12345×105求多項(xiàng)式值的秦九韶算法

輸入

x；a0，a1，…，an

S←a0；u←1k

從

1到n循環(huán)u←x×uS←S+ak×u輸出數(shù)據(jù)S

；結(jié)束輸入

x；a0，a1，…，an

S←ank

從

n

到1

循環(huán)S←ak－1+x×S輸出數(shù)據(jù)S

；結(jié)束秦九韶算法P(x