德布爾算法

數學的子領域數值分析中，De Boor算法是快速而且數值上穩定的算法，用於計算B樣條形式的樣條曲線。這是用於貝茲曲線的de Casteljau算法的一個推廣。

概述

一般的情況如下。若要構造一個穿過一系列p個點${\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p-1}$的曲線。曲線可以描述為一個參數x的函數。要穿過點的序列，曲線必須滿足${\vec {s}}(u_{0})={\vec {d}}_{0},\dots ,{\vec {s}}(u_{p-1})={\vec {d}}_{p-1}$。可假設u₀, ..., u_p-1和${\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和${\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p-1}$時，它能找到樣條曲線${\vec {s}}(x)$在點x的值。它採用O(n²)次操作。注意算法的運行時間依賴於多項式的次數n,而不是點的個數p。

算法概要

假設要計算參數值為$x\in [u_{\ell },u_{\ell +1})$的樣條曲線的值。可以將曲線表示為

${\vec {s}}(x)=\sum _{i=0}^{p-1}{\vec {d}}_{i}N_{i}^{n}(x),$而$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但和${\vec {d}}_{i}$無關。

因為樣條的局域性，

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

所以值${\vec {s}}(x)$由控制點${\vec {d}}_{\ell -n},{\vec {d}}_{\ell -n+1},\dots ,{\vec {d}}_{\ell }$決定;其他控制點${\vec {d}}_{i}$沒有影響。下一節所述的De Boor算法是一個有效計算${\vec {s}}(x)$表達式的程序。

算法

假設$x\in [u_{\ell },u_{\ell +1})$且${\vec {d}}_{i}^{[0]}={\vec {d}}_{i}$對於i = l-n, ..., l. 現在計算

${\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$

其中

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

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