南大数值分析课件3厄米插值课件.ppt

§3  厄米插值厄米插值  /* Hermite Interpolation */不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合即：要求插值函数即：要求插值函数   (x) 满足满足  (xi) = f (xi),  ’ (xi) = f ’ (xi),…,  (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定           阶多项式阶多项式N   1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式其余项为其余项为一般只考虑一般只考虑 f 与与f ’的值南大数值分析课件§3厄米插值§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 是重根)()()(22100xxxxCxh  = =又又:  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厄米插值§3  Hermite Interpolation例例1 南大数值分析课件§3厄米插值§3  Hermite Interpolation一般地，已知一般地，已知 x0 , …, xn 处有处有 y0 , …, yn 和和 y0’ , …, yn’ ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ，， H’2n+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 插值唯插值唯一一南大数值分析课件§3厄米插值§3  Hermite Interpolation例例2 南大数值分析课件§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)。

HW: p.120-121#21，，#22，，#23南大数值分析课件§3厄米插值§4  分段低次插值分段低次插值  /* piecewise polynomial approximation */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) 分段分段低次低次插值插值南大数值分析课件§3厄米插值§4  Piecewise Polynomial Approximation  分段线性插值分段线性插值 /* 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 …南大数值分析课件§3厄米插值§5  三次样条三次样条  /* Cubic Spline */　　　　　　设设                                     三三次次样样条条函函数数                        , 且且在在每每个个          上上为为三三次次多多项项式式 /* cubic polynomial */若若它它同同时时还还满满足足                                     ，，则则称称为为 f 的的三三次次样样条条插插值函数值函数 /* cubic spline interpolant */.注：注：三次样条与分段三次样条与分段 Hermite 插值的根本区别在于插值的根本区别在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的导数值（除了在的导数值（除了在2个端点可能需要）个端点可能需要）；而；而Hermite插值依赖于插值依赖于f 在所有插值点的导数值。

在所有插值点的导数值f(x)H(x)S(x)南大数值分析课件§3厄米插值§5  Cubic  Spline  构造三次样条插值函数的构造三次样条插值函数的三弯矩法三弯矩法 /* method of bending moment */在在               上，记上，记],[for   )()(1][jjjxxxxSxS  = =对每个对每个j, 此为此为3次多项式次多项式则则 S[j]”(x) 为为    次多项式，需次多项式，需     个点的值确定之个点的值确定之12设设 S[j]”(xj 1) = Mj 1，， S[j]”(xj) = Mj 对应力学中的对应力学中的梁弯矩梁弯矩，故名，故名对于对于x  [xj 1,  xj ] 可可得到得到S[j]”(x) =jjjjjjhxxMhxxM11   + + 积分积分2次，可得次，可得 S[j]’(x) 和和 S[j](x) ：：jjjjjjjAhxxMhxxM+ + + +     2)(2)(21121S[j]’(x) =jjjjjjjjBxAhxxMhxxM+ ++ + + +   6)(6)(3131S[j](x) =利用已知利用已知S[j](xj 1) = yj 1 S[j](xj) = yj 可解可解南大数值分析课件§3厄米插值§5  Cubic  SplinejjjjjjjhMMhyyA611     = =jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6(     + +  = =+ +下面解决下面解决 Mj ：： 利用利用S’ 在在 xj 的的连续性连续性[xj 1,  xj ]: S[j]’(x) =jjjjjjjjjjjhMMxxfhxxMhxxM6],[2)(2)(112121      + + + +  1111211216],[2)(2)(+ ++ ++ ++ ++ ++ ++ +  + + + +  jjjjjjjjjjjhMMxxfhxxMhxxM[xj ,  xj+1]: S[j+1]’(x) =利用利用S[j]’(xj) = S[j+1]’(xj)，合并关于，合并关于Mj 1、、 Mj、、 Mj+1的同类的同类项，并记项，并记                     ,                ,                                                    , 整理后得到：整理后得到：11jjjjhhh+++= 1jj-=  ]),[],[(6111jjjjjjjxxfxxfhhg-++-+=211gMMMjjjjjj=+++-    j  1n 1即：有即：有      个未知数，个未知数，     个方程。

个方程n 1n+1还需还需2个个边界条件边界条件 /* boundary conditions */南大数值分析课件§3厄米插值§5  Cubic  Spline 第第1类边条件类边条件 /* clamped boundary */：： S’(a) = y0’，， S’(b) = yn’[a ,  x1 ]: S[1]’(x) =1011012112106],[2)(2)(hMMxxfhaxMhxxM  + + + +  010110)],[(62gy0’xxfhMM= = = =+ +nnnnnngxxfyn’hMM= = = =+ +  ]),[(6211类似地利用类似地利用[ xn 1,  b ] 上的上的 S[n]’(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 南大数值分析课件§3厄米插值§5  Cubic  Spline注：注：另有另有三转角法三转角法得到样条函数，即设得到样条函数，即设 S[j]’(xj) = mj，，则易知则易知[xj 1,  xj ]上的上的S[j](x) 就是就是Hermite函数函数再利用用S”的连续性，可导出关于的连续性，可导出关于mj 的方程组，加上边界的方程组，加上边界条件即可解条件即可解Cubic Spline 由由boundary conditions 唯一唯一确定收敛性：收敛性：若若                  ，且，且                       ，则，则一致一致S(x)  f(x)即即:提高精度只须提高精度只须增加节点增加节点, 而无须提高样条阶数而无须提高样条阶数稳定性：稳定性：只要边条件保证只要边条件保证 |  0 |, |  0 |, |  n |, |   n | < 2，，则方程组系数阵为则方程组系数阵为SDD阵阵，，保证数值稳定。

保证数值稳定HW:  p.204  #24  #25南大数值分析课件§3厄米插值§5  Cubic  Spline Sketch of the Algorithm: Cubic Spline    ①①  计算计算  j ,    j ,  gj ;              ②②  计算计算 Mj (追赶法等追赶法等) ;    ③③ 找到找到 x 所在区间所在区间 ( 即找到相应的即找到相应的 j ) ;    ④④ 由该区间上的由该区间上的 S[j](x) 算出算出 f(x) 的近似值的近似值插值法小结插值法小结  Lagrange : 给出给出 y0 … yn，选基函数，选基函数 li(x)，其次数为，其次数为                       节点数节点数 –1  Newton   Ln(x)，，只是形式不同；节点等距或渐增节点只是形式不同；节点等距或渐增节点时方便处理时方便处理  Hermite：：  给出给出 yi 及及 yi ’，选，选 hi(x) 及及 hi(x)   Spline：分段低次：分段低次, 自身光滑自身光滑, f 的导数只在边界给出。

的导数只在边界给出 南大数值分析课件§3厄米插值§5  Cubic  SplineLab 11. Cubic Spline        Construct the cubic spline interpolant S for the function f, defined at points                        , satisfying some given boundary conditions.  Partition an given interval into m equal-length subintervals, and approximate the function values at the endpoints of these subintervals. InputThere are several sets of inputs.  For each set:The 1st line contains an integer 20   n   0  which is the number of interpolating points   1.   n =  1 signals the end of file.The 2nd line contains n+1 distinct real numbers                        .The 3rd line contains n+1 real numbers                                        .The 4th line contains an integer Type and three real numbers s0 , sn, and Fmax.   If Type = 1, the clamped boundary condition is given:                  and                 .  If Type = 2, the natural boundary condition is given:                    and                   .  No other values of Type will be given. Fmax is the default value that S (x) will assume if x is out of the range [x0, xn].The last line of a test case consists of two real numbers t0 and tm, and an integer m   1.  Here the interval            is partitioned into m equal-lengh subintervals,  …               .    The numbers are separated by spaces and new lines. 南大数值分析课件§3厄米插值§5  Cubic  SplineOutput ( ( represents a space) represents a space)For each test case, you are supposed to output the following information: 1. 1. The set of coefficients of S(x) in the format:                                 where                                  for                         .       Each coefficient is to be printed as in C printf:                   fprintf(outfile, "%12.8e", coefficient );2. 2. m+1 approximating values of  f  at                 in the format:                 fprintf(outfile, "f(%12.8e)=%12.8e\n", t, S );The outputs of two test cases must be seperated by a blank line. Sample Input Sample Input 20.01.02.00.01.02.011.01.00.00.03.022–0.5–0.250.0–0.02475000.33493751.101000020.00.00.0–1.00.04–1南大数值分析课件§3厄米插值§5  Cubic  SplineSample Output  Sample Output  0.00000000e+0001.00000000e+0000.00000000e+0000.00000000e+0001.00000000e+0001.00000000e+000 0.00000000e+0000.00000000e+000f(0.00000000e+000)=0.00000000e+000f(1.50000000e+000)=1.50000000e+000f(3.00000000e+000)=0.00000000e+000 –2.47500000e–0021.03237500e+0000.00000000e+0006.50200000e+0003.34937500e–0012.25150000e+0004.87650000e+000–6.50200000e+000f(–1.00000000e+000)=0.00000000e+000f(–7.50000000e–001)=0.00000000e+000f(–5.00000000e–001)=–2.47500000e–002f(–2.50000000e–001)=3.34937500e–001f(0.00000000e+000)=1.10100000e+000南大数值分析课件§3厄米插值。