查看“德布尔算法”的源代码

{{unreferenced|time=2009-5-17}}

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

== 概述 ==

一般的情况如下。我们要构造一个穿过一系列''p''个点<math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>的曲线。曲线可以描述为一个参数''x''的函数。要穿过点的序列，曲线必须满足<math>\vec{s}(u_0)=\vec{d}_0, \dots,
\vec{s}(u_{p-1})=\vec{d}_{p-1}</math>。我们假设''u<sub>0</sub>, ..., u<sub>p-1</sub>''和<math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>一起给定。这个问题称为[[插值]]。

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

De Boor算法是一个算法，当给定''u<sub>0</sub>, ..., u<sub>p-1</sub>''和<math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>时，它能找到样条曲线<math>\vec{s}(x)</math>在点''x''的值。它采用[[大O记号|O]](n<sup>2</sup>)次操作。注意算法的运行时间依赖于多项式的次数''n'',而不是点的个数''p''。

== 算法概要 ==
假设我们要计算参数值为<math> x \in [u_{\ell},u_{\ell+1}) </math>的样条曲线的值。我们可以将曲线表示为 

:<math> \vec{s}(x) = \sum_{i=0}^{p-1} \vec{d}_i N_i^n(x), </math>而<math>N_i^0(x)=\left\{\begin{matrix} 1, & \mbox{if }x \in [u_{\ell},u_{\ell+1}) \\ 0, & \mbox{... } \end{matrix}\right.</math>
其中''N<sub>i</sub><sup>n</sup>（x）''是x的多项式其参数依赖于''u<sub>0</sub>, ..., u<sub>n</sub>''但和<math>\vec{d}_i</math>无关。

因为样条的局域性，
:<math> \vec{s}(x) = \sum_{i=\ell-n}^{\ell} \vec{d}_i N_i^n(x) </math>
所以值<math>\vec{s}(x)</math>由控制点<math> \vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell} </math>决定;其他控制点<math>\vec{d}_i</math>没有影响。下一节所述的De Boor算法是一个有效计算<math> \vec{s}(x) </math>表达式的程序。

== 算法 ==

假设<math> x \in [u_{\ell},u_{\ell+1}) </math>且<math> \vec{d}_i^{[0]} = \vec{d}_i </math>对于''i = l-n, ..., l''.
现在计算
:<math> \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 </math>
其中
:<math> \alpha_{k,i} = \frac{x-u_i}{u_{i+n+1-k}-u_i}</math>。
则<math> \vec{s}(x) = \vec{d}_{\ell}^{[n]} </math>.

[[Category:算法]]
[[Category:样条]]