Lagrangesches Interpolationspolynom

Beschreibung

Hier suchen wir eine Polynomfunktion, die möglichst gut auf spezielle Datennpunkte passt.

Definition

Es seien $(x_i,y_i)\in K^2$ $n+1$ verschiedene Stützpunkte. (d.h. sie haben unterschiedliche $x$-Werte) Dann gibt es genau ein Polynom $f\in K[x{]}_n$ so, dass $\forall i=0,1,...,n:{ϵ}_{x_i}(f)=y_i$

${ϵ}_x(f)$ bezeichnet hier den Auswertungshomomorphismus. Das Polynom $f$, das die Eigenschaft erfüllt wird Lagrangesches Interpolationspolynom gennannt.

Der Eindeutigkeit traue ich noch nicht ganz. Wenn alle Werte die Höhe $0$ haben, dann ist die Funktion wegen Skalierung nicht mehr eindeutig. Meine Vermutung ist, dass immer ein normiertes Polynom herauskommt. Aber selbst dann gibt es mehr als ein Polynom, dass durch alle $0$-Punkte verlaufen könnte. Moment, ich gebe mich geschlagen. Die Funktion muss immer einen Grad weniger haben als es Punkte gibt. Eine Polynomfunktion, die nicht $0$ ist, kann gar nicht alle Punkt auf $0$ einfangen.

Lagrangesches Basispolynom

Siehe Lagrangesches Basispolynom

Lagrangesches Interpolationspolynom

Das Lagrangesches Interpolationspolynom errechnet sich durch $f:={\sum }_{j=0}^n{y}_j{L}_j\text{ mit }{L}_j:={\prod }_{i=0,j\ne i}^n\frac{x-x_i}{x_j-x_i}$

Die Idee ist dass wir eine Funktion $y_i{L}_i$ konstruieren, die bei $x_i$ den Wert $y_i$ hat aber bei allen anderen $x_j$ den Wert $0$.

Q: Lagrangesches Interpolationspolynom A: (f := \sum_{j = 0}^n y_jL_j)

Eigenschaften

Komplexität

Durch obere Berechnung können wir ein Polynom in $O(n)$ Schritten aufbauen.

Kennen wir bereits das Interpolationspolynom, können wir um einen neuen Punkt hinzufügen. Das Hinzufügen kostet $O(n)$.