Interpolatie

Uit Wikipedia, de vrije encyclopedie

Wanneer iemand een interpolatie uitvoert, doet hij een uitspraak over een onbekende situatie op basis van een serie bekende situaties (c.q. waarnemingen of metingen) door aan te nemen dat er een verband tussen al die situaties bestaat. Voorwaarde om over interpolatie te spreken in plaats van over extrapolatie is dat de onbekende situatie zich binnen het domein van die bekende situaties bevindt.

Bijvoorbeeld: als u om 14:00 uur een fietstocht begint en na 2 uur volgens uw fietscomputer 40 km heeft afgelegd, kunt u afleiden dat u om 15:00 uur (toen u was vergeten op uw fietscomputer te kijken) zo'n 20 km had afgelegd. Daarbij heeft u dus aangenomen dat u met een constante snelheid heeft gefietst en zo bent u tot de eenvoudige relatie tussen verstreken tijd en afgelegde afstand gekomen. De schatting voor 15:00 uur is een interpolatie op basis van de bekende start- en finishtijd.

[bewerk] Definitie

Meer wiskundig uitgedrukt is een interpolatie in een tweedimensionaal probleem (in een x,y-assenstelsel) de techniek om een functie te vinden die door een aantal bekende coördinatenparen (x_i, y_i) (i = 1, 2, ...) gaat, teneinde ook voor een willekeurig ander punt x₀ de bijbehorende y-waarde te kunnen vinden. Bovengenoemde voorwaarde betreffende het "domein van de bekende situaties", luidt in deze context: x₀ mag niet kleiner zijn dan de kleinste x_i uit de verzameling bekende punten noch groter dan de grootste x_i.

De eerste en meest wezenlijke stap is het vinden van een functievoorschrift f dat een verband tussen x- en y-waarden legt:

y = f (x)

, waarbij

y i = f (x i)

voor alle i = 1, 2, ...

De triviale tweede stap is het bepalen van de onbekende y-waarde, wat heel eenvoudig kan met: $y 0 = f (x 0)$ .

Opmerking: Hier wordt gesproken van een functie die exact door alle bekende punten gaat; een "goede benadering" (of best fit) van die punten is dus niet voldoende.

[bewerk] Lineaire interpolatie

De eerder beschreven fietstocht is een voorbeeld van lineaire interpolatie. Daarvoor zijn precies twee bekende punten nodig en is voor elke x-waarde tussen beide uitersten een y-waarde te berekenen met

$y = f(x) = y_{1} + \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \cdot (x - x_{1})$

of met dit gelijkwaardige alternatief

$y = f(x) = y_{2} + \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \cdot (x - x_{2})$

[bewerk] Interpolatiepolynomen

Lineaire interpolatie is het eenvoudigste geval van interpoleren met behulp van een polynoom; het polynoom is daarin van de eerste graad. In het algemeen kan met stellen dat men voor m+1 bekende punten een uniek polynoom van de graad m kan vinden die door al deze punten gaat. Als de bekende punten (x_i,y_i) zijn, met i = 0, 1, 2, ..., m, dan wordt het functievoorschrift van het polynoom:

$y = f(x) = c_{0} + c_{1} x + c_{2} x^{2} + ... + c_{m} x^{m} \,\!$

Aangezien f(x) door alle bekende punten gaat, is het volgende stelsel van m vergelijkingen geldig:

$\begin{matrix} y_{0} = c_{0} + c_{1} x_{0} + c_{2} x_{0}^{2} + ... + c_{m} x_{0}^{m} \\ y_{1} = c_{0} + c_{1} x_{1} + c_{2} x_{1}^{2} + ... + c_{m} x_{1}^{m} \\ y_{2} = c_{0} + c_{1} x_{2} + c_{2} x_{2}^{2} + ... + c_{m} x_{2}^{m} \\ \ldots \\ y_{m} = c_{0} + c_{1} x_{m} + c_{2} x_{m}^{2} + ... + c_{m} x_{m}^{m} \end{matrix}$

Om het functievoorschrift eenduidig vast te leggen, dienen de waarden van de coëfficiënten c₀ t/m c_m berekend te worden. Dit zijn m+1 onbekenden die uit een stelsel van m+1 vergelijkingen moeten worden gehaald. Dit probleem is dus in principe oplosbaar.

Voor het lineaire geval is deze werkwijze goed te demonstreren: stel de bekende punten zijn (x₁,y₁) en (x₂,y₂). Het functievoorschrift is van de vorm

$y = f(x) = c_{0} + c_{1} x \,\!$

en het stelsel vergelijkingen voor de bekende punten:

$\begin{matrix} y_{1} = c_{0} + c_{1} x_{1} \\ y_{2} = c_{0} + c_{1} x_{2} \end{matrix}$

Trek de eerste vergelijking van de tweede af om het volgende te krijgen:

$y_{2} - y_{1} = c_{1} \cdot (x_{2} - x_{1})$

Hieruit volgt natuurlijk dat

$c_{1} = \frac{y_{2}-y_{1}}{x_{2}-x_{1}}$

en wanneer dit gesubstitueerd wordt in een van de vergelijkingen uit het stelsel hierboven:

$c_{0} = y_{1} - c_{1} x_{1} = y_{1} - \frac{y_{2}-y_{1}}{x_{2}-x_{1}} x_{1}$

Kortom, het functievoorschrift luidt:

$f(x) = c_{0} + c_{1} x = y_{1} - \frac{y_{2}-y_{1}}{x_{2}-x_{1}} x_{1} + \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \cdot x = y_{1} + \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \cdot (x - x_{1})$

wat zoals verwacht precies overeenkomt met de functie uit de vorige paragraaf.

[bewerk] Lagrange-interpolatie

[bewerk] Afleiding van het Lagrange-polynoom

Hoe meer punten gebruikt worden voor het construeren van een integratiepolynoom, des te ingewikkelder wordt het stelsel vergelijkingen dat opgelost moet worden om de coëfficiënten van de polynoom te bepalen. De methode van Lagrange biedt in dergelijke gevallen uitkomst.

Ter herinnering: de functie f(x) moet in de bekende punten voldoen aan

$\begin{matrix}y_{0} = f(x_{0}) \\ y_{1} = f(x_{1}) \\ y_{2} = f(x_{2}) \\ \ldots \\ y_{m} = f(x_{m}) \end{matrix}$

Het functievoorschrift van f(x) zou nu ook als volgt geschreven kunnen worden:

$f(x) = y_{0} \cdot g_{0}(x) + y_{1} \cdot g_{1}(x) + y_{2} \cdot g_{2}(x) + \ldots + y_{m} \cdot g_{m}(x)$

Hierin zijn m+1 nieuwe functies g_j(x) geïntroduceerd. Dit lijkt de situatie gecompliceerder te maken, maar deze functies zijn gemakkelijk af te leiden. Wordt de nieuwe formulering voor f(x) namelijk gebruikt in een willekeurige voorwaarde i, dan ontstaat:

$y_{i} = f(x_{i}) = y_{0} \cdot g_{0}(x_{i}) + y_{1} \cdot g_{1}(x_{i}) + \ldots + y_{i} \cdot g_{i}(x_{i}) + \ldots + y_{m} \cdot g_{m}(x_{i})$

Het moge duidelijk zijn dat g_j=i(x_i) gelijk moet zijn aan 1 (één) en dat alle andere g_j(x_i) 0 (nul) moeten zijn om de linker- en rechterkant van het =-teken identiek te houden. Oftewel: voor een zekere g_j(x_i) geldt

$\begin{matrix}g_{j}(x_{i}) = 1 \mbox{ voor } j = i \\ g_{j}(x_{i}) = 0 \mbox{ voor } j \not= i \end{matrix}$

Omdat er m van zulke voorwaarden zijn, kun je ook zeggen:

$\begin{matrix}g_{i}(x_{j}) = 1 \mbox{ voor } j = i \\ g_{i}(x_{j}) = 0 \mbox{ voor } j \not= i \end{matrix}$

Met andere woorden, x_j (j = 0, 1, ..., i-1, i+1, ..., m) zijn de nulpunten van g_i(x). Omdat f(x) een m^de-graads polynoom is, is g_i(x) dat ook. En aangezien er eveneens m bekende nulpunten zijn, is g_i(x) snel gevonden:

$g_{i}(x) = C \cdot (x - x_{0}) \cdot (x - x_{1}) \cdot \ldots \cdot (x - x_{i-1}) \cdot (x - x_{i+1}) \cdot \ldots \cdot (x - x_{m})$

waarin C een nog onbekende factor is. Het is echter al duidelijk te zien dat g_i(x_j) = 0 wanneer i ongelijk aan j is, ongeacht de waarde van C. Maar wat is de waarde van C dan? Die volgt uit de eerste voorwaarden die aan deze functie werd gesteld, namelijk dat g_i(x_j=i) = 1:

$g_{i}(x_{i}) = C \cdot (x_{i} - x_{0}) \cdot (x_{i} - x_{1}) \cdot \ldots \cdot (x_{i} - x_{i-1}) \cdot (x_{i} - x_{i+1}) \cdot \ldots \cdot (x_{i} - x_{m}) = 1$

waaruit volgt dat

$C = \frac{1}{(x_{i} - x_{0}) \cdot (x_{i} - x_{1}) \cdot \ldots \cdot (x_{i} - x_{i-1}) \cdot (x_{i} - x_{i+1}) \cdot \ldots \cdot (x_{i} - x_{m})}$

Dit geeft het Lagrange-polynoom, de functie g_j(x):

$g_{i}(x) = \frac{(x - x_{0}) \cdot (x - x_{1}) \cdot \ldots \cdot (x - x_{i-1}) \cdot (x - x_{i+1}) \cdot \ldots \cdot (x - x_{m})}{(x_{i} - x_{0}) \cdot (x_{i} - x_{1}) \cdot \ldots \cdot (x_{i} - x_{i-1}) \cdot (x_{i} - x_{i+1}) \cdot \ldots \cdot (x_{i} - x_{m})}$

$g_{i}(x) = \prod_{j=0,j \not= i}^{m}{\frac{(x - x_{j})}{(x_{i} - x_{j})}}$

[bewerk] De interpolatieformule van Lagrange

De belangrijkste vergelijkingen uit voorgaande afleiding zijn:

$f(x) = y_{0} \cdot g_{0}(x) + y_{1} \cdot g_{1}(x) + y_{2} \cdot g_{2}(x) + \ldots + y_{m} \cdot g_{m}(x) = \sum_{i=0}^{m}{y_{i} \cdot g_{i}(x)}$

$g_{i}(x) = \prod_{j=0,j \not= i}^{m}{\frac{(x - x_{j})}{(x_{i} - x_{j})}}$

De samenvoeging hiervan is de interpolatieformule van Lagrange:

$f(x) = \sum_{i=0}^{m}{\left \{ y_{i} \cdot \prod_{j=0,j \not= i}^{m}{\frac{(x - x_{j})}{(x_{i} - x_{j})}}\right \} }$

Een alternatieve en meer bekende schrijfwijze haalt de hulp van een extra functie h(x) erbij:

$h(x) = \prod_{j=0}^{m}{x-x_{j}}$

$f(x) = \sum_{i=0}^{m}{y_{i} \cdot \frac{h(x)}{(x - x_{i})h'(x_{i})}}$

[bewerk] Uitwerking voor twee en drie punten

Als controle volgt hier de uitwerking voor een geval met twee bekende punten (x₁,y₁) en (x₂,y₂):

$f(x) = \sum_{i=1}^{2}{\{y_{i} \cdot \prod_{j=1,j \not= i}^{2}{\frac{(x - x_{j})}{(x_{i} - x_{j})}}\}} = y_{1} \cdot \frac{x-x_{2}}{x_{1}-x_{2}} + y_{2} \cdot \frac{x-x_{1}}{x_{2}-x_{1}} = \frac{x-x_{1}}{x_{2}-x_{1}}y_{2} - \frac{x-x_{2}}{x_{2}-x_{1}}y_{1}$

met een handige herschikking van termen krijgt dit een bekender gezicht:

$f(x) = \frac{(y_{2}-y_{1})(x-x_{1})-x_{1}y_{1}+x_{2}y_{1}}{x_{2}-x_{1}} = \frac{y_{2}-y_{1}}{x_{2}-x_{1}} \cdot (x - x_{1}) + y_{1}$

De juistheid van de alternatieve formulering van Lagranges formule is voor een interpolatie tussen twee punten (x₁, y₁) ook snel aangetoond:

$h(x) = \prod_{j=0}^{m}{x-x_{j}} = (x - x_{1})(x - x_{2})$

$h'(x) = \frac{d(x - x_{1})}{dx}(x - x_{2}) + (x - x_{1}) \frac{d(x - x_{2})}{dx} = (x - x_{2}) + (x - x_{1})$

$\begin{matrix} f(x) & = & \sum_{i=0}^{m}{y_{i} \cdot \frac{h(x)}{(x - x_{i})h'(x_{i})}} & \ \\ \ & = & y_{1}\frac{(x - x_{1})(x - x_{2})}{(x - x_{1})(x_{1} - x_{2})} + y_{2}\frac{(x - x_{1})(x - x_{2})}{(x - x_{2})(x_{2} - x_{1})} & = y_{1}\frac{x - x_{2}}{x_{1} - x_{2}} + y_{2}\frac{x - x_{1}}{x_{2} - x_{1}}\end{matrix}$

Voor drie punten (x₁,y₁), (x₂,y₂) en (x₃,y₃) nu:

$f(x) = y_{1} \cdot \frac{x-x_{2}}{x_{1}-x_{2}} \cdot \frac{x-x_{3}}{x_{1}-x_{3}} + y_{2} \cdot \frac{x-x_{1}}{x_{2}-x_{1}} \cdot \frac{x-x_{3}}{x_{2}-x_{3}} + y_{3} \cdot \frac{x-x_{1}}{x_{3}-x_{1}} \cdot \frac{x-x_{2}}{x_{3}-x_{2}}$