Blatt 05, 22.05.2019¶

Aktivieren Sie wie gewohnt ihre Arbeitsumgebung und starten Sie den Jupyter Notebook server, siehe zB Blatt 1, Aufgabe 0.
Erstellen Sie ein neues Python 3 Notebook oder laden Sie dieses von der Homepage herunter.
Importieren Sie numpy und pymor.basic und machen Sie matplotlib für das Notebook nutzbar.

Kopieren Sie alle benötigten Bestandteile für die Diskretisierung von Blatt 4 Aufgabe 2 und nennen Sie die Diskresierung d. Vergessen Sie nicht den ParameterSpace.

Erstellen Sie analog zu Blatt 04 Aufgabe 2 ein VectorArray $U$, das aus 30 zufälligen Lösungen besteht.

Aufgabe 1: Orthogonale Projektionen¶

Wir wollen nun den Begriff der Orthogonalen Projektionen behandeln.

Sei dafür $U$ ein beliebiges VectorArray und $V$ ein VectorArray gleicher Dimension der Länge 1. Sei außerdem $v_{proj}$ die orthogonale Projektion von $v$ auf den von den Vektoren in $U$ aufgespannten Vektorraum. Dann ist $v - v_{proj}$ orthogonal zu diesem Raum und insbesondere zu jedem Vektor aus $U$. Sind $u_i$, $i = 1, \ldots, N$ die Vektoren in $U$, so gilt also:

$$(v - v_{proj}, u_i) = 0, \qquad i = 1, \ldots, N.$$

Sind nun $\lambda_j$, $j = 1, \ldots, N$ die Koeffizienten von $v_{proj}$ bezüglich der $u_j$ basis, d.h. $\sum_{j=1}^N \lambda_j u_j = v_{proj}$, so folgt:

$$ \sum_{j=1}^N \lambda_j (v_i, v_j) = (v, u_i), \qquad i = 1, \ldots, N.$$

Setzten wir $M_{i,j} := (v_i, v_j)$, $R := [(v, u_1), \ldots, (v, u_N)]^T$ und $\Lambda := [\lambda_1, \ldots, \lambda_N]^T$, so erhalten wir das lineare Gleichungssystem

$$ M \cdot \Lambda = R,$$

mit dem wir die Koeffizienten $\lambda_i$ und somit $v_{proj}$ bestimmen können.

Assemblieren und Lösen Sie für das Vectorarray $U$ von Blatt 4 Aufabe 2 und ein Vectorarray $V$, welches eine weitere Lösung von d enthält. Hinweis: Benutzen Sie die gramian-Methode für die Matrix $M$.

Formen Sie die Linearkombination der Koeffizienten mit den Basisvektoren in $U$ um $v_{proj}$ zu berechnen.

Visualisieren Sie das Ergebnis zusammen mit $V$. Visualisieren Sie auch den Projektionsfehler.

Wiederholen Sie 1.-3. für die $H^1_0$-Projektion auf $U$. Hinweis: Benutzen Sie das entsprechende Produkt aus d.

Berechnen Sie die Euklidische, $H^1_0$, sowie $L^2$ Norm für beide Projektionsfehler

Erstellen Sie nun einen VectorArray V mit 100 zufällig gewählten Lösungen von d.

Berechnen Sie für $V$ die maximalen Projektionsfehler auf die ersten $N$ Vektoren in U.
- Hinweis: Die Berechnung der Projektions-Matrix und rechten Seite für verschiedene Basisgrößen können wir optimieren, indem wir diese zunächst für die volle Basis berechnen und dann entsprechend ausschneiden. Wie bei Numpy-Arrays können wir auch bei VectorArrays slicing verwenden. Dabei erhalten wir ebenfalls einen View in das Original-Array. Es wird kein Kopie der Daten erzeugt.

Plotten Sie die Projektionsfehler in Abhängigkeit von $N$ in einem semilog-plot.

Berechnen Sie die Kondition der Projektionsmatrizen in Abhängigkeit von $N$ und plotten Sie das Ergebnise

Aufgabe 3 Greedy Algorithmus¶

Der folgende Pseudocode definiert den Greedy-Algorithmus in der ursprünglichen Form.

Input: Menge von Vektoren $\mathcal{M} \subset V$, Ziel-Basisgröße $N$. Output: Basis $b_1, \dots, b_N$

$\texttt{for } n:=1 \texttt{ to } N:$ $$ \hspace{-10em} b_n := \text{argmax}_{m \in \mathcal{M}} \Vert m - P_{\text{span}(b_1,\dots,b_n)}(m) \Vert$$ $\texttt{endfor}$

Implementieren Sie den oben definierten Greey-Algorithmus mit den folgenden Argumenten:
- Das VectorArray $\mathcal{M}$ welches eine Menge von Vektoren enthält.
- ein Skalarprodukt auf $V$.
- eine Ziel-Basisgröße $N$.

Hinweis: Wollen wir mit Hilfe eines Skalarprodukt-Operators Normen berechnen, können wir statt apply2 die pairwise_apply2-Methode verwenden, die gerade die Diagonale der von apply2 berechneten Matrix zurückliefert

Wenden Sie Ihren Algorithmus auf das VectorArray $U$ von oben mit $N=30$ und einem geeigneten Produkt an.

Berechnen Sie die Projektionsfehler und Konditionen wie in Aufgabe 1 Teilaufgabe 8. und 9. Vergleichen Sie das Ergebnis mit den Ergebnissen aus Aufabe 1.