·22 第1章插值 那么Ln()为一至多n次多项式且满足{Ln()=f(c),i=0,l,2,.,n,故 Ln(x)就是关于插值点{xo,x1,.,xn}的插值多项式，这种插值形式称为Lagrange 插值多项式.l,(e)称为关于节点{zo,x1,·,xn}的Lagrange基函数. 例1.3用下列插值节点数据，构造三次Lagrange插值多项式，并计算f(0.6. -2.00 0.00 1.00 2.00 f(r) 17.00 1.00 2.00 17.00 解基函数为 (x-E1)(x-2)(x-x3) (x-0)(x-1.00)(x-2.00) a@)=0-10-20-a=(-2.00-0-2.0-1.00(-2.0-2.00 =2a26z-10e-2) @=-a-+2e-e-2到 (x-x0)(x-2)(x-x3) (x-x0)(x-x1)(-3) 国=-0a-到=专c+2-2) 的=%a-c+e- 三次Lagrange插值多项式 4=7e-e-a+c+ae-e-到-号+3te-到 +e+2e-0 f(0.6)≈L3(0.6)=-0.472 2.n次插值多项式的误差 定理1.2设Ln(x)是a,b上过{(z,f(x),i=0,1,·,n}的n次插值多 项式，x,e[a,x互不相同，当∫∈Cm+[a,时，插值多项式的误差 创9z=oc-.一其中5eaa9 *证明记n(a)=f(a)-Ln(e).因Ln(c)=f(x),i=0,1,.,n,{zo, x1,·,xn}是Rn(a)的根，于是可设Rn(e)=k(x(x-o)(r-c).(r-xn) 下面的目标是算出k(x),为此引入变量为t的函数(t): p(=f()-Ln()-k(x)(t-xo)(t-1).(t-xn)
1.1拉格朗日(Lagrange)插值多项式 .23. 令t=x,得p()=0,i=0,1,.,n 令t=王，由定义p(x)=f()-Ln(m)-k(r)r-xo)(r-1).(x-n)=0, 即p(t)至少有n+2个零点，由于f∈Cm+1[a,b,由Rolle定理，p(t)在相邻的 两个零点之间至少有一个零点，即国至少有n+1个零点，同理再对”()应用 Rolle定理，即”"(d)至少有n个零点，反复应用Role定理得到pn+)()至少有 一个零点 再对(t)求n+1阶导数， pm+(①)=fm+)(t)-k(x)(n+1月 令t=5,有 0=pm+)()=fn+)()-k(x)(n+1)！ 得到 k)=f+"⑤ (n+1)月 Rn(z)= fn+1)() n+-or-)e-n∈a, 由于pm+)()的零点与p()的零点{红，o,·,xn}有关，因而ξ为x的函 数.n次插值多项式的误差Bm(x)是插值多项式Ln(x)的截断误差，每个插值条 件都在余项Rn(x)中有所贡献 若fm+)(x川≤M,E∈a,则Rn(c)可表示为 Le<兰- 由插值多项式的存在唯一性，对于函数{f(c)=x*,k=0,1,·,n,fm+)(x) 0→n(er)=0,关于节点{zo,x1,.,xn}的Lagrange插值多项式就是其本身， Ln(回=∑4()=大，k=0,1,.,n =0 令k=0,得到∑4（四）=1 定理1.2给出了当被插函数充分光滑时的插值误差或称插值余项表达式，但是 在实际计算中，常常不知道f(c)的具体表达式，得不到f+)(工)的形式或较精确 的误差界.在实际计算中，可对误差进行下面的事后估计方法，或用差商计算（见 1.2.2小节)
.24 第1章插值 给出n+2个插值节点{xo,1,·,xn+1},任选其中的n+1个插值节点，不 妨取{，i=0,1,.,n}构造一个n次插值多项式，记为Ln(e,在n+2个插值 节点中另选n+1个插值点，不妨取{x,i=1,2,·,n+1}构造一个n次插值多 项式，记为in(x,由定理1.2，可得到 f国-n国=@e-oe-e-） (①) (n+1)！ f(x)-Ln(x) fa+n包e-)e-2.(e-n+) (m+1 (2) 设f+1)(x)在插值区间内连续而且变化不大，设fn+)(G1)≈∫n+)(52), 则有 f儿四)-Ln回≈T-w f(x)-Ln(x）r-rn+1 得到 网看国+回 f(e)-Ln(x)≈ r-o(Ln(e)-in》 (1.10) T0-Zn+1 3.Lagrange插值多项式的算法 下面用伪码描述Lagrange插值多项式的算法. step1输入：插值节点n,插值，点序列{(x,),i=0,1,n},要计算 的函数点x step2fori=0 to n li控制Lagrange基函数序列 2.1{tmp:=1;Itmp表示Lagrange基函数l(x): for j=o to i-1 tmp:=tmp*(x-j)/(xi-j); for j=i-l to n tmp:=tmp*(z-zj)/(xi-j);} 2.2 fx:-fx+tmp*y} ！计算Ln(c)=∑k(c)=fx; i=0 8tep3输出Ln(c)的计算结果fx 伪码是描述算法的过程设计语言，它是某种高级语言和自然语言的混杂语言 它取某种高级语言中的一些关键字，用于描述算法的结构化构造和数据说明等.伪 码的语句中嵌有自然语言的叙述，伪码易于理解和修改，也易于转化为程序代码，是 种使用频率较高的描写算法的语言。在伪码中，惊叹号！表示注释语句
1.2牛顿(Newton)插值多项式 25. 本教材中算法重在理解和描述计算过程，没有做优化处理 例1.4设P,1(e)由点{(ro,f(xo),(红1，f(c1)》构造的Lagrange插值多项 式，设B,2(x)由点{(x1,f(x1),(c2,f(a2)}构造的Lagrange插值多项式，则 乃1,2)=在-nA2)-c-2A1国 T2-0 是由点{(x,f(x),i=0,1,2}构造的二次Lagrange插值多项式 分析按插值定义，验证P.1,2(x)=f(x),i=0,1,2. 证明 B12=o-Ao二-B1园=fo 2-0 A12）=白-oA2e）-e-A1=f 2-0 h12=2-oA22）-o-2)A12l=fa) 2-0 由插值多项式的唯一性，P.1.2(x)由点(x,f(x),i=0,1,2构造的二次插值 多项式 由点{(，f(z),i=0,l,.,n}按Neville方法构造的n次插值多项式： hnn回)=在-oA2n）-c-n)Pn-回 In-To 1.2牛顿(Newton)插值多项式 Lagrange插值多项式的优点是格式整齐和规范，它的缺点是没有承袭性质，当 需要增加插值节点时，需要重新计算所有插值基函数4(x).本节给出具有承袭性 质的Newton插值多项式.在Newton插值中需要用到差商计算. 1.2.1差商及其计算 1.差商定义 定义1.2一阶差商 称函数值的差fx1)-f(xo)与自变量的差(1-xo)之商比值为f(e)关于点 {0,1}的一阶差商，记为f[o,x1, fo,=f()-f(ro) T1-0 而称 f0,4,=fe,-f0,到 E2-工0
.26. 第1章插值 为f(x)关于点x0,x12的二阶差商. 函数f关于xo的零阶差商即为函数在xo的函数值frol=f(xo)》 设f()在包含x0和1的区间上可微，则由中值定理有 fro,x]=f'(),ξeo,x] 定义1.3k阶差商 设xo,x1,·,xk互不相同，∫x)关于0，x1,.,xk的k阶差商为 f0,4,.,小=f2.-f0,- (1.11 Ek T0 关于差商有很多性质，我们仅列举其中的两条. 性质1.1k阶差商f[xo,x1,·,x是由函数值f(xo),f(a1),·,f(xk)的 线性组合而成 1 用归纳法可以证明这一性质， 例如 o,=f,-fe, 2-0 f(ro) f(x1) f(x2) (0-1)0-项十-0)1-2十(2-0- 性质1.2若{io,i1,.,}为{0,1，.，的任一排列，则 f0,x1,.,=fzo,E1,.,x】 该性质表明差商的值只与节点有关而与节点的顺序无关，即差商对节点具有对 称性，这一性质由性质11可直接推出。 性质1.3若f(x)为m次多项式，则∫o,x1,.,k-1,到为m-k次多 项 事实上f回)-f有因子工-o,故o,因=f回)-儿e为m-1次多 项式，于是可归纳证明此性质 E-0