德布尔算法

数学的子领域数值分析中，De Boor算法是快速而且数值上稳定的算法，用于计算B样条形式的样条曲线。这是用于贝兹曲线的de Casteljau算法的一个推广。

一般的情况如下。我们要构造一个穿过一系列个点${\displaystyle {\stackrel{\to <!--\; \to \; -->}{d}}_0,{\stackrel{\to <!--\; \to \; -->}{d}}_1,\dots <!--\; \dots \; -->,{\stackrel{\to <!--\; \to \; -->}{d}}_{p-<!--\; -\; -->1}}$的函数。要穿过点的序列，曲线必须满足${\displaystyle \stackrel{\to <!--\; \to \; -->}{s}(u_0)={\stackrel{\to <!--\; \to \; -->}{d}}_0,\dots <!--\; \dots \; -->,\stackrel{\to <!--\; \to \; -->}{s}(u_{p-<!--\; -\; -->1})={\stackrel{\to <!--\; \to \; -->}{d}}_{p-<!--\; -\; -->1}}$和${\displaystyle {\stackrel{\to <!--\; \to \; -->}{d}}_0,{\stackrel{\to <!--\; \to \; -->}{d}}_1,\dots <!--\; \dots \; -->,{\stackrel{\to <!--\; \to \; -->}{d}}_{p-<!--\; -\; -->1}}$阶多项式的曲线。这表示在任意区间上，曲线必须等于次数最多的多项式。它在不同的区间上可以是不同的多项式。多项式必须：当区间和上的多项式在点上相遇，它们必须有同样的值，而且他们的导数必须相等（以保证曲线是光滑的）。

De Boor算法是一个算法，当给定和${\displaystyle {\stackrel{\to <!--\; \to \; -->}{d}}_0,{\stackrel{\to <!--\; \to \; -->}{d}}_1,\dots <!--\; \dots \; -->,{\stackrel{\to <!--\; \to \; -->}{d}}_{p-<!--\; -\; -->1}}$的值。它采用O(n2)次操作。注意算法的运行时间依赖于多项式的次数,而不是点的个数。

假设我们要计算参数值为${\displaystyle {\stackrel{\to <!--\; \to \; -->}{d}}_i^{}={\stackrel{\to <!--\; \to \; -->}{d}}_i}$.现在计算

其中

则${\displaystyle \stackrel{\to <!--\; \to \; -->}{s}(x)={\stackrel{\to <!--\; \to \; -->}{d}}_{\mathrm{\ell <!--\; \ell \; -->}}^{}}$.