第四章 函数的数值逼近

第四章函数的数值逼近§4.0插值与拟合§4.1插值的基本理论§4.2Lagrange插值多项式§4.3分段插值与保形插值§4.4样条插值§4.5曲线拟合的最小二乘方法§4.6函数的最佳平方逼近1§4.0插值与拟合1、问题的提出

◆函数没有明确的表达式

◆函数有明确的表达式，但不是（分段）有理函数2、插值与拟合

◆插值问题：作一条曲线，其类型是事先人为给定的（比如：代数多项式），使该曲线经过所有已知点。◆拟合问题：作一条指定类型的曲线，使该曲线能在“一定意义”下逼近已知点。下一页零件2图4.1心形图上一页3§4.1插值的基本理论1、插值问题的提法◆基本提法：对于给定函数表yn…y1y0y=f(x)xn…x1x0x表4.1（其中f(x)在区间[a,b]上连续，x0,x1,…,xn

是[a,b]上n+1个互异点），要求在某函数类{φ(x)}中求一个函数φ(x)，使（4.1)4通常，称区间[a,b]为插值区间，称点xi(i=0,1,…,n)为插值结点，称(4.1)为插值条件，φ(x)为函数f(x)在结点xi(i=0,1,…,n)上的插值函数，f(x)为被插值函数。函数类{φ(x)}的取法有很多种，常用的有代数多项式，三角函数和有理函数。本章只讨论代数多项式，相应的插值问题称为多项式插值。并用φ(x)作为函数f(x)的近似函数，即5根据给出的函数表(4.1)，求不高于n次的代数多项式

(4.2)使(4.3)

几何意义：通过曲线y=f(x)上的n+1个点Mi(xi,yi)(i=0,1,…,n)，作一条n次代数多项式曲线y=Pn(x)近似代替曲线y=f(x)，如图(4.2)所示。图4.22、多项式插值问题的基本提法满足插值条件(4.3)的多项式(4.2)，称为函数f(x)在结点xi(i=0,1,…,n)上的n次插值多项式。63、插值多项式的存在唯一性由插值条件(4.3)知，插值多项式Pn(x)的系数a0,a1,…,an

满足线性方程组(4.4)其系数行列式7系数行列式D是一个n+1阶的Vandermond行列式，因结点互异，故D≠0。再由Cramer法则，线性方程组有唯一解。于是有定理1.当插值结点互异时，满足插值条件(4.3)的n次插值多项式Pn(x)存在且唯一。84、插值余项记Rn(x)=f(x)–Pn(x),则Rn(x)是用代数多项式Pn(x)近似代替函数f(x)的截断误差，通常称Rn(x)为n次插值多项式Pn(x)的余项。(4.5)定理2.若f(x)在区间[a,b]上有直到n+1阶导数，Pn(x)为f(x)在n+1个结点xi∈[a,b](i=0,1,…,n)上的n次插值多项式，则对任何x∈[a,b]有9证：由插值条件(4.3)可知，Rn(xi)=0(i=0,1,…,n)

故可设Rn(x)=k(x)ωn+1(x)(4.6)其中k(x)为待定函数。对于[a,b]上异于xi

的任一点x，作辅助函数F(t)=f(t)–Pn(t)–k(x)ωn+1(t)则F(t)在[a,b]上具有n+1阶导数F(n+1)(t)=f(n+1)(t)–k(x)(n+1)!(4.7)且F(x)=F(x0)=F(x1)=…=F(xn)=0即F(t)在[a,b]上至少有n+2个互异的零点x,x0,x1,…,xn.由洛尔定理知，F(t)在两个零点间F’(t)至少有一个零点，故F’(t)在(a,b)上至少有n+1个互异零点。对F’(t)再应用洛尔定理，依次类推，可知F(n+1)(t)在(a,b)内至少有一个零10注意：利用解方程组(4.4)去建立形如(4.2)的插值多项式，计算量大，有时还会对精度有较大的影响，因而是不可取的。点ξ，即F(n+1)(ξ)=0.

于是，由(4.7)式知，f(n+1)(ξ)–k(x)(n+1)!＝0代入(4.6)式，即得结论。对于x=xi(i=0,1,…,n)，(4.5)式显然成立。故11§4.2Lagrange插值多项式①基函数考虑最简单的插值问题。设离散数据点为{(xk,δik)}nk=0，这里i是一个非负整数，0≤i≤n，由于多项式必须满足插值条件即是的根，故可取(4.8)求插值多项式，记为12且条件满足条件(4.8)式的n次代数多项式lk(x)(k=0,1,…,n),称为在n+1个结点xi(i=0,1,…,n)上的n次插值基函数。这时可确定系数a.于是，13一般离散数据的插值多项式是基函数的线性组合：(4.9)显然，满足插值条件，即②Lagrange插值多项式则

我们把满足以上条件的插值多项式函数称为Lagrange插值多项式，记14于是，特例，当n=1时，称为线性插值当n=2时，称为抛物插值，图像如下151617例解:18且19Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高无承袭性。增加一个节点，所有的基函数都要重新计算202、Newton插值为了克服Lagrange插值的缺点，我们把多项式构造成如下形式：这种形式的插值多项式称为n次Newton插值多项式，记为Nn(x),即其中系数ai(i=0,1,…,n)可由插值条件Nn(xi)=yi(i=0,1,…,n)

确定。引入差商（均差）的概念。(4.10)

21定义1.称为函数f(x)关于点xi,xj

的一阶差商；称(i,j,k互异)为f(x)在点xi,xj,xk

处的二阶差商；一般地，称为f(x)在点xi0,xi1,…,xim

处的m阶差商；特别地，规定零阶差商f[xi]=f(xi).◆差商的性质Ⅰ.m阶差商可表为函数值f(xi0),f(xi1),…,f(xim)的线性组合，即(4.12)(4.11)22可以用归纳法证明。从(4.12)可以看出，均差与节点的排列次序无关，称为均差的对称性，即Ⅱ.由性质Ⅰ和(4.11)式可得Ⅲ.若f(x)在[a,b]上存在n阶导数，且节点x0,…,xn∈[a,b]则n阶差商与导数关系如下：(4.13)注意：对列表函数或高阶导数不存在的函数，其余项经常由差商的形式给出。23为了便于计算与应用，通常采用表格形式计算差商，如表(4.2).xkf(xk)一阶差商二阶差商三阶差商四阶差商x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]x4f(x4)f[x3,x4]f[x2,x3,x4]f[x1,x2,x3,x4]f[x0,x1,x2,x3,x4]::::::表(4.2)24

用差商表示Newton插值多项式的系数。事实上，由插值条件Nn(x0)=f(x0)可得a0=f(x0).再由插值条件Nn(x1)=f(x1),

即a0+a1(x1-x0)=f(x1)进一步由插值条件Nn(x2)=f(x2),

即

a0+a1(x2-x0)＋a2(x2-x0)(x2-x1)=f(x2)25

一般地，可由归纳法证明（自己验证）故满足插值条件Nn(xi)=f(xi)(i=0,1,…,n)的n次Newton插值多项式为(4.14)例2

给出f(x)的函数表（见下表），试用线性插值，抛物插值和4次Newton插值求f(0.596)的近似值，并估计它们的截断误差。x0.400.550.650.800.901.05f(x)0.410750.578150.696750.888111.026521.2538226解：首先根据给定的函数表构造差商表，这时，Newton插值多项式（4.14）的系数依次为0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012f[x0]=0.41075f[x0,x1]=1.11600f[x0,x1,x2]=0.28000f[x0,x1,x2,x3]=0.19733f[x0,x1,x2,x3,x4]=0.0313427故用线性插值得f(0.596)≈N1（0.596）=0.41075＋1.11600×(0.596-0.40)=0.629486用抛物插值得f(0.596)≈N2（0.596）＝N1(0.596)+0.28000×(0.596-0.40)×(0.596-0.55)

＝0.63201048用4次Newton插值得f(0.596)≈N4（0.596）

28|R1(x)|≈|f[x0,x1,

x2]ω2(0.596)|≤2.53×10－3|R2(x)|≈|f[x0,x1,

x2,x3]ω3(0.596)|≤9.61×10－5|R4(x)|≈|f[x0,…,x5]ω5(0.596)|≤3.63×10－9

这说明插值多项式的次数越高，误差越小，越可能接近真实值。＝N2(0.596)+0.19733(0.596-0.4)(0.596－0.55)(0.596-0.65)+0.03134(0.596-0.4)(0.596-0.55)(0.596-0.65)(0.596-0.8)＝0.63192

由差商的性质Ⅲ，插值多项式的余项分别为29余项由插值多项式的唯一性，当f(n+1)(x)存在时，n次Lagrange插值多项式和Newton插值多项式的余项仍为(4.5)式。例题3121517211816654321考虑函数表生成它的Lagrange插值多项式。Chap4_1.m30例题4考虑在区间[-1,1]上的函数构造等距节点上的Lagrange插值多项式。目的

观察当插值节点逐渐增多时，插值多项式对原函数的拟合变化情况。tryrunge.m31§4.3分段插值与保形插值

1、分段插值

引例fenduanex2.m给定n+1个结点a=x0<x1<…<xn=b上的函数值y0,y1,…,yn

，求一折线函数Ih(x)满足：则称Ih(x)为分段线性插值函数。32由定义可知Ih(x)在每一个小区间[xk,xk+1]上可表示为若用插值基函数表示，则在整个区间[a,b]上Ih(x)为33342、保形插值

给定[a,b]上的一种分划及f(x)在分划点上的函数值f(xk)=yk,及f’(xk)=dk

(k=0,1,…,n),则作一个分段三次Hermite

插值多项式P(x),满足条件

①P(x)∈C1[a,b]；②P(xk)=yk,P’(xk)=dk,k=0,1,…,n；③P(x)在每个小区间上是三次多项式。根据前面的结果，不难作出各个点上的插值基函数。3536dk未知？37dk的取法记第k个小区间的区间长度第k个小区间分段线性插值斜率如果与符号相同，则令如果与符号相反，则令极值点保持原来曲线的走向38121517211816654321考虑函数表生成它的保形插值多项式。例题5Chap4_3.m39§4.4样条插值对于给定函数表xx0x1…xny=f(x)y0y1…yn表4.2（其中），若函数S(x)∈C2[a,b]满足条件：

①S(x)在每个子区间[xi-1,xi](i=1,2,…,n)上都是不高于三次的多项式；

②S(x),S’(x),S’’(x)在区间[a,b]上连续；

③S(xi)=yi(i=0,1,…,n).（A－1）则称S(x)为函数f(x)关于结点x0,x1,…,xn

的三次样条插值函数。40条件①表明S(x)是一个分段三次多项式，用Si(x)

表示S(x)在第i个子区间上的表达式，则Si(x)形如其ai,bi,ci,di

待定，子区间共有n个，需确定4n个系数。另外，根据条件②③，有共有4n-2个方程，显然要确定S(x)还差两个条件。41◆边界条件的取法

Ⅰ.Ⅱ.

特别地，当时，称为自然边界条件。

Ⅲ.当原函数f(x)以b-a为周期的周期函数，则要求S(x)也是周期函数。42◆样条插值函数的建立

构造满足插值条件（A-1）及相应边界条件的三次样条插值函数S(x)的表达式可以有多种方法。例如，可以直接利用分段三次Hermite插值，只要假定S’(xj)=mj

(j=0,1,…,n),于是其中是插值基函数。利用插值条件及相应的边界条件，则可得关于mj(j=0,1,…,n)的三对角方程组，求出mj则得到所求的三次样条函数S(x).

利用S(x)的二阶导数值S’’(x)=Mj(j=0,1,…,n)表示S(x)43交互实验：插值方法比较目的：通过比较几种不同插值方法，使大家对四种插值效果在感性上有所认识，便于以后使用。tryinterp.m44实例：考察某种纤维的强度与其拉伸倍数的关系,下表是实际测定的24个纤维样品的强度与相应的拉伸倍数是记录:§4.5曲线拟合的最小二乘方法45纤维强度随拉伸倍数增加而增加并且24个点大致分布在一条直线附近---------(1)46必须找到一种度量标准来衡量什么曲线最接近所有数据点一、最小二乘法的基本概念一般使用在回归分析中称为残差称为平方误差47在回归分析中称为残差平方和从而确定(1)中的待定系数注意(1)式是一条直线因此将问题一般化48仍然定义平方误差49我们选取的度量标准是---------(2)---------(3)5051二、法方程组由可知因此可假设因此求最小二乘解转化为二次函数52由多元函数取极值的必要条件得即53---------(4)即54引入记号则由内积的概念可知---------(5)---------(6)显然内积满足交换律55方程组(4)便可化为---------(7)将其表示成矩阵形式-----(8)56并且其系数矩阵为对称阵所以法方程组的系数矩阵非奇异,即根据Cramer法则,法方程组有唯一解57即是的最小值所以因此58作为一种简单的情况,基函数之间的内积为平方误差59

回到本节开始的实例，从散点图可以看出纤维强度和拉伸倍数之间近似与线性关系故可选取线性函数为拟合函数，其基函数为建立法方程组根据内积公式，可得60法方程组为解得平方误差为61拟合曲线与散点的关系如右图:62三、数据拟合的Matlab实现1、polyfit()p=polyfit(x,y,n)其中x,y是数据点，n是拟合多项式次数，p是多项式系数（由高到低）2、polyval()y=polyval(p,x)其中p是拟合多项式系数，y是拟合多项式在x点的值。注意：当已知n个点处的函数值，而拟合多项式的次数为n-1时，则拟合函数polyfit()就是计算n-1阶插值多项式的值。Least.m63应用实例：人口预测概念：内插、外推censusgui.m64§4.6函数的最佳平方逼近设有函数，总可以在一定意义下，确定的空间中求已知函数的近似，这类问题称为函数逼近。例如是n+1维的线性空间。在Pn上定义内积其中称为权函数。65若存在，使得则称为函数的最佳平方逼近多项式。考虑一般的最佳平方逼近问题是一线性空间。66若存在，使得则称为函数在Φ上的最佳平方逼近多项式。即求解函数的极值问题。该函数取得极值的必要条件是67类似前面讨论用内积符号写出来，即称为最佳平方逼近问题的法方程。定理：设法方程的解为，则确为函数在Φ上的最佳平方逼近多项式。68小结函数的数值逼近：插值问题Lagrange插值

Newton插值分段插值和保形插值样条插值拟合最小二乘拟合－－最佳平方逼近69作业P902、5（a）补充：1、求一个次数不高于4次的多项式P(x)，使它满足P(0)=P’(0)=0,P(1)=P’(1)=1,P(2)=1.2、用最小二乘法求一形如y=a+bx2的多项式，使与下列数据相拟合：xi1925313844yi19.032.349.073.397.8703、求解矛盾方程组71补充：Hermite插值

插值函数在节点上函数值、对应的导数值、甚至高阶导数值相等，则满足这种要求的插值多项式称为Hermite

插值多项式。

下面只讨论函数值与导数个数相等的情形。设在上，yi=f(xi),mi=f’(xi)(i=0,1,…,n)

，要求插值多项式H(x)满足条件

(A－1)这里给出2n+2个相互独立的条件，可唯一确定一个次数不超过2n+1的多项式H2n+1(x)=H(x),其形式为72采用基函数方法确定系数。先求插值基函数及