第二章 插值法

1、第二章 插值方法/* Interpolation */2.1 引言Ø 函數(shù)逼近問題的引出：現(xiàn)實(shí)應(yīng)用中常用函數(shù)表示某種內(nèi)在規(guī)律的數(shù)量關(guān)系，但是情況往往是：1）在某個(gè)區(qū)間a,b存在，有時(shí)候是連續(xù)的，但是只能通過實(shí)驗(yàn)或觀測(cè)得到一系列點(diǎn)的函數(shù)值（得到函數(shù)表），而無法得到的表達(dá)式2）函數(shù)表達(dá)式已知，但計(jì)算復(fù)雜（如，等）使用不方便，通常也使用函數(shù)表。如：三角函數(shù)表，對(duì)數(shù)表，平方根表，立方根表等。問題：有時(shí)需要求不在函數(shù)表上的函數(shù)值怎么辦？解決方法：根據(jù)所給的的函數(shù)表，構(gòu)造一個(gè)簡(jiǎn)單的函數(shù)近似替代（存在誤差?。?，稱為函數(shù)逼近。稱為逼近函數(shù)，為被逼近函數(shù)。通常選擇一類比較簡(jiǎn)單的函數(shù)，如代數(shù)多項(xiàng)式或分段

2、代數(shù)多項(xiàng)式。函數(shù)逼近的方法有很多，例如Taylor級(jí)數(shù)，F(xiàn)ourier級(jí)數(shù)，有限元方法、邊界元方法，小波分析等，大學(xué)科叫逼近論。本課程討論連續(xù)函數(shù)的逼近，主要介紹插值法。Ø 插值 （interpolation）已知的函數(shù)表 xy求：使 插值問題稱為的插值函數(shù)；為被插值函數(shù)；為插值結(jié)點(diǎn)；為插值區(qū)間；求插值函數(shù)的方法稱為插值法。當(dāng)為多項(xiàng)式時(shí)，相應(yīng)的插值法為多項(xiàng)式插值；為分段的多項(xiàng)式，稱為分段插值；為三角多項(xiàng)式，稱為三角插值。插值法的幾何示意圖，P14圖2.1多項(xiàng)式插值是數(shù)值分析的基本工具，常用來計(jì)算被插函數(shù)的近似函數(shù)值，零、極點(diǎn)，導(dǎo)數(shù)、積分（第四章 數(shù)值積分和數(shù)值微分），解微分方程（第五

3、章）、積分方程等。2.2 拉格朗日插值2.2.1 插值多項(xiàng)式的存在唯一性問題：用不同的多項(xiàng)式插值方法得到的插值多項(xiàng)式的形式有可能不同，它們是否等價(jià)？（可以轉(zhuǎn)化為相同的標(biāo)準(zhǔn)式？）答案是肯定的！兩點(diǎn)確定一條直線（ 一次多項(xiàng)式 ）三點(diǎn)確定一個(gè)拋物線（ 二次多項(xiàng)式 ）是否n+1點(diǎn)確定一個(gè)n次多項(xiàng)式？ 給定n+1個(gè)互異的插值點(diǎn)，求符合插值條件的次數(shù)不超過n的插值多項(xiàng)式（標(biāo)準(zhǔn)式） 存在且唯一！證明見P14，定理2.1?？梢酝ㄟ^求解方程組得到系數(shù)，從而得到的表達(dá)式，但是這樣做不但計(jì)算復(fù)雜，且難以得到的簡(jiǎn)單表達(dá)式。當(dāng)n=20時(shí)，在108次/秒的計(jì)算機(jī)上計(jì)算需要幾十萬年！2.2.2 線性插值與拋物插值Ø

4、; 線性插值當(dāng)n=1時(shí)：已知 xk, xk+1；yk, y k+1， 求線性插值多項(xiàng)式 使得：且.可見，是過和的一條直線。 點(diǎn)斜式 兩點(diǎn)式令，則：稱及為一次插值基函數(shù)，或線性插值基函數(shù)。注意：基函數(shù) Ø 拋物線插值當(dāng)n=2時(shí)：已知xk-1，xk, xk+1；yk-1, yk, y k+1， 求二次插值多項(xiàng)式 使得：，?？梢?，是過，和的拋物線。利用基函數(shù)法構(gòu)造 i , j = k-1, k, k+1因此構(gòu)造此時(shí)：稱，及為二次插值基函數(shù)，或拋物插值基函數(shù)。2.2.3 拉格朗日插值多項(xiàng)式從n=1和n2的情形，可推廣到n>1的情形：只要構(gòu)造n次插值的基函數(shù)滿足： 注意：n1個(gè)節(jié)點(diǎn)然后令

5、n次插值多項(xiàng)式 顯然有成立。每個(gè)有n個(gè)根，分別為，因此第i個(gè)基函數(shù)可以寫成：又： ，故：因此：這n+1個(gè)n次多項(xiàng)式為節(jié)點(diǎn)上的n次插值基函數(shù)。n次插值多項(xiàng)式 稱為拉格朗日插值多項(xiàng)式。記：則：于是：?jiǎn)栴}：如圖2.1（P14），插值多項(xiàng)式在插值點(diǎn)上的誤差為0，但是在其他位置上的估計(jì)誤差是未知的。如何估計(jì)出在其他點(diǎn)上的誤差限？1） 如果是n次多項(xiàng)式，則和等價(jià)，誤差為0；2） 如果不是n次多項(xiàng)式，如何處理?為了解決第2）種情況，我們引入差值余項(xiàng)的概念，估計(jì)出插值多項(xiàng)式估計(jì)誤差的上界！2.2.4 插值余項(xiàng)（ Remainder ）在a,b上用近似，其截?cái)嗾`差，稱為插值多項(xiàng)式的余項(xiàng)或插值余項(xiàng)。定理2.2：關(guān)

6、于插值余項(xiàng)的估計(jì)（P18）證明：插值多項(xiàng)式在n+1個(gè)插值點(diǎn)上的誤差為0，因此至少有n+1個(gè)根，可以寫成 要求需求任意固定（估計(jì)x點(diǎn)的誤差），構(gòu)造變量為t的函數(shù) 此時(shí)，為與t無關(guān)的常量！有n+2個(gè)根，分別為，故在a,b上有n2個(gè)零點(diǎn)；由羅爾定理，在的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn)，故在a,b上有n1個(gè)零點(diǎn)；（注意：是對(duì)t求導(dǎo)）同理，在a,b上有n個(gè)零點(diǎn)，在a,b上有1個(gè)零點(diǎn)。中間步驟：（注意，對(duì)t求導(dǎo)?。閚次多項(xiàng)式，故而為0。因此，因此記做：于是：且依賴于x。故：余項(xiàng)表達(dá)式只有在的高階導(dǎo)數(shù)存在時(shí)才能應(yīng)用，又因?yàn)榈木唧w位置通常不可能給出，因此常計(jì)算逼近的截?cái)嗾`差限：， 其中 。注意：當(dāng)為任一個(gè)次數(shù)&

7、#163; n 的多項(xiàng)式時(shí)，, 可知。即n次插值多項(xiàng)式對(duì)于次數(shù)£ n 的多項(xiàng)式是精確的。附例1：給定 下面哪個(gè)是的圖像？Ø P19例2.12.3 逐次線性插值法則Ø 拉格朗日插值法的缺陷增加插值節(jié)點(diǎn)時(shí)，原來算出的數(shù)據(jù)均不能利用，必須重新計(jì)算。為克服這一缺陷，通常用逐次線性插值法求得高次插值。Ø 逐次線性插值是以為節(jié)點(diǎn)的1次拉格朗日插值公式，實(shí)際上是過點(diǎn)和的直線，采用點(diǎn)斜式：是以為節(jié)點(diǎn)的1次拉格朗日插值公式，同理有：令：容易證明：由插值公式的唯一性可知，是以為節(jié)點(diǎn)的2次拉格朗日插值多項(xiàng)式。發(fā)現(xiàn)：兩個(gè)一次多項(xiàng)式可以通過線性插值得到二次插值多項(xiàng)式。依此類推：

8、點(diǎn)斜式是以為節(jié)點(diǎn)的k次拉格朗日插值多項(xiàng)式。注：過點(diǎn)和的直線。實(shí)際上： 兩點(diǎn)式是對(duì)兩個(gè)低次插值的線性插值，這種通過低次插值再作線性插值生成高次插值的方法稱為逐次線性插值。Ø Aitken法利用公式： 遞推表2.1Ø Neville法驗(yàn)證 利用公式： 遞推表2.2每增加一個(gè)計(jì)算節(jié)點(diǎn)就計(jì)算一行，如果精度不滿足要求，再增加一個(gè)節(jié)點(diǎn)，前面的計(jì)算完全有效！問題：如何判斷精度是否滿足要求？增加多少個(gè)節(jié)點(diǎn)能夠停止計(jì)算？Ø 誤差估計(jì)由插值多項(xiàng)式存在的唯一性，仍有（P18 定理2.2），這里可采用一種更簡(jiǎn)便的方法。當(dāng)在插值區(qū)間變化不大時(shí)，設(shè)，則有：兩式相除:可轉(zhuǎn)化為： 因此：如果 則

9、可以認(rèn)為：滿足精度要求。Ø P21 例2.2注意：滿足精度要求時(shí)，算法停止2.4 差商(divided difference ,亦稱均差)與牛頓插值公式2.4.1 差商及其性質(zhì)Lagrange 插值雖然易算，但若要增加一個(gè)節(jié)點(diǎn)時(shí)，全部基函數(shù)都需重新算過。公式不具有繼承性，不利于編程?？梢詫⒏膶懗上旅娴男问剑合Ｍ吭黾右粋€(gè)節(jié)點(diǎn)時(shí)，只附加一項(xiàng)上去即可。為待定系數(shù)。P22：關(guān)于的遞推公式，用解方程的方法計(jì)算復(fù)雜！如何計(jì)算的值？我們先引入差商的概念Ø 差商(亦稱均差) /* divided difference */為函數(shù)關(guān)于的一階差商。一階差商的幾何意義：弦截線的斜率為函數(shù)關(guān)于的

10、二階差商。一般地，稱：為函數(shù)關(guān)于（k+1個(gè)點(diǎn)）的k階差商。Ø 差商的基本性質(zhì)ü 性質(zhì)1：差商的對(duì)稱性事實(shí)上： 其中： 這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明，這個(gè)性質(zhì)說明差商的值與節(jié)點(diǎn)的排列順序無關(guān)，稱為差商的對(duì)稱性。即：ü 性質(zhì)2：差商的另一種定義由性質(zhì)1和差商的定義可知（將和互換位置）ü 性質(zhì)3：差商與導(dǎo)數(shù)的關(guān)系在上存在n階導(dǎo)數(shù)，且節(jié)點(diǎn)，則n階差商與導(dǎo)數(shù)關(guān)系如下：這個(gè)公式可以直接用羅爾定理證明。類似2.2.4 插值余項(xiàng)，定理2.2，P18。ü 性質(zhì)4：線性 ( P43 習(xí)題15 ) 若： 那么： 提示：用數(shù)學(xué)歸納法證明ü 性質(zhì)4：把x看成上

11、的一個(gè)點(diǎn)，若是x的n次多項(xiàng)式，則一階差商是x的n1次多項(xiàng)式；二階差商是x的n2次多項(xiàng)式；一般地：n次多項(xiàng)式的k階差商是x的nk次多項(xiàng)式（），當(dāng)k>n時(shí)，k階差商為零。 由性質(zhì)3可以證明。Ø 差商的計(jì)算P23 表2.42.4.2 牛頓插值公式把x看成上的一個(gè)點(diǎn)，可得： 由差商的定義式反推得到把后一式代入前一式，就可以得到：其中：滿足插值條件，稱為牛頓插值多項(xiàng)式。對(duì)比2.4.1中的形式：各項(xiàng)的系數(shù) Ø P24 例2.3注意：四階差商近似常數(shù)，由性質(zhì)4（n次多項(xiàng)式的k階差商是x的nk次多項(xiàng)式），常數(shù)可以認(rèn)為是0次多項(xiàng)式，此時(shí)n=k，說明可以用4次多項(xiàng)式近似逼近，誤差較?。?

12、.5 差分與等距節(jié)點(diǎn)插值公式實(shí)際應(yīng)用中，經(jīng)常遇到等距離節(jié)點(diǎn)的情形（等間距采樣），這時(shí)插值公式可以進(jìn)一步簡(jiǎn)化，計(jì)算也簡(jiǎn)單得多。此時(shí)要研究等距節(jié)點(diǎn)的插值公式，首先從差分說起2.5.1差分及其性質(zhì)Ø 差分的定義已知：節(jié)點(diǎn)等距分布 ，這里h為常數(shù)，稱為步長(zhǎng)。稱：分別為在處以h為步長(zhǎng)的向前差分（forward difference），向后差分（backward difference）和中心差分（centered difference）。符號(hào)分別稱為向前差分算子，向后差分算子和中心差分算子。二階差分定義為：一般地，m階差分定義為： 注意：不是由和遞歸得到！因?yàn)榍笠浑A中心差分用到的和不是函數(shù)表上的

13、值，如果用函數(shù)表上的值則一階中心差分可寫成：，；因此，二階中心差分。不變算子I： 移位算子E： 注：；Ø 差分的性質(zhì)ü 性質(zhì)1：各階差分均可用函數(shù)值表示其中： ，即 ü 性質(zhì)2：可用各階差分表示函數(shù)值，如：ü 性質(zhì)3：差商與差分的關(guān)系依此類推：同理可證，對(duì)于向后差分ü 性質(zhì)4：線性ü 性質(zhì)5：差分與導(dǎo)數(shù)的關(guān)系因此： Ø 差分的計(jì)算差分計(jì)算可通過構(gòu)造差分表得到P26，表2.62.5.2 等距節(jié)點(diǎn)插值公式將牛頓插值公式中的各階差商用相應(yīng)的差分代替，就可以得到各種形式的等距節(jié)點(diǎn)插值公式。Ø 牛頓前插公式等距節(jié)點(diǎn)：要計(jì)算附

14、件點(diǎn)x的函數(shù)的值，令，則：于是：Ø 牛頓后插公式節(jié)點(diǎn)倒序排列：要計(jì)算附件點(diǎn)x的函數(shù)的值，令則：于是：注：一般當(dāng) x 靠近時(shí)用前插，靠近時(shí)用后插，故兩種公式亦稱為表初公式和表末公式。Ø P27 例2.4注：若是n次多項(xiàng)式，則是nm次多項(xiàng)式。當(dāng)n>m時(shí)，。2.6 Hermite（埃爾米特）插值Ø Hermite插值多項(xiàng)式拉格朗日插值多項(xiàng)式和牛頓插值多項(xiàng)式與被逼近函數(shù)在插值點(diǎn)上有相同的函數(shù)值，但是插值多項(xiàng)式與被逼近函數(shù)一般不相切（導(dǎo)數(shù)不同）光滑性差！Hermite插值多項(xiàng)式：求與在插值點(diǎn)上具有相同的函數(shù)值和導(dǎo)數(shù)值（甚至高階導(dǎo)數(shù)值）的插值多項(xiàng)式。Ø Hermite插值多項(xiàng)