样条函数插值

1、样条函数插值 SPLINE INTERPOLATION 信息与数学学院,内容提要 引言 样条函数的物理背景 一般 K 次样条 3次样条插值 高次自然样条与B- 样条基础,4.8 样条函数插值 4.8.1 引言 样条函数的物理背景 回顾前面几节讲过的各种代数插值,它们有一个共同的弱点,那就是: 它们都是相当刚性(stiff)的.也就是说, 局部数据误差易向远处传播、放大.,以Lagrange插值为例,设数据真值 被代之以含有误差 的 , 令 是以 为插值条件的插值多项式,于是最终的插值误差是 由讲义第168页插值公式(6)知,上式右端第二项为 这表明结点 处的数据误差 通过插值基函数 放大和扩散

2、.,更何况,如果被插函数有奇点,甚至只要解析延拓到复平面有隐秘奇点出现, 则当 为高次多项式时,误差放大和扩散 还将助长很可怕 的强振荡! 展示Runge现 象的著名例子就 清楚地描述了这 种振荡(右图).,相同数据3次样条插值与Lagrangr插值效果比较 Cubic Spline Interpolation Lagrangr Interpolation,如果采用分段多项式插值, 则由于插值基函数只是局部活跃(它们的支集是局部紧致的), 结点上的误差可以被控制在小的范围内, 因而也带来了内在的高度稳定性. 这是分段插值的一大优势! 许多实际问题希望插值函数具有较高阶的整体光滑性. 此时, 高

3、次Hermite插值或分段高次Hermite插值可以利用(注意:分段高次Lagrange插值和Newton插值等是做不到的,在插值结点上它们只能保证插值函数连续). 注:函数 的支集 Supp 定义为 Supp,但高次Hermite插值在许多场合中看不中用! 提高Hermite插值多项式的次数就要增加约束条件 给出插值结点处被插函数及其直到足够高阶 导数之值. 作为约束条件的所有数据都是通过观测得到的,而 观测总难免有误差. 于是 高次插值不仅增添了数据准备和计算的困 难,也将导致更大的误差.,还有许多应用不仅要求插值函数具有足够高阶的整体光滑性, 还要求在某些结点处转折灵活. 例如若干点处加

4、载集中力的杆、梁或板弯曲. 这就导致本节要讨论的样条函数(Spline)插值. 数学里的样条( Spline )一词来源于它的直观几何 背景：绘图员或板金工人常用弹性木条或金属条加压铁(构成样条!)来绘制或者放样成光顺曲线或者曲面.但它之所以成为数值分析的标志性成果之一并且在数学物理的广泛领域获得非常成功的应用,还在于它的明确的物理背景.请看下面的例子.,例1.如图4.8.1,一均匀 弹性弦两端固定于两 点 , 在区 间 内取点列 图4.8.1 并在内结点集上分别给集中载荷 则载荷分布 可表为 其中 是集中于结点 的点脉冲函数.,事实上, 在小变形和均匀分布外力假设下,上述弦的平衡问题的微分方

5、程模型乃是两点边值问题 现在是作用离散的集中力,此时弦达到平衡状态时位移函数 应满足,因此有 这意味着: 在每一加载点 处 脉冲间断; 是阶梯函数; 是分段线性的连续函数, 在每一内结点转 折灵活. 后面我们将指出, 如此的 便是一次样条 函数,例2. 考察梁弯曲方程 与例1类似地加载集中力,只是两端点除给零位移 约束外还要加一阶或二阶导数约束.于是集中力作用 下的梁弯曲方程成为 此时我们得到: 图4.8.2, 在内结点 上 脉冲间断; 为阶梯函数; 在每个子区间 上 是三次多项式; 和 都是 上的连续函数. 这便是后面我们要着重讨论的三次样条. 此例展示了三次样条的如下特征: 它分段三次光滑

6、; 整体二次光滑(足够光滑); 在内结点处三阶导数间断(转折灵活).,上面两个例子分别涉及弹性弦和梁的小变形平衡. 这就自然会想到弹性力学中联系平衡态与变形能的两 个重要的极值原理：最小势能原理和虚功原理. 既然 一次和三次样条分别与弦和梁的小变形平衡问题联系 着,那么直觉告诉我们它们也应有相应的极值性质. 后 面我们将证明的确如此! 作为伏笔,我们指出:上两例中弹性弦和梁的变形能 分别表为 和,4.8.2 一般 k 次样条 定义4.8.1( 次样条函数)设 是区间 上的一个分划 或分割，即 称 为定义在区间 上关于分划 的一个 次样条 函数,如果 : 在每一区间 上是次数 不超过 的多项式.

7、 (2)在区间 上是 次连续可微的.,节点 处 的 阶导数间断,因而转折灵活,次样条函数类记为 为方便后面的讨论，我们将样条函数 写成如下形式,例. 根据上述定义,0次样条函数 为分段常数,即阶 梯函数,它可表为 1次样条函数 为分段线性函数,它可表为 一般二次多项式不是严格意义下的二次样条!,4.8.3 3次样条插值 问题的提法：给定数据表 构造3次样条函数 满足插值条件,构造方法： 应具有如下形式 并且满足条件(4.2)和,因 是分段3次多项式 ,故在每个区间 上 都是3次多项式 ,从而 共须 个独立条件确定 . 和 在 个内结点连续,即满足条件(4.4),因而 (4.4)给出了 个条件；

8、 (4.2)提供了 个独立条件; 还差2个条件,有多种给法.最常见的给法是: (i) （简支边界，导致三弯矩关系式, 关系式）, 特别地, (自然边界,三次自然样条); (ii) (固支边界,导致三转角关系式, 关系式).,注意：上述给出的 个条件是问题本身隐含的， 和共 个独立条件须提供，故 结点三次样插值 问题只有 个自由度.(请与分段三次Hermite插值比较!) 三次自然样条插值 关系式的构造方法 记 注意到 于 是连续的 和分段线性的,从而 在每个 上是线性的,故可表 为 对此式积分两次并应用条件(4.2)可得到,微分(4.6)可得到 和 由(4.4)第二式,(4.7)与(4.8)应

9、相等,于是得到,利用条件 得到关于 的线性方程组 其中 解出 代入(4.6)即得到 .,Cubic Spline Interpolation Lagrangr Interpolation,类似地可构造 关系式(留作练习). 下面的两个定理有重要意义. 定理(4.1）设 则 定理(4.2）设 则,我们只证明第二个定理. 证明之前, 先解释它的重要意义. () 前面曾提到,梁弯曲达到平衡态时变形能(内能)可表为 于是(4.11) 意味着: 在满足端点约束 和 以及插值条件 （*） 的一切连续二次可微的函数中，三次自然样条插值函数使得 变形能 达到最小的.,()当 时,注意曲线 的曲率. 而积分 达

10、到最小意味着三次自然样条插值函数是各 种可能的插值函数中使得均方曲率为最小的插值函数,即在一 定意义下最为光顺的插值函数.这是三次自然样条插值函数的 一个非常特别和有用的性质. 下面证明定理 (4.2) 证明 令 ,则 并且 下证,利用分部积分并注意到 以及 得到,4.8.4 高次自然样条与B-样条 高次自然样条 确切地说,高次自然样条只对奇数阶定义. 下面定义 次自然样条. 定义4.8.2( 自然次样条函数)给定区间 上的分划 如定义4.8.1 .函数 称为 自然样条,如果它: (i)在每个子区间 上都是次数不超过 的多项式; 在区间 和 上是次数不超过 的多项式. 分划 下的 次自然样条函

11、数构成的集合记为 . (依此定义,三次自然样条在区间 和 上退化为一 次多项式.),为方便后面导出B-样条,我们考虑利用构造Lagrange插值或 Newton插值的结点基函数那样的方法,使一般 次自然样 条能用适当的基函数作“元件”来“组合装配”出来. 对 次幂函数 作一种“截肢”手术:截去 的部分 并以 0 接上,得到所谓半截幂函数(truncated power function) 这种手术导致 处 阶导数间断(有跃度),但直到 阶导数仍连续.,我们来观察跃度: 阶梯函数的基函数 此函数本身在 处有间断,跃度为1. 一次单项式 的半截幂及其1阶导数 次单项式 的半截幂及其 阶导数,至此我

12、们已经可以观察到: 单项式半截幂 可被视为一个结点的 次 样条; 平移后得到的 也是一个结点的 次样条; 平移、压缩、组合后得到的 是两个结点的 次样条. 尤为重要的是:利用半截幂这样简单的样条可构造 出一系列新的样条.,定理(4.3)前述分划 上存在唯一自然样条 且可表为 其中 证明(留作讨论题). 思考题: 半截幂函数 的支集 Supp 为何? 定性地分 类函数数据误差的扩散情况.,B-样条基础 前已指出:我们可以利用半截幂这样简单的样条作 为基装配成一系列新的样条.下面讨论通过提供基函 数(Bases Function)来构造样条函数空间的一般方法. 首先将有限的结点集扩展为无穷集分划

13、其次定义半截幂 的一阶差分 如此得到的样条 称为0次B-样 条(B-spline).,有如下性质: 对所有的 和所有的 ; 对所有的 于是0次样条函数可表为 阶梯函数 递归地定义 次B-样条 如下:,记 则(4.12)可写成 例1.1次B-样条(图4.8.3) 图4.8.3 于是1次样条函数可表为 分段线性函数,例2. 2次B-样条(图4.8.4) 图4.8.4 例3. 3次B-样条(图4.8.5) 图4.8.5,次B-样条 有如下性质(证明作为课外讨论题): B-样条组 是 上的线性无关组. 在相同的分划 之下, 越大, 的集Supp 越大,振幅越小,因而误差随远离结点而衰减. 记 则有 若

14、 为一致分划,则 B-样条 提供了一类具有若干特殊性质的基!,B-样条插值 我们的兴趣在于利用B-样条作插值.为此,我们限制 于区间 .插值问题的提法为: 求 形如 满足条件 () 和 () 某种边界约束. 有关B-样条的更多理论与应用讨论留待下次课.,小结 样条相对于其它分段多项式插值的主要优点是它保证了 较高阶的整体光滑性.实践中,曲率间断就须仔细打量才能察觉, 三次样条能保证二阶导数连续,三阶导数仅在结点间断, 如此 的光滑通常是足够的.三阶导数在结点间断还带来了转折灵活 的特点. B-样条的支集虽然随阶数的提高而扩大,但结点数据误差 仍可控制于局部,且愈远离结点愈衰减,这使得样条插值的稳定 性要优于其它高次多项式插值. 次B-样条 之性质 意味着 越大 越光滑,但它的支集也就