请给一种算法计算2256要求乘法次数尽可能少-复习

请给一种算法计算2256要求乘法次数尽可能少。复习：这样共计算8次乘法就可以计算出结果第二章插值法种离散数据建立连续模型.解决上述问题是函数插值与逼近的主要任在实践中经常会碰到这样的问题：较为简单的函数近似某个复杂的函数,或为各务。插值是数值逼近的一种重要方法。

本章介绍一些常用函数插值方法.用一一、实际背景基本过程：

飞机、汽车的外形设计制造测点插值曲线插值曲面

三角函数表、对数函数表、指数函数表等

不在表上的函数值如何求？

插值问题：求一条曲线严格通过数据点曲线拟合问题：求一条曲线在一定意义下靠近数据点

注：插值问题和曲线拟合问题统称函数逼近问题！二、问题的分类三、插值问题的有关概念已知函数y=f(x)在一系列互不相同的节点

x0…xn

处的函数值x

x0x1

x2…xny

y0y1

y2…yn构造一个简单易算的近似函数g(x)

，满足条件g(xi)=f(xi)(i=0,…n)。称这样的问题为插值问题，并称g(x)为f(x)的插值函数，x0,

x1,x2,

…,xn是插值节点。包含节点的区间称为插值区间x0x1x2x3x4xg(x)

f(x)满足插值条件的插值函数g(x)唯一吗？答不唯一。g(x)可以是代数多项式、三角多项式、有理函数等等，但最简单而最常用的是代数多项式。?代数多项式插值问题已知函数y=f(x)在一系列互不相同的节点

x0…xn

处的函数值x

x0x1

x2…xny

y0y1

y2…yn若次数不超过n的多项式Pn(x)，满足条件Pn(xi)=f(xi)(i=0,…n)。则称Pn(x)为f(x)的n次插值多项式这样的Pn(x)唯一存在吗？?根据插值条件有证：次数不超过n的多项式可设为：定理满足以上插值条件且次数不超过n的多项式Pn(x)唯一存在。则其系数行列式为因此方程组有唯一解，即Pn(x)存在并唯一。这样构造多项式计算量大，且没有一般结构式，下面介绍几种直接构造Pn(x)的方法。2.2、Lagrange插值多项式根据线性空间的理论一、线性插值与抛物插值问题：给定区间及端点函数值，要求线性插值多项式，使它满足当n=1时的n次代数多项式插值称为线性插值就是两点的连线（点斜式）（两点式）的线性组合得到，其系数分别为及，即令称及为线性插值基函数，显然，及也是线性插值多项式，在节点及上满足条件抛物线插值当n=2时的n次代数多项式插值称为抛物线插值。xyoy=f(x)y=L2(x)xk+1xk-1xk我们希望二次插值也能由一些二次插值基函数来线性组合:这时，li(x)(i=k-1,k,k+1)是二次多项式，且应满足满足上面条件的

li(x)是否存在?若存在，具有什么形式呢?于是同理li(x)称为二次插值基函数.显然它满足条件二次拉格朗日插值公式

二、拉格朗日插值多项式

将前面的方法推广到一般情形，讨论如何构造通过个节点的次插值多项式.

根据插值的定义应满足希望找到li(x)，i=0,…,n

使得

li(xj)=

ij

；然后令

==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li有n

个根x0…

xi…xn

=-=---=njj

ijiniiixxCxxxxxxCxl00)())...()...(()(

-==j

ijiiiixxCxl)(11)(

拉格朗日多项式与有关，而与无关节点fn次插值基函数为于是例解:且此例中,利用两个节点169和225,也可以作插值多项式,这种插值方法称为Lagrange线性插值,求近似值时可在n+1个节点中取相邻的两个节点作线性插值例解:Lagrange插值基函数为Lagrange线性插值多项式为所以请编写出Lagrange插值的Matlab程序Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高

拉格朗日插值算法实现

x0x1xi

xi+1xn-1xny=f(x)y=Ln(x)ab在插值区间

a,b

上用插值多项式Ln(x)近似代替f(x),除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。其截断误差为Rn(x)=f(x)-Ln(x)

三、插值余项与误差估计其中如果那么插值多项式逼近的截断误差限是

由给定条件知在节点上为零，即，其中是与x有关的待定函数.

现把x看成[a,b]上的一个固定点，作函数根据插值条件及余项定义，可知在点及x处均为零，故在上有个零点.证明于是根据罗尔定理，在的两个零点间至少有一个零点，故在内至少有个零点.

对再应用罗尔定理，可知在内至少有

n个零点.

依此类推，在内至少有一个零点，记为，使于是

且依赖于x当时，线性插值余项为当时，抛物插值余项为注：

当

f(x)为任一个次数

n

的多项式时，,可知，即插值多项式对于次数

n的多项式是精确的。例

已知分别利用sinx的1次、2次Lagrange插值计算sin50

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

以及x1,x2

计算

利用这里而

sin50=0.7660444…)185(50sin10

pL0.77614外推

(extrapolation)

的实际误差

0.01001

利用sin50

0.76008,内插

(interpolation)

的实际误差

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

所在的区间的端点，插值效果较好。n=2)185(50sin20

pL0.76543

sin50=0.7660444…2次插值的实际误差

0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，

例

考虑下述的插值法问题：求二次多项式P(x)，满足P(x0)=y0,其中是已给的数据并给出使这一问题的解存在且唯一的条件.解：设则由已知条件有即所以故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为这就是P（x）存在且唯一的条件。优点：

Lagrange插值公式(利用插值基函数很容易得到):含义直观,结构紧凑,在理论分析中非常方便;计算机上实现也很容易.缺点：一是计算量大；另外，还有一个更严重的缺点，当插值节点增加时，全部插值基函数均要随之变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要增加一项计算。

为克服上述两个缺点,

努力：把插值多项式变形为便于计算的形式。希望：计算改变的过程中,尽可能能利用已有的计算结果.拉格朗日插值公式的优缺点Lagrange插值多项式的插值基函数形式上太复杂,计算量很大,并且重复计算也很多是否可以将下面n+1个多项式作为插值基函数呢？2.3

牛顿(Newton)插值公式?)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]

我们再看线性插值的点斜式:)(00xxy-+=f[x0,x1]常数(差商)

由此启发，我们希望二次插值也能类似地有有规律的组合表达式:P2(x)=

0+1(x-x0)+2(x-x0)(x-x1)利用P2(x0)=y0有:0=y0,利用P2(x1)=y1有:1=0101xxxx--(())ff=f[x0,x1],利用P2(x2)=y2有:2=f[x0,x1]

(x2-x0)(x2-x1)

(x2-x0)(x2-x1)0xx2-(())ff

(x2-x0)-f[x0,x2]f[x0,x1]

x2-x1

=-=f[x0,x1,x2];P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)f[x0,x1]f[x0,x1,x2]f[x0,x2]一、

插值多项式的逐次生成二次牛顿插值公式注:1.事实上,从上述可看出二次牛顿插值公式是用待定系数法求得的;2.它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)f[x0,x1]f[x0,x1,x2]f[x0,x1],f[x0,x1,x2]f(x0),

1,(x-x0),(x-x0)(x-x1)即函数的线性组合,组合系数为本质上还是基函数法.

更一般地，n+1个节点的插值多项式，我们希望由上述类似的一组特殊函数：来线性组合为：1,(x-x0),(x-x0)(x-x1)，……，(x-x0)(x-x1)…(x-xn)那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法.容易发现,计算a0,a1,a2,…,an

是很有规律的.二、均差及其性质当x=x0时，Pn(x0)=a0=f0.当x=x1时，Pn(x1)=a0+a1(x1-x0)=f1,推得a1=f1-f0x1-x0当x=x2时，Pn(x2)=a0+a1(x2-x0)+a2(x2-x0)(x2-x1)=f2,推得f1-f0x1-x0-f1-f0x1-x0a2=x2-x1

依次递推可得到a3,…,an.为写出系数ak的一般表达式,先引进如下均差定义.

定义2

称为函数f(x)关于点x0,xk的一阶均差.称为f(x)的二阶均差.一般地,称

为f(x)的k阶均差(差商).f[x0,xk]=f(xk)-f(x0)xk-x0f[x0,x1,xk]=f[x0,xk]-f[x0,x1]xk-x1f[x0,x1,…,xk]=f[x0,…,xk-2,xk]-f[x0,x1,…,xk-1]xk-xk-1均差有如下的基本性质:f[x0,x1,…,xk]=f[x1,…,xk-1,xk]-f[x0,x1,…,xk-1]xk-x02º由性质1º可得:f[x0,x1,…,xk]=f(n)(ξ)n!3º若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn[a,b],则n阶均差与导数关系如下:这个公式可直接用罗尔定理证明.1ºk阶均差可表示为函数值f(x0),f(x1),…,f(xk)的线性组合,即f[x0,x1,…,xk]=f(xj)(xj-xj+1)…(xj-xk)…(xj-xj+1)(xj-x0)∑

kj=0这个性质也表明均差与节点的排列次序无关,称为均差的对称性,即f[x0,x1,…,xk]=f[x1,x0,x2,…,xk]=…=f[x1,…,xk,x0]所以均差表:可以看出，牛顿插值公式计算方便，增加一个插值点，只要多计算一项，而Nn(x)的各项系数恰好是各阶差商值，很有规律

例

给出函数y=(x)的函数表

解

差商表如下i0123xi-2-112(xi)531721写出函数y=(x)的差商表.xiƒ(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-1三、牛顿插值多项式Nn(x)Rn(x)其中Nn(x)称为牛顿插值多项式;Rn(x)称为牛顿插值余项.它比拉格朗日插值多项式计算量省,且便于程序设计.Rn(x)Nn(x)ωn+1(x)注：

由唯一性可知Nn(x)

Ln(x)，只是算法不同，故其余项也相同，即

例

依据如下函数值表建立不超过3次的拉格朗日插值多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性.

解:(1)拉格朗日插值多项式Ln(x).插值基函数xk0124f(xk)19233拉格朗日插值多项式为:(2)牛顿插值多项式Nn(x).建立如下差商表(3)唯一性验证.通过比较牛顿