Interdisziplinäres Projekt - in.tum.de fileInterdisziplinäres Projekt im Rahmen der Diplomhauptprüfung f ür Informatiker im Nebenfach Mathematik an der Technischen Universit

Interdisziplinares Projekt

im Rahmen der Diplomhauptprufung fur Informatiker im NebenfachMathematik

an der

Technischen Universitat Munchen

Fakultat fur Informatik

Thema: Musterlosungen zur Vorlesung Konkrete Mathematik

Bearbeiter: Nils NitschFred-Hartmann-Weg 1985435 Erding

Prufer: Professor Dr. Thomas HuckleTechnische Universitat MunchenLehrstuhl fur Informatik mit Schwerpunkt Wissenschaftliches Rechnen

Abgabedatum: 29. September 2005

Inhaltsverzeichnis

1 Rundungsfehler 3

2 Lineare Gleichungssysteme 15

3 Interpolation 29

4 Fourier-Transformation 39

5 Iterative Verfahren 44

6 Differentialgleichungen 55

2

1 Rundungsfehler

1.1 Aufgabe 1 (Buch, Ubung: 24)

1.1.1 Aufgabenstellung

Geben Sie alle Funktionen f(x) an, die fur samtliche x eine konstante Konditionszahlcondx = k besitzen.Insbesondere: fur welche Funktion wird der Fehler in den Eingangsdaten uberhaupt nichtverstarkt (k = 0)?

1.1.2 Losung

Tip

Finden Sie die Losung der Differentialgleichung

y′ = k · y

xmit , k ∈ R

(z.B. Nachschlagen in einer Formelsammlung)

Losungsschritt

Die Losung der Differentialgleichung lautet:

f(x) = xk

Losungsschritt

Daraus folgt:

condx =∣∣∣∣x · f ′(x)

f(x)

∣∣∣∣ = ∣∣∣∣x · k · xk−1

xk

∣∣∣∣ = ∣∣∣∣xk · kxk

∣∣∣∣ = |k|

Losungsschritt

Insbesondere gilt fur k = 0:condx = 0

D.h. nur fur f(x) = const wird der Fehler in den Eingangsdaten uberhaupt nichtverstarkt.

3



Ersetzen Sie den Differentialoperator dx := d/dx fur stetig differenzierbare Funktionenf ∈ C1[0, 1] durch den Differenzenoperator ∆h

x mittels

∆hxf(x) :=

f(x + h)− f(x)h

, h > 0.

Zur Vereinfachung betrachten Sie nur den Rundungsfehler, der bei der Differenz entstehtund den Fehler, der durch die Diskretisierung, d.h. das Ersetzen des Differential- durchden Differenzoperator, gemacht wird. Der resultierende Gesamtfehler fd ergibt sich ausder Bildung der Differenz −M und der angenaherten Ableitung ∆h

x in Abhangigkeit derSchrittweite h. Fur welches h ist der Gesamtfehler minimal?

1.2.2 Losung

Tip

Analysieren Sie den Diskretisierungsfehler mit Hilfe der Taylor-Reihe fur f(x+h). GebenSie auch die auftretenden Konstanten an! Der bei der Differenz auftretende Fehler sei ε.

Losungsschritt

Fur den Diskretisierungsfehler gilt (mit Hilfe der Taylor-Reihe):

f(x + h) = f(x) + f ′(x) · h +f ′′(ξ)

2!· h2, ξ ∈ [x, x + h]

⇒ f ′(x) =f(x + h)− f(x)

h− f ′′(ξ)

2· h

⇒∣∣∣f ′(x)−∆h

xf(x)∣∣∣ ≤ ∣∣∣∣f ′′(ξ)2

· h∣∣∣∣

Tip

Rundungsfehler bei der Differenzbildung:

a−M b = (a− b) · (1 + ε)

4

Losungsschritt

Rundungsfehler bei der Differenzbildung:

∆hxf(x) = ∆h

xf(x) · (1 + ε)

wobei ε der relative Fehler bei der Subtraktion ist mit |ε| ≤ εmasch.Daraus ergibt sich fur den Rundungsfehler:∣∣∣∆h

xf(x)−∆hxf(x)

∣∣∣ ≤ ∣∣∣∆hxf(x)

∣∣∣ · εmasch ≤|f(x + h)|+ |f(x)|

|h|· εmasch ≤ c1 · εmasch

1h

Losungsschritt

Der Gesamtfehler lautet damit:∣∣∣∣∣∆hxf(x)− f ′(x)

f ′(x)

∣∣∣∣∣ ≤ |∆hxf(x)−∆h

xf(x)|+ |∆hxf(x)− f ′(x)|

|f ′(x)|≤ c1 ·εmasch ·

1h

+∣∣∣∣ f ′′(ξ)2f ′(x)

∣∣∣∣︸︷︷︸:=c2

·h

= c1 ·1h· εmasch + c2 · h = fd(h)

Der Gesamtfehler ist nun minimal fur f ′d = 0, d.h.

f ′d = − 1h2· c1 · εmasch + c2 = 0

⇔ h2 =c1

c2· εmasch

⇒ h =√

c1

c2· εmasch ⇒ h = O(

√εmasch)

5



Analysieren Sie mit Hilfe der Epsilontik den Ausdruck y = a2 − b2.

a) Berechnen Sie die Konditionszahlen bezuglich a und b. Fur welchen Fall ist das Pro-blem schlecht konditioniert?

b) Zeigen Sie, dass fur den relativen Fehler des Resultats gilt

εy = − 2a2

a2 − b2· εa +

2b2

a2 − b2· εb −

a2

a2 − b2· ε1 +

b2

a2 − b2· ε2 − ε3.

Die Werte εa und εb reprasentieren die relativen Fehler in den Eingabedaten a undb und ε1, ε2 und ε3 die relativen Fehler in den Berechnungen von a ·M a, b ·M b unda2 −M b2.

c) Fuhren Sie die Analyse auch fur den alternativen Berechnungsweg (a+M b) ·M (a−M b)durch. Vergleichen und diskutieren Sie die Ergebnisse.

d) Welchen Berechnungsweg wurden Sie empfehlen? Warum?

1.3.2 Losung

zu a)

Losungsschritt

Fur y = a2 − b2 gilt bezuglich a und b:

f(a) = a2 − b2

f(b) = a2 − b2

d.h.

1) bzgl. a: f(a) = a2 − b2; f ′(a) = 2a

⇒ conda =∣∣∣∣a · (2a)a2 − b2

∣∣∣∣ = ∣∣∣∣ 2a2

a2 − b2

∣∣∣∣2) bzgl. b: f(b) = a2 − b2; f ′(b) = −2b

⇒ condb =∣∣∣∣b · (−2b)

a2 − b2

∣∣∣∣ = ∣∣∣∣− 2b2

a2 − b2

∣∣∣∣

6

Losungsschritt

D.h. das Problem ist schlecht konditioniert fur den Fall, dass a ≈ b

zu b)

Losungsschritt

frel(y) = y−yy

y = a(1 + εa) ·M a(1 + εa)−M b(1 + εb) ·M b(1 + εb)= a2(1 + 2εa) · (1 + ε1)−M b2(1 + 2εb)(1 + ε2)= ((a2 + ε1a

2 + 2εaa2)− (b2 + ε2b

2 + 2εbb2)) · (1 + ε3)

= a2 − b2 + εa2a2 − εb2b2 + ε1a2 − ε2b

2 + ε3(a2 − b2)

Losungsschritt

Nun gilt fur den relativen Fehler:

frel(y) =y − y

y

=a2 − b2 − y

a2 − b2

= − 2a2

a2 − b2· εa +

2b2

a2 − b2· εb −

a2

a2 − b2· ε1 +

b2

a2 − b2· ε2 − ε3 �

zu c)

Losungsschritt

y = (a + b)(a− b)

y = (a(1 + εa) +M b(1 + εb)) ·M (a(1 + εa)−M b(1 + εb))= ((a + aεa + b + bεb) · (1 + ε1)) ·M ((a + aεa − b− bεb)(1 + ε2))= (a2 − b2 + (a2 − b2)ε1 + (a2 − b2)ε2 + 2a2εa − 2b2εb) · (1 + ε3)= a2 − b2 + 2a2εa − 2b2εb + (a2 − b2)ε1 + (a2 − b2)ε2 + (a2 − b2)ε3

Somit gilt fur den relativen Fehler:

frel = − 2a2

a2 − b2εa +

2b2

a2 − b2εb − ε1 − ε2 − ε3

7

Losungsschritt

In dem Verfahren aus a) liegt ein hohere relativer Fehler vor, da ε1 und ε2 durch denvorangestellten Faktor a2

a2−b2bzw. b2

a2−b2verstarkt werden.

zu d)

Losungsschritt

Hier ist das Verfahren aus c) zu empfehlen, da es weniger Fehleranfallig ist und zudemauch nur 3 Rechenoperationen benotigt, d.h. gleich schnell ist.

8



Entscheiden Sie, welche der folgenden Ausdrucke fehleranfalliger ist. Versuchen Sie gege-benenfalls ein besseres Verfahren zur Berechnung anzugeben und untersuchen Sie auchdie Kondition.

a) 2 sin2 x2 = 1− cos x fur x ≈ 0

b) log(xy ) = log(x)− log(y) fur x > 0 und y > 0

c) f(x) = 1 + sinx

d) f(x) = (x− 1)2 − (x + 1)2 fur x ≈ 0

e) f(x) = exp(x)− 1− x fur x ≈ 0

1.4.2 Losung

zu a)

Losungsschritt

Um den Rundungsfehler im Verlauf der verschiedenen Berechnungsarten zu verfolgen,betrachten wir ungestorte Eingabedaten, also x ohne Rundungsfehler. Es ergibt sich furdie jeweiligen relativen Fehler im Endergebnis bei Verwendung der rechten Formel

frel =[1− (1 + ε1) cos x](1 + ε2)− (1− cos x)

1− cos x

=ε2 − cos x(ε1 + ε2)

1− cos(x)

= ε2 − ε1cos x

1− cos x

Da der Term cos x1−cos x beliebig groß werden kann, gibt es keine obere Schranke fur den

relativen Fehler. Diese Berechnungsvorschrift ist also nicht geeignet.

Losungsschritt

Fur die linke Formel ergibt sich ein relativer Fehler von:

y = 2(sinx

2· (1 + ε1))2 · (1 + ε2)

= 2 sin2 x

2· (1 + ε1)2 · (1 + ε2)

⇒ |frel| = 2|ε1|+ |ε2| ≤ εmasch

Diese Art der Berechnung ist offenbar stabil, wobei der Fehler im Bereich der Maschi-nengenauigkeit bleibt.

9

Tip

Reihenentwicklung von sin und cos einsetzten.

Losungsschritt

Die Konditionszahl der Funktion lautet:

condx =x · sinx

1− cos x

Fur x ≈ 0 kann man die Reihenentwicklung von cos und sin einsetzten und erhalt inerster Naherung

condx =x2 + . . .

1− (1− x2/2 + . . .)≈ 2

zu b)

Losungsschritt

Fur den linken Term ergibt sich:

y = log(x

x· (1 + ε1)

)· (1 + ε2)

=(

log(

x

y

)+ log(1 + ε1)

)· (1 + ε2)

Daraus ergibt sich fur den relativen Fehler:

frel =

∣∣∣y − log xy

∣∣∣∣∣∣log xy

∣∣∣=

∣∣∣∣∣(1 + ε2)

(1 +

log (1 + ε1)log x

y

)− 1

∣∣∣∣∣=

∣∣∣∣∣ε2 +log (1 + ε1)

log xy

∣∣∣∣∣Losungsschritt

Fur den rechten Term ergibt sich:

y = ((1 + ε1) log x− (1 + ε2) log y) · (1 + ε3)

10


frel =|y − log x + log y||log x− log y|

=∣∣∣∣(1 + ε3)

(1 +

ε1 log x− ε2 log y

log x− log y

)∣∣∣∣=

∣∣∣∣ε3 +ε1 log x− ε2 log y

log x− log y

∣∣∣∣Da log(1 + ε1) ≈ ε1 ist log

(xy

)i.A. gunstiger. Falls jedoch x ≈ y ≈ 1 fuhrt der untere

Ausdruck zu besseren Ergebnissen.

Losungsschritt

Die Konditionszahlen fur beide Terme lauten:

condx =1

log xy

und condy =−1

log xy

Fur x ≈ y ist dieses Problem schlecht konditioniert, daher kann man kein stabiles Ver-fahren erwarten.

zu c)

Losungsschritt

Es gilt:

y = (1 + sin x(1 + ε1)) · (1 + ε2)= 1 + sinx + sin xε1 + (1 + sin x)ε2


frel =∣∣∣∣ y − 1− sinx

1 + sin x

∣∣∣∣=

∣∣∣∣ sinx

1 + sin x· ε1 + ε2

∣∣∣∣Da der Term sin x

1+sin x fur den Fall x ≈ 32π + k · 2π beliebig groß werden kann, gibt es in

diesem Fall keine obere Schranke fur den relativen Fehler. Diese Berechnungsvorschriftist hier also nicht geeignet.

Tip

Einsetzen von x = x2 + x

2 und umformen.

11

Losungsschritt

Formt man den Term 1 + sinx um, so erhalt man:

1 + sin x = 1 + 2 · sin(x

2

)cos(x

2

)fur den gilt:

y =[1 + 2 · (sin

(x

2

)(1 + ε1)) · (cos

(x

2

)(1 + ε2)) · (1 + ε3)

](1 + ε4)

= 1 + 2 · sin(x

2

)cos(x

2

)+ 2 · sin

(x

2

)cos(x

2

)(ε1 + ε2 + ε3 + ε4) + ε4


frel =

∣∣∣∣∣ y − 1− 2 · sin(

x2

)cos(

x2

)1 + 2 · sin

(x2

)cos(

x2

) ∣∣∣∣∣=

∣∣∣∣∣2 · sin(

x2

)cos(

x2

)(ε1 + ε2 + ε3 + ε4) + ε4

1 + 2 · sin(

x2

)cos(

x2

) ∣∣∣∣∣Hier erhalt man nun fur den Fall x ≈ 3

2π + k · 2π ein Fehler ≈ εmasch.

Losungsschritt

Ein Vergleich der Konditionszahlen ergibt nun fur f(x) = 1 + sinx:

condx =x · f ′(x)

f(x)=

x · cos x

1 + sin x

und fur g(x) = 1 + 2 · sin(

x2

)cos(

x2

):

condx =x · g′(x)

g(x)=

x · cos(x)1 + 2 · sin

(x2

)cos(

x2

)Hierbei ist ersichtlich, dass Verfahren 1 fur den Fall x ≈ 3

2π+k ·2π schlecht konditioniertist, Verfahren 2 jedoch uberall gut konditioniert ist.

zu d)

Losungsschritt

Es gilt:

y = (((x− 1)(1 + ε1))2(1 + ε2)− ((x + 1)(1 + ε3))2)(1 + ε4))(1 + ε5)


frel =∣∣∣∣ y − y

x

∣∣∣∣ = ∣∣∣∣(2ε1 + ε2)(x− 1)2

y− (2ε3 + ε4)(x + 1)2

y+ ε5

∣∣∣∣Hier ist offensichtlich fur y ≈ 0 mit großen relativen Fehler zu rechnen.

12

Tip

Ausmultiplizieren

Losungsschritt

Einfaches Ausmultiplizieren ergibt:

f(x) = (x− 1)2 − (x + 1)2 = −4x


frel =∣∣∣∣(−4x)(1 + ε)− (−4x)

−4x

∣∣∣∣ = |ε|

Losungsschritt

condx =x · f ′(x)

f(x)=

x(−4)−4x

= 1

Daher haben wir hier ein gut konditioniertes Problem, welches mit der zweiten Rechen-methode auch mit kleinem Fehler gelost werden kann.

zu e)

Losungsschritt

Es gilt:

y = ((ex − 1)(1 + ε1)− x)(1 + ε2) = ex − 1− x + exε2 − ε2 − xε2 − exε1 − ε1


frel =∣∣∣∣ε2 − ex + 1

ex − 1− xε1

∣∣∣∣Hier ist fur x ≈ 0 mit großen relativen Fehler zu rechnen.

Tip

Reihentwicklung von ex einsetzen.

Losungsschritt

Ein stabiles Verfahren kann man uber die Reihenentwicklung von ex konstruieren:

ex = 1 + x +x2

2!+

x3

3!. . . ⇒ ex − 1− x =

x2

2!+

x3

3!Bricht man diese Reihe nach n Elementen ab, so erhalt man einen Fehler, der kleiner istals xn

n! .

13

Losungsschritt

Die Konditionszahl der Funktion lautet:

condx =x · (ex − 1)ex − 1− x

=xex − x

ex − 1− x

Das Problem ist also fur x ≈ 0 schlecht konditioniert.

14

2 Lineare Gleichungssysteme



Gegeben ist ein lineares Gleichungssystem mit einer Tridiagonalmatrix

a1 c1 0 · · · 0

d2 a2 c2...

0. . . . . . . . . 0

.... . . . . . cn−1

0 · · · · · · dn an

x1

x2......

xn

=

b1

b2......

bn

a) Formulieren Sie das Verfahren der Gauß-Elimination ohne Pivotsuche in einem Pseu-

docode zur Losung des obigen Gleichungssystems.

b) Wieviele Additionen, Multiplikationen, Divisionen benotigt dieser Algorithmus?

c) Man untersuche die Fragestellung von Teilaufgabe a) und b) fur den Fall von Spalten-und Total-Pivotsuche.

15

2.1.2 Losung

zu a)

Losungsschritt

FOR i = 1,...,n-1factor = A[i+1,i] / A[i,i]A[i+1,i+1] = A[i+1,i+1] - factor * A[i,i+1]b[i+1] = b[i+1] - factor * b[i]A[i+1,i] = 0

ENDFOR

Durch das Ausnutzen der Tridiagonalstruktur kommt dieser Algorithmus ohne ver-schachtelte Schleifen aus.

zu b)

Losungsschritt

Pro Eliminationsschritt ergeben sich folgende Operationen:- n-1 Divisionen- 2(n-1) Multiplikationen- 2(n-1) Additionen

Dieser Algorithmus braucht großenordnungsmaßig also O(n) Operationen.

zu c)

Losungsschritt

mit Spalten-Pivotsuche:

//----------------------------------// Spalten-Pivotsuche//----------------------------------FOR i = 1,...,n-1

pivot = |A[i,i]|IF( |A[i+1,i]| > pivot ) THEN

//-----------------------// Zeilentausch//-----------------------FOR colIdx = i,...,i+3

pivot = A[i,colIdx]A[i,colIdx] = A[i+1,colIdx]

16

A[i+1,colIdx] = pivotENDFORpivot = b[i]b[i] = b[i+1]b[i+1] = pivot

ENDIFfactor = A[i+1,i] / A[i,i]A[i+1,i+1] = A[i+1,i+1] - factor * A[i,i+1]//------------------------------// eliminieren der i+2-ten Spalte// (kann durch Zeilentausch aufgef ullt worden sein)//------------------------------IF (i+2 <= n ) THEN

A[i+1,i+2] = A[i+1,i+2] - factor * A[i,i+2]ENDIFb[i+1] = b[i+1] - factor * b[i]

ENDFOR

Die Anzahl der benotigten Operationen belauft sich hierbei auf:

- n-1 Divisionen

- 2(n-1) + n-2 = 3n-4 Additionen

- 2(n-1) + n-2 = 3n-4 Multiplikationen

Dabei konnte man den Algorithmus noch dahingehend optimieren, dass man die n-2Additionen/Multiplikationen nur ausfuhrt, falls das Element an der Stelle A[i,i+2] != 0ist. Damit wurde die oben genannte Anzahl an Operationen nur im schlechtesten Fallausgefuhrt werden. In jedem Fall kommt bei diesem Algorithmus der Aufwand fur dieSpalten-Pivotsuche hinzu.

Trotz der erhohten Kosten die durch den Zeilentausch enstehen braucht dieser Algo-rithmus großenordnungsmaßig immer (nur) noch O(n) Operationen.

Losungsschritt

mit Zeilen-Pivotsuche:

//----------------------------------// Zeilen-Pivotsuche//----------------------------------FOR i = 1,...,n-1

pivot = |A[i,i]|

17

IF( |A[i,i+1]| > pivot ) THEN//-----------------------// Spaltentausch//-----------------------FOR rowIdx = i,...,i+3

pivot = A[rowIdx,i]A[rowIdx,i] = A[rowIdx,i+1]A[rowIdx,i+1] = pivot

ENDFORpivot = x[i]x[i] = x[i+1]x[i+1] = pivot

ENDIFfactor = A[i+1,i] / A[i,i]A[i+1,i+1] = A[i+1,i+1] - factor * A[i,i+1]b[i+1] = b[i+1] - factor * b[i]//------------------------------// eliminieren der i+2-ten Zeile// (kann durch Spaltentausch aufgef ullt worden sein)//------------------------------IF (i+2 <= n ) THEN

factor = - A[i+1] / A[i,i]A[i+2,i+1] = factor * A[i,i+1]b[i+1] = b[i+1] - factor * b[i]

ENDIFENDFOR

Die Anzahl der benotigten Operationen belauft sich hierbei auf:

- n-1 + n-2 = 2n-3 Divisionen

- 2(n-1) + n-2 = 3n-4 Additionen

- 2(n-1) + 2(n-2) = 4n-6 Multiplikationen

Die Kosten erhohen sich gegenuber dem Gauß-Algorithmus mit Spalten-Pivotsuche (5n-5) auf 9n-13 Operationen.

Trotz der erhohten Kosten die durch den Spaltentausch enstehen braucht dieser Al-gorithmus großenordnungsmaßig immer (nur) noch O(n) Operationen.

18



Gegeben ist ein lineares Gleichungssystem der Form

a1,1 a1,2 0 · · · 0 a1,n

a2,1 a2,2 a2,3 0 · · · 0

0 a3,2. . . . . . . . .

......

. . . . . . . . . . . . 00 · · · 0 an−1,n−2 an−1,n−1 an−1,n

an,1 0 · · · 0 an,n−1 an,n

x1

x2......

xn−1

xn

=

b1

b2......

bn−1

bn

a) Beschreiben Sie, wie sich die Besetztheitsstruktur der Matrix andert, wenn Sie Gauß-

Elimination ohne Pivotsuche durchfuhren.

b) Geben Sie ein Verfahren an, die Eintrage der Matrix so zu speichern, dass im Verlaufder Gauß-Elimination ohne Pivotsuche keine uberflussigen Nullen gespeichert werden.

c) Formulieren Sie das Verfahren der Gauß-Elimination ohne Pivotsuche in einem Pseu-docode zur Losung des obigen Gleichungssystems. Benutzen Sie dabei die in b)definierte Speicherung der Matrix. Schatzen Sie großenordnungsmaßig die Anzahlder anfallenden Rechenoperationen ab.

d) Wie kann sich die Struktur der Matrix andern, wenn Sie Spalten-Pivotsuche durchfuhren?

2.2.2 Losung

zu a)

Losungsschritt

Beim Eliminieren von a2,1 ergibt sich ein neuer Eintrag in der letzten Spalte bei a2,n.Beim Eliminieren von an,1 ergibt sich ein neuer Eintrag bei an,2. Im Verlauf der Gauß-Elimination wandert also in der untersten Zeile ein Eintrag nach rechts, und die rechtesteSpalte wird schrittweise aufgefullt.

zu b)

Losungsschritt

Wir speichern die drei Diagonalen in drei Vektoren, namlich di = ai,i fur i = 1 . . . n, ci =ai+1,i fur i = 1 . . . n−1 und ei = ai,i+1 fur i = 1 . . . n−1.Da wir auf jeden Fall zur Bestim-mung der Losung am Schluss das Dreiecksgleichungssystem auflosen mussen, benotigenwir alle Eintrage in der letzten Spalte, die wir daher ebenfalls in einem eigenen Vektorfi = ai,n fur i = 1 . . . n − 2 speichern (i = n − 1 und j = n liegt im Vektor e und

19

d). Die zusatzlichen Eintrage in der letzten Zeile benotigen wir spater nicht mehr (es seidenn, wir wollen eine LU-Zerlegung berechnen). Daher konnen wir dieses jeweils einzelneElement in einer Zahl α speichern, die jeweils dieses linke untere Element im jeweiligenEliminationsschritt enthalt. (Man konnte sogar den Vektor f einsparen, und die jeweilszu Null gemachten Stellen in c durch die entstehenden Eintrage der letzten Spalte nut-zen).

zu c)

Losungsschritt

FOR i = 1,...,n-1factor = c[i] / d[i]d[i+1] = d[i+1] - factor * e[i]b[i+1] = b[i+1] - factor * b[i]IF( i < n-1 ) THEN

factor = α / d[i]d[n] = d[n] - factor * f[i]b[n] = b[n] - factor * b[i]

ENDIFIF( i < n-2 ) THEN

f[i+1] = -f[i] * (c[i] / d[i])α = -e[i] * ( α / d[i])

ENDIFIF( i = n-2 ) THEN

e[n-1] = e[n-1] - f[i] * (c[i] / d[i])c[n-1] = c[n-1] - e[i] * ( α / d[i])

ENDIFENDFOR

Danach noch Auflosen des Dreiecksgleichungssystems (bidiagonal + letzte Spalte):

x[n] = b[n] / d[n]x[n-1] = (b[n-1] - e[n-1] * x[n]) / d[n-1]FOR i = n-2,...,1

x[i] = (b[i] - f[i] * x[n] - e[i] * x[i+1]) / d[i]ENDFOR

Die Kosten liegen im Bereich O(n) da nur einfache Schleifen der Lange n durchlaufenwerden.

20

zu d)

Losungsschritt

Vernachlassigen wir zunachst die einzelnen Eintrage links unten und rechts oben, sokann es durch Vertauschen zweier Nachbarzeilen passieren, dass oben eine zusatzlichDiagonale auftritt (a1,3, . . . , an−2,n). Dazu kommen auf jeden Fall die letzte Spalte undletzte Zeile wie unter a). Tritt der Fall auf, dass die jeweilige Zeile mit der unterstenZeile vertauscht wird, so werden dadurch in der vorletzten Spalte zusatzliche Eintrageerzeugt (a1,n−1, . . . , an−3,n−1).

21



Gegeben ist das lineare Gleichungssystem in Hessenberg-Form

h1,1 h1,2 · · · · · · h1,n

h2,1 h2,2 · · · · · · h2,n

0. . . . . .

......

. . . . . . . . ....

0 · · · 0 hn,n−1 hn,n

x1

x2......

xn−1

xn

=

b1

b2......

bn−1

bn

a) Formulieren Sie in einem Pseudocode das Verfahren der Gauß-Elimination ohne Pi-

votsuche unter Ausnutzung der Struktur der gegebenen Matrix.

b) Wie viele Operationen benotigen Sie großenordnungsmaßig?

c) Womit ist zu rechnen, wenn Sie Spalten- oder Zeilen-Pivotsuche zulassen?

2.3.2 Losung

zu a)

Losungsschritt

FOR i=1,...,n-1factor = A[i+1,i] / A[i,i]A[i+1,i] = 0FOR j=i+1,...,n

A[i+1,j] = A[i+1,j] - factor * A[i,j]ENDFORb[i+1] = b[i+1] - factor * b[i]

ENDFOR

Durch die gegebene Struktur der Matrix A muss nur eine Zeile pro Eliminationsschrittbearbeitet werden.

22

zu b)

Losungsschritt

Es fallen folgenden Operationen an:- n-1 Divisionen,

n−1∑i=1

i =(n− 1)(n− 2)

2=

n2

2− 3n

2+ 1 Additionen und Multiplikationen

fur die Elimination des Elements an der Stelle A[i+1,i] und noch einmal n-1 Additio-nen und Multiplikationen fur das Element b[i+1] .Da hier der Faktor n2

2 uberwiegt, liegt die Anzahl der Operationen großenordnungsmaßigbei O(n2).

zu c)

Losungsschritt

Fur die Spalten-Pivotsuche andert sich nichts, da hier die Zeile i nur mit der Zeile i+1vertauscht werden kann, da alle anderen Spalteneintrage der Spalte i (beginnend inZeile i ) gleich Null sind. Daher werden dann nur Zeilen gleicher Struktur miteinandervertauscht.

Bei der Zeilen-Pivotsuche kann es nun aber passieren, dass stark besetzte Spalten mitschwach besetzten Spalten vertauscht werden. Dadurch kann es passieren, dass die “fast-schon“-Dreickecksmatrix zerstort wird und dieses durch mehrfaches Subtrahieren einerZeile zu anderen Zeilen in einem Eliminationsschritt wieder ausgeglichen werden muss.Dabei entsteht dann wieder der “standard“ Gauß-Algorithmus mit einer Operationen-anzahl in der Großenordnung von O(n3).

23



Bestimmen Sie die effiziente Speicherung und effiziente Varianten der Gauß-Eliminationbei linearen Gleichungssystemen mit folgender Gestalt:

AX =

∗ ∗∗ ∗∗

∗ ∗∗ ∗

2.4.2 Losung

Losungsschritt

Zur Speicherung werden drei Vektoren benotigt. Die Diagonaleintrage werden in demVektor Diag gespeichert (Diag[i] = ai,i mit i = 1, ..., n). Die Eintrage unterhalbder Diagonalen werden in dem Vektor LowDiag gespeichert (LowDiag[i] = an−i+1,i

mit i = 1, ..., n/2 (wobei n/2 abgerundet). Analog werden die Eintrage oberhalb derDiagonalen in dem Vektor UppDiag gespeichert (UppDiag[i] = ai,n−i+1 mit i =1, ..., n/2 (wobei n/2 abgerundet).

Losungsschritt

FOR i=1,...,n/2factor = LowDiag[i] / Diag[i]Diag[n-i+1] = Diag[n-i+1] - factor * UppDiag[i]b[n-i+1] = b[n-i+1] - factor * b[i]

ENDFOR

24




AN =

∗ ∗∗ ∗ ∗∗ ∗ ∗∗ ∗ ∗∗ ∗

2.5.2 Losung

Losungsschritt

Zur Speicherung werden drei Vektoren benotigt. Die Diagonaleintrage werden in demVektor Diag gespeichert (Diag[i] = ai,i mit i = 1, ..., n). Die Eintrage der linkenSpalte (a1,1 ausgenommen) werden in dem Vektor LeftCol gespeichert (LeftCol[i]= ai+1,1 mit i = 1, ..., n− 1). Die Eintrage der rechten Spalte (an,n ausgenommen) wer-den in dem Vektor RightCol gespeichert (RightCol[i] = ai+1,n mit i = 1, ..., n−1).

Losungsschritt

FOR i=1,...,n-1factor = LeftCol[i] / Diag[i]IF( i+1 < n ) THEN

RightCol[i+1] = RightCol[i+1] - factor * RightCol[i]ELSE

Diag[i+1] = Diag[i+1] - factor * RightCol[i]ENDIFb[i+1] = b[i+1] - factor * b[1]

ENDFOR

25




AZ =

∗ ∗ ∗ ∗ ∗

∗∗

∗∗ ∗ ∗ ∗ ∗

2.6.2 Losung

Tip

Umwandeln der Matrix durch Zeilen und Spaltentausch.

Losungsschritt

Zur Speicherung werden drei Vektoren benotigt. Die Diagonaleintrage werden in demVektor Diag gespeichert (Diag[i] = ai,n−i+1 mit i = 1, ..., n). Die obere Zeile wirdin dem Vektor UppRow gespeichert (UppRow[i] = a1,i mit i = 1, ...n). Die untereZeile wird in dem Vektor LowRow gespeichert (LowRow[i] = an,i mit i = 1, ..., n).Hierbei erleichtert es den spateren Algorithmus, dass die Eintrage a1,n und an,1 doppeltabgespeichert werden.

Um nun mit moglichst wenig Operationen (Additionen, Divisionen etc.) das Gleichungs-system zu losen, wird die Matrix wie folgt umgewandelt:- Umkehren der Diagonalen

AZ =

∗ ∗ ∗ ∗ ∗

∗∗

∗∗ ∗ ∗ ∗ ∗

→

∗ ∗ ∗ ∗ ∗∗∗∗

∗ ∗ ∗ ∗ ∗

- Tauschen der 2. und letzten Zeile

∗ ∗ ∗ ∗ ∗∗∗∗

∗ ∗ ∗ ∗ ∗

→

∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗

∗∗

∗ 0

26

- Tauschen der 2. und letzten Spalte∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗

∗∗

∗ 0

→

∗ ∗ ∗ ∗ ∗∗ ∗ ∗ ∗ ∗

∗∗∗

Nun muss man nur noch ein Vielfaches der ersten Zeilen von der Zweiten Zeile abziehenund es werden dadurch keine Nullen in der Matrix verstort.

Losungsschritt

//------------------------------// Diagonale umkehren//------------------------------FOR i=2,...,n/2

val = Diag[i]Diag[i] = Diag[n-i+1]Diag[n-i+1] = val

ENDFOR//------------------------------// Tausch Zeile 2 mit Zeile n//------------------------------val = Diag[2]Diag[2] = LowRow[2]//------------------------------// Tausch Spalte 2 mit Spalte n//------------------------------Diag[n] = valval = Diag[2]Diag[2] = LowRow[n]LowRow[n] = valval = UppRow[2]UppRow[2] = UppRow[n]UppRow[n] = val//------------------------------// Gauß//------------------------------factor = LowRow[1] / Diag[1]FOR i=2,...,n

LowRow[i] = LowRow[i] - factor * UppRow[i]ENDFOR//------------------------------

27

// Letztes Setzten der Werte//------------------------------Diag[2] = LowRow[2]LowRow[1] = 0

28

3 Interpolation



Bestimmen Sie die Anzahl der Operationen zur Berechnung des interpolierenden Poly-noms p0, . . . , pn(c) an der Stelle c mittels

a) Lagrange-Polynom

b) Neville-Schema

c) Newton-Form des interpolierenden Polynoms

3.1.2 Losung

zu a)

Tip

Aufstellen eines Pseudo-Codes fur die Lagrange-Polynome:

p(x) =n∑

j=0

yjLj(x) mit Lj(x) =n∏

i=0;i6=j

x− xi

xj − xi

Losungsschritt

Ein Pseudo-Code zur Berechnung des Polynoms an der Stelle c mittels Lagrange-Polynomenlautet:

FOR j=0,...,nL = 1FOR i=0,...,n

IF( i != j ) THENL = L * ( c - x[i] ) / ( x[j] - x[i] )

ENDIFENDFORp = p + y[j] * L

ENDFOR

29

Losungsschritt

Durch die ineinander geschachtelte FOR-Schleife benotigen wir hier O(n2) Operationen.

zu b)

Losungsschritt

Ein Pseudo-Code zur Berechnung des Polynoms an der Stelle c mittels des Neville-Schemas lautet:

FOR i=0,...,np[i] = y[i]FOR k=i-1,...,0

p[k] = p[k+1] + ( p[k+1] - p[k] ) * ( c - x[i] ) / x[i] - x[k]ENDFOR

ENDFOR

Losungsschritt


zu c)

Losungsschritt

Ein Pseudo-Code zur Berechnung des Polynoms an der Stelle c mittels der Newton-Formdes Interpolationspolynoms lautet:

//-----------------------------------------------------// Berechnung der dividierten Differenzen://-----------------------------------------------------

FOR i=0,...,np[i] = y[i]FOR k=i-1,...,0

p[k] = p[k+1] + ( p[k+1] - p[k] ) / x[i] - x[k]ENDFOR

ENDFOR

//-----------------------------------------------------

30

// Berechnung des Polynoms://-----------------------------------------------------

p = f[n]FOR j=n-1,...,0

p = p * ( c - x[j] ) + f[j]ENDFOR

Losungsschritt




Wir betrachten die Funktion f(x) = x8. Bestimmen Sie zu f das interpolierende Polynomvom Grad kleiner gleich 6 zu den Stutzstellen -3,-2,-1,0,1,2,3.

3.2.2 Losung

Tip

In der Losung wir der Ansatz uber die Newton-Form des Interpolierenden Polynomsverwendet.

Losungsschritt

Die Stutzstellen zu der Funktion f(x) = x8 lauten:

x0 = (−3, 6561)x1 = (−2, 256)x2 = (−1, 1)x3 = (0, 0)x4 = (1, 1)x5 = (2, 256)x6 = (3, 6561)

31

Unser gesuchtes Polynom (Newton-Form des Interpolierenden Polynoms) hat die Form(nach dem Horner-Schema):

p(x) = (((((f [x0, ..., x6](x− x5) + f [x0, ..., x5])(x− x4) ++f [x0, ...x4])(x− x3) + f [x0, ..., x3])(x− x2) ++f [x0, x1, x2])(x− x1) + f [x0, x1])(x− x0) + f [x0]

Wir mussen nun also die Koeffizienten (dividierte Differenzen) f [x0, ..., xj ], j = 1, ..., 6berechnen.

Losungsschritt

Die Koeffizienten (mit ∗ gekennzeichnet) und die Zwischenergebnisse lauten:

f [x0] = y0 = = 6561 (∗)f [x0, x1] = y1−y0

x1−x0= 256−6561

−2+3 = −6305 (∗)f [x1, x2] = y2−y1

x2−x1= 1−256

−1+2 = −255f [x2, x3] = . . . = . . . = −1f [x3, x4] = . . . = . . . = 1f [x4, x5] = . . . = . . . = 255f [x5, x6] = . . . = . . . = 6305f [x0, x1, x2] = f [x1,x2]−f [x0,x1]

x2−x0= −255+6305

−1+3 = 3025 (∗)f [x1, x2, x3] = . . . = . . . = 127f [x2, x3, x4] = . . . = . . . = 1f [x3, x4, x5] = . . . = . . . = 127f [x4, x5, x6] = . . . = . . . = 3025f [x0, x1, x2, x3] = . . . = . . . = −966 (∗)f [x1, x2, x3, x4] = . . . = . . . = −42f [x2, x3, x4, x5] = . . . = . . . = 42f [x3, x4, x5, x6] = . . . = . . . = 966f [x0, x1, x2, x3, x4] = . . . = . . . = 231 (∗)f [x1, x2, x3, x4, x5] = . . . = . . . = 21f [x2, x3, x4, x5, x6] = . . . = . . . = 231f [x0, x1, x2, x3, x4, x5] = . . . = . . . = −42 (∗)f [x1, x2, x3, x4, x5, x6] = . . . = . . . = 42f [x0, x1, x2, x3, x4, x5, x6] = . . . = . . . = 14 (∗)

Losungsschritt

Einsetzen der Koeffizienten ergibt nun:

p(x) = (((((14 · (x− x5)− 42)(x− x4) ++231)(x− x3)− 966)(x− x2) ++3025)(x− x1)− 6305)(x− x0) + 6561

32

Zuletzt Einsetzen der Stutzstellen:

p(x) = (((((14 · (x− 2)− 42)(x− 1) ++231)x− 966)(x + 1) ++3025)(x + 2)− 6305)(x + 3) + 6561

Unser gesuchtes Polynom lautet also:

p(x) = 14x6 − 49x4 + 36x2



Approximieren Sie die Funktion ld(x) = log2(x).

a) Berechnen Sie das Interpolationspolynom zu ld(x) mit den Stutzstellen 16,32 und 64.

b) Bestimmen Sie die linearen Ausgleichsgrade zu diesem Stutzstellen und und verglei-chen Sie sie mit dem Interpolationspolynom aus a).

3.3.2 Losung

zu a)

Tip

In der Musterlosung wurde der Ansatz mittels Lagrange-Polynomen gewahlt.

Losungsschritt

Die Stutzstellen zu der Funktion f(x) = log2(x) lauten:

x0 = (16, 4)x1 = (32, 5)x2 = (64, 6)

Unser gesuchtes Polynom (Lagrange-Polynome) hat die Form:

p(x) =2∑

j=0

yjLj(x) mit Lj(x) =2∏

i=0;i6=j

x− xi

xj − xi

33

Losungsschritt

Die Lagrange Polynome lauten:

L0(x) = (x−32)(x−64)(16−32)(16−64) = x2−96x+2048

768

L1(x) = (x−16)(x−64)(32−16)(32−64) = −x2−80x+1024

512

L2(x) = (x−16)(x−32)(64−16)(64−32) = x2−48x+512

1536

Losungsschritt

Einsetzen in unser Polynom ergibt:

p(x) = 4 · L0(x) + 5 · L1(x) + 6 · L2(x)

= − 11536

x2 +332

x + 223

zu b)

Tip

Die lineare Ausgleichsgerade g(x) = a · x + b setzt sich aus der linken und der rechtenStutzstelle zusammen.

Losungsschritt

Die lineare Ausgleichsgerade g(x) = a · x + b zu den gegeben Stutzstellen errechnet sichwie folgt:

g(x) =f(x2)− f(x0)

x2 − x0· (x− x0) + f(x0)

=124

x− 23

+ 4

=124

x + 313

Losungsschritt

Fur unsere Stutzstelle x1 erhalt man hier nun:

g(32) =124· 32 + 3

13

= 423

34



Zu den Stutzstellen x0 < x1 < x2 mit bekannten Funktionswerten f(x0), f(x1) und f(x2)soll das Integral

∫ ba f(x)dx naherungsweise bestimmt werden; dabei sei a ≤ x0 < x2 ≤ b.

Beschreiben Sie, wie man mittels eines Polynoms zweiten Grades dieses Integral nahe-rungsweise berechnen kann und geben Sie eine explizite Quadraturregel der Form∫ b

af(x)dx ≈

2∑j=0

wjf(xj).

3.4.2 Losung

Tip

Gewichtung der Stutzstellen mittels Lagrange-Polynomen.

Losungsschritt

Wir suchen hier ein Polynom p(x) zweiten Grades fur das gilt:∫ b

af(x)dx ≈

∫ b

ap(x)dx =

2∑i=0

wjf(xi)

Da wir die Werte fur f(xi), i = 0, 1, 2 bereits geben haben, brauchen wir also nur dieGewichte fur unsere Stutzstellen zu suchen, z.B. mittels Lagrange-Polynome.

Losungsschritt

Durch Einsetzten der Lagrange-Polynome erhalten wir nun unsere Quadraturregel∫ b

af(x)dx ≈

2∑j=0

wjf(xj) =2∑

i=0

f(xi)∫ b

aLi(x)dx

wobei gilt:

L0(x) =(x− x1)(x− x2)

(x0 − x1)(x0 − x2)

L1(x) =(x− x0)(x− x2)

(x1 − x0)(x1 − x2)

L2(x) =(x− x0)(x− x1)

(x2 − x0)(x2 − x1)

35



Gegeben sei eine Integrationsregel mit nur einer Stutzstelle x0 und einem Gewicht α:

α · f(x0) ≈∫ b

af(x) dx.

Bestimmen Sie x0 und α so, dass die Integrationsregel fur Polynome moglichst hohenGrades exakt gilt.

3.5.2 Losung

Tip

f(x) als Polynom 0-ten bzw. 1-ten Grades betrachten.

Losungsschritt

Wir betrachten:

i) f(x) = x0 = 1

ii) f(x) = x1

Losungsschritt

Daraus folgt ∫ b

a1 dx = b− a ⇔ α · 1 = b− a ⇔ α = b− a

Losungsschritt

sowie ∫ b

ax dx =

b2 − a2

2⇔ α · x0 =

b2 − a2

2⇔ x0 =

b + a

2



Bestimmen Sie zu den Stutzstellen x0 = 0, x1 = a, x2 = 1 Gewichte w0, w1, w2 und aso, dass die Integrationsregel∫ 1

0f(x) dx = w0f(x0) + w1f(a) + w2f(1)

fur Polynome moglichst hohen Grades exakt ist.

36

3.6.2 Losung

Tip

Betrachte f(x) als Polynom vom Grad n = 0, 1, 2, 3.

Losungsschritt

Wir betrachten:

i) f(x) = x0 = 1

ii) f(x) = x1

iii) f(x) = x2

iv) f(x) = x3

Daraus folgt:

i)∫ 1

01 dx = 1 = w0 + w1 + w2

ii)∫ b

ax dx =

12

= w1a + w2

iii)∫ b

ax2 dx =

13

= w1a2 + w2

iv)∫ b

ax3 dx =

14

= w1a3 + w2

Losungsschritt

nun ii)− iii):

16

= w1a− w1a2 = w1(a− a2)

⇔ w1 =1

6(a− a2)

und iii)− iv):

112

= w1(a2 − a3) =a(a− a2)6(a− a2)

=a

6

⇔ a =12

37

Losungsschritt

Einsetzen in i) und ii) ergibt dann:

w0 =16, w1 =

23

w2 =16

a =12

38

4 Fourier-Transformation



Zeigen Sie fur j, k ∈ N:

i)∫ π

−πcos(jx) cos(kx) dx = 0 fur j 6= k

ii)∫ π

−πsin(jx) sin(kx) dx = 0 fur j 6= k

iii)∫ π

−πcos(jx) sin(kx) dx = 0∀j, k

4.1.2 Losung

zu i)

Tip

2 cos α cos β = cos(α− β) + cos(α + β)

Losungsschritt ∫ π

−πcos(jx) · cos(kx) dx =

12

∫ π

−π2 cos(jx) · cos(kx) dx =

=12

∫ π

−πcos((j−k)x) + cos((j+k)x) dx =

12

∫ π

−πcos((j−k)x) dx +

12

∫ π

−πcos((j+k)x) dx =

Losungsschritt

Fur j = k gilt:12

∫ π

−πcos(0 · x) dx +

12

∫ π

−πcos(2k · x) dx = π

Fur j 6= k gilt:

12|sin((j − k)x)|π−π +

12|sin((j + k)x)|π−π = 0− 0 = 0

39

zu ii)

Tip

2 sinα sinβ = cos(α− β)− cos(α + β)


−πsin(jx) · sin(kx) dx =

12

∫ π

−π2 sin(jx) · sin(kx) dx =

=12

∫ π

−πcos((j−k)x) − cos((j+k)x) dx =

12

∫ π

−πcos((j−k)x) dx − 1

2

∫ π

−πcos((j+k)x) dx =

Losungsschritt

Fur j = k gilt:12

∫ π

−πcos(0 · x) dx − 1

2

∫ π

−πcos(2k · x) dx = π

Fur j 6= k gilt:

12|sin((j − k)x)|π−π −

12|sin((j + k)x)|π−π = 0− 0 = 0

zu iii)

Tip

2 sinα cos β = sin(α− β) + sin(α + β)


−πcos(jx) · sin(kx) dx =

12

∫ π

−π2 cos(jx) · sin(kx) dx =

=12

∫ π

−πsin((j−k)x) + sin((j+k)x) dx =

12

∫ π

−πsin((j−k)x) dx +

12

∫ π

−πsin((j+k)x) dx =

=12|− cos((j − k)x)|π−π +

12|− cos((j + k)x)|π−π

Losungsschritt

Da cos(−ϕ) = cos(ϕ) gilt ∀j, k ∈ N:

12(− cos((j − k)π) + cos((j − k)π)− cos((j + k)π) + cos((j + k)π)) = 0

40



Sei f eine stuckweise stetige periodische Funktion mit Fourier-Reihe

f(x) =a0

2+∑

(ak cos(kx) + bk sin(kx)).

Zeigen Sie, dass die Fourier-Koeffizienten gegeben sind durch

ak =1π

∫ π

−πf(x) cos(kx) dx und bk =

1π

∫ π

−πf(x) sin(kx) dx

4.2.2 Losung

Tip

∫ π

−πcos(jx) cos(kx) dx = π fur j = ±k und

∫ π

−πcos(jx) sin(kx) dx = 0 ∀j, k ∈ N

Losungsschritt

Beweis von ak:Einsetzen ergibt:

1π

∫ π

−π

[a0

2+∑

(ak cos(kx) + bk sin(kx))]· cos(jx) dx =

=1π

∫ π

−π

a0

2· cos(jx) dx︸︷︷︸=0

+∑

ak

∫ π

−πcos(kx) · cos(jx) dx︸︷︷︸

=π

+∑

bk

∫ π

−πsin(kx) · cos(jx) dx︸︷︷︸

=0

=

=1π

ak · π = ak

Tip

∫ π

−πsin(jx) sin(kx) dx = π fur j = ±k und

∫ π

−πcos(jx) sin(kx) dx = 0 ∀j, k ∈ N

41

Losungsschritt

Beweis von bk:Einsetzen ergibt:

1π

∫ π

−π

[a0

2+∑

(ak cos(kx) + bk sin(kx))]· sin(jx) dx =

=1π

∫ π

−π

a0

2· sin(jx) dx︸︷︷︸=0

+∑

ak

∫ π

−πcos(kx) · sin(jx) dx︸︷︷︸

=0

+∑

bk

∫ π

−πsin(kx) · sin(jx) dx︸︷︷︸

=π

=

=1π

bk · π = bk



Sei n = 3m, also durch drei teilbar. Beschreiben Sie, wie

wj =∑

cke2πijk/n, j = 0, 1, ..., n− 1

in drei Summen der Lange m aufgespalten werden kann. Wie kann man mit dieserAufspaltung die Berechnung der IDFT eines Vektors der Lange n auf die Berechnungvon mehreren IDFT’s kurzerer Vektoren zuruckgefuhrt werden?

4.3.2 Losung

Tip

Zur Losung fur j = 0, ...,m− 1:

- Summe von Bereich k = 0, ..., n− 1 auf Bereich k = 0, ...,m− 1 anpassen

Losungsschritt

wj

n−1∑k=0

ck exp(2πikj

n) =

=n/3−1∑k=0

(c3k exp(

2πi3kj

n) + c3k+1 exp(

2πi(3k + 1)jn

) + c3k+2 exp(2πi(3k + 2)j

n))

=

=m−1∑k=0

(c3k exp(

2πikj

m))

+exp(2πij

3m)

m−1∑k=0

(c3k+1 exp(

2πikj

m))

+exp(4πij

3m)

m−1∑k=0

(c3k+2 exp(

2πikj

m))

fur j = 0, ...,m− 1.

42

Tip

Ubergang von j → m + j

Losungsschritt

Durch Ersetzen von j → m + j erhalt man die zweite Gruppe von Eintragen:

wm+j =∑(

c3k exp(2πik(m + j)

m))

+ . . . =

=∑(

c3k exp(2πikj

m))

+

+exp(2πi/3) exp(2πij

3m)∑(

c3k+1 exp(2πikj

m))

+


3m)∑(

c3k+2 exp(2πikj

m))

Tip

Ubergang von j → 2m + j

Losungsschritt

Durch Ersetzen von j → 2m + j erhalt man die dritte Gruppe von Eintragen:

w2m+j =∑(

c3k exp(2πik(2m + j)

m))

+ . . . =

=∑(

c3k exp(2πikj

m))

+


3m)∑(

c3k+1 exp(2πikj

m))

+


3m)∑(

c3k+2 exp(2πikj

m))

Berechnet man also die IDFT der drei kurzen Vektoren mit Komponenten c3k, c3k+1

und c3k+1, so kann man diese drei sich ergebenden Vektoren, mit passenden Faktorenversehen, zu der gesuchten Losung kombinieren.

43

5 Iterative Verfahren



Zeigen Sie, dass die Iterationxn+1 = cos(xn)

fur alle x0 ∈ R gegen den einzigen Fixpunkt χ, χ = cos(χ) konvergiert.

a) Formulieren Sie ferner ein Newton-Verfahren zur Berechnung von χ. Konvergiertdieses Verfahren ebenfalls fur jeden beliebigen Startwert?

b) Vergleichen Sie die Konvergenzgeschwindigkeit der beiden Interationsverfahren.

5.1.2 Losung

Tip

Betrachte xn+2 = cos(cos(xn)), also nur jeden zweiten Iterationsschritt.

Losungsschritt

Die folgende Grafik zeigt, dass es nur einen Fixpunkt fur x = cos(x) gibt:

44

Wir betrachten h(x) := cos(cos(x)), also nur jeden zweiten Iterationsschritt. Konver-giert dies, so konvergiert auch die ursprungliche Folge. Dann gilt:

|h′(x)| = | sin(cos(x))| · | sin(x)| ≤ sin(1) < 1

⇒ |h(x)− h(y)| = |h′(z)| · |x− y| ≤ sin(1) · |x− y|

mit z als Zwischenstelle. Daraus folgt h kontrahierend und stets konvergent gegen deneindeutigen Fixpunkt. Hieraus folgt wiederum f(x) konvergent.

zu a)

Losungsschritt

Newton liefert:

Φ(x) = x− f(x)f ′(x)

= x +x− cos(x)1 + sin(x)

=x sin(x) + cos(x)

1 + sin(x)

Losungsschritt

Schlechte Konvergenz bzw. keine Konvergenz falls f ′(x0) ≈ 0 bzw. f ′(x0) = 0.

f ′(x) = 1 + sin(x) = 0 ⇔ x =32π + 2kπ

D.h. fur einen Startwert x0 = 32π + 2kπ konvergiert unser Verfahren nicht.

zu b)

Losungsschritt

Da χ 6= 32π + 2kπ gilt:

f ′(χ) = 1 + sin(χ) 6= 0

Somit ist χ eine einfache Nullstelle und das Newton-Verfahren konvergiert quadratisch.

Losungsschritt

f(x) = cos(x) konvergiert offensichtlich linear.



Wir suchen eine einfache Nullstelle χ einer Funktion g(x). Naturlich ist dann χ aucheine Nullstelle von g2(x).

45

a) Formulieren Sie das Newton-Verfahren zur Bestimmung von χ einmal mittels derFunktion g(x) und einmal mittels der Funktion g2(x) (unter Verwendung von g′(x)).

b) Da χ eine einfache Nullstelle ist, konnen wir g(x) = (x − χ)h(x) schreiben mith(χ) 6= 0. Welches der beiden Verfahren konvergiert schneller? Wie ist der Unter-schied zu erklaren?

c) Sei nun χ eine zweifache Nullstelle einer Funktion f(x). Wie kann daher das Newton-Verfahren modifiziert werden, so dass schnelle Konvergenz erreicht wird? Begrundung!

5.2.2 Losung

zu a)

Losungsschritt

xk+1 = xk −g(xk)g′(xk)

Losungsschritt

xk+1 = xk −g2(xk)

(g2(xk))′= xk −

g2(xk)2g(xk)g′(xk)

= xk −12

g(xk)g′(xk)

zu b)

Tip

Konvergenz des Newton-Verfahren bei einfacher bzw. doppelter Nullstelle.

Losungsschritt

Bei einer einfachen Nullstelle hat g2(x) naturlich eine doppelte Nullstelle. Das Newton-Verfahren konvergiert bei einer einfachen Nullstelle quadratisch, bei einer doppeltenNullstelle nur linear.

zu c)

Tip

Betrachtung von√|g(x)|.

46

Losungsschritt

Hat g(x) eine doppelte Nullstelle, so hat√|g(x)| dort eine einfache Nullstelle. Verwende

also das Newton-Verfahren z.B. mit der Wurzel. Dies entspricht der Iteration

xk+1 = xk −√

g(xk)1

2√

g(xk)g′(xk)

= xk − 2g(xk)g′(xk)

Tip

Betrachtung von g′(x).

Losungsschritt

Hat g(x) eine doppelte Nullstelle, so hat g′(x) dort eine einfache Nullstelle. Verwendealso das Newton-Verfahren z.B. mit der Ableitung. Dies entspricht der Iteration

xk+1 = xk −g′(x)g′′(x)



Zur Berechnung von 1/b suchen wir eine Nullstelle χ der Funktion f(x) = 1/x− b, b 6= 0.

a) Formulieren Sie das Newton-Verfahren zur Bestimmung von χ. Fur welche Startwertekonvergiert das Verfahren in einem Schritt?

b) Fur welche b ist das Newton-Verfahren lokal quadratisch Konvergent?

c) Diskutierten Sie die Iteration, die durch die Festlegung Φ(x) = bx2, xk+1 = Φ(x)definiert ist. Wo liegen evtl. Fixpunkte? Ist dieses Verfahren zur Berechnung von 1/bzu empfehlen?

5.3.2 Losung

zu a)

Losungsschritt

xk+1 = xk −f(xk)f ′(xk)

= xk −1/xk − b

−1/x2k

= 2xk − bx2k

47

Tip

Finde Losung zu x1 = 1/b.

Losungsschritt

Konvergenz in einem Schritt, falls gilt:

x1 = 1/b = 2x0 − bx20 ⇔

(bx0 − 1)2 = 0 ⇔

x0 = 1/b

Konvergenz also in einem Schritt wenn der Startwert gleich der gesuchten Losung ist.

zu b)

Tip

Wann ist das Newton-Verfahren quadratisch konvergent?

Losungsschritt

Das Newton-Verfahren ist quadratisch konvergent, falls nur einfache Nullstellen vorlie-gen. Nun gilt:

f ′(x) = − 1x2

alsof ′(1/b) = −b2 6= 0

Somit ist 1/b eine einfache Nullstelle und daher liegt lokal quadratische Konvergenz vor.

zu c)

Tip

Fixpunkt liegt vor, wenn Φ(x) = x.

Losungsschritt

Fixpunkt bei:Φ(x) = x ⇔

x = bx2 ⇔

x = 0 oder x = 1/b

48

Tip

Anstossender/anziehender Fixpunkt?

Losungsschritt

Es gilt:Φ′(x) = 2bx und somit Φ′(1/b) = 2b/b = 2

Daher ist 1/b ein abstossender Fixpunkt. Die Folge xk wird also gegen 0 oder ±∞konvergieren, aber nur fur den exakten Startwert x0 = 1/b auch gegen 1/b. Zudem waremaximal mit linearer Konvergenz zu rechen, das Verfahren ist also nicht geeignet.



Wir betrachten die Iterationsfunktion Φ(x) = (x2 + 1)/(2x). Welche Fixpunkte hat Φ?Sind diese Fixpunkte abstossend oder anziehend?Zeigen Sie dass fur einen Startwert x0 gilt:

|xk+1 − 1| ≤ 12xk

(xk − 1)2

Was folgt daraus fur die Konvergenzordnung dieses Verfahrens?Man bestimme ein Intervall I so, dass fur x ∈ I die Funktion Φ kontrahierend ist undeine Abbildung Φ : I → I darstellt.

5.4.2 Losung

Tip

Fixpunkt liegt vor, wenn Φ(x) = x.

Losungsschritt

Φ(x) = x ⇔x = (x2 + 1)/(2x) ⇔x2 + 1 = 2x2 ⇔x = ±1

Somit sind die Fixpunkte x1,2 = ±1.Weiter gilt:

Φ′(x) =12− 1

x2

Φ(x1,2) = 0

Daher sind x1,2 anziehende Fixpunkte.

49

Losungsschritt

xk+1 − 1 = 12(xk + 1

xk− 1− 1) =

= 12(xk − 1− 1

xk(xk − 1)) =

= 12xk

(xk − 1)(xk − 1) =

= (xk−1)2

2xk

Somit quadratische Konvergenz, da 12xk

fur den Fall der Konvergenz beschrankt bleibt.

Losungsschritt

z.B. I = [1, 2]; dann ist 0 ≤ Φ′(x) ≤ 1/2 in I (nach a)), also kontrahierend. Ausserdemgilt fur x ∈ I: Φ(x) ≥ 1 und Φ(x) ist naher an 1 als x, insgesamt also Φ(x) ∈ I.



Das Heron-Verfahren ist ein Verfahren, um die Quadratwurzel einer beliebigen positivenZahl mit festem Aufwand auf Maschinengenauigkeit zu berechnen. Es basiert auf derBestimmung der Nullstelle der Funktion f(x) = x2 − a mittels des Newton-Verfahrens.

a) Bestimmen Sie zunachst mittels linearer Interpolation fur a ∈ [1, 4) einen gutenNaherungswert fur

√a. Verwenden Sie die Funktion

s(x) =124

(8x + 17)

als Naherung an die Wurzelfunktion. Schatzen Sie den relativen Fehler des gefundenenNaherungswertes ab (also die Große von (s(x)−

√x)/√

x).

b) Formulieren Sie das Newton-Verfahren zur Bestimmung der Nullstelle√

a von f(x).Wie entwickelt sich der Fehler wahrend der Iteration? Wie viele Iterationen sindnotig, um

√a bis auf Maschinengenauigkeit zu berechnen, falls a ∈ [1, 4) ist?

c) Wie kann das obige Verfahren angewandt werden, falls a /∈ [1, 4) gilt? Dazu schreibenwir a in der Form a = α22p mit passendem p und α ∈ [1, 4) .

50

5.5.2 Losung

zu a)

Tip

Fur die lineare Interpolation L(x) gilt:

x0 < x < x1, y0 = f(x0), y1 = f(x1), h = x1 − x0

⇒ L(x) = y0 +y1 − y0

h(x− x0)

Losungsschritt

Hier gilt:a0 < a < a1 mit a0 = 1, a1 = 4 ⇒ h = 3

f(a0) =2524

= y0

f(a1) =4924

= y1

Somit ist L(x):

L(a) =2524

+4925 −

2524

3(a− 1)

=2524

+13(a− 1)

=13a +

1724

Losungsschritt

Fur den relativen Fehler des Naherungswertes gilt:

frel =L(a)−

√a√

a

wobei

L(a) = ((13a)(1 + ε1) +

1724

)(1 + ε2)

.=13aε1 + (

13a +

1724

)ε2 +13a +

1724

51

Somit gilt fur den relativen Fehler:

frel =13aε1 + (1

3a + 1724)ε2 + 1

3a + 1724 −

13a− 17

2413a + 17

24

=a

a + 178

ε1 + ε2

zu b)

Losungsschritt

Es gilt:

f(x) = x2 − a ⇒ Φ(x) = x− f(x)f ′(x)

= x− x2 − a

x=

x2 + a

2x

Tip

Fur den relativen Fehler im k-ten Schritt gilt:

frelk =xk −

√a√

a

Einsetzten der Heron-Rekursion(Newton-Verfahren im (k-1)-ten Schritt) fur xk.

Losungsschritt

Fur den relativen Fehler im k-ten Schritt gilt:

frelk =xk −

√a√

a

Setzen wir die vorher ermittelte Newton-Form fur xk ein, so erhalten wir:

frelk =

x2k−1+a

xk−1−√

a√

a=

1√a

(x2

k−1 + a

2xk−1−√

a

)

=1

2√

axk−1

(x2

k−1 − 2√

axk−1 + a)

=√

a

2xk−1

(xk−1 −

√a√

a

)2

=1

2(

xk−1−√

a√a

+ 1)(frelk−1

)2 =1

2(1 + frelk−1)(frelk−1

)2

Tip

Abschatzen einer oberen Schranke fur frelk , z.B. frelk ≤12(frelk−1

)2 und anschließendesAuflosen nach k.

52

Losungsschritt

Wir schatzen unseren relativen Fehler im k-ten Schritt ab:

frelk ≤ 12(frelk−1

)2 ≤ 12

(12(frelk−2

)2)2

≤ . . . ≤ 2−12−2 · · · 2−2k−2(frel1)

2k−1

= 2−12−2 · · · 2−2k−22−2k−1

(1 + frel0)−2k−1

(frel0)2k

= 2−(2k−1)(1 + frel0)−2k−1

(frel0)2k

, k ≥ 1

Nun mussen wir noch nach k auflosen:(12

)2k−1( 11 + frel0

)2k−1

(frel0)2k ≤ εmasch

2 ·

12·

√1

1 + frel0

· frel0︸︷︷︸=:α

2k

≤ εmasch

(α)2k

≤ εmasch

22k · log(α) ≤ log

(εmasch

2

)2k ≥

log( εmasch2 )

log(α)

k ≥ log(

log( εmasch2 )− log(α)log(2)

)

zu c)

Losungsschritt

Hierzu passen wir einfach s(x) und unser gefundenes Newton-Verfahren an und benutzens0(=s(α)) als Startwert.

s(x) =124

(8x + 17) → s(α) =124

(8α + 17)

xk+1 =x2

k + a

2xk→ sk+1 =

s2k + α

2sk, k = 0, ..., N − 1

wobei N die Anzahl der Iterationsschritte ist.

Losungsschritt

Die gesuchte Losung fur√

a ist dann: sN · 2p

53



Sei f eine zweimal stetig stetig differenzierbare Funktion. Wir wollen mittels Newton-Verfahren eine Nullstelle unbekannter Ordnung bestimmen, unter Verwendung der Funk-tion h(x) := f(x)/f ′(x). Was lasst sich uber die Konvergenz des Newton-Verfahrens,angewandt auf die Funktion h, sagen?

5.6.2 Losung

Tip

Schreiben von f(x) als f(x) = (x− x0)k · g(x)

Losungsschritt

Wir schreiben f(x) als f(x) = (x− x0)k · g(x) mit x0 als Nullstelle der Ordnung k.

⇒ f ′(x) = k(x− x0)k−1 · g(x) + (x− x0)k · g′(x)

Losungsschritt

Somit folgt fur h(x):

h(x) =f(x)f ′(x)

=(x− x0)k · g(x)

k(x− x0)k−1 · g(x) + k(x− x0)k · g(x)

=g(x)

k·g(x)x−x0

+ g′(x)

= (x− x0) ·g(x)

k · g(x) + (x− x0) · g′(x)

Losungsschritt

Somit ist x0 also eine einfache Nullstelle und das Newton-Verfahren konvergiert quadra-tisch.

54

6 Differentialgleichungen



Gegeben ist ein Anfangswertproblem der Form y′(x) = Φ(y, x), y(a) = y0. Bei aqui-distanter Schrittweite h betrachten wir die Iterationsvorschrift

yk+1 = yk +h

2(Φ(yk, xk) + Φ(yk+1, xk+1)) .

a) Aus welcher Quadraturregel ergibt sich dieses Verfahren? Man beschreibe den Zu-sammenhang.

b) Zeigen Sie, wie man aus der obigen Beziehung bei bekannten Werten von xk, yk undh den neuen Wert yk+1 berechnen kann. Um welche Art von Problem handelt es sichdabei? Welche Art von Verfahren kann man benutzen? Beschreiben Sie die Startbe-dingungen eines solchen Verfahrens.Geben Sie einen Algorithmus an zu Losung des AWPs mit naherungsweiser Berech-nung von y(b) fur ein b > a.

6.1.2 Losung

zu a)

Losungsschritt

Dieses Verfahren stammt aus der Trapezregel, und zwar∫ xk+1

xk

y′dx = yk+1 − yk ≈xk+1 − xk

2· (y′k+1 + y′k) =

h

2(Φ(yk, xk) + Φ(yk+1, xk+1))

zu b)

Losungsschritt

Das Problem besteht hierin, dass der neue Wert yk+1 nicht explizit gegeben ist, sondernnur implizit, also erst noch durch ein zusatzliches Verfahren aus der definierten Gleichungberechnet werden muss. Hier bieten sich zum einen eine einfache Fixpunktiteration oder

55

zum anderen das Newton-Verfahren an.Fixpunktiteration: Betrachte die Funktion

f(y) = yk +h

2(Φ(yk, xk) + Φ(y, xk+1))

und bestimme den Fixpunkt y = f(y). Da |df/dy| fur kleine Werte von h auch kleinwird, ist f kontrahierend.Newton-Verfahren: Betrachte die Funktion

f(y) = yk +h

2(Φ(yk, xk) + Φ(y, xk+1))− y

und suche die Nullstelle.

Losungsschritt

Als Startwert kann man jeweils das alte yk benutzen.Konvergiert die erzeugte Folge y gegen eine Zahl y, so ist y ein Fixpunkt bzw. eineNullstelle, und wir konnen yk+1 = y setzen.



Gegeben ist das Anfangswertproblem

y′(x) = ϕ(y, x) = x, x0 = 0, y(x0) = 0.

Wir benutzen die aquidistante Einteilung x0 = 0, x1 = h, . . . , xn = nh = b.

a) Bestimmen Sie die exakte Losung y(x) und die Naherrungswerte yj ≈ y(xj), j =1, . . . , n, die durch das (Vorwarts-)Euler-Verfahren gegeben werden.

b) Wie groß ist der lokale Diskretisierungsfehler |y1 − y(x1)|? Wie groß ist der globaleFehler |yn − y(b)|?

6.2.2 Losung

zu a)

Tip

Trennung der Variablen.

56

Losungsschritt

Hier liegt eine Gleichung vom Typ

y′(x) = f(x)g(y)

mit g(y) = 1 und f(x) = x vor. Mittels Trennung der Variablen erhalten wir:

1g(y)dy = f(x)dx ⇔

dy = xdx

Durch Integration jeder Seite (unbestimmt) erhalten wir:

G(y) =∫

dy = y, F (x) =∫

xdx =x2

2

Mit der Allgemeinen Losung

G(y)− F (x) = c, c ∈ R

konnen wir die exakte Losung fur c0 = G(y0) − F (x0) berechnen. Hier also c0 = 0,⇒unsere Losung lautet:

y =x2

2

Losungsschritt

Das Euler-Verfahren liefert

y1 = y0 + h(φ(y0, x0) = 0 + hx0 = 0y2 = y1 + h(φ(y1, x1) = 0 + hx1 = h2

y3 = x2 + h(φ(y2, x2) = h2 + 2h2 = 3h2

. . .

oder allgemein

yk = h2 ·k−1∑j=1

j = h2 (k − 1)k2

57

zu b)

Losungsschritt

lokaler Fehler:

y(x1)− y1 =x2

1

2− y1 =

h2

2− 0 =

h2

2=

b2

2n2

globaler Fehler:

y(b)− yn = y(xn)− yn =b2

2− h2(n− 1)n

2=

b2

n− (b2/n2)(n2 − n)

2=

(bh)2

=b2

2n.

Der lokale Fehler ist also O(h2) und der globale Fehler O(h).



Gegeben ist das Anfangswertproblem(uv

)′=(−1000 α

α −1

)(uv

), x0 =, u(x0) = 1, v(x0) = 1.

Wir benutzen die aquidistante Einteilung x0 = 0, x1 = x0 + h, . . . , xn = x0 + nh = b,also h = b/n.

a) Formulieren Sie das (Vorwarts-)Euler-Verfahren zur Bestimmung von Naherungslosun-gen uj ≈ u(xj) und vj ≈ v(xj).

Im Folgenden betrachten wir den Spezialfall α = 0.

b) Bestimmen Sie die exakten Losungen u(x) und v(x). Man gebe eine einfache Formelfur die Naherungswerte uj ≈ u(xj) und vj ≈ v(xj) an, die durch das(Vorwarts-)Euler-Verfahren gegeben werden, in Abhangigkeit von h.

b) Wie groß darf h gewahlt werden, so dass uj und vj beide fur j → ∞ das richtigeVerhalten zeigen? Wie groß darf h gewahlt werden, so dass vj fur j →∞ das richtigeVerhalten zeigt?

6.3.2 Losung

zu a)

Losungsschritt(uk+1

vk+1

)=(

uk

vk

)+ h

(−1000 α

α −1

)(uj

vj

)=(

(1− 1000h)uj + αvj

αuj + (1− h)vj

)fur j = 1, . . . , n und u0 = v0 = 1.

58

zu b)

Tip

Homogene lineare Differentialgleichung 1. Ordnung.

Losungsschritt

Uns liegt eine lineare Differentialgleichung 1. Ordnung, also y′(x) = a(x)y, vor. DieLosung hierzu lautet:

y(x) = ceA(x), c ∈ R mit A(x) =∫

a(x)dx

In unseren Fall lauten die Losungen, mit u(x0) = v(x0) = 1 :

u(x) = e−1000x, v(x) = e−x

Losungsschritt

Das Euler-Verfahren liefert fur u(x):

u1 = (1− 100hu0) = (1− 1000)hu2 = (1− 1000h)(1− 1000h) = (1− 1000)2h. . .

Insgesamt also:

uj = (1− 1000h)j und analog vj = (1− h)j

zu c)

Losungsschritt

Es gilt: u(x) = v(x) = 0 fur x →∞. Daher sollten die Naherungslosungen dasselbe Ver-halten zeigen. Das stimmt aber fur uj(x) und vj(x) nur gemeinsam, falls 0 < h < 1/1000(dann auch monoton fallendes Verhalten), oder 0 < h < 2/1000 (dann alternierend ge-gen 0).Betrachten wir dagegen nur die Folge vj , so ist diese Bedingung schon fur h < 1, bzw.h < 2, erfullt.

59

Documents

Interdisziplinäres Projekt - in.tum.de fileInterdisziplinäres Projekt im Rahmen der Diplomhauptprüfung f ür Informatiker im Nebenfach Mathematik an der Technischen Universit