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

5.1.1函數(shù)插值問題

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

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

插值問題定義5-1

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

5.1.1函數(shù)插值問題

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

函數(shù)插值涉及的基本問題插值函數(shù)的存在唯一性問題插值函數(shù)的構(gòu)造問題截斷誤差估計與收斂性問題

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

拉格朗日插值法

埃爾米特插值法

牛頓插值法

樣條函數(shù)插值法

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

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

定義5-3

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

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

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

線性插值及幾何意義

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

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

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

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

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

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

拋物插值及幾何意義

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

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

要求基函數(shù)

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

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

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

拉格朗日拋物插值公式的截斷誤差例

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

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

基函數(shù)

拉格朗日插值公式例5-4p935.2.4插值余項的誤差估計

定義5-5

設pn(x)是函數(shù)f(x)的n次插值多項式,其截斷誤差又稱插值余項記為Rn(x)=f(x)-pn(x)

定理5-2（插值余項定理）

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

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

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

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

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

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

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

Shamir門限方案

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

Shamir門限方案是基于多項式的Lagrange插值公式的。

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

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

例s=11,k=3,n=5,隨機選取多項式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問題與策略

問題

由于拉格朗日公式具有“對稱性”，但不具備“承襲性”，即插值基點個數(shù)改變后所有基函數(shù)都改變。插值余項與被插函數(shù)的n+1階導數(shù)有關

策略

引入不超過n次多項式的另一組基：

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)

主要工作

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

a0，a1，a2，…，an

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

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

均差定義5-6

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

均差表

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

牛頓插值算法步驟p100

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

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

問題描述

求不超過3次的插值多項式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個滿足以下條件的3次埃爾米特插值基函數(shù)。5.4.2兩點三次埃爾米特插值

兩點三次埃爾米特多項式

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

基函數(shù)的確定

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

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

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

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

龍格現(xiàn)象的應對：

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

分段線性插值就是過插值點用折線來近似曲線。

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

整體截斷誤差

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

整體截斷誤差對于分段三次埃爾米特插值，可以證明：當f(x)一階導數(shù)連續(xù)時，不僅I(x)一致收斂與f(x)，而且I’(x)也一致收斂于f’(x)。它廣泛應用于外形設計。5.6三次樣條插值

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

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

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

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

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

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

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

通常記

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

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

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

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

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

一階導連續(xù)

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

共有4n-2個條件!

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

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

第二種邊界條件已知兩端點處的二階導數(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)在三個點處的值為

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

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

構(gòu)造過程：

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

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

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

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

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

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

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

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

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

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

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

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

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