WikiDer > Interpolation

Interpolatie

Zum sprachlichen Verständnis siehe Interpolation (Literatur)

Interpolation ist die Ableitung neuer Datenpunkte innerhalb des Bereichs eines Satzes bekannter diskreter Datenpunkte unter Annahme einer gewissen Beziehung zwischen diesen Punkten. Das unterscheidet es von Extrapolation wo die unbekannte Situation außerhalb der Domain dieser vertrauten Situationen. Mit anderen Worten, Interpolation ist die Erweiterung einer Reihe von Zahlen um Punkte, die innerhalb dieser Reihe liegen und Extrapolation ist die Erweiterung einer Reihe von Zahlen mit Punkten außerhalb dieser Reihe.

Zum Beispiel: Wenn eine Radtour um 14:00 Uhr beginnt und nach 2 Stunden gemäß der Fahrradcomputer 40 km zurückgelegt worden sind, dann kann man davon ausgehen, dass um 15:00 Uhr etwa 20 km zurückgelegt wurden. Die Annahme hier ist, dass es eine konstante Fahrradgeschwindigkeit gab, eine einfache Beziehung zwischen verstrichener Zeit und zurückgelegter Strecke. Die Schätzung für 15:00 ist eine Interpolation basierend auf der bekannten Start- und Endzeit.

Definition

Mathematisch gesprochen ist eine Interpolation in a zweidimensional Problem (in a ${Anzeigestil x,y}$ -Koordinatensystem) die Technik, eine Funktion zu finden, die durch eine Anzahl bekannter Koordinatenpaare gegeben ist ${Anzeigestil (x_{i},y_{i}),i=1,2,ldots,n}$ geht, damit auch für jeden anderen punkt ${displaystyle x_{0}}$ die entsprechende ${Anzeigestil y}$ Wert zu finden. Die obige Bedingung bezüglich des Bereichs bekannter Situationen lautet in diesem Zusammenhang: ${displaystyle x_{0}}$ darf nicht kleiner als das kleinste sein ${displaystyle x_{i}}$ aus der Menge der bekannten Punkte, nicht größer als der größte ${displaystyle x_{i}}$ .

Der erste und wichtigste Schritt besteht darin, a zu finden Jobbeschreibung ${displaystyle f}$ dass eine Verbindung zwischen ${Anzeigestil x}$ - und ${Anzeigestil y}$ -Werte erklärt:

{Anzeigestil y=f(x)}

, bei welchem

{Anzeigestil y_{i}=f(x_{i})}

für alle

{displaystyle i=1,2,ldots,n}

Der triviale zweite Schritt besteht darin, die Unbekannte zu bestimmen ${Anzeigestil y}$ Wert, was sehr einfach gemacht werden kann mit: ${displaystyle y_{0}=f(x_{0}).}$

Hinweis: Dies ist eine Funktion, die alle bekannten Punkte exakt durchläuft; eine gute Näherung (oder beste Passform) dieser Punkte ist daher nicht ausreichend.

Lineare Interpolation

Beispiel für lineare Interpolation

Die zuvor beschriebene Radtour ist ein Beispiel für eine lineare Interpolation. Dies erfordert genau zwei bekannte Punkte und für jeden ${Anzeigestil x}$ -Wert zwischen beiden Extremen a ${Anzeigestil y}$ -Wert zu berechnen mit

{displaystyle y=f(x)=y_{1} {frac {y_{2}-y_{1}}{x_{2}-x_{1}}}cdot (x-x_{1})}

oder mit dieser gleichwertigen Alternative

{displaystyle y=f(x)=y_{2} {frac {y_{2}-y_{1}}{x_{2}-x_{1}}}cdot (x-x_{2})}

Interpolationspolynome

Lineare Interpolation ist der einfachste Fall der Interpolation mit a Polynom; das Polynom darin ist ersten Grades. Generell kann man sagen, dass für ${displaystyle m1}$ bekannte Punkte ein eindeutiges Polynom des Grades ${displaystyle m}$ eine, die alle diese Punkte durchläuft. Wenn die bekannten Punkte ${Anzeigestil (x_{i},y_{i})}$ mit jemanden sein ${displaystyle i=1,2,ldots ,m,}$ dann lautet die Funktionsregel des Polynoms:

{displaystyle y=f(x)=c_{0} c_{1}x c_{2}x^{2} ldots c_{m}x^{m}}

Schon seit ${Anzeigestil f(x)}$ geht durch alle bekannten Punkte, das folgende System von ${displaystyle m}$ Gleichungen gültig:

{displaystyle { egin{matrix}y_{0}=c_{0} c_{1}x_{0} c_{2}x_{0}^{2} ldots c_{m}x_{0}^{m}/ y_{1}=c_{0} c_{1}x_{1} c_{2}x_{1}^{2} ldots c_{m}x_{1}^{m}/y_{2}=c_{ 0} c_{1}x_{2} c_{2}x_{2}^{2} ldots c_{m}x_{2}^{m}/ldots /y_{m}=c_{0} c_{1 }x_{m} c_{2}x_{m}^{2} ldots c_{m}x_{m}^{m}end{matrix}}}

Um die Funktionsregel eindeutig zu bestimmen, müssen die Werte der Koeffizienten ${displaystyle c_{0},ldots ,c_{m}}$ berechnet werden. Diese sind ${displaystyle m1}$ Unbekannte, die aus einem System von ${displaystyle m1}$ Vergleiche müssen gemacht werden. Dieses Problem ist daher prinzipiell lösbar.

Für den linearen Fall ist diese Methode leicht zu demonstrieren: Angenommen, die bekannten Punkte sind ${displaystyle (x_{1},y_{1})}$ und ${Anzeigestil (x_{2},y_{2})}$ . Die Funktionsanweisung hat die Form

{displaystyle y=f(x)=c_{0} c_{1}x}

und das Gleichungssystem für die bekannten Punkte:

{displaystyle { egin{matrix}y_{1}=c_{0} c_{1}x_{1}/y_{2}=c_{0} c_{1}x_{2}end{matrix}}}

Die Lösung ist:

{displaystyle c_{1}={frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}

{displaystyle c_{0}=y_{1}-{frac {y_{2}-y_{1}}{x_{2}-x_{1}}}x_{1}}

Die Stellenbeschreibung lautet also:

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

was erwartungsgemäß genau der Funktion aus dem vorigen Abschnitt entspricht.

Lagrange-Interpolation

Ableitung des Lagrange-Polynoms

Je mehr Punkte verwendet werden, um ein Integrationspolynom zu konstruieren, desto komplexer wird das Gleichungssystem, das gelöst werden muss, um die Koeffizienten des Polynoms zu bestimmen. Die Methode von Lagrange bietet in solchen Fällen eine Lösung.

Zur Erinnerung: die Funktion ${Anzeigestil f(x)}$ muss sich in den bekannten Punkten treffen

{displaystyle { egin{matrix}y_{0}=f(x_{0})/y_{1}=f(x_{1})/y_{2}=f(x_{2})/vdots /y_{ m}=f(x_{m})ende{array}}}

Die Stellenbeschreibung von ${Anzeigestil f(x)}$ könnte jetzt auch so geschrieben werden:

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

In diesem sind ${displaystyle m1}$ neue Funktionen ${displaystyle g_{j}(x)}$ eingeführt. Dies scheint die Situation zu verkomplizieren, aber diese Merkmale sind leicht abzuleiten. Ist der neue Wortlaut für ${Anzeigestil f(x)}$ nämlich in jedem Zustand verwendet ${Anzeigestil i,}$ dann ergibt sich:

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

Es mag klar sein, dass ${Displaystil g_{i}(x_{i})=1}$ und das alle anderen ${Anzeigestil g_{j}(x_{i})=0}$ um die linke und rechte Seite des =-Zeichens identisch zu halten. Mit anderen Worten, für eine gewisse ${displaystyle g_{j}(x_{i})}$ gilt

{displaystyle { egin{matrix}g_{i}(x_{i})=1/g_{j}(x_{i})=0{mbox{ for }}jeq iend{matrix}}}

Weil da ${displaystyle m}$ von solchen Bedingungen kann man auch sagen:

{displaystyle { egin{matrix}g_{i}(x_{i})=1/g_{i}(x_{j})=0{mbox{ for }}jeq iend{matrix}}}

Mit anderen Worten: ${displaystyle x_{j}(j=0,1,ldots ,i-1,i 1,ldots,m)}$ sind die Nullen von ${Anzeigestil g_{i}(x).}$ weil ${Anzeigestil f(x)}$ ein ${displaystyle m}$ ist das Gradpolynom is ${displaystyle g_{i}(x)}$ das auch. Und da gibt es auch ${displaystyle m}$ sind bekannte Nullstellen, ist ${displaystyle g_{i}(x)}$ Schnell gefunden:

{displaystyle g_{i}(x)=Ccdot (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})}

in welchem ${Anzeigestil C}$ ist ein unbekannter Faktor. Das ist aber schon klar ${Anzeigestil g_{i}(x_{j})=0}$ wenn ${displaystyle ieq j}$ ist unabhängig vom Wert von ' ${Anzeigestil C.}$ Aber was ist der Wert von ${Anzeigestil C}$ als? Dies folgt aus den ersten Bedingungen, die an diese Position gestellt werden, nämlich dass namelijk ${Anzeigestil g_{i}(x_{j})=1.}$

{displaystyle g_{i}(x_{i})=Ccdot (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}

woraus folgt, dass

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

Das gibt dem Lagrange-Polynom, die Funktion ${displaystyle g_{j}(x)}$

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

{displaystyle g_{i}(x)=prod_{j=0,jeq i}^{m}{frac {x-x_{j}}{x_{i}-x_{j}}}}

Interpolationsformel von Lagrange

Die wichtigsten Gleichungen aus der vorherigen Herleitung sind:

{displaystyle 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)=Summe _{i=0}^{m}{y_{i}cdot g_{i}(x)}}

und

{displaystyle g_{i}(x)=prod_{j=0,jeq i}^{m}{frac {x-x_{j}}{x_{i}-x_{j}}}}

Die Kombination dieser ist die Interpolationsformel von Lagrange:

{displaystyle f(x)=sum _{i=0}^{m}left{y_{i}cdot prod _{j=0,jeq i}^{m}{frac {x-x_{j}}{ x_{i}-x_{j}}}Nacht}}

Eine alternative und vertrautere Schreibweise benötigt eine zusätzliche Funktion h(x) damit:

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

{displaystyle f(x)=sum _{i=0}^{m}y_{i}cdot {frac {h(x)}{(x-x_{i})h'(x_{i})}} }

Ausarbeitung für zwei und drei Punkte

Zur Kontrolle hier die Ausarbeitung für einen Fall mit zwei bekannten Punkten ${displaystyle (x_{1},y_{1})}$ und ${Anzeigestil (x_{2},y_{2}):}$

{displaystyle f(x)=sum _{i=1}^{2}left{y_{i}cdot prod _{j=1,jeq i}^{2}{frac {x-x_{j}}{ x_{i}-x_{j}}}ight}=y_{1}cdot {frac {x-x_{2}}{x_{1}-x_{2}}} y_{2}cdot {frac {x -x_{1}}{x_{2}-x_{1}}}}

Mit einer praktischen Neuordnung von Begriffen nimmt dies ein vertrauteres Gesicht an:

{displaystyle 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}}

Die Richtigkeit der alternativen Formulierung der Lagrange-Formel ist für eine Interpolation zwischen zwei Punkten ${displaystyle (x_{1},y_{1})}$ auch schnell bewiesen: