跳至內容

德布爾算法

維基百科,自由的百科全書

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

概述

[編輯]

一般的情況如下。若要構造一個穿過一系列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

算法概要

[編輯]

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

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

因為樣條的局域性,

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

算法

[編輯]

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

其中

.