德布尔算法

此條目没有列出任何参考或来源。 (2009年5月17日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

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

一般的情况如下。若要构造一个穿过一系列p个点${\displaystyle {\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p-1}}$的曲线。曲线可以描述为一个参数x的函数。要穿过点的序列，曲线必须满足${\displaystyle {\vec {s}}(u_{0})={\vec {d}}_{0},\dots ,{\vec {s}}(u_{p-1})={\vec {d}}_{p-1}}$。可假设u₀, ..., u_p-1和${\displaystyle {\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p-1}}$一起给定。这个问题称为插值。

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

De Boor算法是一个算法，当给定u₀, ..., u_p-1和${\displaystyle {\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p-1}}$时，它能找到样条曲线${\displaystyle {\vec {s}}(x)}$在点x的值。它采用O(n²)次操作。注意算法的运行时间依赖于多项式的次数n,而不是点的个数p。

假设要计算参数值为${\displaystyle x\in [u_{\ell },u_{\ell +1})}$的样条曲线的值。可以将曲线表示为

${\displaystyle {\vec {s}}(x)=\sum _{i=0}^{p-1}{\vec {d}}_{i}N_{i}^{n}(x),}$而${\displaystyle N_{i}^{0}(x)=\left\{{\begin{matrix}1,&{\mbox{if }}x\in [u_{\ell },u_{\ell +1})\\0,&{\mbox{... }}\end{matrix}}\right.}$

其中N_iⁿ（x）是x的多项式其参数依赖于u₀, ..., u_n但和${\displaystyle {\vec {d}}_{i}}$无关。

因为样条的局域性，

${\displaystyle {\vec {s}}(x)=\sum _{i=\ell -n}^{\ell }{\vec {d}}_{i}N_{i}^{n}(x)}$

所以值${\displaystyle {\vec {s}}(x)}$由控制点${\displaystyle {\vec {d}}_{\ell -n},{\vec {d}}_{\ell -n+1},\dots ,{\vec {d}}_{\ell }}$决定;其他控制点${\displaystyle {\vec {d}}_{i}}$没有影响。下一节所述的De Boor算法是一个有效计算${\displaystyle {\vec {s}}(x)}$表达式的程序。

假设${\displaystyle x\in [u_{\ell },u_{\ell +1})}$且${\displaystyle {\vec {d}}_{i}^{[0]}={\vec {d}}_{i}}$对于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 }$

其中

${\displaystyle \alpha _{k,i}={\frac {x-u_{i}}{u_{i+n+1-k}-u_{i}}}}$。

则${\displaystyle {\vec {s}}(x)={\vec {d}}_{\ell }^{[n]}}$.