7.1 Einleitung

Bearbeiten

Bei der Polynominterpolation stellt sich mit wachsender Stützstellenzahl häufig ein oszillierendes Verhalten der Polynome ein und kann nach dem Satz von Faber im Fall, dass die Stützwerte von einer gegebenen Funktion herrühren, nicht notwendig mit gleichmäßiger Konvergenz der Interpolationspolynome bei feiner werdenden Gittern gerechnet werden. Diese Tatsachen motivieren die Einführung der in diesem Abschnitt betrachteten Splinefunktionen zur Interpolation, welche in vielen mathematischen Bereichen Anwendung finden. Für deren Definition sei

(7.1)  

eine fest gewählte Zerlegung des Intervalls  . Ihre Elemente   bezeichnet man im Zusammenhang mit Splines (aus historischen Gründen) meist als Knoten.

Definition 7.1

Bearbeiten
Eine Spline-Funktion oder kurz ein Spline der Ordnung   zur Zerlegung   von   mit Knoten   ist eine Funktion  , die auf jedem Intervall   der Zerlegung mit einem Polynom  -ten Grades übereinstimmt. Den Raum solcher Splines bezeichnet man mit
 
Man spricht von einem interpolierenden Spline   mit (gegebenen) Stützwerten    , wenn gilt:
(7.2)  

Ein Spline   ist also durch   Polynome

 

gegeben, wobei   nur auf dem Teilintervall   der Zerlegung   betrachtet wird. In den inneren Knoten     von   gelten wegen   die Glattheitsbedingungen

(7.3)  

Dies sind insgesamt   Bedingungen. Für einen interpolierenden Spline   mit Stützwerten     kommen gemäß (7.2) dazu noch die   Interpolationsbedingungen

(7.4)    

Für die Konstruktion eines interpolierenden Splines sind also insgesamt

(7.5)  

Glattheits- und Interpolationsbedingungen zu erfüllen.

Offenbar ist   mit den üblichen Verknüpfungen ein linearer Vektorraum. Dieser enthält alle Polynome vom Grad   sowie die abgebrochenen Potenzen vom Grad  

 

für  . Denn wegen

(7.6)  

sind letztere Funktionen insbesondere  -mal stetig auf   differenzierbar. Der folgende Satz besagt, dass die abgebrochenen Potenzen vom Grad   zusammen mit den Monomen   eine Basis des Spline-Raumes   bilden.

Satz 7.2

Bearbeiten
Es gilt
(7.7)  
sowie
 

Zur Konstruktion eines Splines   hat man höchstens   Freiheitsgrade. Denn auf dem Intervall   kann man jedes Polynom vom Grad  , also   Koeffizienten bzw. Parameter frei wählen. Die zu den folgenden   Intervallen   gehörenden Polynome   haben insgesamt   Koeffizienten, von denen aber   durch die Glattheitsforderungen (7.3) festgelegt sind, so dass man höchstens

 

weitere Freiheitsgrade hat. Daher ist   und es bleibt zu zeigen, dass die   Funktionen in (7.7) linear unabhängig sind.

Sei dazu

 

Für   schließt man aus (7.6)

 

und daher

 

Wenden wir für   die linearen Funktionale

 

auf   an, so folgt demzufolge mit dem Kroneckersymbol  

 

Also gilt

 

was auch     impliziert.

q.e.d.

Die in (7.7) angegebene Basis von   ist für praktische Zwecke jedoch nicht geeignet. So erweist es sich als ungünstig, dass die Träger der Funktionen, welche die Basis bilden, d. h. die Bereiche, auf denen diese Funktionen verschieden von Null sind, nicht endlich sind. Ferner sind die Monome für große   sowie die abgebrochenen Potenzfunktionen für dicht beieinander liegende Knoten nahezu linear abhängig, was die Auswertung eines Splines in einem Punkt mittels dieser Basis zu einer numerisch schlecht konditionierten Aufgabe macht. Für die Herleitung einer numerisch günstigeren Basis von  , welche aus Funktionen mit kompaktem Träger, d. h. Funktionen, die außerhalb eines abgeschlossenen Intervalls identisch Null sind, gebildet wird, sei auf Deuflhard/Hohmann, S. 245 ff., verwiesen.

Im Folgenden werden wir für interpolierende Splines der Ordnung   (lineare Splines) und der Ordnung   (kubische Splines) Algorithmen zu ihrer Berechnung sowie Fehlerabschätzungen angeben. Splines der Ordnung   (quadratische Splines) spielen in der Praxis eine geringere Rolle und werden daher hier nicht behandelt.

7.2 Interpolierende lineare Splines

Bearbeiten

Wir wollen uns zunächst mit interpolierenden linearen Splines   für gegebene Knoten   und Stützwerte     beschäftigen. Für jedes   besitzt ein solcher Spline auf dem Intervall   mit einem Polynom   offenbar die Darstellung

(7.8)  

wobei die Glattheitsbedingungen (7.3)

 

bzw.

 

und die Interpolationsbedingungen (7.4)

 

zu erfüllen sind. Die Glattheits- und Interpolationsbedingungen legen also die Koeffizienten in dem allgemeinen Ansatz (7.8) in eindeutiger Weise durch

(7.9)  

fest und liefern den interpolierenden linearen Spline. Wir haben also gezeigt:

Satz 7.3

Bearbeiten
Zu Knoten   und Stützwerten     gibt es genau einen interpolierenden linearen Spline  . Er besitzt auf dem Intervall   die Darstellung (7.8) mit Koeffizienten (7.9).

Sind die Stützwerte   Funktionswerte einer gegebenen Funktion  , fordert man also

 

so kann man für den Fehler bei der Spline-Interpolation Folgendes schließen, wobei

(7.10)  

die Maximumnorm auf   bezeichne.

Satz 7.4

Bearbeiten
Zu einer Funktion  , Knoten   und Stützwerten     sei   der interpolierende lineare Spline. Mit
 
gilt dann
 

Für jedes   stimmt der Spline   auf dem Intervall   mit dem Polynom   überein, welches den Interpolationsbedingungen

 

genügt. Satz 6.11 über den Fehler bei der Polynominterpolation liefert daher für alle   die Abschätzung

 

wobei eingeht, dass die Funktion   ihr Maximum auf   bei

 

annimmt. Damit ist die behauptete Fehlerabschätzung bewiesen.

q.e.d.

Nach Satz 7.4 hat man für   die wichtige Aussage

 

für den Fehler bei der Interpolation mit linearen Splines. Ist weiter für  

 

mit einem   eine Zerlegung von  , ist

 

und   der zugehörige interpolierende lineare Spline mit Stützwerten

 

so kann man aufgrund von Satz 7.4 für  , anders als im Fall der gewöhnlichen Polynominterpolation (vgl. Satz 6.16), immer die gleichmäßige Konvergenz der   gegen   schließen, d. h.

 

7.3 Interpolierende kubische Splines

Bearbeiten

7.3.1 Minimaleigenschaften

Bearbeiten

Wir wollen als nächstes interpolierende kubische Splines und deren Berechnung ausführlicher betrachten. Wir beginnen damit, eine für die Anwendungen wichtige Minimaleigenschaft solcher Splines vorzustellen. Hierzu bezeichne im Folgenden

 

die  -Norm auf dem  .

Lemma 7.5

Bearbeiten
Zu einer Funktion  , Knoten   und Stützwerten     sei   ein zugehöriger interpolierender kubischer Spline. Man hat dann
(7.11)  

Nach Definition der Norm   gilt

 
(7.12)  

so dass wir uns nur noch mit dem mittleren Ausdruck in (7.12) befassen müssen. Für   liefert für diesen zweimalige partielle Integration

 
 

wobei der vorletzte Term aufgrund der Interpolationsforderungen   identisch Null ist und das letzte Integral verschwindet, da   auf den Teilintervallen   gilt. Summation über   liefert aufgrund der Stetigkeit der Funktionen   auf dem Intervall   die folgende Teleskopsumme und damit die Aussage des Lemmas:

 

q.e.d.

Unter gewissen zusätzlichen Bedingungen vereinfacht sich die Aussage von Lemma 7.5:

Satz 7.6

Bearbeiten
Gegeben seien eine Funktion  , Knoten   und die Stützwerte    . Für einen zugehörigen interpolierenden kubischen Spline   gilt dann
(7.13)  
sofern eine der drei folgenden Randbedingungen erfüllt ist:
(a)  
(b)  
(c)  , falls  .

In jedem der Fälle (a), (b) und (c) verschwindet in (7.11) der letzte Ausdruck, so dass dann die Identität (7.11) in die Identität (7.13) übergeht.

Aus Satz 7.6 schließt man:

Korollar 7.7

Bearbeiten
Sei   wie in Satz 7.6 definiert. Dann gilt
(7.14)  
für alle Funktionen  , welche den selben Bedingungen genügen, wie sie für   in Satz 7.6 gefordert sind.

Die Beziehung (7.14) ergibt sich für Splines mit der Eigenschaft (a), (b) oder (c) wegen   unmittelbar aus Satz 7.6.

q.e.d.

Die Krümmung einer Kurve   in der Ebene an der Stelle   ist durch

 

definiert. Für kleine Auslenkungen  , wie sie z.B. bei einer dünnen Holzlatte auftreten, gilt näherungsweise   und damit für die gesamte Krümmung der Kurve näherungsweise

 

Kubische Splines besitzen also nach dem letzten Satz unter allen Kurven in  , welche gewissen Interpolations- und Randbedingungen genügen, in dem genannten genäherten Sinne minimale Krümmung. Diese Minimaleigenschaft stellt den Grund dafür dar, dass in der Praxis, wie beispielsweise bei der Konstruktion von Schiffsrümpfen oder der Festlegung von Schienenwegen, häufig kubische Splinefunktionen für die Interpolation verwendet werden. (Ein „spline“ ist ein englischer Name für eine dünne Holzlatte, die beim Zeichnen benutzt wurde.)

7.3.2 Vorüberlegungen

Bearbeiten

Wir wollen nun auf die Berechnung interpolierender kubischer Splines   mit Knoten   und zugehörigen Stützpunkten     eingehen. Da ein solcher Spline auf jedem Intervall   mit einem Polynom 3. Grades   identisch ist, gilt dort

(7.15)  
 
 

Insgesamt ist ein (interpolierender) kubischer Spline also durch die   Koeffizienten   und   für   bestimmt. Für deren Berechnung hat man zunächst die   Glattheitsbedingungen (7.3) und die   Interpolationsbedingungen (7.4), also, wie schon allgemeiner in (7.5) festgestellt wurde, insgesamt   Gleichungen zur Verfügung. (Es deutet sich also schon an, dass man zur eindeutigen Bestimmung eines interpolierenden kubischen Splines 2 weitere Festlegungen benötigt.) Stellt man diese   Gleichungen auf, so kann man diese anschließend durch geschicktes Ineinandereinsetzen auf die in dem folgenden Lemma genannten   linearen Gleichungen (7.17) reduzieren. Statt so vorzugehen, gehen wir hier von dem Ergebnis aus und zeigen wir umgekehrt, dass die Lösung der genannten   linearen Gleichungen auf einen interpolierenden kubischen Spline führt. Dazu definieren wir

(7.16)  

Lemma 7.8

Bearbeiten
Falls   reelle Zahlen     den   gekoppelten Gleichungen
(7.17)  
mit rechten Seiten
(7.18)  
genügen, so liefert der lokale Ansatz (7.15) mit den Setzungen
(7.19)  
(7.20)  
für   einen interpolierenden kubischen Spline   mit Knoten   und Stützwerten    .

Für     wie in (7.15) erhält man mit   aus (7.19)

(7.21)  

Weiter hat man mit (7.19) und (7.20)

 
(7.22)  

Die Beziehungen (7.21) und (7.22) zusammen liefern die Interpolationsbedingungen (7.4) sowie die Stetigkeitsbedingungen

 

Weiter folgt für   aus (7.17)

 

und damit wiederum unter Verwendung von (7.19) und (7.20)

 
 
 

Schließlich gilt mit (7.20)

(7.23)  

und folglich

(7.24)  

Damit sind auch die Glattheitsbedingungen (7.3) nachgewiesen und ist folglich   mit der lokalen Darstellung (7.15) und Koeffizienten wie in (7.19) und (7.20) Element von  .

q.e.d.

In der in Lemma 7.8 beschriebenen Situation bezeichnet man die   reellen Zahlen     als Momente. Da insbesondere

 

gilt und gemäß (7.24)

 

ist, hat man

(7.25)  

Das heißt, dass die Momente   mit den zweiten Ableitungen des Splines   in den Knoten   übereinstimmen.

7.3.3 Natürliche, vollständige und periodische Splines

Bearbeiten

Lemma 7.8 zeigt, dass die Koeffizienten in der lokalen Darstellung (7.15) unmittelbar aus den   Momenten   berechnet werden können. Diese   Momente wiederum ergeben sich aus den   linearen Gleichungen (7.17), so dass also noch zwei Freiheitsgrade vorliegen. Aufgrund der Bedingungen (a), (b) und (c) in Satz 7.6 bieten sich für deren Festlegung die folgenden drei Möglichkeiten an:

Natürliche Randbedingungen:  
Vollständige Randbedingungen:   für gegebene  ,
Periodische Randbedingungen:  

Im Folgenden wollen wir für diese drei Fälle die Gleichungen (7.17) zusammen mit den beiden zusätzlichen Randbedingungen in Matrix-Vektor-Form angeben.

Im Fall der natürlichen Randbedingungen lassen sich die Gleichungen (7.17) in folgender Form schreiben, wobei wegen   (vgl. (7.25)) in diesem Fall   aus der ersten und   aus der letzten dieser Gleichungen gestrichen werden kann:

(7.26)  

Im Fall der vollständigen Randbedingungen verwenden wir die Beziehungen

(7.27)  

und

 
(7.28)  

welche die beiden folgenden zusätzlichen Gleichungen ergeben:

(7.29)  
(7.30)  

Mit den Randbedingungen   und   bezeichnen wir die rechten Seiten dieser Gleichungen mit

 

Fügt man damit die Gleichungen (7.29) und (7.30) an erster bzw. letzter Stelle den Gleichungen (7.17) hinzu, so gelangt man zu dem Gleichungssystem

 

Schließlich gewinnt man für die periodischen Randbedingungen wegen   und   durch Gleichsetzung von (7.27) und (7.28) die zusätzliche Gleichung

 

Zusammen mit dieser Gleichung an erster Position und Ersetzung von   durch   in der letzten der Gleichungen (7.17) gelangt man in diesem Fall zu dem linearen Gleichungssystem

 

Wir stellen nun weiter fest, dass die Matrizen in den obigen Gleichungssystemen, welche zur Bestimmung eines natürlichen, vollständigen und periodischen kubischen Splines gelöst werden müssen, jeweils symmetrisch und strikt diagonaldominant sind und positive Diagonalelemente besitzen. (Für die Definition einer strikt diagonaldominanten Matrix siehe Definition 3.2.) Für solche Matrizen kann man zeigen:

Lemma 7.9

Bearbeiten
Es sei   eine symmetrische und strikt diagonaldominante Matrix mit    . Dann ist A positiv definit.

Es sei   Eigenwert und   Eigenvektor der symmetrischen Matrix  , d. h.

 

wobei wir   so normieren, dass   gilt. Sei nun   derart, dass   ist. Dann hat man

 

und damit

 

Demzufolge gilt

 

bzw. wegen der strikten Diagonaldominanz von   und  

 

q.e.d.

Nach Lemma 3.20 ist eine positiv definite Matrix insbesondere regulär, so dass jedes der obigen drei hergeleiteten linearen Gleichungssysteme eine eindeutige Lösung besitzt. Somit können wir zusammen mit Lemma 7.8 schließen:

Korollar 7.10

Bearbeiten
Zu Knoten   und Stützwerten     gibt es jeweils genau einen interpolierenden kubischen Spline   mit natürlichen, (für vorgegebene Zahlen  ) vollständigen bzw. periodischen Randbedingungen.

Die Matrizen in den bei der Bestimmung des natürlichen und vollständigen Splines auftretenden Gleichungssystemen sind offenbar strikt diagonal dominante Tridiagonal-Matrizen, für die man eine LR-Zerlegung mit nur   bzw.   arithmetischen Rechenoperationen berechnen kann. Außerdem sind die Konditionen dieser Matrizen unproblematisch, so dass man die entsprechenden Systeme numerisch stabil lösen kann. Ferner gibt es auch für eine zyklische, positiv definite Tridiagonal-Matrix, wie sie bei einem periodischen Spline vorliegt, eine effiziente Cholesky-Zerlegung (siehe Schwarz und Werner für Details).

Schließlich sind generell für interpolierende kubische Splines bei Verwendung der Maximumnorm (7.10) die folgenden Fehlerabschätzungen gültig:

Satz 7.11

Bearbeiten
Zu einer Funktion  , Knoten   und Stützwerten     sei   ein interpolierender kubischer Spline. Weiter sei
 

Falls mit einer Konstanten  

(7.31)  

gilt, so folgen mit der Konstanten

(7.32)  
die nachstehenden Abschätzungen:
 
 
 
 

Der Satz ist z.B. bei Plato bewiesen. Eine Bedingung der Form (7.31) lässt sich gerade für den natürlichen, vollständigen und periodischen kubischen Spline verifizieren (siehe ebenfalls Plato), wobei beispielsweise für den natürlichen Spline   gezeigt werden kann. Nach Satz 7.11 hat man für   somit für die drei untersuchten Splinetypen die Aussage

 

Ferner hat man damit, ähnlich wie für lineare Splines, mit den in Abschnitt 7.2 eingeführten Definitionen

 

wenn   hier den entsprechenden natürlichen, vollständigen oder periodischen kubischen Spline bezeichnet.

Beispiel 7.12

Bearbeiten

Gegeben seien die in der Tabelle

 

von der Funktion   herrührenden Stützwerte   und gesucht sei dazu der natürliche Spline. Offenbar hat man   und    . Aus (7.18) errechnet man

 
 
 

Damit lautet das Gleichungssystem (7.26)

 

Seine Lösung ist  , so dass wir aus (7.19) und (7.20) und mit den Randvorgaben   des natürlichen Splines folgende Größen erhalten:

 
 

und

 

Mit   und   für   gelangen wir somit zu der folgenden Darstellung des gesuchten Splines  :

 

Maximale Approximationsfehler werden in den Intervallen   und   und zwar genau bei   angenommen und der Betrag beider Fehler ist  . Es gilt hier

 

Weiter erhält man mit   für   in (7.32) den Wert   und damit

 

Für praktische Zwecke sind also die Abschätzungen in Satz 7.11 häufig nicht brauchbar. Für die vorliegende Funktion   hatte Runge gezeigt, dass die Maximumnormen der Interpolationsfehler im Fall der üblichen Polynominterpolation auf dem Intervall   für die äquidistanten Stützstellen     für   gegen   streben (s. Schwarz, S. 102).