第二章插值法数值分析课件.ppt

第二章第二章 插值法插值法/*Interpolation*/Interpolation_introduction1 引引 言言1.1.函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算,而又需要计算许而又需要计算许多点处的函数值多点处的函数值2.2.仅有几个采样点处的函数值仅有几个采样点处的函数值,而又需要知道非采样而又需要知道非采样点处的函数值点处的函数值 v上述问题的一种上述问题的一种解决思路：解决思路：建立复杂函数或者未建立复杂函数或者未知函数的一个便于计算的近似表达式知函数的一个便于计算的近似表达式.v解决方法解决方法插值法插值法 1.1.插值概念插值概念求求插值函数插值函数(x)的问题的问题(方法方法)称为称为插值问题插值问题(方法方法)。2.2.几何意义、内插法、外插法几何意义、内插法、外插法内插外插2 拉格朗日多项式拉格朗日多项式 /*Lagrange Polynomial*/niyxPiin,.,0,)(=求求 n 次多项式次多项式 使得使得条件：无重合节点，即条件：无重合节点，即l0(x)l1(x)2 Lagrange Polynomial多项式插值是数值分析的基本工具，常用来计算被插函数多项式插值是数值分析的基本工具，常用来计算被插函数的近似的近似函数值函数值，零、极点零、极点，导数、积分导数、积分（第四章（第四章 数值积数值积分和数值微分），分和数值微分），解微分方程解微分方程（第五章）、（第五章）、积分方程积分方程x0 x1x2x3x4xPn(x)f(x)解 几何上看，即求几何上看，即求多项式曲线多项式曲线与与被插值函数曲线被插值函数曲线间满足：间满足：特点：插值曲线插值曲线Pn(x)过被插值曲线过被插值曲线f(x)的上给定的的上给定的n+1个点。个点。n=1已知已知 x0,x1;y0,y1，求求使得使得111001)(,)(yxPyxP=可见可见 P1(x)是过是过(x0,y0)和和(x1,y1)两点的直线。两点的直线。)()(0010101xxxxyyyxP +=101xxxx 010 xxxx =y0+y1l0(x)l1(x)=10)(iiiyxl称为拉氏基函数称为拉氏基函数 满足条件满足条件 li(xj)=ij 2 Lagrange Polynomial 提问：上面所提的多项式提问：上面所提的多项式Pn(x)是否存在？是否存在？若存在，是否唯一？如何求？若存在，是否唯一？如何求？证明证明 插值条件插值条件(2.2)(2.2)等价于线性方程组等价于线性方程组定理定理1 1 满足插值条件满足插值条件(2.2)(2.2)的的不超过不超过n次的插值次的插值多项式多项式唯一存在。唯一存在。系数行列式（系数行列式（n+1+1阶范德蒙行列式）阶范德蒙行列式）由克莱默法则知，方程组有唯一解由克莱默法则知，方程组有唯一解2-1 插值多项式的存在唯一性插值多项式的存在唯一性 唯一性的另一证明唯一性的另一证明 满足满足 的的 n 阶插值多项阶插值多项式是唯一存在的。式是唯一存在的。证明证明 (前面已利用前面已利用Vandermonde 行列式论证行列式论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x)外还有另一外还有另一 n 阶多项阶多项式式 Pn(x)满足满足 Pn(xi)=yi。考察考察 则则 Qn 的阶数的阶数 n而而 Qn 有有 个不同的根个不同的根n+1x0 xn注：若不将多项式次数限制为注：若不将多项式次数限制为 n，则插值多项式不唯一。则插值多项式不唯一。例如例如 也是一个插值多项式，也是一个插值多项式，其中其中 可以是任意多项式。可以是任意多项式。2 Lagrange PolynomialInterpolation polynomial 2-2 线性插值与抛物插值线性插值与抛物插值 x0 x1(x0,y0)(x1,y1)P1(x)f(x)可见可见 P1(x)是过是过(x0,y0)和和(x1,y1)两点的直线。两点的直线。直线直线方程为方程为:等价变形为等价变形为:记为记为:1.线性插值线性插值引入记号引入记号:则则:分析两个基函数有分析两个基函数有:对于三个点对于三个点,类似有类似有:称为插值基函数称为插值基函数x0 x1x2P2(x)f(x)f(x)2.抛物线抛物线(二次二次)插值插值 将以上思路推广到将以上思路推广到n+1个节点情形，即可得到类似的个节点情形，即可得到类似的插值基函数和插值多项式表示形式。插值基函数和插值多项式表示形式。P2(x)xn 1希望找到希望找到li(x)，i=0,n 使得使得 li(xj)=ij；然后然后令令，则显然有，则显然有Pn(xi)=yi。li(x)每个每个 li 有有 n 个根个根 x0 xi xn=jiC0=nj i jxx)(inxxixxxxC0).().(ixl)(=j i jxixiC)(1=iixl1)(Lagrange Polynomial与节点有关，而与与节点有关，而与 f无关无关=niinxlxP0)()(yi 基函数法（基函数法（n=1情形的推广情形的推广）2 Lagrange Polynomial2-3 Lagrange插值多项式插值多项式 2-4 插插值余值余项项/*Remainder*/设节点设节点在在a,b内存在内存在,考察截断误差考察截断误差，且，且 f 满足条件满足条件 ,Rolles Theorem:若若 充分光滑，充分光滑，则，则存在存在 使得使得 。推广：推广：若若使得使得使得使得存在存在使得使得Rn(x)至少有至少有 个根个根n+1=niinxxxKxR0)()()(任意固定任意固定 x xi (i=0,n),考察考察=niixtxKtRnt0)()()()(x)有有 n+2 个不同的根个不同的根 x0 xn x!)1()()()1(+-+nxKRxnn 注意这里是对注意这里是对 t 求导求导=+!)1)()()()1()1(nxKLfxnnxn !)1()()()1(+=+nfxKxn 2 Lagrange Polynomial1 Lagrange Polynomial注：注：通常不能确定通常不能确定 x,而是估计而是估计 ,x(a,b)将将 作为误差估计上限。作为误差估计上限。当当 f(x)为任一个次数为任一个次数 n 的的多项式多项式时，时，,可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项式是多项式是精确精确的。的。Quiz:给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 l2(x)的图像？的图像？y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x ABC 1 Lagrange Polynomial例：例：已知已知分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。解：解：n=1分别利用分别利用x0,x1 以及以及 x1,x2 计算计算利用利用这里这里而而sin 50 =0.7660444)185(50sin10 p pL0.77614外外推推/*extrapolation*/的实际误差的实际误差 0.010010.01001利用利用sin 50 0.76008,内插内插/*interpolation*/的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。1 Lagrange Polynomialn=2)185(50sin20 p pL0.76543sin 50 =0.76604442次次插值的实际误差插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但但绝对不是次数越绝对不是次数越高就越好，嘿嘿高就越好，嘿嘿 When you start writing the program,you will find how easy it is to calculate the Lagrange polynomial.Oh yeah?What if I find the current interpolation not accurate enough?Then you might want to take more interpolating points into account.Right.Then all the Lagrange basis,li(x),will have to be re-calculated.Excellent point!We will come to discuss this problemnext time.1 Lagrange Polynomial练习：练习：设设f(x)=x4,利用利用 Lagrange 插值写出以插值写出以-1,0,1,2为节点为节点 的插值多项式。的插值多项式。练习：练习：已知插值节点满足已知插值节点满足xi-xi-1=h,i=1,2,3,证明三次插值证明三次插值多项式多项式L3(x)与被插函数与被插函数f(x)的差有如下关系：的差有如下关系：1 Lagrange Polynomial练习：练习：证明证明Interpolation_introduction问题的提出：问题的提出：如果需要增加精度，一般采用增加插值节点来实如果需要增加精度，一般采用增加插值节点来实现。但是由于插值基函数的性质，使得计算新的插值现。但是由于插值基函数的性质，使得计算新的插值多项式时，原来的计算量不能很好地利用，造成计算多项式时，原来的计算量不能很好地利用，造成计算的浪费，为了克服这一缺点，我们将要介绍下面的逐的浪费，为了克服这一缺点，我们将要介绍下面的逐步线性插值和步线性插值和Newton插值。插值。3 逐次线性插值逐次线性插值 /*Lagrange Polynomial*/3 逐次线性插值法逐次线性插值法 /*Lagrange Polynomial*/实际上实际上，是对两个低次插值的线性插值，这种通过低次插值再作是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次插值的方法称为线性插值生成高次插值的方法称为逐次线性插值逐次线性插值。Aitken法法(按下表计算按下表计算)线性插值基函数线性插值基函数增加增加如果精度不够，增加节点如果精度不够，增加节点x4,同时表中增加一行，三角同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。形斜边上即为所要求的各次插值多项式。k1k0k2k3k4 Neville法法(按下表计算按下表计算)增加增加如果精度不够，增加节点如果精度不够，增加节点x4,同时表中增加一行，三角形斜边上同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。即为所要求的各次插值多项式。k1k0k1k1k1HW:用用类似于前面的方法类似于前面的方法构造构造Neville计算公式计算公式注：注：Atkin方法和方法和Neville方法与方法与Lagrange公式相比，当公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适当变化。插值公式中，每个基函数都需要作适当变化。误差估计：误差估计：由插值多项式的存在唯一性知，仍有由插值多项式的存在唯一性知，仍有但但这里可采用一种更简便的方法。当这里可采用一种更简便的方法。当f(n+1)(x)在插在插值区间变化不大时，设值区间变化不大时，设f(n+1)(x)L，则有则有根据前面的计算结果估计当前根据前面的计算结果估计当前的误差：事后误差估计（实用）的误差：事后误差估计（实用），前面给出的误差估计（事先，前面给出的误差估计（事先误差估计误差估计）不实用不实用4 牛顿插值牛顿插值 /*Newtons Interpolation*/Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x)都需重新算过。公式不具有继承性，都需重新算过。公式不具有继承性，不利于编程。不利于编程。将将 Ln(x)改写成改写成的形式，希望加一个节点时，的形式，希望加一个节点时，只附加一项只附加一项上去即可。上去即可。?差商差商(亦称均差亦称均差)/*divided difference*/1阶差商阶差商/*the 1st divided difference of f w.r.t.xi and xj*/2阶差商阶差商f(x0)1阶差商的几何阶差商的几何意义：弦截线意义：弦截线的斜率的斜率4 Newtons Interpolation4 Newtons Interpolation11101010111010,.,.,.,.,.,+=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商阶差商：事实上事实上其中其中 Warning:my head is explodingWhat is the point of this formula?差商的值与差商的值与 xi 的顺序无关！的顺序无关！1.1.线性线性：2.2.差商差商可以表示为可以表示为函数值的线性组合函数值的线性组合：3.3.对称性：对称性：由由2 2知知，差商的值与节点的顺序无关！差商的值与节点的顺序无关！4.4.差商的另一种定义：由差商的另一种定义：由2，3及均差定义可得及均差定义可得4 Newtons Interpolation4 Newtons Interpolation 牛顿插值牛顿插值 /*Newtons Interpolation*/Nn(x)n次次多项式，满多项式，满足：足：Nn(xi)=f(xi)Rn(x)插值余项，插值余项，满足满足Rn(xi)=0，i=0,n ai=f x0,xi(1)(2)(n)(n)(n-1)(2)(1)4 Newtons Interpolation注：注：由由唯一性可知唯一性可知 Nn(x)Ln(x)，只是算法不同，表只是算法不同，表达形式不同，故其余项也相同，即达形式不同，故其余项也相同，即 实际计算过程为实际计算过程为f(x0)f(x1)f(x2)f(xn 1)f(xn)f x0,x1f x1,x2 f xn 1,xnf x0,x1,x2 f xn 2,xn 1,xnf x0,xn f(xn+1)f xn,xn+1 f xn 1,xn,xn+1 f x1,xn+1 f x0,xn+1增加增加如果精度不够，增加节点如果精度不够，增加节点xn+1,同时表中增加一行，三角形斜边上同时表中增加一行，三角形斜边上即为所要求的各次项系数。即为所要求的各次项系数。1 Lagrange Polynomial练习：练习：设设f(x)=3x2+5,求求fx0,x1,x2,fx0,x1,x2,x3练习：练习：练习：练习：4 Newtons Interpolation 等距节点公式等距节点公式 /*Formulae with Equal Spacing*/向前差分向前差分 /*forward difference*/iiifff=+1ikikikikffff1111)(+=向后差分向后差分 /*backward difference*/111 =ikikikfffi 1iifff=中心差分中心差分 /*centered difference*/其中其中当当节点节点等距等距分布时分布时:fi=f(xi)差分计算可通过构造差分表得到差分计算可通过构造差分表得到增加增加 差分的重要性质：差分的重要性质：线性：例如线性：例如 各阶差分可用函数值表示：各阶差分可用函数值表示：其中其中/*binomial coefficients*/4 Newtons Interpolation 函数值可用各阶差分表示：函数值可用各阶差分表示：差商与差分的关系差商与差分的关系：若若 f(x)是是 n 次多项式，则次多项式，则 是是 次多项式，次多项式，而而 差分与导数的关系差分与导数的关系(由差分与差商、差商与导数的关系得由差分与差商、差商与导数的关系得）：）：4 Newtons Interpolation等距节点牛顿公式等距节点牛顿公式 牛顿前差公式牛顿前差公式/*Newtons forward-difference formula*/注：注：一般当一般当 x 靠近靠近 x0 时用前插，靠近时用前插，靠近 xn 时时用后插，故两用后插，故两种公式亦称为种公式亦称为表初公式表初公式和和表末公式表末公式。牛顿后差公式牛顿后差公式/*Newtons forward-difference formula*/例：例：6 埃尔米特插值埃尔米特插值 /*Hermite Interpolation*/不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x)满足满足 (xi)=f(xi),(xi)=f (xi),(mi)(xi)=f(mi)(xi).注：注：n+1 个条件可以确定指数不超过个条件可以确定指数不超过n次的多项式。次的多项式。要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式其余其余项为项为一般只考虑一般只考虑 f 与与f 的值。的值。埃尔米特插值埃尔米特插值3 Hermite Interpolation例：例：设设 x0 x1 x2,已知已知 f(x0)、f(x1)、f(x2)和和 f(x1),求多项式求多项式 P(x)满足满足 P(xi)=f(xi)，i=0,1,2，且且 P(x1)=f(x1),并估计误并估计误差。差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶的阶数数=3+=213)()()()()(=0iiixhx1f xhxfxP h0(x)有根有根x1,x2，且且 h0(x1)=0 x1 是重根。是重根。)()()(22100 xxxxCxh =又又:h0(x0)=1 C0 h2(x)h1(x)有根有根 x0,x2 )()()(201xxxxBAxxh +=由余下条件由余下条件 h1(x1)=1 和和 h1(x1)=0 可可解。解。与与h0(x)完全类似。完全类似。(x)h1有根有根 x0,x1,x2 h1)()()(2101xxxxxxCx =h1又又:(x1)=1 C1 可解。可解。其中其中 hi(xj)=ij,hi(x1)=0,(xi)=0,(x1)=1 h1 h1与与 Lagrange 分析完全类分析完全类似似3 Hermite Interpolation一般地，已知一般地，已知 x0,xn 处有处有 y0,yn 和和 y0,yn，求求 H2n+1(x)满足满足 H2n+1(xi)=yi，H2n+1(xi)=yi。解：解：设设+=ni)()()(=0iixxyixH2n+1n=0iyi其中其中 i(xj)=ij,i(xj)=0,(xj)=0,(xj)=ij ii(x)有根有根 x0,xi,xn且都是且都是2重根重根 由余下条件由余下条件 i(xi)=1 和和 i(xi)=0 可解可解Ai 和和 Bi (x)i 有根有根 x0,xn,除了除了xi 外都是外都是2重根重根 i)()(iili2(x)xxCx=又又 i (xi)=1 Ci=1i)(x)(ili2(x)xx=这样的这样的Hermite 插值唯插值唯一一i)()()(2xlBxAxiii+=in+1次次所以所以类似有：类似有：,则则证明略证明略.3 Hermite InterpolationQuiz:给定给定 xi=i+1,i=0,1,2,3,4,5.下面哪个是下面哪个是 i(x)的图像的图像？x0-10.5123456yxy0-10.5123456斜率斜率=1 求求Hermite多项式的基本步骤：多项式的基本步骤：写出相应于条件的写出相应于条件的i(x)、i(x)的组合形式；的组合形式；对每一个对每一个i(x)、i(x)找出尽可能多的条件给出的根；找出尽可能多的条件给出的根；根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式；根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数；最后完整写出最后完整写出H2n+1(x)。注：待定系数法仍适用，但插值节点多注：待定系数法仍适用，但插值节点多时比较麻烦。时比较麻烦。1 1分析分析（方法（方法1 1）：）：误差：误差：#例例 2 2:建立插值多项式建立插值多项式)(3xH,使之满足插值条件使之满足插值条件 =)()(2,1,0)()(0033xfxHixfxHii.方法方法2 2：（用带有重节点的差商表：（用带有重节点的差商表）#7 分段低次插值分段低次插值 /*piecewise polynomial approximation*/为了保证插值函数的逼近效果，需要较多的插值节，为了保证插值函数的逼近效果，需要较多的插值节，导致较高的多项式次数。导致较高的多项式次数。然而在实际应用中然而在实际应用中,很少采用高次插值很少采用高次插值:在两相邻插值节点间在两相邻插值节点间,插值函数未必能够很好地近似插值函数未必能够很好地近似被插值函数被插值函数;对于等距节点的牛顿插值公式对于等距节点的牛顿插值公式,函数值的微小扰动可函数值的微小扰动可能引起高阶差分有很大的变化。能引起高阶差分有很大的变化。7-1 多项式插值的问题多项式插值的问题Remember what I have said?Increasing the degree of interpolating polynomial will NOT guarantee a good result,since high-degree polynomials are oscillating.例：例：在在 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)分段分段低次低次插值插值 分别采用分别采用1010次、次、1515次、次、2020次的等距节点插值多项式。随次的等距节点插值多项式。随着插值次数的提高着插值次数的提高,在在 范围内的近似程度并没有变范围内的近似程度并没有变好好,反而变坏反而变坏.高次插值并不一定带来更好的近似效果。高次插值并不一定带来更好的近似效果。4 Piecewise Polynomial Approximation7-2 分段线性插值分段线性插值 /*piecewise linear interpolation*/在每个区间在每个区间 上，用上，用1阶多项式阶多项式(直线直线)逼近逼近 f(x):记记 ，易证：当，易证：当 时，时，一致一致失去了原函数的光滑性失去了原函数的光滑性。分段分段Hermite插值插值 /*Hermite piecewise polynomials*/给定给定在在 上利用两点的上利用两点的 y 及及 y 构造构造3次次Hermite函数函数导数一般不易得到。导数一般不易得到。How can we make a smooth interpolation without asking too much from f?Headache 7-3 分段三次分段三次Hermite插值插值 /*Hermite piecewise polynomials*/8 三次样条三次样条 /*Cubic Spline*/分段插值法具有一致的收敛性分段插值法具有一致的收敛性,但它只保证插值函数整但它只保证插值函数整体的连续性体的连续性,但在连接处不一定光滑，不能够满足精密机械但在连接处不一定光滑，不能够满足精密机械设计（如船体、飞机、汽车等的外形曲线设计）对函数光滑设计（如船体、飞机、汽车等的外形曲线设计）对函数光滑性的要求。性的要求。早期的工程技术人员在绘制给定点的曲线时，使用一种早期的工程技术人员在绘制给定点的曲线时，使用一种具有弹性的细长木条（或金属条），称之为具有弹性的细长木条（或金属条），称之为样条（样条（SplineSpline），），强迫它弯曲通过已知点。弹性力学理论指出样条的挠度曲线强迫它弯曲通过已知点。弹性力学理论指出样条的挠度曲线具有二阶连续的导函数，并且在相邻给定点之间为三次多项具有二阶连续的导函数，并且在相邻给定点之间为三次多项式，即为数学上的式，即为数学上的三次样条插值曲线三次样条插值曲线。设设 。三次样条函数三次样条函数 ,且且在在每每个个 上上为为三三次次多多项项式式/*cubic polynomial*/。若若它它同同时时还还满满足足 ，则则称称为为 f 的的三三次次样样条条插插值值函函数数/*cubic spline interpolant*/.注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在2个端点可能需要）个端点可能需要）；而；而Hermite插值依赖于插值依赖于f 在所有插值点的导数值。在所有插值点的导数值。f(x)H(x)S(x)三次样条插值函数三次样条插值函数 在每一个小区间上是在每一个小区间上是3次次的多项式的多项式,在整个插值区间上有在整个插值区间上有4n个系数个系数.且且有有4 4n-2-2个约束个约束:内节点内节点 边界节点边界节点 要要确确定定4 4n n个个系系数数，还还需需附附加加2 2个个约约束束条条件件.常常用的约束条件有以下三类：用的约束条件有以下三类：此时一般有此时一般有 成立成立.周期性边界条件周期性边界条件 ,.弯矩边界条件 特别的称 为自然边界条件.转角边界条件转角边界条件 构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/构造三次样条插值函数的构造三次样条插值函数的三转角方程三转角方程 /*method of bending moment*/5 Cubic Spline 构造三次样条插值函数的构造三次样条插值函数的三弯矩法三弯矩法 /*method of bending moment*/在在 上，记上，记,for )()(1jjjxxxxSxS =对每个对每个j,此为此为3次多项式次多项式则则 Sj”(x)为为 次多项式，需次多项式，需 个点的值确定之。个点的值确定之。12设设 Sj”(xj 1)=Mj 1，Sj”(xj)=Mj 对应力学中的对应力学中的梁弯矩梁弯矩，故名，故名对于对于x xj 1,xj 可可得到得到Sj”(x)=jjjjjjhxxMhxxM11 +积分积分2次，可得次，可得 Sj(x)和和 Sj(x)：jjjjjjjAhxxMhxxM+2)(2)(21121Sj(x)=jjjjjjjjBxAhxxMhxxM+6)(6)(3131Sj(x)=利用已知利用已知Sj(xj 1)=yj 1 Sj(xj)=yj 可解可解5 Cubic SplinejjjjjjjhMMhyyA611 =jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6(+=+下面解决下面解决 Mj：利用利用S 在在 xj 的的连续性连续性xj 1,xj:Sj(x)=jjjjjjjjjjjhMMxxfhxxMhxxM6,2)(2)(112121 +1111211216,2)(2)(+jjjjjjjjjjjhMMxxfhxxMhxxMxj,xj+1:Sj+1(x)=利用利用Sj(xj)=Sj+1(xj)，合并关于合并关于Mj 1、Mj、Mj+1的同类的同类项，并记项，并记 ,整理后得整理后得到：到：11jjjjhhh+=1jj-=),(6111jjjjjjjxxfxxfhhg-+-+=211gMMMjjjjjj=+-j 1n 1即：有即：有 个未知数，个未知数，个方程。个方程。n 1n+1还需还需2个个边界条件边界条件/*boundary conditions*/5 Cubic Spline 第第1类边条件类边条件/*clamped boundary*/：S(a)=y0，S(b)=yna,x1:S1(x)=1011012112106,2)(2)(hMMxxfhaxMhxxM +010110),(62gy0 xxfhMM=+nnnnnngxxfynhMM=+),(6211类似地利用类似地利用 xn 1,b 上的上的 Sn(x)第第2类边条件：类边条件：S”(a)=y0”=M0，S”(b)=yn”=Mn这时：这时：特别地，特别地，M0=Mn=0 称为称为自由边界自由边界/*free boundary*/，对应的对应的样条函数称为样条函数称为自然样条自然样条/*Natural Spline*/。第第3类边条件类边条件/*periodic boundary*/：当当 f 为为周期函数周期函数时，时，yn=y0，S(a+)=S(b)M0=Mn 5 Cubic Spline注：注：另有另有三转角法三转角法(p.49-53)得到样条函数，即设得到样条函数，即设 Sj(xj)=mj，则易知，则易知xj 1,xj 上的上的Sj(x)就是就是Hermite函数函数。再利用。再利用S”的连续性，可导出关于的连续性，可导出关于mj 的的方程组，方程组，加上边界条件即可解。加上边界条件即可解。Cubic Spline 由由boundary conditions 唯一唯一确定。确定。收敛性：收敛性：若若 ，且，且 ，则，则一致一致S(x)f(x)即即:提高精度只须提高精度只须增加节点增加节点,而无须提高样条阶数。而无须提高样条阶数。稳定性：稳定性：只要边条件保证只要边条件保证|0|,|0|,|n|,|n|2，则方程组系数阵为则方程组系数阵为SDD阵阵，保证数值稳定。保证数值稳定。例 给定数据如下 ：5 Cubic Spline Sketch of the Algorithm:Cubic Spline 计算计算 j,j,gj;计算计算 Mj (追赶法等追赶法等);找到找到 x 所在区间所在区间(即找到相应的即找到相应的 j);由该区间上的由该区间上的 Sj(x)算出算出 f(x)的近似值。的近似值。插值法小结插值法小结 Lagrange:给出给出 y0 yn，选基函数选基函数 li(x)，其次数为其次数为 节点数节点数 1。Newton Ln(x)，只是形式不同；节点等距或渐增节点只是形式不同；节点等距或渐增节点时方便处理。时方便处理。Hermite：给出给出 yi 及及 yi，选选 i(x)及及 i(x)。Spline：分段低次分段低次,自身光滑自身光滑,f 的导数只在边界给出。的导数只在边界给出。后面为链接