前述插值问题要求被插函数与插值多项式在节点取相同值市公开课一等奖百校联赛特等奖课件.pptx

前述插值问题前述插值问题:要求被插函数与插值多项式在节点取要求被插函数与插值多项式在节点取 相同值相同值 Lagrange Lagrange型插值条件型插值条件 4 埃尔米特插值埃尔米特插值 /*Hermite Interpolation*/Hermite型插值条件型插值条件然而然而,实际许多问题还经常要求实际许多问题还经常要求求一次数求一次数多项式多项式 ，使之满足给定，使之满足给定HermiteHermite型插值条件：型插值条件：Hermite型插值型插值:两曲线不但有共同交点两曲线不但有共同交点还要有共同切线还要有共同切线2（n+1）个条件个条件第1页3 Hermite Interpolation普通地，已知普通地，已知 x0,xn 处有处有 y0,yn 和和 y0,yn，求，求 H2n+1(x)满足满足 H2n+1(xi)=yi，H2n+1(xi)=yi。解：解：设设+=ni)()()(=0iixhxhyixH2n+1 n=0iyi可验证可验证 hi(xj)=ij,hi(xj)=0,(xj)=0,(xj)=ij 上式满上式满足条件足条件 hi hihi(x)有根有根 x0,xi,xn且都是且都是2重根重根 )()()(2xlBxAxhiiii+=由余下条件由余下条件 hi(xi)=1 和和 hi(xi)=0 可解可解Ai 和和 Bi (x)hi有根有根 x0,xn,除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx=hi又又:(xi)=1 Ci=1 hi)(x)(ili2(x)xx=设设则则这么这么Hermite 插值唯一插值唯一第2页+=ni)()()(=0iixhxhyixH2n+1 n=0iyi hi)(x)(ili2(x)xx=其中其中尤其：对两节点三次埃尔米特插值尤其：对两节点三次埃尔米特插值第3页3 Hermite InterpolationQuiz:给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 h2(x)图像？图像？x0-10.5123456yxy0-10.5123456斜率斜率=1 求求Hermite多项式基本步骤：多项式基本步骤：写出对应于条件写出对应于条件hi(x)、hi(x)组合形式；组合形式；对每一个对每一个hi(x)、hi(x)找出尽可能多条件给出根；找出尽可能多条件给出根；依据多项式总阶数和根个数写出表示式；依据多项式总阶数和根个数写出表示式；依据还未利用条件解出表示式中待定系数；依据还未利用条件解出表示式中待定系数；最终完整写出最终完整写出H(x)。+=ni)()()(=0iixhxhyixH2n+1 n=0iyi hi)(x)(ili2(x)xx=第4页例例 给定函数值表以下给定函数值表以下:第5页第6页5 分段低次插值分段低次插值 /*piecewise polynomial approximation*/提升多项式次数提升多项式次数并不一定得到好结果并不一定得到好结果例：例：在在 5,5上考查上考查 Ln(x)。取。取-5-4-3-2-1 0 1 2 3 4 5-0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大，称为越大，称为Runge 现象现象Ln(x)f(x)第7页分段分段低次低次插值插值折线代替曲线折线代替曲线在每个区间在每个区间 上，用上，用1阶多项式阶多项式(直线直线)迫近迫近 f(x):记记 ，易证：当，易证：当 时，时，一致一致分段插值函数只能确保连续性，分段插值函数只能确保连续性，不能确保光滑性。不能确保光滑性。第8页 分段分段Hermite插值插值 /*Hermite piecewise polynomials*/给定给定在在 上利用两点上利用两点 y 及及 y 结构结构3次次Hermite函数函数所要提供信息太多，导数普通不易得到，光滑所要提供信息太多，导数普通不易得到，光滑性不太高（只有连续一阶导）性不太高（只有连续一阶导）第9页整体插值因为节点屡次数高而有可能发生龙格现象，整体插值因为节点屡次数高而有可能发生龙格现象，分段插值能够得到整体连续函数，但在连接点处普通分段插值能够得到整体连续函数，但在连接点处普通不光滑，而分段不光滑，而分段Hermite插值即使在连接点处一阶光插值即使在连接点处一阶光滑，但各节点导数不易给出滑，但各节点导数不易给出既想分段插值，又想在既想分段插值，又想在节节点处保持光滑，甚至点处保持光滑，甚至二阶光滑二阶光滑三次样条。三次样条。希望：希望：样条起源样条起源6 三次样条三次样条 /*Cubic Spline*/问题提出：问题提出：第10页设设 。三三次次样样条条函函数数 ,且且在在每每个个 上上为为三三三三次次次次多多多多项项项项式式式式/*cubic polynomial*/。若若它它同同时时还还满满足足 ，则则称称为为 f 三三次次样样条条插插值值函数函数/*cubic spline interpolant*/.样条本质上是样条本质上是一段一段三次多项式一段一段三次多项式拼合而成曲线拼合而成曲线在拼接处在拼接处,不但函数是连续不但函数是连续,且一阶和二阶导数也是连续且一阶和二阶导数也是连续共共4n个待定系数个待定系数共共3(n-1)个条件个条件共共n+1个条件个条件共共4n-2个条件个条件第11页 第第1类边界条件类边界条件/*clamped boundary*/：S(a)=y0，S(b)=yn 第第2类边界条件：类边界条件：S”(a)=y0”，S”(b)=yn”尤其地，尤其地，y0”=yn”=0 称为称为自由边界自由边界/*free boundary*/，对对应样条函数称为应样条函数称为自然样条自然样条/*Natural Spline*/。第第3类边界条件类边界条件/*periodic boundary*/：当当 f 为为周期函数周期函数时，时，yn=y0，S(a+)=S(b)注：注：三次样条与分段三次样条与分段 Hermite 插值根本区分在于插值根本区分在于S(x)本身本身光滑光滑，不需要知道，不需要知道 f 导数值（除了在导数值（除了在2个端点可能需要）；个端点可能需要）；而而Hermite插值依赖于插值依赖于f 在全部插值点导数值。在全部插值点导数值。f(x)H(x)S(x)第12页 结构三次样条插值函数结构三次样条插值函数第13页加以整理后可得第14页由条件因为以上两式相等,得第15页-(1)第16页假如问题要求满足第一类(一阶)边界条件:基本方程组(1)化为n-1阶方程组即化为矩阵形式第17页-(2)这是一个三对角方程组假如问题要求满足第二类(二阶自然)边界条件:自然边界条件第18页由前式,可知第19页与基本方程组(1)联合,并化为矩阵形式,得-(3)第20页注：注：三对角方程组三对角方程组,能够使用追赶法求解能够使用追赶法求解收敛性：收敛性：若若 ，且，且 ，则，则一致一致S(x)f(x)即即:提升精度只须提升精度只须增加节点增加节点,而无须提升样条阶数。而无须提升样条阶数。第21页5 Cubic Spline小结小结 计算计算 k,k,gk;计算计算 mj (追赶法等追赶法等);找到找到 x 所在区间所在区间(即找到对应即找到对应 k);由该区间上由该区间上 S(x)算出算出 f(x)近似值。近似值。第22页第一类边界条件第一类边界条件第二类边界条件第二类边界条件第23页例.对于给定节点及函数值解:h0=1 h1=2 h2=1第24页第25页第26页插值法小结插值法小结 Lagrange:给出给出 y0 yn，选基函数，选基函数 li(x)，其次数为，其次数为 节点数节点数 1。Newton Ln(x)，只是形式不一样；节点等距时方便处只是形式不一样；节点等距时方便处理。理。Hermite：给出给出 yi 及及 yi，选，选 hi(x)及及 hi(x)。Spline：分段低次：分段低次,本身光滑本身光滑,f 导数只在边界给出。导数只在边界给出。第27页