1.1拉格朗日(Lagrange)插值多项式 21 {m,f),i=0,1,…,n以，则P(e)满足{Pn()=fz),i=0,l,2,…,n,事 实上一个插值点就是一个插值条件. 将{(e,f()》,i=0,1,2,…,n}依次代入P(c)中得到线性方程组 a0+a10+2x话+…+anx0=f(xo) ao+a1x1+a2x+…+anx=f1） (1.6) a0+a1m+a2x品+…+anxh=f(xn) 方程组的系数行列式是范德蒙(Vandermonde)行列式 10x V(x0,1,…,xn)= 11号… Π(-) 0<j<i<n 当互异时，Ⅱ(c-)≠0，方程组(1.6)的解存在唯一.即问题1.3的 0≤j<i≤n 解存在而且唯一 通过求解(1.6)得到插值多项式P(x,因其计算量太大而不可取，下面用La grange基函数，构造n次Lagrange插值多项式. 对于n+1个互不相同的插值节点{(，f(x),i=0,1,2,…,n},由n次插 值多项式的唯一性，可对每个插值节点作出相应的n次插值基函数{：()，i= 0,1,2,…,nm},要求 l(a）=6= ∫1，i=j 0,i≠j {x0,x1,·,-1,+1,…,xn}是l(z)零点，因此可设 l(）=a(x-xo)e-1)…(--1)(-x+i)…(e-xn) 由()=1，将x=x4代入(c)得到 l()=a(m-x0)(m-x1)小…(m-x-i)-E+i)…(m-xn）=1 (c-0)…(e-x-i(x-+1)小…(e-xn) (1.7) 作其组合 Ln(e)=∑(e)fc) (1.8)
.22 第1章插值 那么Ln(e)为一至多n次多项式且满足{Ln()=f,i=0,l,2,…,n以，故 Ln(c)就是关于插值点{xo,d1,…,xn}的插值多项式，这种插值形式称为Lagrange 插值多项式.(e)称为关于节点{o,1,·,工n}的Lagrange基函数 例1.3用下列插值节点数据，构造三次Lagrange插值多项式，并计算f(0.6) -2.00 0.00 100 2.00 f 17.00 100 2.00 17.00 解基函数为 l6(x)= (x-x1)(x-x2)(x-x3） (x-0)(x-1.00)(x-2.00) (0-1)00-2)0-2.00-0(-2.00-1.00(-2.00-2.00 =24-1e-2 4()= (-o)(-2)(=-23) (c1-0)(x1-D2)x1-x3) +2e-e-2 l2(x)= e-me=到==c+2re-2 (r2-x0)(2-T)(x2-T3) ao--治a动妆+ge- 三次Lagrange插值多项式 h回=274e-10e-2+e+2e-10e-2-3c+2e-2到 24 +e+2e-0 f(0.6)≈L3(0.6)=-0.472 2.n次插值多项式的误差 定理12设Ln(x)是[a,上过{(c,f(z),i=0,1,…,n)的n次插值多 项式，∈a,,x互不相同，当f∈Cm+1a,)时，插值多项式的误差 m+7e-z-e-其中ea,月a *证明记R(e)=fx)-Ln(e.因Ln()=f,i=0,l,…,n,{0, x1,…,xn}是Rn(c)的根，于是可设Rn(e)=k(r(x-ro)z-x1)…(r-xn) 下面的目标是算出k(x),为此引入变量为t的函数(t: (0=f)-Ln()-k(t-xo)(t-)…(t-xn)
l.1拉格朗日(Lagrange)插值多项式 ·23 令t=x,得p()=0,i=0,1,…,n 令t=x,由定义p(x)=f(x)-Ln(x)-k(x)(x-x0)(e-x1)…(e-xn)=0, 即p()至少有n+2个零点，由于∫∈Cm+1[a,,由Role定理，p(t)在相邻的 两个零点之间至少有一个零点，即可'()至少有n+1个零点，同理再对”()应用 Rolle定理，即"()至少有n个零点，反复应用Rolle定理得到pn+)()至少有 一个零点， 再对p()求n+1阶导数 pm+)()=fm+9(d)-kx)(n+1)月 令t=6,有 0=n+()=∫+)()-k(x)(n+10月 得到 f(n+1)(E) k(a)= (n+1)H fm+1(), 由于pn+(0的零点与()的零点{红，0，·，xn}有关，因而为x的函 数.n次插值多项式的误差R(z)是插值多项式Ln(x)的截断误差，每个插值条 件都在余项R(x)中有所贡献. 若fm+)(≤M,x∈a,,则R(回)可表示为 Ra≤aie- 由插值多项式的存在唯一性，对于函数{f(x)=x,k=0,1,·,n},fm+1)(x)= 0→Rn(r)=0,关于节点{xo,1,…,工n}的Lagrange插值多项式就是其本身， Ln倒)=∑4(e)=六，k=0,1…,n 0 令k=0,得到(x)=1. =0 定理1.2给出了当被插函数充分光滑时的插值误差或称插值余项表达式，但是， 在实际计算中，常常不知道∫(x)的具体表达式，得不到∫+)(x)的形式或较精确 的误差界.在实际计算中，可对误差进行下面的事后估计方法，或用差商计算（见 1.2.2小节)
,24 第1章插值 给出n十2个插值节点{0，，…，+小，任选其中的n+1个插值节点，不 妨取{x,i=0,1,·,n}构造一个n次插值多项式，记为Lm(a),在n+2个插值 节点中另选n+1个插值点，不妨取{x,i=1,2,·,n+1)构造一个n次插值多 项式，记为in(x,由定理12，可得到 (m+1) () fg-in回=n园e-e-小…e-d (m+1)1 (2) 设fm+)(e)在插值区间内连续而且变化不大，设fm+(51)≈∫m+)(2), 则有 僧编 -T0 得到 阳*看国+回 fa-h”国-La (1.10) 3.Lagrange插值多项式的算法 下面用伪码描述Lagrange插值多项式的算法. step1输入：插值节点n,插值点序列{(,),i=0,1,…,n},要计算 的函数点正 step2fori=0 to n li控制Lagrange基函数序列 2.1{tp:=1;Itmp表示Lagrange基函数l(e: for j=o to i-1 tp:=tp*(红-x)/(x-) for j=i-1 to n tp:=tp*(x-g)/(-小；】 2.2fx:=fx+tp*} ！计算Ln(国)=∑4e=x =0 step3输出Ln(a)的计算结果fx 伪码是描述算法的过程设计语言，它是某种高级语言和自然语言的混杂语言， 它取某种高级语言中的一些关键字，用于描述算法的结构化构造和数据说明等.伪 码的语句中嵌有自然语言的叙述，伪码易于理解和修改，也易于转化为程序代码，是 种使用频率较高的描写算法的语言.在伪码中，惊叹号！表示注释语句
l1.2牛顿(Newton)插值多项式 ·25· 本教材中算法重在理解和描述计算过程，没有做优化处理， 例1.4设B.1(e)由点{(xo,f(aro),(e1,f(m1)}构造的Lagrange插值多项 式，设B.2(x)由点{(r1,f(ax1),(a2,f(x2)》构造的Lagrange插值多项式，则 A12=-nA2倒-e-2A包 T2一工0 是由点{(x,f(x)》,i=0,1,2}构造的二次Lagrange插值多项式. 分析按插值定义，验证B1,2()=f(x),i=0,1,2. 证明 h12o=o-oB2n）=-2]B1回=f） T2-0 Poa()=()()-()P()() 2一0 A.12)=-oA2a）--B1l=f T9一无0 由插值多项式的唯一性，乃，1,2(x)由点(m,f(x),i=0,1,2构造的二次插值 多项式。 由点{(c,f(x),i=0,l,·,n}按Neville方法构造的n次插值多项式： B1…n回)=包-A2a回-e-nR=-回 n-0 l.2牛顿(Newton)插值多项式 Lagrange插值多项式的优点是格式整齐和规范，它的缺点是没有承袭性质，当 需要增加插值节点时，需要重新计算所有插值基函数4（口）。本节给出具有承袭性 质的Newton插值多项式.在Newton插值中需要用到差商计算 1.2.1差商及其计算 1.差商定义 定义1.2一阶差商 称函数值的差f(x1)-fxo)与自变量的差(x1-xo)之商比值为fa)关于点 {x0,}的一阶差商，记为∫0， fo,l=f)-fo】 1-0 而称 fm,1,=f,2-fo, 2-0