Newtoninterpolatie

Newtoninterpolatie is een methode voor polynomiale interpolatie die een interpolerende polynoom in Newtonvorm construeert door een gegeven set knopen en de bijbehorende functiewaarden. Als de knopen x0, x1, ..., xn zijn en de waarden f(xi) bekend, dan is de interpolerende polynoom P(x) = f[x0] + f[x0,x1](x - x0) + f[x0,x1,x2](x - x0)(x - x1) + ... + f[x0,...,xn](x - x0)...(x - x_{n-1}). Hier zijn f[xi] = f(xi) en f[xi,...,xj] de verdeelde verschillen, gedefinieerd door f[xi,...,xj] = (f[xi+1,...,xj] - f[xi,...,x_{j-1}]) / (xj - xi).

De Newtonform heeft het voordeel van incrementele opbouw: bij toevoeging van een nieuw knooppunt x_{n+1} hoeft men de huidige polynoom niet vanaf nul te herberekenen, maar kan men een nieuwe term en de benodigde verdeelde verschillen bijwerken in O(n) tijd. Evaluatie van P(x) kan efficiënt gebeuren met een Horner-achtige structuur. Newtoninterpolatie is volledig equivalent aan de Lagrange-interpolatie; beide leveren dezelfde unieke polynoom van graad ≤ n die door de gegeven punten gaat, maar de Newtonvorm is praktischer wanneer knopen worden toegevoegd of aangepast.

Toepassingen bevinden zich in numerieke analyse en gegevensmodellering, waar men discrete meetwaarden interpoleren of functies tussen knopen willen schatten. Een nadeel kan bij hoge orde interpolatie bij equidistante knopen optreden, het Runge-verschijnsel, waardoor de interpolerende polynoom grillig kan worden.