《數(shù)值計(jì)算方法》課件5插值法

5.1函數(shù)插值的基本問題

5.1.1函數(shù)插值問題

函數(shù)插值的必要性

使復(fù)雜函數(shù)簡(jiǎn)單化使無解析式的函數(shù)（離散型、圖形圖像）獲得解析式為其他數(shù)值方法提供支持手段（如數(shù)值積分、微分）

插值問題定義5-1

5.1函數(shù)插值的基本問題

5.1.1函數(shù)插值問題

代數(shù)多項(xiàng)式插值問題由于多項(xiàng)式有其優(yōu)良的特性，所以通常都是用多項(xiàng)式作為插值函數(shù)。還有其它類型的插值函數(shù)，如有理函數(shù)插值、三角函數(shù)插值等

函數(shù)插值涉及的基本問題插值函數(shù)的存在唯一性問題插值函數(shù)的構(gòu)造問題截?cái)嗾`差估計(jì)與收斂性問題

代數(shù)多項(xiàng)式插值函數(shù)的構(gòu)造方法

拉格朗日插值法

埃爾米特插值法

牛頓插值法

樣條函數(shù)插值法

分段低次插值法5.1.2插值函數(shù)的存在唯一性問題

基函數(shù)定義5-2

定義5-3

定理5-1(插值函數(shù)的存在唯一性定理)在n+1個(gè)互異基點(diǎn)處滿足插值條件且次數(shù)不超過n次的多項(xiàng)式pn(x)是存在唯一的。證明：待定系數(shù)法，系數(shù)矩陣是n+1階范德蒙行列式，由于插值基點(diǎn)互異，行列式不為零，系數(shù)存在且唯一。注意：次數(shù)不超過n次必不可少，否則，唯一性不保證；定理表明：插值函數(shù)與插值方法無關(guān)例5-1p88

5.2拉格朗日(Lagrang)插值----Ln(x)

拉格朗日插值函數(shù)均可表示為一組基函數(shù)與函數(shù)值的線性組合，這些基函數(shù)與被插函數(shù)無關(guān)，只需用插值基點(diǎn)有來構(gòu)造。5.2.1拉格朗日線性插值L1(x)

線性插值及幾何意義

n=1時(shí)的n次多項(xiàng)式L1(x)稱為線性插值。此時(shí)，有兩個(gè)互異的插值基點(diǎn):x0，x1，插值條件為:L1(x0)=y0,L1(x1)=y1。其幾何意義就是用過點(diǎn)(x0,y0)和(x1,y1)的直線y=L1(x)代替y=f(x)。

拉格朗日線性插值函數(shù)L1(x)

由兩點(diǎn)式直線公式，整理可得5.2.1拉格朗日線性插值L1(x)

線性插值基函數(shù)及幾何意義

線性拉格朗日插值基函數(shù)。它們都是線性函數(shù)，且具有性質(zhì)：其幾何意義見圖示。

插值余項(xiàng)留給讀者自己證明：例5-2已知sin30o=0.5,sin45o=0.707107,求sin50o的近似值。5.2.2拉格朗日二次(拋物)插值L2(x)

拋物插值及幾何意義

插值基點(diǎn)：x0，x1，x2（互異）插值函數(shù)：二次多項(xiàng)式（拋物線）插值條件：L2(xi)=yi,i=0,1,2.

拋物插值基函數(shù)及幾何意義

要求基函數(shù)

l0(x)，l1(X)，l2(x)均為2次多項(xiàng)式，且滿足：不難得到：

其幾何意義是明顯的。5.2.2拉格朗日二次(拋物)插值L2(x)

拉格朗日拋物插值公式由拋物插值基函數(shù)的性質(zhì)和插值函數(shù)的唯一性，得

拉格朗日拋物插值公式的截?cái)嗾`差例

利用9,16,25的平方根求17和5的平方根的近似值。注意：外插與內(nèi)插的誤差比較。例5-3已知sin30o=0.5,sin45o=0.707107,sin60o=866025，用拋物插值法求sin50o的近似值。5.2.3n次拉格朗日插值

問題描述插值基點(diǎn)：x0，x1，…，xn（n+1個(gè)點(diǎn)互異）插值函數(shù)：不超過n次的多項(xiàng)式插值條件：Ln(xi)=yi,i=0,1,2,…,n

基函數(shù)

拉格朗日插值公式例5-4p935.2.4插值余項(xiàng)的誤差估計(jì)

定義5-5

設(shè)pn(x)是函數(shù)f(x)的n次插值多項(xiàng)式,其截?cái)嗾`差又稱插值余項(xiàng)記為Rn(x)=f(x)-pn(x)

定理5-2（插值余項(xiàng)定理）

設(shè)函數(shù)f(x)在包含插值基點(diǎn)及插值點(diǎn)x的區(qū)間[a,b]上連續(xù)，在(a,b)上具有n+1階導(dǎo)數(shù)，則必存在依賴于x的點(diǎn)，使其中：

不難寫出線性插值和拋物插值的余項(xiàng)公式。5.2.4插值余項(xiàng)的誤差估計(jì)關(guān)于余項(xiàng)公式的幾點(diǎn)說明（1）由插值函數(shù)唯一性定理和余項(xiàng)定理知：只要插值條件給定，插值函數(shù)是唯一存在（不論用什么樣的插值方法），其余項(xiàng)也是相同的。即余項(xiàng)公式（5-17）對(duì)后面將要討論的牛頓插值法也使用。（2）由余項(xiàng)定理不難得到下面幾個(gè)推論：例5-6p955.2.4插值余項(xiàng)的誤差估計(jì)關(guān)于余項(xiàng)公式的幾點(diǎn)說明（3）拉格朗日插值基函數(shù)的另一種表示（4）余項(xiàng)的最大估計(jì)與事后估計(jì)插值函數(shù)被表示為基函數(shù)與函數(shù)值的線性組合基函數(shù)整齊、對(duì)稱,與被插函數(shù)無關(guān),且均為n次多項(xiàng)式公式的理論價(jià)值高于牛頓插值，在其它數(shù)值方法中用到的插值函數(shù)大多都用拉格朗日插值公式表示不便于增加插值節(jié)點(diǎn)，因?yàn)榛瘮?shù)與插值節(jié)點(diǎn)和個(gè)數(shù)有關(guān)不便于估計(jì)插值余項(xiàng)，因?yàn)橛囗?xiàng)與被插函數(shù)的n+1階導(dǎo)數(shù)有關(guān)5.2.5拉格朗日插值的特點(diǎn)同一函數(shù)在不同的基函數(shù)下的表示形式是不同的。不同的插值方法選取的基函數(shù)是不同的。如何構(gòu)造插值基函數(shù)是掌握插值方法的關(guān)鍵。5.2.6拉格朗日插值在密鑰管理中的應(yīng)用

像導(dǎo)彈發(fā)射、金庫等重要場(chǎng)所的通行檢查都必須有多人參與才能生效，需要將密鑰分配給多人管理，并且必須有一定數(shù)目的掌管密鑰的人同時(shí)到場(chǎng)才能恢復(fù)密鑰。

門限方案：設(shè)秘密（密鑰）s被分成n個(gè)部分信息，每一部分信息稱為一個(gè)子密鑰或影子，由一個(gè)參與者持有，使得：

由k個(gè)或多于k個(gè)參與者持有的部分信息可重構(gòu)s。

由少于k個(gè)參與者持有的部分信息無法重構(gòu)s。稱這種方案為（k,n）秘密分割門限方案，k稱為門限方案的門限值。如果一個(gè)參與者或一組未經(jīng)授權(quán)的參與者在猜測(cè)秘密s時(shí)，并不比局外人猜秘密時(shí)有優(yōu)勢(shì)，即如果

由少于k個(gè)參與者持有的部分信息得不到秘密s的任何信息。則稱這個(gè)門限方案是完善的，即（k,n）秘密分割門限方案是完善的。5.2.6拉格朗日插值在密鑰管理中的應(yīng)用

Shamir門限方案

Shamir門限方案和中國剩余門限方案是兩個(gè)最具代表性的門限方案。

Shamir門限方案是基于多項(xiàng)式的Lagrange插值公式的。

簡(jiǎn)要描述：給定一個(gè)k-1次多項(xiàng)式，其常數(shù)項(xiàng)就是我們要保護(hù)的秘密，求出此多項(xiàng)式在n個(gè)相異點(diǎn)出的函數(shù)值，則（xi，yi）,i=1,2,…,n就是n個(gè)子密鑰。

插值理論：對(duì)一個(gè)k-1次多項(xiàng)式進(jìn)行插值，當(dāng)插值基點(diǎn)大于等于k時(shí)，其多項(xiàng)式插值結(jié)果就是原多項(xiàng)式，從而可得到其常數(shù)項(xiàng)（秘密），而少于k個(gè)基點(diǎn)的多項(xiàng)式插值不能還原給定的多項(xiàng)式，當(dāng)然也就不能得到秘密。

例s=11,k=3,n=5,隨機(jī)選取多項(xiàng)式f(x)=4x2-7x+11，則f(3)=26,f(-2)=41,f(1)=8,f(5)=74,f(10)=341,秘密為f(0)=11.5.3牛頓(Newton)插值----Nn(x)5.3.1問題與策略

問題

由于拉格朗日公式具有“對(duì)稱性”，但不具備“承襲性”，即插值基點(diǎn)個(gè)數(shù)改變后所有基函數(shù)都改變。插值余項(xiàng)與被插函數(shù)的n+1階導(dǎo)數(shù)有關(guān)

策略

引入不超過n次多項(xiàng)式的另一組基：

1，(x-x0)，(x-x0)(x-x1)，…，(x-x0)(x-x1)…(x-xn-1)作為插值公式的基函數(shù)，則牛頓插值公式可表示為：Nn(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-x1)…(x-xn-1)

主要工作

牛頓插值公式的主要工作就是計(jì)算插值公式中的系數(shù)

a0，a1，a2，…，an

待定系數(shù)法是不可取的，為此，引入均差（差商）。

特例：線性和拋物牛頓插值公式的構(gòu)造5.3.2均差及其計(jì)算

均差定義5-6

均差的性質(zhì)5.3.2均差及其計(jì)算

均差表

例5-7xif(xi)一階均差二階均差三階均差四階均差…x0x1x2x3x4…f(x0)f(x1)f(x2)f(x3)f(x4)…f[x0,x1]f[x1,x2]f[x2,x3]f[x3,x4]…f[x0,x1,x2]f[x1,x2,x3]f[x2,x3,x4]…f[x0,x1,x2,x3]f[x1,x2,x3,x4]…f[x0,x1,x2,x3,x4]…………………試試改變節(jié)點(diǎn)次序，三階差商的值相同嗎？5.3.3牛頓插值公式及余項(xiàng)差商的性質(zhì)(3)說明了兩種插值公式的余項(xiàng)是等價(jià)的5.3.3牛頓插值公式及余項(xiàng)由插值多項(xiàng)式的唯一性定理可知，滿足相同插值條件的拉格朗日插值多項(xiàng)式與牛頓插值多項(xiàng)式本質(zhì)上是同一個(gè)插值多項(xiàng)式，只是由于插值基函數(shù)選擇不同使得其具有不同的表示形式。相比拉格朗日插值，牛頓插值具有以下優(yōu)點(diǎn)：插值多項(xiàng)式具有承襲性，便于增加插值節(jié)點(diǎn)；插值余項(xiàng)更具一般性，對(duì)于表格函數(shù)或?qū)?shù)不存在的情形都適用；插值公式中每一項(xiàng)的系數(shù)就是各階差商，計(jì)算量小，便于程序?qū)崿F(xiàn)。例5-8P100

牛頓插值算法步驟p100

牛頓插值算法流程框圖p1005.4埃爾米特(Hermite)插值5.4.1含有導(dǎo)數(shù)條件的插值

為了更好地近似被插值函數(shù)，許多實(shí)際問題不僅要求插值函數(shù)與被插函數(shù)在插值節(jié)點(diǎn)處函數(shù)值相等，還要求插值節(jié)點(diǎn)處的導(dǎo)數(shù)值也相等。一般來說，如果給出n+1個(gè)含有函數(shù)值和導(dǎo)數(shù)值的插值條件，就可以構(gòu)造出次數(shù)不超過n次的埃爾米特插值多項(xiàng)式。稱這種帶有導(dǎo)數(shù)條件的插值為埃爾米特(Hermite)插值。例5-9求具有三個(gè)節(jié)點(diǎn)滿足插值條件p(xj)=f(xj)(j=0,1,2)及p’(x1)=f’(x1)的三次埃爾米特插值多項(xiàng)式，并證明余項(xiàng)例5-10P102例5-11P1035.4.2兩點(diǎn)三次埃爾米特插值

問題描述

求不超過3次的插值多項(xiàng)式H(x)，滿足插值條件

H(xk)=yk=f(xk),H(xk+1)=yk+1=f(xk+1)H’(xk)=mk=f’(xk),H’(xk+1)=mk+1=f’(xk+1)

構(gòu)造思想：借助拉格朗日插值的思想，先構(gòu)造4個(gè)滿足以下條件的3次埃爾米特插值基函數(shù)。5.4.2兩點(diǎn)三次埃爾米特插值

兩點(diǎn)三次埃爾米特多項(xiàng)式

由埃爾米特插值基函數(shù)的性質(zhì)，兩點(diǎn)三次埃爾米特多項(xiàng)式可寫成

基函數(shù)的確定

4個(gè)基函數(shù)都是不超過3次的多項(xiàng)式，由4個(gè)條件可唯一確定，最終得到。例5-12p104用兩點(diǎn)三次埃爾米特插值公式解例5-105.4埃爾米特(Hermite)插值5.4.2兩點(diǎn)三次埃爾米特插值

插值余項(xiàng)類似拉格朗日插值余項(xiàng)的證明，得到兩點(diǎn)三次埃爾米特插值公式的余項(xiàng)為用兩點(diǎn)三次埃爾米特公式重作例5-1，求sin50o的近似值。5.5分段低次插值5.5.1龍格(Runge)現(xiàn)象

龍格現(xiàn)象：插值節(jié)點(diǎn)增多，其插值精度未必提高

龍格現(xiàn)象的實(shí)質(zhì)：插值多項(xiàng)式Pn(x)不收斂與f(x)

龍格現(xiàn)象的應(yīng)對(duì)：

分段低次插值。各小區(qū)間連接處導(dǎo)數(shù)不連續(xù)分段埃爾米特插值。要提供個(gè)節(jié)點(diǎn)處的導(dǎo)數(shù)值分段光滑插值。樣條插值有理分式插值。5.5分段低次插值5.5.2分段線性插值

分段線性插值就是過插值點(diǎn)用折線來近似曲線。

每個(gè)子區(qū)間[xk,xk+1]上的線性插值余項(xiàng)

整體截?cái)嗾`差

當(dāng)f(x)為僅連續(xù)函數(shù)時(shí)，分段線性插值函數(shù)仍是一致收斂的。5.5.3分段三次埃爾米特插值

整體截?cái)嗾`差對(duì)于分段三次埃爾米特插值，可以證明：當(dāng)f(x)一階導(dǎo)數(shù)連續(xù)時(shí)，不僅I(x)一致收斂與f(x)，而且I’(x)也一致收斂于f’(x)。它廣泛應(yīng)用于外形設(shè)計(jì)。5.6三次樣條插值

工程實(shí)際中對(duì)插值函數(shù)的光滑性要求高，內(nèi)點(diǎn)處要求一、二階導(dǎo)數(shù)連續(xù)；

但插值條件僅已知n+1個(gè)節(jié)點(diǎn)處的函數(shù)值，內(nèi)點(diǎn)處的導(dǎo)函數(shù)值沒有指定。

m次樣條函數(shù)s(x)是一個(gè)分段函數(shù)，對(duì)于區(qū)間[a,b]的一個(gè)劃分a=x0<x1<…<xn=b(n>1)

函數(shù)s(x)在每個(gè)子區(qū)間[xi,xi+1]上都是不超過m次的多項(xiàng)式，并且m-1階導(dǎo)數(shù)s(m-1)(x)在內(nèi)點(diǎn)x1,…,xn-1處連續(xù)。

通常使用三次樣條函數(shù)進(jìn)行插值，稱為三次樣條插值函數(shù)；

此時(shí)，三次樣條函數(shù)同時(shí)滿足插值條件

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

通常記

s’’(x)=M(x)，稱為彎矩，呈折線；s’’’(x)=Q(x)，稱為剪力，呈臺(tái)線；s’(x)=m(x),一階光滑。5.6三次樣條插值5.6.1三次樣條插值的定解條件

n個(gè)子區(qū)間，每個(gè)子區(qū)間是三次多項(xiàng)式，共需4n個(gè)條件。

插值條件，s(xi)=f(xi)，i=0,1,…,n，共n+1個(gè)條件。

內(nèi)點(diǎn)處連續(xù)條件:零階導(dǎo)連續(xù)

s(xi-0)=s(xi+0),i=1,…,n-1,共n-1個(gè)條件。

一階導(dǎo)連續(xù)

s’(xi-0)=s’(xi+0),i=1,…,n-1,共n-1個(gè)條件。二階導(dǎo)連續(xù)s’’(xi-0)=s’’(xi+0),i=1,…,n-1,共n-1個(gè)條件。

共有4n-2個(gè)條件!

為得到4n個(gè)條件，需附加2個(gè)條件，稱為邊界條件。5.6三次樣條插值5.6.1三次樣條插值的定解條件

第一種邊界條件（固支條件）已知兩端點(diǎn)處的一階導(dǎo)數(shù)值s’(x0)=f’(x0),s’(xn)=f’(xn)

第二種邊界條件已知兩端點(diǎn)處的二階導(dǎo)數(shù)值s’‘(x0)=f’’(x0),s’‘(xn)=f‘’(xn)特別地，令s’‘(x0)=s’‘(xn)=

0，稱為自然邊界條件。

第三種邊界條件（周期條件）s’(x0+0)=s’(xn-0),s’’(x0+0)=s’’(xn-0)例5-13已知函數(shù)f(x)在三個(gè)點(diǎn)處的值為

f(-1)=1,f(0)=0,f(1)=1在區(qū)間[-1,1]上，求f(x)在自然邊界條件下的三次樣條插值多項(xiàng)式。5.6.1三次樣條插值的定解條件5.6三次樣條插值5.6.2三次樣條插值函數(shù)的構(gòu)造方法一：m法即三轉(zhuǎn)角法

基本思路：以插值點(diǎn)處的一階導(dǎo)數(shù)mj為待定系數(shù)。

構(gòu)造過程：

先每個(gè)子區(qū)間采用兩點(diǎn)三次埃爾米特插值寫出樣條函數(shù)Sj(x)；它隱含了插值和零階連續(xù)條件和內(nèi)點(diǎn)處一階導(dǎo)數(shù)連續(xù)條件；再對(duì)Sj(x)求二階導(dǎo)數(shù)，利用內(nèi)點(diǎn)處二階導(dǎo)數(shù)連續(xù)

Sj-1’’(xj-0)=Sj’’(xj+0)j=1,2,…,n-1

最后得到關(guān)于待定參數(shù)mj的三對(duì)角線性方程組。

特點(diǎn)：求解第一種邊界條件有利。例5-14p111方法二：M法即三彎矩法

基本思路：以插值點(diǎn)處的二階導(dǎo)數(shù)Mj為待定系數(shù)。

構(gòu)造過程：先用分段線性插值公式寫出樣條函數(shù)S(x)的二階導(dǎo)函數(shù)M(x),它隱含了內(nèi)點(diǎn)處的二階導(dǎo)數(shù)連續(xù)條件;再對(duì)M(x)

作兩次不定積分,得S(x),由插值和連續(xù)條件確定2n個(gè)積分常數(shù),

然后對(duì)S(x)求一階導(dǎo)數(shù)，用一階導(dǎo)數(shù)內(nèi)點(diǎn)處的連續(xù)條件

Sj-1’(xj-0)=Sj’(xj+0)j=1,2,…,n-1

最后得到關(guān)于待定參數(shù)Mj的三對(duì)角線性方程組。

特點(diǎn)：求解第二種邊界條件有利。5.6三次樣條插值5.6.2三次樣條插值函數(shù)的構(gòu)造5.7二元函數(shù)插值方法5.7.1雙線性插值

問題：假設(shè)已知函數(shù)f(x,y)在下圖所示矩形區(qū)域的頂點(diǎn)Ai的函數(shù)值，尋求一插值函數(shù)P(x,y)滿足這4個(gè)插值條件。

求解思路：利用拉格朗日插值的思想構(gòu)造4個(gè)基函數(shù)，滿足：插值函數(shù)：令P(x,y)=a+bx+cy+dxy上式對(duì)x和y均為線性的，故稱為雙線性函數(shù)