数值分析-课件第4章

实际问题中经常要涉及到函数值的计算问题：（1）如果函数表达式本身比较复杂，且需要多次重复计算时，计算量会很大；（2）有的函数甚至没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数来近似代替，这就是数值逼近问题。

第四章多项式插值与函数逼近问题背景§1插值问题

/*InterpolationProblem*/（插值的定义）已知定义于区间上的实值函数在个互异节点

处的函数值，若函数集合中的函数满足则称为在函数集合中关于节点的一个插值函数，并称为被插值函数,[a,b]为插值区间，为插值节点，（*）式为插值条件。设外插法：内插法：用计算被插值函数在点处的近似值用计算被插值函数在点处的近似值/*AlgebraicInterpolation*/插值类型代数插值：集合为多项式函数集x0x1x2x3x4xg(x)

f(x)几何意义：有理插值：集合为有理分式函数集/*Rational*/三角插值：集合为三角函数集/*Trigonometric*/代数插值的存在唯一性设即代入插值条件：方程组的系数矩阵是Vandermonde矩阵

方程组存在唯一解，因此满足插值条件(*)

的不超过n次的插值多项式是唯一存在的.截断误差插值余项设在区间[a,b]上连续，在区间[a,b]上存在,

是满足插值条件（*）的不超过n次的插值多项式，则对存在，满足其中。且当在区间[a,b]有上界时，有代数插值的插值余项/*Remainder*/注意这里是对

t

求导证明：设结论显然成立时构造辅助函数则有个互异零点、由罗尔(Roll)定理在区间（a,b）上至少有n+1个互异零点在区间（a,b）上至少有n个互异零点以此类推，反复利用Roll定理在区间（a,b）上至少有1个零点而注：（1）插值误差与节点和之间的距离有关；

（2）如果本身为多项式，其插值函数为本身。

（3）通常不能确定,而是估计,x(a,b)

将作为误差估计上限。§2代数插值多项式的构造方法一、拉格朗日多项式

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多项式使得条件：无重合节点，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0

,y0)和(x1,y1

)两点的直线。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl称为拉氏基函数

/*LagrangeBasis*/，满足条件li(xj)=ij与有关，而与无关n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li(x)

有n

个根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial节点f若记例如也是一个插值多项式，其中可以是任意多项式。（2）Lagrange插值多项式结构对称，形式简单，常用于理论分析，因为当n较大时，计算复杂。（3）误差估计注：（1）若不将多项式次数限制为n

，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，n较大时，计算量非常大。Quiz:

给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC例1：已知分别利用sinx的1次、2次Lagrange

插值计算sin50

并估计误差。解：n=1分别利用x0,x1

以及x1,x2

计算利用这里而sin50=0.7660444…)185(50sin10pL0.77614外推

/*extrapolation*/

的实际误差0.0101利用sin50

0.76008,内插

/*interpolation*/

的实际误差0.00596内插通常优于外推。选择要计算的x

在区间的内部，插值效果较好。高次插值通常优于低次插值n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061但绝对不是次数越高就越好，嘿嘿……反插值问题已知定义于区间上的单调连续函数在个互异节点处的函数值，若函数值已知，如何求？即求因此可以看作如下插值问题：已知定义于区间上的连续函数在个互异节点处的函数值，求函数值

xi

1.01.41.82.0yi=f(xi)-2.0-0.80.41.2例2：已知单调连续函数在如下采样点的函数值：求方程在[1，2]内根的近似值。解：§2牛顿插值

/*Newton’sInterpolation*/Lagrange

插值虽然易算，但若要增加一个节点时，全部基函数li(x)

都需重新算过。将Ln(x)改写成的形式，希望每加一个节点时，只附加一项上去即可。????一、

差商(亦称均差)

/*divideddifference*/1阶差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2阶差商11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)阶差商：事实上其中差商的值与xi

的顺序无关！二、牛顿插值

/*Newton’sInterpolation*/已知定义于区间上的连续函数在个互异节点处的函数值n次Lagrange

插值多项式可表示为：其中12…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]3注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即

实际计算过程为（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn例3：已知函数的函数表：

xi12345yi=f(xi)14786写出4次Newton插值多项式解：构造差商表三、差商性质

/*Propertyofdivideddifference*/性质1即其中证明：数学归纳法n=1n=2同理归纳，结论成立性质2差商具有对称性，即的值与节点的顺序无关。由性质1易知性质3如果的k阶差商是的m次多项式，则的k+1阶差商是的m-1次多项式。证明：上式右端的分子是的m次多项式，记为则为m-1次多项式故结论成立。性质4证明：设以为节点的n次Newton插值多项式为则四、等距节点插值公式/*InterpolationFormulaewithEqualSpacing*/当节点等距分布时:称为在点处的阶向前差分称为在点处的阶向后差分称为在点处的阶中心差分向前差分

/*forwarddifference*/向后差分

/*backwarddifference*/中心差分

/*centereddifference*/恒等算子

/*identicaloperator*/移位算子

/*shiftoperator*/

差分性质（/*Propertyofdifference*/

）性质1其中证明：数学归纳法m=1m=j即对任意整数m成立性质2其中存在证明：性质3其中数学归纳法（自己证）性质4（补充）