多項式插值不僅有牛頓法，內維爾算法與艾特肯迭代法提供了更適合程式化的遞歸結構。本文深度解析三種插值實現（Neville、Aitken、自創改進），展示如何通過遞歸差商實現高效、數值穩定的插值計算。
| 算法 | 核心遞推 | 特點 |
|---|---|---|
| Neville | Pᵢ,ⱼ = [(x₀-xᵢ₋ⱼ)Pᵢ,ⱼ₋₁ - (x₀-xᵢ)Pᵢ₋₁,ⱼ₋₁] / (xᵢ-xᵢ₋ⱼ) | 單表遞推，直接產出目標點值 |
| Aitken | Pⱼ,ᵢ = Pⱼ₋₁,ⱼ + (x₀-xⱼ)(Pⱼ₋₁,ᵢ-Pⱼ₋₁,ⱼ)/(xᵢ-xⱼ) | 逐行構建，適合增量節點 |
| 自創 | q(i,k) = -1/(xᵢ₋ₖ₊₁-xᵢ)[(x₀-xᵢ₋ₖ₊₁)q(i,k-1) - (x₀-xᵢ)q(i-1,k-1)] | 改進權重因子，嘗試加速收斂 |
#define q(a,b) q[(a)*(a+1)/2 + b] // Neville/自創
#define p(a,b) q[a+1 + (b)*(b+1)/2] // Aitken 共用同一記憶體池
// 總大小：(n+2)(n+1)/2，涵蓋所有三角表neville()void neville() {
for (i=0; i<=n; i++) {
q(i,0) = f[i]; // 第 0 列：函數值
for (k=1; k<=i; k++)
q(i,k) = ((root-x[i-k])*q(i,k-1) - (root-x[i])*q(i-1,k-1)) / (x[i]-x[i-k]);
if (fabs(q(i,i) - q(i-1,i-1)) < 1e-10) break; // 對角線收斂判斷
}
if (i > n) i--;
outfile << "Neville:" << q(i,i) << endl;
}幾何意義： q(i,k) 代表通過節點 x[i-k]...x[i] 的 k 次插值多項式在 root 處的值。對角線 q(i,i) 即 n 次多項式值。
aitken()void aitken() {
for (i=1; i<=n; i++) {
p(0,i) = f[0] + (root-x[0])*(f[i]-f[0])/(x[i]-x[0]); // 線性插值基礎
for (j=1; j n) i--;
outfile << "Aitken:" << p(i-1,i) << endl;
} 優勢： 每行 i 固定節點 x[i]，逐行擴展，適合流式數據處理。
mine()void mine() {
q(0,0) = f[0];
for (i=1; i<=n; i++) {
q(i,0) = f[i];
q(i,1) = 1/(x[0]-x[i]) * ((root-x[i])*f[0] - (root-x[0])*f[i]);
for (k=2; k<=i; k++)
q(i,k) = -1/(x[i-k+1]-x[i]) * ((root-x[i-k+1])*q(i,k-1) - (root-x[i])*q(i-1,k-1));
if (fabs(q(i,i) - q(i-1,i-1)) < 1e-10) break;
}
if (i > n) i--;
outfile << "mine:" << q(i,i) << endl;
}// in.txt
4
-2 0.04
-1 0.2
0 1
1 5
2 25
0.5
// output
Neville: 2.04
Aitken: 2.04
mine: 2.04三種方法在光滑函數 f(x) = (x+2)²? 實際 f(-2)=0.04, f(-1)=0.2, f(0)=1, f(1)=5, f(2)=25 上結果一致，驗證正確性。
所有算法採用對角線差值收斂準則：
if (fabs(current - previous) < 1e-10) break;這利用了插值多項式次數增加時，若函數光滑則高次項貢獻遞減的性質。但需注意：龍格現象下高次插值可能發散，實際工程建議配合最大次數限制。
class RecursiveInterpolator {
std::vector x_, f_;
public:
double neville(double x0) const;
double aitken(double x0) const;
// 共用記憶體池優化
private:
mutable std::vector workspace_;
}; 內維爾與艾特肯算法展示了遞歸差商的優雅數學結構：將多項式插值轉化為簡單的表格填寫過程。三種實現的對比揭示了同一數學本質的不同計算圖景。對於工程實踐，Neville 算法因其對稱性與穩定性成為首選；而理解 Aitken 的增量特性與自創改進的嘗試，則能拓寬演算法設計視野。下次需要插值時，不妨嘗試手寫 Neville——它比拉格朗日公式更簡潔、更穩定、更工程化。
