Skip to content

牛頓插值多項式(Newton Polynomial)

Last Updated on 2024-08-26 by Clay

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


計算方式

1. 差商計算

對於一組資料輸入 x_{0}, x_{1},\ ..., x_{n} 和其對應的值 y_{0}, y_{1},\ ..., y_{n},第一階差商為定義為:

f[x_{i}, x_{j}] = \frac{f(x_{j})-f(x_{i})}{x_{j}-x_{i}}

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

f[x_{i}, x_{i+1},\ ..., x_{j}]=\frac{f[x_{i+1},\ ..., x_{j}]-f[x_{i},\ ..., x_{j-1}]}{x_{j}-x_{i}}


2. 建立插值多項式

之後,我們可以使用計算出的差商來建構一個多項式 P(x)

\displaystyle P(x)=f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+...


3. 計算新的內插值

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

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

有一個比較奇怪的案例是龍格現象(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


Read More

Tags:

Leave a Reply