Python 實作牛頓插值多項式計算

牛頓插值多項式採用差商形式，適合逐點新增節點且不需重新計算所有係數。本文提供兩個核心函數：coeffts 計算牛頓多項式係數，evalPoly 在給定點評估多項式值，並說明演算法流程。

演算法原理

給定節點 (xData[i], yData[i])，牛頓插值多項式為：

P(x) = a[0] + a[1](x-x0) + a[2](x-x0)(x-x1) + ...

係數 a[k] 為 k 階差商，可透過遞推表格計算。

Python 實作

def evalPoly(a, xData, x):
    """評估牛頓多項式在 x 的值"""
    n = len(xData) - 1
    p = a[n]
    for k in range(1, n + 1):
        p = a[n - k] + (x - xData[n - k]) * p
    return p

def coeffts(xData, yData):
    """計算牛頓多項式係數向量 a"""
    m = len(xData)
    a = yData.copy()
    for k in range(1, m):
        a[k:m] = (a[k:m] - a[k-1]) / (xData[k:m] - xData[k-1])
    return a

使用範例

xData = [0, 1, 2, 3]
yData = [1, 2, 5, 10]  # 對應 f(x) = x^2 + 1

a = coeffts(xData, yData)
print("係數:", a)  # [1. 1. 1. 0.]

# 在 x=2.5 插值
val = evalPoly(a, xData, 2.5)
print("P(2.5) =", val)  # 7.25

優點與應用

• 新增節點時只需計算新差商，舊係數不變。
• 適合動態插值、表格查詢等場合。
• 數值穩定性優於 Lagrange 形式。

此實作簡潔高效，可直接整合至科學計算專案中。