牛頓插值多項式（Newton Polynomial）

Last Updated on 2024-08-26 by Clay

牛頓內插法是一種多項式的插值方法，使用多筆數據建構一組多項式函數，其優點在於隨著資料的添加，牛頓內插法不需要從頭開始計算，而是可以基於現有的函數進行擴展。

---

計算方式

1. 差商計算

對於一組資料輸入 和其對應的值 ，第一階差商為定義為：

而更高階的差商則需要遞迴求解：

2. 建立插值多項式

之後，我們可以使用計算出的差商來建構一個多項式 ：

3. 計算新的內插值

使用此多項式 ，我們可以計算任何 的插值，即便 不是原始資料集中的一部分；當然，我們原始的資料集越多，我們插值的誤差就越小。

這種內插的方式可以在有更多資料時，在多項式中添加新的資料點，無須重新計算之前的係數；然而，當資料非常多時，差商表的計算需求和儲存量也會增加。

有一個比較奇怪的案例是龍格現象(Rouge's phenomenon)，是在多項式插值中的一個註明問題，尤其是在等距選擇資料點進行高階多項式插值時，即使函數本身非常平滑，多項式在區間邊緣的近似誤差也會顯著增加，在區間的端點產生劇烈震盪。

---

程式實作

以下是一個 Python 的內插實現。

from typing import List


def divided_diff(x: List[float], y: List[float]) -> List[float]:
    """Calculate the divided difference table"""
    n = len(y)
    coef = y[:]
    for j in range(1, n):
        for i in range(n-1, j-1, -1):
            coef[i] = (coef[i] - coef[i-1]) / (x[i] - x[i-j])
    return coef

def newton_interpolate(x: List[float], y: List[float], x_value: float) -> float:
    """Calculate the interpolation at x_value"""
    coef = divided_diff(x, y)
    n = len(x) - 1
    p = coef[n]
    for k in range(1, n+1):
        p = coef[n-k] + (x_value - x[n-k]) * p
    return p

# Given points
x = [-1, 1, 2, 4]
y = [-2, 6, 7, 93]

# Calculate the interpolation at x=3
x_value = 3
interpolated_value = newton_interpolate(x, y, x_value)

print(f"The interpolation result at x={x_value} is: {interpolated_value}")

Output:

The interpolation result at x=3 is: 30.0

---

References

• Wikipedia - Newton Polynomial
• 牛頓插值多項式：拉格朗日怎麼說？

---

Read More

奇異值分解（Singular Value Decomposition, SVD）筆記

機率密度函數 (Probability Density Function, PDF)