In der numerischen Analyse werden Polynome von Lagrange für die polynomische Interpolation verwendet. Für einen gegebenen Satz von verschiedenen Punkten und Zahlen ist das Polynom von Lagrange das Polynom von kleinstem Grad, der an jedem Punkt den entsprechenden Wert annimmt (d. h. die Funktionen an jedem Punkt zusammenfallen). Das interpolierende Polynom von kleinstem Grad ist jedoch einzigartig, und es ist deshalb passender, von "der Form von Lagrange" dieses einzigartigen Polynoms aber nicht "des Interpolationspolynoms von Lagrange zu sprechen," da dasselbe Polynom durch vielfache Methoden erreicht werden kann. Obwohl genannt, nach Joseph Louis Lagrange wurde es zuerst 1779 von Edward Waring entdeckt und 1783 von Leonhard Euler wieder entdeckt.

Interpolation von Lagrange ist gegen das Phänomen von Runge und die Tatsache empfindlich, dass das Ändern der Interpolationspunkte verlangt, das Wiederrechnen des kompletten interpolant kann Polynome von Newton leichter machen zu verwenden. Polynome von Lagrange werden in der Methode von Newton-Ställen der numerischen Integration und im heimlichen Teilen von Shamir des Schemas in der Geheimschrift verwendet.

Definition

In Anbetracht einer Reihe von k + 1 Datenpunkte

:

wo keine zwei dasselbe sind, ist das Interpolationspolynom in der Form von Lagrange eine geradlinige Kombination

:

Basispolynome von Lagrange

:

Bemerken Sie, wie, in Anbetracht der anfänglichen Annahme, dass keine zwei dasselbe sind, so ist dieser Ausdruck immer bestimmt. Der Grund, der Paaren damit nicht erlaubt wird, besteht darin, dass keine Interpolation solch fungiert, der bestehen würde; eine Funktion kann nur einen Wert für jedes Argument bekommen. Andererseits, wenn auch, dann würden jene zwei Punkte wirklich ein einzelner Punkt sein.

Für alle, schließt den Begriff in den Zähler ein, so wird das ganze Produkt Null sein an:

:

Andererseits,

:

Mit anderen Worten sind alle Basispolynome Null an, außer, weil sie am Begriff Mangel hat.

Hieraus folgt dass, so an jedem Punkt, das zeigend, interpoliert die Funktion genau.

Beweis

Funktion L (x) gesucht werden ist ein Polynom in von kleinstem Grad, der die gegebene Datei interpoliert; d. h. nimmt Wert beim Entsprechen für alle Datenpunkte an:

:

Bemerken Sie dass:

1. In gibt ihm K-Begriffe im Produkt, und jeder Begriff enthält einen x, so muss L (x) (der eine Summe dieser K-Grad-Polynome ist) auch ein K-Grad-Polynom sein.

\prod_ {M

0, \, m\neq j\^ {k} \frac {x_i-x_m} {x_j-x_m }\

</Mathematik>

Beobachten Sie, was geschieht, wenn wir dieses Produkt ausbreiten. Weil das Produkt, hüpft

Wenn dann alle Begriffe sind (außer, wo, aber dieser Fall, ist wie hingewiesen, in der Definitionsabteilung---unmöglich, wenn Sie versucht haben, diesen Begriff auszuschreiben, Sie dass und seitdem, gegen finden würden).

Auch wenn dann seitdem es nicht ausschließt, wird ein Begriff im Produkt für, d. h., zeroing das komplette Produkt sein. So

= \delta_ {ji} = \begin {Fälle}

1, & \text {wenn} j=i \\

0, & \text {wenn} j \ne i \end {Fälle }\

</Mathematik>

wo das Delta von Kronecker ist. So:

:

So ist die Funktion L (x) ein Polynom mit dem Grad am grössten Teil von k und wo.

Zusätzlich ist das interpolierende Polynom, wie gezeigt, durch den unisolvence Lehrsatz an der Polynomischen Interpolation einzigartig.

Hauptidee

Das Beheben eines Interpolationsproblems führt zu einem Problem in der geradlinigen Algebra, wo wir eine Matrix lösen müssen. Mit einer Standardmonom-Basis für unser Interpolationspolynom bekommen wir die Matrix von Vandermonde. Indem wir eine andere Basis, die Basis von Lagrange wählen, bekommen wir die viel einfachere Identitätsmatrix = &delta; den wir sofort lösen können: Die Basis von Lagrange kehrt die Matrix von Vandermonde um.

Dieser Aufbau ist dasselbe als der chinesische Rest-Lehrsatz. Anstatt für Reste von ganzen Zahlen modulo Primzahlen zu überprüfen, überprüfen wir für Reste von Polynomen, wenn geteilt, durch linears.

Beispiele

Beispiel 1

Finden Sie eine Interpolationsformel für (x) ƒ = Lohe (x) gegeben dieser Satz bekannter Werte:

:

\begin {richten }\aus

x_0 & =-1.5 & & & & & f (x_0) & =-14.1014 \\

x_1 & =-0.75 & & & & & f (x_1) & =-0.931596 \\

x_2 & = 0 & & & & & f (x_2) & = 0 \\

x_3 & = 0.75 & & & & & f (x_3) & = 0.931596 \\

x_4 & = 1.5 & & & & & f (x_4) & = 14.1014.

\end {richten }\aus</Mathematik>

Die Basispolynome sind:

:

= {1\over 243} x (2x-3) (4x-3) (4x+3) </Mathematik>

:

= {} - {8\over 243} x (2x-3) (2x+3) (4x-3) </Mathematik>

:

= {3\over 243} (2x+3) (4x+3) (4x-3) (2x-3) </Mathematik>

:

= - {8\over 243} x (2x-3) (2x+3) (4x+3) </Mathematik>

:

= {1\over 243} x (2x+3) (4x-3) (4x+3). </Mathematik>

So ist das interpolierende Polynom dann

:

& {} \qquad {} - 8f (x_1) x (2x-3) (2x+3) (4x-3) \\

& {} \qquad {} + 3f (x_2) (2x+3) (4x+3) (4x-3) (2x-3) \\

& {} \qquad {} - 8f (x_3) x (2x-3) (2x+3) (4x+3) \\

& {} \qquad {} + f (x_4) x (2x+3) (4x-3) (4x+3) \Big) \\

& = 4.834848x^3 - 1.477474x.

\end {richten} </Mathematik> {aus}

Beispiel 2

Wir möchten (x) ƒ = x über die Reihe 1  x  3, in Anbetracht dieser drei Punkte interpolieren:

: \begin {richten }\aus

x_0 & = 1 & & & f (x_0) & = 1 \\

x_1 & = 2 & & & f (x_1) & = 4 \\

x_2 & = 3 & & & f (x_2) & =9.

\end {richten }\aus</Mathematik>

Das interpolierende Polynom ist:

:

L (x) &= {1 }\\cdot {x - 2 \over 1 - 2 }\\cdot {x - 3 \over 1 - 3} + {4 }\\cdot {x - 1 \over 2 - 1 }\\cdot {x - 3 \over 2 - 3} + {9 }\\cdot {x - 1 \over 3 - 1 }\\cdot {x - 2 \over 3 - 2} \\[10pt]

&= x^2.

\end {richten} </Mathematik> {aus}

Beispiel 3

Wir möchten (x) ƒ = x über die Reihe 1  x  3, in Anbetracht dieser 3 Punkte interpolieren:

Das interpolierende Polynom ist::

L (x) &= {1 }\\cdot {x - 2 \over 1 - 2 }\\cdot {x - 3 \over 1 - 3} + {8 }\\cdot {x - 1 \over 2 - 1 }\\cdot {x - 3 \over 2 - 3} + {27 }\\cdot {x - 1 \over 3 - 1 }\\cdot {x - 2 \over 3 - 2} \\[8pt]

&= 6x^2 - 11x + 6.

\end {richten} </Mathematik> {aus}

Referenzen

Die Lagrange-Form des Interpolationspolynoms zeigt den geradlinigen Charakter der polynomischen Interpolation und die Einzigartigkeit des Interpolationspolynoms. Deshalb wird es in Beweisen und theoretischen Argumenten bevorzugt. Einzigartigkeit kann auch vom invertibility der Matrix von Vandermonde wegen des Nichtverschwindens der Determinante von Vandermonde gesehen werden.

Aber, wie vom Aufbau, jedes Mal ein Knoten x Änderungen gesehen werden kann, müssen alle Basispolynome von Lagrange wiederberechnet werden. Eine bessere Form des Interpolationspolynoms für den praktischen (oder rechenbetont) Zwecke ist die Barycentric-Form der Interpolation von Lagrange (sieh unten) oder Polynome von Newton.

Lagrange und andere Interpolation an Punkten ebenso unter Drogeneinfluss, als im Beispiel oben, geben ein Polynom nach, das oben und unter der wahren Funktion schwingt. Dieses Verhalten neigt dazu, mit der Zahl von Punkten zu wachsen, zu einer als das Phänomen von Runge bekannten Abschweifung führend; das Problem kann durch die Auswahl von Interpolationspunkten an Knoten von Tschebyscheff beseitigt werden.

Die Lagrange Basispolynome können in der numerischen Integration verwendet werden, um die Formeln von Newton-Ställen abzuleiten.

Interpolation von Barycentric

Das Verwenden

:

wir können die Basispolynome von Lagrange als umschreiben

:

oder, durch das Definieren der barycentric Gewichte

:

wir können einfach schreiben

:

der allgemein die erste Form der barycentric Interpolationsformel genannt wird.

Der Vorteil dieser Darstellung besteht darin, dass das Interpolationspolynom jetzt als bewertet werden kann

:

der, wenn die Gewichte vorgeschätzt worden sind, nur Operationen (das Auswerten und die Gewichte) verlangt im Vergleich mit, für die Basispolynome von Lagrange individuell zu bewerten.

Die barycentric Interpolationsformel kann auch leicht aktualisiert werden, um einen neuen Knoten durch das Teilen von jedem, durch und das Konstruieren des neuen als oben zu vereinigen.

Wir können weiter die erste Form durch das erste Betrachten der barycentric Interpolation der unveränderlichen Funktion vereinfachen:

:

Das Teilen dadurch modifiziert die Interpolation, noch Erträge nicht

:

der die zweite Form oder wahre Form der barycentric Interpolationsformel genannt wird. Diese zweite Form hat den Vorteil, der für jede Einschätzung dessen nicht bewertet zu werden braucht.

Begrenzte Felder

Das Lagrange Polynom kann auch in begrenzten Feldern geschätzt werden. Das hat Anwendungen in der Geheimschrift, solcher als im Heimlichen Teilen von Shamir des Schemas.

Siehe auch

• Polynomische Interpolation
• Der Algorithmus von Neville
• Newton-Form des Interpolationspolynoms
• Form von Bernstein des Interpolationspolynoms
• Formeln von Newton-Ställen
• Lebesgue unveränderlich (Interpolation)
• Das Chebfun System

Links

• ALGLIB hat Durchführungen in C ++ / C# / VBA / Pascal.
• GSL hat einen polynomischen Interpolationscode in C
• Lagrange Methode der Interpolation - Zeichen, PPT, Mathcad, Mathematica, MATLAB, Ahorn am holistischen numerischen Methode-Institut
• Interpolationspolynom von Lagrange auf www.math-linux.com
• Schätzung des Fehlers in der Lagrange Polynomischen Annäherung an ProofWiki
• Modul für Lagrange Polynome durch John H. Mathews
• Dynamische Lagrange Interpolation mit JSXGraph
• Numerische Computerwissenschaft mit Funktionen: Das Chebfun-Projekt