数学的子领域数值分析中,De Boor算法是快速而且数值上稳定的算法,用于计算B样条形式的样条曲线。这是用于贝兹曲线的de Casteljau算法的一个推广。
一般的情况如下。若要构造一个穿过一系列p个点
的曲线。曲线可以描述为一个参数x的函数。要穿过点的序列,曲线必须满足
。可假设u0, ..., up-1和
一起给定。这个问题称为插值。
解决这个问题的一个方法是用样条。样条是一个分段nth阶多项式的曲线。这表示在任意区间[ui, ui+1)上,曲线必须等于次数最多n的多项式。它在不同的区间上可以是不同的多项式。多项式必须同步:当区间[ui-1, ui)和[ui, ui+1)上的多项式在点ui上相遇,它们必须有同样的值,而且他们的导数必须相等(以保证曲线是光滑的)。
De Boor算法是一个算法,当给定u0, ..., up-1和
时,它能找到样条曲线
在点x的值。它采用O(n2)次操作。注意算法的运行时间依赖于多项式的次数n,而不是点的个数p。
假设要计算参数值为
的样条曲线的值。可以将曲线表示为
而
其中Nin(x)是x的多项式其参数依赖于u0, ..., un但和
无关。
因为样条的局域性,

所以值
由控制点
决定;其他控制点
没有影响。下一节所述的De Boor算法是一个有效计算
表达式的程序。
假设
且
对于i = l-n, ..., l.
现在计算
![{\displaystyle {\vec {d}}_{i}^{[k]}=(1-\alpha _{k,i}){\vec {d}}_{i-1}^{[k-1]}+\alpha _{k,i}{\vec {d}}_{i}^{[k-1]};\qquad k=1,\dots ,n;\quad i=\ell -n+k,\dots ,\ell }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dc4aa5b0dc93dd795746d4fdda9517c7b1b5631)
其中
。
则
.