德布尔算法

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

概述

一般的情况如下。若要构造一个穿过一系列p个点${\overrightarrow{d}}_0,{\overrightarrow{d}}_1,\dots ,{\overrightarrow{d}}_{p-1}$的曲线。曲线可以描述为一个参数x的函数。要穿过点的序列，曲线必须满足$\overrightarrow{s}(u_0)={\overrightarrow{d}}_0,\dots ,\overrightarrow{s}(u_{p-1})={\overrightarrow{d}}_{p-1}$。可假设u₀, ..., u_p-1和${\overrightarrow{d}}_0,{\overrightarrow{d}}_1,\dots ,{\overrightarrow{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和${\overrightarrow{d}}_0,{\overrightarrow{d}}_1,\dots ,{\overrightarrow{d}}_{p-1}$时，它能找到样条曲线$\overrightarrow{s}(x)$在点x的值。它采用O(n²)次操作。注意算法的运行时间依赖于多项式的次数n,而不是点的个数p。

算法概要

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

$\overrightarrow{s}(x)=\sum _{i=0}^{p-1}{\overrightarrow{d}}_i{N}_i^n(x),$而$N_i^0(x)=\{\begin{array}{cc}1,& \text{if }x\in [u_{\ell },u_{\ell +1})\\ 0,& \text{... }\end{array}$

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

因为样条的局域性，

$\overrightarrow{s}(x)=\sum _{i=\ell -n}^{\ell }{\overrightarrow{d}}_i{N}_i^n(x)$

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

算法

假设$x\in [u_{\ell },u_{\ell +1})$且${\overrightarrow{d}}_i^{[0]}={\overrightarrow{d}}_i$对于i = l-n, ..., l. 现在计算

${\overrightarrow{d}}_i^{[k]}=(1-{\alpha }_{k,i}){\overrightarrow{d}}_{i-1}^{[k-1]}+{\alpha }_{k,i}{\overrightarrow{d}}_i^{[k-1]};k=1,\dots ,n;i=\ell -n+k,\dots ,\ell$

其中

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

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