„Hermiteinterpolation" – Versionsunterschied

In der numerischen Mathematik ist die Hermiteinterpolation (benannt nach Charles Hermite) ein Interpolationsverfahren zur Polynominterpolation, das auch Ableitungen der zu interpolierenden Funktion berücksichtigt.

Ein Ergebnis für die klassische Polynominterpolation besagt, dass äquidistante Stützstellen – also gleicher Abstand zwischen den bekannten Funktionswerten – zu einem exponentiellen Anstieg der Kondition der Polynominterpolation führt, ihren Fehler also drastisch erhöht.^[1]

In der Praxis haben äquidistante Messpunkte aber gewisse Vorteile und sind manchmal auch unvermeidbar. Man benötigt daher ein Interpolationsverfahren, das auch für diesen Fall nur kleine Fehler erzeugt. Ein Ansatz ist die Splineinterpolation, bei der das Gebiet, auf dem eine Funktion interpoliert werden soll, durch ein Gitter zerteilt und in jedem der entstandenen Intervalle eine Polynominterpolation durchgeführt wird.

Wählt man dabei den „naiven", Newtonschen Ansatz, stimmen die Ableitungen der Interpolierten an den Gitterpunkten nicht notwendigerweise überein – folglich ist die Interpolierte an diesen Punkten in der Regel nicht (stetig) differenzierbar. Es muss nicht bei „Ecken", wie im Beispiel rechts, bleiben. Es könnte zum Beispiel auch passieren, dass auf zwei benachbarten Intervallen die Interpolierten sich „von oben" dem Gitterpunkt nähern und so tatsächlich eine – anschaulich – „Spitze" entsteht.

Da dieses Verhalten offensichtlich unerwünscht ist, versucht man, die Übergänge glatt zu gestalten, indem man neben den Funktionswerten in den Gitterpunkten weiterhin beliebig viele Ableitungen als bekannt voraussetzt und die Interpolationspolynome so wählt, dass die Ableitungen in dem gemeinsamen Punkt übereinstimmen. Praktisch reicht es, die erste Ableitung gleichzusetzen, um einen „glatt" aussehenden Graphen zu erhalten.

Diese Aufgabe lässt sich analog zur Problemstellung in der klassischen Polynominterpolation schriftlich lösen. Als Beispiel dient hier die Aufgabe,

${\displaystyle f(-1)=-1,,円f'(-1)=0,,円f(2)=0}${\displaystyle f(-1)=-1,,円f'(-1)=0,,円f(2)=0} in ${\displaystyle {\mathcal {P}}_{2}}${\displaystyle {\mathcal {P}}_{2}} zu interpolieren.

Man definiert

${\displaystyle p(x):=a_{0}+a_{1}\cdot x+a_{2}\cdot x^{2}}${\displaystyle p(x):=a_{0}+a_{1}\cdot x+a_{2}\cdot x^{2}} und leitet ab zu ${\displaystyle p'(x):=a_{1}+a_{2}\cdot 2x}${\displaystyle p'(x):=a_{1}+a_{2}\cdot 2x}.

Das Gleichungssystem wird damit zu

${\displaystyle {\begin{pmatrix}1&-1&1\0円&1&-2\1円&2&4\end{pmatrix}}\cdot {\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\end{pmatrix}}={\begin{pmatrix}-1\0円\0円\end{pmatrix}}.}${\displaystyle {\begin{pmatrix}1&-1&1\0円&1&-2\1円&2&4\end{pmatrix}}\cdot {\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\end{pmatrix}}={\begin{pmatrix}-1\0円\0円\end{pmatrix}}.}

Lösen nach ${\displaystyle a=(a_{0},a_{1},a_{2})^{T}}${\displaystyle a=(a_{0},a_{1},a_{2})^{T}} bringt die gesuchten Koeffizienten.

Dieser Lösungsansatz hat den Nachteil, dass er in der Komplexitätsklasse ${\displaystyle {\mathcal {O}}(n^{3})}${\displaystyle {\mathcal {O}}(n^{3})} liegt und damit langsam ist. Es wäre wünschenswert, die Newton-Basis von der klassischen Polynominterpolation übernehmen zu können. Dieser Ansatz schließt allerdings zusammenfallende Stützstellen aus und ist daher nicht ohne Modifikation anwendbar. Daher erweitert man ihn zum Hermitschen Interpolationsverfahren.

Die Hermite-Genocchi-Formel bildet die Grundlage der Hermiteinterpolation. Die Voraussetzung des Satzes sind:

• ${\displaystyle f}${\displaystyle f} ist ${\displaystyle k}${\displaystyle k}-mal stetig differenzierbar: ${\displaystyle f\in C^{k}([a,b]),\quad k\in \mathbb {N} }${\displaystyle f\in C^{k}([a,b]),\quad k\in \mathbb {N} }
• ${\displaystyle k+1}${\displaystyle k+1} Stützstellen: ${\displaystyle x_{0},\ldots ,x_{k}\in [a,b].}${\displaystyle x_{0},\ldots ,x_{k}\in [a,b].}

Nun liefert die Formel eine Integraldarstellung für die dividierten Differenzen aus dem Newtonalgorithmus der Polynominterpolation:

${\displaystyle f[x_{0},\ldots ,x_{k}]=\int _{\Sigma ^{k}}f^{(k)}\left(x_{0}+\sum _{i=1}^{k}s_{i}(x_{i}-x_{0})\right),円ds,}${\displaystyle f[x_{0},\ldots ,x_{k}]=\int _{\Sigma ^{k}}f^{(k)}\left(x_{0}+\sum _{i=1}^{k}s_{i}(x_{i}-x_{0})\right),円ds,}

mit dem k-dimensionalen Einheitssimplex:

${\displaystyle \;\Sigma ^{k}=\left\{s\in \mathbb {R} ^{k},,円\forall i:s_{i}\geq 0,\sum _{i=1}^{k}s_{i}\leq 1\right\}.}${\displaystyle \;\Sigma ^{k}=\left\{s\in \mathbb {R} ^{k},,円\forall i:s_{i}\geq 0,\sum _{i=1}^{k}s_{i}\leq 1\right\}.}

Man beweist diese Identität durch vollständige Induktion.^[2]

Im Gegensatz zu den dividierten Differenzen taucht im Integral in dieser Formel kein Quotient mit der Differenz zweier Stützstellen auf – rein rechnerisch ist es also möglich, konfluente (zusammenfallende) Stützstellen einzusetzen. Stellt man die Formel als

${\displaystyle f[x_{0},\ldots ,x_{k}]={\frac {1}{k!}}f^{(k)}(x^{*}),\quad \mathrm {falls} \quad x_{0}=\ldots =x_{k}=x^{*}}${\displaystyle f[x_{0},\ldots ,x_{k}]={\frac {1}{k!}}f^{(k)}(x^{*}),\quad \mathrm {falls} \quad x_{0}=\ldots =x_{k}=x^{*}}

dar, lässt sich diese Identität einfach beweisen.

Offensichtlich kann man folglich durch mehrfaches Verwenden von Stützstellen Ableitungen in der Interpolation berücksichtigen.

Also gilt der folgende Satz:

Es gelte:

• ${\displaystyle f}${\displaystyle f} ist ${\displaystyle n}${\displaystyle n}-mal stetig differenzierbar: ${\displaystyle f\in C^{n}([a,b]),\quad n\in \mathbb {N} }${\displaystyle f\in C^{n}([a,b]),\quad n\in \mathbb {N} }
• ${\displaystyle n+1}${\displaystyle n+1} Stützstellen: ${\displaystyle x_{0},\ldots ,x_{n}\in [a,b]}${\displaystyle x_{0},\ldots ,x_{n}\in [a,b]}
• die Häufigkeit der Wiederhoung der Stützstelle ${\displaystyle x_{i}}${\displaystyle x_{i}} sei mit ${\displaystyle m_{i}\in \mathbb {N} }${\displaystyle m_{i}\in \mathbb {N} } gegeben.

Dann erfüllt das Newton-Polynom:

${\displaystyle p(x):=f(x_{0})+\sum _{i=1}^{n}f[x_{0},\ldots ,x_{i}]\prod _{j=0}^{i-1}(x-x_{j})}${\displaystyle p(x):=f(x_{0})+\sum _{i=1}^{n}f[x_{0},\ldots ,x_{i}]\prod _{j=0}^{i-1}(x-x_{j})}

die Hermiteschen Interpolationsbedingungen:

${\displaystyle f^{(k)}(x_{i})=p^{(k)}(x_{i})\quad \forall ,円i=0,\ldots ,n\ \forall k=0,\ldots ,m_{i}-1.}${\displaystyle f^{(k)}(x_{i})=p^{(k)}(x_{i})\quad \forall ,円i=0,\ldots ,n\ \forall k=0,\ldots ,m_{i}-1.}

Darüber hinaus ist diese Lösung eindeutig.

Für den Fehler der Hermiteinterpolierten gilt nach dem Fehler in der Taylorentwicklung die obere Schranke

${\displaystyle f(x)-p(x)={\frac {f^{(n+1)}(\zeta )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}),\;\zeta \in [\alpha ,\beta ],\;f\in C^{n+1}}${\displaystyle f(x)-p(x)={\frac {f^{(n+1)}(\zeta )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}),\;\zeta \in [\alpha ,\beta ],\;f\in C^{n+1}}

Im Falle des Gitters

${\displaystyle x_{0}=\dots =x_{k}<x_{k+1}<\dots <x_{n}}${\displaystyle x_{0}=\dots =x_{k}<x_{k+1}<\dots <x_{n}}

gilt:

${\displaystyle f(x)-p(x)={\frac {f^{(n+1)}(\zeta )}{(n+1)!}}(x-x_{0})^{k+1}\prod _{i=k+1}^{n}(x-x_{i})}${\displaystyle f(x)-p(x)={\frac {f^{(n+1)}(\zeta )}{(n+1)!}}(x-x_{0})^{k+1}\prod _{i=k+1}^{n}(x-x_{i})}

Zur praktischen Berechnung der Interpolierten verwendet man wie gehabt das Schema der dividierten Differenzen.

Im Fall ${\displaystyle x_{0}=x_{1}=\ldots =x_{k}}${\displaystyle x_{0}=x_{1}=\ldots =x_{k}} muss anstatt der dort verwendeten Formel

${\displaystyle f[x_{0},\ldots ,x_{k}]={\frac {1}{k!}}f^{(k)}(x_{0})}${\displaystyle f[x_{0},\ldots ,x_{k}]={\frac {1}{k!}}f^{(k)}(x_{0})}

berechnet werden.

Zu beachten ist, dass ferner einige Umsortierungen notwendig sind. Im Folgenden sei ${\displaystyle x_{0}=\ldots =x_{i}=\ldots =x_{k}=\ldots =x_{n}}${\displaystyle x_{0}=\ldots =x_{i}=\ldots =x_{k}=\ldots =x_{n}}:

• Statt ${\displaystyle f[x_{i},\ldots ,x_{k}]}${\displaystyle f[x_{i},\ldots ,x_{k}]} muss man die dividierte Differenz ${\displaystyle f[x_{0},\ldots ,x_{k-i}]}${\displaystyle f[x_{0},\ldots ,x_{k-i}]} berechnen
• Taucht in der Rekursion ${\displaystyle f[x_{i}]}${\displaystyle f[x_{i}]} auf, berechnet man stattdessen ${\displaystyle f[x_{0}]}${\displaystyle f[x_{0}]}
• In allen Fällen, in denen die Formel aus dem ursprünglichen Neville-Aitken-Schema verwendet wird, ersetzt man jedes ${\displaystyle x_{i}}${\displaystyle x_{i}} durch ${\displaystyle x_{0}}${\displaystyle x_{0}}.

Der Pseudocode soll verdeutlichen, wie man die verallgemeinerte Form der dividierten Differenzen berechnet. Listen werden im Folgenden als ab 1 indiziert angenommen.

xvals ← Stützstellen
yvals ← Funktionswerte f(x) und ggf. Ableitungen bei mehrfachen x-Werten
zvals ← { f(xvals[i]) | i ∈ 1..#xvals }

for i ← #xvals..1 do
 for j ← i..#xvals do
 if i = j then
 [xi..xj]f ← zvals[i]
 else if xvals[i] = xvals[j] then
 index ← Index des ersten Vorkommens von xvals[i] in xvals
 [xi..xj]f ← yvals[j - i + index] / (j-i)!
 else
 [xi..xj]f ← ([xi+1..xj]f - [xi..xj-1]f) / (xvals[j] - xvals[i])

Erstmals veröffentlichte Hermite seine Untersuchungen zur Hermiteinterpolation 1878 in: Sur la formule d'interpolation de Lagrange, Journal für die reine und angewandte Mathematik, Band 84, Seite 70-79^[3]

Fehler bei Vorlage * Parametername unbekannt (Vorlage:Wikibooks): "3"

• Richard L. Burden, J. Douglas Faires: Numerische Methoden. Spektrum, Akad. Verlag, Heidelberg/ Berlin/ Oxford 2000, ISBN 3-8274-0596-3.

1. ↑ A. H. Turetskii: The bounding of polynomials prescribed at equally distributed points. In: Proc. Pedag. Inst. Vitebsk; 3; 1940.
   Siehe auch Runges Phänomen
2. ↑ Ralf Kornhuber, Christof Schütte: Einführung in die Numerische Mathematik. Hrsg.: AG Numerische Mathematik. Freie Universität Berlin April 2008, 3.1.1 Hermite-Interpolation und Taylor’sche Formel, S. 39–45 (PDF, 2.4 MB – Vorlesungsskript). 
3. ↑ Elliot Ward Cheney: Introduction to Approximation Theory, McGraw-Hill Book Company, 1966, Library of Congress Catalog Card Number 65-25916, ISBN 007-010757-2, Seite 225 + 242

• Numerische Mathematik
• Charles Hermite als Namensgeber

• Wikipedia:Vorlagenfehler/Schwesterprojekt