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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x0

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

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

作為x*

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

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

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

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

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

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

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

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

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

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

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

1.4數(shù)值運算誤差分析函數(shù)運算誤差算術(shù)運算誤差1.4數(shù)值運算誤差分析函數(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=

故：

相對誤差：和差積商的誤差估計：δ(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)是在某個x附近連續(xù)可微的實函數(shù)，也稱為是一個數(shù)學(xué)問題，記

稱cond(f,x)為數(shù)學(xué)問題y=f(t)在t=x處的條件數(shù)，也可簡稱為數(shù)學(xué)問題y=f(x)的條件數(shù)。注釋在表示一個數(shù)學(xué)問題的條件數(shù)時，有時候需要明確指出f的自變量x，以及f(x)在x=x0處的條件數(shù)，這時，也可以把條件數(shù)更具體地表示為)()('),cond(xfxfxxf=)()(']),(cond[0000xfxfxxxf=計算數(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：如果一個數(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)是通過一個中間變量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)定性和減小運算誤差在計算過程中誤差不會擴大或?qū)τ嬎憬Y(jié)果的精度要求影響不大。減小運算誤差:1要避免兩相近數(shù)相減。2要防止大數(shù)吃掉小數(shù)。3要避免除數(shù)絕對值遠(yuǎn)小于被除數(shù)絕對值。4注意簡化計算步驟，減少運算次數(shù)。例：計算積分寫成遞推公式誤差傳遞規(guī)律公式改為

則誤差按規(guī)律

逐漸縮小

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

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

x2+bx+c=0

，其中-b,c2要防止大數(shù)“吃掉”小數(shù)，注意保護(hù)重要物理參數(shù)。在8位十進(jìn)制計算機上計算。要規(guī)格化和對階。結(jié)果，大數(shù)“吃掉”小數(shù)。類似地改變計算方法一元二次方程根的表示方法假如一元二次方程有絕對值不同的兩個實根，記sign(b)表示取b符號，記x1為絕對值較小的那一個實根，也就是分子是同號兩數(shù)相減的那一個；x2為絕對值較大的那一個實根，從而有對于求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)制計算機上計算在5位十進(jìn)制計算機上計算。要規(guī)格化和對階。結(jié)果，大數(shù)“吃掉”小數(shù)。改變計算方法，按絕對值由小到大相加。3注意簡化計算步驟，減少運算次數(shù)，避免誤差積累例：計算的值。又如只需14次乘法。多項式的值計算方法對于一般形式的多項式

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

A=(a0,a1,…,an)

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