Kapitel in einem PDF

Transcrição

1 Arithmetische Grundlagen
Karlsruhe Institute of Technology
Am 4. Juni 1996 explodierte kurz nach dem Start die
erste Ariane 5 Rakete durch einen Softwarefehler.
Die Horizontalgeschwindigkeit wurde durch eine
Gleitkommazahl
v ∈ [−10308 , −10−308 ] ∪ {0} ∪ [10−308 , 10308 ]
dargestellt.
Innerhalb der Rechnung wurde die Zahl versehentlich
in eine ganzzahlige Darstellung
i ∈ {0, 1, 2, ..., 32 767}
konvertiert.
Als die Geschwindigkeit v > 32 767 erreichte, verlor die
Software die Geschwindigkeitsinformation und damit
schließlich die Orientierung.
http://ta.twi.tudelft.nl/users/vuik/wi211/disasters.html
http://www5.in.tum.de/ huckle/bugse.html
C. Wieners: Einführung in die Numerische Mathematik für Studierende der Fachrichtung Informatik und Ingenieurwissenschaften
1
Am 25. Februar 1991 während des ersten Golfkriegs in
Dharan, Saudi Arabien, verfehlte eine amerikanische
Patriot–Rakete eine anfliegende irakische Scud Rakete
durch eine falsche Zeitberechnung.
Eine 1/10 Sekunde wurde ungenau dargestellt (durch
Rundungsfehler wurde die periodische Dualentwicklung
0.0001100110011001100110011001100....
in der Computerdarstellung zu
0.00011001100110011001100
abgeschnitten), so dass nach 100 Stunden Betriebszeit
eine Zeitdifferenz von ca. 0.3 Sekunden entstand.
Dieser Fehler wurde nicht in allen Teilen des
Betriebsprogramms korrigiert.
http://ta.twi.tudelft.nl/users/vuik/wi211/disasters.html
http://www5.in.tum.de/ huckle/bugse.html
2
(1.3)
a) Eine Gleitkommazahlen zur Basis B ∈ {2, 3, ...} der Mantissenlänge M und
Exponentenlänge E ist die Menge
FL =
n
± Be
M
∑
m=1
am B −m : e = e− +
E−1
o
∑ ck B k , am , ck ∈ {0, 1, ..., B − 1}
k =0
b) Eine Gleitkommaarithmetik wird durch eine Abbildung fl : R −→ FL mit fl(x) = x für x ∈ FL
definiert. Sei bestimmt die Rundung: x ⊕ y = fl(x + y ), x y = fl(x · y ), etc.
Die zugehörige Maschinengenauigkeit ist
|x − fl(x)|
eps := sup
; 0 < |x| < M .
|x|
(1.2)
(1.3)
a) Ein Problem heißt sachgemäß gestellt, wenn es eindeutig lösbar ist und die Lösung stetig
von den Daten abhängt.
b) Die Kondition eines Problems ist eine Maß dafür, wie stark die Abhängigkeit der Lösung
von den Daten ist.
c) Die Stabilität eines numerischen Algorithmus ist eine Maß dafür, wie stark die
Daten-Abhängigkeit der numerischen Lösung im Vergeich zu der tatsächlichen Lösung ist.
N
Sei f : RN −→ RK eine
differenzierbare Funktion und x ∈ R . Dann heißt
kn = ∂ f (x) absolute Konditionszahl.
a) κabs
∂ xn k
kn = ∂ f (x) |xn | relative Konditionszahl.
b) κrel
∂ xn k
|f (x)|
k
3
Sei | · | eine Vektornorm, und sei k · k eine zugeordete Matrixnorm, d. h.,
x ∈ RN , A ∈ RM×N .
|Ax| ≤ kAk |x| ,
Wir verwenden für x ∈ RN und A ∈ RM×N
N
|x|1 =
∑ |xn |
|x|2 =
p
xT x
|x|∞ = max |xn |
n=1,...,N
n=1
und die zugeordnete Operatornorm kAkp = supx6=0N
M
kAk1 = max
∑
n=1,...,N m=1
|amn | ,
kAk2 =
|Ax|p
|x|p
q
ρ(AT A) ,
, d.h.
N
kAk∞ = max
∑ |amn |
m=1,...,M n=1
mit Spekralradius ρ(A) = max{|λ | : λ Eigenwert von A}.
(1.4)
Sei A ∈ RN×N invertierbar. Dann heißt κp (A) = kAkp kA−1 kp die Kondition von A.
Sei b ∈ RN , b 6= 0N , 4b ∈ RN eine kleine Störung und b̃ = b + 4b.
Sei x ∈ RN Lösung von Ax = b, x̃ ∈ RN Lösung von Ax̃ = b̃, und 4x = x̃ − x der Fehler.
| 4 b|p
| 4 x|p
≤ κp (A)
.
Dann gilt für den relativen Fehler
|x|p
|b|p
4
Auslöschung bei Nullstellenberechnung
Wir betrachten die Gleichung
x 2 − 2px + q = 0,
deren Nullstellen durch
q
x = p ± p2 − q
gegeben sind. Diese Berechnungsvorschrift ist aber für p q nicht zu empfehlen, da dann
Auslöschung bei der betragsmäßig kleineren Nullstelle auftritt. Wählt man beispielsweise
p = 108 und q = 1, so berechnet Matlab
x1 = 2 ∗ 108 ,
x2 = 0.
Die Auslöschung bei x2 kann man umgehen, indem man zuerst die größere Nullstelle durch
q
x1 = p + sign(p) p2 − q
berechnet und dann (mit dem Satz von Vieta) die zweite Nullstelle durch
x2 =
q
x1
erhält. Mit dieser Vorschrift berechnet Matlab die bessere Lösung
x1 = 2 ∗ 108 ,
x2 = 0.5 ∗ 10−9 .
5
2 Direkte Lösungsverfahren für lineare Gleichungen
(2.1)
(2.2)
(2.3)
Sei L ∈ RN×N eine normierte untere Dreiecksmatrix und b ∈ RN . Dann ist L invertierbar und
das Lineare Gleichungssystem (LGS) Ly = b ist mit O(N 2 ) Operationen lösbar.
Entsprechend ist für eine invertierbare obere Dreiecksmatrix R ∈ RN×N das LGS Rx = y in
O(N 2 ) Operationen lösbar.
Wenn eine Matrix A ∈ RN×N eine LR-Zerlegung A = LR mit einer normierten untere
Dreiecksmatrix L und einer invertierbaren obere Dreiecksmatrix R besitzt, dann ist A
invertierbar und das LGS Ax = b ist mit O(N 2 ) Operationen lösbar.
Eine Matrix A ∈ RN×N besitzt genau dann eine LR-Zerlegung von A, wenn alle
Hauptuntermatrizen A[1 : n, 1 : n] invertierbar sind. Die LR-Zerlegung ist eindeutig und lässt
sich mit O(N 3 ) Operationen berechnen.
N
(2.5)
Eine Matrix A ∈ RN×N heißt strikt diagonal-dominant, falls |A[n, n]| > ∑ |A[n, k ]|.
k =1
k 6=n
Sie heißt positiv definit, wenn x T Ax > 0 für x ∈ RN , x 6= 0.
In beiden Fällen existiert eine LR-Zerlegung.
(2.6)
Sei A ∈ RN×N symmetrisch und positiv definit.
Dann existiert genau eine Cholesky-Zerlegung A = LLT mit einer unteren Dreiecksmatrix L.
Software: http://www.netlib.org/lapack
6
2 Direkte Lösungsverfahren für lineare Gleichungen
(2.7)
(2.8)
(2.9)
a) Eine bijektive Abbildung π : {1, ..., N} −→ {1, ..., N} heißt Permutation.
b) Sie ist eindeutig durch einen Permutationsvektor p ∈ RN mit p[n] = π(n) bestimmt.
c) Die zugehörige Permutationsmatrix ist P = (eπ(1) · · · |eπ(N) ) ∈ RN×N .
Sei A ∈ RN×N invertierbar. Dann existiert eine Permutationsmatrix P, so dass PA eine
LR-Zerlegung PA = LR besitzt, so dass |L[m, n]| ≤ 1 gilt.
a) Zu v ∈ RN und k 6= n mit v [k ]2 + v [n]2 > 0 existiert eine Givens-Rotation G ∈ RN×N mit
G[k , k ] G[k , n]
c
s
=
,
c 2 + s2 = 1 ,
G[n, k ] G[n, n]
−s c
und G[j][j] = 1 für j 6= k , n und G[i][j] = 0 sonst, so dass für w = Gv gilt: w[n] = 0.
]
[n]
√ 1 , c = sτ, sonst setze τ = vv [k
√1
Für |v [n]| > |v [k ]| setze τ = vv [k
[n] , s =
], c =
2
1+τ 2
1+τ
b) Zu v ∈ RN , v 6= 0, existiert eine Householder-Spiegelung H = IN −
, s = cτ.
2
ww T ∈ RN×N mit
wT w
w ∈ RN , w[1] = 1, sodass Hv = σ e1 mit σ ∈ R.
Falls v [1] > 0, setze σ = −|v |2 , sonst setze σ = |v |2 . Dann definierte w =
1
v [1]−σ
(v − σ e1 ).
Rotationen und Spiegelungen Q sind orthogonale Matrizen, d.h. Q T Q = IN , Q −1 = Q T ,
kQk2 = 1 und κ2 (Q) = 1.
(2.10)
Zu A ∈ RK ×N existiert eine QR-Zerlegung A = QR mit einer orthogonalen Matrix Q ∈ RK ×K
und eine oberen Dreiecksmatrixmatrix R ∈ RM×N .
7
LR-Zerlegung (ohne Vektorisierung)
N = size(A,1);
for n=1:N-1
% Berechnung der n-ten Spalte von L
for m=n+1:N
A(m,n) = A(m,n)/A(n,n);
end;
% keine Berechnung der n-ten Zeile von R erforderlich
% Berechnung der Restmatrix
for m=n+1:N
for k=n+1:N
A(m,k) = A(m,k) - A(m,n) * A(n,k);
end;
end;
end;
8
LR-Zerlegung
N = size(A,1);
for n=1:N-1
A(n+1:N,n) = A(n+1:N,n)/A(n,n);
A(n+1:N,n+1:N) = A(n+1:N,n+1:N) - A(n+1:N,n) * A(n,n+1:N);
end;
x = b;
for n=2:N
x(n) = x(n) - A(n,1:n-1) * x(1:n-1);
end;
for n=N:-1:1
x(n) = (x(n) - A(n,n+1:N)*x(n+1:N))/A(n,n);
end;
9
Cholesky-Zerlegung
N = size(A,1);
for n=1:N
A(n:N,n) = A(n:N,n) - A(n:N,1:n-1) * A(n,1:n-1)’;
A(n:N,n) = A(n:N,n) / sqrt(A(n,n));
end;
x = b;
for n=1:N
x(n) = (x(n) - A(n,1:n-1) * x(1:n-1))/ A(n,n);
end;
for n=N:-1:1
x(n) = (x(n) - A(n+1:N,n)’ * x(n+1:N))/ A(n,n);
end;
10
LR-Zerlegung mit Pivotsuche
N = size(A,1);
p = (1:N)’;
for n = 1:N-1
[r,m] = max(abs(A(n:N,n)));
m = m+n-1;
if abs(A(m,n))<eps
error(’*** ERROR *** LR-Zerlegung existiert nicht’);
end;
if (m ~= n)
A([n m],:) = A([m n],:);
p([n m]) = p([m n]);
end;
A(n+1:N,n) = A(n+1:N,n)/A(n,n);
A(n+1:N,n+1:N) = A(n+1:N,n+1:N) - A(n+1:N,n)*A(n,n+1:N);
end;
x = b(p);
for n=2:N
x(n) = x(n) - A(n,1:n-1)*x(1:n-1);
end;
for n=N:-1:1
x(n) = (x(n) - A(n,n+1:N)*x(n+1:N))/A(n,n);
end;
11
Berechnung der Householder-Vektoren
function [v,beta] = householder(y)
N = length(y);
s = y(2:N)’ * y(2:N);
if N == 1
s = 0;
end;
v = [1;y(2:N)];
if s == 0
beta = 0;
else
mu = sqrt(y(1)^2 + s);
if y(1) <= 0
v(1) = y(1) - mu;
else
v(1) = -s/(y(1) + mu);
end;
beta = 2*v(1)^2/(s + v(1)^2);
v = v / v(1);
end;
return;
12
QR-Zerlegung
[M,N] = size(A);
for m = 1:min(N,M-1)
[v,beta] = householder(A(m:M,m));
if beta ~= 0
w = beta * v’ * A(m:M,m:N);
A(m:M,m:N) = A(m:M,m:N) - v * w;
A(m+1:M,m) = v(2:M-m+1);
end;
end;
for m = 1:min(N,M-1)
v = [1;A(m+1:M,m)];
beta = 2 / (v’ * v);
if beta ~= 2
b(m:M) = b(m:M) - beta*(v’*b(m:M)) * v;
end;
end;
for n=min(N,M):-1:1
x(n) = (b(n) - A(n,n+1:N) * x(n+1:N)) / A(n,n);
end;
13
3 Lineare Ausgleichsrechnung
(3.1)
(3.2)
Sei A ∈ RK ×N und b ∈ RK . Dann gilt:
x ∈ RN minimiert |Ax − b|2 ⇐⇒ AT Ax = AT b.
Zu A ∈ RK ×N mit R = rang(A) existieren Singulärwerte σ1 , ..., σR > 0 und eine
Singulärwertzerlegung
A = V ΣU T
mit V ∈ RK ×K , U ∈ RN×N orthogonal und Σ ∈ RK ×N mit Σ[r , r ] = σr für r = 1, ..., R und
Σ[k , n] = 0 sonst.
(3.3)
(3.4)
(3.5)
(3.6)
A+ = UΣ+ V T ist die Pseudo-Inverse
mit Σ+ ∈ RN×K mit Σ+ [r , r ] = 1/σr für r = 1, ..., R und Σ+ [n, k ] = 0 sonst.
x = A+ b löst die Normalengleichung AT Ax = AT b.
Sei A ∈ RK ×N und b ∈ RK .
Dann gilt für die Tikhonov-Regularisierung mit α > 0:
x ∈ RN minimiert |Ax − b|22 + α |x|22 ⇐⇒ (AT A + αIN )x = AT b.
Es gilt lim (AT A + αIN )−1 AT b = A+ b.
α−→0
14
Ein schlecht konditioniertes Gleichungssystem
Wir betrachten das lineare Gleichungssystem Ax = b mit der Hilbertmatrix
1
A=
∈ RN+1×N+1
m + n + 1 m,n=0,...,N
n
∈ RN+1 .
und der rechten Seite b = (−1)n log(2) + ∑ (−1)m
n=0,...,N
m=1
Die exakte Lösung lautet:
N
1
2
3
4
5
6
x0
0.93
0.99
1.00
1.00
1.00
1.00
x1
−0.48
−0.80
−0.94
−0.98
−1.00
−1.00
x2
x3
x4
x5
x6
0.33
0.66
0.86
0.95
0.98
−0.22
−0.53
−0.77
−0.90
0.15
0.42
0.67
−0.11
−0.32
0.07
(Beispiel aus Kress: Numerical Analysis)
15
Stören wir nun aber die rechte Seite geringfügig, indem wir log(2) nur bis auf
5 Nachkommastellen auswerten, so erhalten wir folgende Lösung:
N
1
2
3
4
5
6
x0
0.93
0.99
1.00
1.01
1.06
1.39
x1
−0.48
−0.81
−0.96
−1.16
−2.74
−16.58
x2
x3
x4
x5
x6
0.33
0.70
1.63
12.68
151.10
−0.25
−1.70
−31.16
−584.81
0.72
33.87
1071.96
−13.26
−926.77
304.50
Also: Eine geringfügige Störung der Daten führt zu einer großen Störung des Ergebnisses.
Der Grund dafür liegt in der schlechten Kondition der Hilbertmatrix. Diese ist in der
Spektralnorm:
N
κ2 (A)
2
19.28
3
524.06
4
1.55e + 04
5
4.77e + 05
6
1.495e + 07
(Beispiel aus Kress: Numerical Analysis)
16
Invertierung der Hilbert-Matrix (Matlab)
>> H = hilb(3); IH = inv(H); IH(1,1:3)
ans = 9.00000000000003 -36.0000000000001 30.0000000000001
>> H = hilb(5); IH = inv(H); IH(1,1:3)
ans = 24.9999999999919 -299.999999999882 1049.99999999958
>> H = hilb(7); IH = inv(H); IH(1,1:3)
ans = 49.0000000578711 -1176.00000232576 8820.00002248178
>> H = hilb(9); IH = inv(H); IH(1,1:3)
ans = 80.9999332549633 -3239.99529943927 41579.919225348
>> H = hilb(11); IH = inv(H); IH(1,1:3)
ans = 120.91751059331
-7251.2942628623
141342.563141014
17
Wir können die Kondition verbessern, indem wir die Tikhonov-Regularisierung auf die
Hilbertmatrix anwenden, d.h.
x α = (AT A + αIN )−1 AT b .
Regularisieren wir mit einem Parameter α = 10−10 , so erhalten wir
N
1
2
3
4
5
6
x0
0.93
0.99
1.00
0.99
1.00
1.00
x1
−0.48
−0.81
−0.95
−0.89
−0.91
−0.94
x2
x3
x4
x5
x6
0.33
0.69
0.47
0.52
0.58
−0.24
0.06
0.02
0.08
−0.14
−0.18
−0.25
0.04
−0.17
0.20
18
4 Eigenwertberechung
(4.1)
(4.2)
(4.3)
(4.4)
Eine Matrix H ∈ RN×N heißt Hessenberg-Matrix, wenn H[n + 2 : N, n] = 0N−n−1 für
n = 1, ..., N − 2.
Sei A ∈ RN×N . Dann existiert eine orthogonale Matrix Q ∈ RN×N , so dass H = QAQ T eine
Hessenberg-Matrix ist. Die Berechnung benötigt O(N 3 ) Operationen.
Wenn A symmetrisch ist, dann ist H eine Tridiagonalmatrix.
Sei A ∈ RN×N symmetrisch, tridiagonal, und irreduzibel, d.h.
A[n + 2 : N, n] = A[n, n + 2 : N]T = 0N−n−1 und A[n − 1, n] = A[n, n − 1] 6= 0.
Dann hat A paarweise verschiedene reele Eigenwerte λ1 < λ2 < · · · < λN .
Inverse Iteration mit variablem Shift
S0) Wähle z 0 ∈ RN , z 0 6= 0N , ε ≥ 0. Setze k = 0.
S1) Setze w k = |z1| z k , µk = r (A, w k ).
k 2
S2) Falls |Aw k − µk w k |2 ≤ ε STOP.
S3) Berechne z k +1 = (A − µk IN )−1 w k .
S4) Setze k := k + 1, gehe zu S1).
Wenn der Startvektor z 0 hinreichend nahe bei einem Eigenvektor v m mit isoliertem
Eigenwert λ = λm liegt, konvergiert die Iteration kubisch, d.h. |µk − λ | ≤ C |µk − λ |3 .
19
4 Eigenwertberechnung: QR-Iteration mit Shift
Sei A ∈ RN×N symmetrisch.
S0) Berechne A0 = QAQ T tridiagonal (Hessenberg-Transformation).
Wähle ε ≥ 0. Setze k = 0.
S1) Falls |Ak [n + 1, n]| ≤ ε für ein n:
getrennte Eigenwertberechnung für Ak [1 : n, 1 : n] und Ak [n + 1 : N, n + 1 : N].
S2) Berechne dk = 12 (Ak [N − 1, N − 1] − Ak [N, N]) und
q
sk = Ak [N, N] + dk − sgn(dk ) dk2 + Ak [N − 1, N]2 .
S3) Berechne QR-Zerlegung
Qk Rk = Ak − sk IN
und setze
Ak +1 = Rk Qk + sk IN .
S4) Setze k := k + 1, gehe zu S1).
Es gilt Ak +1 = QkT Ak Qk . Also haben Ak +1 und Ak disselben Eigenwerte.
Falls der shift sk = Ak [N, N] gewählt wird, entspricht die QR-Iteration der Inversen Iteration
mit variablem Shift und Startvektor z 0 = eN .
20
Impliziter QR-Algorithmus mit Wilkinson-Shift
Für symmetrische Matrizen (o.B.d.A. Hessenbergform) lässt sich der QR-Algorithmus so
modifizieren, dass die QR-Zerlegung in jedem Iterationsschritt nur implizit durch N − 1
Transformationen mit Givensrotationen durchgeführt werden muss. Durch den
Wilkinson-Shift (siehe Golub, van Loan) erhalten wir außerdem kubische Konvergenz, im
Gegensatz zur linearen Konvergenz des QR-Algorithmus’ ohne Shift. Dabei können wir eine
Toleranz für die verschwindenden Nebendiagonalelemente vorgeben.
Wir betrachten
A = tridiag(−1, 2, −1) ∈ RN×N .
Für die Toleranz tol = ε braucht der Algorithmus die folgende Anzahl von Iterationen:
N
100
200
500
1000
Iterationen
281
532
1120
2310
Das sind im Schnitt weniger als 3 Iterationen pro Eigenwert.
Der maximale Fehler bei diesen Berechnungen beträgt zwischen 10−13 und 10−14 .
21
5 Iterationsverfahren für lineare Gleichungen
(5.1)
S0) Wähle x 0 ∈ RN und ε > 0.
Berechne r 0 = b − Ax 0 . Setze k = 0.
S1) Falls |r 0 | ≤ ε STOP.
S2) Berechne
wk
=
Br k −1
x k +1
=
xk + wk
k +1
=
r k − Aw k
r
Setze k := k + 1 und gehe zu S1).
Sei A = L + D + R. Dann gilt B = D −1 für das Jacobi-Verfahren und B = L + D
Gauß-Seidel-Verfahren.
(5.2)
−1
für das
Sei A, B ∈ RN×N mit ρ(IN − BA) < 1. Dann ist A invertierbar, und es gilt für alle b ∈ RN und
alle Startvektoren x 0 ∈ RN konvergiert die Iteration
x k +1 = x k + B(b − Ax k ) ,
gegen lim
k −→∞
xk
= A−1 b.
k = 0, 1, 2, ...
Dann exisitiert eine Vektor-Norm | · | und dazu eine Matrix-Norm k · k
mit kIN − BAk < 1. Damit ergibt sich |x − x k | ≤ kIN − BAkk |x − x 0 | (lineare Konvergenz).
Software: z.B. http://www.cise.ufl.edu/research/sparse/SuiteSparse
22
5 Iterative Lösungsverfahren: Krylov-Verfahren
Sei h·, ·iV ein Skalarprodukt in V = RN .
S0) Wähle x 0 ∈ RN .
Berechne r 0 = b − Ax 0 , z 1 = Br 0 , h10 = |z 1 |V und v 1 =
1 1
h10 z .
Setze k = 1.
S1) Berechne
wk
=
BAv k
z k +1
=
w k − ∑ hjk v j mit hjk = hv j , w k iV
k
j=1
v k +1
=
1
hk +1,k
z k +1 mit hk +1,k = |z k +1 |V
S2) Setzte k := k + 1 und gehe zu S1).
Dann ist v 1 , ..., v k eine Orthonormalbasis von dem Krylov-Raum
Vk = span{Br 0 , BABr 0 , ..., (BA)k −1 Br 0 } = {Qk y : y ∈ Rk } ,
Qk = v 1 |....|v k .
k +1
Es gilt BAv k = ∑ hjk v j , also BAQk = Qk +1 Hk mit Hk = (hjm ) ∈ Rk +1,k .
j=1
GMRES-Verfahren: Wähle hv , wiV = v T w.
cg-Verfahren (A, B symmetrisch positiv definit): Wähle hv , wiV = v T Aw.
23
5 Iterative Lösungsverfahren: GMRES-Verfahren
S0) Wähle x 0 ∈ RN , ε > 0.
Berechne r 0 = b − Ax 0 , z 1 = Br 0 , h10 = |z 1 |2 und v 1 =
1 1
h10 z .
Setze k = 1.
S1) Berechne
wk
=
BAv k
z k +1
=
w k − ∑ hjk v j mit hjk = (v j )T w k
k
j=1
v k +1
=
1
hk +1,k
z k +1 mit hk +1,k = |z k +1 |2
S2) Berechne y k ∈ Rk mit ρk = |Hk yk − h10 e1 |2 = min!
Dabei ist Hk = (hjm )j=1,...,k +1, m=1,...,k ∈ Rk +1,k .
k
S3) Wenn ρk < ε, setze x k = x 0 + ∑ yjk v j
STOP.
j=1
S4) Setze k := k + 1 und gehe zu S1).
(4.4)
Es gilt ρk =
min |B(b − Az)|2 .
z∈x 0 +Vk
24
5 Iterative Lösungsverfahren: cg-Verfahren
Seien A, B ∈ RN×N symmetrisch und positiv definit.
S0) Wähle x 0 ∈ RN , ε > 0.
Berechne r 0 = b − Ax 0 , w 0 = Br 0 , ρ0 = (w 0 )T r 0 und d 1 = w 0 . Setze k = 0.
S1) Falls ρk ≤ ε
STOP
S2) Setze k := k + 1 und berechne
uk
=
Ad k
ρk −1
(u k )T d k
αk
=
xk
=
x k −1 + αk d k
r
k
=
r k −1 − αk u k
w
k
=
Br k
ρk
=
d k +1
=
(w k )T r k
ρ
wk + k dk
ρk −1
Gehe zu S1).
(4.5)
pκ(BA) − 1 k
Es gilt |x k − x|A ≤ 2 p
|x 0 − x|A .
κ(BA) + 1
25
6 Iterationsverfahren für nichtlineare Gleichungen
Sei F : RN −→ RN differenzierbar. Sei x ∗ ∈ RN eine Nullstelle von F (·), d.h. F (x ∗ ) = 0.
Dann gilt 0 = F (x) + DF (x)(x ∗ − x) + o(x ∗ − x).
Falls DF (x) invertierbar ist, gilt x ∗ = x − DF (x)−1 F (x) + o(x ∗ − x).
Falls DF (x ∗ ) invertierbar ist, ist x ∗ Fixpunkt von ΦF (x) = x − DF (x)−1 F (x), d.h. ΦF (x ∗ ) = x ∗ .
Newton-Verfahren: Wähle x 0 ∈ RN und definiere x k +1 = ΦF (x k ) für k = 0, 1, 2, ...
(6.1)
Sei DF (x ∗ ) invertierbar. Dann ist das Newton-Verfahren für alle x 0 hinreichend nahe bei x ∗
wohldefiniert, und x k konvergiert gegen x ∗ . Wenn zusätzlich F (·) glatt genug ist, ist die
Konvergenz quadratisch, d.h. es existiert C > 0 mit |x k +1 − x ∗ | ≤ C |x k − x ∗ |2 .
Wenn DF (x)−1 durch B ∈ RN×N approximiert wird, erhalten wir eine einfache
Fixpunktiteration mit ΦF ,B (x) = x − BF (x).
(6.2)
(6.3)
Sei ρ(IN − B DF (x ∗ )) < 1. Dann gilt: Für alle x 0 hinreichend nahe bei x ∗ konvergiert die
einfache Fixpunkt-Iteration x k +1 = ΦF ,B (x k ) linear gegen x ∗ .
Iterationsverfahren für nichtlineare Gleichungen mit Dämpfungsstrategie
S0) Wähle x 0 ∈ RN , θ ∈ (0, 1), smax ∈ N und ε > 0. Setze k = 0.
S1) Falls |F (x k )| ≤ ε STOP (Konvergenz)
S2) Wähle Bk ≈ DF (x k )−1 und berechne c k = −Bk F (x k ).
S3) Wähle tk ∈ {1, θ , θ 2 , ..., θ smax } mit |F (x k + tk ck )| < |F (x k )|.
Falls |F (x k + tk ck )| ≥ |F (x k )| für tk = θ smax STOP (keine Konvergenz)
S4) Setze x k +1 = x k + tk ck , k := k + 1 und gehe zu S1).
26
7 Polynom-Interpolation
(7.1)
Lagrange-Interpolation
Zu Stützstellen t0 < t1 < · · · < tN und Werten f0 , f1 , . . . , fN ∈ R
existiert genau ein Polynom P ∈ PN mit P(tn ) = fn .
N
Konstruktion: Definiere die Lagrange-Basis Ln (t) =
∏
k =0, k 6=n
(7.2)
t−tk
tn −tk
N
, setze P(t) = ∑ fn Ln (t).
n=0
Zu t0 ≤ t1 ≤ · · · ≤ tN definiere dn = max{n − k : tk = · · · = tn }.
dn
1
d
P(tn ) = fn .
dn ! dt
Hermite-Interpolation
Zu Werten f0 , f1 , . . . , fN ∈ R existiert genau ein Polynom P ∈ PN mit
Konstruktion: Zu t0 ≤ t1 ≤ · · · ≤ tN definiere die Newton-Basis durch
ω0 ≡ 1, ω1 (t) = t − t0 , ωk (t) = (t − tk −1 )ωk −1 (t) ∈ Pk ,
k = 1, . . . , N .
Nun definiere f [tn ] = fn und f [tk , . . . , tn ] = fn falls tk = tk +1 = · · · = tn .
Dann berechne rekursiv f [tk , . . . , tn ] =
f [tk +1 ,...,tn ]−f [tk ,...,tn−1 ]
tn −tk
.
N
Dann ist P(t) = ∑ f [t0 , . . . , tk ]ωk (t) das Interpolationspolynom.
k =0
Neville-Schema: Sei P0 ∈ Pn−k −1 Interpolation zu fk , ..., fn−1 an tk ≤ · · · ≤ tn−1 , und sei
P1 ∈ Pn−k −1 Interpolation zu fk +1 , ..., fn an tk +1 ≤ · · · ≤ tn . Dann ist
k P (t) + tn −t P (t) Interpolation zu f , ..., f an t ≤ · · · ≤ t .
P(t) = tt−t
n
n
1
0
k
k
tn −t
n −t
k
(7.3)
k
Sei f ∈ C N+1 (a, b), t, tn ∈ (a, b), und fn =
Interpolationsfehler f (t) − PN (t) =
1
(N+1)!
1
dn !
dn
d
dt
N+1
d
dt
f (tn ). Dann gilt für den
f (τ) ωN+1 (t) mit τ ∈ (a, b).
27
Runge-Phänomen bei Interpolation
Wir betrachten das Interpolationsproblem für äquidistant
verteilte Stützstellen.
Wir
würden erwarten, dass für
eine genügend glatte Funktion
die Folge der Interpolationspolynome, gehörig zu immer
kleinerem Stützstellenabstand,
in der Maximumsnorm gegen
die Funktion konvergiert. Dass
dem nicht so ist zeigt zum
Beispiel das sogenannte RungePhänomen für die Funktion
f : [−5, 5] → R,
f (x) :=
1
.
1 + x2
Der maximale Fehler wird hier sogar immer größer, je höher der Grad des
Interpolationspolynoms ist. Für den Grad 10 ist das zugehörige Interpolationspolynom
eingezeichnet. Der Fehler wird offenbar durch die starke Oszillation verursacht, dies
verschlimmert sich noch mit steigendem Polynomgrad.
28
Das Neville-Schema – Berechnung der Koeffizienten
function f = coeff(t,f)
N = length(t);
for k=1:N-1
for n=N:(-1):k+1
if t(n) ~= t(n-k)
f(n) = (f(n) - f(n-1)) / (t(n) - t(n-k));
end
end
end
return
function y = eval_newton(t,b,x)
N = length(t);
y = b(1);
p = 1;
for n=2:N
p = p * (x - t(n-1));
y = y + b(n) * p;
end
return
29
Neville-Schema – Auswertung des Polynoms
function y = eval_neville(t,f,x)
N = length(t);
for k=1:N-1
for n=N:(-1):k+1
if t(n) ~= t(n-k)
f(n) = ((x-t(n-k))*f(n)+(t(n)-x)*f(n-1)) / (t(n)-t(n-k));
end
end
end
y = f(N);
return
30
8 Spline-Interpolation
(8.1)
a) Zu einer Zerlegung ∆ : a = t0 < t1 < · · · < tN = b von [a, b] definiere den kubischen
Spline-Raum
S3 (∆) = S ∈ C 2 [a, b] : Sn := S|[tn−1 ,tn ] ∈ P3 ,
n = 1, . . . , N .
b) S ∈ S3 (∆) heißt interpolierender Spline zu f ∈ C 0 [a, b] wenn S(tn ) = f (tn ).
(8.2)
(8.3)
Es gilt dim S3 (∆) = 3 + N. Mit einer der Randbedingungen
(I)
Natürliche Randbedingung
S 00 (a) = 0 und S 00 (b) = 0
(II)
Hermite-Randbedingung zu f ∈ C 1 [a, b]
S 0 (a) = f 0 (a) und S 0 (b) = f 0 (b)
(III)
Periodische Randbedingungen
S 0 (a) = S 0 (b) und S 00 (a) = S 00 (b)
ist die Spline-Interpolation S ∈ S3 (∆) zu f eindeutig lösbar.
Die Momente Mn = S 00 (tn ) von S ∈ S3 (∆) zu f sind eindeutig durch
µn Mn−1 + Mn + λn Mn+1 = 3f [tn−1 , tn , tn+1 ]
und µn =
hn
,
2(hn + hn+1 )
Sn (t)
(8.4)
=
λn =
hn+1
bestimmt und es gilt
2(hn + hn+1 )
Mn (t − tn−1 )3 + Mn−1 (tn − t)3 f (tn ) + f (tn−1 ) hn2
+
−
(Mn + Mn−1 )
6hn
2
12
f (t ) − f (t ) h
tn + tn−1
n
n
n−1
+
− (Mn − Mn−1 ) t −
.
hn
6
2
Sei f ∈ C 4 [a, b]. Dann gilt für die Spline-Interpolation
kS − f k∞ ≤ h4 kf 0000 k∞ .
31
Spline-Interpolation mit Matlab
n = 7;
x = rand(n,1);
y = rand(n,1);
plot(x,y,’.’)
axis([-0.1 1.1 -0.1 1.1]);
t = 1:n;
ts = 1:1/10:n;
xs = spline(t,x,ts);
ys = spline(t,y,ts);
hold on;
plot(xs,ys,’r’);
hold off;
32
9 Trigonometrische Interpolation und FFT
(9.1)
Sei f : R −→ C eine 2π-periodische stetige Funktion und N = 2P . Sei tn = n
Dann existiert genau ein trigonometrisches Interpolationspolynom
2π
und fn = f (tn ).
N
N−1
TN (t) =
∑ cn exp(int) ,
cn ∈ C
n=0
mit TN (tn ) = fn für n = 0, ..., N − 1. Es gilt
ck =
1
N
N−1
∑ fn ω −kn ,
ω = exp(i2π/N) .
n=0
Die Koeffizienten lassen sich rekursiv mit O(N log N) Operationen berechnen:
N−1
N/2−1
n=0
m=0
∑ fn ω −kn = ∑
N/2−1
f2m ξ −km + ω −1
∑
f2m+1 ξ −km ,
ξ = ω2 .
m=0
Für s-mal stetig differenzierbare Funktionen konvergieren die Koeffizienten cn gegen die
Fourier-Koeffizienten
Z
1 2π
f̂k =
f (t) exp(ikt) dt ,
2π 0
und es existiert eine Konstante Cs > 0 mit
Z 2π
1/2
d s
kf − TN kL2 (0,2π) ≤ Cs N −s k
f kL2 (0,2π) ,
kgkL2 (0,2π) =
|g(t)|2 dt
.
dt
0
33
FFT mit Matlab
Fs = 1000;
% Sampling frequency
T = 1/Fs;
% Sample time
L = 1000;
% Length of signal
t = (0:L-1)*T; % Time vector
% Sum of a 50 Hz sinusoid and
%
a 120 Hz sinusoid
x = 0.7*sin(2*pi*50*t)+sin(2*pi*120*t);
y = x+2*randn(size(t)); % plus noise
plot(Fs*t(1:50),y(1:50))
title(’Signal Corrupted Random Noise’)
xlabel(’time (milliseconds)’)
NFFT = 2^nextpow2(L);
% Next power of 2 from length of y
Y = fft(y,NFFT)/L;
f = Fs/2*linspace(0,1,NFFT/2+1);
% Plot single-sided amplitude spectrum.
plot(f,2*abs(Y(1:NFFT/2+1)))
title(’Single-Sided Amplitude Spectrum of y(t)’)
xlabel(’Frequency (Hz)’)
ylabel(’|Y(f)|’)
34
10 Numerische Integration
(10.1)
Sei [a, b] ⊂ R ein Intervall, und sei Ξ ⊂ [a, b] eine endliche Menge mit #Ξ = N.
Dann existiert genau eine Quadratur
QΞ : C[a, b] −→ R ,
QΞ (f ) =
∑ ωξ f (ξ )
ξ ∈Ξ
mit Gewichten ωξ ∈ R zu den Stützstellen ξ ∈ Ξ, die für Polynome vom Grad N − 1 exakt ist:
QΞ (P) =
Z b
a
P(t) dt ,
P ∈ PN−1 .
Konstruktion: Sei Lξ (t) = ∏η∈Ξ\{ξ }
t−η
.
ξ −η
Dann gilt ωξ =
Rb
a
Lξ (t) dt.
Es gibt keine Quadratur QΞ mit #Ξ = N, die für Polynome P ∈ P2N exakt ist.
Es gibt genau eine Quadratur GN mit N Stützstellen, die für Polynome P ∈ P2N−1 exakt ist.
R
Wähle dazu die Nullstellen des Orthogonalpolynoms LN ∈ PN bzgl. (f , g) = ab f (t)g(t) dt.
(10.3) Sei QΞ eine Quadratur, die für Polynome P ∈ PK −1 exakt ist. Dann existiert C > 0 mit
Z b
d K f (t) dt ≤ C f
QΞ (f ) −
dt
∞
a
(10.2)
(10.4)
Für die summierte Trapezregel
1
M−1
1
TM (f ) = h f (a) + ∑ f (a + mh) + f (b)
2
2
m=1
Rb
2
00
gilt TM (f ) − a f (t) dt ≤ C h kf k∞ .
mit
h=
b−a
M
35
10 Extropolierte Trapezsummen (Romberg)
Die Trapezsummen lassen sich extrapolieren: Setze Tk 0 = T2k M (f ) und definiere rekursiv
1
(Tk ,i−1 − Tk −1,i−1 ),
i = 1, . . . , m und k = i, . . . , m .
4i − 1
ist für Polynome P ∈ P2k +1 exakt.
Tki = Tk ,i−1 +
Dann ist Tmk
Beispiel: Approximiere
Z 1
0
π
1
dt =
4
1 + t2
Neville-Schema zur Extrapolation von Tk 0 = T2k +4
T00
T01
T02
T03
= 0.785235403010347
= 0.785357473293744 T11 = 0.785398163388209
= 0.785387990871414 T12 = 0.785398163397304 T22 = 0.785398163397910
= 0.785395620265938 T13 = 0.785398163397446 T23 = 0.785398163397456 T33 = 0.785398163397449
Konvergenzabschätzung durch Vergleich von Trapezsummen
T01 − T00 = 0.00012207028
T02 − T01 = 0.00003051757 T12 − T11 = 0.0000000000090942
T03 − T02 = 0.00000762939 T22 − T12 = 0.0000000000001426
Fehler
T00 −
T01 −
T02 −
T03 −
π
4
π
4
π
4
π
4
= −0.00016276038
= −0.00004069010 T11 −
= −0.00000101725 T12 −
= −0.00000025431 T13 −
π
4
π
4
π
4
= −9.2390539e − 12
= −1.4477308e − 13
= −2.1094237e − 15
T22 −
T23 −
π
4
π
4
= 4.6151971e − 13
= 7.4384942e − 15
T33 − π4 = 2.2204460e − 16
36
11 Numerische Integration von Differentialgleichungen
(11.1)
(11.2)
Sei t0 ∈ R und T > 0. Zu einem Anfangswert u0 ∈ RM und f ∈ C([t0 , t0 + T ] × RM , RM ) suchen
wir eine Lösung u ∈ C 1 ([t0 , t0 + T ], RM ) der Anfangswertaufgabe
u̇(t) = f t, u(t) für t ∈ [t0 , t0 + T ]
und dem Anfangswert u(t0 ) = u0 .
Wenn L > 0 existiert
mit |f (t, w) − f (t,
z)| ≤ L |w − z|, dann gilt für zwei Lösungen
u̇(t) = f t, u(t) und v̇ (t) = f t, v (t)
|u(t) − v (t)| ≤ exp(L(t − t0 )) |u(t0 − v (t0 )|
für t ≥ t0 .
Daher ist die Lösung der Anfangswertaufgabe eindeutig.
(11.3)
Klassisches Runge-Kutta-Verfahren: Sei tn = t0 + nτ, u 0 = u0 und setze
f (tn−1 , u n−1 )
τ
τ
k2 = f (tn−1 + , u n−1 + k1 )
2
2
τ
τ
k3 = f (tn−1 + , u n−1 + k2 )
2
2
k4 = f (tn−1 + τ, u n−1 + τk3 )
τ
u n = u0n−1 + (k1 + 2k2 + 2k3 + k4 ) .
6
Dann gilt |u(tn ) − u n | ≤ C exp(L(tn − t0 )τ 4 .
k1
(11.3)
=
Implizites Euler-Verfahren: In jedem Schritt bestimme u n als Lösung der nichtlinearen
Gleichung u n = u n−1 + τf (tn , u n ). Dann gilt |u(tn ) − u n | ≤ C exp(L(tn − t0 )τ.
37
11 Simulation: Radioaktiver Zerfall u̇ = −λ u
N
exakt
explizites Eulerverfahren
u n = u n−1 + τf (u n−1 )
implizites Eulerverfahren
u n = u n−1 + τf (u n )
Mittelpunktsregel
u n = u n−2 + 2τf (u n−1 )
4
8
16
32
64
0.50000
0.50000
0.50000
0.50000
0.50000
0.46711
0.48431
0.49233
0.49621
0.49811
O(1/N)
0.52770
0.51440
0.50735
0.50371
0.50187
O(1/N)
0.51266
0.50323
0.50081
0.50020
0.50005
O(1/N 2 )
Table: Vergleich der Konvergenzordnung |c(tn ) − cn | = O(N −β ) = O(hN ) im Zeitintervall [0, 5730].
β
N =5
N = 100
Figure: Stabilität der numerischen Approximation. Vergleich im Zeitintervall [0, 57300] für N = 5, 100.
38
ODE mit Matlab
function vdpode(MU)
tspan = [0; max(20,3*MU)];
y0 = [2; 0];
options = odeset(’Jacobian’,@J);
[t,y] = ode15s(@f,tspan,y0,options);
figure;
plot(t,y(:,1));
title([’Solution of van der Pol
Equation, \mu = ’ num2str(MU)]);
xlabel(’time t’);
ylabel(’solution y_1’);
axis([tspan(1) tspan(end) -2.5 2.5]);
function dydt = f(t,y)
dydt = [ y(2)
MU*(1-y(1)^2)*y(2)-y(1) ];
end
function dfdy = J(t,y)
dfdy = [ 0
1
-2*MU*y(1)*y(2)-1 MU*(1-y(1)^2)];
end
end
39

Kapitel in einem PDF

Transcrição

Documentos relacionados

Direkte numerische Simulation eines Helmholtzresonator

Numerische Methoden in der Finanzmathematik

29. Sitzung - an der Universität Duisburg

Programm - element—5

Protokoll CV-Stammtisch 12.08.2008

Städtisches Klinikum Karlsruhe

Jobben während des Studiums…

PDF / 414 KB - Stadt Bad Segeberg

PH Studi-News Ausgabe Februar 2014

AIT-Forscher als General Chair auf weltweit führender IEEE

HAFEN Kultur FEST - Rheinhäfen Karlsruhe

Prävention von und Intervention bei häuslicher Gewalt (Dr. Petra