www.wikidata.de-de.nina.az

Hermiteinterpolation In der numerischen Mathematik ist die benannt nach Charles Hermite ein Interpolationsverfahren zur

Hermiteinterpolation

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

Erstmals veröffentlichte Hermite seine Untersuchungen zu diesem Verfahren 1877 in dem Journal: Sur la formule d’interpolation de Lagrange. In: Journal für die reine und angewandte Mathematik, Band 84, S. 70–79.

Vorbereitung Bearbeiten

Motivation Bearbeiten

Splineinterpolation ohne Berücksichtigung der Steigung. Man sieht klar den „Knick“ bei

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 – also der Fehlerabhängigkeit – der Polynominterpolation führt, ihren Fehler also drastisch erhöht.

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.

Splineinterpolation mit Berücksichtigung der Steigung

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 analytisch lösen. Als Beispiel dient hier die Aufgabe,

Man definiert

Das Gleichungssystem wird damit zu

Lösen nach bringt die gesuchten Koeffizienten.

Dieser Lösungsansatz hat den Nachteil, dass er in der Komplexitätsklasse 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.

Hermite-Genocchi-Formel Bearbeiten

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

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

mit dem k-dimensionalen Einheitssimplex:

Man beweist diese Identität durch vollständige Induktion.

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

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:

Hermiteinterpolation Bearbeiten

Es gelte:

Dann erfüllt das Newton-Polynom:

die Hermiteschen Interpolationsbedingungen:

Darüber hinaus ist diese Lösung eindeutig.

Fehlerabschätzung Bearbeiten

Für den Fehler der Hermiteinterpolierten gibt es eine explizite Darstellung.

Sei dafür .
Dann existiert für jedes ein , sodass

gilt.
Im Falle des Gitters

gilt:

Tschebyscheff-Abszissen Bearbeiten

Der zweite Faktor der Fehlerformel hängt nur von den Stützstellen ab und kann wie folgt abgeschätzt werden.

Seien beliebig.
Nun gilt die Abschätzung:

Diese Schranke wird angenommen mittels einer speziellen Wahl der Stützstellen – den sogenannten Tschebyscheff-Abszissen:

Berechnung der Interpolierten Bearbeiten

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

Im Fall muss anstatt der dort verwendeten Formel

berechnet werden.

Zu beachten ist, dass ferner einige Umsortierungen notwendig sind. Im Folgenden sei :

  • Statt muss man die dividierte Differenz berechnen
  • Taucht in der Rekursion auf, berechnet man stattdessen
  • In allen Fällen, in denen die Formel aus dem ursprünglichen Neville-Aitken-Schema verwendet wird, ersetzt man jedes durch .

Pseudocode Bearbeiten

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

Weblinks Bearbeiten

Wikibooks: Hermiteinterpolation – Implementierungen in der Algorithmensammlung

Literatur Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Elliot Ward Cheney: Introduction to Approximation Theory. McGraw-Hill Book Company, 1966, ISBN 0-07-010757-2, S. 225, 242.
  2. A. H. Turetskii: The bounding of polynomials prescribed at equally distributed points. In: Proc. Pedag. Inst. Vitebsk; 3, 1940.
    Siehe auch Runges Phänomen
  3. 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 (fu-berlin.de [PDF; 2,4 MB] Vorlesungsskript).
  4. Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag, 2006, S. 281.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der numerischen Mathematik ist die Hermiteinterpolation benannt nach Charles Hermite ein Interpolationsverfahren zur Polynominterpolation das auch Ableitungen der zu interpolierenden Funktion berucksichtigt Erstmals veroffentlichte Hermite seine Untersuchungen zu diesem Verfahren 1877 in dem Journal Sur la formule d interpolation de Lagrange In Journal fur die reine und angewandte Mathematik Band 84 S 70 79 1 Inhaltsverzeichnis 1 Vorbereitung 1 1 Motivation 1 2 Hermite Genocchi Formel 2 Hermiteinterpolation 3 Fehlerabschatzung 3 1 Tschebyscheff Abszissen 4 Berechnung der Interpolierten 4 1 Pseudocode 5 Weblinks 6 Literatur 7 EinzelnachweiseVorbereitung BearbeitenMotivation Bearbeiten nbsp Splineinterpolation ohne Berucksichtigung der Steigung Man sieht klar den Knick bei x 0 5 displaystyle x 0 5 nbsp Ein Ergebnis fur die klassische Polynominterpolation besagt dass aquidistante Stutzstellen also gleicher Abstand zwischen den bekannten Funktionswerten zu einem exponentiellen Anstieg der Kondition also der Fehlerabhangigkeit der Polynominterpolation fuhrt ihren Fehler also drastisch erhoht 2 In der Praxis haben aquidistante Messpunkte aber gewisse Vorteile und sind manchmal auch unvermeidbar Man benotigt daher ein Interpolationsverfahren das auch fur 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 durchgefuhrt wird nbsp Splineinterpolation mit Berucksichtigung der SteigungWahlt man dabei den naiven Newtonschen Ansatz stimmen die Ableitungen der Interpolierten an den Gitterpunkten nicht notwendigerweise uberein folglich ist die Interpolierte an diesen Punkten in der Regel nicht stetig differenzierbar Es muss nicht bei Ecken wie im Beispiel rechts bleiben Es konnte zum Beispiel auch passieren dass auf zwei benachbarten Intervallen die Interpolierten sich von oben dem Gitterpunkt nahern und so tatsachlich eine anschaulich Spitze entsteht Da dieses Verhalten offensichtlich unerwunscht ist versucht man die Ubergange glatt zu gestalten indem man neben den Funktionswerten in den Gitterpunkten weiterhin beliebig viele Ableitungen als bekannt voraussetzt und die Interpolationspolynome so wahlt dass die Ableitungen in dem gemeinsamen Punkt ubereinstimmen Praktisch reicht es die erste Ableitung gleichzusetzen um einen glatt aussehenden Graphen zu erhalten Diese Aufgabe lasst sich analog zur Problemstellung in der klassischen Polynominterpolation analytisch losen Als Beispiel dient hier die Aufgabe f 1 1 f 1 0 f 2 0 displaystyle f 1 1 f 1 0 f 2 0 nbsp in P 2 displaystyle mathcal P 2 nbsp zu interpolieren Man definiert p x a 0 a 1 x a 2 x 2 displaystyle p x a 0 a 1 cdot x a 2 cdot x 2 nbsp und leitet ab zu p x a 1 a 2 2 x displaystyle p x a 1 a 2 cdot 2x nbsp Das Gleichungssystem wird damit zu 1 1 1 0 1 2 1 2 4 a 0 a 1 a 2 1 0 0 displaystyle begin pmatrix 1 amp 1 amp 1 0 amp 1 amp 2 1 amp 2 amp 4 end pmatrix cdot begin pmatrix a 0 a 1 a 2 end pmatrix begin pmatrix 1 0 0 end pmatrix nbsp Losen nach a a 0 a 1 a 2 T displaystyle a a 0 a 1 a 2 T nbsp bringt die gesuchten Koeffizienten Dieser Losungsansatz hat den Nachteil dass er in der Komplexitatsklasse O n 3 displaystyle mathcal O n 3 nbsp liegt und damit langsam ist Es ware wunschenswert die Newton Basis von der klassischen Polynominterpolation ubernehmen zu konnen Dieser Ansatz schliesst allerdings zusammenfallende Stutzstellen aus und ist daher nicht ohne Modifikation anwendbar Daher erweitert man ihn zum Hermitschen Interpolationsverfahren Hermite Genocchi Formel Bearbeiten Die Hermite Genocchi Formel bildet die Grundlage der Hermiteinterpolation Die Voraussetzung des Satzes sind f displaystyle f nbsp ist k displaystyle k nbsp mal stetig differenzierbar f C k a b k N displaystyle f in C k a b quad k in mathbb N nbsp k 1 displaystyle k 1 nbsp Stutzstellen x 0 x k a b displaystyle x 0 ldots x k in a b nbsp Nun liefert die Formel eine Integraldarstellung fur die dividierten Differenzen aus dem Newtonalgorithmus der Polynominterpolation f x 0 x k S k f k x 0 i 1 k s i x i x 0 d s 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 nbsp mit dem k dimensionalen Einheitssimplex S k s R k i s i 0 i 1 k s i 1 displaystyle Sigma k left s in mathbb R k bigg forall i s i geq 0 wedge sum i 1 k s i leq 1 right nbsp Man beweist diese Identitat durch vollstandige Induktion 3 Im Gegensatz zu den dividierten Differenzen taucht im Integral in dieser Formel kein Quotient mit der Differenz zweier Stutzstellen auf rein rechnerisch ist es also moglich konfluente zusammenfallende Stutzstellen einzusetzen Stellt man die Formel als f x 0 x k 1 k f k x f a l l s x 0 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 nbsp dar lasst sich diese Identitat einfach beweisen Offensichtlich kann man folglich durch mehrfaches Verwenden von Stutzstellen Ableitungen in der Interpolation berucksichtigen Also gilt der folgende Satz Hermiteinterpolation BearbeitenEs gelte f displaystyle f nbsp ist n displaystyle n nbsp mal stetig differenzierbar f C n a b n N displaystyle f in C n a b quad n in mathbb N nbsp n 1 displaystyle n 1 nbsp Stutzstellen x 0 x n a b displaystyle x 0 ldots x n in a b nbsp die Haufigkeit der Wiederholung der Stutzstelle x i displaystyle x i nbsp sei mit m i N displaystyle m i in mathbb N nbsp gegeben Dann erfullt das Newton Polynom p x f x 0 i 1 n f x 0 x i 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 nbsp die Hermiteschen Interpolationsbedingungen f k x i p k x i i 0 n k 0 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 nbsp Daruber hinaus ist diese Losung eindeutig Fehlerabschatzung BearbeitenFur den Fehler der Hermiteinterpolierten p displaystyle p nbsp gibt es eine explizite Darstellung Sei dafur f C n 1 a b displaystyle f in C n 1 a b nbsp Dann existiert fur jedes x a b displaystyle x in a b nbsp ein 3 a b displaystyle xi in a b nbsp sodass f x p x f n 1 3 n 1 i 0 n x x i displaystyle f x p x frac f n 1 xi n 1 prod i 0 n x x i nbsp gilt 4 Im Falle des Gitters x 0 x k lt x k 1 lt lt x n displaystyle x 0 ldots x k lt x k 1 lt dots lt x n nbsp gilt f x p x f n 1 3 n 1 x x 0 k 1 i k 1 n x x i displaystyle f x p x frac f n 1 xi n 1 x x 0 k 1 prod i k 1 n x x i nbsp Tschebyscheff Abszissen Bearbeiten Der zweite Faktor der Fehlerformel hangt nur von den Stutzstellen ab und kann wie folgt abgeschatzt werden Seien x 0 x n I 1 1 displaystyle x 0 ldots x n in I 1 1 nbsp beliebig Nun gilt die Abschatzung max x I i 0 n x x i 2 n displaystyle max x in I prod i 0 n x x i geq 2 n nbsp Diese Schranke wird angenommen mittels einer speziellen Wahl der Stutzstellen den sogenannten Tschebyscheff Abszissen x j cos 2 j 1 n 1 p 2 j 0 n max x I i 0 n x x i 2 n displaystyle begin aligned x j amp cos left frac 2j 1 n 1 frac pi 2 right quad j 0 ldots n Rightarrow max x in I prod i 0 n x x i amp 2 n end aligned nbsp Berechnung der Interpolierten BearbeitenZur praktischen Berechnung der Interpolierten verwendet man wie gehabt das Schema der dividierten Differenzen Im Fall x 0 x 1 x k displaystyle x 0 x 1 ldots x k nbsp muss anstatt der dort verwendeten Formel f x 0 x k 1 k f k x 0 displaystyle f x 0 ldots x k frac 1 k f k x 0 nbsp berechnet werden Zu beachten ist dass ferner einige Umsortierungen notwendig sind Im Folgenden sei x 0 x i x k x n displaystyle x 0 ldots x i ldots x k ldots x n nbsp Statt f x i x k displaystyle f x i ldots x k nbsp muss man die dividierte Differenz f x 0 x k i displaystyle f x 0 ldots x k i nbsp berechnen Taucht in der Rekursion f x i displaystyle f x i nbsp auf berechnet man stattdessen f x 0 displaystyle f x 0 nbsp In allen Fallen in denen die Formel aus dem ursprunglichen Neville Aitken Schema verwendet wird ersetzt man jedes x i displaystyle x i nbsp durch x 0 displaystyle x 0 nbsp Pseudocode Bearbeiten Der Pseudocode soll verdeutlichen wie man die verallgemeinerte Form der dividierten Differenzen berechnet Listen werden im Folgenden als ab 1 indiziert angenommen xvals Stutzstellen 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 Weblinks Bearbeiten nbsp Wikibooks Hermiteinterpolation Implementierungen in der AlgorithmensammlungLiteratur BearbeitenRichard L Burden J Douglas Faires Numerische Methoden Spektrum Akad Verlag Heidelberg Berlin Oxford 2000 ISBN 3 8274 0596 3 Charles Hermite Sur la formule d interpolation de Lagrange In Journal fur die reine und angewandte Mathematik Band 84 S 70 79 1 Martin Hermann Numerische Mathematik Band 2 Analytische Probleme 4 uberarbeitete und erweiterte Auflage Walter de Gruyter Verlag Berlin und Boston 2020 ISBN 978 3 11 065765 4 Einzelnachweise Bearbeiten a b Elliot Ward Cheney Introduction to Approximation Theory McGraw Hill Book Company 1966 ISBN 0 07 010757 2 S 225 242 A H Turetskii The bounding of polynomials prescribed at equally distributed points In Proc Pedag Inst Vitebsk 3 1940 Siehe auch Runges Phanomen Ralf Kornhuber Christof Schutte Einfuhrung in die Numerische Mathematik Hrsg AG Numerische Mathematik Freie Universitat Berlin April 2008 3 1 1 Hermite Interpolation und Taylor sche Formel S 39 45 fu berlin de PDF 2 4 MB Vorlesungsskript Wolfgang Dahmen Arnold Reusken Numerik fur Ingenieure und Naturwissenschaftler Springer Verlag 2006 S 281 Abgerufen von https de wikipedia org w index php title Hermiteinterpolation amp oldid 237026136