德布爾算法

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

基本介紹

• 中文名：德布爾算法
• 外文名：De Boor algorithm
• 類型：快速穩定算法
• 套用：數值分析
• 領域：樣條、算法

概述

一般的情況如下。我們要構造一個穿過一系列p個點的曲線。曲線可以描述為一個參數x的函式。要穿過點的序列，曲線必須滿足。我們假設u0, ..., up-1和一起給定。這個問題稱為插值。

解決這個問題的一個方法是用樣條。樣條是一個分段nth階多項式的曲線。這表示在任意區間[ui, ui+1)上，曲線必須等於次數最多n的多項式。它在不同的區間上可以是不同的多項式。多項式必須同步：當區間[ui-1, ui)和[ui, ui+1)上的多項式在點ui上相遇，它們必須有同樣的值，而且他們的導數必須相等（以保證曲線是光滑的）。

De Boor算法是一個算法，當給定u0, ..., up-1和 時，它能找到樣條曲線在點x的值。它採用O(n2)次操作。注意算法的運行時間依賴於多項式的次數n,而不是點的個數p。

算法概要

假設我們要計算參數值為的樣條曲線的值。我們可以將曲線表示為：

而

其中是x的多項式其參數依賴於u0, ..., un但和無關。

因為樣條的局域性，

所以值由控制點決定;其他控制點沒有影響。下一節所述的De Boor算法是一個有效計算表達式的程式。

算法

假設且 對於i = l-n, ..., l. 現在計算

其中

則。