第六章(曲线插值)

1、1 2 3 曲线的参数方程为曲线的参数方程为 )( )( )( tzz tyy txx 归一化归一化处理：为了方便起见，可以将参数t的范围区 间规范化成0，1。 参数化表示比显式、隐式有更多的优点！参数化表示比显式、隐式有更多的优点！ 参数化表示方式易于用矢量和矩阵运算，对曲率、参数化表示方式易于用矢量和矩阵运算，对曲率、 斜率等的计算也有别于传统方式。斜率等的计算也有别于传统方式。 4 x 0 x 0 yy 1 y 1n y n y 1 x 1n x n x ( )yf x 5 6 （1）拉格朗日插值（）拉格朗日插值（lagrange插值）插值） （2）Hermite插值插值 7 使使Pn(

2、x) 满足条件满足条件 2 012 ( ) n nn P xaa xa xa x ( ),0, 1, nii P xyin 8 插值多项式的几何意义实质上是将通过插值多项式的几何意义实质上是将通过n+1个点个点 (xi,yi),i=0,1,2,n的多项式曲线当作被插函数曲线的多项式曲线当作被插函数曲线 y=f(x)的近似曲线。的近似曲线。 9 设所要构造的插值多项式为：设所要构造的插值多项式为： n nn xaxaxaaxP 2 210 )( 由插值条件由插值条件 niyxP iin , 1, 0)( 得到如下线性代数方程组：得到如下线性代数方程组： nn n nn n n n n yaxax

3、a yaxaxa yaxaxa 10 11110 00100 1 1 1 10 此方程组的系数行列式为此方程组的系数行列式为 nij ji xx 0 )( 上式即为范得蒙行列式，由于插值结点上式即为范得蒙行列式，由于插值结点xi互不相同，互不相同， 故故D 0 ，则，则Pn(x)可由可由a0, a1, an唯一确定。唯一确定。 n nnn n n xxx xxx xxx D 2 1 2 11 0 2 00 1 1 1 11 12 构造各个插值节点上的基函数构造各个插值节点上的基函数 满足如下条件满足如下条件 0 xi x 1 x 2 x n x 0( ) lx 1( ) l x n( ) lx

4、 13 求求n次多项式次多项式 k = 0, 1, n ik ik xl ik , 0 , 1 )( ii n k kkin yxlyxP )()( 1 则则 i = 0, 1, 2, n 即即 Pn(x) 满足插值条件满足插值条件 14 k n k n kj j jk j k n k kn y xx xx yxlxP 000 )()( )()()( )()()( )( 1110 1110 nkkkkkkk nkk k xxxxxxxxxx xxxxxxxxxx xl n kj j jk j xx xx 0 从而得从而得n 阶拉格朗日（阶拉格朗日（Lagrange）插值公式：）插值公式： 根据

5、根据lk(x) 的表达式，的表达式，xk 以外所有的结点都是以外所有的结点都是lk(x) 的根的根 15 特别地，当特别地，当n=1时，为线性插值：时，为线性插值： 则有：则有： 1 0 01 ( ) xx lx xx 0 1 10 ( ) xx l x xx 满足插值条件。满足插值条件。 1 01 0 0 10 1 1 )(y xx xx y xx xx xP 16 线性插值多项式线性插值多项式 10 001 10 ( ) yy yyxxp x xx P1(x)可以改写为可以改写为 故线性插值多项式的几故线性插值多项式的几 何含义就是构造过插值何含义就是构造过插值 节点的一条线段节点的一条线

6、段 17 当当n=2时，为抛物线插值：时，为抛物线插值： 则有：则有： 满足插值条件。满足插值条件。 2211002 )()()()(yxlyxlyxlxP 12 0 0102 ()() ( ) ()() xxxx lx xxxx 02 1 1012 ()() ( ) ()() xxxx l x xxxx 01 2 2021 ()() ( ) ()() xxxx lx xxxx 18 抛物线插值多项式抛物线插值多项式 抛物线插值多项式的几抛物线插值多项式的几 何含义就是从几何上看何含义就是从几何上看 就是用通过三点抛物线就是用通过三点抛物线 函数函数P2(x)近似代替原始近似代替原始 被插函数

7、被插函数f(x)。 P2(x) 19 在实际应用中，不仅要求插值函数与被插函数在节在实际应用中，不仅要求插值函数与被插函数在节 点上点上函数值函数值相等，而且要求若干阶相等，而且要求若干阶导数导数也相等，如也相等，如 机翼设计等。机翼设计等。 ( )( )f xx （i = 0, 1, , n）()() ii xf x ()() ii xfx (2)(2) ()() ii xfx ()() ()() mm ii xfx 满足满足函数值函数值相等且相等且导数导数也相等的插值方法称为埃尔米也相等的插值方法称为埃尔米 特（特（HermiteHermite插值）插值） 20 一般来说，给定一般来说，给

8、定 m+1 个插值条件，就可以构造出一个插值条件，就可以构造出一 个个 m 次次 Hermite 插值多项式插值多项式 n 两个典型的两个典型的 Hermite 插值插值 l 三点三次三点三次 Hermite 插值插值 l 两点三次两点三次 Hermite 插值插值 插值节点：插值节点： 插值条件：插值条件： 插值节点：插值节点： 插值条件：插值条件： 21 插值节点：插值节点： 插值条件：插值条件： 两点三次两点三次 Hermite 插值插值 模仿模仿 Lagrange 多项式的思想，设多项式的思想，设 )()()()()( 110011003 xbxbxaxaxH 其中其中 均为均为 3

9、次多项式，且满足次多项式，且满足 0101 ( ),( ),( )xxx (), ()0, ()0, () jijiji jijiji xx xx i, j= 0, 1 22 将插值条件代入立即可得将插值条件代入立即可得 300110011 ( )( )( )( )( )Hxyxyxmxmx 0(x), 1(x), 0(x), 1(x) 的表达式？的表达式？ 0(x) 0101 ()0, ()0 xx 2 1 0 01 ( )() xx xaxb xx 00000101 ()1, ()0, ()0, ()0 xxxx 0000 ()1, ()0 xx 010 010101 322 , 1 xx

10、x ab xxxxxx 23 2 01 0 1001 ( )12 xxxx x xxxx 同理可得同理可得 2 01 1 0110 ( )12 xxxx x xxxx 相类似地，可以推出相类似地，可以推出 2 1 00 01 ( )() xx xxx xx 2 0 11 10 ( )() xx xxx xx 24 满足插值条件满足插值条件P(x0) = f(x0) = y0，P(x0) = f(x0) = m0 P(x1) = f(x1) = y1，P(x1) = f(x1) = m1 的三次的三次 Hermite 插值多项式为插值多项式为 22 0011 301 10010110 22 01

11、 0011 0110 ( )1212 xxxxxxxx Hxyy xxxxxxxx xxxx mxxmxx xxxx 25 0 0阶导数连续性阶导数连续性，记作C C0 0连续连续，是指两个曲线段在公共 点处有相同的坐标。 一阶导数连续性一阶导数连续性，记作C C1 1连续连续，指两个相邻曲线段在交 点处有相同的一阶导数。 二阶导数连续性二阶导数连续性，记作C C2 2连续连续，指两个相邻曲线段在交 点处有相同的一阶和二阶导数。 0 0阶几何连续性阶几何连续性，记为G G0 0连续连续，与0阶导数连续性相同。 一阶几何连续性一阶几何连续性，记为G G1 1连续连续，指一阶导数在两个相邻 段的交

12、点处成比例，而大小不一定相等。 二阶几何连续性二阶几何连续性，记为G G2 2连续，指两个曲线段在相交处 其一阶和二阶导数均成比例。G2连续下，两个曲线段在交 点处的曲率相等。 26 p三点光滑法 p五点光滑法 p三次样条光滑法 27 五点光滑法是等高线光滑中最常使用的方法，其 光滑的结果类似于制图员的手工光滑效果。基本 思路为： p每两个数据点之间建立一条三次多项式曲线方 程。 p曲线具有连续的一阶导数。 p 各数据点的导数是以一点为中心，左右两边各 相邻的两个点，一共五个点来确定的。 28 五点光滑法各数据点的一阶导数是由其他相邻四个 点求得的。 图中P1点的一阶导数待求， 设其值为t1

13、1234 312234 1 kkkk kkkkkk t K1，K2，K3，K4分别为四 个折线段Pi-2Pi-1，Pi-2Pi-1, Pi-2Pi-1,Pi+1Pi+2的斜率。 29 当等高线不闭合，对于第一个点和第二个点以及倒数第二个 点及第一个点，采用补点的方法求一阶导数，补点采用增量 相等的原则来补： 当欲求P1点一阶导数时，需要向前补充A点。其补充原则为： P2P1坐标增量-P1P0坐标增量= P1P0坐标增量-P0A坐标增量，由 此可以补出A点坐标。 30 设每两个数据点的三次多项式为： 由此可以对每一个原始等高线的折线段求出一组a,b,c,d四个 参数，构建一个三次多项式，实现光滑

14、。 dcxbxaxy 23 插值条件为： 11 11 )( )( )( )( ii ii ii ii txy txy xfy xfy 31 五点光滑法是等高线光滑中最常使用的方法，其 光滑的结果类似于制图员的手工光滑效果。基本 思路为： p每两个数据点之间建立一条三次多项式曲线方 程。 p曲线具有连续的一阶导数。 p 各数据点的导数是以一点为中心，左右两边各 相邻的两个点，一共五个点来确定的。 32 能否找到一个简单易算的能否找到一个简单易算的 p(x) ，使得，使得 f(x) p(x) 已知已知 f(x) 在某些点的函数值：在某些点的函数值： 但是但是 m 通常很大通常很大 yi 本身是测量

15、值，不准确，即本身是测量值，不准确，即 yi f (xi) 这时不要求这时不要求 p(xi) = yi , 而只要而只要 p(xi) yi 总体上尽可能小总体上尽可能小 33 l 使使 最小最小 p(xi) yi 总体上尽可能小总体上尽可能小 l 使使 最小最小 |)(|max 1 ii mi yxp m i ii yxp 1 |)(| q 常见做法常见做法 太复杂太复杂 不可导，求不可导，求 解困难解困难 l 使使 最小最小 m i ii yxp 1 2 |)(| 最小二乘法：最小二乘法：目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法 34 01 ( ) m mm P xaa xa

16、 x 对于给定的一组数据对于给定的一组数据(xi,yi)(i=0,1,2,.,n) 求求m(m=n)m(m=n)次多项式来拟合原始函数次多项式来拟合原始函数 ( )yf x 需要求出多项式的需要求出多项式的m+1m+1个待定系数即可，且使得个待定系数即可，且使得 以下函数值达到最小以下函数值达到最小 n i 1 2 2 1 n i imi xPy F(a0，a1，am)= = =Min m k k k xa 0 35 要使函数值达到最小，即有多元函数求极值 j a F 022 001 j i n i m k k iki j i n i imi xxayxxPy n i j ii n i jk

17、i m ok k xyxa 11 即 k = 0, 1, , n 最小值点最小值点0 j F a 36 111 0 21 1 1111 12 1111 nnn m iii iii nnnn m iiiii iiii m nnnn mmmm iiiii iiii nxxy a xxxax y a xxxx y 写成方程组的形式 法方程组法方程组 可以证明该方程组有唯一解 37 pBezier曲线 pB样条曲线 38 39 40 41 Bezier曲线实际上是曲线实际上是B样条样条(Basic Spline）曲线的特曲线的特 例。例。B样条曲线除保持了样条曲线除保持了Bezier曲线的直观性和凸包

18、曲线的直观性和凸包 性等优点之外，其样条函数中多项式次数也独立于性等优点之外，其样条函数中多项式次数也独立于 控制点数目，控制点数目，B样条曲线还允许局部调整。由于以样条曲线还允许局部调整。由于以 上原因，上原因，B样条曲线得到了广泛应用。样条曲线得到了广泛应用。 42 43 P0P2 P1 M P(0) P(0) P0P2MP1P(0) 44 P0P3P1P2 P(0) M1 P(1) M2 45 P0P2 P1 M P(0) P0 P2 M P1 P(0) P(0) 46 P2 P5 P1 P0 P4 P3 47 P2 P6 P1 P0 P4P3 P5 48 49 3 2 33323130 23222120 13121110 03020100 32 1 1 Y Y Y aaaa aaaa aaaa aaaa XXXZ 三次曲面方程为 格网中的p点为待插点，设原 始被插函数方程为f(x,y)，令 该点所在格网内插函数为三 次多项式曲面方程。 50 yx yxf yx z yx yxf yx z yx yxf yx z yx yxf yx z y yxf y z x yxf x z