2

Inhaltsverzeichnis

1  Einleitung  3

2  Allgemeine Betrachtungen  4

3  Periodische Spline-Interpolation in der Taylor-Form  9

3.1  Segmente in der Taylor-Form  9

3.2  Periodische Spline-Interpolation in der Taylor-Form für äquidistante x-Werte  10

3.3  Periodische Spline-Interpolation in der Taylor-Form  

f  ür äquidistante x-Werte in gekürzter Form  17

3.4  Periodische Spline-Interpolation in der Taylor-Form  

f  ür nicht äquidistante x-Werte  20

3.5  Periodische Spline-Interpolation in der Taylor-Form  

f  ür nicht äquidistante x-Werte in gekürzter Form  28

3.6  Schrittweise Berechnung der Koeffizienten in der Taylor-Form  

bei  bekannten Anfangswerten  34

4  Periodische Spline-Interpolation in der Bernstein-Bézier-Form  37

4.1  Segmente in der Bernstein-Bézier-Form  37

4.2  Periodische Spline-Interpolation in der Bernstein-Bézier-Form  

f  ür äquidistante Parameterwerte  40

4.3  Periodische Spline-Interpolation in der Bernstein-Bézier-Form  

f  ür äquidistante Parameterwerte in gekürzter Form  49

4.4  Periodische Spline-Interpolation in der Bernstein-Bézier-Form  

f  ür nicht äquidistante Parameterwerte  52

4.5  Periodische Spline-Interpolation in der Bernstein-Bézier-Form  

f  ür nicht äquidistante Parameterwerte in gekürzter Form  62

4.6  Parametrisierung  66

4.7  Schrittweise Berechnung der Bézier-Punkte bei bekannten Anfangswerten  74

5  Periodische Spline-Interpolation unter Verwendung  

von  B-Spline-Basisfunktionen  78

5.1  B-Spline-Basisfunktionen  78

5.2  Periodische Spline-Interpolation unter Verwendung von  

B  -Spline-Basisfunktionen für äquidistante Parameterwerte  81

5.3  Periodische Spline-Interpolation unter Verwendung von  

B  -Spline-Basisfunktionen für äquidistante Parameterwerte in gekürzter Form  88

5.4  Periodische Spline-Interpolation unter Verwendung von  

B  -Spline-Basisfunktionen für nicht äquidistante Parameterwerte  90

5.5  Periodische Spline-Interpolation unter Verwendung von B-Spline-Basisfunktionen  

f  ür nicht äquidistante Parameterwerte in gekürzter Form  103

5.6  Eigenschaften der B-Spline-Kurven  108

5.7  Schrittweise Berechnung der Kontrollpunkte bei bekannten Anfangswerten  118

6  Referenzen  122

3

1 Einleitung

In dieser Abhandlung wird anhand von einfachen Beispielen die Vorgehensweise bei der

periodischen Spline-Interpolation erläutert. Periodisch heißt hier nicht, dass man nur

periodische Funktionen oder geschlossene Kurven erzeugen kann, was eine starke Ein-

schränkung bedeuten würde. Mithilfe der periodischen Spline-Interpolation erhält man auch

translationsinvariante Funktionen und Kurven. In der Abbildung 1 ist eine translations-

invariante Kurve dargestellt, die man durch Interpolation in den Punkten

) 0 | 0 ( X , 1

Es müsste eigentlich statt „periodische Spline-Interpolation“ genauer „Interpolation mit

periodischen Randbedingungen“ heißen. Zwingend periodisch sind nur die Ableitungen ersten

und zweiten Grades, wenn man für die Segmente ganzrationale Funktionen dritten Grades

oder sogenannte kubische Bézier-Kurven verwendet. In unserer Abbildung stimmen die erste

und zweite Ableitung in den Punkten X und X überein. Die Segmente für Spline- 0 5

Funktionen werden in dieser Abhandlung in der Taylor-Form dargestellt. Die Segmente für

Spline-Kurven werden sowohl in der Bernstein-Bézier-Form (Bézier-Spline-Kurven) als

auch unter Verwendung von B-Spline-Basisfunktionen (B-Spline-Kurven) angegeben. Die

Koeffizienten für die Taylor-Form, die Bézier-Punkte für die Bernstein-Bézier-Form und

die Kontrollpunkte (de Boor-Punkte) für die Darstellung unter Verwendung von B-Spline-

Basisfunktionen werden hier nach einer neuartigen iterativen Methode berechnet. Ein-schränkungen, was die Anzahl der Interpolationspunkte (Datenpunkte) angeht, müssen nicht

gemacht werden. Die Rechenzeit für die Koeffizienten (Taylor-Form), Bézier-Punkte oder

Kontrollpunkte (de Boor-Punkte) für einen XP-Rechner (AMD Athlon Dual Core Processor

3800+) mit einem als JAVA-Applet geschriebenen Programm liegt für 10000 Interpolations-

punkte (Datenpunkte) bei rund 19 s. Als kleine Hilfe für Programmierer werden wesentliche

Programmteile in Form eines Struktogramms angegeben.

4

2 Allgemeine Betrachtungen

Wir beginnen mit der Definition der Spline-Funktion für die periodische Spline-

Interpolation (Abb. 2 und Abb. 3 für polationspunkten (Datenpunkten)

durch die folgenden vier Eigenschaften definiert:

a) Die Spline-Funktion ) (x s ist im gesamten Intervall ] , [ 0 n x x zweimal stetig differenzier-bar.

  b) ) (x s ist in jedem Intervall ] , [ l x x für 1 ..., , 1 , 0 n l durch eine ganzrationale  1 l Funktion dritten Grades

    ^{2 3} d x c x b x a x s ) ( l l l l l

gegeben. (Das Schaubild dieser ganzrationalen Funktion heißt Segment.)

  ) (x s n l ..., , 1 , 0 erfüllt die Interpolationsbedingung y x s ) ( für . c) l l

d) Für die periodische Spline-Interpolation muss die periodische Randbedingung

        x s x s und ) ( ) ( 0 x s x s erfüllt sein. ) ( ) ( 0 n n y  Ist y , so lässt sich die Spline-Funktion zu einer überall zweimal stetig differenzier- n 0

baren Funktion periodisch fortsetzen (Abb. 2).

y  y , so lässt sich die Spline-Funktion zu einer überall zweimal stetig differenzier-Ist n 0

baren Funktion translationsinvariant fortsetzen (Abb. 3).

5

Die Definition der Spline-Kurve für die periodische Spline-Interpolation (Abb. 4 und Abb. 1

Seite 3 für

Spline-Kurve

     vektoren l x ( n l ..., , 1 , 0 , ) und den Parameterwerten (Knoten) u u u ... ist n 2 n 1 0

durch die folgenden vier Eigenschaften definiert:

a) Die Spline-Kurve

b) ) (u s ist in jedem Intervall

gegeben. (Das zugehörige Schaubild heißt Segment.)

  u x s ) ( für n l ..., , 1 , 0 . c) ) (u s erfüllt die Interpolationsbedingung l l

d) Für die periodische Spline-Interpolation muss die periodische Randbedingung

        u u s s und ) ( ) ( 0 u u s s erfüllt sein. ) ( ) ( 0 n n x  x , so ist die Spline-Kurve überall zweimal stetig differenzierbar und geschlossen Ist n ⁰ (Abb. 4).

x  x Ist n

⁰ Kurve translationsinvariant fortsetzen (in Abb. 1 Seite 3 ist

Die Darstellung der Segmente in b) ist weitgehend willkürlich gewählt. In der Praxis erweist

sich für Spline-Funktionen die Taylor-Form (Seite 10) und für Spline-Kurven die Dar-

stellung in der Bernstein-Bézier-Form (Seite 38 (15)) (Bézier-Spline-Kurve) oder die Dar-

stellung unter Verwendung von B-Spline-Basisfunktionen (Seite 82) (B-Spline-Kurve) als

wesentlich günstiger. Diese Darstellungsformen sind der Inhalt der Kapitel 3, Kapitel 4 und

Kapitel 5 und werden dort an einfachen Beispielen erläutert.

Jedes der drei Kapitel (Kapitel 3 bis Kapitel 5) folgt ungefähr dem gleichen Ablauf. Das hat

den Vorteil, dass die Kapitel unabhängig voneinander gelesen werden können.

In den Abschnitten 3.1 bzw. 4.1 werden die Segmente ) (x s l bzw. ) (u s und im Abschnitt 5.1 l

die B-Spline-Basisfunktionen genauer untersucht. In den Abschnitten 3.2, 4.2 und 5.2 be-

fassen wir uns mit der periodischen Spline-Interpolation für äquidistante (l. aequus gleich; l.

;  distantia Entfernung, Abstand) x-Werte n l x l ..., , 1 , 0 bzw. äquidistante (uniforme (l.

6

uniformis einförmig)) Parameterwerte n l u l ..., , 1 , 0 . Da für eine große Anzahl von Inter-polationspunkten (Datenpunkten) (ab etwa 400 Punkten) die Vorgehensweise in den Ab-

schnitten 3.2, 4.2 und 5.2 keine Ergebnisse mehr liefert (für die Beispiele in unserer Ab-

handlung gibt es diese Probleme wegen der geringen Punktzahl allerdings nicht), wird in den

Abschnitten 3.3, 4.3 und 5.3 die gekürzte Form verwendet, in welcher der Nachteil der Be-

schränkung der Anzahl von Interpolationspunkten (Datenpunkten) nicht mehr auftritt. In den

Abschnitten 3.4, 4.4 und 5.4 wird die periodische Spline-Interpolation für nicht äquidistante

;  x-Werte n l x l ..., , 1 , 0 bzw. für nicht äquidistante (nicht uniforme) Parameterwerte

;  ..., , 1 , 0 behandelt. Für den Fall, dass eine große Anzahl von Interpolationspunkten n l u l

(Datenpunkten) vorliegt, muss auch hier das gekürzte Verfahren (in den Abschnitten 3.5, 4.5

und 5.5) angewendet werden. Da unsere Methode zwar zur Bestimmung eines jeden

Segments angewendet werden kann, dann aber für eine große Anzahl von Interpolations-punkten (Datenpunkten) relativ langsam ist, behandeln wir im letzten Abschnitt jedes der ge-

nannten Kapitel 3, 4 und 5 eine Methode, wie man eine begrenzte Zahl (bis etwa 20) von

Zwischensegmenten schneller bestimmen kann. Eine Betrachtung, in der die Zeitersparnis

durch dieses Vorgehen dargestellt ist, wird angefügt. In jedem der Kapitel (Kapitel 3, 4 und 5)

werden einfache Beispiele (Taschenrechner oder Computer-Algebra-System sind

empfehlenswert) durchgerechnet. Es sind aber auch rechenaufwändigere Beispiele angefügt,

für die ein Computerprogramm unerlässlich ist. Damit interessierte Leser die Beispiele nach-rechnen können, werden die Eingabewerte als Tabellen angefügt. Wir verwenden bei der Dar-stellung der Zahlen durchweg die angloamerikanische Schreibweise.

Einige Sachverhalte, die für alle Kapitel wichtig sind, wollen wir nun im Folgenden be-schreiben.

Die Striche ’ und ’’, die ab hier in diesem Kapitel auftreten, dienen nur zur Unterscheidung

und haben mit Ableitungen nichts zu tun. Für die Anzahl der Interpolationspunkte (Daten-

punkte) wird immer n und für die Nummerierung der Segmente immer l, beginnend bei 0,

verwendet.

a , Für die periodische Spline-Interpolation spielen die Koeffizienten l vor dem linearen und

1

a , vor dem quadratischen Glied der Taylor-Form (siehe Seite 13 (6)) eines jeden Segments l 2

a , a , s eine wesentliche Rolle. Hat man und bestimmt, so kann man die fehlenden l 1 l ² l

a , a , a , a , Koeffizienten und leicht berechnen. Für und (also die Koeffizienten vor l 0 l 3 l 1 l 2

dem linearen und dem quadratischen Glied) gilt

und

  mit y  r l

Interpolationspunkte (Datenpunkte). Es ist

Die Berechnung von n

erfolgen. Die Definition von

Interpolation in der Taylor-Form für nicht äquidistante x-Werte“ auf Seite 20.

7

Bei der periodischen Spline-Interpolation in der Bernstein-Bézier-Form spielen die inneren

b b Bézier-Punkte B und B mit den Ortsvektoren und für jedes Segment 3  3 ^ 3  3  1 l 2 l 1 l 2 l   s 1 ..., , 1 , 0 ; n l eine wesentliche Rolle. Es gilt für die Ortsvektoren dieser Bézier-Punkte l ([24] THEOREM 7 Seite 14)

und

  x mit  r l

Interpolationspunkte (Datenpunkte). Es ist

Auch hier kommt wieder n

„Periodische Spline-Interpolation in der Bernstein-Bézier-Form für nicht äquidistante (nicht

uniforme) Parameterwerte“ auf Seite 52 und Seite 53.

Bei der periodischen Spline-Interpolation unter Verwendung von B-Spline-Basisfunktionen

spielen die Kontrollpunkte (de Boor-Punkte) l D (einer für jedes Segment) mit den Orts-

d ( l d beeinflusst vier aufeinanderfolgende Segmente) eine wesentliche Rolle. Es vektoren l

gilt ([24] THEOREM 9 Seite 18)

  x mit  r l

v zu tun. Die Definition von d , erfolgt im Abschnitt 5.4: „Periodische Splinewieder mit n n l r ,

Interpolation unter Verwendung von B-Spline-Basisfunktionen für nicht äquidistante (nicht

uniforme) Parameterwerte“ auf Seite 91.

Wir können kurz folgendermaßen zusammenfassen:

a , a , a) Für Spline-Funktionen sind die Koeffizienten vor dem linearen und vor dem l 1 l 2

quadratischen Glied in der Taylor-Form eines jeden Segments l s immer eine Linear-

kombination der b) Für Spline-Kurven sind die Differenzen

Form bzw. die Differenz

jeden Segments l

Dabei lassen sich die Koeffizienten dieser Linearkombinationen immer als Brüche mit dem

v darstellen. Nenner n

Um später die etwas mehr theoretischen Teile besser zu verstehen und um die Berechnung

v , das ja in jedem der drei Kapitel (Kapitel 3, Kapitel 4 und Kapitel 5) vorkommt, von n

durchführen zu können, müssen die folgenden Definitionen bekannt sein. Eine wesentliche

Rolle spielen die zweireihigen Matrizen der Form

8

([23] Seite 10 (1.3); [24] Seite 3 und [34] Seite 43 ) denn es kommen häufig Produkte solcher

   Matrizen vor. Wir definieren das Matrixprodukt ) ( ... ) ( ) ( a G a G a G ([24]  1 i j j

DEFINITION 2 Seite 4)

Da auch Matrixprodukte vorkommen, in denen der untere Index den oberen Index um 1 oder

2 übersteigt, definieren wir zusätzlich, wenn i um 1 größer als j ist

(1)

und wenn i um 2 größer als j,

(2)

v , das in den Formeln der einzelnen Kapitel nur im Nenner vorkommt ist definiert als ([24] n THEOREM 2 Seite 9)

(3)

Um uns etwas mehr mit der Materie vertraut zu machen, wollen wir 3

2   und bestimmen. Das Ergebnis 3 v kommt als Zwischenergebnis in späteren 3

Rechnungen zu einem Beispiel (Seiten 59 und 98) vor.

Nach Definition müssen wir

bestimmen. Das führt auf die Rechnung

,   i Wir erhalten mit den obigen

oder mit dem Produkt der beiden rechten Matrizen als Teilprodukt

Es ist dann nach der Definition (3) von n v

      66 17) ( 47) ( 2 v .

3

9

3 Periodische Spline-Interpolation in der Taylor-

Form

3.1 Segmente in der Taylor-Form

In Abb. 5 sehen wir vier Schaubilder von Funktionen, die auf dem Intervall [-5, 5] definiert

0  P und und gehören zu ganzrationalen sind. Alle haben sie die Endpunkte ) 1 | 5 ( ) 3 | 5 ( P 1

Funktionen vom Grad 3. Wir verwenden zunächst die Eigenschaft, dass alle vier Schaubilder

dieselben Endpunkte haben. Der Ansatz in der Taylor-Form (B. TAYLOR, 1685 - 1731,

englischer Mathematiker) liefert

mit dem Zusatz, dass dann

also

0  1 a

und

     3 1000 100 10 1 ) 5 ( a a a f , 3 2 1

also o. B. d. A. nach 3 a aufgelöst

Damit also alle vier Schaubilder durch die Punkte

zugehörigen Funktionen die Form

  100 10 2 a a          ^{3 2 2 1} . ] 5 , 5 [ ; ) 5 ( ) 5 ( ) 5 ( 1 ) ( x x x a x a x f a ^{2 1 ,} 2 a 1000 1

Es handelt sich um eine Funktionenschar mit den Parametern 1 a und 2 a . In unserem Beispiel

(Abb. 5) gilt für die Schaubilder von oben nach unten

10

und

         ^{3 2} . ] 5 , 5 [ ; ) 5 ( 023 . 0 ) 5 ( 2 . 0 ) 5 ( 1 . 0 1 ) ( x x x x x f   2 . 0 , 1 . 0

Der Leser kann dies selbst, z. B. mithilfe eines Computer-Algebra-Systems, nachprüfen.

Wir behandeln nun das Problem etwas allgemeiner. Dazu suchen wir die Schar der ganz-

) | ( rationalen Funktionen dritten Grades, deren Schaubilder durch ) | ( y x P und mit y x P ^{1 1 1 0 0 0}     x 0 x gehen. Wie oben am speziellen Beispiel erläutert, muss dann mit dem Ansatz 0 1

(Taylor-Form)

 0 ) ( y x f 0

also

a  y ^{0 0} und

           3 2 1 ) ( y a a a y x f , ^{1 3 2 1 0}    also damit und mit y y y o. B. d. A. 0 1 0

Damit also alle Schaubilder einer Schar ganzrationaler Funktionen dritten Grades durch die

P Punkte (

⁰ haben. Es wird hier nicht ohne Grund das Wort „können“ verwendet, da man als Parameter ja

a und 3 a oder auch 2 a und 3 a hätte verwenden können. auch 1

3.2 Periodische Spline-Interpolation in der Taylor-Form für

äquidistante x-Werte

Im Folgenden sollen nun Funktionen betrachtet werden, für deren Schaubilder gilt: Es werden

Teilstücke der Schaubilder von Funktionen wie oben, nämlich ganzrational vom 3. Grad, „an-

einandergesetzt“.

Vergleichen wir dazu zunächst die Schaubilder der Abb. 6 und Abb. 7 Seite 11.

Was fällt auf?

] 6 , 10 [ a) Beide zu den Schaubildern gehörenden Funktionen sind auf dem Intervall

definiert.

11

b) Beide Schaubilder haben einen „glatten“ Verlauf.

0  1  2  ) 2 | 10 ( P , , , c) Beide Schaubilder verlaufen durch die Punkte ) 0 | 6 ( ) 3 | 2 ( P P

 ) 3 | 2 ( P und . ) 2 | 6 ( P 3 4

d) Der Abstand der x-Koordinaten aufeinanderfolgender Punkte P beträgt bei beiden

  Schaubildern immer

e) Die erste Kurve kann, wie man in Abb. 8 sieht, in den Punkten

periodisch und „glatt“ fortgesetzt werden (siehe auch Abb. 2 Seite 4).

0  ) 2 | 10 ( P und zwar periodisch fort-Die zweite Kurve kann in den Punkten ) 2 | 6 ( P 4

gesetzt werden, ist dort auch stetig aber nicht differenzierbar (Abb. 9).

Wir wollen nun an unserem Beispiel (Abb. 6 Seite 10) genauer erklären, was man unter

) (x s periodischer Spline-Interpolation versteht: Dabei ist eine Funktion zu bestimmen, deren

Schaubild durch die oben vorgegebenen Punkte, die Interpolationspunkte (Datenpunkte),

verlaufen soll. Zwischen diesen Interpolationspunkten (Datenpunkten) soll das Schaubild

möglichst glatt verlaufen. Dazu eignen sich z. B. ganzrationale Funktionen (hier 3. Grades).

Die Teilstücke des Funktionsschaubildes zwischen aufeinander folgenden Interpolations-

 3 , 2 , 1 , 0 , ) ( l x s l werden Segmente punkten (Datenpunkten) (einschließlich dieser Punkte)

12

genannt. Diese Segmente sollen so aneinandergefügt sein, dass die linksseitige Ableitung (bis

zum zweiten Grad) am rechten Ende eines Segments mit der rechtsseitigen Ableitung (bis

zum zweiten Grad) am linken Ende des darauffolgenden Segments übereinstimmt. Es soll also

(4)

gelten.

Da es sich um die periodische Spline-Interpolation handelt, soll die rechtsseitige Ableitung

P mit der linksseitigen Ableitung (bis zum zweiten (bis zum zweiten Grad) im ersten Punkt 0

P übereinstimmen. Das bedeutet Grad) im letzen Punkt 4

(5)

Die Funktion ist also zweimal stetig differenzierbar periodisch fortsetzbar, wenn außerdem

die y-Werte des ersten und letzten Punktes übereinstimmen, wie es in unserem Beispiel der

Fall ist. Denken wir uns alle möglichen zweimal stetig differenzierbaren Fortsetzungen auf

        ... , 2 , 1 , 0 , 1 , 2 ..., , ] 16 6 , 16 10 [ k k k eingezeichnet, so erhalten wir den Intervallen

Abb. 8 Seite 11.

Die entstandene Funktion hat die Eigenschaft, dass für alle

  ) 16 ( x f

Unter einer periodischen Funktion mit der Periode h > 0 versteht man eine Funktion f(x), für

die für alle x aus der Definitionsmenge f(x + h) = f(x) gilt.

 in Abb. 6 Seite 10 durch ) 2 | 6 ( P , so hat das so Ersetzen wir den letzten Punkt ) 2 | 6 ( P ⁴ 4

erhaltene Schaubild das folgende Aussehen (Abb. 10).

Zeichnet man die, dann auch hier möglichen, zweimal stetig differenzierbaren Fortsetzungen

ein, so bekommt man das Schaubild der Abb. 11 Seite 13.

Das Schaubild ist translationsinvariant bezüglich des eingezeichneten Vektors

bedeutet: Es wird bei einer Verschiebung bezüglich des eingezeichneten Vektors auf sich ab-

gebildet. Wir wollen auch die dazu gehörende Funktion translationsinvariant nennen. Das

führt auf die folgende Definition:

Unter einer translationsinvarianten Funktion versteht man eine Funktion

alle x aus der Definitionsmenge gilt:

Für die Funktion von Abb. 11 Seite 13 (siehe auch Abb. 3 Seite 4) gilt

für eine translationsinvariante Funktion p = 0, so ist sie eine periodische Funktion.

Periodische Funktionen sind also ein Spezialfall der translationsinvarianten Funktionen.

Gehen wir wieder zur Abb. 6 Seite 10 zurück. In der Taylor-Form lassen sich alle vier

 s l in der Form Segmente

(6)

darstellen. Wie schon oben auf Seite 10 erwähnt, gilt (

und

(7)

wenn man noch

3 , 2 , 1 , 0 l ) hat also die Form Das l + 1-te Segment (

) ( x s l

Es bleibt also noch die Aufgabe, die l

Bedingungen Seite 12 (4) und Seite 12 (5) erfüllt sind.

Dazu dienen die folgenden Zahlenreihen, die man den Abb. 12 und Abb. 13 Seite 14 ent-

nehmen kann.

Wie man die obigen Tabellen bestimmt, wird später erklärt werden. Die Zahlenreihen in den

 Tabellen können als Vektoren zusammengefasst werden. Für unser Beispiel (

Wir erinnern uns vielleicht noch an die

Betrachtungen“. Hier kommen drei Indizes vor. Dass in

(

Zahlenreihen für jedes Segment die gleichen sind, wie wir weiter unten sehen werden, der

Index l also weggelassen werden kann. Außerdem kommen zwei Querstriche vor. Das liegt

daran, dass sich

werden, durch einen Faktor unterscheiden. Wir berücksichtigen zusätzlich, dass

y  y  . In Computerprogrammen kann es günstiger sein, y y y mod zu verwenden. und 2 6 3 7 n l

Man spart dann, wenn

zwar unerheblich, für

0    1  ) 2 | 10 ( P 1 ..., , 1 , 0 n l für unser Beispiel (wir erinnern uns, dass die Punkte , , ) 0 | 6 ( P

 2  , ) 3 | 2 ( P und vorgegeben waren) sind also (-2, 3, -6, 5), (3, -6, 5, -2), ) 3 | 2 ( ) 2 | 6 ( P P 3 4

(-6, 5, -2, 3) und (5, -2, 3, -6). Wie man sieht, sind die Werte in den Klammern zyklisch ver-

tauscht. 0 a , den Koeffizienten des linearen Glieds aus der Taylor-Darstellung, erhalten wir , 1

aus

Für unser Beispiel also

a 0 , 1

a , den Koeffizienten des quadratischen Glieds aus der Taylor-Darstellung, erhalten Für 0 , 2

wir

und für unser Beispiel also

a 0 , 2

15

Wegen des Ergebnisses von Seite 13 (7) ergibt sich

Das erste Segment lautet also in der Taylor-Form

Für die anderen Segmente muss man entsprechend (

a

a 2

und

a 2

berechnen.

Man stellt dann fest, dass die Darstellung der restlichen Segmente

und

ist.

Nun zur Berechnung obiger Vektoren

(

ordinaten bei äquidistanten x-Werten sind

(8)

und

16

(9)

^       1 n n n . mit ) ) 3 2 ( ) 3 2 (( ) 1 ( 2 v n

Man sieht, dass die rechten Seiten in beiden Formeln nicht von l abhängen und also für jedes

Segment dieselben sind. Dies gilt nur, wenn die x-Werte der Punkte äquidistant sind. Da die

Formeln außerdem ähnlichen Aufbau haben, wollen wir uns darauf beschränken nur für eine

u  von     der Formeln einen Wert zu berechnen, und zwar ) , , , ( u u u u . Aus der ^{4 , 2} 4 , 3 4 , 2 4 , 1 4 , 0

1  sein muss. Wir setzen Tabelle (Abb. 12 Seite 13) wissen wir schon, dass das Ergebnis 8

 4 n

und Verwendet man dann das pascalsche Dreieck und fasst gleichartige Terme zusammen, so er-

hält man

mit den Potenzrechenregeln

und nach dem Zusammenfassen der Ausdrücke



Mithilfe eines Taschenrechners bekommt man

und mit weiteren Teilergebnissen

Es wird im Folgenden (Abb. 14 Seite 17) ein Struktogramm für den Programmteil angegeben,

         der für die Berechnung aller Koordinaten von ) ..., , , ( u u u und ) ..., , , ( u u u   , 1 , 1 , 0 n n n n , 1 , 1 , 0 n n n n

(im Struktogramm mit u1 und u2 bezeichnet) relevant ist.

Gibt man „große“ Werte für n ein, z. B. n = 400, so stellt man fest, dass der Computer manche

         Koordinaten von ) ..., , , ( u u u ) ..., , , ( u u u nicht mehr berechnet. Als bzw.   , 1 , 1 , 0 n n n n , 1 , 1 , 0 n n n n

Begründung soll hier der Nenner der Formeln von Seite 15 (8) und Seite 16 (9) für n = 400

angegeben werden. Es ist

      6 012 000 573 505 986 450 142 098 840 668 ^{400 400 399} ) 3 2 ( ) 3 2 ( ) 1 ( 2 v 400

597 428 410 587 043 906 339 909 644 908 607 369 957 261 873 714 089 165 163 401 554

156 940 623 509 078 767 243 239 903 035 335 367 919 536 373 980 867 801 842 281 244

524 479 782 480 409 129 736 088 952 465 189 517 268 457 191 084 705 030 099 738 661

395 663 872, also eine 229stellige Zahl. Wenn man darüber hinaus noch bedenkt, dass für den

v | |  n 1 lim Betrag des Nenners von Seite 15 (8) und Seite 16 (9) ([24] Seite 19) gilt, so  n ) 3 2 (   n

ist dieser große Wert von 400 v nicht weiter verwunderlich.

3.3 Periodische Spline-Interpolation in der Taylor-Form

für äquidistante x-Werte in gekürzter Form

Ein einfacher Trick für das am Ende von Abschnitt 3.2 erwähnten Problem, dass Rechnungen

 mit Werten

und Nenner in den Koordinaten von

 ^  n ¹ 2 ( ) 1 (

und

Da auch hier die zwei Formeln ähnlichen Aufbau haben, wollen wir uns darauf beschränken,

u  von         wieder nur die Koordinate ) , , , ( u u u u (auch zum Vergleich mit dem Vor- ^{4 , 2} 4 , 3 4 , 2 4 , 1 4 , 0

hergehenden) zu berechnen.

Unter Verwendung des pascalschen Dreiecks bekommen wir

Für die beiden nächsten Umformungen habe ich zugegebenermaßen zum Taschenrechner ge-

griffen.

und

Ausmultiplizieren in Zähler und Nenner und anschließendes Zusammenfassen und Ausklam-

mern ergibt

Mithilfe eines Taschenrechners

 

Nach Multiplikation, Subtraktion und Division

 

und

Das Obigem entsprechende Struktogramm ist weniger umfangreich als das für die ungekürzte

Form und hat zusätzlich den Vorteil, dass man jetzt mit „großen“ Werten für n rechnen kann.

Abb. 15

Das Struktogramm zur graphischen Ausgabe der Segmente kann dann folgendermaßen ausse-

hen

Abb. 16

Minimal- und Maximaltemperaturen

Im Anschluss wollen wir ein Beispiel für die periodische Spline-Interpolation für äquidistante

x-Werte angeben. Es handelt sich dabei um einen Auszug aus den Wetteraufzeichnungen

meiner Frau für den Monat April im Jahre 2007. Sie werden feststellen, dass es ein ziemlich

warmer April war. Natürlich ist nicht zwingend erforderlich, dass man bei dieser Grafik für

beide Kurven die periodische Spline-Interpolation verwendet. Sie ist aber eine von mehreren

Möglichkeiten. Eine translationsinvariante, zweimal stetig differenzierbare Fortsetzung für

jede der Kurven wäre zwar möglich, würde aber keinen Sinn machen. Der Temperaturverlauf

im vorangehenden März und dem darauffolgenden Mai würde dem mit Sicherheit wider-

sprechen. Um dem Leser, der das Schaubild selbst mithilfe eines Programms erzeugen will,

das Ablesen der Werte aus dem Diagramm zu ersparen, wird die zugehörige Wertetabelle

beigefügt. Wie schon in der Einleitung erwähnt wurde, sind die Zahlenwerte in der anglo-amerikanischen Form angegeben.

20

3.4 Periodische Spline-Interpolation in der Taylor-Form

für nicht äquidistante x-Werte

Der folgende Teil handelt davon, wie man und für nicht äquidistante x-Werte be- a , a , l 1 l 2

rechnen kann. Noch ausführlicher wird das nach diesem Teil beschrieben und durchgeführt.

In dem Kapitel „Allgemeine Betrachtungen“ (Seite 6) wurde schon erwähnt, dass

und

Fasst man dann noch die

      ) ..., , , ( u u u a , bzw. a , für zusammen, so lässt sich einem Vektor  , , 1 , , 1 , , 0 n l n n l n l l 1 l ²   1 ..., , 1 , 0 n l als

        T ) ..., , , ( ) ..., , , ( u u u y y y a     ^{, , 1 , , 1 , , 0 1 1 , 1} n l n n l n l n l l l l

bzw.

schreiben. Dabei ist

^{ }    (Seite 8 (3)). ) 2 , 2 ( g ) 1 , 1 ( g 2 v   1 1 n n ^{ } n 0 0

Für die periodische Spline-Interpolation in der Taylor-Form gelten die folgenden Formeln für

 und   . u , u , n l r , n l r ,

  u ^{, ,} n l r

oder

  u n l r , ,

und

   u ^{, ,} n l r

21

oder

   u n l r , ,

 ergibt sich also als Summe der zweiten Koordinate des Zeilenvektors von u , n l r ,

   

und der ersten Koordinate des Spaltenvektors von

 ^ g   1 n l  ^   1 r l  ^ g   1 n l  ^   1 r l

  ergibt sich also als Summe der ersten Koordinate des Zeilenvektors von u , n l r ,

    

und der zweiten Koordinate des Spaltenvektors von

 ^ 1) (1, g   1 n l  ^   1 r l  ^ 1) (2, g   1 n l  ^   1 r l

Sinnvoll ist natürlich, die Matrizenprodukte

durch schrittweises Ausmultiplizieren, beginnend bei

  Also G ( 1 l

usw. Desgleichen ist es sinnvoll, die Matrizenprodukte

durch schrittweises Ausmultiplizieren, beginnend bei

 Also G ( l   n    3 r ) ( ) ( G G für usw.     2 1 n l n l

Damit auch bei dem zweiten Produkt die Zählung bei 0 beginnt, wollen wir dort die Index-

    1 r n transformation vornehmen.

Das obige Ergebnis lässt sich dann folgendermaßen schreiben.

 ergibt sich als Summe der zweiten Koordinate des Zeilenvektors von u , n l r ,

(10)



   und der ersten Koordinate des Spaltenvektors von

22

(11)

 g 

 g 

mit

  ergibt sich als Summe der ersten Koordinate des Zeilenvektors von u , n l r ,

(12)

und der zweiten Koordinate des Spaltenvektors von

(13)

 g 

 g 

mit

Da

^{ }      1 ..., , 1 , 0 ; ) 2 , 2 ( g ) 1 , 1 ( g 2 n l v     1 1 l n l n   n l l   n ([24] Seite 9, THEOREM 2) und wir im Verlauf der obigen Rechnung für

berechnet haben, muss nur noch



  (14)   

bestimmt werden, da n v sich als Differenz von 2 und der Spur dieser Matrix ergibt.

Hier folgt nun der genaue Algorithmus, der an einem einfachen Beispiel erklärt wird.

P und 4 Die periodische Spline-Funktion (hier periodisch, da die y-Werte von 0

stimmen) soll durch die Punkte

 ) 1 | 8 ( P ⁴ für das erste Segment. Mit

2   2 und

7   10 gelten oder wir rechnen mit

y mod ). (siehe auf Seite 14 die Erklärung zur Rechnung mit n l

Mit der folgenden Methode bekommt man nach n Iterationen den exakten Wert. Was bei zu

großen n geschieht, wird später erklärt werden. Bei der Bestimmung der Koeffizienten a , l 1

und a , kann man folgendermaßen vorgehen. Wir wollen dabei die einzelnen Teile der Vor- l 2

gehensweise, nämlich

auf drei Arten angeben: a) in allgemeiner Form, b) für unser obiges Beispiel mit

3   1   2   10 4 2 , , und c) als Struktogramm. Wir beziehen uns im Folgenden auf ein

festes n und auf ein bestimmtes Segment, d. h. auf ein festes l. Deswegen wollen wir die Be-

u  statt u   statt  zeichnungen der Einfachheit halber folgendermaßen wählen: r u , und r n l r ^,   . u , n l r ,

Setzen der Anfangswerte

a) Wir setzen

wegen der Ergebnisse von Seite 21 (10) und Seite 22 (12) für

wegen der Ergebnisse von Seite 22 (11) und Seite 22 (13) und

b) Wir setzen

u  und u2[r] für r u   erhalten wir das Struktogramm der Abb. 19 Seite 24. c) Mit u1[r] für r

Abb. 19

Bestimmen der Iterationen

  1 ..., , 2 , 1 n r Iteration für

a)

wegen der Ergebnisse von Seite 21 (10) und Seite 22 (12).

r wegen der Ergebnisse von Seite 22 (11) und Seite 22 (13) für .

b) Iteration für r = 1

Iteration für r = 2

Iteration für r = 3

u  und u2[r] für r u   erhalten wir das Struktogramm der Abb. 20 c) Mit u1[r] für r

Warum muss man mithilfe von

G1_[1, 1]:= G1[1, 1], G1_[1, 2]:= G1[1, 2], G1_[2, 1]:= G1[2, 1] und G1_[2, 2]:= G1[2, 2]

Kopien erstellen? Warum verwendet man nicht z. B. einfach

G1[2, 1]:= -6/∆[(l + n - 1) mod n]*G1[1, 1] - 2*G1[2, 1]?

Der Grund ist der Folgende: Zwei Zeilen über dieser Anweisung (dort allerdings mit G1_[1, 1]

und G1_[2, 1] auf der rechten Seite) wurde G1[1, 1] schon neu berechnet, wir wollen aber das

alte G1[1, 1], nämlich G1_[1, 1], verwenden.