Approximation - Interpolation

Inhaltsverzeichnis

1 Einleitung

2 Begriffsbeschreibung „Interpolation“

3 Anwendung der Interpolation in der Praxis

4 Interpolationsmethoden
4.1 Weierstraßscher Approximationssatz
4.2 Taylor-Polynome
4.3 Lagrange-Interpolation
4.3.1 Kurzbiographie Joseph Louis de Lagrange
4.3.2 lineare Lagrange-Interpolation
4.3.3 numerische Lagrange-Interpolation n -ten Grades
4.4 Spline-Interpolation
4.4.1 lineare Spline-Interpolation
4.4.2 kubische Spline-Interpolation

5 Schlußwort
- Quellenverzeichnis
Bücher
Internet
Sonstige Quellen

1 Einleitung

Es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen, sondern das Erwerben, nicht das Dasein, sondern das Hinkommen, was den größten Genuss gewährt. (C. F. Gauss)

Wer sich keinen Punkt denken kann, der ist einfach zu faul dazu. (Wilhelm Busch)

Die vorliegende Facharbeit im Bereich "Approximation" beschäftigt sich mit dem Themenschwerpunkt "Interpolation". Das Problem, genaue Informationen über Vorgänge in Mathematik und Technik zu gewinnen, ergibt sich aus der Kenntnis meist weniger punktueller Daten. Diese Daten stammen, speziell in der Technik oft aus Messungen, bei denen keine kontinuierliche Werteaufzeichnung möglich ist. In Abhängigkeit von der Verteilung der gegebenen Werte können unterschiedliche Methoden der Interpolation zum Einsatz kommen. Es existieren viele verschiedene Interpolationsverfahren mit unterschiedlichen Spezialisierungen und Anwendungsgebieten. Diese Arbeit soll einen Überblick über die wichtigsten Methoden liefern. Um den Einstieg in die Thematik etwas zu erleichtern, erfolgt zu Beginn eine Definition des thematischen Begriffes. Anschließend wird ein kurzer Überblick über die wichtigsten Anwendungsbereiche gegeben. Den Schwerpunkt bilden dann einige häufig benutzen Interpolationsmethoden, wobei ich mich hauptsächlich mit der Lagrange-Interpolation beschäftigen werde.

2 Begriffsbeschreibung „Interpolation“

In der Mathematik, aber auch in anderen Fachgebieten wie z.B. der Physik oder den Geowissenschaften kommt es häufig vor, dass sich beispielsweise aus Punktmessungen einige Wertepaare ergeben, die einen bestimmten Zusammenhang beschreiben. Um diesen zu veranschaulichen überträgt man die Daten in ein Koordinatensystem und erhält dadurch eine Anzahl von Punkten. Nun ist es für viele Anwendungen interessant, wie sich der zu beschreibende Zusammenhang zwischen den gegebenen Werten verhält. Dazu kann man die Punkte mit einer Linie oder einer mehr oder weniger glatten Kurve verbinden und daraus die gesuchten Zwischenwerte ablesen. Das kann mit der Hand durch eine frei gezogene Linie ausgeführt werden. Dieses Verbinden der Punkte mittels einer so gut wie möglich gezogenen Linie ist der Aufgabenbereich der Interpolation, allerdings wird hierbei anstatt einer willkürlich gezeichneten Kurve eine mathematische Funktion ermittelt, welche die gegebenen Punkte enthält und mit der die Funktionswerte an jeder beliebigen Stelle, auch zwischen den gegebenen Punkten, errechnet werden können.

Daher ist die Interpolation eine mathematische Methode, welche benutzt wird um eine Funktion zu finden deren Graph durch eine vorgegebene endliche Menge von Punkten (x 1 , y 1) , ... (x n, y n) der Ebene verläuft. Dabei ist x 0 < x 1 < ... < x n vorausgesetzt , x 0 , ..., x n nennt man die Stützstellen der Interpolation und y 1 , ..., y n werden als Funktions- oder Stützwerte bezeichnet. Jede interpolierende Funktion f sollte wenigstens auf dem Intervall x 0 = x = x n definiert und stetig sein, sie erfüllt die Bedingung f (x 0) = y 0 , ..., f (x n) = y n. Da in der Praxis nur selten Zusammenhänge auftreten, deren graphischer Verlauf Sprünge, Knicke oder Definitionslücken enthält, sollte der Graph der Funktion außerdem einen möglichst "glatten" Kurvenverlauf aufweisen. Denn starke Sprünge lassen sich mit Interpolationsverfahren nur schlecht beschreiben. Um dies zu erreichen, dürfen weder Sprünge in der Funktion selber, noch in deren Steigung (1. Ableitung) und Krümmung (2.Ableitung) auftreten, das heißt sie sollte in dem zu interpolierenden Intervall mindestens zweimal stetig differenzierbar sein. Es können für Interpolationszwecke nahezu alle Arten von Funktionen benutzt werden, wobei aber einfache Polynomfunktionen zu bevorzugen sind, da bei komplizierten Funktionen sonst die Einfachheit und Überschaubarkeit verloren gehen kann und der Rechenaufwand steigt.

Die einfachste Methode eine interpolierende Funktion zu finden, ist aufeinander folgende Punkte durch eine Strecke zu verbinden, dies nennt man lineare Interpolation. Beispielsweise wird ein Funktionsgraph in vielen Computerprogrammen dadurch gezeichnet, dass zu einer möglichst hohen Zahl von Stützstellen die dazugehörigen Funktionswerte berechnet werden und das Programm dann mit Hilfe linearer Interpolation eine Näherung des Funktionsgraphen zeichnet. Mit der Zahl der Stützstellen steigt meistens auch die Qualität des erhaltenen Bildes (Abb. 2.1). Viele Computerprogramme und Grafiktaschenrechner liefern deshalb keine exakten Ergebnisse, sondern angenäherte approximierte Werte. Dies genügt um sich über Abläufe, Phänomene und technische Funktionen eine Vorstellung und einen Überblick zu verschaffen und so wird bei vielen Anwendungen die lineare Interpolation verwendet. Für exakte Berechnungen und sehr genaue Approximationen stehen Verfahren wie die Spline-Interpolation zur Verfügung. Da der Genauigkeitsgrad der Approximation stark vom geforderten Rechenaufwand abhängt, wird je nach Bedarf eine der verschiedenen Interpolationsmethoden ausgewählt. Diese Wahl hängt davon ab, ob man sich eben nur ein Bild von der Funktion machen will oder sehr genaue Ergebnisse benötigt, welche nah an der realen Funktion liegen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1 Abhängigkeit der Genauigkeit der linearen Interpolation P n(x) von der Stützstellenanzahl x n

Durch lineare Interpolation wird die Funktion der es sich anzunähern gilt recht ungenau beschrieben oder man benötigt eine sehr hohe Anzahl an Stützstellen. Des weiteren besteht bei der linearen Interpolation die Gefahr, dass wichtige Erkenntnisse über die zu approximierende Funktion verloren gehen, speziell wenn die Punkte, welche linear verbunden werden weit auseinander liegen und zwischen zwei Punkten eine schnelle Änderung der zu approximierenden Funktion vorhanden ist. Wie man in Abb. 2.2 erkennen kann entsteht durch Anwendung der Linearinterpolation ein Graph, welcher das Minimum zwischen P 2 und P 3 in keiner Weise berücksichtigt. Es gehen also wichtige Erkenntnisse über f (x) verloren. Wenn man sich bei diesem Beispiel also nur auf den Graphen g (x) der linearen Interpolation verlassen würde ginge sogar die Erkenntnis verloren, dass f (x) auch negative Funktionswerte besitzt.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2 Abweichung durch Linearinterpolation

Eine andere Methode besteht darin, ein Polynom P(x) zu bestimmen, das die gewünschten Bedingungen erfüllt (Abb. 2.3). Bei n Stützstellen entsteht dabei stets mit einem Polynom vom Grad kleiner oder gleich n – 1. Zum einen ist bei Polynomen die Forderung nach einem "glatten" Kurvenverlauf erfüllt, zum anderen sind weiterführende Rechnungen wie Differentialrechnung oder Integration durchführbar. Außerdem ist es immer möglich ein Interpolationspolynom zu finden, auch bei einer sehr großen Anzahl von Stützpunkten. Diese Polynominterpolation hat den entscheidenden Vorteil, dass die entstandene Funktion glatt und damit beliebig oft differenzierbar ist. Dies ist mit linearer Interpolation nicht möglich, weil keine stetige Funktion entsteht. Deshalb kommt häufig die Methode der Polynom-Interpolation zum Einsatz, da eine Funktion mit Polynomen auch wesentlich genauer beschreibbar ist, als mit Geraden. Um das Polynom einfach zu halten, sollte sein Grad möglichst klein sein.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.3 Polynominterpolation von f (x) mit einem Polynom dritten Grades P (x)

3 Anwendung der Interpolation in der Praxis

Die Interpolation wird in vielen technischen Bereichen verwendet. Oft sind bei Experimenten keine kontinuierlichen Werteaufzeichnungen möglich und es werden nur einzelne Messungen zu bestimmten Zeitpunkten durchgeführt. Mit Hilfe der unterschiedlichen Verfahren der Interpolation werden Werte für Orte bestimmt an denen keine Messung erfolgt ist. Aus spärlich verteilten Punkt- bzw. Einzelmessungen, welche in einem Koordinatensystem nur als Punkte dargestellt werden können, sollen kontinuierliche Funktionen entstehen. Dies ist in der Elektrotechnik am Beispiel der Entladekurve eines Kondensators möglich. Die Messung erfolgt zum Zeitpunkt t =0 und anschließend in gleichen Zeitintervallen. Dadurch entstehen punktuelle Messwerte, bei denen die Zeitintervalle die Stützstellen und die jeweiligen Spannungs- und Stromwerte die dazugehörigen Funktionswerte darstellen. Durch Interpolation erhält man eine Funktion, welche sich der Exponentialfunktion annähert und die Entladung des Kondensators beschreibt (Abb. 3.1). Es wurden die unbekannte Werte der Funktion aus den gemessenen Daten für die Zeiten ermittelt an denen keine Messung durchgeführt wurde.

Bei Computerprogrammen werden Interpolationsverfahren oft bei der Erstellung von Computeranimationen oder Computergrafiken benutzt, um den Arbeitsaufwand zu verringern und die Qualität zu verbessern. Des Weiteren benutzen viele Computerprogramme, wie auch graphische Taschenrechner, Interpolationsmethoden um Grafik und Funktionen darzustellen und daran Berechnungen zu realisieren.

Auch in den Geowissenschaften spielt Interpolation eine große Rolle. Ursprünglich wurden die Methoden der Interpolation zur Bestimmung der Erzstufen in Erzminen entwickelt, heute finden sie auf allen Gebieten der Geowissenschaften und auch darüber hinaus Verwendung. Eines der größten Probleme ist, kontinuierliche topographische Informationen einer bestimmten Region in angemessene Daten zu überführen. Dabei müssen die Daten so in einer kontinuierlichen Funktion zusammengestellt werden, dass sie die topographische Oberfläche der gewünschten Region wiedergeben. Damit wird Interpolation in der Topographie bei der Darstellung von Höhenunterscheiden benutzt. Auf zweidimensionalen topographischen Landkarten, wird mit Hilfe von Höhenlinien (Isohypsen) eine dreidimensionale Darstellung erreicht. Da meist nur einzelne Messpunkte als Höhenangaben zur Verfügung stehen, werden diese Messpunkte mit Hilfe der Interpolation zu kontinuierlichen Isohypsen verbunden.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.1 Entladung eines Kondensators, aus Messpunkten resultierende Funktionen

4 Interpolationsmethoden

4.1 Weierstraßscher Approximationssatz

Der Weierstraßsche Approximationssatz bildet die theoretische Grundlage für die algebraischen Polynome. Durch diese Polynome werden stetige Funktionen gleichmäßig approximiert. Das heißt, ist auf einem abgeschlossenen Intervall [ a, b ], die Funktion f (x) definiert und stetig, dann existiert zu einer vorgegebenen Zahl Abbildung in dieser Leseprobe nicht enthalten stets ein Polynom P (x), welches der Funktion beliebig nahe kommt. Dieses Polynom P (x) beschreibt die Funktion f (x) im gesamten Intervall gleichmäßig (Abb. 4.1). Für alle Werte von x im Intervall [ a, b ] ergibt sich folgende Beziehung zwischen der zu approximierenden Funktion f (x), dem Polynom P (x), welches sich f (x) annähert und der vorgegebenen ZahlAbbildung in dieser Leseprobe nicht enthalten:

Abbildung in dieser Leseprobe nicht enthalten

Es wird folglich eine Differenz zwischen f (x) und dem angenäherten Polynom P (x) errechnet, welche in einem definierten Bereich <Abbildung in dieser Leseprobe nicht enthalten bleiben muss. Diese errechnete Differenz gibt die Güte der gleichmäßigen Approximation wider. Sie sollte so klein wie möglich sein um eine gute Annäherung zu erzielen. Es ist von großem Vorteil, dass durch Approximation der stetigen Funktion Polynome entstehen, denn es ist einfach deren Integrale und Ableitungen zu berechnen, welche dann wiederum Polynome darstellen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.1 Weierstraßscher Approximationssatz

4.2 Taylor-Polynome

Der Weierstraßsche Approximationssatz ist für theoretische Aussagen sehr wichtig, jedoch für numerische Untersuchungen nicht effektiv, denn oft ist nicht die gleichmäßige Approximation über das gesamte Intervall nötig. Man benötigt deshalb ein Polynom, welches einige spezielle Bedingungen erfüllt und an die jeweilige Aufgaben- bzw. Problemstellung angepasst ist und dennoch sehr nahe an der steigen Funktion liegt. Diese Bedingungen erfüllen die Taylor-Polynome vom Grad n, welche wie folgt gebildet werden:

Abbildung in dieser Leseprobe nicht enthalten

Diese Approximation mit Taylor-Polynomen ist nur dann effektiv, wenn die Funktion f (x) in der unmittelbaren Umgebung der vorgegebenen Stelle x = x 0 angenähert werden soll. Falls ein größerer Bereich von f (x) um die Stelle x 0 approximiert werden soll, versagen die Taylor-Polynome. Wenn das benötigte Intervall zur Approximation vergrößert wird, erhöht sich auch automatisch der Grad n der Taylor-Polynome.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.2 Approximation von f(x) mit Taylorpolynom T0(x) und T1(x)

Bei Erhöhung des Polynomgrades n vergrößert sich das Intervall um die Stelle x0 jedoch nur sehr langsam, auf dem die Taylor-Polynome P n(x) die vorgegebene Funktion f (x) hinreichend genau approximieren. Allerdings ist mit der Erhöhung des Polynomgrades auch ein viel größerer Rechenaufwand nötig, was ab einen bestimmten Grad des Polynoms zu aufwendig wird und in keinem Verhältnis zur erzielten Genauigkeit der Approximation mehr steht. Des Weiteren sind hohe Ableitungen von f (x) nötig, welche bei komplizierten Funktionen das Rechnen erschweren und den zeitlichen Aufwand erhöhen. Deswegen werden in der Praxis nur solche Approximationstechniken benutzt, die auf Informationen über die stetige Funktion f (x) an mehreren Stützstellen x 0 , x 1 ,…,x n zurückgreifen. Eine solche Methode, die es ermöglicht auch über ein größeres Intervall gute Übereinstimmungen der stetigen Funktion mit der Approximierten zu erzielen, ist die Lagrange-Interpolation.

4.3 Lagrange-Interpolation

4.3.1 Kurzbiographie Joseph Louis de Lagrange

Joseph Louis de Lagrange heiß eigentlich Giuseppe Ludovico Lagrangia. Er war französischer Mathematiker und Naturforscher mit italienischer Herkunft. Lagrange leistete bedeutende Arbeiten zur Mechanik, Himmelsmechanik und zur Analysis. Lagrange wurde am 25. Januar 1736 in Turin geboren und studierte Mathematik und Naturwissenschaften an der Universität von Turin. Bereits im Alter von 16 Jahren lehrte Lagrange Mathematik an der Artillerieschule Turin und 1755 wurde er Professor an dieser Einrichtung. Drei Jahre darauf gründete Lagrange eine Gesellschaft, aus der sich später die Turiner Akademie der Wissenschaften entwickelte. Im Jahre 1766 ging er auf Einladung von Friedrich II. nach Berlin und trat an der Preußischen Akademie der Wissenschaften die Nachfolge von Leonhard Euler an. Lagrange wechselte 1787 auf Einladung König Ludwigs XVI. nach Paris an die dortige Akademie der Wissenschaften. Zur Zeit der Französischen Revolution war er für die Kommission zur Aufstellung eines neuen Systems der Maße und Gewichte verantwortlich, aus der das metrische System resultierte und gehörte dem Komitee für Erfindungen an. Nach der Revolution ernannte man Lagrange 1795 zum Professor an der neu eingerichteten École Normale. Zwei Jahre später wurde er Professor an der École Polytechnique, ein Posten, den er bis zu seinem Tod wahrnahm. Unter Napoleon wurde er Mitglied des Senats und erhielt den Titel eines Grafen. Lagrange starb im Alter von 77 Jahren am 10. April 1813 in Paris.

4.3.2 lineare Lagrange-Interpolation

Die einfachste Form der Lagrange-Interpolation ist die lineare Lagrange-Interpolation. Bei diesem Verfahren werden, wie oben schon beschrieben, lediglich zwei Punkte P 0(x 0, y 0) und P 1(x 1, y 1) durch eine Gerade, das heißt durch ein Polynom ersten Grades P(x) verbunden (Abb. 4.3). Dieses Polynom besteht bei der linearen Interpolation aus zwei Lagrange-Polynomen L 0 und L 1, welche mit ihrem jeweiligen Stützwert y 0 bzw. y 1 multipliziert und anschließend addiert werden. Dies wird in der folgenden Form dargestellt:

Abbildung in dieser Leseprobe nicht enthalten

Dabei sind x 0 und x 1 die Stützstellen und y 0 bzw. y 1 die dazugehörigen Funktionswerte, wobei der Zusammenhang y 0 = f (x 0),…, y n = f (x n) gilt. Das lineare Interpolationspolynom P(x) wird unter Verwendung der beiden Quotienten

Abbildung in dieser Leseprobe nicht enthalten

konstruiert. Diese Polynome erfüllen an den Stützstellen x 0 und x 1 spezielle Bedingungen:

- an der Stützstelle x0 gilt: L 0(x 0) = 1 und L 1(x 1) = 0
- an der Stützstelle x1 gilt: L 0(x 0) = 0 und L 1(x 1) = 1

(vgl. Abb. 4.3)

Beispiel:

Geben sind zwei Punkte, mit den Koordinaten P 0 = (2,1) und P 1 = (3,-2) (Abb. 4.3) und gesucht ist die zu interpolierende Funktion P(x), welche die beiden Punkte linear verbinden soll.

Lösung:

Abbildung in dieser Leseprobe nicht enthalten

￫ Nach der Formel Abbildung in dieser Leseprobe nicht enthalten werden die Punkte P 0 und P 1 eingesetzt:

Abbildung in dieser Leseprobe nicht enthalten = Abbildung in dieser Leseprobe nicht enthalten = Abbildung in dieser Leseprobe nicht enthalten

￫ Es ergibt sich die Funktion (Abb. 4.4):

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.3 lineare Lagrange-Interpolation von P (x) durch zwei Punkte P 0 und P 1 , mit den Polynomen L 0 und L 1

Wie man in Abb. 4.3 erkennen kann erfüllen die Lagrange-Polynome L 0(x) und L 1(x) die oben genannten Bedingungen an den Stellen x 0 und x 1, so ist der Funktionswert von L 0(x 0) = 1 und an der Stelle x 1 ist L 0(x 1) = 0, folglich ergibt sich für L 1(x 1) = 1 und für L 1(x 0) = 0.

4.3.3 numerische Lagrange-Interpolation n-ten Grades

Das Konzept der linearen Lagrange-Interpolation, welche mit lediglich zwei Stützstellen ein Polynom ersten Grades bildet, kann damit verallgemeinert werden. Man bestimmt ein Polynom P n (x) von Grad höchstens n, welches durch die n +1 vorgegebenen Punkte (x 0, y 0), (x 1, y 1),…,(x n, y n) verläuft. Die Stützstellen x 0, x 1,…, x n werden dabei als paarweise verschieden vorausgesetzt, da Stützstellen mit identischen Werten nicht nutzbar sind. Das heißt das entstehende Polynom ist vom Grad immer um eins niedriger als die Anzahl der Stützstellen, welche gegeben sind. So erhält man bei der linearen Lagrange-Interpolation durch zwei Stützstellen ein Polynom ersten Grades und beispielsweise entsteht bei numerischer Lagrange-Interpolation mit vier Stützstellen, folglich ein Polynom dritten Grades usw. Die Polynome in der Lagrange-Form werden, nach Lagrange, mit L bezeichnet. Sie werden wie folgt dargestellt:

Abbildung in dieser Leseprobe nicht enthalten

Wie bei der linearen Lagrange-Interpolation gelten weiterhin spezielle Bedingungen für die Lagrange-Polynome L 0(x 0),…, L n(x n) an den Stützstellen x 0 , ..., x n , welche verallgemeinert werden können:

Abbildung in dieser Leseprobe nicht enthalten

Damit ist der Funktionswert eines Lagrange-Polynoms L i(x) an der Stelle x k immer 1, wenn der Wert von k dem von i entspricht. Entgegengesetzt ist der Funktionswert des Polynoms immer 0, wenn sich der Wert k von i unterscheidet. Dies wird in Abb. 4.4 sehr deutlich. Dargestellt ist eine zu approximierende Funktion f (x) und vier äquidistante Stützstellen, d.h. die Abstände der Stützstellen x 0…4 sind konstant. Die vier Lagrange-Polynome L 0…4 ergeben ein Polynom dritten Grades P 3 (x), welches die Funktion f (x) im Intervall [ x 0, x 3] approximiert. Man sieht, dass die Genauigkeit mit der f (x) approximiert wird nicht allzu groß ist. Für eine höhere Genauigkeit werden eine höhere und dichtere Anzahl von Stützstellen im Intervall benötigt, was den Grad des Polynoms jedoch ebenfalls erhöhen würde.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.4 Verhalten der Lagrange-Polynome an den Stützstellen

Beispiel:

Geben sind drei Punkte mit den Koordinaten P 0 = (1,2), P 1 = (3,0) und P 2 = (4,5), (Abb. 4.5). Gesucht ist die zu interpolierende Funktion P (x), welche durch alle drei Punkte verläuft.

Lösung:

Da es sich um drei Punkte handelt, ist die zu erwartende Funktion f (x) eine Funktion zweiten Grades, da der Grad der Funktion bei n Stützstellen immer n- 1 ist. Dementsprechend wird das Polynom mit P 2(x) bezeichnet. Da drei Stützpunkte bekannt sind, werden voraussichtlich drei Lagrange-Polynome zu bestimmen sein.

Abbildung in dieser Leseprobe nicht enthalten

￫ Nach Abbildung in dieser Leseprobe nicht enthalten sind die Lagrange-Polynome L 0…2 wie folgt zu errechnen:

Abbildung in dieser Leseprobe nicht enthalten

￫ Jetzt werden die Lagrange-Polynome L 0…2 und die jeweilig dazugehörigen Funktionswerte y 0…2 in die Formel Abbildung in dieser Leseprobe nicht enthalten eingesetzt:

Abbildung in dieser Leseprobe nicht enthalten

￫ Da der Funktionswert y 1 = 0 ist, fällt der TermAbbildung in dieser Leseprobe nicht enthalten, aus dem Polynom weg. Das trifft im Allgemeinen auf Funktionswerte y n = 0 zu, deshalb ist es für die Berechnung von P (x) nicht notwendig, für Punkte mit (x, 0), ein Lagrange-Polynom L n zu errechnen. Speziell in diesem Beispiel wäre damit die Berechnung für L 1 überflüssig gewesen.

Abbildung in dieser Leseprobe nicht enthalten

￫ daraus ergibt sich wie erwartet die interpolierte Funktion zweiten Grades (Abb. 4.5):

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.5 Interpolation der Funktion P(x) durch drei Punkte P 0…2 mit Lagrange-Polynomen L 0…2(x)

Die Güte der Interpolation hängt sehr von der Verteilung der Stützstellen über das Interpolationsintervall ab. Sind die Stützstellen äquidistant verteilt und der Grad n des Polynoms L n(x) hoch, dann oszilliert die Funktion an den Rändern des Intervalls [ x 0, x n] sehr stark. Das bedeutet, dass die Funktion an den Rändern sehr stark schwingt und folglich sind die Funktionswerte Abbildung in dieser Leseprobe nicht enthalten an diesen äußeren Stellen sehr viel höher als in den mittleren Regionen. Deshalb müssen zur Minderung dieses Fehlers die Stützstellen nicht äquidistant, sondern an den Rändern des Intervalls dichter gelegt werden als in der Mitte.

4.4 Spline-Interpolation

4.4.1 lineare Spline-Interpolation

Das Verfahren von Lagrange beruht darauf ein einziges Interpolationspolynom zu ermitteln, das alle Stützpunkte enthält. Eine andere Vorgehensweise liegt der Spline-Interpolation zugrunde. Hierbei ist die Interpolationsfunktion S (x) eine abschnittsweise definierte Funktion, man unterteilt das Intervall Abbildung in dieser Leseprobe nicht enthalten in eine gewisse Anzahl von Teilintervallen und konstruiert für jedes einzelnes Teilintervall eine Polynom-Interpolation niedrigen Grades. Dies nennt man, wegen der einzelnen Arbeitsschritte stückweise Polynom-Interpolation bzw. Spline-Interpolation. Wie bei der Lagrange-Interpolation stellt auch bei dieser Methode die stückweise lineare Interpolation das einfachste Verfahren dar (Abb. 4.6). Dabei werden die Punkte (x 0(f (x 0)),…,(x n(f (x n)) durch Geraden verbunden. Dabei ist aber eine sehr hohe Anzahl an Stützstellen nötig, damit eine akzeptable Genauigkeit erreicht werden kann. Ein weiterer Nachteil ist, dass die einzelnen Splines an ihren Grenzen keine glatten Übergänge bilden und damit ist die aus Geradenstücken zusammengesetzte Interpolationsfunktion P (x) nicht glatt. Das bedeutet die interpolierte Funktion P (x) ist nicht differenzierbar.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.6 lineare Spline-Interpolation mit 5 Segmenten (splines)

4.4.2 kubische Spline-Interpolation

In der Praxis benötigt man sehr häufig einen glatten Kurvenverlauf, einschließlich glatter Übergänge zwischen den einzelnen Teilstücken. Darum verlangt man an den vorgegebenen Verbindungsstellen (Stützstellen), dass die Kurvenstücke ohne Sprung (stetig) und ohne Knick (differenzierbar) aneinander passen. Um einen glatten Kurvenverlauf zu gewährleisten, soll S (x) im Intervall [ x 0, x n] zweimal stetig differenzierbar sein, das heißt insbesondere an den Stützstellen sollen die Funktionswerte und die beiden ersten Ableitungen der dort zusammenstoßenden Polynome gleich sein. Um dies zu erreichen werden in der Regel Polynome dritten Grades verwendet. Bei stückweiser Polynom-Interpolation, welche auf jedem Segment Polynome dritten Grades verwendet, spricht man von kubischer Spline-Interpolation. Die Funktion, welche bei einer kubischen Spline-Interpolation entsteht wird kubischer Spline genannt. Mathematisch kann man zeigen, dass die so entstehenden Kurvenstücke durch kubische Polynome beschreibbar sind, das heißt für jedes Teilstück gilt das allgemeine Polynom:

Abbildung in dieser Leseprobe nicht enthalten

Eine Kubische Spline-Interpolation erzeugt somit zu n vorgegebenen Stützpunkten n -1 Polynome dritten Grades, welche an den Stützstellen zweimal stetig differenzierbar sind. Das heißt, dass die Polynome an den Segmentgrenzen stetig im Verlauf, in der Steigung und in der Krümmung sind. Da das kubische Polynom vier freie Parameter enthält, ist auf dem gesamten Intervall [ x 0, x n] die stetige Differenzierbarkeit der Interpolationsfunktion gewährleistet. Zusätzlich ist noch eine stetige zweite Ableitung garantierbar, welche für die Krümmung und damit für die glatten Übergänge zwischen den Kurvenstücken wichtig ist. Man unterscheidet zwei Arten der Splines mit denen glatte Übergänge geschaffen werden. Erstens gibt es Splines mit freien Rand, die sogenannten natürlichen Splines und Splines mit eingespannten Rand. Es gilt folgende Unterscheidung:

Abbildung in dieser Leseprobe nicht enthalten

Das heißt bei natürlichen Splines mit freien Rand ist die zweite Ableitung an den Übergangsstellen x 0, x 1,…, x n null. Dies bedeutet, dass an den Übergängen keine Krümmung und eine konstante Steigung vorhanden sind. Dadurch entsteht ein lineares Verhalten der Splines an den Übergängen und diese werden damit absolut glatt. Bei Splines mit eingespannten Rand müssen an den Randpunkten x 0, x 1,…, x n die Werte von f’ (x) oder zumindest hinreichend genaue Approximationen dieser Funktionswerte benötigt. Da für Splines mit eingespannten Rand mehr Informationen von f (x) in die Interpolation mit eingehen, liefert diese Art genauere Ergebnisse. Dennoch werden die natürlichen Splines häufiger verwendet, da die geforderten Informationen über f’ (x) meist nur unter erheblichen Aufwand bereitgestellt werden können. Dieser Aufwand ist im Vergleich zu der gering erhöhten Genauigkeit, im Normalfall, nicht effektiv und man greift in der Praxis sehr häufig auf die natürlichen Splines zurück.

Die kubische Spline-Interpolation ist die zurzeit mordernste und am häufigsten verwendete Interpolationsmethode. Dennoch ist die Berechnung der interpolierenden Splinefunktion mit erheblich größerem Rechenaufwand verbunden als beispielsweise das Aufstellen eines Interpolationspolynoms nach Lagrange. Die Spline-Interpolation ist jedoch für viele Anwendungen besser geeignet als die Interpolation durch eine einzige Polynomfunktion. Hierbei spielt besonders eine Eigenschaft eine Rolle. Unter allen zweimal stetig differenzierbaren Funktionen, die n +1 Stützpunkte interpolieren, also jene die eine "glatte" Kurve durch die Punkte bilden, ist die kubische Splinefunktion diejenige, welche die geringste Gesamtkrümmung aufweist.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4.7 Vergleich der Welligkeit von Lagrange- und kubischer Spline-Interpolation

In Abb. 4.7 kann man erkennen, dass die kubische Splinefunktion S (x) aus fünf einzelnen Polynomen p 0…4 besteht. Jedes dieser Polynome ist dritten Grades. Die Splines p 0…4 sind natürlich Splines, da ihre zweite Ableitung null ist, das heißt sie haben an den Übergängen keine Krümmung und laufen gerade ineinander. Die Funktion P (x), welche mit Lagrange-Polynomen erzeugt wurde, besteht im Gegensatz nur aus einem Polynom fünften Grades. Man kann eindeutig sehen, dass die Splinefunktion wesentlich glatter ist als die Lagrangefunktion. Dies zeigt, dass im Gegensatz zu Interpolationspolynomen, die besonders bei mehreren Stützpunkten starke Schwankungen und Wellen aufweisen können, kubische Splinefunktionen einen glätteren Kurvenverlauf besitzen. Sie ähneln somit mehr einer Kurve, die man durch die Verbindung der Punkte per Hand oder mit einem biegsamen Kurvenlineal erhalten würde. Ein solches elastisches Lineal (engl.: spline) kann daher als mechanisches Modell für die Spline-Interpolation angesehen werden. Ein weiterer Vorteil dieser Interpolationsmethode ist, dass die einzelnen Polynome dritten Grades leichter zu handhaben sind, beispielsweise bei der Berechnung von Zwischenwerten, als Polynome höheren Grades, die man zum Beispiel bei vielen Stützpunkten durch Interpolation nach Lagrange erhalten würde, wo Polynome fünften und höheren Grades keine Seltenheit sind.

5 Schlusswort

Neben diesen hier gezeigten kurzen Überblick über mehrere Interpolationsverfahren gibt es natürlich noch weitere, die je nach Anwendungszweck verwendet werden. Die Interpolation durch Polynomfunktionen, wie die Lagrange-Interpolation, ist zwar relativ leicht durchzuführen, sie stößt aber schnell an ihre Grenzen, wenn höhere Genauigkeit und somit mehr Stützstellen und höhere Funktionsgrade nötig sind. Die Spline-Interpolation dagegen kann bedenkenlos auch bei einer großen Anzahl von Stützstellen angewendet werden, auch wenn für jedes Segment ein einzelnes Polynom konstruiert werden muss und damit der Rechenaufwand erheblich ist. Nahezu in jedem wissenschaftlichen Bereich treten Arten von Interpolation auf, die hier beschriebenen Verfahren zur Polynom- und Spline-Interpolation bilden eine Grundlage für weitere, komplexere Interpolationsmethoden, welche für die jeweilige praktische Anwendung spezialisiert sind.

Quellenverzeichnis

Bücher

1 Dr. Ade, H., Dr. Schell, H., Themenhefte Mathematik – Numerische Mathematik, Stuttgart, Ernst Klett Verlag, 1975

2 Prof. Dr. Böhme, Gerd, Analysis 1, Berlin, Springer-Verlag, 6. Auflage, 1990

3 Dieudonné, Jean, Geschichte der Mathematik 1700-1900, Braunschweig, Vieweg & Sohn, 1985

4 Fichtenholz, G. M., Differential und Integralrechnung III, Berlin, VEB Deutscher Verlag der Wissenschaften, 11. Auflage, 1987

5 Prof. Dr. Hermann, Martin, Numerische Mathematik, München, Oldenbourg Verlag, 2001

Internet

6 http://www.geog.fu-berlin.de/~jkrywkow/silke/interpol.html

7 http://www.geophys.uni-stuttgart.de/skripten/inv/node8.html

8 http://www.gris.uni-tuebingen.de/gris/grdev/java/doc/html/german/3.1.2.html

9 http://www.mathproject.de/Funktionen/4_5.html

10 http://www.techfak.uni-bielefeld.de/~jsteil/html/script/numscript/s2node9.html

11 http://www.we.fh-osnabrueck.de/fbwe/vorlesung/edv2/node17.html

Sonstiges

12 Microsoft® Encarta® Professional 2002. © 1993-2001 Microsoft Corporation. Alle Rechte vorbehalten.

13 alle Bilder erstellt mit: Mathcad 2001 Professional, ©1986-2000 MathSoft, Inc. All rights reserved.