Blatt 10

M ATHEMATISCHES I NSTITUT
38
P ROF. D R . ACHIM S CH ÄDLE
A NDREAS T ROLL
39
40
41
42
Σ
N AME :
M AT- NR .:
06.01.2016
N AME :
M AT- NR .:
Numerik II – 10. Übungsblatt
G RUPPE :
Aufgabe 38:
(a) Es sei A ∈ Rn×n eine Matrix vom Rang m. Zeigen Sie, dass Matrizen X, Y ∈ Rn×m existieren,
so dass A = XY T gilt.
(b) Es seien A und I + Y T A−1 X regulär. Beweisen Sie die Sherman–Morrison–Woodbury–Formel
(A + XY T )−1 = A−1 − A−1 X(I + Y T A−1 X)−1 Y T A−1 .
(c) Es seien X, Y ∈ Rn×m , n ≥ m sowie eine reguläre Matrix A ∈ Rn×n gegeben. Zeigen Sie, dass
die Matrix A + XY T genau dann regulär ist, wenn I + Y T A−1 X regulär ist.
Aufgabe 39:
Bei der Wahl der Startmartizen B0 = CC T und B̃0 = I in den BFGS-Algorithmen aus der Vorlesung
gilt für die Iterierten
xk = C x̃k + c
∀k
falls dies für die Startwerte (k = 0) gilt. (Das BFGS–Verfahren ist affin invariant.)
Aufgabe 40:
Geben sei f (x) = 12 xT Ax − xT b, mit einer symmetrischen positiv definiten Matrix A ∈ Rn×n und
Vektoren x, b ∈ Rn , sowie eine invertierbare Matrix C ∈ Rn×n und ein Vektor c ∈ Rn .
(a) Schreiben Sie den Algortithmus aus 2.14 (Quasi-Newton-Verfahren) für die Minimierung von f
auf, wobei Sie die eindimensionalen Minimierungsprobleme exakt lösen und die BFGS-Formel
als Update für die Matrizen Bk verwenden.
(b) Schreiben Sie den Algortithmus aus 2.14 (Quasi-Newton-Verfahren) für die Minimierung von
f˜(x̃) := f (C x̃ + c) auf, wobei Sie die eindimensionalen Minimierungsprobleme exakt lösen und
ek verwenden.
die BFGS-Formel als Update für die Matrizen B
Hinweis: Dies ist keine Programmieraufgabe.
Aufgabe 41:
Zeigen Sie, dass die Inversen der Ak nach der DFP-Formel
Ak+1 = (I − γk yk sTk )Ak (I − γk sk ykT ) + γk yk ykT
mit γk =
1
ykT sk
die folgende Rekursion gilt:
−1
A−1
k+1 = Ak −
T −1
A−1
sk sTk
k yk yk Ak
+
−1
ykT sk
ykT Ak yk
Hinweis: Verwenden Sie die Sherman–Morrison–Woodbury–Formel
Bitte wenden
Aufgabe 42:
(alte Klausuraufgabe)
(a) Zeigen Sie, dass die Faltung mit einen Vektor linear ist, d.h. zeigen Sie, dass für einen Vektor
a ∈ Cn die Abbildung
Cn → Cn : x 7→ a ∗ x
linear ist.
(b) Stellen Sie für a = (−2, 1, 0, 0, 1, 3) und b = (0, 0, 1, 1, 0, 0) das zu a ∗ x = b gehörige lineare
Gleichungssystem auf.
(c) Geben Sie ein Verfahren (Pseudocode) an, um für gegebene a, b ∈ Cn , mit n = 2L , das Gleichungssystem
a∗x=b
schnell zu lösen. Falls das Gleichungssystem keine eindeutige Lösung hat, geben Sie eine Fehlermeldung aus.
Hinweis: Der k-te Eintrag der Faltung zweier (periodisch fortgesetzter) Vektoren u, v ∈ Cn ist
(u ∗ v)k =
n−1
X
uk−j vj
j=0
Abgabe der Übungsaufgaben am Mittwoch, 13. Januar 2016 zu Beginn der Vorlesung.

Download Report