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.
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.
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.
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:
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
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.
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
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:
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.)
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
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
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:
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:
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:
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.
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).