數(shù)值算法2014.8主要內(nèi)容插值和擬合方程f(x)=0求根神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火、模糊控制算法選用算法應(yīng)遵循的原則1.盡量簡化計(jì)算步驟，減少乘除運(yùn)算的次數(shù).

例如，計(jì)算多項(xiàng)式通常運(yùn)算的乘法次數(shù)為若采用遞推算法,

則乘法次數(shù)僅為n.又如2.防止大數(shù)“吃掉”小數(shù)當(dāng)|a|>>|b|時，盡量避免a+b。例如，假設(shè)計(jì)算機(jī)只能存放10位尾數(shù)的十進(jìn)制數(shù)，則3.盡量避免相近數(shù)相減例如，當(dāng)x很大時，應(yīng)

，

當(dāng)x接近于0時，應(yīng)4.避免絕對值很小的數(shù)做分母當(dāng)|b|<<|a|時，應(yīng)盡量避免。5.選用數(shù)值穩(wěn)定性好的算法，以控制舍入誤差高速增長例如若（誤差）則計(jì)算

時誤差擴(kuò)大了倍,而

（n=1,2,…）

是穩(wěn)定的。

構(gòu)造一個(相對簡單的)函數(shù)通過全部節(jié)點(diǎn),即再用計(jì)算插值，即插值擬合算法一維插值的定義已知n+1個節(jié)點(diǎn)其中互不相同，不妨設(shè)求任一插值點(diǎn)處的插值節(jié)點(diǎn)可視為由產(chǎn)生,g(x)表達(dá)式復(fù)雜,或無封閉形或未知。

稱為拉格朗日插值基函數(shù)。

已知函數(shù)f(x)在n+1個點(diǎn)x0,x1,…,xn處的函數(shù)值為y0,y1,…,yn

。求一n次多項(xiàng)式函數(shù)Pn(x)，使其滿足：

Pn(xi)=yi,i=0,1,…,n.

解決此問題的拉格朗日插值多項(xiàng)式公式如下其中Li(x)為n次多項(xiàng)式：拉格朗日(Lagrange)插值例：選取n+1個不同插值節(jié)點(diǎn)，其中n為插值多項(xiàng)式的次數(shù)，當(dāng)n分別取2,4,6,8,10時，繪出下列函數(shù)拉格朗日插值插值多項(xiàng)式圖形.

分段線性插值計(jì)算量與n無關(guān);n越大，誤差越小.xjxj-1xj+1x0xnxoy比分段線性插值更光滑。xyxi-1xiab

在數(shù)學(xué)上，光滑程度的定量描述是：函數(shù)(曲線)的k階導(dǎo)數(shù)存在且連續(xù)，則稱該曲線具有k階光滑性。光滑性的階次越高，則越光滑。是否存在較低次的分段多項(xiàng)式達(dá)到較高階光滑性的方法？三次樣條插值就是一個很好的例子。三次樣條插值

三次樣條插值g(x)為被插值函數(shù)。二維插值的定義xyO第一種（網(wǎng)格節(jié)點(diǎn)）：例：樣條插值的應(yīng)用

用三次樣條插值描繪如圖所示圖形的上部輪廓線。

已知mn個節(jié)點(diǎn)其中互不相同，不妨設(shè)

構(gòu)造一個二元函數(shù)通過全部已知節(jié)點(diǎn),即再用計(jì)算插值，即第二種（散亂節(jié)點(diǎn)）：yx0已知n個節(jié)點(diǎn)其中互不相同，

構(gòu)造一個二元函數(shù)通過全部已知節(jié)點(diǎn),即再用計(jì)算插值，即

注意：最鄰近插值一般不連續(xù)。具有連續(xù)性的最簡單的插值是分片線性插值。最鄰近插值xy(x1,y1)(x1,y2)(x2,y1)(x2,y2)O

二維或高維情形的最鄰近插值，與被插值點(diǎn)最鄰近的節(jié)點(diǎn)的函數(shù)值即為所求。

將四個插值點(diǎn)（矩形的四個頂點(diǎn)）處的函數(shù)值依次簡記為：

分片線性插值xy(xi,yj)(xi,yj+1)(xi+1,yj)(xi+1,yj+1)Of(xi,yj)=f1，f(xi+1,yj)=f2，f(xi+1,yj+1)=f3，f(xi,yj+1)=f4插值函數(shù)為：第二片(上三角形區(qū)域)：(x,y)滿足插值函數(shù)為：注意：(x,y)當(dāng)然應(yīng)該是在插值節(jié)點(diǎn)所形成的矩形區(qū)域內(nèi)。顯然，分片線性插值函數(shù)是連續(xù)的；分兩片的函數(shù)表達(dá)式如下：第一片(下三角形區(qū)域)：(x,y)滿足

雙線性插值是一片一片的空間二次曲面構(gòu)成。雙線性插值函數(shù)的形式如下：其中有四個待定系數(shù)，利用該函數(shù)在矩形的四個頂點(diǎn)（插值節(jié)點(diǎn)）的函數(shù)值，得到四個代數(shù)方程，正好確定四個系數(shù)。雙線性插值xy(x1,y1)(x1,y2)(x2,y1)(x2,y2)O擬合與插值的關(guān)系

函數(shù)插值與曲線擬合都是要根據(jù)一組數(shù)據(jù)構(gòu)造一個函數(shù)作為近似，由于近似的要求不同，二者的數(shù)學(xué)方法上是完全不同的。問題：給定一批數(shù)據(jù)點(diǎn)，需確定滿足特定要求的曲線或曲面解決方案：若不要求曲線（面）通過所有數(shù)據(jù)點(diǎn)，而是要求它反映對象整體的變化趨勢，這就是數(shù)據(jù)擬合，又稱曲線擬合或曲面擬合。若要求所求曲線（面）通過所給所有數(shù)據(jù)點(diǎn)，就是插值問題；常用的是最小二乘擬合(略)最臨近插值、線性插值、樣條插值與曲線擬合結(jié)果：二、方程f(x)=0求根1.區(qū)間迭代法：二分法

2.迭代法

(1)將方程f(x)=0等價(jià)變形為x=(x)，建立迭代關(guān)系式：

xk+1=(xk)，k=0,1,2,…

若(x)連續(xù)，且迭代序列{xk}的極限存在，則該極限就是x*。

(2)局部收斂與全局收斂(3)收斂定理5．牛頓迭代法

(2).牛頓法的收斂性：平方收斂(3)牛頓迭代法的優(yōu)缺點(diǎn)：收斂速度快，需要求導(dǎo)數(shù)，局部收斂。(4)牛頓下山法:取適當(dāng)參數(shù)(0,1]，使成立k=0,1,2,…。

(1).牛頓迭代公式6．弦截法

(1)弦截法的公式k=0,1,2,…

(2)快速弦截法

k=0,1,2,…

(3)弦截法的收斂性例.快速求解空間任意螺旋線與任意平面的全部交點(diǎn)。

圓柱螺旋線的向量式：(x,y,z)T=(cos(t-t0),sin(t-t0),z)T

經(jīng)坐標(biāo)軸旋轉(zhuǎn)-平移得空間一般螺旋線方程平面的一般方程

ax+by+cz=d把螺旋線方程代入平面方程整理，用t/代替原來的t，cost、sint、t的系數(shù)分別為A、B、C常數(shù)項(xiàng)為D,得：Acost+Bsint+Ct+D=0

令：f(t)=Acost+Bsint+Ct+D問題歸為解非線性方程f(t)=0。

分析方程左邊函數(shù)f(t)，其具有如下的特點(diǎn)：

(1)f(t)極值的出現(xiàn)具有周期2(2)f(t)=0的大部分根在t軸上下方兩相鄰極值點(diǎn)之間，個別在極值點(diǎn)處。(3)令f

(t)=0，由得f(t)極值點(diǎn)位于

(4)若相鄰兩極值f(t1)f(t2)<0，則必有根t

(t1，t2)；過點(diǎn)A1(t1，f(t1))、A2(t2，f(t2))作直線A1A2，以A1A2與t軸的交點(diǎn)t0為初值，一般地可用牛頓法求解，特別地當(dāng)根t位于極值點(diǎn)附近時，牛頓法收斂速度太慢，可取區(qū)間[t1，t2]，用二分法求解。

(5)特殊情況

1.當(dāng)C=0時，f(t)是周期函數(shù)，振幅不超過，當(dāng)時，f(t)=0無解。當(dāng)時，其解周期性出現(xiàn)f(t)=0有唯一解或無解。如果有解一定在彎曲點(diǎn)處。

算法描述輸入平面方程一般式，螺旋線方程一般參數(shù)式，用3個歐拉角和映像z軸到螺旋線中心軸的變換向量把輸入平面方程一般式，螺旋線方程參數(shù)式判斷方程是否奇異求極值點(diǎn)有解否？輸出無解標(biāo)志用二分法求唯一解求周期解解在極值附近否？用二分法求解用牛頓法求解是唯一解?yyyNNNN

二分法有根區(qū)間的確定牛頓法初值的確定：(牛頓法局部收斂，而且會出現(xiàn)加收斂)以連接相鄰兩個極值點(diǎn)的直線與t軸交點(diǎn)橫坐標(biāo)為初始點(diǎn)。數(shù)值積分和數(shù)值微分

1．黎曼和：

2．牛頓—柯特斯(Newton—Cotes)求積公式

將積分區(qū)間[a,b]等分n份,記,分點(diǎn)為,k=0,1,...,n,用拉格朗日插值多項(xiàng)式代替被積函數(shù)f(x)，得到n階Newton—Cotes公式3.常用的Newton—Cotes公式n=1時，得梯形公式:In=2時，得辛普森公式:I4復(fù)化求積公式隨著n的增加可減少積分誤差，但高階Newton—Cotes公式又會造成數(shù)值不穩(wěn)定，因而采用復(fù)化公式。將積分區(qū)間[a,b]等分n等份,在每個小區(qū)間[xk,xk+1]上使用低階Newton—Cotes公式,(k=0,1,...,n).1).復(fù)化梯形公式

在每個子區(qū)間上用梯形公式,將它們累加得復(fù)化梯形公式：2).復(fù)化辛浦生公式記xk+1/2是區(qū)間的中點(diǎn),在每個子區(qū)間上用辛浦生公式,并將它們累加得復(fù)化辛浦生公式：5.變步長梯形法(逐次分半梯形公式)以復(fù)化梯形公式為例n等分區(qū)間2n等分區(qū)間近似有：類似，復(fù)化Simpsom公式6.先看看事后誤差估計(jì)（不同的誤差表達(dá)式，事后誤差估計(jì)式是不同的）自適應(yīng)計(jì)算記為復(fù)化一次，2次的Simpson公式控制求7．自適應(yīng)步長法

函數(shù)變化有急有緩，為了照顧變化劇烈部分的誤差，需要加密格點(diǎn)。對于變化緩慢的部分，加密格點(diǎn)會造成計(jì)算的浪費(fèi)。以此我們介紹一種算法，可以自動在變化劇烈的地方加密格點(diǎn)計(jì)算，而變化緩慢的地方，則取稀疏的格點(diǎn)。是8．龍貝格(Romberg)算法

受事后誤差估計(jì)式啟發(fā)，用低階的公式線性組合后成為一個高階的公式。

Romberg

算法：<?<?<?………………

T1=)0(0T

T8=)3(0TT4=)2(0T

T2=)1(0T

S1=)0(1T

R1=)0(3T

S2=)1(1T

C1=)0(2T

C2=)1(2T

S4=)2(1T

直到|Tm(0)-Tm-1(0)|<ε或

二重積分的復(fù)化梯形公式

系數(shù)，在積分區(qū)域的四個角點(diǎn)為1/4，4個邊界為1/2，內(nèi)部節(jié)點(diǎn)為1定義：若積分的數(shù)值積分公式對于任意一個次數(shù)不高于m次的多項(xiàng)式都精確成立，而存在一個m+1次多項(xiàng)式使之不精確成立，則稱該數(shù)值積分公式的代數(shù)精確度為m。

9．積分公式的代數(shù)精確度

引理:n階Newton—Cotes公式的代數(shù)精確度至少是n。

當(dāng)n為奇數(shù)時，n階Newton—Cotes公式的代數(shù)精確度為n；當(dāng)n為偶數(shù)時，n階Newton—Cotes公式的代數(shù)精確度是n+1

10．高斯型求積公式

適當(dāng)選取其中2n+2個參數(shù)Ak,xk(k=0,1,…,n),使得數(shù)值積分公式的代數(shù)精確度達(dá)到2n+1,這類求積公式稱為高斯型求積公式。

對于求積公式:(2)求出pn(x)的n個零點(diǎn)x1,x2,…xn即為Gsuss點(diǎn).

(1)求出區(qū)間[a,b]上權(quán)函數(shù)為W(x)的正交多項(xiàng)式pn(x).(3)計(jì)算積分系數(shù)

Gauss型求積公式的構(gòu)造方法(3)復(fù)化高斯求積公式(4)高精度Lobatto數(shù)值積分Lobatto積分公式是高斯型求積公式的修正，始終將上下端點(diǎn)作為節(jié)點(diǎn)，n+1階Lobatto積分公式的代數(shù)精度達(dá)到2n+1

(1)Gauss-Laguerre求積公式(2)Gauss-Hermite求積公式

將積分區(qū)間[a,b]分成n等分，在每個子區(qū)間上用兩點(diǎn)高斯求積公式，再把他們累加得區(qū)間[a,b]上復(fù)化Gauss-Legendre求積公式。

11.利用樣條函數(shù)計(jì)算列表函數(shù)的數(shù)值積分：先構(gòu)造樣條函數(shù)，然后再求積分。

1、插值型求導(dǎo)公式已知f(x)在n+1個點(diǎn)上的函數(shù)值，構(gòu)造插值多項(xiàng)式Pn(x)近似代替原函數(shù)f(x)，利用P’n(x)來代替f’(x)。這就稱為插值型求導(dǎo)公式

常微分方程的數(shù)值解法考慮一階常微分方程初值問題:

常微分方程的數(shù)值解：設(shè)微分方程的解y(x)的存在區(qū)間是[a,b]，在[a,b]內(nèi)取一系列節(jié)點(diǎn)a=x0<x1<…<xn=b,其中hk=xk+1-xk

；(一般采用:h=(b-a)/n)。在每個節(jié)點(diǎn)xk求解函數(shù)y(x)的近似值:yk≈y(xk)，這樣y0,y1,...,yn稱為微分方程的數(shù)值解。用數(shù)值方法，求得f(xk)的近似值yk，再用插值或擬合方法就求得y(x)的近似函數(shù)。(二)、主要算法1.顯式歐拉格式：k=1,2,n-1.

隱式歐拉格式：2.兩步歐拉格式：k=1,2,n-1.3.梯形方法:；3.改進(jìn)的歐拉方法：預(yù)測值:

校正值:

2．局部截?cái)嗾`差局部截?cái)嗾`差：當(dāng)y(xk)是精確解時，由y(xk)按照數(shù)值方法計(jì)算出來的的誤差y(xk+1)-稱為局部截?cái)嗾`差。注意：yk+1和的區(qū)別。因而局部截?cái)嗾`差與誤差ek+1=y(xk+1)-yk+1不同。如果局部截?cái)嗾`差是O(hp+1),我們就說該數(shù)值方法具有p階精度。

5、龍格-庫塔法龍格-庫塔法的思想：選取[xk,xk+1]上若干個點(diǎn)的導(dǎo)數(shù)，將它們作線性組合作為平均斜率，使數(shù)值方法達(dá)到預(yù)期的階。

1).二階龍格-庫塔法：當(dāng):時，得一簇龍格-庫塔公式，其局部截?cái)嗾`差均為O(h3)都是二階精度。特別取

就是改進(jìn)歐拉公式。2)、經(jīng)典四階龍格－庫塔格式(也稱為標(biāo)準(zhǔn)龍格－庫塔方法)：

四階龍格－庫塔方法的截?cái)嗾`差為O(h5)，具有四階精度。一般一階常微分方程初值問題用四階龍格－庫塔方法計(jì)算，其精度均滿足實(shí)際問題精度要求。

3).變步長龍格－庫塔方法：從節(jié)點(diǎn)xk出發(fā)，以步長h據(jù)四階龍格－庫塔方法求出一個近似值,然后以步長h/2求出一個近似值，若

>,繼續(xù)將步長折半，若

,將步長加倍，直到>，這時再步長折半一次，即得結(jié)果()。

4).RKF格式：變步長龍格－庫塔方法，因頻繁加倍或折半步長會浪費(fèi)計(jì)算量。Felhberg改進(jìn)了傳統(tǒng)龍格－庫塔方法，得到RKF格式，較好解決了步長的確定，而且提高了精度與穩(wěn)定性，為Matlab等許多數(shù)值計(jì)算軟件采用。4/5階RKF格式：由4階龍格－庫塔方法與5階龍格－庫塔方法結(jié)合而成。

6.亞當(dāng)斯方法(Adams):使用前面已算出的數(shù)值解一邊減少計(jì)算量。（記：；）1).顯式Adams方法：二階顯式Adams方法：;

三階顯式Adams方法：;

四階顯式Adams方法：.2).隱式Adams方法二階隱式Adams方法：;

三階隱式Adams方法：;

四階隱式Adams方法：

3）.Adams預(yù)報(bào)-校正系統(tǒng)：先用顯式格