Interpolatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Zie het artikel Voor het taalkundige begrip, zie interpolatie (literatuur)

Wanneer iemand een interpolatie uitvoert, doet hij een uitspraak over een onbekende situatie op basis van een serie bekende situaties (zoals 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. Met andere woorden, interpolatie is het uitbreiden van een reeks getallen met punten die binnen die reeks liggen en extrapolatie is het uitbreiden van een reeks getallen met punten die buiten die reeks liggen.

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.

Definitie[bewerken]

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 (xi, yi) (i = 1, 2, ...) gaat, teneinde ook voor een willekeurig ander punt x0 de bijbehorende y-waarde te kunnen vinden. Bovengenoemde voorwaarde betreffende het "domein van de bekende situaties", luidt in deze context: x0 mag niet kleiner zijn dan de kleinste xi uit de verzameling bekende punten noch groter dan de grootste xi.

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.

Lineaire interpolatie[bewerken]

voorbeeld van 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})

Interpolatiepolynomen[bewerken]

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 (xi,yi) 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 c0 t/m cm 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 (x1,y1) en (x2,y2). 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.

Lagrange-interpolatie[bewerken]

Afleiding van het Lagrange-polynoom[bewerken]

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 gj(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 gj=i(xi) gelijk moet zijn aan 1 (één) en dat alle andere gj(xi) 0 (nul) moeten zijn om de linker- en rechterkant van het =-teken identiek te houden. Oftewel: voor een zekere gj(xi) 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, xj (j = 0, 1, ..., i-1, i+1, ..., m) zijn de nulpunten van gi(x). Omdat f(x) een mde-graads polynoom is, is gi(x) dat ook. En aangezien er eveneens m bekende nulpunten zijn, is gi(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 gi(xj) = 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 gi(xj=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 gj(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})}}

De interpolatieformule van Lagrange[bewerken]

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)}

en

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})}}

Uitwerking voor twee en drie punten[bewerken]

Als controle volgt hier de uitwerking voor een geval met twee bekende punten (x1,y1) en (x2,y2):

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 (x1, y1) 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 (x1,y1), (x2,y2) en (x3,y3) 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}}