[科普中国]-德布尔算法

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

概述一般的情况如下。我们要构造一个穿过一系列p个点的曲线。曲线可以描述为一个参数x的函数。要穿过点的序列，曲线必须满足。我们假设u0, ..., up-1和一起给定。这个问题称为插值。2

解决这个问题的一个方法是用样条。样条是一个分段nth阶多项式的曲线。这表示在任意区间[ui, ui+1)上，曲线必须等于次数最多n的多项式。它在不同的区间上可以是不同的多项式。多项式必须同步：当区间[ui-1, ui)和[ui, ui+1)上的多项式在点ui上相遇，它们必须有同样的值，而且他们的导数必须相等（以保证曲线是光滑的）。3

De Boor算法是一个算法，当给定u0, ..., up-1和 时，它能找到样条曲线在点x的值。它采用O(n2)次操作。注意算法的运行时间依赖于多项式的次数n,而不是点的个数p。4

算法概要假设我们要计算参数值为的样条曲线的值。我们可以将曲线表示为：

而

其中是x的多项式其参数依赖于u0, ..., un但和无关。

因为样条的局域性，

所以值由控制点决定;其他控制点没有影响。下一节所述的De Boor算法是一个有效计算表达式的程序。2

算法假设且 对于i = l-n, ..., l. 现在计算

其中

则。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学