B样条全非负配点与变号缩减

形式陈述

取次数 $p\ge1$ 、合法夹持节点向量与按节点顺序排列的 $N$ 个B样条，保留节点插入的内部右侧值、最右端左极限约定。允许内部节点重数达到 $p+1$ 而产生跳变。给定严格递增查询 $a\le x_1<\cdots<x_m\le b$ ，普通点值配点矩阵为

C_{ri}=B_{i,p}(x_r),\qquad r=1,\ldots,m,\quad i=0,\ldots,N-1.

它是全非负矩阵：任意按原顺序选出的同阶行列子式都非负。样条文献常把这个性质叫total positivity；本页不把它误写成“每个子式严格为正”。局部支撑会产生零条目和零子式。

对实序列 $c$ ，令 $S^-(c)$ 为删去所有零后相邻异号的次数，全零序列取零。对 $s=\sum_i c_iB_{i,p}$ ，任意上述查询有

S^-\bigl(s(x_1),\ldots,s(x_m)\bigr)\le S^-(c).\tag{1}

输出是一份与查询网格无关的变号上界。它数的是强变号，不是所有零点的重数；若函数连续，可解释为穿过水平线，仍不计相切或整段重合。允许跳变时，数值可以从正侧跳到负侧而不取零，不能称为实际交点；正函数触及零再返回正侧不会增加 $S^-$ 。它也不是PDE格式的离散总变差 $\sum_i|U_{i+1}-U_i|$ 不增长定理。

直觉

一次插结把系数 $c$ 变成 $\widetilde c=Ec$ 。 $E$ 的每一行只复制一个旧系数，或以非负权重混合相邻两项：第 $i$ 行的支撑包含于 $\{i-1,i\}$ ，两端按合法下标删去不存在项。所有混合系数之和为一。

从有序支撑到所有子式

取 $E$ 任意方形子矩阵，按行列原序展开行列式。一个非零排列项必须让每行匹配到它的支撑列。若两行 $r<s$ 出现倒序匹配 $j>k$ ，则

j\le r,\qquad k\ge s-1\ge r,

与 $j>k$ 矛盾。因此非零项只能对应保序匹配，在所选列的排序中就是恒等排列；它是非负元素的乘积。没有合法匹配时子式为零。所以 $E$ 全非负。重复插结的矩阵积仍全非负，因为Cauchy–Binet公式把每个乘积矩阵子式写成

\det(AB)_{I,J}=\sum_{|L|=|I|}\det A_{I,L}\det B_{L,J},

每项都非负。

对每个内部查询点，反复插入直至重数为 $p$ ，此时对应曲线值就是细化后的一个系数；若该点原已是满重数跳点，选择右侧端系数。 $a$ 取首系数， $b$ 取末系数。所有查询值按顺序形成细化系数序列的子序列。因此 $C=PE_q\cdots E_1$ ，其中 $P$ 只是保序取行矩阵，也全非负。于是配点矩阵所有子式非负。只查询函数值的条件在这里不可省略：把某些行换成导数行，不再是这种保序取系数操作。

变号缩减的直接证明

从旧系数序列出发，先把每个混合值插到它的两个来源系数之间。若两来源同号，混合值不会有相反符号；若两来源异号，原本的一次变号最多仍是一次；零值按删除规则处理。因此这个加长序列不增加变号。再从中保序抽取真正的新系数序列，只会减少或保留变号。重复插结，最后抽取查询值，就得到式(1)。此证明不需要把一般全非负矩阵的变号定理当作未经说明的黑箱。

例子与边界

一个可以完整验算的矩阵

令 $p=2$ ， $t=(0,0,0,1,2,2,2)$ ，查询 $(0,1/2,1,3/2,2)$ 。由原有B样条递推得到

C=\begin{pmatrix} 1&0&0&0\\ 1/4&5/8&1/8&0\\ 0&1/2&1/2&0\\ 0&1/8&5/8&1/4\\ 0&0&0&1 \end{pmatrix}.\tag{2}

中间相邻两行、两列的一个二阶子式为 $(5/8)(1/2)-(1/8)(1/2)=1/4$ 。第1、2、4、5行的四阶子式为 $25/64-1/64=3/8$ 。第1、2行与第3、4列的子式则为零；全非负不等于严格全正。

取 $c=(1,-2,2,-1)$ ，有三次系数变号。矩阵乘积为

Cc=(1,-3/4,0,3/4,-1)^{\mathsf T},

删除中间零后仍有三次变号，所以这个上界可达到。整条曲线在两段上分别为

s(x)= \begin{cases}1-6x+5x^2,&0\le x\le1,\\ 4z-5z^2,\quad z=x-1,&1\le x\le2. \end{cases}

零点为 $1/5,1,9/5$ ，在各点两侧符号均改变，所以全区间正好三次穿越。

非负单位分解还不够

在 $[0,1]$ 取

b_0(x)=\{1+\cos(4\pi x)\}/2,\qquad b_1(x)=\{1-\cos(4\pi x)\}/2.

它们非负、和为一。但系数 $(1,-1)$ 只有一次变号，函数 $b_0-b_1=\cos(4\pi x)$ 在查询 $(0,1/4,1/2,3/4,1)$ 上给 $(1,-1,1,-1,1)$ ，有四次变号。查询 $1/4,1/2$ 的两行矩阵为 $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ ，行列式为 $-1$ 。缺失的是有序插结结构，而非凸组合数值范围。

若将式(2)的查询行任意倒序，子式符号也可能改变；定理要求行按查询位置、列按B样条支撑顺序排列。数值检测到一个负小子式还应区分真正负值和舍入误差，穷举浮点子式不能代替结构证明。

推论与应用

把变号上界移到任意直线

令Greville位置 $\xi_i=(t_{i+1}+\cdots+t_{i+p})/p$ 。有 $\sum_i\xi_iB_{i,p}(x)=x$ ：将这些系数代入导数系数公式，非零支撑的导数系数全为一，再结合左端值；满重数时逐块成立且两侧都给节点坐标。因此对 $\ell(x)=\alpha+\beta x$ ，

s(x)-\ell(x)=\sum_i[c_i-\alpha-\beta\xi_i]B_{i,p}(x),

应用式(1)即知，曲线穿过此直线的次数不超过系数序列 $c_i-\alpha-\beta\xi_i$ 的变号次数。对连续曲线，几何上这是控制折线相对此直线的穿越证书；对不连续曲线，只声明左右取值的强变号上界。只需计算有限序列，不必从密集采样猜测未见的交点。

在前例 $\xi=(0,1/2,3/2,2)$ 。取直线 $\ell=1/2$ ，偏移系数为 $(1/2,-5/2,3/2,-3/2)$ ，最多三次穿越。实际首段 $1-6x+5x^2=1/2$ 在 $[0,1]$ 内有一根 $(6-\sqrt{26})/10$ ；第二段 $4z-5z^2=1/2$ 有两根 $(4\pm\sqrt6)/10$ ，所以三次上界仍达到。

这比原来的导数系数同号证书回答了更广的“能穿过指定直线多少次”问题，但不把同一单调充分条件再算作一个新定理。对连续曲线，控制折线非降或凸可导出相应形状保持；若只需检查导数符号，直接使用原有导数页更短。

拟合数据不是控制系数

式(1)比较的是样条系数和函数值。插值或最小二乘先要从数据求出系数，求解矩阵的逆不必全非负，因而不能据此宣称“单调数据的普通三次插值一定单调”。若要求拟合曲线具有已知形状，可以把导数系数非负等约束施加在求解阶段；这另需约束优化，当前定理没有自动替你施加它。

自测一。 单段二次 $s(x)=(x-1/2)^2$ 在 $[0,1]$ 上的Bernstein系数为 $(1/4,-1/4,1/4)$ ，两次系数变号；函数只有一个二重零点，却没有符号穿越，故 $S^-(s)=0$ 。定理是上界，既不保证达到，也不把相切计成两次变号。

自测二。 $p=1$ 、 $t=(0,0,1,1,2,2)$ 、 $c=(1,1,-1,-1)$ 的曲线能否不取零却有一次强变号？能。它在 $[0,1)$ 恒为1，在 $[1,2]$ 恒为−1；系数和样本各有一次变号，但没有零点。

参考资料

Carl de Boor，B(asic)-Spline Basics，§11与§13，Theorem 13及其推论：细化取值、变号缩减与直线穿越。
Carl de Boor，Total Positivity of the Spline Collocation Matrix，Indiana University Mathematics Journal 25(6), 1976，pp.541–551，Theorem 2；本文只使用普通点值配点，并以插结矩阵重新给出非负子式证明。

形式陈述 ​

从有序支撑到所有子式 ​

变号缩减的直接证明 ​

一个可以完整验算的矩阵 ​

非负单位分解还不够 ​

把变号上界移到任意直线 ​

拟合数据不是控制系数 ​

反向链接