Kurzskript zur Vorlesung

Numerische Mathematik I

gehalten von Prof. Paola Pozzi PhD (WS 2011/12)

Ich verwende das Kurzskript vom Professor G.Dziuk (http://portal.uni-freiburg.de/aam/abtlg/ls/lsdz),Universitat Freiburg.

Weitere Literatur:

1. J. Stoer, R. Bulirsch: Numerische Mathematik I. Springer 2007.

2. P. Deuflhard, A. Hohmann: Numerische Mathematik I. De Gruyter 2008.

3. G. Hammerlin, K. H. Hoffmann: Numerische Mathematik. Springer 1990.

4. E. Suli, D. Mayers: An Introduction to Numerical Analysis, Cambridge Univ. Press2006.

5. L.N. Trefethen, D. Bau: Numerical Linear Algebra, Siam 1997.

6. R.Rannacher: Einfuhrung in die Numerische Mathematik, Vorlesungsskript,(http://numerik.iwr.uni-heidelberg.de)

7. G. Plonka-Hoch: Numerische Mathematik I, Vorlesungsskript WS 2009/10,(http://num.math.uni-goettingen.de/plonka/)

Korrekturen bitte anpaola.pozzi@uni-due.de

1

1 Funktionalanalytische Grundlagen

1.1 Metrik

Definition 1.1 Sei X 6= ∅. Eine Abbildung d : X × X → R heißt Metrik, falls fur allex1, x2, x3 ∈ X gilt:

(M1) d(x1, x2) = 0 ⇐⇒ x1 = x2 (Definitheit)(M2) d(x1, x2) ≤ d(x1, x3) + d(x3, x2) (Dreiecksungleichung)(M3) d(x1, x2) = d(x2, x1) (Symmetrie).

(X, d) heißt dann metrischer Raum. Man beachte, daß keine Addition in X erklart ist.

Folgerung 1.2 d(x1, x2) ≥ 0 (x1, x2 ∈ X).

Beispiele 1.3

a) X = [0,∞), d(x1, x2) = |x1 − x2| ist metrischer Raum.

b) X = Rn = x = (x1, . . . , xn) | xj ∈ R, j = 1, . . . , n ist mit d(x, y) = maxj=1,...n

|xj − yj |ein metrischer Raum.

c) X = C0([a, b],R), d(f, g) = |f(a)− g(a)| beschreibt keinen metrischen Raum.

d) X = C0([a, b],R) = f : [a, b]→ R |f ist in [a, b] stetig ist mit

d(f, g) = maxx∈[a,b]

|f(x)− g(x)|

ein metrischer Raum, wobei naturlich f = g :⇔ f(x) = g(x) fur alle x ∈ [a, b] sei.

e) X = C0([a, b],R) ist mit

d(f, g) = (

b∫a

(f(x)− g(x))2dx)1/2

ein metrischer Raum. Auch X = f ∈ C0([a, b],R) | f ≥ 15 auf [a, b] ist mit d einmetrischer Raum.

Hilfssatz 1.4 (Cauchy-Schwarzsche Ungleichung)

b∫a

|f(x)g(x)|dx ≤ (

b∫a

f(x)2dx)1/2(

b∫a

g(x)2dx)1/2

Definition 1.5 Ein metrischer Raum (X, d) heißt vollstandig , falls jede Cauchyfolge in Xkonvergiert, d.h. ist (xn)n∈N ⊂ X, d(xn, xm) → 0 (n,m → ∞), so gibt es ein x ∈ X, so dassd(xn, x)→ 0 (n→∞), d. h. xn → x (n→∞).

Beispiele 1.6 a, b und d sind vollstandig. e ist nicht vollstandig.

2

Satz 1.7 (Banachscher Fixpunktsatz)Sei X ein vollstandiger metrischer Raum und f : X → X eine kontraktive Abbildung (Kon-traktion), d.h. es gibt ein q ∈ [0, 1), so dass fur alle x1, x2 ∈ X gilt:

d(f(x1), f(x2)) ≤ q d(x1, x2).

Dann gibt es genau ein x∗ ∈ X, so dass

f(x∗) = x∗

ist, d.h. x∗ ist Fixpunkt von f .

Beispiel 1.8 Division durch Multiplikation.

Beispiel 1.9 Zur Notwendigkeit der Kontraktionsbedingung

Folgerung 1.10 Es sei f eine kontraktive Abbildung eines vollstandigen metrischen RaumsX in sich. Dann konvergiert das Verfahren

xn+1 = f(xn) (n = 0, 1, ...)

fur jede Wahl von x0 ∈ X gegen den Fixpunkt x∗ ∈ X. Es gelten die a-priori-Abschatzung

d(x∗, xn) ≤ qn

1− qd(x1, x0)

und die a-posteriori-Abschatzung

d(x∗, xn) ≤ q

1− qd(xn, xn−1)

Der Fehler nimmt so ab:

d(x∗, xn) ≤ qd(x∗, xn−1) (n ∈ N).

Folgerung 1.11 Ist X ⊂ R ein abgeschlossenes Intervall und f : X → X differenzierbarmit supx∈X |f ′(x)| ≤ q < 1, so besitzt f einen Fixpunkt in X.

Beispiel 1.12 Picard-Iteration zur Losung der Differentialgleichung

u′(t) = 1 + u(t)2 (t ∈ (0, T )),

mit Anfangswert u(0) = 0.

1.2 Norm

Definition 1.13 Sei X ein linearer Raum (Vektorraum). Eine Abbildung ‖·‖ : X → R heißtNorm , wenn fur alle x, x1, x2 ∈ X und alle α ∈ K(K = R oder C) gilt:

(N1) ‖x‖ = 0 ⇒ x = 0(N2) ‖αx‖ = |α| ‖x‖(N3) ‖x1 + x2‖ ≤ ‖x1‖+ ‖x2‖

(X, ‖ · ‖) heißt normierter Raum. Ist X mit der Metrik d(x1, x2) := ‖x1 − x2‖ einvollstandiger metrischer Raum, so heißt (X, ‖ · ‖) Banachraum.

3

Folgerung 1.14 ‖ · ‖ ≥ 0, ‖0‖ = 0, | ‖x1‖ − ‖x2‖ | ≤ ‖x1 − x2‖.

Beispiel 1.15 X = Rn oder Cn, (x+ y)i = xi + yi, (αx)i = αxi, (i = 1, ..., n).

‖x‖p := (n∑i=1

|xi|p)1p fur p ∈ [1,∞),

‖x‖∞ := max|xi| | i = 1, ..., n

sind Normen auf Rn oder Cn.

Hilfssatz 1.16 (Youngsche Ungleichung) Seien a, b ≥ 0; p ∈ (1,∞), 1p + 1

p′ = 1. Danngilt:

a b ≤ 1

pap +

1

p′bp′.

Hilfssatz 1.17 (Holder-Ungleichung) Seien x, y ∈ Cn; p > 1, 1p + 1

p′ = 1. Dann gilt:

n∑i=1

|xiyi| ≤ (

n∑i=1

|xi|p)1p (

n∑i=1

|yi|p′)

1p′ .

1.3 Lineare Operatoren und Matrixnormen

Definition 1.18 Es seien X1, X2 normierte Raume. Eine Abbildung T : X1 → X2 heißtlinearer Operator, falls fur alle x1, x2 ∈ X,α1, α2 ∈ K(= R oder C) gilt

T (α1x1 + α2x2) = α1T (x1) + α2T (x2).

(Schreibweise: T (x) = Tx.) Ein linearer Operator heißt beschrankt, falls

∃ c ≥ 0 ∀x ∈ X1 : ‖Tx‖X2 ≤ c‖x‖X1 .

Die wichtigsten linearen Operatoren sind die Matrizen.

Beispiel 1.19 X1 = Rn, X2 = Rm,

Rn 3 x 7→ y = Tx ∈ Rm, mit yj =

n∑i=1

Tjixi, j = 1, ...m.

Dabei seien Tji ∈ R gegeben.

Beispiel 1.20 X1 = C2([a, b],R), X2 = C0([a, b],R), ‖f‖X1 = max[a,b] |f | + max[a,b] |f ′| +max[a,b] |f ′′|, ‖f‖X2 = max[a,b] |f |, (Tf)(x) := f ′′(x) (x ∈ [a, b]).

Satz 1.21 X1 und X2 seinen normierte Raume. Ist T : X1 → X2 linearer Operator, so sindaquivalent:i) T ist stetig,ii) T ist stetig in 0,iii) T ist beschrankt.

4

Definition 1.22 Es seien X1 und X2 normierte Raume. Wir definieren

L(X1, X2) := T : X1 → X2 | T linear und beschrankt.

Die Zahl

‖T‖L(X1,X2) = ‖T‖ := supx∈X1\0

‖Tx‖X2

‖x‖X1

heißt (Operator-)Norm von T . Ist T eine Matrix, so heißt ‖T‖ die zu X1 und X2 gehorendeMatrixnorm.Fur uns sind insbesondere die Matrixnormen wichtig. Wenn man eine gegebene m×n-Matrixals linearen Operator: Rn → Rm auffasst, erhalt man zu zwei Normen auf Rn und Rm genaueine zugehorige Matrixnorm.

Beispiel 1.23 Sind Rn,Rm mit ‖ · ‖2 normiert und ist T ∈ L(Rn,Rm) eine m×n-Matrix, sonennt man die zugehorige Matrixnorm Spektralnorm. Die Spektralnorm einer Matrix T istdurch

‖T‖2,2 = ‖T‖σ = großter Eigenwert von (T t)T1/2.

gegeben. Ist T symmetrisch, so ist

‖T‖2,2 = max|λ|∣∣∣λ ist Eigenwert von T.

Hilfssatz 1.24 L(X1, X2) ist mit der Operatornorm ein normierter Raum. Falls X2 ein Ba-nachraum ist, ist auch L(X1, X2) ein Banachraum. Sind T ∈ L(X1, X2), S ∈ L(X2, X3), soist ST ∈ L(X1, X3), und es gilt

‖ST‖L(X1,X3) ≤ ‖S‖L(X2,X3)‖T‖L(X1,X2).

Addition und Multiplikation mit Skalaren sind punktweise erklart: (T1 + T2)x := T1x+ T2x,(αT )x := αTx.

1.4 Zahlendarstellung auf Rechnern

Ganze Zahlen (integer) werden durch

z = ±z1...zm, zi ∈ 0, 1, ..., 9, z1 6= 0

dargestellt. Eine n-stellige Gleitpunktzahl x zur Basis b hat die Form

x = ±(0.z1...zn)b · bE

mit zi ∈ 0, 1, ..., b− 1, m ≤ E ≤M und z1 6= 0 fur x 6= 0 (normalisiert). Dabei ist

(0.z1...zn)b = z1b−1 + z2b

−2 + ...+ znb−n .

Rundungsregel (n-stellig): Der Zahl

x = ±0.z1...znzn+1zn+2... · 10E

5

mit z1 6= 0 ordnet man die Zahl

fl(x) =

±0.z1...zn · 10E (0 ≤ zn+1 ≤ 4)

±(0.z1...zn + 0. 0 . . . 0︸ ︷︷ ︸n− 1 Nullen

1) · 10E (5 ≤ zn+1 ≤ 9)

zu. Die Zahl ε := 5 · 10−n heißt Maschinengenauigkeit.Auf einem Rechner verwendet man also Operationen, fur die Assoziativ- und Distributivge-setze nicht gelten, namlich

x⊕ y := fl(x+ y), x y := fl(x− y), x y := fl(x · y), x y := fl(x/y) .

Wir verwenden folgende Konvention fur die n-stellige Rechnung: Jede Operation wird zunachstberechnet (ohne Rundung) und danach auf n Stellen mit fl gerundet. Außerdem werten wirFormeln jeweils von links nach rechts gemaß Klammerung aus.

Beispiel 1.25 1) Es seien n = 3 und a = 15.6 = 0.156e2, b = 15.7 = 0.157e2. Dann ist(a− b)2 = 0.01. Aber man erhalt (a a) (2 (a b))⊕ (b b) = −1.0.2) Es seien n = 3 und a = 0.651 = 0.651e0, b = 0.653 = 0.653e0. Dann ist b⊕ [(a b) 2] =0.652 aber (a⊕ b) 2 = 0.650e0.

2 Die numerische Losung linearer Gleichungssysteme

2.1 Kondition von Matrizen

Definition 2.1 Sei T eine regulare Matrix und ‖ · ‖ eine Matrixnorm. Dann heißt

κ(T ) := ‖T‖‖T−1‖

die Kondition der Matrix T (bezuglich der Matrixnorm).

Beispiel 2.2

T =

(1.2969 0.86480.2161 0.1441

)‖T‖∞,∞ = 2.1617, ‖T−1‖∞,∞ = 1.513 · 108, κ∞,∞(T ) = 3.2706521 · 108.

Beispiel 2.3 Fur die N ×N -Matrix

T =

1 0 0 . . . 0 01 1 0 . . . 0 01 0 1 . . . 0 0

. . .1 0 0 . . . 1 01 0 0 . . . 0 1

ist κ∞,∞(T ) = 4. Dagegen ist κ1,1(T ) = n2.

6

Satz 2.4 Sei T eine regulare N ×N -Matrix und ‖ · ‖ eine Norm auf RN . δT sei eine Matrixmit ‖T−1‖ ‖δT‖ < 1. Sei weiter b ∈ RN , b 6= 0 und δb ∈ RN . Dann ist die Matrix T + δTebenfalls regular und fur die Losungen x und x+ δx von

Tx = b, (T + δT )(x+ δx) = b+ δb

gilt die folgende Abschatzung des relativen Fehlers ‖δx‖/‖x‖:

‖δx‖‖x‖

≤ κ(T )

‖δb‖‖b‖

+1 + κ(T )‖δb‖‖b‖

1− κ(T )‖δT‖‖T‖

‖δT‖‖T‖

.

Beispiel 2.5 Fur die tridiagonale (N − 1)× (N − 1)-Matrix

T =

2 −1 0 . . . 0 0−1 2 −1 . . . 0 0

0 −1 2 . . . 0 0. . .

0 0 0 . . . 2 −10 0 0 . . . −1 2

ist

κ2,2(T ) =4

π2N2 +O(1), N →∞.

2.2 Gauß-Elimination und LU-Zerlegung

Lemma 2.6 Es sei T eine regulare n × n-Matrix mit oberer Dreiecksgestalt, d. h. Tjk = 0fur j > k. Dann ist die Losung von Tx = b durch

xi =1

Tii

(bi −

n∑k=i+1

Tikxk

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

gegeben.

Programm 2.7Fur i = n, . . . , 1xi := bi

Fur k = n, . . . , i+ 1xi := xi − TikxkEnde

xi := xi/TiiEnde

Beispiel 2.8 4× 4-Gleichungssystem mit dem Gauß-Algorithmus losen.

7

Satz 2.9 (Gauß-Elimination) Es sei T ∈ Rn×n mit detT 6= 0, b ∈ Rn. Ausserdem seien

die im folgenden auftretenden Zahlen T(j)jj 6= 0 (j = 1, ..., n). Dann liefert das Verfahren

T (1) = T, b(1) = b

Fur r = 1, . . . , n− 1 sei

Lir = T(r)ir /T

(r)rr (i = r + 1, . . . , n)

T(r+1)ij =

T

(r)ij − LirT

(r)rj (i, j = r + 1, ..., n)

Lir (i = r + 1, . . . , n; j = r)

T(r)ij (i, j sonst).

b(r+1)i =

b(r)i − Lirb

(r)r (i = r + 1, ..., n)

b(r)i (i = 1, ..., r)

die Losung x von Tx = b gemaß

xn = b(n)n /T (n)

nn

xi = (b(n)i −

n∑j=i+1

T(n)ij xj)/T

(n)ii (i = n− 1, . . . , 1).

Folgerung 2.10 (LU-Zerlegung) Durch

Uij =

T

(n)ij (j ≥ i)

0 sonst, Lij =

1 (i = j)

T(n)ij (j < i)

0 sonst

, (i, j = 1, . . . , n)

ist eine LU-Zerlegung der Matrix T gegeben:

T = LU.

Programm 2.11 (LU-Zerlegung einfach)

Fur r = 1, . . . , n− 1Falls |Trr| < ε, dann stoppe und melde Fehler

Fur i = r + 1, . . . , nTir := Tir/Trr

Fur k = r + 1, . . . , nTik := Tik − Tir ∗ TrkEnde

EndeEnde

8

Hat man eine Zerlegung T = LU berechnet, so lasst sich die Losung von Tx = b in zweiSchritten berechnen:

y = L−1b, x = U−1y,

das heißt

yi = bi −i−1∑j=1

Lijyj (i = 1, . . . , n), xi = (yi −n∑

j=i+1

Uijxj)/Uii (i = n, . . . , 1)

Beispiel 2.12 fur eine regulare Matrix, die keine LU-Zerlegung besitzt: T =

(0 11 0

).

Satz 2.13 Es sei T eine regulare n×n-Matrix. Dann gibt es Permutationsmatrizen P un Q,so dass der Gaußalgorithmus auf

(P−1TQ−1)Qx = P−1b

anwendbar ist, d. h. dass

(P−1TQ−1)(r)rr 6= 0 (r = 1, . . . , n)

ist. Eine Permutationsmatrix enthalt ausser Nullen in jeder Zeile und jeder Spalte genau eineEins. (Ohne Beweis).

Beispiel 2.14 Spalten-Pivotierung.

Beispiel 2.15 dafur, dass eine bessere Strategie notwendig ist.

Definition 2.16 Eine n× n-Matrix T heißt zeilenweise aquilibriert, wenn gilt:

n∑k=1

|Tik| = 1 (i = 1, . . . , n).

Algorithmus 2.17 (Gauß-Elimination mit Spaltenpivotierung)

1. Fur i = 1, . . . , n berechne di = 1/∑n

k=1 |Tik| und setze T (1) = T .2. Fur r = 1, . . . , n− 1

a. bestimme einen Zeilenindex i = ir so, dass |dirT(r)ir,r| = max

i=r,...,n|diT (r)

ir | ist.

b. Vertausche die Zeilen r und ir des Gleichungssystems.c. Fuhre fur die so geanderte Matrix T (r) den Eliminationsschritt gemaß Satz 2.9 aus.

Rechenaufwand beim Gauß-Algorithmus: 23n

3 + 0(n2) flops (floating point operations).

9

2.3 Spezielle lineare Gleichungssysteme

Definition 2.18 Fur eine Matrix T ∈ Rn×n heisst

Tm := (Tij)i,j=1,...,m (m = 1, . . . , n)

m-te Hauptminore.

Satz 2.19 (Cholesky-Zerlegung) Sei A ∈ Rn×n symmetrisch und positiv definit. Danngibt es eine untere Dreiecksmatrix G ∈ Rn×n so, dass

A = GGt

gilt. Diese Zerlegung heisst Cholesky-Zerlegung.

Beispiel 2.20 A =

1 2 12 5 21 2 10

= GGt mit G =

1 0 02 1 01 0 3

.

2.4 Die klassischen Interationsverfahren

2.4.1 Voruberlegungen zur Konvergenz

Wir werden Iterationsverfahren der Form

x(m+1) = x(m) − S−1Tx(m) + S−1b, (m = 0, 1, . . .)

mit einer geeignet zu wahlenden regularen Matrix S untersuchen.Solche Verfahren beruhen auf der Umformung

Tx = b⇔ Sx+ (T − S)x = b⇔ x = (I − S−1T )x+ S−1b.

Definition 2.21 Das Spektrum S(T ) einer n×n-Matrix ist die Menge aller Eigenwerte vonT , d.h.

S(T ) := λ ∈ C | det(T − λI) = 0.

Der Spektralradius ist die Zahl

ρ(T ) := max|λ| | λ ∈ S(T ).

Satz 2.22 T ∈ L(Rn,Rn). Dann gilt

ρ(T ) ≤ ‖T‖,

wenn ‖ · ‖ eine beliebige Matrixnorm ist.

Satz 2.23ρ(T ) = lim

m→∞‖Tm‖

1m .

10

Satz 2.24 Es seien S und T regulare n × n-Matrizen in Rn. Dann konvergiert das Iterati-onsverfahren

x(m+1) = (I − S−1T )x(m) + S−1b (m = 0, 1, ...)

fur jede Wahl des Startwerts x(0) ∈ Rn gegen die Losung von Tx = b genau dann, wenn

ρ(I − S−1T ) < 1.

Folgerung 2.25 Ist ‖I − S−1T‖ < 1 fur irgendeine Matrixnorm, so konvergiert das Iterati-onsverfahren aus Satz 2.24.

Folgerung 2.26 Fur das Iterationsverfahren aus Satz 2.24 gilt:

supx∗ 6=x(0)

lim supm→∞

m

√‖x(m) − x∗‖‖x(0) − x∗‖

= ρ(I − S−1T ),

wobei Tx∗ = b sei.

2.4.2 Jacobi-Verfahren und Gauß-Seidel-Verfahren

Standardzerlegung der (im Folgenden stets regularen) Matrix T

T = D + L+ U,

D =

T11 0. . .

0 Tnn

,

L =

0 0

T21. . .

.... . .

. . .

Tn1 . . . Tn,n−1 0

, U =

0 T12 . . . T1n

. . .. . .. . . Tn−1,n

0 0

.

Satz 2.27 Sei T eine n×n-Matrix mit Tii 6= 0 (i = 1, ..., n). Dann konvergiert das Gesamt-schrittverfahren (Jacobi-Verfahren)

x(m+1)i =

1

Tii(−

n∑j=1j 6=i

Ti,jx(m)j + bi) (i = 1, ..., n)

genau dann, wenn ρ(D−1(L+ U)) < 1 ist. Hier ist S = D gewahlt.

Beispiel 2.28 T=tridi(-1,2,-1) (aus Beispiel 2.5).

11

Satz 2.29 Sei T eine n× n-Matrix mit

|Tii| >n∑k=1k 6=i

|Tik| (i = 1, ..., n) (starkes Zeilensummenkriterium)

oder

|Tkk| >n∑i=1i6=k

|Tik| (k = 1, ..., n) (starkes Spaltensummenkriterium).

Dann konvergiert das Gesamtschrittverfahren.

Satz 2.30 Sei T eine n× n-Matrix mit Tii 6= 0 (i = 1, . . . , n). Dann konvergiert das Einzel-schrittverfahren (Gauß-Seidel-Verfahren)

x(m+1)i =

1

Tii(−

i−1∑k=1

Tikx(m+1)k −

n∑k=i+1

Tikx(m)k + bi) (i = 1, ..., n).

genau dann, wenn ρ((D + L)−1U) < 1 ist. Hier wurde S = D + L gewahlt.

Definition 2.31 Eine Matrix A ∈ Cn×n, A = (aij)i,j=1...n heisst zerlegbar, wenn es nichtleereTeilmengen N1 und N2 der Indexmenge N := 1, 2, . . . , n gibt mit den Eigenschaften

(a) N1 ∩N2 = ∅(b) N1 ∪N2 = N

(c) aij = 0 fur alle i ∈ N1 und j ∈ N2.

Eine Matrix, die nicht zerlegbar ist, heisst unzerlegbar.

Beispiel 2.32 (a) Die Matrix

A =

a11 . . . a1k 0 . . . 0...

......

...ak1 . . . akk 0 . . . 0ak+1,1 . . . ak+1,k ak+1,k+1 . . . ak+1,n

......

......

an1 . . . ank an,k+1 . . . ann

ist zerlegbar: hier sind N1 = 1, 2, . . . , k und N2 = k + 1, . . . , n.(b) Eine (n × n)-Matrix A mit nicht verschwindenden Nebendiagonalelementen ak,k+1 undak+1,k, 1 ≤ k ≤ n− 1, ist unzerlegbar.

Satz 2.33 Es sei Tii 6= 0 (i = 1, ..., n) und

|Tii| ≥n∑j=1j 6=i

|Tij | (i = 1, ..., n),

wobei es ein i gebe, so dass Ungleichheit besteht. Außerdem sei T unzerlegbar. Dann konver-gieren Einzelschrittverfahren und Gesamtschrittverfahren (fur jeden Startwert).

12

Beispiel 2.34 Einzelschrittverfahren und Gesamtschrittverfahren konvergieren fur T=tridi(−1, 2,−1).

Beispiel 2.35 dafur, dass das Gesamtschrittverfahren konvergieren kann, ohne dass das Ein-zelschrittverfahren konvergiert.

Satz 2.36 Es sei T reell, symmetrisch und positiv definit. Dann konvergiert das Einzel-schrittverfahren.

2.4.3 Das SOR-Verfahren

Satz 2.37 (SOR-Verfahren) Fur eine regulare (n × n)-Matrix T mit Tii 6= 0 konvergiertdas SOR-Verfahren mit Relaxationsparameter ω

x(m+1)i = (1− ω)x

(m)i + ω

1

Tii

− i−1∑j=1

Tijx(m+1)j −

n∑j=i+1

Tijx(m)j + bi

genau dann, wenn ρ((D + ωL)−1((1− ω)D − ωU)) < 1 ist.

Im folgenden verwenden wir

J(ω) = (D + ωL)−1((1− ω)D − ωU),

wobei wir voraussetzen, dass diese Matrix wohldefiniert ist.

Satz 2.38 Sei T ∈ Rn×n symmetrisch und positiv definit. Dann gilt

ρ(J(ω)) < 1,

falls ω ∈ (0, 2) ist.

Satz 2.39 (Kahan) Fur jede Matrix T gilt

ρ(J(ω)) ≥ |ω − 1|,

falls J(ω) existiert. Das bedeutet, dass dann aus ρ(J(ω)) < 1 folgt ω ∈ (0, 2).

Beispiel 2.40 Standardmatrix T = tridi (−1, 2,−1), h = 1n . J bezeichne die jeweilige Itera-

tionsmatrix des Verfahrens. Fur das Gesamtschrittverfahren gilt fur den Spektralradius derIterationsmatrix JGSV

ρ(JGSV ) = cos(πh) = 1− π2

2h2 +O(h4) (h→ 0).

Fur das Einzelschrittverfahren erhalt man

ρ(JESV ) = ρ(JGSV )2 = cos2(πh) = 1− π2h2 +O(h4) (h→ 0).

Mit optimalem Parameter ω∗ = 2

1+√

1−µ2, µ = cos(πh) gilt fur das SOR-Verfahren

ρ(JSOR) =1− sin(πh)

1 + sin(πh)= 1− 2πh+O(h2) (h→ 0).

13

Beispiel 2.41 (Die Laplace-Matrix) Bei einer Diskretisierung des Problems u ∈ C0(G)∩C2(G), G = (0, 1)× (0, 1), bei gegebenem f ∈ C0(G),

−∆u = f in G, u = 0 auf ∂G,

entsteht das lineare Gleichungssystem Tu = b zur Bestimmung einer Approximation von u.Dabei ist

u = (u11, . . . , un1, . . . , u1n, . . . , unn)t

und mit h = 1n+1 ,

b = h2(f11, . . . , fn,1, . . . , f1,n, . . . , fn,n)t.

Die Matrix T lasst sich wie folgt beschreiben:

T =

A B 0B A

. . .. . .

. . .

0. . .

. . . BB A

, A =

4 −1 0−1 4 −1

. . .. . .

. . .. . .

. . . −10 −1 4

, B =

−1 0. . .

0 −1

.

3 Ausgleichsrechnung

Beispiel 3.1 Gewicht eines Neugeborenes.

Problem: bei gegeben Messdaten (ti, yi), (i = 1, . . . ,m), suche nach Koeffizienten α0, . . . , αndes Polynoms

pn(t) =

n∑ν=0

ανtν , (m > n+ 1),

so dass pn “moglichst gut” durch die Punkte (ti, yi) verlauft. Genauer: aus pn(ti) = yi furi = 1, . . . ,m entsteht ein uberbestimmtes lineares Gleichungssystem Aα = y, wobei

A :=

1 t1 t21 . . . tn11 t2 t22 . . . tn2...

...1 tm t2m . . . tnm

∈ Rm×(n+1), y =

y1...ym

, α =

α0...αn

;

gesucht ist α ∈ Rn+1, so dass ‖Aα− y‖22 minimiert wird.

Satz 3.2 Das lineare Auslgleichsproblem

‖Aα− y‖22 7−→ min !

besitzt stets eine Losung. Falls A maximalen Rang besitzt (also rg(A) = n+1), ist die Losungeindeutig bestimmt und es gilt:

α = ((AT )A)−1AT y.

Beispiel 3.3 Polynomial data fitting.

14

4 Die numerische Losung von Eigenwertproblemen

Beispiel 4.1 dafur, dass die Nullstellenberechnung bei Polynomen ein schlecht konditionier-tes Problem ist.

4.1 Vektoriteration

Beispiel 4.2 Idee der Vektoriteration.

Satz 4.3 Sei T eine diagonalisierbare n×n-Matrix mit Eigenwerten λ1, . . . , λn und zugehori-gen normierten Eigenvektoren t1, . . . , tn. Ist λn = |λn|eiϕ, dominanter Eigenwert, das heißt

ist |λn| > |λj | (j 6= n), und ist x(0) =n∑j=i

αjtj mit αn 6= 0, so konvergiert die Folge (x(m))m∈N,

x(m) = Tx(m−1), x(m) =x(m)

‖x(m)‖

(m = 1, 2, . . .), in folgendem Sinn:

e−imϕx(m) → αn|αn|

tn (m→∞).

Außerdem gilt

x(m+1)i0

x(m)i0

→ λn (m→∞)

fur den Fall, dass die i0-te Komponente des Vektors tn ungleich Null ist.

Bemerkung: Beachte, dass ein dominanter Eigenwert immer reell ist.

Folgerung 4.4 Sei T eine diagonalisierbare n × n-Matrix mit Eigenwerten λ1, . . . , λn undzugehorigen normierten Eigenvektoren t1, . . . , tn. Ist 0 < |λ1| < |λ2| ≤ . . . ≤ |λn|, λ1 =

|λ1|eiϕ, und ist x(0) =n∑j=i

αjtj mit α1 6= 0, so konvergiert die Folge der inversen Vektoriteration

x(m) = T−1x(m−1), x(m) =x(m)

‖x(m)‖

(m = 1, 2, . . .) in folgendem Sinn:

eimϕx(m) → α1

|α1|t1 (m→∞).

Außerdem gilt

x(m+1)io

x(m)io

→ 1

λ1(m→∞)

fur den Fall, dass die i0-te Komponente des Vektors t1 ungleich Null ist.

Beispiel 4.5 Inverse Verktoriteration.

15

Satz 4.6 (Satz von Gerschgorin) Sei T ∈ K (K = R oder C) und λ ein beliebiger Eigen-wert von T . Dann gilt:

λ ∈n⋃i=1

Ki, wobei Ki :=z ∈ C : |z − Tii| ≤

n∑j=1j 6=1

|Tij |.

Beispiel 4.7 Gerschgorin Kreise.

4.2 Das QR-Verfahren

Lemma 4.8 Die Kondition einer Matrix T ∈ Rn×n bezuglich der Spektralnorm andert sichnicht bei Multiplikation mit einer orthogonalen Matrix.

Definition 4.9 Sei x ∈ Rn \ 0. Eine Matrix der Form

Hij(x) = δij − 2xixj|x|2

(i, j = 1, . . . , n)

heißt Householdermatrix. (Hier ist | · | ist die Euklidische Norm.)

Lemma 4.10 Sei x ∈ Rn \ 0, H(x) Householdermatrix. Dann gilt: H ist symmetrisch undH2 = I. Sind x, y ∈ Rn \ 0 mit x 6= y und |x| = |y|, so gilt:

H(±(x− y))x = y.

Satz 4.11 (QR-Zerlegung) Eine regulare Matrix T ∈ Rn×n lasst sich mit Hilfe von n − 1Householdertransformationen (Multiplikation mit Householdermatrizen) auf die Form

T = QR

bringen, wobei QQt = QtQ = I gilt und R eine obere Dreiecksmatrix ist. Es gibt Househol-dermatrizen H(j), (j = 1, . . . , n− 1), so dass T = QR mit

Q = H(1) · · ·H(n−1) und R = H(n−1) · · ·H(1)T

ist.

Beispiel 4.12 QR-Zerlegung einer (3× 3)-Matrix.

Lemma 4.13 Sei T ∈ Rn×n eine regulare Matrix. Dann existiert eine eindeutig bestimmteQ ∈ Rn×n mit der Eigenschaft QtQ = I und eine eindeutig bestimmte obere DreiecksmatrixR ∈ Rn×n mit positiven Diagonalelementen Rii > 0, i = 1, . . . , n, so dass T = QR.

Satz 4.14 (QR-Verfahren) Sei T = WDW−1 = W diag (λ1, . . . , λn)W−1, die LU -ZerlegungW−1 = LW−1UW−1 existiere, es sei |λ1| > · · · > |λn| > 0. Dann gilt fur die durch dasVerfahren

T (1) := T

T (j) = Q(j)R(j)

T (j+1) := R(j)Q(j)

erzeugten Matrizen T (j) = (T(j)ik )i,k=1,...,n :

limj→∞

T(j)kk : k = 1, . . . , n = λ1, . . . , λn.

16

Lemma 4.15 Es seien A(j) ∈ Rn×n, j ∈ N, regulare Matrizen mit limj→∞A(j) = I und

A(j) = Q(j)R(j) zugehorige QR-Zerlegungen. Dann gilt:

limj→∞

Q(j) = I = limj→∞

R(j).

5 Nichtlineare Gleichungen

5.1 Voruberlegungen

Beispiel 5.1 Finde alle x = (x1, x2) ∈ R2, so dass

x21 + 4x2

2 − 1 = 0, 4x21 − x2

2 − 1 = 0.

Beispiel 5.2 Bestimme alle x ∈ R mit x sin 1x = 0.

Satz 5.3 Sei Ω ⊂ Rn offen, beschrankt, konvex, und sei J ∈ C1(Ω, Ω) mit

M = maxx∈Ω||J ′(x)|| < 1,

wobei J ′(x)ij =∂Ji∂xj

(x); i, j = 1, . . . , n ist. Dann konvergiert das Verfahren

x(m+1) = J(x(m)) (m ∈ N0)

fur jede Wahl von x(0) ∈ Ω gegen den einzigen Fixpunkt x∗ ∈ Ω von J in Ω:

limm→∞

x(m) = x∗, J(x∗) = x∗.

Außerdem gilt:‖x(m) − x∗‖ ≤ M

1−M ‖x(m) − x(m−1)‖,

‖x(m) − x∗‖ ≤ Mm

1−M ‖x(1) − x(0)‖.

5.2 Das Newtonverfahren

Das Newtonverfahren zur Losung des nichtlinearen Gleichungssystems T (x) = 0 lautet

x(m+1) = x(m) − T ′(x(m))−1T (x(m)) (m = 0, 1, . . .).

Beispiel 5.4 T (x) = x− e−x, x ∈ R.

Beispiel 5.5 T (x) = arctg x, x ∈ R.

Satz 5.6 Die Funktion f ∈ C2([a, b]) habe im Innern des Intervalls [a, b] ein Nullstelle z undes sei

m := min[a,b]|f ′(x)| > 0, M := max

[a,b]|f ′′(x)|.

Sei ρ so gewahlt, dass

q :=M

2mρ < 1, Bρ(z) = x ∈ R : |x− z| ≤ ρ ⊆ [a, b].

17

Dann sind fur jeden Startpukt x(0) ∈ Bρ(z) die Newton-Iterierten x(m) ∈ Bρ(z) definiert undkovergieren gegen die Nullstelle z. Dabei gelten:

|x(m) − z| ≤ 2m

Mq2m ,

|x(m) − z| ≤ M

2m|x(m) − x(m−1)|2, (m ∈ N).

Satz 5.7 (Newton-Verfahren in Rn) Satz zitiert aus: Berger, “‘Nonlinearity and functio-nal analysis”(Theorem 3.1.16).

Programm 5.8 (Newtonverfahren)x := x(0), y := T (x),Fur m = 1, 2 . . .

berechne T ′(x),lose T ′(x)z = −y,x := x+ z,y := T (x),falls |y| < ε, stoppe,

Ende.

Definition 5.9 Ein Iterationsverfahren besitzt (mindestens) die Konvergenzordnung p ≥ 1,falls die von ihm erzeugte Folge (x(m))m∈N so gegen den Grenzwert x∗ konvergiert, dass

lim supm→∞

|x(m+1) − x∗||x(m) − x∗|p

= c

mit einem c ∈ [0,∞) fur p > 1 und c ∈ [0, 1) fur p = 1 gilt.

Folgerung 5.10 Das Iterationsverfahren aus Satz 5.3 hat die Konvergenzordnung 1. DasNewtonverfahren aus Satz 5.6 besitzt die Konvergenzordnung 2.

5.3 Eindimensionale Nullstellensuche

Programm 5.11 (Bisektion)

while (b-a >= epsilon)

x = 0.5*(a + b);

Tx = T(a)*T(x);

if (Tx == 0)

break;

else

if (Tx > 0)

a = x;

else

b = x;

18

Satz 5.12 (Bisektion) Sei I = [a, b] und T ∈ C0(I,R) erfulle T (a)T (b) < 0. Fur gegebenesε > 0 liefert der obige Algorithmus entweder eine Nullstelle x∗ von T oder ein Intervall derLange kleiner oder gleich ε, in dem eine Nullstelle x∗ von T liegt. Bezeichnet x(m) das x ausdem m-ten Interationsschritt, so gilt:

|x∗ − x(m)| ≤ 1

2m(b− a).

Satz 5.13 (Sekantenverfahren) Die Funktion T ∈ C2([a, b]) habe im Intervall (a, b) eineNullstelle x∗. Sei

0 <1

A= min

[a,b]|T ′|, K = max

[a,b]|T ′′|.

Sei ρ > 0 so, dass q = 12AKρ < 1 ist. Dann konvergiert das Sekantenverfahren

x(m+1) = x(m) − x(m) − x(m−1)

T (x(m))− T (x(m−1))T (x(m)) (m ∈ N)

fur Startwerte x(0), x(1) ∈ Bρ(x∗) \ x∗, x(0) 6= x(1), und es gilt die Abschatzung

|x(m) − x∗| ≤2

AKqam

mit den Fibonaccizahlen am+1 = am + am−1, a0 = a1 = 1.

Bemerkung: Das Sekantenverfahren besitzt (mindestens) die Konvergenzordnung p = 12(√

5+1).

5.4 Minimierungsverfahren und gedampftes Newtonverfahren

Lemma 5.14 Es sei Ω ⊂ Rn offen und x∗ ∈ Ω. Es gebe eine reellwertige Funktion F mitF ∈ C1(Ω,R) und T = F ′ in Ω, das heißt

Tj(x1, . . . , xn) =∂F

∂xj(x1, . . . , xn).

Dann gilt:F (x∗) = inf

x∈ΩF (x) ⇒ T (x∗) = 0.

Bemerkung. Der Gradient F ′(x0) ∈ Rn \ 0 zeigt in Richtung des großten Anstiegs derFunktion F im Punkt x0.

Algorithmus 5.15 (Methode des steilsten Abstiegs) Sei x(0) ∈ Rn gegeben. Fur m =0, 1, 2 . . .: Berechne

d(m) = −F ′(x(m))t.

Ist d(m) = 0, so stoppe. Sonst bestimme t(m) ∈ [0,∞), so dass

F (x(m) + t(m)d(m)) = infs∈[0,∞)

F (x(m) + sd(m)).

Setze dannx(m+1) = x(m) + t(m)d(m).

19

Satz 5.16 Es sei F ∈ C1(Rn,R) und x(0) ∈ Rn gegeben. Die Menge

L(x(0)) = x ∈ Rn|F (x) ≤ F (x(0))

sei beschrankt. Der Algorithmus 5.15 breche nicht nach endlich vielen Schritten ab.Dann gilt: Die Folge (F (x(m)))m∈N ist konvergent, die Folge (x(m))m∈N ist beschrankt, undfur jeden Haufungspunkt x∗ der Folge (x(m))m∈N gilt F ′(x∗) = 0.

Beispiel 5.17 (a) F (x) = 12(x2

1 + x22), (b) F (x) = 1

2(x21 − x2

2).

Bemerkung zur Motivation/Herleitung des gedampften Newtonverfahrens.

6 Approximation

6.1 Approximation durch trigonometrische Polynome

Definition 6.1 Fur ak, bk ∈ R und N ∈ N0 heißt

TN (x) =a0

2+

N∑k=1

(ak cos kx+ bk sin kx)

trigonometrisches Polynom (vom Grad kleiner oder gleich N). Mit XN bezeichnen wir denVektorraum der trigonometrischen Polynome vom Grad kleiner oder gleich N .

Beispiel 6.2 sin2(x), cos2(x), sin(x) cos(x).

Hilfssatz 6.32π∫0

cos jx cos kx dx =

0 (j 6= k)2π (j = k = 0)π (j = k > 0)

,

2π∫0

sin jx sin kx dx =

0 (j 6= k)π (j = k > 0)

,

2π∫0

sin jx cos kx dx = 0 fur j, k ∈ N.

Hilfssatz 6.4 Durch 1√2π, 1√

πcos kx, 1√

πsin kx| k ∈ 1, . . . , N ist eine Basis von XN ge-

geben.

Hilfssatz 6.5 Auf X = C0([0, 2π]) ist durch ‖f‖L2(0,2π) =(∫ 2π

0 f(x)2 dx) 1

2eine Norm defi-

niert.

Satz 6.6 Die beste Approximation bezuglich der L2(0, 2π)-Norm an eine Funktion f ∈ Xdurch ein trigonometrisches Polynom fN ∈ XN ist durch

fN (x) =a0

2+

N∑k=1

(ak cos kx+ bk sin kx)

20

mit

ak =1

π

2π∫0

f(y) cos ky dy, bk =1

π

2π∫0

f(y) sin ky dy (k = 0, . . . , N)

gegeben. Es gilt also:

‖f − fN‖L2(0,2π) = infTN∈XN

‖f − TN‖L2(0,2π).

Folgerung 6.7 ∫ 2π

0(f(x)− fN (x))2 dx =

∫ 2π

0f(x)2 dx−

∫ 2π

0fN (x)2 dx

Folgerung 6.8

a20

2+∞∑k=1

(a2k + b2k

)≤ 1

π

∫ 2π

0f(x)2 dx

Hilfssatz 6.9 Fur α ∈ R gilt

eiα = cosα+ i sinα, e−iα = cosα− i sinα.

Lemma 6.10 Komplexe Form der trigonometrischen Polynome:

fN (x) =a0

2+

N∑k=1

(ak cos kx+ bk sin kx) =N∑

k=−Ncke

ikx

mit

ck =1

2(ak − ibk) =

1

2π

∫ 2π

0f(x)e−ikx dx.

Beispiel 6.11

6.2 Hilbertraume

Definition 6.12 Es sei X ein Vektorraum uber K. Eine Abbildung (·, ·) : X ×X → K heißtSkalarprodukt auf X, falls fur alle x, y, z ∈ X und alle α ∈ K gilt:

(S1) (x, y) = (y, x)(S2) (αx, y) = α(x, y)(S3) (x, y + z) = (x, y) + (x, z)(S4) (x, x) ≥ 0(S5) (x, x) = 0 ⇐⇒ x = 0.

(X, (·, ·)) heißt Pra-Hilbertraum. Er heißt Hilbertraum, wenn X bezuglich ‖ · ‖ =√

(·, ·)vollstandig ist.

21

Lemma 6.13 In einem Pra-Hilbertraum gilt die Cauchy-Schwarzsche Ungleichung

|(x, y)| ≤√

(x, x)√

(y, y).

Lemma 6.14 Auf einem Pra-Hilbertraum ist durch ‖x‖ =√

(x, x) eine Norm definiert.

Hilfssatz 6.15 Im Pra-Hilbertraum gilt die Parallelogrammregel

‖x+ y‖2 + ‖x− y‖2 = 2(‖x‖2 + ‖y‖2

).

Satz 6.16 (Projektionssatz) Es sei X ein Pra-Hilbertraum und U ⊂ X ein linearer Teil-raum, der vollstandig ist. Dann gibt es zu jedem x ∈ X genau ein p ∈ U , so dass

‖x− p‖ = infu∈U‖x− u‖

gilt. Es ist fur alle u ∈ URe (x− p, u) = 0.

Letztere Bedingung ist auch hinreichend dafur, dass p ein Minimum ist.

6.3 Approximation im Hilbertraum

Definition 6.17 Es sei X ein normierter Raum, U ⊂ X eine nicht leere Teilmenge. Außer-dem sei f ∈ X gegeben. Dann heißt g ∈ U eine beste Approximation (Bestapproximierende)an f bezuglich U , wenn

‖f − g‖ = infu∈U‖f − u‖

gilt, d. h. g ∈ U und fur alle u ∈ U ist ‖f − g‖ ≤ ‖f − u‖. Die Zahl

d(f, U) = infu∈U‖f − u‖

nennt man Abstand des Elements f von U .

Satz 6.18 Ist U ein n–dimensionaler Teilraum des Pra-Hilbertraums X mit Basis u1, . . . , un,so ist g ∈ U ,

g =

n∑j=1

αjuj ,

beste Approximation an f ∈ X (bezuglich U) genau dann, wenn die Koeffizienten α1, . . . , αnden Normalgleichungen

n∑j=1

(uj , uk) αj = (f, uk) (k = 1, . . . , n)

genugen. Dieses lineare Gleichungssystem ist eindeutig losbar.

Beispiel 6.19

X = C0([0, 2π],C), (f, g) =

∫ 2π

0f(x)g(x) dx, U =

N∑k=−N

ckeikx| ck ∈ C, k = 1, . . . , N

.

Mit Satz 6.18 folgt das Resultat von Satz 6.6/Lemma 6.10.

22

Beispiel 6.20 Beste Approximation von ex auf dem Intervall [0, 1] durch Polynome n-tenGrades.

Definition 6.21 Eine Teilmenge U ⊂ X eines Pra-Hilbertraums X heißt Orthonormalsy-stem (ONS), falls fur alle u, v ∈ U gilt:

(u, v) = 0 u 6= v und ‖u‖ = 1.

Beispiel 6.22 a) In X = C0([0, 2π],R), (f, g) =∫ 2π

0 f(x)g(x) dx ist fur N ∈ N die Menge

U = 1√

2π,

1√π

cos jx,1√π

sin jx∣∣∣ j ∈ 1, . . . , N

ein Orthonormalsystem.b) In X = C0([0, 2π],C), (f, g) =

∫ 2π0 f(x)g(x) dx ist fur M ∈ N0 die Menge

U = 1√

2πei jx

∣∣∣ j ∈ −M, . . . ,M

ein Orthonormalsystem.

Lemma 6.23 Fur N ∈ N sei xm = 2πN m (m = 0, . . . , N − 1).

X = f : x0, . . . , xN−1 → C, (f, g) =N−1∑m=0

f(xm)g(xm)

ist ein Pra-Hilbertraum. Fur N ≥ 2M + 1 ist

U =( 1√

Nei kxm

)m=0,...,N−1

∣∣∣ k ∈ −M, . . . ,M

ein Orthonormalsystem in X.

Beispiel 6.24 Legendre-Polynome.

Satz 6.25 Sei U ein n-dimensionaler linearer Teilraum eines Pra-Hilbertraums X, und dieBasis u1, . . . , un von U bilde ein Orthonormalsystem in X. Dann ist die Bestapproximierendeg ∈ U an f ∈ X durch

g =n∑k=1

(f, uk) uk

gegeben, und es gilt

d(f, U)2 = ‖f‖2 −n∑k=1

| (f, uk) |2.

Beispiel 6.26

23

Satz 6.27 f sei auf [0, 2π] stuckweise stetig differenzierbar, d. h. es gibt eine Einteilung0 ≤ x1 < x2 < · · · < xM < 2π, so dass f ∈ C1([0, 2π) \ x1, . . . , xM) ist und die Grenzwertef(xk ± 0), f ′(xk ± 0), f(2π − 0), f ′(2π − 0) existieren. f sei 2π-periodisch auf R fortgesetzt.Dann konvergiert die f zugeordnete Fourierreihe

(Ff)(x) =a0

2+

∞∑k=1

(ak cos kx+ bk sin kx) =

∞∑k=−∞

ckei kx,

(ak, bk siehe Satz 6.6, ck siehe Lemma 6.10) punktweise auf R gegen die gemittelte Funktion

f(x) =1

2(f(x+ 0) + f(x− 0)) x ∈ R.

6.4 Die schnelle Fouriertransformation

6.4.1 Diskrete Fourierapproximation

Satz 6.28 Es sei f ∈ Cr(R) fur ein r ≥ 2 und 2π-periodisch. Mit den Großen

ck =1

2π

∫ 2π

0f(y)e−i ky dy, c

(N)k =

1

N

N−1∑l=0

f(xl)e−i kxl , xl =

2π

Nl

gilt dann:

c(N)k =

∑j∈Z, j−k∈NZ

cj

und

|ck − c(N)k | ≤ c(r, f)

1

N rfur |k| ≤ N

2.

Satz 6.29 (Trigonometrische Interpolation) Fur das trigonometrische Polynom

p(x) =N−1∑j=0

βjeijx

giltp(xk) = fk (k = 0, . . . , N − 1)

fur xk = 2πkN und fk ∈ C genau dann wenn

βj =1

N

N−1∑k=0

fke−ijxk (j = 0, . . . , N − 1).

Definition 6.30 Die Abbildung T : CN → CN , die durch

w = Tz, wk =1√N

N−1∑j=0

e−ijk2πN zj (k = 0, . . . , N − 1)

definiert ist, heißt diskrete Fouriertransformation N -ter Ordnung. Zur Abkurzung schreiben

wir ζN = e−2πiN . Also ist

wk =1√N

N−1∑j=0

ζjkN zj .

24

Satz 6.31 Die Abbildung T : CN → CN ist linear und isometrisch,

‖Tx‖ = ‖x‖,

und die Inverse von T ist durch ihre Adjungierte gegeben:

T−1 = T ∗ = T t.

‖x‖ =(∑N

j=1 |xj |2) 1

2ist die euklidische Norm in CN .

6.4.2 Schnelle Fouriertransformation

Lemma 6.32 Sei N = 2n und ζN = e−2πiN . Dann lassen sich die Komponenten der diskreten

Fouriertransformation w = Tz wie folgt berechnen. Fur l = 0, . . . , n− 1 ist

w2l = 1√N

n−1∑j=0

ζ ljn zgj , zgj = zj + zj+n,

w2l+1 = 1√N

n−1∑j=0

ζ ljn zuj , zuj = ζj2n(zj − zj+n).

Die Berechnung der wk kann also auf die Berechnung zweier gleicher Koeffizienten der halbenOrdnung n = N

2 reduziert werden. Ist N = 2m, so kann man dieses Vorgehen iterieren.

Beispiel 6.33 Schnelle Fouriertransformation vierter Ordnung.wσ(0)

wσ(1)

wσ(2)

wσ(3)

=1

2

1 1 0 01 ζ2 0 00 0 1 10 0 1 ζ2

1 0 1 00 1 0 11 0 −1 00 ζ4 0 −ζ4

z0

z1

z2

z3

Dabei ist σ die Permutation σ = (0, 2, 1, 3).

Programm 6.34 (FFT) N = 2n, n ∈ NGegeben: z(0), . . . , z(N − 1)

Zu berechnen: c(N)(0), . . . , c(N)(N − 1)m := N ;Fur t = n, . . . , 1

m := m/2zeta := 1zeta2m := exp−2πi

2mFur k = 0, . . . ,m− 1

Fur r = 0, . . . , N − 1 step 2mu := z(r + k)v := z(r + k +m)z(r + k) := u+ vz(r + k +m) := (u− v) ∗ zetaEnde

zeta := zeta ∗ zeta2m

25

EndeEnde.Fur r = 0, . . . , N − 1c(N)(σ(r)) = 1√

Nz(r) (σ = Bitumkehrabbildung!)

Ende

Die Bitumkehrabbildung σ ist gegeben durch

σ

s−1∑j=0

aj2j

=s−1∑j=0

as−1−j2j .

Der Rechenaufwand bei der schnellen Fouriertransformation ist bezuglich komplexer Multi-plikationen proportional zu N logN .

6.5 Polynominterpolation

Beispiel 6.35 (Approximation durch Interpolation)

6.5.1 Lagrange-Interpolation

Mit Pn bezeichnen wir die Menge der Polynome p vom Grad kleiner oder gleich n:

p(x) = a0 + a1x+ . . .+ anxn (aj ∈ R).

Das Interpolationsproblem (IP) lautet:Gegeben:

- (n + 1) paarweise verschieden Punkte x0, . . . , xn ∈ R (die Stutzstellen oder Knotengenannt werden)

- (n+ 1) zugehorige Werte y0, . . . , yn ∈ R (Funktions-oder Stutzwerte)

Gesucht: p ∈ Pn mit p(xk) = yk (k = 0, . . . , n).

Satz 6.36 Das Interpolationsproblem (IP) besitzt genau eine Losung.

Definition 6.37 Es seien n+1 paarweise verschiedene Punkte xk ∈ R, k = 0, . . . , n, gegeben.Dann heissen

l(n)i (x) =

n∏j=0j 6=i

x− xjxi − xj

(i = 0, . . . , n)

die zu diesen Knoten gehorenden Lagrange-Grundpolynome.

Lemma 6.38 Voraussetzungen wie in Definition 6.37. Es gilt:

l(n)i (xj) = δij .

Weiter ist

l(n)j (x) =

n∏i=0i6=j

x− xixj − xi

=ϕn+1(x)

(x− xj)ϕ′n+1(xj)(j = 0, ..., n),

wobei ϕn+1(x) :=n∏k=0

(x− xk).

26

Satz 6.39 (Lagrange-Interpolierende) Seien x0, . . . , xn ∈ R paarweise verschieden. Durch

Ln(x) =n∑i=0

f(xi) l(n)i (x),

ist ein Polynom Ln ∈ Pn gegeben, das f(xk) interpoliert:

Ln(xk) = f(xk) (k = 0, . . . , n).

Die Losung ist eindeutig bestimmt.

Beispiel 6.40 Gegeben sind die Daten:

xk 0 1 3

yk 1 3 2

Gesucht ist L2(2).

Lemma 6.41 Gegeben (xk, yk), k = 0, . . . , n, mit xk paarweise verschieden. Wahle k0, . . . , kr ∈0, 1, 2, . . . , n paarweise verschieden. Sei pk0,...,kr ∈ Pr das Interpolationspolynom, das dieInterpolationsbedingungen an den Stellen xk0 , . . . , xkr erfullt, d.h.

pk0,...,kr(xkj ) = ykj (j = 0. . . . , r).

Es gelten die Rekursionsformel:(i) pk(x) = yk k ∈ 0, . . . , n(ii)

pk0,...,kr(x) =(x− xk0)pk1,...,kr(x)− (x− xkr)pk0,...,kr−1(x)

xkr − xk0.

Beispiel 6.42 (Algorithmus von Neville) 1. Schema fur n = 3:

y0 = p0(x)p01(x)

y1 = p1(x) p012(x)p12(x) p0123(x)

y2 = p2(x) p123(x)p23(x)

y3 = p3(x)

2. Berechnung von L2(2) mit den Daten aus Beispiel 6.40.

Beispiel 6.43 (Horner Schema) Sei

p(x) =n∑i=0

ai xn−i.

Das Schemac0 = a0, ci = ai + ci−1x0 (i = 1, . . . , n)

liefert den Funktionwert p(x0) = cn. (Merke die Faktorisierung

p(x0) = an + x0(an−1 + x0(an−2 + x0(. . .+ x0(a1 + x0a0) . . .))). )

27

6.5.2 Newton-Interpolation

Definition 6.44 Seien x0, . . . , xn ∈ R paarweise verschieden. Die Newton-Grundpolynomesind definiert durch

ϕ0(x) = 1, ϕk(x) =k−1∏j=0

(x− xj) (k = 1, . . . , n).

Definition 6.45 Sei pj ∈ Pj das Interpolationspolynom zu den paarweise verschiedenenStutzstellen x0, . . . , xj und pj(xk) = yk (bzw. yk = f(xk)) fur k = 0, . . . , j. Dann heisst derKoeffizient der hochsten Potenz xj von pj dividierte Differenzen j-ter Ordnung. Man schreibt

[y0, . . . , yj ] (bzw. [f(x0), . . . , f(xj)] oder auch f [x0, . . . , xj ]).

Satz 6.46 Fur die dividierte Differenz [y0, . . . , yj ] zu den paarweise verschiedenen Stutzstel-len xk und den Stutzwerten yk, k = 0, . . . , j, gilt:

(i) [y0, . . . , yj ] =∑j

r=0 yrj∏k=0k 6=r

1xr−xk .

(ii) [y0, . . . , yj ] ist invariant gegenuber Permutation der Wertepaare (x0, y0), . . . , (xj , yj).(iii) [y0, . . . , yj ] lasst sich rekursiv berechnen:

[yi] = yi, i = 0, . . . , j

[yi, . . . , yi+l] =[yi+1, . . . , yi+l]− [yi, . . . , yi+l−1]

xi+l − xii = 0, . . . , j − l; l = 1, . . . , j.

Satz 6.47 (Newtonsches Interpolationspolynom) Das Iterpolationspolynom p ∈ Pn,das die Bedingungen p(xk) = f(xk), k = 0, . . . , n, erfullt, hat die Darstellung

p(x) =

n∑k=0

f [x0, ..., xk]ϕk(x) = (Ln(x)).

Algorithmus 6.48 Zur rekursiven Berechnung der dividierten Differenzen.

f(x0)

f [x0, x1] = f(x1)−f(x0)x1−x0

f(x1) f [x0, x1, x2] = f [x0,x1]−f [x1,x2]x0−x2

f [x1, x2] = f(x2)−f(x1)x2−x1 f [x0, x1, x2, x3] = f [x0,x1,x2]−f [x1,x2,x3]

x0−x3f(x2) f [x1, x2, x3] = f [x1,x2]−f [x2,x3]

x1−x3f [x2, x3] = f(x3)−f(x2)

x3−x2f(x3)...

28

Programm 6.49 Mit y(j) = f(xj) und x(j) = xj berechne

Fur i = 0, ..., nc(i) := y(i)EndeFur k = 1, ..., n

Fur i = n, ..., k step −1c(i) := (c(i)− c(i− 1))/(x(i)− x(i− k))Ende

Ende.

Beispiel 6.50 Newtonsches Interpolationspolynom zu den Daten

xk 0 1 2 3

yk 1 2 0 1

Folgerung 6.51 Sei xj = x0 + jh. Dann ist

f [x0, ..., xn] =Dnf(x0)

n! hn

mitD0f(x0) := f(x0), Df(x0) := f(x0 + h)− f(x0), Dn+1f(x0) := DnDf(x0).

Folgerung 6.52 Sei xj = x0 + jh. Dann gilt

Ln(x) =n∑k=0

(Dkf)(x0)

k! hkϕk(x).

Satz 6.53 Seien x0, ..., xn paarweise verschieden. Fur x ∈ R sei m(x) := minx0, ..., xn, x,M(x) = maxx0, ..., xn, x. Weiter sei f ∈ Cn+1([m(x),M(x)]). Dann gibt es ein ξ ∈[m(x),M(x)], so daß

f(x)− Ln(x) =f (n+1)(ξ)

(n+ 1)!ϕn+1(x)

gilt. Dabei ist Ln das interpolierende Polynom vom Grad ≤ n zu den Daten f(x0), ..., f(xn).

Folgerung 6.54 Voraussetzungen wie im vorigen Satz, nur xj ∈ [a, b], −∞ < a < b < ∞.Dann gilt

‖f − Ln‖C0([a,b]) ≤ (b− a)n+1 1

(n+ 1)!‖f (n+1)‖C0([a,b]).

Beispiel 6.55 (Runge)

29

6.6 Spline-Interpolation

Satz 6.56 Es seien xj ∈ [a, b], uj ∈ R, a = x0 < x1 < ... < xn = b. Außerdem sei

X =u ∈ C1([a, b],R)

∣∣u(xj) = uj (j = 0, ..., n), u|(xj ,xj+1) laßt sich zu

u ∈ C4([xj , xj+1],R) (j = 0, ..., n− 1) fortsetzen.

Ist u ∈ X ein Minimum des Funktionals

I(u) =1

2

n−1∑j=0

xj+1∫xj

u′′(x)2dx,

d. h. I(u) ≤ I(v) fur alle v ∈ X, so ist u|(xj ,xj+1) ein Polynom vom Grad ≤ 3, u ∈ C2([a, b],R)

und u′′(a) = u

′′(b) = 0.

Definition 6.57 Sei m ∈ N. Eine stuckweise polynomiale Funktion u ∈ C2m−2([a, b]) aufdem Gitter −∞ < a = x0 < x1 < . . . < xn = b <∞,

u|(xj ,xj+1) ∈ P2m−1,

die u0, . . . , un interpoliert,u(xj) = uj (j = 0, . . . , n),

heißt Spline (2m− 1)-ter Ordnung mit naturlichen Randbedingungen, falls

u(k)(a) = u(k)(b) = 0 (k = m, . . . , 2m− 2).

(Wenn m = 2 spricht man von kubischen Splines.)

Satz 6.58 Fur jedes Gitter x0 < x1 < ... < xn von n + 1 Punkten und gegebene Datenu0, ..., un gibt es genau einen kubischen Spline u. Auf [xj−1, xj ] ist

u(x) = Mj−1(xj − x)

6hj

3

+Mj(x− xj−1)

6hj

3

+(uj −Mjh

2j

6)(x− xj−1)

hj+ (uj−1 −

Mj−1h2j

6)(xj − x)

hj.

Dabei ist hj = xj − xj−1 und M0, ...,Mn ist die Losung des tridiagonalen Gleichungssystems

aj Mj−1 + 2Mj + (1− aj)Mj+1 = dj (j = 1, . . . , n− 1)

mit M0 = Mn = 0 und

aj =hj

hj + hj+1, dj =

6

hj + hj+1

(uj+1 − ujhj+1

− uj − uj−1

hj

).

Satz 6.59 Voraussetzungen wie im Satz 6.56. Sei s der kubische Spline, der di Daten u0, . . . , uninterpoliert. Dann gilt:

I(s) ≤ I(u) ∀u ∈ X.

30

Satz 6.60 (ohne Beweis) Es liege die Situation des Satzes 6.58 vor, wobei die Daten alsuj = f(xj), (j = 0, . . . , n) fur eine gegebene Funktion f ∈ C4([a, b]) gewahlt seien. Dann giltfur den Fehler zwischen dem Spline u und der Funktion f die Abschatzung

‖u− f‖C0([a,b]) ≤ ch4‖f (4)‖C0([a,b]),

wobei h = maxhj | j = 1, . . . , n ist.

6.7 Numerische Integration: Quadratur

Sei −∞ < a < b < ∞ und f : [a, b] → R. Zur Abkurzung setzen wir I(f) =∫ ba f(t) dt.

Die Resultate zur Interpolation aus Abschnitt 6.5 liefern Integrationsformeln und Fehler-abschatzungen.Zu paarweise verschiedenen Stutzstellen a = x0 < x1 < · · · < xn = b gibt es eine eindeutigbestimmte interpolatorische Quadraturfomel, die mindestens Polynome vom Grad kleinergleich n exakt integriert:

I(n)(f) =

∫ b

aLn(x)dx =

n∑k=0

αkf(xk), αk =

∫ b

al(n)k (x)dx.

Satz 6.61 Fur interpolatorische Quadraturformel gilt:

I(f)− I(n)(f) =

∫ b

af [x0, . . . , xn, x]

n∏j=0

(x− xj)dx

Definition 6.62 Eine Quadraturformel wird “mindestens von der Ordnung m” genannt,wenn durch sie wenigstens alle Polynome aus Pm−1 exakt integriert werden.

Beispiel 6.63 (Newton-Cotes Quadraturformel) Sei h = b−an , xi = a+ ih, i = 0, . . . , n.

(a) Trapezregel

I(1)(f) =b− a

2[f(a) + f(b)]

(b) Simpson-Regel

I(2)(f) =b− a

6[f(a) + 4f

(a+ b

2

)+ f(b)].

Satz 6.64 Sei n ≥ 1, f ∈ Cn+1([a, b]). Dann gilt:∣∣∣∣∫ b

af(x)dx− I(n)(f)

∣∣∣∣ ≤ Mn+1

(n+ 1)!

∫ b

a|ϕn+1(x)|dx

wobei Mn+1 = max[a,b] |f (n+1)|.Zum Beispiel:

(a) Trapezregel : |∫ ba f(x)dx− I(1)(f)| ≤ (b−a)3

12 M2

(b) Simpson-Regel: |∫ ba f(x)dx− I(2)(f)| ≤ (b−a)4

196 M3.

31

Satz 6.65 Sei f ∈ C4([a, b]). Dann gilt:∫ b

af(x)dx− b− a

6[f(a) + 4f

(a+ b

2

)+ f(b)] = −(b− a)5

2880f (iv)(ξ)

fur ein ξ ∈ (a, b). (Somit ist die Simpson-Regel sogar exakt auf P3.)

Folgerung 6.66 Sei f ∈ C4([a, b]). Dann ist∣∣∣∣∫ b

af(x)dx− I(2)(f)

∣∣∣∣ ≤ (b− a)5

2880M4.

Nun zerlege man das Intervall [a, b] in Teilintervalle und wende auf jedem dieser Teilintervalledie obigen Regeln an.

Beispiel 6.67 Sei m ≥ 2, h = b−am , xi = a + ih, i = 0, . . . ,m. Die summierte Trapezregel

lautet:

I(1)h (f) = h(

1

2f(x0) + f(x1) + · · ·+ f(xm−1) +

1

2f(xm)).

Es gilt: |I(f)− I(1)h (f)| ≤ M2

12(b−a)3

m2 .

Beispiel 6.68 Sei m ≥ 2, h = b−a2m , xi = a+ ih, i = 0, . . . , 2m. Die summierte Simpson-Regel

lautet:

I(2)h (f) =

h

3(f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + · · ·+ 2f(x2m−2) + 4f(xm−1) + f(xm)).

Es gilt: |I(f)− I(2)h (f)| ≤ M4

2880(b−a)5

m4 .

32