《算法的乐趣》第三十七节

本节首先给出样条函数的数学定义：若函数在整个区间上具有m-1阶连续导数，且在每个子区间上是m次多项式，则称为m次样条函数；若它在各节点处与原函数值相等，则为样条插值函数。

本节首先给出样条函数的数学定义：若函数在整个区间上具有m-1阶连续导数，且在每个子区间上是m次多项式，则称为m次样条函数；若它在各节点处与原函数值相等，则为样条插值函数。工程上常用三次样条，因其具有二阶连续导数。三次样条由n个三次多项式组成，共需确定4n个系数，而节点处的连续性和插值条件只能提供4n-2个方程，因此需要补充两个边界条件：第一类（给定端点一阶导数）、第二类（给定端点二阶导数，若均为零则称自然边界条件）或第三类（周期函数）。

推导求解常用“三转角法”和“三弯矩法”，二者本质相同，只是利用一阶或二阶导数的多项式特性不同。以“三弯矩法”为例，先设各节点二阶导数值为Mi，据此写出每个子区间上二阶导数的线性表达式，两次积分并利用插值条件定出积分常数，得到只含未知量Mi的区间表达式；再对一阶导数在节点处左右导数相等的条件整理，得到关于Mi的n-1个方程，加上两个边界条件方程，构成三弯矩方程组。该方程组的系数矩阵严格对角占优，可用追赶法（即托马斯法）求解：先对矩阵作Crout分解，再分别递推求出中间向量和最终解，求得Mi后代回即得三次样条函数。