第1章數(shù)值計(jì)算引論

數(shù)值計(jì)算方法第1章數(shù)值計(jì)算引論第2章非線性方程的數(shù)值解法第3章線性代數(shù)方程組的數(shù)值解法第4章插值法第5章曲線擬合的最小二乘法第6章數(shù)值積分和數(shù)值微分第7章常微分方程初值問題的數(shù)值解法數(shù)值計(jì)算方法

第1章數(shù)值計(jì)算引論1.1數(shù)值計(jì)算方法1.2誤差的來源1.3近似數(shù)的誤差表示法1.4數(shù)值運(yùn)算誤差分析1.5數(shù)值穩(wěn)定性和減小運(yùn)算誤差

第1章數(shù)值計(jì)算引論

數(shù)值計(jì)算方法與誤差分析理工科大學(xué)本科生————科學(xué)研究?，F(xiàn)代科學(xué)研究的三大手段————

理論分析、科學(xué)實(shí)驗(yàn)、科學(xué)計(jì)算。1.1數(shù)值計(jì)算方法1.1.1數(shù)值計(jì)算方法及其主要內(nèi)容

1.課程名稱：科學(xué)與工程數(shù)值計(jì)算方法簡稱：科學(xué)計(jì)算、科學(xué)與工程計(jì)算、數(shù)值分析、計(jì)算方法、數(shù)值計(jì)算方法。科學(xué)與工程：從實(shí)用的角度，將科學(xué)研究與工程技術(shù)上遇到的實(shí)際問題用數(shù)學(xué)模型來描述，以便進(jìn)行定量的分析、研究。

數(shù)值：數(shù)、數(shù)字，由0-9十個(gè)數(shù)字、小數(shù)點(diǎn)和正負(fù)號(hào)等組成的數(shù)。計(jì)算方法：解題的方法?？梢杂米匀徽Z言、數(shù)學(xué)語言或約定的符號(hào)語言來描述。計(jì)算：只能包括計(jì)算機(jī)能夠直接處理的運(yùn)算,即加減乘除等基本運(yùn)算。數(shù)值計(jì)算：相對于非數(shù)值計(jì)算，如查表、排序等。用（0-9十個(gè)數(shù)字、小數(shù)點(diǎn)、正負(fù)號(hào)等組成的）數(shù)，通過計(jì)算機(jī)進(jìn)行加減乘除等基本運(yùn)算。

2。數(shù)值算法：對科學(xué)研究與工程技術(shù)上遇到的實(shí)際數(shù)學(xué)問題的解法歸結(jié)為用數(shù)值進(jìn)行加減乘除等基本運(yùn)算，并有確定運(yùn)算順序，完整而準(zhǔn)確的描述稱為數(shù)值算法。

數(shù)值計(jì)算方法是研究用數(shù)字計(jì)算機(jī)解決數(shù)學(xué)問題的數(shù)值算法及其理論的一門課程。3.主要內(nèi)容：工程上遇到的數(shù)學(xué)問題

數(shù)值計(jì)算的誤差分析非線性方程線性方程組插值法最小二乘法數(shù)值積分和數(shù)值微分常微分方程1.1.2用計(jì)算機(jī)解題的步驟當(dāng)給定一個(gè)科學(xué)研究與工程技術(shù)上遇到的實(shí)際問題時(shí)，首先根據(jù)專業(yè)知識(shí)建立實(shí)際問題的數(shù)學(xué)模型，即模型化（modeling)或建模。然后對數(shù)學(xué)模型進(jìn)行求解。數(shù)學(xué)模型（包括公式、表格、圖形等）求解有兩條途徑：求解析解和數(shù)值解。

求解析解，解以表達(dá)式表示，這是準(zhǔn)確解。求數(shù)值解，解是以一些離散點(diǎn)上取值的形式表示，多數(shù)情況下，數(shù)值解是近似的，求數(shù)值解要用計(jì)算機(jī)。求數(shù)學(xué)模型數(shù)值解的方法稱為數(shù)值計(jì)算方法。選擇計(jì)算方法以后進(jìn)行程序設(shè)計(jì)，即用程序語言把算法編成程序，然后上機(jī)得出數(shù)值解。實(shí)際問題-----數(shù)學(xué)問題(建模)---構(gòu)造數(shù)值計(jì)算方法---

程序設(shè)計(jì)---上機(jī)計(jì)算---數(shù)值解---結(jié)果分析數(shù)值計(jì)算的基本方法(補(bǔ))離散化插值法迭代法逼近法1離散化方法設(shè)f(x)是定義在[a,b]上的連續(xù)函數(shù)，當(dāng)它們的表達(dá)式很復(fù)雜，甚至寫不出來時(shí)，我們可以選擇若干個(gè)離散點(diǎn)

x0,x1,…,xn∈[a,b]

求出f(x)在這些點(diǎn)處的函數(shù)值或函數(shù)值的近似值

fi=f(xi)i=0,1,…,n,

從而得到一個(gè)如下的函數(shù)值列表：xx0x1…xnyf(x0)f(x1)…f(xn) 2插值方法對于任意給出的某個(gè)函數(shù)y=f(x)的函數(shù)值列表:

我們可以構(gòu)造一個(gè)簡單函數(shù)，比如n次多項(xiàng)式pn(x)，滿足條件

pn(xi)=yi,i=0,1,…,n

并利用pn(x)近似表示f(x)。提示：由于pn(x)是一個(gè)多項(xiàng)式函數(shù)，用它在某一點(diǎn)處的函數(shù)值、導(dǎo)數(shù)值、區(qū)間上的定積分等來近似未知函數(shù)y=f(x)的值、微分、定積分xx0x1…xnyy0y1…yn3函數(shù)逼近設(shè)f(x)是滿足某種特定條件的函數(shù)，表達(dá)式比較復(fù)雜甚至寫不出來，但是我們可以把它表示為一個(gè)簡單函數(shù)系列{fn(x),n=1,2,…}的極限,即

limfn(x)=f(x)(n∞)

這樣我們就可以根據(jù)不同的精度要求選取適當(dāng)大的正數(shù)N,利用fN(x)近似替代f(x)。提示：如果f(x)可以展為泰勒級(jí)數(shù)，那么我們可以取fn(x)為f(x)的泰勒展式前n+1項(xiàng)。4迭代的方法如要計(jì)算某個(gè)真值

x*，可構(gòu)造一個(gè)序列{xn,n=0,1,2,…}，該序列滿足：

x0

已知；有一個(gè)簡單函數(shù)φ(t)，且xn+1=φ(xn)，n=0,1,2,…limxn=x*(n→∞)

則，可反復(fù)利用xn+1=φ(xn)，經(jīng)過N次迭代后，用xn+1

作為x*

的近似值。實(shí)例：求5的平方根的迭代格式初值x0=2，xn+1=2+1/(xn+2)簡單迭代法初值x0=2，xn+1=（xn+1/xn)/2牛頓迭代法請大家練習(xí)用兩種迭代法求解的結(jié)果1.1.3算法及算法的評價(jià)算法：為解決某一特定問題或完成某個(gè)特定任務(wù)而設(shè)計(jì)或規(guī)定的一個(gè)有限步的操作指令序列稱為算法。提示：算法具有如下一些特征：輸入：有0個(gè)或多個(gè)輸入輸出：有一個(gè)或多個(gè)輸出(處理結(jié)果)確定性：每步定義都是確切、無歧義的有窮性：算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性：每一步操作均可由有限次最基本的運(yùn)算來完成。算法的描述：自然語言：流程圖：偽代碼：算法的評價(jià)：程序的可讀性好；節(jié)省計(jì)算時(shí)間節(jié)省存儲(chǔ)空間數(shù)值穩(wěn)定性與收斂性

關(guān)于算法的評價(jià)

既然研究典型的數(shù)學(xué)問題的計(jì)算方法、或者說數(shù)值解方法最后都要用“算法”來描述，所以對具體的計(jì)算方法的評價(jià)也就轉(zhuǎn)化為對算法的評價(jià)。一個(gè)算法的好壞可用下面幾個(gè)指標(biāo)來刻劃程序的可讀性好；節(jié)省計(jì)算時(shí)間節(jié)省存儲(chǔ)空間數(shù)字穩(wěn)定性好收斂速率的描述在一個(gè)迭代過程中，如果我們有

其中c為非零常數(shù)，則稱{xn}p階收斂于x*。術(shù)語：當(dāng)p=1時(shí)，稱算法具有線性速率收斂；當(dāng)1<p<2時(shí)，稱算法具有超線性收斂速率；當(dāng)p=2時(shí)，稱算法具有二次終結(jié)性質(zhì)或二次收斂速率。1.1.4程序的基本結(jié)構(gòu)本書程序的基本結(jié)構(gòu)采用模塊化程序設(shè)計(jì)思想主要分四大模塊FormProblem()：主要完成程序的參數(shù)（常量）設(shè)置Operation()：完成算法的基本操作ShowTable()：完成計(jì)算結(jié)果（含中間結(jié)果）的屏幕輸出SaveTable()：計(jì)算結(jié)果的保存（寫文件）誤差的來源即產(chǎn)生誤差的原因。主要有四種：1.模型誤差---建立的數(shù)學(xué)模型和實(shí)際的距離，客觀量的準(zhǔn)確值與數(shù)學(xué)模型的準(zhǔn)確解的差。例如自由落體運(yùn)動(dòng)方程1-2誤差的來源2.觀測誤差：數(shù)學(xué)模型當(dāng)中的參數(shù)或常數(shù)常常是是觀測或?qū)嶒?yàn)來的，這樣必然有誤差，稱為觀測誤差或測量誤差，由觀測數(shù)據(jù)而產(chǎn)生的誤差。例如自由落體運(yùn)動(dòng)方程3.截?cái)嗾`差(方法誤差)---數(shù)學(xué)模型的準(zhǔn)確解與利用數(shù)值計(jì)算方法得到的準(zhǔn)確解之差。無窮過程用有窮項(xiàng)代替例如:無窮級(jí)數(shù)取前n項(xiàng)代替截?cái)嗾`差用有限的過程代替無限的過程，和用簡單的計(jì)算問題代替復(fù)雜的計(jì)算問題所產(chǎn)生的誤差。4.舍入誤差：計(jì)算工具字長是有限位，在計(jì)算時(shí)只能對有限位數(shù)字進(jìn)行運(yùn)算，超過這個(gè)位數(shù)時(shí)，要舍入，于是產(chǎn)生舍入誤差。原始數(shù)據(jù)、中間步驟和最終結(jié)果都可能產(chǎn)生舍入誤差。如圓周率3.14159265……

一般實(shí)數(shù)不能精確存儲(chǔ)，例如：在10位十進(jìn)制數(shù)限制下：1-3近似數(shù)的誤差表示1.3.2相對誤差1.3.3有效數(shù)字：由絕對誤差決定。

若近似值x*的絕對誤差(限)是某位的半個(gè)單位，則說x*精確到該位，若從該位到x*的左面第一位非零數(shù)字一共有n位，則稱近似值x*有n位有效數(shù)字。

1.用四舍五入得到的近似數(shù)的誤差限是末位的半個(gè)單位。近似數(shù)的誤差限是末位的半個(gè)單位，則有n位有效數(shù)字。因此用四舍五入得到的近似數(shù)是有效數(shù)字。

2.在公式運(yùn)算中，要先區(qū)分準(zhǔn)確量和近似數(shù)。準(zhǔn)確數(shù)有無窮多位有效數(shù)字.3.有效數(shù)字位與小數(shù)點(diǎn)后有多少位數(shù)無直接關(guān)系。1.3.4有效數(shù)字與相對誤差1.定理給出的是一個(gè)充分條件，而不是必要條件。定理的逆命題不成立。

2.在實(shí)際應(yīng)用時(shí)，為了要使所取近似數(shù)的相對誤差滿足一定要求，可以用定理，確定所取近似數(shù)應(yīng)具有有效數(shù)字的位數(shù)。

1.定理給出的是一個(gè)充分條件，而不是必要條件。定理的逆命題不成立。即若近似數(shù)有n位有效數(shù)字，相對誤差不一定滿足定理。

2.在實(shí)際應(yīng)用時(shí)，為了要使所取近似數(shù)具有n位有效數(shù)字，要求所取近似數(shù)的相對誤差滿足定理的要求。

1.4數(shù)值運(yùn)算誤差分析函數(shù)運(yùn)算誤差算術(shù)運(yùn)算誤差1.4數(shù)值運(yùn)算誤差分析函數(shù)y=f(x1,x2)的全微分為：

若x1,x2的準(zhǔn)確值為x1*,x2*,則y的準(zhǔn)確值為y*=f(x1*,x2*)

又的dx1≈x1*-x1=dx2≈x2*-x2=dy≈y*-y=

故：

相對誤差：和差積商的誤差估計(jì)：δ(x1±x2)=δ(x1)±δ

(x2)δ(x1x2)=x2δ(x1)+x1δ(x2)δ(x1/x2)=δ(x1)/x2-δ(x2)x1/x22η(x1±x2)=(x1/(x1±x2）)η(x1)±(x2/(x1±x2）)η(x2)η(x1x2)=η(x1)+η(x2)η(x1/x2)=η(x1)-η(x2)利用條件數(shù)估算誤差定義：設(shè)y=f(t)是在某個(gè)x附近連續(xù)可微的實(shí)函數(shù)，也稱為是一個(gè)數(shù)學(xué)問題，記

稱cond(f,x)為數(shù)學(xué)問題y=f(t)在t=x處的條件數(shù)，也可簡稱為數(shù)學(xué)問題y=f(x)的條件數(shù)。注釋在表示一個(gè)數(shù)學(xué)問題的條件數(shù)時(shí)，有時(shí)候需要明確指出f的自變量x，以及f(x)在x=x0處的條件數(shù)，這時(shí)，也可以把條件數(shù)更具體地表示為)()('),cond(xfxfxxf=)()(']),(cond[0000xfxfxxxf=計(jì)算數(shù)學(xué)問題的條件數(shù)舉例例：試求tan(x)在x=π/6處的條件數(shù)。分析：記δ(x0)、η(x0)和δ[f(x0)]、η[f(x0)]分別為x0和f(x0)的絕對誤差和相對誤差，則有

η(x0)=δ(x0)/x0η[f(x0)]=δ[f(x0)]/f(x0)

利用δ[f(x0)]=f’(x0)δ(x0),即得

結(jié)論1：η[f(x0)]=cond[f(x),x0]η(x0)結(jié)論2：如果一個(gè)數(shù)學(xué)問題y=f(x)的條件數(shù)的絕對值|cond[f(x),x0]|<1，那么有|η[f(x)]|<|η(x)|，這表明相對誤差有縮小的趨勢；若|cond[f(x)]|>>1，則數(shù)學(xué)問題是不穩(wěn)定的，或者說是病態(tài)的，輸入值的微小誤差可以導(dǎo)致輸出值的較大的誤差復(fù)合函數(shù)的條件數(shù)：假設(shè)函數(shù)關(guān)系y=f(x)是通過一個(gè)中間變量u復(fù)合而成的，即y=y(u)，u=u(x)。利用復(fù)合函數(shù)的求導(dǎo)規(guī)則

我們有亦即：cond[y(u(x)),x0]=cond[y(u),u0]cond[u(x),x0]

1.5數(shù)值穩(wěn)定性和減小運(yùn)算誤差在計(jì)算過程中誤差不會(huì)擴(kuò)大或?qū)τ?jì)算結(jié)果的精度要求影響不大。減小運(yùn)算誤差:1要避免兩相近數(shù)相減。2要防止大數(shù)吃掉小數(shù)。3要避免除數(shù)絕對值遠(yuǎn)小于被除數(shù)絕對值。4注意簡化計(jì)算步驟，減少運(yùn)算次數(shù)。例：計(jì)算積分寫成遞推公式誤差傳遞規(guī)律公式改為

則誤差按規(guī)律

逐漸縮小

1.5.1數(shù)值穩(wěn)定性:一個(gè)算法，如果計(jì)算結(jié)果受誤差的影響小，就稱這個(gè)算法具有較好的數(shù)值穩(wěn)定性。否則，就稱數(shù)值穩(wěn)定性不好。因此要設(shè)法控制誤差的傳播。1.5.2減小運(yùn)算誤差1.要避免相近兩數(shù)相減

13.5846-13.5839=0.00076位有效數(shù)字變成了1位有效數(shù)字。損失了有效數(shù)字的位數(shù)。當(dāng)x接近于0時(shí)，應(yīng)例解一元二次方程a

x2+bx+c=0

，其中-b,c2要防止大數(shù)“吃掉”小數(shù)，注意保護(hù)重要物理參數(shù)。在8位十進(jìn)制計(jì)算機(jī)上計(jì)算。要規(guī)格化和對階。結(jié)果，大數(shù)“吃掉”小數(shù)。類似地改變計(jì)算方法一元二次方程根的表示方法假如一元二次方程有絕對值不同的兩個(gè)實(shí)根，記sign(b)表示取b符號(hào)，記x1為絕對值較小的那一個(gè)實(shí)根，也就是分子是同號(hào)兩數(shù)相減的那一個(gè)；x2為絕對值較大的那一個(gè)實(shí)根，從而有對于求x1來說，可以把分子有理化，從而得到求一元二次方程根數(shù)值解的具體方法如果記那么x1，x2還可進(jìn)一步簡單地表示為x1=c/Quad(a,b,c)，x2=Quad(a,b,c)/a其中x1，x2分別為一元二次方程的絕對值較小，較大的根。求解Quad(a,b,c)的c語言函數(shù)可以說明為doubleQuad(doublea,doubleb,doublec)例在5位十進(jìn)制計(jì)算機(jī)上計(jì)算在5位十進(jìn)制計(jì)算機(jī)上計(jì)算。要規(guī)格化和對階。結(jié)果，大數(shù)“吃掉”小數(shù)。改變計(jì)算方法，按絕對值由小到大相加。3注意簡化計(jì)算步驟，減少運(yùn)算次數(shù)，避免誤差積累例：計(jì)算的值。又如只需14次乘法。多項(xiàng)式的值計(jì)算方法對于一般形式的多項(xiàng)式

A(x)=a0+a1x+…+anxn把它表示為：PolyValue(x,A,n)=a0+a1x+…+anxn其中A是(2.1)式給出的多項(xiàng)式A(x)的系數(shù)構(gòu)成的(行)向量，亦即：

A=(a0,a1,…,an)

程序設(shè)計(jì)時(shí)，可以把A說明為一個(gè)n+1維數(shù)組，此時(shí)約定A[0]存放a0，A[1]存放a1，…，A[n]存放an。函數(shù)聲明：doublePolyValue(doublex,double*A,intn)1逐項(xiàng)求和算法思想：按次數(shù)由低到高的順序逐項(xiàng)求和。用變量power存放x的各次冪，并利用xk=xxk-1來簡化計(jì)算。源程序：（見下頁）doublePolyValue(doublex,double*A,intn){ doublepo