龍格現象教給我們的一課
讀到這一篇時，你已經目睹過單一條高次插值多項式做出一件真正令人不安的事。對一個再無辜不過的函數取樣——經典例子是 [-1, 1] 上的 1/(1 + 25 x^2)——在許多等距的點上取樣，再拿一條多項式穿過它們全部，那條曲線並不會隨著你加點而變好。它變糟了。在區間兩端附近，它冒出劇烈的振盪，且隨著次數升高而無上限地越長越高。這就是龍格現象，它的教訓很直白：硬逼一條全域多項式去串起許多點，是用錯了工具。前一篇給了一帖解藥（把點移到切比雪夫節點上）。這一篇給出另一帖，而且可說是更實用的那一帖。
關鍵的洞見是：放棄「一條曲線」這個念頭。一條 n 次多項式有 n 個可用的彎，而當 n 很大時它就會把它們用掉——正是這份靈活性讓兩端炸開。所以與其用一條僵硬、神經兮兮、橫跨一切的 n 次曲線，不如鋪上許多條短曲線，每一條都是低且固定的次數，每一條只負責相鄰兩個資料點之間那一小段。把這些短弧首尾相黏。結果就是一條樣條：一個分段的多項式，每一段都是低次，穿過所有資料，卻沒有任何全域的彎可以發狂。每一段都太短、太溫柔，鬧不起事來。
從「連連看」走向某種平滑
最簡單的樣條，是你從小就在畫的那種：用一條直線連起每一對相鄰的點。這就是分段線性插值——一條 1 次的樣條。它有許多美好的性質。它永遠不會超過資料的範圍，它無法振盪，加更多點只會讓它變得更好，而且求值簡單到不行。對許多工作而言（隨手畫個圖、查一張取樣密集的對照表），它真的就夠了，而且龍格現象拿它一點辦法也沒有。它唯一的缺點是：它有看得見的折角——在每個資料點上斜率都突然改變，所以曲線有尖角。眼睛看得出來，而任何需要平滑導數的計算，都會被這些尖角噎住。
要把尖角磨平，我們讓每一段的靈活度往上提一級。假設每一段是一條三次式——3 次多項式——而非直線。一條三次式有四個係數，恰好夠的自由度同時做四件事：穿過它左端的資料點、穿過它右端的資料點，並在接點處與鄰居的斜率和曲率對齊。當我們要求相鄰的三次式不僅在數值上、還要在一階導數 f'(x) 與二階導數 f''(x) 上、於每一個內部節點都吻合時，尖角就徹底消失了。接點變得無形：曲線與它的前兩階導數處處連續。這就是著名的三次樣條，它是平滑插值的主力馬。
三次樣條實際上是怎麼造出來的
讓三次樣條既聰明又便宜的部分，就在這裡。有 m 個區間，就有 m 條三次式，於是有 4m 個未知係數——聽起來像一團亂麻。但這些條件排列得極為漂亮。每條三次式都得命中它的兩個端點（這是 2m 個條件），而在 m-1 個內部節點上，斜率要吻合、曲率也要吻合（這又是 2(m-1) 個）。數一數，你恰好還差兩個條件，才能把一切釘死。那最後兩個，就是你在最兩端提供的邊界條件——而這一小份自由是真實存在的，所以光憑資料本身，樣條並不唯一確定，直到你選定要如何把它封口。
- 把節點上未知的二階導數（記為 M_0、M_1、...、M_m）當作真正的未知數；如此一來，每個區間上的三次式就由它兩端的兩個 M 值，加上兩個資料高度所決定。
- 施加「斜率必須跨每個內部節點吻合」的條件。每一條這樣的條件只把一個節點與它緊鄰的左右鄰居連起來，給出一條含 M_{n-1}、M_n、M_{n+1} 的方程。
- 挑兩個邊界條件來封閉這個系統：「自然」（令 M_0 = M_m = 0，木條在兩端鬆弛攤平）、「夾持」（把兩端斜率固定為已知值）、或「非節點」。
- 解出所得系統裡的所有 M 值，再從每條三次式兩端的兩個 M 值與兩個資料高度，讀出它的係數。
漂亮的回報，在於那個線性系統的形狀。因為每一條斜率吻合方程只碰到一個節點與它緊鄰的兩個鄰居，這個矩陣是三對角的——只在主對角線與它旁邊的兩條上非零，其餘處處為零。一個三對角系統不需要花 O(n^3) 代價的一般高斯消去法；托馬斯演算法以前掃後掃，用 O(n) 的時間就解完，與點數成線性。所以穿過一千個點的三次樣條，幾乎是瞬間造好。對照那條全域多項式，它的范德蒙系統稠密、且惡名昭彰地病態。便宜、穩定、平滑：在龍格那條曲線狂抖時所關心的每一條軸上，樣條都勝出。
B-樣條：同一條曲線，更好的基底
還有第二種方式來描述「分段三次式」這同一個家族，而它已經接管了電腦繪圖、CAD 與字型設計。與其儲存每一段多項式的係數，不如把樣條建成一些特殊的、隆起狀的積木的加權和，這些積木叫做 B-樣條（「B」代表「基底」basis）。每一條 B-樣條本身就是一個小的分段多項式，只在少數幾個相鄰區間上非零、其餘處處為零——它是一個局部化的隆起。任何你能用係數方式寫出的樣條，你都同樣可以寫成這些隆起的和，每一個由一個控制係數縮放。B-樣條基底，只不過是同一個曲線空間更聰明的一組座標。
為同一批曲線換一組新基底，何苦來哉？因為局部性。由於每一條 B-樣條隆起只碰到少數幾個區間，改動一個控制係數，只會在那一小片鄰域裡推動曲線，其餘原封不動。一位設計師拖動字型輪廓的一個控制點，並不希望字母的另一端跟著起漣漪——有了 B-樣條，它就不會。這跟全域多項式恰恰相反，在那裡動一個資料點，整條曲線從頭到尾都會被重塑。局部性也意味著數值穩定（不會因巨大而相消的項而災難性抵消）以及再次出現的稀疏帶狀系統。繪圖界的 NURBS 曲線就是再加一道手腳（權重）的 B-樣條，它們坐落在你螢幕上幾乎每一個平滑形狀的底下。
誠實的界限：樣條承諾什麼、又不承諾什麼
樣條很美好，但讓我們對它的界限說個清楚。第一，一條插值樣條仍然精確地穿過每一個資料點——所以若你的取樣帶有雜訊，樣條會忠實地重現那些雜訊，扭著身子穿過每一個出格的點。當資料有雜訊時，你通常根本不該做插值；你該擬合一條平滑樣條，或一個容許錯過那些點的最小平方模型。第二，三次樣條的精度在點距 h 上是 O(h^4)：優秀，且隨著加點而穩定改善，但它是一個固定的多項式階，並非切比雪夫逼近對一個真正光滑的函數所能達到的、火箭般的指數級精度。樣條以一點點巔峰精度，換取了穩健與局部性。
第三，邊界條件確實要緊，而且並非沒有後果。一條「自然」樣條強迫兩端曲率為零，這對底層函數而言往往是錯的，並且會在邊界附近損害精度；「非節點」或「夾持」（若你知道兩端真正的斜率）通常表現得更好。而你算出的每一個樣條值，仍然是一個浮點近似——托馬斯解法雖然對樣條所產生的對角佔優系統是穩定的，仍會累積尋常的捨入，所以那條「精確」穿過你那些點的曲線，其實只精確到大約機器精度。這些都絲毫無損於那句主標題：要讓一條平滑曲線穿過品質尚可、相對乾淨的資料，一條低次的分段樣條幾乎永遠是對的答案，而單一條高次多項式幾乎永遠不是。