Ueb02 lsg - Übung 2 Lösung PDF

Preview

Summary

Übung 2 Lösung ...

Description

Mathematik IV f. Elektrotechnik Mathematik III f. Informatik 2. Übungsblatt Fachbereich Mathematik Prof. Dr. Stefan Ulbrich M.Sc. Jan-Erik Lübbers Dipl.-Math. Hannes Meinlschmidt Dipl.-Math. Carsten Schäfer

SoSe 2015 29. April 2015

Gruppenübung

Aufgabe G1 (Polynominterpolation vs. Lineare Splines) Gegeben seien die folgenden Messwerte:

xi yi

−4 −3 −2 −1 0 1 2 3 4 0 0 0 0 1 0 0 0 0

(a) Zeichnen Sie die Messwerte in ein Koordinatensystem ein und überlegen Sie sich, wie der funktionale Zusammenhang zwischen x und y aussehen könnte. Zeichnen Sie ihren Vorschlag in die Skizze ein. Diskutieren Sie Ihren Vorschlag mit Ihren Nachbarn. (b) Berechnen Sie das zugehörige Interpolationspolynom p8 vom Grad n ≤ 8. Werten Sie p8 an den Stellen −4, − 27 , −3, . . . , 4 (auf 2 Nachkommastellen genau) aus und tragen Sie Ihr Ergebnis in eine Wertetabelle ein. Sie müssen p8 nicht in einer speziellen Form angeben. Hinweis: Wer nicht gleich losrechnet, sondern sich erst Gedanken über die geeignete Vorgehensweise macht, kann sich hier einiges an Aufwand sparen. (c) Zeichnen Sie die Punkte aus der Wertetabelle aus (b) in die Zeichnung aus (a) ein und skizzieren Sie den Verlauf von p8 , indem Sie diese Punkte durch eine geeignete Kurve verbinden. (d) Zeichnen Sie den linearen Spline zur Zerlegung ∆ = {−4, −3, . . . , 4} in die Skizze aus (a) und (c) ein und vergleichen Sie diesen mit dem Polynom p8 . Welche Funktion kommt Ihrem Vorschlag aus Aufgabenteil (a) am nächsten? Welches Interpolationsverfahren ist hier geeigneter? Warum? Lösung: (a) Hier gibt es kein richtig oder falsch. Wir haben einen möglichen Vorschlag in Abbildung 1 eingezeichnet (grün). (b) Für diesen Aufgabenteil sind mehrere Lösungswege möglich: 1

i. Die erstbeste, aber aufwendige, Möglichkeit besteht darin, die gegeben Messwerte in ein Newtonschema zu übertragen und die dividierten Differenzen zu bestimmen:

x 0 = −4 x 1 = −3 x 2 = −2

y0 = 0

ց

y1 = 0

ր ց

y2 = 0

0

ց

0

ր ց

ր ց

0 x 3 = −1

y3 = 0

ր ց

1 x4 = 0

y4 = 1

ր ց

y5 = 0

ր ց

−1 x5 = 1

0 x6 = 2 x7 = 3 x8 = 4

y6 = 0

ր ց

y7 = 0

ր ց

y0 = 0

ր ց ր ց ր ց ր ց

0

ր ց

0

ր

0

ց

0

ր ց

1 2

ր ց

−1

ր ց

1 2

ր ց

0

ր ց

0

ց

1 6

ր ց

− 21

ր ց

1 2

ր ց

− 61 0

0

ր ց

1 24

ց

− 61

ր ց

1 4

ր ց

− 61

ր ց

1 24

ր

1 − 24

ց

1 12

ր ց

1 − 12

ր ց

1 24

1 48

ց

1 − 36

ր ց

1 48

ր

1 − 144

ց

1 144

ր

1 576

ր

ր

ր

ր

Daraus erhält man



1 1 1 x+ − x(x − 1) 24 24 48  1 1 x(x − 1)(x − 2)(x − 3) . − x(x − 1)(x − 2) + 576 144

p8 (x) = (x + 4)( x + 3)(x + 2)( x + 1)

ii. Man kann sich die Berechnung der dividierten Differenzen auch vereinfachen, indem man die Stützstellen umsortiert:

ˆx 0 = x 0 = −4 yˆ0 = y0 = 0

ց

ˆx 1 = x 1 = −3 yˆ1 = y1 = 0

ր ց

ˆx 2 = x 2 = −2 yˆ2 = y2 = 0

ր ց

ˆx 3 = x 3 = −1 yˆ3 = y3 = 0

ր ց

0

ց

0

ր ց

0

yˆ4 = y5 = 0

ր ց

yˆ5 = y6 = 0

ր ց

ˆx 6 = x 7 = 3

yˆ6 = y7 = 0 yˆ7 = y8 = 0

ր ց

ˆx 8 = x 4 = 0

yˆ8 = y4 = 1

ր

ր ց ր ց ր ց

− 14

ց

0

ր ց

ր ց ր ց ր ց

1 12

ց

0

ր ց

ր ց ր ց

0 0

ր ց

0

0 0

ր ց ր ց

0

0

0 0

ˆx 7 = x 8 = 4

ր ց

0 0

ր ց

0

0 0

ˆx 5 = x 6 = 2

ց

0 0

ˆx 4 = x 5 = 1

0

1 − 24

ր ց

1 24

0

ց

0

ր ց

ր ց ր ց

0

ր ց

1 24

ր

0

ց

0

ր ց

1 48

0

ց

1 144

ր

1 576

ր

ր

ր

ր

ր

2

Aus diesem Schema ergibt sich die Darstellung

1 (x + 4)(x + 3)(x + 2)(x + 1)(x − 1)(x − 2)(x − 3)(x − 4). 576

p8 (x) =

iii. Alternativ kann man sich auch folgende Beobachtung zu Nutze machen: Wegen y0 = y1 = y2 = y3 = y5 = y6 = y7 = y8 = 0 und y4 = 1, sowie x 4 = 0 vereinfacht sich die Lagrange-Darstellung von p8 zu

p8 (x) =

8 X

y k L k,8 (x) = L4,8 (x) =

8 Y x − xj j=0 j6=4

k=0

x4 − x j

=

8 Y x − xj j=0 j6=4

−x j

.

Ausgeschrieben bedeutet dies also

p8 (x) = =

(x + 4)( x + 3)( x + 2)(x + 1)( x − 1)( x − 2)( x − 3)( x − 4) 4 · 3 · 2 · 1 · (−1) · (−2) · (−3) · (−4) (x + 4)(x + 3)(x + 2)( x + 1)( x − 1)( x − 2)( x − 3)( x − 4) 576

.

Unabhängig von der Darstellung und vom Rechenweg ergibt sich folgende Wertetabelle:

x

−4

−3.5

p8 (x)

0

−1.96

−3 −2.5 −2 0

0.55

0

−1.5

−1 −0.5 0

−0.35

0

0.67 1

Wir haben die zweite Hälfte der Tabelle weggelassen, da aus der Lagrange-Darstellung ersichtlich wird, dass p8 eine gerade Funktion ist (d.h. es gilt p8 (x) = p8 (−x)). (c) Das Interpolationspolynom p8 ist in Abbildung 1 dargestellt (blau).

1

0

−1

Linearer Spline (d) Interpolationspolynom (c) Vorschlag (a)

−2 −4 −3.5 −3 −2.5 −2 −1.5 −1 −0.5

0

0.5

1

1.5

2

2.5

3

3.5

4

Abbildung 1: Das Interpolationspolynom p8 und der lineare Spline s . (d) Der lineare Spline lässt sich einfach einzeichnen, indem man die Punkte (x i , y i ), i = 0, . . . , 8 durch einen Polygonzug verbindet. Der Spline ist in Abbildung 1 dargestellt (rot). Die Messwerte legen die Vermutung nahe, dass die gemessene Funktion für x > 1 und x < −1 konstant gleich Null oder nur sehr wenig von Null verschieden ist. Das Interpolationspolynom schwankt in diesen Bereichen sehr stark und ist deutlich von Null verschieden. Daher kann die Interpolation durch den linearen Spline als die vernünftigere der beiden Interpolationstechniken angesehen werden. 3

Aufgabe G2 (Interpolationsfehler) Wir betrachten die Funktion

f : [0, 2] → [−1, 1],

x 7→ sin(πx).

Die Abbildung f soll nun durch Interpolation an den Stützstellen x 0 , . . . , x 4 angenähert werden. (a) Wir wählen die Stützstellen äquidistant auf [0, 2], d.h. x k = 0 + 2k, k = 0, . . . , 4. i. Geben Sie eine Abschätzung für den Fehler der Polynominterpolation vom Grad n ≤ 4 an. ii. Geben Sie eine Abschätzung für den Fehler der linearen Spline-Interpolation zur Zerlegung ∆ = {x i : i = 0, . . . , 4} an. (b) Wir wollen nun an den Tschebyschev-Abszissen   b−a 2k + 1 π b+a ˆ · xk = cos + , 2 n+1 2 2

k = 0, . . . , 4

interpolieren. i. Geben Sie eine bessere Abschätzung für den Fehler der Polynominterpolation vom Grad n ≤ 4 als in (a) an. ii. Geben Sie eine Abschätzung für den Fehler der linearen Spline-Interpolation auf dem kleineren ˆ = { ˆx i : i = 0, . . . , 4} an. Intervall [ xˆ4 , xˆ0 ] zur Zerlegung ∆ Lösung: (a)

i. Wir verwenden Korollar 1.1.4 aus der Vorlesung. Demnach gilt für den Fehler:    f (5) (x) max | f (x) − p4 (x)| ≤ max · 25 . x ∈[0,2] x ∈[0,2] 5! Wir bestimmen also die fünfte Ableitung von f :

f ′ (x) = π · cos(πx),

f (x ) = sin(π x ), f ′′ (x ) = −π2 · sin(πx ),

f ′′′ ( x ) = −π3 · cos(π x ),

f (4) (x) = π4 · sin(πx),

f (5) (x) = π5 · cos(πx).

f (5) (x) = π5 · cos(πx) durchläuft auf [0, 2] alle Werte in [−π5 , π5 ]. Wir können die Schranke an den Fehler also durch max | f (x) − p4 (x)| ≤

x ∈[0,2]

π5 · 32 ≈ 81.6052 120

abschätzen. ii. Wir verwenden Satz 1.2.3 aus der Vorlesung. Demnach gilt für den Fehler:

2    1 ′′   max | f (x) − s(x)| ≤ max f (x) · max x i+1 − x i . i=0,...,3 x ∈[0,2] 8 x ∈[0,2]  2 Wegen der äquidistanten Wahl der x k ist der letzte Faktor 21 = 41 und die zweite Ableitung f ′′ (x) = −π2 · sin(πx) durchläuft auf [0, 2] alle Werte in [−π2 , π2 ]. Wir können die Schranke an den Fehler also durch max | f (x) − s(x)| ≤

x ∈[0,2]

1 2 1 π2 ·π · = ≈ 0.3084 8 32 4

abschätzen. 4

(b) Wir berechnen zuerst die neuen Stützstellen:     π 3π + 1 ≈ 1.5878, + 1 ≈ 1.9511, ˆ ˆx 0 = cos x 1 = cos 10 10     9π 7π x = cos xˆ3 = cos + 1 ≈ 0.0489. + 1 ≈ 0.4122, ˆ4 10 10

ˆx 2 = cos

  π + 1 = 1, 2

Es fällt auf, dass die Tschebyschev-Abszissen nur wenig von den äquidistanten Stützstellen abweichen. Das liegt an der geringen Anzahl (n + 1) = 5 von Stützstellen. Für größeres n wird der Unterschied deutlicher. i. Wir verwenden Korollar 1.1.4 aus der Vorlesung, nutzen jedoch diesmal den mittleren Term in der Ungleichungskette. Demnach gilt für den Fehler:    f (5) (x) max | f (x) − ˆp4 (x)| ≤ max ˆ · max |ω(x)|. x ∈[0,2] x ∈[0,2] x ∈[0,2] 5!

Der erste Faktor ist bereits aus (a) bekannt und laut Skript gilt für die Interpolation an den Tschebyschev-Abszissen die Gleichung   1 b − a n+1 −n 2 = 15 · 2−4 = max |ω(x)| ˆ . = x ∈[0,2] 2 16

Wir können die Schranke an den Fehler also durch

max | f (x) − pˆ4 (x)| ≤

x ∈[0,2]

1 π5 · ≈ 0.1594 120 16

angeben. ii. Wir wollen wieder Satz 1.2.3 aus der Vorlesung verwenden. Im Gegensatz zur Polynominterpolation ist es bei Splines wichtig, dass die Stützstellen aufsteigend sortiert sind. Wir müssen daher eine Umsortierung vornehmen:     π 3π + 1, ˜x 2 = xˆ2 = 1, + 1, ˜ x˜3 = ˆx 1 = cos x 4 = xˆ0 = cos 10 10     7π 9π ˜ x 1 = xˆ3 = cos x˜0 = ˆx 4 = cos + 1, + 1. 10 10 Für die Zerlegung gilt auch unter Verwendung der neu eingeführten Bezeichnungen

ˆ = {xˆi : i = 0, . . . , 4} = { ˜x i : i = 0, . . . , 4}. ∆ Demnach gilt für den Fehler:

2    1 ′′   max f (x) · max x˜i+1 − x˜ i . max | f (x) − ˆs (x)| = max | f (x) − ˆs (x)| ≤ i=0,...,3 x ∈[˜x 0 ,x˜4 ] x ∈[ˆ x 4 , xˆ0 ] 8 x ∈[˜x 0 , x˜4 ]

Der vordere Faktor in der Fehlerabschätzung bleibt trotz verkleinertem Intervall unverändert gegenüber (a), da man leicht überprüft, dass das Maximum π2 von | f ′′ | z.B. in x = 0.5 angenommen wird. Für den hinteren Faktor gilt 2   2     7π 7π 2 2 = cos ≈ 0.3455 max ˜x i+1 − x˜ i = (˜x 2 − ˜x 1 ) = − cos i=0,...,3 10 10 und somit ist

  7π π2 2 max | f (x) − ˆs (x)| ≤ · cos ≈ 0.4262. x ∈[ˆx 4 , xˆ0 ] 8 10 5

Wir sehen, dass die Schranke für den Fehler bei der Polynominterpolation für äquidistante Stützstellen wesentlich schlechter ist, als bei den Tschebyschev-Abszissen. Das liegt hier aber vor allem daran, dass das Maximum des Knotenpolynoms im äquidistanten Fall nur sehr grob abgeschätzt werden kann, für die Tschebyschev-Abszissen jedoch exakt bekannt ist. Es ist zu erwarten, dass die tatsächlichen Fehler für die verschiedenen Stützstellenwahlen nur gering von einander abweichen, da auch die Sützstellen nicht besonders unterschiedlich sind. Die eigentliche Stärke der Tschebyschev-Abszissen kommt erst bei höherem Polynomgrad richtig zur Geltung. In diesem Fall unterscheidet sich die Wahl der Stützpunkte auch deutlicher von der äquidistanten Unterteilung. Wir werden auf den hier betrachteten Fehler noch einmal in Aufgabe G3 eingehen. Aufgabe G3 (Lineare Splines & Tschebyschev-Interpolation) Wir betrachten nochmals Aufgabe G2. (a) Bestimmen Sie die Interpolationspolynome p4 und pˆ4 vom Grad n ≤ 4, die die Funktion f an den Stützstellen (x k ) bzw. (ˆ x k ) interpolieren. (b) Der jeweilig größte Interpolationsfehler wird in x ∗ = 0.1878 bzw. xˆ∗ = 1.3032 gemacht. Bestimmen Sie die Werte der Interpolationsfehler und vergleichen Sie diese mit denen in G2 gemachten Abschätzungen. (c) In Abbildung 2 sehen Sie die Funktion f . Zeichnen Sie in das Bild den linearen Spline s zu den Knoten (x k ) ein. Berechnen Sie den maximalen Interpolationsfehler des linearen Splines s zur Zerlegung ∆. Vergleichen Sie den Wert ebenfalls mit der Abschätzung aus G2.

6

1.2 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1.2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

1.4

Abbildung 2: Zu Aufgabe G3: Funktion f (x) = sin(πx)

1.5

1.6

1.7

1.8

1.9

2

7

Lösung: (a)

i. Wir tragen die Stützstellen in ein Newtonschema ein und berechnen die dividierten Differenzen: ց x 0 = 0 y0 = f ( x 0 ) = 0 2 ց 1 ր x 1 = 2 y1 = f (x 1 ) = 1 −4 ց ց 8 −2 ր ց ց 3 ր ր 0 ց 0 x 2 = 1 y2 = f (x 2 ) = 0 ց 8 ր −2 ր ց 3 4 ր x 3 = 23 y3 = f (x 3 ) = −1 ր ց 2 ր ր x 4 = 2 y4 = f (x 4 ) = 0 Wir lesen in der oberen Diagonale die Koeffizienten γi für die Newtonsche Darstellung ab und erhalten   8   16 8 x p4 (x) = 2x − 4x x − 12 + x x − 12 (x − 1) = x 3 − 8x 2 + 3 3 3 als Interpolationspolynom zu den äquidistanten Stützstellen. ii. Wir verfahren wie oben, verwenden aber diesmal die Tschebyschev-Abszissen, die wir in Aufgabe G2 berechnet haben. Das Newtonschema hat dann folgende Form:

x 0 ≈ 1.9511 ˆ x 1 ≈ 1.5878 ˆ ˆ x2 = 1 ˆ x 3 ≈ 0.4122 ˆ x 4 ≈ 0.0489

ˆy0 = f (ˆ x 0 ) ≈ −0.153

ց

ˆy1 = f (ˆ x 1 ) ≈ −0.9622

ր ց

x2) = 0 ˆy2 = f (ˆ

ր ց

ˆy3 = f (ˆ x 3 ) ≈ 0.9622 ˆy4 = f (ˆ x 4 ) ≈ 0.153

2.2274

ց

−1.637

ր ց

−1.637

ր ց

2.2274

ր

ր ց

4.0631

ց

0

ր ց

−4.0631

2.6403

ց

2.6403

ր

0

ր

ր

Wir lesen wieder die Koeffizienten ab und erhalten

ˆ p4 (x) = −0.153 + 2.2274(x − 1.9511) + 4.0631(x − 1.9511)(x − 1.5878) + 2.6403(x − 1.9511)(x − 1.5878)(x − 1). als Interpolationspolynom. (b) Wir berechnen die Fehler



 16 8 3 2 x − 8x ∗ + x ∗ ≈ 0.5564 − 0.7371 = −0.1807, f (x ∗ ) − p4 ( x ∗ ) = sin(π x ∗ ) − 3 ∗ 3  x ∗ ) − − 0.153 + 2.2274(ˆx ∗ − 1.9511) x ∗ ) − ˆp4 (ˆx ∗ ) = sin(πˆ f (ˆ x ∗ − 1.9511)(ˆx ∗ − 1.5878) + 4.0631(ˆ

 + 2.6403(ˆx ∗ − 1.9511)(ˆx ∗ − 1.5878)(ˆ x ∗ − 1)

≈ −0.8149 + 0.6993 = −0.1156.

Wir sehen, dass im Falle äquidistanter Stützstellen die Schranke den tatsächlichen Interpolationsfehler um mehr als das 400-Fache überschätzt. Dies liegt auch mit daran, dass die Abschätzung für das Knotenpolynom sehr grob ist. (c) Der Spline ist in Abbildung 3 zu sehen. 8

1.2 1 0.8 0.6 0.4 0.2 0 −0.2 −0.4 −0.6

Linearer Spline s(x) Funktion f (x) = sin(πx)

−0.8 −1 −1.2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

Abbildung 3: Lösung zu Aufgabe G3 (c)

1.4

1.5

1.6

1.7

1.8

1.9

2

9

Wir bestimmen den Interpolationsfehler h(x) := f (x ) − s( x ) auf den einzelnen Teilintervallen [x i , x i+1 ], i = 0, 1, 2, 3. Wir betrachten das erste Teilintervall [0, 0.5]. Wir sehen, dass dort der Spline gerade der linearen Funktion x 7→ 2x entspricht. Außerdem entnehmen wir Abbildung 3, dass dort s(x ) ≤ f ( x ) gilt. Der maximale Interpolationsfehler auf [0, 0.5] lässt sich also als das Maximum von

g : [0, 0.5] → [0, 1]

x 7→ sin(πx) − 2x

bestimmen. Wir setzen die erste Ableitung 0 und erhalten !

′

0 = g (x) = π cos(πx) − 2

¯x =

⇔

cos−1 π

2  π

≈ 0.2803 ∈ [0, 0.5].

Wir bestimmen die zweite Ableitung

g ′′ (x) = f ′′ (x ) = −π2 sin(π x ) x ) < 0 gilt. x¯ ist also ein lokales Maximum von g . An den Intervallenden und sehen, dass g ′′ (¯ verschwindet der Interpolationsfehler wegen der Interpolationsbedingung, daher ist der maximale Fehler auf [0, 0.5] also max | f (x) − s(x)| = g

x ∈[0,0.5]



cos−1 π

 2  π

≈ 0.2105.

Man überlegt sich nun leicht, dass die Beziehungen h(x) = h(1 − x) = g(1 − x) für x ∈ [0.5, 1] und h(x) = −h(x − 1) = −g(x − 1) für x ∈ [1, 2] gelten. Der maximale Interpolationsfehler auf den Teilintervallen ist also jeweils gleichgroß. Daher ist

max | f (x ) − s( x )| = max | f (x) − s(x)| ≈ 0.2105.

x ∈[0,2]

x ∈[0,0.5]

Die Schranke aus Aufgabe G2 ist um ca. 50% größer als der tatsächliche Fehler.

Hausübung Aufgabe H1 (Kubische Splines) Gegeben sei die Funktion

f : [−1, 1] → [1, 2],

π

x 7→ 2cos( 2 x ) .

Interpolieren Sie die Funktion f durch einen kubischen Spline. Verwenden Sie dabei die Zerlegung ∆ = {−1, 0, 1} und natürliche Randbedingungen. Lösung: Es gilt

y0 = f (−1) = 1,

y1 = f (0) = 2,

y2 = f (1) = 1,

und

h0 = h1 = 1.

Daraus ergibt sich für die Momente M0 , M1 , M2 das Gleichungssystem

   0 M0  1 2 1  M1  = −2 6 3 6 M2 0 0 0 1 

1 0 0



10

mit der eindeutigen Lösung

M0 = 0,

M1 = −3,

M2 = 0.

Dass M0 = M2 = 0 sein muss, hätten wir auch direkt aus den natürlichen Randbedingungen ablesen können. So oder so ergeben sich die Konstanten

3 2−1 1 − (−3 − 0) = , 6 1 2 3 1−2 1 − (0 − (−3)) = − , c1 = 2 6 1

c0 =

d0 = 1, 5 1 d1 = 2 − (−3) = . 6 2

Daraus folgt

3 1 s0 (x) = − (x + 1)3 + (x + 1) + 1, 2 2 1 5 3 s1 (x) = (x − 1)3 − x + . 2 2 2 Wir beobachten noch s1 (x) = s0 (−x). Diese Achsensymmetrie des kubischen Splines war aufgrund der Achsensymmetrie von f und den symmetrisch um die Achse x 1 gewählten Knoten auch zu erwarten. Die Funktion und der Spline sind in Abbildung 4 dargestellt.

2 1.8 1.6 1.4 1.2 1 0.8 0.6 −1.2 −1 −0.8 −0.6 −0.4 −0.2

Funktion Spline