zur Übung aus
"Numerische Mathematik"
im Wintersemester 1998/99.
| Team: | Betreuer: |
|
|
1) Einleitung.....................................................1
1.1) Das Team des Projekts..............1
1.2) Aufgabenstellung.........................1
1.3) Verwendung des Programms.....11.3.1) Start des Programms...................1
1.3.2) Beschreibung der Menüleiste......3
1.3.3) Programmende.............................52) Mathematische Grundlagen...................................6
2.1) Interpolation auf beliebigen Stützen (Lagrange Interpolation).6
2.2) Tschebyscheffsche Interpolation.................................................7
2.3) Spline Interpolation.......................................................................8
2.4) Kurvendarstellung´........................................................................93) Beispiele.......................................................................................10
3.1) Interpolation auf beliebigen Stützen...........................................10
3.2) Interpolation auf Tschebyscheff-Stützen....................................17
3.3) Zweidimensionale Kurvendarstellung mit unterschiedlichen Parametrisierungen............................................................................194) Die graphische Darstellung..........................................................24
4.1) Zeichnen der Koordinatenachsen...........................................24
4.2) Zeichnen der Achsenbeschriftung...........................................24
4.3) Zeichnen der Interpolationsfunktion (nicht-parmetrisch)........25
4.4) Zeichnen der Interpolationsfunktion (parametrisch)...............265) Anhang (Quellencode)...............................................................27
Mitglieder der Projektgruppe sind:
Das Programm ist ein typisches Windows-95-Anwendungsprogramm. Der Programmname lautet "Interpolation". Zum Start des Programms muß nur der Ordner, in dem sich das Programm befindet, geöffnet werden. Das Programm kann dann wie üblich mit einem Doppelklick gestartet werden.
Nach dem Öffnen des Programms mit einem Doppelklick erscheinen folgende Fenster:
Sie haben nun im linken Fenster vier verschiedene Auswahlmöglichkeiten:
A) beliebige Stützen: Es erfolgt eine Lagrange-Interpolation mit beliebiger Stützstellenverteilung sowie zwei kubische Spline-Interpolationen (natürliche und nicht-natürliche) auf den selben Stützstellen.
B) Tschebyscheff-Stützen: Es erfolgt eine Lagrange-Interpolation auf den Tschebyscheff-Stützen im Intervall [-1,1] (dh es kann keine Intervalltransformation vorgenommen werden) sowie zwei kubische Spline-Interpolationen (natürliche und nicht-natürliche) auf den selben Stützstellen.
C) Parametrisch (t manuell): Es erfolgt eine 2-dimensionale Kurvendarstellung, wobei die Kurve auf vier verschieden Arten berechnet wird: parametrischer Lagrange, parametrischer Spline, mit x gezogener Spline und custom Spline! Der Parameter t sowie die Werte für x und y können nach erfolgtem Start im Koordinatenfenster manuell eingegeben werden (zB nach Anklicken des Buttons "Hinzufügen). Die Berechnung der Position des neuen Stützwertes in der Reihenfolge der Stützen erfolgt automatisch!
D) Parametrisch (t automatisch): Es erfolgt eine 2-dimensionale Kurvendarstellung, wobei die Kurve auf vier verschieden Arten berechnet wird: parametrischer Lagrange, parametrischer Spline, mit x gezogener Spline und custom Spline! Die Bestimmung des Parameters t erfolgt automatisch. Im Gegensatz zur Auswahl C) kann hier jedoch die Position des neuen Wertes eingegeben werden!
Nach erfolgter Auswahl erscheint folgendes Bild:
Im Menü Datei finden sich die unter Windows üblichen Befehle "Neu, Öffnen, Schließen, Speichern unter, Drucken, Seitenansicht, Druckereinrichtung, zuletzt verwendete Dateien und Beenden". Diese bedürfen hier wohl keiner Erklärung.
Im Menü Funktionen können die drei bzw. vier gezeichneten Kurven aus und wieder eingeblendet werden. Die verschiedene Kurven können auch mit den entsprechenden Buttons in der Symbolleiste aus bzw. eingeblendet werden (Verharren mit dem Mauszeiger auf einem Button bewirkt wie in Windows üblich das Anzeigen der Button-Funktion). Dabei gelten folgende Farbzuweisungen:
Beliebige Stützen bzw. Tschebyscheff-Stützen:
Lagrange-Polynom: blau
Natürlicher Spline: grün
Nicht-natürlicher Spline: rot
Parametrisch (t manuell bzw. t automatisch):
Lagrange-Polynom: blau
Parametrischer Spline: grün
Gezogener Spline (mit x): rot
Custom Spline (selbst entworfen): ocker
Des weiteren befinden sich im Menü Funktionen sowie auf der Symbolleiste die zustandsbezogenen Befehle Splineeinstellungen bzw. gezogener Spline.
Wurde nach dem Start des Programms die Auswahl beliebige Stützen oder die Auswahl Tschebyscheff-Stützen getroffen, so ist der Befehl Splineeinstellungen aktiv. Wurde nach dem Start des Programms eine der beiden Möglichkeiten der parametrischen Interpolation gewählt, so ist der Befehl gezogener Spline aktiv.
Nach dem Anklicken des aktiven Befehls erscheint das entsprechende Fenster:
Im linken Fenster können Einstellungen für den nicht-natürlichen Spline vorgenommen werden. Entweder es wird die not-a-Knot-Bedingung aktiviert, oder es werden die Werte der 1., 2. oder 3. Ableitung für x0 und xn angegeben. Wird die dritte Möglichkeit ausgewählt und die Werte an x0 und xn werden nicht verändert (voreingestellt ist 0), so entspricht das genau der Definition des natürlichen Splines und die beiden Kurven sind deckungsgleich!
Im rechten Fenster können Einstellungen für den custom Spline vorgenommen werden. Die Wahlmöglichkeiten nicht ziehen und Tension mit x entsprechen den beiden voreingestellten Splines mit den Farben rot und grün. Bei Tension mit y wird der Spline in y-Richtung gezogen und bei Tension mit pow(DeltaS,...) wird der Spline in x- und y-Richtung und abhängig vom eingegebenen Parameter gezogen!
Eine genauere Beschreibung der Möglichkeiten erfolgt im Kapitel Mathematische Grundlagen!
Im Menü Werte können Stützstellen verändert, gelöscht oder hinzugefügt werden. Dieselben Funktionen sind auch im Koordinatenfenster implementiert. Außerdem kann im Menü Werte auch der Funktionswert berechnet werden (Die Eingabe eines Wertes für x oder t liefert die Werte der 3 bzw. 4 unterschiedlichen Interpolationsfunktionen). Diese Funktion ist auch auf der Symbolleiste zu finden. Der letzte Befehl in diesem Menü lautet Zufallswerte einfügen (5 Stück) und kann auch mehrmals hintereinander betätigt werden. Es können jedoch nie mehr als 50 Stützstellen eingegeben werden!
Das Menü Koordinaten beinhaltet die selben Funktionen wie die sog. Zoom-Symbolleiste am linken Rand des Programmfensters. Es ist hier möglich nach links, rechts, oben und unten zu scrollen bzw. die Skalierung der x- und der y-Achse zu vergrößern und zu verkleinern (zoom out / zoom in). Der Befehl Reset zoom stellt die Standardeinstellungen wieder her. Sollte bei diesem Vorgang eine der Achsen aus dem Bild wandern, so wird sie in türkiser statt in blauer Farbe wieder eingeblendet!
Im Menü Ansicht kann die Symbolleiste, die Statusleiste, die Zoom-Symbolleiste bzw. das Koordinatenfenster ein- und ausgeblendet werden.
Im Menü Fenster finden sich die in Windows üblichen Befehle und unter dem Symbol ? ist Information über das Programm zu finden.
Des weiteren befinden sich auf der Symbolleiste noch folgende zusätzliche und nicht zum Windows-95-Standard zählende Buttons:
Koordinatenkreuz: Verbergen bzw. einblenden des Koordinatenkreuzes.
Achsenbeschriftung: Verbergen bzw. einblenden der Achsenbeschriftung.
Stützbeschriftung: Ein- bzw. ausblenden der Werte an den Stützstellen.
Stützkreuze: Verbergen bzw. einblenden der Stützen (blaue Kreuze im Koordinatensystem).
Lagrange auch außer Intervall: zeichnet die Lagrange-Interpolationsfunktion auch außerhalb des Intervalls (des größten und kleinsten x-Wertes), bzw. verbirgt sie dort. Dieser Button ist bei parametrischer Interpolation selbstverständlich inaktiv!
Natürlich können Interpolationsfunktionen auch gedruckt, gespeichert bzw. wieder geöffnet werden. Anmerkung: Gedruckt wird genau jener Bereich und jene Funktionen, die am Bildschirm gerade sichtbar sind.
Das Programm kann wie jedes andere Windows 95-Programm mit dem Befehl Beenden im Menü Datei oder einem Mausklick auf das Kreuz im rechten oberen Eck des Programmfensters beendet werden.
Ziel der Lagrangeinterpolation ist es, ein Polynom n-ten Grades anzugeben, welches für gegebene Stützstellen xi und zugehörige Stützwerte yi die Interpolationsbedingung Pn(xi) = yi erfüllt. Dieses Interpolationspolynom ist eindeutig bestimmbar und hat folgende Gestalt:
Pn(x) = 
mit Li (x) = 
(i = 0, 1, …, n)
Die Darstellung der Pn(x) ist für praktische Zwecke allerdings nicht geeignet, da ihre Auswertung viel zu aufwendig wäre. Aus diesem Grund kommt man nach algebraischen Umformungen zu der sogenannten baryzentrischen Formel zur Berechnung des interpolierenden Wertes Pn(x) an der Neustelle x:
mit 
(i
= 0, 1, …, n) und li = 
Damit können für jede neue Interpolationsstelle x die 
sukzessive berechnet und die Zahl der Stützstellen leicht erhöht werden. Kommt eine neue
Stützstelle xn+1 hinzu, so können die zugehörigen Stützkoeffizienten lin+1 unter Ausnützung der bekannten Werte linauf folgende Art berechnet werden:
lin+1 = lin/ (xi-xn+1)
Diese Beziehung erlaubt es, die ersten n+1 Stützkoeffizienten lin+1 durch je nur eine Division aus den lin zu gewinnen. Der Rechenaufwand (wesentliche Operationen) für die Bereitstellung der li beträgt damit insgesamt 1/2 ´ n ´ (n+1).
Bei der Interpolation auf Tschebyscheffstützen sind die Stützstellen genau die Nullstellen der Tschebyscheffpolynome. Die Tschebyscheffpolynome sind rekursiv definiert:
T0(x) = 1, T1(x) = x Tn+1(x) = 2´ x´ Tn(x) – Tn-1(x)
Mit Tn(x) = cos (nj ) x = cos(j )
Die n Nullstellen von Tn(x) sind:
, (k = 1, 2, …,n);
Diese verteilen sich im Intervall [-1,1] nicht äquidistant, sondern liegen gegen Ende des Intervalls dichter. Außerdem sind sie symmetrisch um den Nullpunkt verteilt.
Dem Benützer des Programms ist es daher nur möglich, die Stützwerte einzugeben. Das Programm berechnet dann automatisch die zur Interpolation benötigten Nullstellen, deren Position selbstverständlich von der Anzahl der eingegeben Werte abhängt.
Zur Darstellung der Funktion wird folgende Linearkombination der Tschebyscheffpolynome verwendet:
Pn(x) = 
mit den Koeffizienten 
.
Der Grund, warum die Nullstellen des Tschebyscheffpolynoms als Stützpunkte verwendet werden liegt in der Minimierung des Interpolationsfehlers. Der Interpolationsfehler läßt sich in diesem Fall auf folgende Art abschätzen:
½ f(x)-Pn(x)½£
wobei Mn+1 = 
Ziel der Spline-Interpolation ist es, mit Hilfe von Polynomsplines dritten Grades (kubischer Spline) eine möglichst glatte Kurve zu konstruieren, die durch vorgegebene Punkte (xi , yi) geht. Bei monotoner Anordnung der Stützstellen (x0, …, xn), kann die gesuchte Kurve durch eine Splinefunktion S dargestellt werden, die sich stückweise aus kubischen Polynomen Pi = ai + bi (x-xi) + ci (x-xi)2 + di (x-xi)3 für x Î [xi, xi+1] (i = 0, 1, …,n) zusammensetzt. Die Pi müssen dabei folgenden Randbedingungen erfüllen:
Außerdem unterscheidet man noch zwischen natürlichem und nicht natürlichem Spline.
Beim natürlichen kubischen Spline muß noch folgende Bedingung erfüllt sein:
5 a.) S´‘(x0) = S´‘(xn) = 0
Bei den nicht natürlichen Splines können die Werte der ersten, zweiten oder dritten Abbleitung an den Intervallenden vom Benutzer beliebig vorgegeben werden.
5 b.) S´(x0) = a S´(xn) = b bzw. S´´(x0) = a S´´(xn) = b bzw. S´´´(x0) = a S´´´(xn) = b
Bei der not-a-knot Bedingung stimmen auch die dritten Ableitungen der Splinefunktion in den Knoten x1, xn-1 überein. Damit sind x1, xn-1 keine echten Knoten der Splinefunktion ("not a knot"). Auch hier handelt es sich um einen nicht natürlichen Spline.
Im Falle des natürlichen Splines ergibt sich für die Koeffizienten ai,
bi, ci, di das Gleichungssystem A c = a:
A =
c = 
und a = 
wobei hi = xi+1 xi i = 0, 1, … n-1.
Die Matrix A ist tridiagonal, stark diagonal dominant, besitzt nur positive Elemente und ist positiv definit. Deswegen ist das System gut konditioniert, so daß die Lösung des Gleichungssystem ohne Pivotsuche oder Nachiteration numerisch leicht ermittelbar ist.
Bei allen anderen Arten der Splineinterpolation ändert sich das Gleichungssystem leicht ab, ohne dabei allerdings seine guten Eigenschaften zu verlieren.
Oft ist es nicht möglich eine Kurve in der Form y = f(x) anzugeben. In diesem Fall ist für die gesuchte Kurve die Parameterdarstellung x = x(t) bzw. y = y(t) mit t als Kurvenparameter zu verwenden. Dann ist es notwendig, sowohl für die Wertepaare (tk, xk) als auch für die Wertepaare (tk, yk) die Spline-Interpolierende zu bestimmen, die dann zusammen die gesuchte Kurve bestimmen.
Es gibt mehrere Arten, wie der Kurvenparameter t gewählt werden kann. Die herkömmlichste Variante ist es, ihn als Bogenlänge der Kurve zu wählen. Dabei werden die Parameterwerte tk folgendermaßen bestimmt:
t0 = 0; tk = tk-1 + D
t; 
k = 1, 2, …,n
Eine andere Möglichkeit besteht darin, durch spezielle Parameterwahl die
Splinefunktion zu "ziehen" (Spline under tension).
Bei diesem Ziehen sind verschiedene Berechnungsarten für das D
t denkbar. Zum einen ist das ein Ziehen mit D x, also:
wobei D s den Abstand der beiden aufeinanderfolgenden Stützstellen darstellt (also das D t von oben).
In diesem Fall wird die Funktion in x-Richtung gezogen. Analoges ist natürlich auch für die y-Richtung möglich. Ein Problem bei dieser Art des Ziehens tritt auf, wenn zwei Stützen sich in x-Richtung nur sehr wenig unterscheiden. Dann wird nämlich D t für diese beiden Stützen sehr klein, was sich dadurch auswirkt, dass der Spline in den restlichen Intervallen sehr große Ausbuchtungen hat. Nähere Erläuterungen bzw. Beispiele finden sich im nächsten Kapitel.
Als einen Vorschlag von uns bieten wir dem Benutzer weiters die Möglichkeit, die Parametrisierung nach folgender Formel durchzuführen, wobei p einen vom Benutzer (frei) wählbaren Zahlenwert darstellt:
Empirisch hat sich dabei ein Wert von p = 0.5 als äußerst gute Wahl erwiesen. Dies heisst, dass D t die Wurzel aus dem Abstand der beiden Stützstellen darstellt. Damit werden unnötige Ausbuchtungen in der Kurve "weggezogen", der Spline aber nicht allzu straff gespannt. Auch hier finden sich Beispiele und Vergleiche mit anderen Methoden des Ziehens im folgenden Kapitel.
Beispiel : Treppenfunktion (siehe Punkte im Koordinatenfenster)
f(x):= 0 für 0 Ì x Í 1 f(x):= 1 für 1 Ì x Í 2
f(x):= 2 für 2 Ì x Í 3 f(x):= 3 für 3 Ì x Í 4
f(x):= 4 für 4 Ì x Í 5
Das Lagrange Polynom schwingt an den Rändern des Intervalls sehr stark, während die beiden Splines selbstverständlich die Funktion wesentlich besser approximieren (Doku1).
Seite 11, oberes Bild: Um zu zeigen, wie weit das Lagrange Polynom an den Intervallrändern "davonschwingt", wurde die Skalierung der y-Achse verkleinert!
Seite 11, unteres Bild: Eine Verbesserung kann bereits sehr einfach durch die Eingabe weiterer Stützstellen, die gegen die Enden des Interpolationsintervalls dichter liegen, erzielt werden (Doku2).
Liegen die eingegebenen Werte der Treppenfunktion näher an den Sprungstellen (zB: statt 0.9 und 1.1 wird der Sprung von 0.99 auf 1.01 durchgeführt), so oszillieren die Interpolationsfunktionen wesentlich stärker (Doku3)!
Auf der gegenüberliegenden Seite sehen Sie ein Beispiel eines Ausdrucks einer Funktion! Bei Eingabe von äquidistanten Stützstellen wird der Interpolationsfehler bei der Lagrange-Methode oft sehr groß und die Interpolationsfunktion oszilliert an den Intervallenden mit hohen Amplituden. Die Spline-Interpolationsfunktionen approximieren die Treppenfunktion hier sehr gut (Doku4).
Auf der gegenüberliegenden Seite ist wieder ein Ausdruck einer Funktion zu sehen. Das Lagrange-Interpolations-Polynom wird nicht dargestellt. Mit den angegebenen Stützen ist der natürliche Spline offensichtlich sehr gut konditioniert, wogegen der nicht-natürliche Spline (hier: mit not-a-knot-Bedingung) stark oszilliert (Doku5).
Der nicht-natürliche Spline mit den gegebenen 1. Ableitungen (hier: x0=xn=0) hat jedoch einen noch besseren Verlauf als der natürliche Spline, wie auf der Abbildung auf dieser Seite gut zu sehen ist (Doku5)!
Sind die Werte der zu approximierenden Funktion an den Intervallenden sehr stark gekrümmt, dann sind die beiden Randbedingungen des natürlichen Splines nicht problemgerecht! Besonders in diesen Fällen eignet sich oft eine der angebotenen Einstellungen für nicht-natürliche Splines besser! Als Beispiel sei hier die Funktion x11 angeführt (Doku6):
Der nicht-natürliche Spline ist hier auf die not-a-knot-Bedingung eingestellt und approximiert die Funktion f(x) = x11, die im negativen Bereich nur negative Werte annimmt, hier sichtbar besser!
Am Ausdruck auf der gegenüberliegenden Seite ist ein weiteres Beispiel für einen natürlichen Spline mit großem Fehler und einem wesentlich besseren nicht-natürlichen Spline (not-a-knot) mit kleinem Fehler zu sehen (Stützstellen: 4 Punkte der Funktion f(x) = x2 ; Doku7).
Abschließend seien noch drei weitere Beispiele angeführt!
Beispiel Doku8 auf dieser Seite zeigt, daß es bei bestimmten Vorgaben möglich ist, daß die Graphen zB im Punkt x0 in völlig verschieden Richtungen führen! Bei Betrachtung der Stützstellen scheint hier der natürliche Spline am besten zu verlaufen.
Beispiel Doku9 auf Seite 16 zeigt, daß bei Angabe vieler Stützstellen der Unterschied zwischen dem zunehmend schlechter werdenden Lagrange Interpolationspolynom, dem relativ guten nicht-natürlichem Spline und dem sehr wenig oszillierenden natürlichen Spline immer größer wird (besonders gut zu sehen bei erster und letzter Stützstelle).
Auch auf dem Bild Doku10 ist ein großer Unterschied zwischen dem stark oszillierenden Lagrange-Graphen und dem natürlichen Spline zu sehen. (Ergänzung zu Kapitel 1: Wie auf diesem Bild zu sehen ist, kann das Koordinatenfenster auf der rechten Bildschirmseite fixiert werden, und zwar mit einem Doppelklick auf die Kopfleiste! Die Funktion wird dann nur mehr auf der restlichen linken Bildschirmseite angezeigt, was zum Vorteil hat, daß das Koordinatenfenster nicht "im Weg" sein kann. Das Koordinatenfenster kann jedoch auch wieder in eine andere Position gezogen werden!)
Wie schon im 2. Kapitel erwähnt zeigt die Lagrange Interpolation auf Tschebyscheff-Stützen wesentlich bessere Approximationseigenschaften als auf beliebigen Stützen!
Im Gegensatz zu den Beispielen im vorigen Kapitel oszilliert das Lagrange Polynom auch bei vergleichsweise vielen Tschebyscheff-Stützen eher wenig!
Im Beispiel Doku11 sind 39 Stützen vorgegeben, und das Lagrange-Interpolationspolynom oszilliert nur unwesentlich mehr als die Spline-Graphen!
Der Berechnung der Graphen im Beispiel Doku12 auf der nächsten Seite liegen nur 3 Werte mehr zu Grunde (also 42). Diese bewirken aber ein jetzt völlig unbefriedeigendes Verhalten des Lagrange-Graphen
Beispiel Doku13 auf Seite18 unten zeigt die gewöhnliche Interpolation der Funktion f(x) = x/(x2+0.1) mit 12 äquidistanten Stützstellen im Intervall [-1,1].
Auf der nachfolgenden Seite ist ein Ausdruck der Lagrange-Interpolation dieser Funktion auf 12 Tschebyscheff-Stützen zu sehen (Doku14). Der Unterschied zu Doku13 ist bemerkenswert!
Die den einzelnen Methoden zu Grunde liegenden Parametrisierungen können in Kapitel 2.4 nachgelesen werden! Der Parameter p des custom splines wird bei den gezeigten Beispielen immer mit 0.5 angenommen!
Beispiel Doku15 zeigt anschaulich die Vorteile der Splinedarstellung bei der zweidimensionalen Kurvendarstellung. Die "paramatrische Lagrange-Kurve" zeigt sehr viele Ausbuchtungen an Stellen, wo gar keine Punkte angegeben sind und approximiert die Kurve zumindest am Rand des Intervalls nur ganz in der Nähe der angegebenen Punkte. Die Spline-Interpolation liefert hingegen eine sehr glatte parametrische Kurve!
Das Beispiel Doku16 zeigt einen großen Nachteil der Tension mit x: haben 2 aufeinanderfolgende Punkte den selben x-Wert, so sind die Ausbuchtungen dieses Splines sehr stark und er bringt in diesem Fall keine Verbesserung. Ein sehr glatte Kurve liefert hier der custom Spline.
Wählt man beim custom spline Tension mit y, so ist das Ergebnis wegen der Punkte 4 und 5 ebenfalls sehr schlecht.
Der Ausdruck auf der nächsten Seite zeigt ein ähnliches, nur etwas weniger krasses Beispiel! Auf Grund der ersten beiden nahe zusammenliegenden x-Werte (0; 0,2) entsteht nach dem zweiten Wert eine Ausbuchtung beim mit x gezogenen Spline (rote Kurve; Doku 17)!
Der nicht gezogene Spline (grün) bzw. der custom spline (ocker) haben einen wesentlich besseren Verlauf, wogegen die Lagrange-Kurve (blau) wie immer etwas schlechter ist.
Wenn 2 aufeinanderfolgende Punkte nahezu gleiche x- oder y-Werte haben, kann man demnach schon vor der Berechnung mit an Sicherheit grenzender Wahrscheinlichkeit voraussagen, daß die Tension mit x bzw. die Tension mit y keine Verbesserung des nicht gezogenen Splines mit sich bringt!
Im Beispiel Doku18 bildet die Lagrange-Kurve zwei kleine unerwünschte Schlaufen! Der custom Spline ist auf Tension mit y eingestellt und bringt sogar noch eine weitere Verschlechterung der Situation mit sich (ocker)! Der in x-Richtung gezogene Spline bringt hier eine wesentliche bessere Approximation (rot)!
Im Beispiel Doku19 sind die gleichen Stützen gegeben wie in Doku18. Als Vergleich ist der in x-Richtung gezogene Spline ein zweites Mal abgebildet. Es ist deutlich zu sehen, daß er ein besseres Ergebnis als der nicht gezogene Spline bringt (grün, Schlaufenbildung)! Die beste Annäherung ist wieder einmal beim custom Spline (in beide Richtungen gezogen, p=0.5) zu sehen (ocker). Diese Einstellung bringt in den meisten Fällen eine sehr gute Approximation!!
Auf der nächsten Seite (Doku20) ist eine ähnliches Beispiel zusehen. Die Lagrange Kurve hat starke Ausbuchtungen, der nicht gezogene Spline sieht schon sehr gut aus und der in x-Richtung gezogene Spline bringt eine weitere marginale Verbesserung. Die beste Approximation liefert wieder der custom Spline!
Danach folgen noch zwei weitere typische Beispiele für die Kurvendarstellung mit unterschiedlichen Interpolationsmethoden! Beide Fälle (Doku21, Doku22) zeigen eine sehr "schlechte" Lagrange-Kurve und eine sehr glatte custom Spline-Kurve!
Die gesamte graphische Darstellung der Interpolationsberechnungen ist in der Quelldatei InterpolationView.cpp implementiert. Die wichtigsten Methoden dieser Datei erfüllen folgende Aufgaben:
sowie weitere Methoden, die u.a. das Drucken der Ergebnisse oder die Umrechnung von Koordinateneinheiten in Pixel beinhalten.
Der Name der Methode zum Zeichnen der Koordinatenachsen lautet CInterpolationView::PaintAxes. Diese Methode berechnet zunächst die Bildschirmposition des Koordinatenursprungs. Falls dieser außerhalb des dargestellten Bereichs liegt – etwa, weil das Fenster entsprechend gezoomt oder verschoben wurde – wird die eigentlich außerhalb liegende Achse dennoch gezeichnet, allerdings in einer helleren Farbe. So kann man sofort erkennen, in welcher Größenordnung der dargestellte Bereich liegt, ohne daß es aber zu Verwechslungen kommen könnte, weil die Achse ja im Grunde nicht im dargestellten Bereich liegt.
An die Methode zur Achsenbeschriftung (Zeichnen kurzer Linien auf den Achsen und Ausgabe des entsprechenden Zahlenwertes), CInterpolationView::PaintAxesTicks, wird unter anderem ein Pointer auf die Klasse IntTemplate übergeben. Von IntTemplate werden ja die Klassen Interpoly und Interpolation2D abgeleitet; dadurch erreicht man, daß sowohl für die nicht-parametrische als auch für die parametrische Variante die selbe Methode PaintAxesTicks verwendet werden kann. Ein weiterer Parameter der Methode ist die "Art" der Achsenbeschriftung. Dies ermöglicht es dem Benutzer, die Einteilung der Achsen entweder äquidistant oder auf den Stützstellen und –werten des Problems vornehmen zu lassen (oder natürlich auf beide Arten).
Falls nun die äquidistante Einteilung und Beschriftung gewählt wird, tritt das Problem auf, die Schrittweite dieser Einteilung in Abhängigkeit vom jeweils dargestellten Bildschirmbereich allgemeingültig zu berechnen. Der Bildschirmbereich kann ja durch Zoomen oder Verschieben verändert werden, die Achseneinteilung soll aber doch für alle solchen Fälle funktionieren. Die Schrittweite, also die Feinheit der Einteilung, kann daher nicht fest vorgegeben werden.
Es ist klar, daß die Schrittweite logarithmisch vom dargestellten Koordinatenbereich abhängen muß. Da das logarithmische Resultat allerdings zweckmäßigerweise gerundet werden muß, würde es bei einer so einfach gearteten Berechnung stets bei bestimmten Größen des dargestellten Bereichs zu einem Sprung in der Schrittweite kommen – was äußerst unerwünscht ist. Ein solches Verfahren zur Schrittweitenberechnung ist quasi numerisch schlecht konditioniert: Die Feinheit der Achseneinteilung verändert sich sehr stark (springt!) – bei kleinen Änderungen des dargestellten Koordinatenbereichs.
Um diesen Sprung in der Feinheit zu vermeiden, wird folgende Vorgangsweise gewählt: Der dargestellte Koordinatenbereich wird als Zahl im Format x.xx...*e^yy (scientific notation) dargestellt; nun wird die Mantisse dieser Darstellung (x.xx...) gerundet und mit der vorher logarithmisch berechneten "groben" Schrittweite multipliziert. So wird der logarithmische Wert also mit der Größe des Koordinatenbereichs gewichtet. Auf diese Weise kann das Springen der Schrittweite gänzlich vermieden werden, und der Übergang erfolgt nicht mehr durch einen Sprung, sondern quasi stetig.
Nun beginnt man an einer bestimmten Stelle auf jeder Achse (für die x-Achse am negativen Ende, für die y-Achse am positiven), zeichnet jeweils eine kurze Linie, die Achseneinteilung, und den dazugehörigen Wert auf der Achse. Falls nun der Bildschirmbereich verändert wird, ist die Beschriftungsfunktion doch noch allgemein gültig und liefert stets eine vernünftige Einteilung. Die numerische Ausgabe erfolgt übrigens mit maximal 6-stelliger Genauigkeit; falls schon nach weniger als 6 Stellen keine signifikanten Dezimalstellen mehr folgen, wird die Ausgabe aber nach den signifikanten Stellen abgebrochen.
Die Einteilung der Achsen auf den Stützstellen und –werten ist einfacher zu realisieren. Nach einer Abfrage, ob die zu beschriftenden Werte auch tatsächlich auf dem Bildschirm liegen, muß nur noch die kurze Linie auf der Achse gezeichnet und der numerische Wert ausgegeben werden. Wieder erfolgt die numerische Ausgabe mit höchstens 6-stelliger Genauigkeit.
Es können übrigens auch beide Arten der Achseneinteilung zugleich aktiviert werden.
An diese Methode, CInterpolationView::PaintFunction, wird u.a. ein Pointer auf ein Objekt der Klasse Interpoly übergeben; dies ist eben ein nicht-parametrisches Interpolationspolynom. In dieser Methode erfolgen zunächst zwei Berechnungen:
Als nächstes stellt sich die Frage nach der Berechnungsschrittweite für die graphische Auswertung; diese ist ja auch gleichbedeutend mit der Anzahl der Funktionsauswertungen! Der Abstand zwischen zwei Funktionsauswertungen soll eben einerseits nicht zu klein sein, um nicht eine allzu große Rechenzeit in Kauf nehmen zu müssen. Andererseits soll die Schrittweite auch hinreichend klein sein, weil die graphische Ausgabe zwischen den berechneten Funktionswerten zwangsläufig linear ist; um eine genügend glatte Darstellung zu erreichen, darf man die Schrittweite also auch nicht allzu groß wählen. Nach einigen Tests sind wir zum Ergebnis gekommen, daß eine Schrittweite von 3 Pixeln gut sein dürfte. Diese Zahl mag klein erscheinen, sie ist aber in der Praxis unproblematisch, weil die Funktionsauswertungen äußerst schnell erfolgen. Und eine so kleine Berechnungsschrittweite führt zu einer sehr glatten graphischen Darstellung und praktisch nie zu Stellen, an denen die Funktion "für das Auge" nicht differenzierbar ist, also zu Knicken.
Die Methode zum Zeichnen parametrischer Interpolationspolynome heißt – wie oben – CInterpolationView::PaintFunction. Diesmal wird allerdings nicht ein Pointer auf Interpoly, sondern ein Pointer auf Interpolation2D übergeben. Die beiden Methoden zur Polynomauswertung können nicht mehr – wie dies bei PaintAxesTicks – gleich gewählt werden, denn die Funktionsauswertung ist im parametrischen und im nicht-parametrischen Fall natürlich verschieden.
Im parametrischen Fall kann man nun für die Berechnungsschrittweite natürlich nicht mehr einen fixen Abstand in Pixeln wählen, da in diesem Fall ja an den Parameterstellen auszuwerten ist! Die Schrittweite muß also "in t" (in Parameterwerten) berechnet werden. Um auch hier wieder zu vernünftigen Ergebnissen zu kommen, gehen wir auf eine Art und Weise vor, die ich im folgenden kurz beschreibe:
Die Schrittweite muß sinnvollerweise von Intervall zu Intervall verschieden gewählt werden; dies hängt mit der Wahl der Parametrisierung zur Berechnung der beiden Polynome zusammen. Zunächst wird daher die Anzahl der Funktionsauswertungen für jedes Intervall berechnet. Berechnungsgrundlage dafür ist die Näherung der Bogenlänge zwischen zwei Punkten (also in Wirklichkeit ihr euklidischer Abstand) in Pixeln. Dieser wird nun durch eine Konstante (STEP_2D) dividiert, die die Feinheit der Unterteilung angibt und die sich nach einigen Tests als günstig erwiesen hat. Der so erhaltene Wert gibt also zunächst die Anzahl der Polynom-Auswertungen in einem bestimmten Teilintervall an. Um nun zur Schrittweite des Parameters t zu gelangen, wird die Differenz des Parameterwerts der beiden Endpunkte durch die Anzahl der Auswertungen dividiert.
Zur Klärung ein Beispiel anhand eines einzelnen Teilintervalls: Es sei STEP_2D = 2, der Abstand der beiden Intervallendpunkte gleich 200 (in Pixeln!). So ergibt sich, daß in diesem Intervall die beiden Interpolationspolynome jeweils 200/2 = 100 Mal ausgewertet werden. Sei nun ta = 0.3 für den Startpunkt des Intervalls, und ta+1 = 0.55 für den Endpunkt. Die Differenz beträgt also 0.25, und es ergibt sich eine Funktionsauswertung an t = 0.3, t = 0.325, t = 0.35, t = 0.375, ...
Zum Schluss folgt noch der Ausdruck des Quellencodes! Die Programmierung erfolgte objektorientiert! Das Hauptprogramm bzw. die Algorithmen für die einzelnen Interpolationsmethoden sind in funktions.h und functions.cpp zu finden.
Auf der mitgelieferten Diskette befindet sich im Hauptverzeichnis das Programm (Interpolation.exe).
Im Ordner Beispiele sind alle Beispiele, die in der Dokumentation verwendet worden sind sowie einige weitere Beispiele vorhanden! Dabei wurden gewöhnliche Interpolationen mit den Namen GewoX, Interpolationen auf den Tschebyscheff-Stützen mit den Namen TscheX und Kurvendarstellungen mit den Namen KurX bezeichnet!
Im Ordner Quellencode findet sich der Source-Code des Programms.
Back to the index page of the interpolation project