德布尔算法

数学的子领域数值分析中，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₀, ..., u_p-1和<math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>一起给定。这个问题称为插值。

解决这个问题的一个方法是用样条。样条是一个分段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和<math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>时，它能找到样条曲线<math>\vec{s}(x)</math>在点x的值。它采用O(n²)次操作。注意算法的运行时间依赖于多项式的次数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_iⁿ（x）是x的多项式其参数依赖于u₀, ..., u_n但和<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>.