牛頓差商（Newton divided differences）

假設你一次一個點地建構插值曲線，而你希望每個新資料點只「加上」一個修正，而不擾動已有的部分——就像為級數加上更細的項。牛頓差商形式正是如此：它把插值多項式寫成一個巢狀和，每一個後續項都把曲線多拉過一個點。

其形式為 p(x) = c_0 + c_1 (x - x_0) + c_2 (x - x_0)(x - x_1) + c_3 (x - x_0)(x - x_1)(x - x_2) + ...。係數 c_k 就是差商，在一張三角形的表中計算。零階差商就是 y 值 f[x_i] = y_i。一階差商是斜率，f[x_i, x_{i+1}] = (f[x_{i+1}] - f[x_i]) / (x_{i+1} - x_i)。更高階遞迴而得：f[x_i, ..., x_{i+k}] = (f[x_{i+1}, ..., x_{i+k}] - f[x_i, ..., x_{i+k-1}]) / (x_{i+k} - x_i)。這張表的主對角線直接給出 c_0, c_1, c_2, ...。每個 (x - x_j) 因式在較早的節點為零，所以加上一項從不破壞先前的擬合——這正是為何「新」資料點只需附加一個係數與一個因式，擴充起來很便宜。

當你逐步擴大資料集，或想估計插值誤差時（被略去的領先差商表現得像誤差項），牛頓形式是實用的主力。建表只需一次 O(n^2)；之後用巢狀（霍納式）乘法計算 p(x) 是 O(n)。拉格朗日寫成加權和的同一個多項式，牛頓寫成巢狀乘積——同一條曲線，不同且往往更方便的記帳方式。一個誠實的提醒：和所有單一高次插值一樣，它在等距節點上仍會受龍格現象之害。