Cht2插值法

数值分析1§1引言第2章多项式插值法一、问题背景?)(xfy),,1,0()(nixfyii),,1,0()()()(nixfxPxPii，满足求简单应用：例如程控加工机械零件等。数值分析2二、一般概念若存在一个上的函数值且已知它在点上有定义在区间设函数.,,,,],[)(1010nnyyybxxxabaxfy.,,,)()((1.1)),,1,0()()(10插值节点插值函数为，点的为则称，满足条件简单函数niixxxxfxPniyxPxP.)((1.2))()()(10插值多项式为则称为实数其中的代数多项式是一个次数不超过若xPaxaxaaxPnxPinn.三角插值分段插值；数值分析3x0yy=p(x)a=x0x1x2x3xn=b•(xi,yi)y=f(x)研究问题：（1）满足插值条件的P(x)是否存在唯一？（2）若满足插值条件的P(x)存在，如何构造P(x)？（3）如何估计用P(x)近似替代f(x)产生的误差？曲线P(x)近似f(x)（4）P(x)是否收敛于f(x)？√√√数值分析4用Pn表示所有次数不超过n的多项式函数类,若pn(x)Pn,则pn(x)=a0+a1x+…+anxn是由n+1个系数唯一确定的.nnnnnnnnnnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010其系数行列式为nnnnnxxxxxxD1111100nnnnnxxxxxx10101110)(0njiijxx定理1给定n+1个互异节点x0,x1,…,xn上的函数值y0,y1,…,yn,则满足插值条件(1.1)的n次插值多项式pn(x)是存在且唯一的.若pn(x)满足插值条件(1.1),则有数值分析5kkkkkkkkxxxxxlxxxxxl1111)(,)(x0y的几何意义)(1xLy一、线性插值与抛物线插值1、线性插值(n=1)设已知区间[xk,xk+1]端点处的函数.)(,)(1111kkkkyxLyxLy=L1(x)xkxk+1)()(111kkkkkkxxxxyyyxL11111)(kkkkkkkkyxxxxyxxxxxL或L1(x)是两个线性函数的线性组合称为节点上线性插值基函数求线性插值——过两点(xk,yk)与(xk+1,yk+1)的直线)()()(111xlyxlyxLkkkk(2.3)§2拉格朗日(Lagrange)插值线性函数值yk=f(xk)，yk+1=f(xk+1)，多项式L1(x)，使其满足数值分析6y10xkxk+1x.1)(,0)(;0)(,1)(1111kkkkkkkkxlxlxlxly10xkxk+1xlk(x)lk+1(x))()()(111xlyxlyxLkkkk(2.3)kkkkkkkkxxxxxlxxxxxl1111)(,)(节点上的线性插值基函数：满足-----过三点(xk-1,yk-1),(xk,yk)与(xk+1,yk+1)2、抛物插值法(n=2时的二次插值)设插值节点为：xk-1,xk,xk+1,求二次插值多项式L2(x)，使得L2(xj)=yj,j=k-1,k,k+1.)(2xLy的几何意义基函数法先求插值基函数lk-1(x),lk(x),lk+1(x)——二次函数,且在节点)4.2(,0)()(,1)(;0)()(,1)(;0)()(,1)(111111111111kkkkkkkkkkkkkkkkkkxlxlxlxlxlxlxlxlxl的抛物线,满足：数值分析7y10xy10xy10xxk-1xkxk+1求lk-1(x):,)()()(11kkkxxxxAxl令待定系数xk-1xkxk+1xk-1xkxk+1)()()()()(11111kkkkkkkxxxxxxxxxl)()()()()(1111kkkkkkkxxxxxxxxxl)()()()()(11111kkkkkkkxxxxxxxxxl)()()()()()()()()()()()()(111111111111112kkkkkkkkkkkkkkkkkkkkkxxxxxxxxyxxxxxxxxyxxxxxxxxyxLL2(xj)=yj,j=k-1,k,k+1.L2(x)=yk-1lk–1(x)+yklk(x)+yk+1lk+1(x)(2.5)值件插条,0)()(,1)(;0)()(,1)(;0)()(,1)(111111111111kkkkkkkkkkkkkkkkkkxlxlxlxlxlxlxlxlxl)()(1111kkkkxxxxA再构造插值多项式L2(x)是三个二次函数的线性组合由数值分析8),(xlnk插值基函数次求一个),())(()()(110nkkkkxxxxxxxxAxl可知二、拉格朗日插值多项式(2.6)).,,1,0(,)()(110niyxLxLnxxxniinnn，满足次插值多项式要求，个插值节点对于给定的一般情况，,,1)(于是得到由kkkAxl(2.8)),,1,0()())(()()())(()()(110110nkxxxxxxxxxxxxxxxxxlnkkkkkknkkk仍采用基函数法，(2.7)),,1,0,(,1,0)(nkikikixlik数值分析9次插值多项式于是，所求n(2.8)),,1,0()())(()()())(()()(,0110110nkxxxxxxxxxxxxxxxxxxxxxlnkjjjkjnkkkkkknkkk也就是构造插值多项式的方法：(1)先求插值基函数，(2)构造插值多项式。(2.9))()(0nkkknxlyxL.)(拉格朗日插值多项式次称为nxLn数值分析10(2.10))())(()(101nnxxxxxxx)())(()()(1101nkkkkkkknxxxxxxxxx(2.11))()()()(011nkknknknxxxxyxL引入记号则得于是.P)()6.2(,P是存在唯一的的插值多项式满足条件中的多项式集合在次数不超过nnnxLn定理2.,0,1,,)(0nmxxlxmnkkmk由定理2，得1)(0nkkxl)(0nkjjjkjkxxxxxl数值分析11练习给定数据表xi0123yi01514求三次拉格朗日插值多项式L3(x).123)2)(1(14)1(12)3)(1(5)2()1(1)3)(2(10xxxxxxxxx并代入数据表值得）中，取：在（39.2n解).12)(1(616)132(2xxxxxx)())(()()())(()(0110110nkjjjkjnkkkkkknkkxxxxxxxxxxxxxxxxxxxx或)(14)(5)(1)(0)(32103xlxlxlxlxL数值分析12插值余项/*Remainder*/设节点)1(nf在[a,b]内存在,考察截断误差)()()(xLxfxRnn],[baCfnbxxxan10，且f满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。)(x0)()(10xx),(10xx0)(推广：若0)()()(210xxx),(),,(211100xxxx使得0)()(10),(10使得0)(0)()(0nxx存在),(ba使得0)()(nRn(x)至少有个根n+1niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察niixtxKtRnt0)()()()((x)有n+2个不同的根x0…xnx),(,0)()1(baxxn!)1()()()1(nxKRxnn注意这里是对t求导!)1)(()()()1()1(nxKLfxnnxn!)1()()()1(nfxKxnniixnnxxnfxR0)1()(!)1()()(niixnnxxnfxR0)1()(!)1()()(数值分析13注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRnQuiz:给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？y0---10.5-0.5123456xy0---10.5-0.5123456xy0---10.5-0.5123456xABC数值分析14],[),)(()(21)()(21)(,1101021xxxxxxfxfxRnxx线性插值余项时当],[),)()(()(61)(,2202102xxxxxxxxfxRnxx抛物插值余项时当数值分析15例：已知233sin,214sin,216sin分别利用sinx的1次、2次Lagrange插值计算sin50并估计误差。解：0x1x2x185500n=1分别利用x0,x1以及x1,x2计算4,610xx利用216/4/6/214/6/4/)(1xxxL这里)3,6(,sin)(,sin)()2(xxxfxxf而)4)(6(!2)()(,23sin21)2(1xxfxRxx00762.0)185(01319.01Rsin50=0.7660444…)185(50sin10L0.77614外推/*extrapolation*/的实际误差0.010013,421xx利用sin500.76008,00660.0185~00538.01R内插/*interpolation*/的实际误差0.00596内插通常优于外推。选择要计算的x所在的区间的端点，插值效果较好。数值分析16n=223))(())((21))(())((21))(())(()(4363463464363646342xxxxxxxL)185(50sin20L0.7654323cos21;)3)(4)(6(!3cos)(2xxxxxxR00077.018500044.02Rsin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……数值分析17nkkknxlyxL0)()(一、Lagrange插值多项式nkkknknknxxxxxxyxL011,)()()()(nkknxxx01)()(若记nkjjjkknxxx)(01)()()()()()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxx