第六章(曲线插值)

1、23曲线的参数方程为曲线的参数方程为)()()(tzztyytxx归一化归一化处理：为了方便起见，可以将参数t的范围区间规范化成0，1。 参数化表示比显式、隐式有更多的优点！参数化表示比显式、隐式有更多的优点！参数化表示方式易于用矢量和矩阵运算，对曲率、参数化表示方式易于用矢量和矩阵运算，对曲率、斜率等的计算也有别于传统方式。斜率等的计算也有别于传统方式。4x0 x0yy1y1nyny1x1nxnx( )yf x56（1）拉格朗日插值（）拉格朗日插值（lagrange插值）插值）（2）Hermite插值插值7使使Pn(x) 满足条件满足条件2012( )nnnP xaa xa xa x( ),

2、0, 1,niiP xyin8插值多项式的几何意义实质上是将通过插值多项式的几何意义实质上是将通过n+1个点个点(xi,yi),i=0,1,2,n的多项式曲线当作被插函数曲线的多项式曲线当作被插函数曲线y=f(x)的近似曲线。的近似曲线。9设所要构造的插值多项式为：设所要构造的插值多项式为： nnnxaxaxaaxP 2210)(由插值条件由插值条件 niyxPiin, 1, 0)( 得到如下线性代数方程组：得到如下线性代数方程组： nnnnnnnnnyaxaxayaxaxayaxaxa10111100010011110此方程组的系数行列式为此方程组的系数行列式为 nijjixx0)(上式即为

3、范得蒙行列式，由于插值结点上式即为范得蒙行列式，由于插值结点xi互不相同，互不相同，故故D 0 ，则，则Pn(x)可由可由a0, a1, an唯一确定。唯一确定。nnnnnnxxxxxxxxxD212110200111 1112构造各个插值节点上的基函数构造各个插值节点上的基函数 满足如下条件满足如下条件0 xix1x2xnx0( )lx1( )l xn( )lx13求求n次多项式次多项式 k = 0, 1, n ikikxlik, 0, 1)(iinkkkinyxlyxP )()(1则则 i = 0, 1, 2, n即即 Pn(x) 满足插值条件满足插值条件 14knknkjjjkjknkk

4、nyxxxxyxlxP 000)()()()()()()()()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxl nkjjjkjxxxx0从而得从而得n 阶拉格朗日（阶拉格朗日（Lagrange）插值公式：）插值公式：根据根据lk(x) 的表达式，的表达式，xk 以外所有的结点都是以外所有的结点都是lk(x)的根的根15特别地，当特别地，当n=1时，为线性插值：时，为线性插值：则有：则有：1001( )xxlxxx0110( )xxl xxx满足插值条件。满足插值条件。101001011)(yxxxxyxxxxxP16线性插值多项式线性插值多项式 1000

5、110( )yyyyxxp xxxP1(x)可以改写为可以改写为故线性插值多项式的几故线性插值多项式的几何含义就是构造过插值何含义就是构造过插值节点的一条线段节点的一条线段17当当n=2时，为抛物线插值：时，为抛物线插值：则有：则有：满足插值条件。满足插值条件。2211002)()()()(yxlyxlyxlxP1200102()()( )()()xxxxlxxxxx0211012()()( )()()xxxxl xxxxx0122021()()( )()()xxxxlxxxxx18抛物线插值多项式抛物线插值多项式 抛物线插值多项式的几抛物线插值多项式的几何含义就是从几何上看何含义就是从几何上

6、看就是用通过三点抛物线就是用通过三点抛物线函数函数P2(x)近似代替原始近似代替原始被插函数被插函数f(x)。 P2(x)19在实际应用中，不仅要求插值函数与被插函数在节在实际应用中，不仅要求插值函数与被插函数在节点上点上函数值函数值相等，而且要求若干阶相等，而且要求若干阶导数导数也相等，如也相等，如机翼设计等。机翼设计等。( )( )f xx （i = 0, 1, , n）()()iixf x ()()iixfx (2)(2)()()iixfx ()()()()mmiixfx 满足满足函数值函数值相等且相等且导数导数也相等的插值方法称为埃尔米也相等的插值方法称为埃尔米特（特（HermiteH

7、ermite插值）插值）20一般来说，给定一般来说，给定 m+1 个插值条件，就可以构造出一个插值条件，就可以构造出一个个 m 次次 Hermite 插值多项式插值多项式 n 两个典型的两个典型的 Hermite 插值插值l 三点三次三点三次 Hermite 插值插值l 两点三次两点三次 Hermite 插值插值插值节点：插值节点： 插值条件：插值条件：插值节点：插值节点：插值条件：插值条件：21插值节点：插值节点： 插值条件：插值条件：两两点三次点三次 Hermite 插值插值模仿模仿 Lagrange 多项式的思想，设多项式的思想，设)()()()()(110011003xbxbxaxax

8、H 其中其中 均为均为 3 次多项式，且满足次多项式，且满足0101( ),( ),( )xxx (), ()0, ()0, ()jijijijijijixxxxi, j= 0, 122将插值条件代入立即可得将插值条件代入立即可得300110011( )( )( )( )( )Hxyxyxmxmx 0(x), 1(x), 0(x), 1(x) 的表达式？的表达式？ 0(x)0101()0, ()0 xx21001( )()xxxaxbxx 00000101()1, ()0, ()0, ()0 xxxx0000()1, ()0 xx010010101322, 1xxxabxxxxxx 23201

9、01001( )12xxxxxxxxx 同理可得同理可得20110110( )12xxxxxxxxx 相类似地，可以推出相类似地，可以推出 210001( )()xxxxxxx 201110( )()xxxxxxx 24满足插值条件满足插值条件P(x0) = f(x0) = y0，P(x0) = f(x0) = m0P(x1) = f(x1) = y1，P(x1) = f(x1) = m1的的三次三次 Hermite 插值多项式为插值多项式为 22001130110010110220100110110( )1212 xxxxxxxxHxyyxxxxxxxxxxxxmxxmxxxxxx 25 0

10、 0阶导数连续性阶导数连续性，记作C C0 0连续连续，是指两个曲线段在公共点处有相同的坐标。 一阶导数连续性一阶导数连续性，记作C C1 1连续连续，指两个相邻曲线段在交点处有相同的一阶导数。 二阶导数连续性二阶导数连续性，记作C C2 2连续连续，指两个相邻曲线段在交点处有相同的一阶和二阶导数。 0 0阶几何连续性阶几何连续性，记为G G0 0连续连续，与0阶导数连续性相同。 一阶几何连续性一阶几何连续性，记为G G1 1连续连续，指一阶导数在两个相邻段的交点处成比例，而大小不一定相等。 二阶几何连续性二阶几何连续性，记为G G2 2连续，指两个曲线段在相交处其一阶和二阶导数均成比例。G2

11、连续下，两个曲线段在交点处的曲率相等。26p三点光滑法p五点光滑法p三次样条光滑法27五点光滑法是等高线光滑中最常使用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：p每两个数据点之间建立一条三次多项式曲线方程。p曲线具有连续的一阶导数。p 各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。28五点光滑法各数据点的一阶导数是由其他相邻四个点求得的。图中P1点的一阶导数待求，设其值为t112343122341kkkkkkkkkktK1，K2，K3，K4分别为四个折线段Pi-2Pi-1，Pi-2Pi-1, Pi-2Pi-1,Pi+1Pi+2的斜率。29当等高线不

12、闭合，对于第一个点和第二个点以及倒数第二个点及第一个点，采用补点的方法求一阶导数，补点采用增量相等的原则来补： 当欲求P1点一阶导数时，需要向前补充A点。其补充原则为：P2P1坐标增量-P1P0坐标增量= P1P0坐标增量-P0A坐标增量，由此可以补出A点坐标。30设每两个数据点的三次多项式为： 由此可以对每一个原始等高线的折线段求出一组a,b,c,d四个参数，构建一个三次多项式，实现光滑。dcxbxaxy23插值条件为： 1111)()()()(iiiiiiiitxytxyxfyxfy31五点光滑法是等高线光滑中最常使用的方法，其光滑的结果类似于制图员的手工光滑效果。基本思路为：p每两个数据

13、点之间建立一条三次多项式曲线方程。p曲线具有连续的一阶导数。p 各数据点的导数是以一点为中心，左右两边各相邻的两个点，一共五个点来确定的。32能否找到一个简单易算的能否找到一个简单易算的 p(x) ，使得，使得 f(x) p(x)已知已知 f(x) 在某些点的函数值：在某些点的函数值：但是但是(1) m 通常很大通常很大 (2) yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f (xi) 这时不要求这时不要求 p(xi) = yi , 而只要而只要 p(xi) yi 总体上尽可能小总体上尽可能小 33l 使使 最小最小 p(xi) yi 总体上尽可能小总体上尽可能小 l 使使

14、最小最小|)(|max1iimiyxpmiiiyxp1|)(|q 常见做法常见做法太复杂太复杂 不可导，求不可导，求解困难解困难 l 使使 最小最小miiiyxp12|)(|最小二乘法：最小二乘法：目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法3401( )mmmP xaa xa x对于给定的一组数据对于给定的一组数据(xi,yi)(i=0,1,2,.,n)求求m(mm(m=n)=n)次多项式来拟合原始函数次多项式来拟合原始函数( )yf x需要求出多项式的需要求出多项式的m+1m+1个待定系数即可，且使得个待定系数即可，且使得以下函数值达到最小以下函数值达到最小ni 12 21ni

15、imixPyF(a0，a1，am)=Minmkkkxa035要使函数值达到最小，即有多元函数求极值jaF 022001jinimkkikijiniimixxayxxPynijiinijkimokkxyxa11即k = 0, 1, , n最小值点最小值点0jFa 3611102111111121111nnnmiiiiiinnnnmiiiiiiiiimnnnnmmmmiiiiiiiiinxxyaxxxax yaxxxx y写成方程组的形式 法方程组法方程组可以证明该方程组有唯一解37pBezier曲线pB样条曲线38394041Bezier曲线实际上是曲线实际上是B样条样条(Basic Splin

16、e）曲线的特曲线的特例。例。B样条曲线除保持了样条曲线除保持了Bezier曲线的直观性和凸包曲线的直观性和凸包性等优点之外，其样条函数中多项式次数也独立于性等优点之外，其样条函数中多项式次数也独立于控制点数目，控制点数目，B样条曲线还允许局部调整。由于以样条曲线还允许局部调整。由于以上原因，上原因，B样条曲线得到了广泛应用。样条曲线得到了广泛应用。4243P0P2P1MP(0)P(0)P0P2MP1P(0)44P0P3P1P2P(0)M1P(1)M245P0P2P1MP(0)P0P2MP1P(0)P(0)46P2P5P1P0P4P347P2P6P1P0P4P3P5484932333231302322212013121110030201003211YYYaaaaaaaaaaaaaaaaXXXZ三次曲面方程为格网中的p点为待插点，设原始被插函数方程为f(x,y)，令该点所在格网内插函数为三次多项式曲面方程。50y