{%hackmd @themes/dracula %}
<!---$\newcommand{\rg}{\text{rang}$--->

$\DeclareMathOperator{\rg}{rang}$

> Pratscher
> Schledorn
> Sergeyeva

| **1** | **2** | **3** | **4** |**5**| $\Sigma$ |
| :---: | :---: | :---: | :---: | :---: | :---:|
|</br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ |

# Aufgabe 8.1: Frobeniusnorm

Die Frobenius-Norm einer Matrix $A\in \mathbb{R}^{n\times n}$ ist definiert als
$||A||_F=(\sum\limits_{i,j=1}^n|a_{ij}|^2)^\frac12$
Zeigen Sie:

1) Die Frobenius-Norm definiert eine Norm auf $\mathbb{R}^{n\times n}$

2) Die Frobenius-Norm ist verträglich mit der euklidischen Vektornorm $||\cdot||_2$

3) Die Frobenius-Norm ist submultiplikativ.

4) Die Frobenius-Norm ist keine natürliche Matrixnorm

*Hinweis: Verwenden Sie die Cauchy-Shwarz-Ungleichung für die Teilaufgaben*

Definition Norm:
Sei $V$ ein Vektorraum über $\mathbb{R}$. Eine Abbildung $||\cdot||: V\to \mathbb{R}_+=\{x\in\mathbb{R}:x\geq 0\}$ heißt **Norm** auf $V$, falls gilt:
1) $||x|| >0$ falls $x\neq 0, x\in V$ (Definitheit)
2) $||\alpha x|| = |\alpha|||x||,x\in V, \alpha \in \mathbb{R}$ (positive Homogenität)
3) $||x+y||\leq ||x|| +||y||, x,y\in V$ (Dreiecksungleichung)

#### **zz: Die Frobenius-Norm definiert eine Norm auf $\mathbb{R}^{n\times n}$**

$||x|| >0$ falls $x\neq 0, x\in V$ (Definitheit)

Es handelt sich hier um die Summe von nicht-negativen Zahlen, welche per Definition somit auch nicht-negativ sein kann. Da $x\geq 0,~x\neq 0$ definiert ist, heißt dass das es Paare $(i,j)$ gibt mit $a_{ij}\neq 0$. Diese werden quadriert und sind somit ebenfalls nicht 0, jedoch sind diese zwagsweise dann positiv. Somit gilt dann auch die Definitheit

2) $||\alpha x|| = |\alpha|||x||,x\in V, \alpha \in \mathbb{R}$ (positive Homogenität)

$\begin{split}||\alpha x|| =& ||\alpha A ||_F \\=& (\sum\limits_{i,j=1}^n|\alpha a_{ij}|^2)^\frac12\\ =& (|\alpha|^2 \sum\limits_{i,j=1}^n|a_{ij}|^2)^\frac12\\ =& |\alpha| (\sum\limits_{i,j=1}^n |a_{ij}|^2)^\frac12\\ =& |\alpha| \cdot || A||_F \\=& |\alpha|\cdot ||x||\end{split}$

3) $||x+y||\leq ||x|| +||y||, x,y\in V$ (Dreiecksungleichung)

**Minkoswki-Ungleichung:**
$(\sum\limits_{i,j=1}^n|a_{ij}+b_{ij}|^2)^\frac12\leq(\sum\limits_{i,j=1}^n(|a_{ij}|+|b_{ij}|)^2)^\frac12$

$\begin{split}||A+B||_F=&(\sum\limits_{i,j=1}^n|a_{ij}+b_{ij}|^2)^\frac12\\
=&(\sum\limits_{i,j=1}^n|a_{ij}|^2+2\cdot \sum\limits_{i,j=1}^n|a_{ij}b_{ij}|+\sum\limits_{i,j=1}^n|b_{ij}|^2)^\frac12\\
=&(\sum\limits_{i,j=1}^n|a_{ij}|^2+2\cdot ((\sum\limits_{i,j=1}^n |a_{ij}|^2)^\frac12\cdot (\sum\limits_{i,j=1}^n|b_{ij}|^2)^\frac12+\sum\limits_{i,j=1}^n|b_{ij}|^2)^\frac12\\
\leq& (||A||_F^2+2||A||_F||B||_F+||B||_F^2)^\frac12\\
=&(||A||_F+||B||_F)²
\end{split}$

#### 2. Verträglichkeit mit der euklidischen $||\cdot ||_2$

zz: $||Ax||_2\leq C||A||_F||x||_2$

$||Ax||_2^2$:

$||Ax||_2^2 = (Ax)^T (Ax) = x^T A^T A x$

Da $A^T A$ eine symmetrische, positive semidefinite Matrix ist, können wir die Spektralnorm $||A||_2$ verwenden. Diese ist durch die Frobenius-Norm nach oben beschränkt:

$||A||_2 \leq ||A||_F$

Somit gilt:

$||Ax||_2 \leq ||A||_2 ||x||_2 \leq ||A||_F ||x||_2$

#### 3. Die Frobenius-Norm ist submulitplikativ

$||AB||_F^2 = \sum_{i,j=1}^n |(AB)_{ij}|^2$

Der Eintrag $(AB)_{ij}$ ist gegeben durch:

$(AB)_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$

Anwendung Cauchy-Schwarz-Ungleichung

$|(AB)_{ij}|^2 = \left| \sum_{k=1}^n a_{ik} b_{kj} \right|^2 \leq \left( \sum_{k=1}^n |a_{ik}|^2 \right) \left( \sum_{k=1}^n |b_{kj}|^2 \right)$

$\sum_{i,j=1}^n |(AB)_{ij}|^2 \leq \sum_{i,j=1}^n \left( \sum_{k=1}^n |a_{ik}|^2 \right) \left( \sum_{k=1}^n |b_{kj}|^2 \right)$

Da die Summation über $i$ und $j$ unabhängig voneinander ist, können wir die Summe aufteilen:

$\sum_{i=1}^n \left( \sum_{j=1}^n |(AB)_{ij}|^2 \right) \leq \sum_{i=1}^n \left( \sum_{k=1}^n |a_{ik}|^2 \right) \left( \sum_{j=1}^n |b_{kj}|^2 \right)$

$\implies$

$||AB||_F^2 \leq \left( \sum_{i,k=1}^n |a_{ik}|^2 \right) \left( \sum_{k,j=1}^n |b_{kj}|^2 \right) = ||A||_F^2 ||B||_F^2$

$\implies$ Wurzelziehen

$||AB||_F \leq ||A||_F ||B||_F$

#### 4. Die Frobenius-Norm ist keine natürliche Matrixnorm

Eine natürliche Matrixnorm $||\cdot ||$ erfüllt die Bedingung $||\mathbb{1}||=1$. Für die Frobenius Norm gilt:

$||\mathbb{1}||_F=(\sum\limits_{i,j=1}^n|\mathbb{1}_{ij}|²)^\frac12=(\sum\limits_{i=1}^n1^2)^\frac12=\sqrt{n}\neq 1$

# Aufgabe 8.2: Sherman-Morrison-Formel

#### 1.) Es seien Vektoren $u\neq 0\in \mathbb{R}^n,v\neq 0 \in \mathbb{R}^n$ gegeben. Zeigen Sie, dass die Matrizen $uv^T\in \mathbb{R}^{n\times n}$ und $vu^T \in \mathbb{R}^{n\times n}$ Rang 1 haben.

Seien $u,v\in\mathbb{R}^n$ und es gelte $u,v\neq 0$. Wir bezeichnen die Matrizen $uv^T$ und $vu^T$ mit $A$ und $B$. Dann gilt:
$A_{ik}=\sum_{j=1}^ma_{ij}\cdot b_{jk}$.
Da die Vektoren beide $\neq0$ sind gilt für ihren Rang:
$\rg(u)=\rg(v)=1$. Aus der linearen Algebra wissen wir, dass $\rg(u)=\rg(u^T)$ gilt.
Nach der Rangungleichhung von Sylvester wissen wir das für 2 Matrizen $C\in m \times n$ und $C'\in n\times l,$ $\rg (C ) + \rg(C') -n \leq \rg(A\cdot B) \leq \min(\rg(C), \rg(B))$ gelten muss.
Für $A\in \mathbb{R}^{n\times n}$ gilt daher:
$\rg (u) + \rg(v^T) -n \leq \rg(u\cdot v^T) \leq \min(\rg(u), \rg(v^T))$. Wir haben nun also obere und untere Grenzen für den rang(A) vorgegeben. Für die untere Schranke gilt also, $\rg(u)+\rg(v^T)-n=1$, für die obere Schranke gilt: $\min(\rg(u),\rg(v))=1$. Damit gilt für den Rang von A:
$\rg(A)=1$

#### 2.) Beweisen Sie die Sherman-Morrison-Formel:
Sei $A\in \mathbb{R}^{n\times n}$ regulär, $u,v\in \mathbb{R}^n$ und $1+v^TA^{-1}u\neq 0$. Dann gilt
$(A+uv^T)^{-1}=A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

Sei $A$ eine reguläre Matrix, und $u,v\in \mathbb{R}^n$ und $1+v^TA^{-1}u\neq0$, dann können wir für beliebiges $u$ und $A$ ein $w\in \mathbb{R}^n$ finden, sodass gilt:
$u=Aw$.
Daraus folgt:
$A+uv^T=A+Awv^T=A(I+wv^T)$, mit $I$ der Einheitsmatrix.
Da die Matrix $A$ regulär ist, ist sie invertierbar. Für ihr Inverses gilt dann:
$(A+uv^T)^{-1}=(I+wv^T)^{-1}A^{-1}=(I-\frac{wv^T}{1+v^Tw})A^{-1}$
Wenn wir jetzt $u=Aw$ Rücksubstituieren ergibt sich:
$(A+uv^T)^{-1}=(I-\frac{A^{-1}uv^T}{1+v^TA^{-1}u})A^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$

# Aufgabe 8.3: LR-Zerlegung

Gegeben sei das Gleichungssystem $Ax=b$ mit
$A=\begin{pmatrix}0&-4&10&\frac{15}{2}\\-2&6&3&10\\2&-6&7&-\frac{11}{2}\\ -2&10&12&0\end{pmatrix}, b=\begin{pmatrix}52\\59\\-11\\-18\end{pmatrix}$

a.) Berechnen Sie mit angegebenen Rechenweg die LR-Zerlegung von $A$ mit Spaltenpivotisierung. Um den Tutoren die Arbeit etwas zu erleichtern wählen Sie bitte diese Pivotisierung:
$P=\begin{pmatrix}0&1&0&0\\1&0&0&0 \\0&0&1&0\\0&0&0&1\end{pmatrix}$

Bestimmen Sie nun die Determinante von $A$ sowie die Matrix $A^{-1}$ und lösen Sie $Ax=b$

$P\cdot A=\begin{pmatrix}0&1&0&0\\1&0&0&0 \\0&0&1&0\\0&0&0&1\end{pmatrix}\cdot \begin{pmatrix}0&-4&10&\frac{15}{2}\\-2&6&3&10\\2&-6&7&-\frac{11}{2}\\ -2&10&12&0\end{pmatrix}=\begin{pmatrix}-2&6&3&10\\0&-4&10&\frac{15}{2}\\2&-6&7&-\frac{11}{2}\\ -2&10&12&0\end{pmatrix}$

$P\cdot A= L \cdot R$

#### 1. Schritt - Elimination

$\begin{pmatrix}-2&6&3&10\\0&-4&10&\frac{15}{2}\\2&-6&7&-\frac{11}{2}\\ -2&10&12&0\end{pmatrix}\text{ mit }\begin{matrix}L_{21}=-\frac{U_{21}}{U_{11}}=-\frac{0}{-2}=-0 \\ L_{31}=-\frac{U_{31}}{U_{11}}=-\frac{2}{-2}=1\\ L_{41}=-\frac{U_{41}}{U_{11}}=-\frac{-2}{-2}=-1 \end{matrix}$

$L_1=\begin{pmatrix}1&0&0&0\\0&1&?&?\\ 1&?&1&?\\-1&?&?&1 \end{pmatrix}$

$L_1\tilde A^{(1)}=\begin{pmatrix}-2&6&3&10\\0&-4&10&\frac{15}{2}\\0&0&10&\frac{9}{2}\\ 0&4&9&-10\end{pmatrix}$

#### 2. Schritt - Elimination
$P_2=\begin{pmatrix}1&0&0&0\\0&0&0&1 \\0&0&1&0\\0&1&0&0\end{pmatrix}$

$\begin{pmatrix}-2&6&3&10\\0&4&9&-10\\
0&0&10&\frac{9}{2}\\ 0&-4&10&-\frac{15}{2}\end{pmatrix}\text{ mit }\begin{matrix} L_{32}=\frac{U_{32}}{U_{22}}=\frac{0}{4}=-0\\L_{42}=-\frac{U_{42}}{U_{22}}=-\frac{-4}{4}=1 \end{matrix}$

$L_2=\begin{pmatrix}1&0&0&0\\0&1&?&?\\ 1&0&1&?\\-1&1&?&1 \end{pmatrix}$

$L_2\tilde A^{(2)}=\begin{pmatrix}-2&6&3&10\\0&4&9&-10\\
0&0&10&\frac{9}{2}\\ 0&0&19&-\frac{35}{2}\end{pmatrix}$

#### 3. Schritt - Elimination

$P_3=\begin{pmatrix}1&0&0&0\\0&1&0&0 \\0&0&0&1\\0&0&1&0\end{pmatrix}$

$\begin{pmatrix}-2&6&3&10\\0&4&9&-10\\
0&0&10&\frac{9}{2}\\ 0&0&19&-\frac{35}{2}\end{pmatrix}\text{ mit } \begin{matrix}L_{43}=-\frac{U_{43}}{U_{33}}=-\frac{19}{10}\end{matrix}$

$L_3=\begin{pmatrix}1&0&0&0\\0&1&0&0\\ 1&0&1&0\\-1&1&-\frac{19}{10}&1 \end{pmatrix}$

$L_3\tilde A^{(3)}=\begin{pmatrix}-2&6&3&10\\0&4&9&-10\\
0&0&10&\frac{9}{2}\\ 0&0&0&-\frac{521}{20}\end{pmatrix}=R$

$L=\begin{pmatrix}1&0&0&0\\0&1&0&0\\ 1&0&1&0\\-1&1&-\frac{19}{10}&1 \end{pmatrix}$

#### Determinante
Die Determinante von $A$ ist das Produkt der Diagonalelemente von $R$:
$\det(A) = (-2) \cdot 4 \cdot 10 \cdot \left( -\frac{521}{20} \right) = 2084$

#### Inverse

Um die Inverse von $A$ zu berechnen, verwenden wir die LR-Zerlegung und lösen $Ax = \mathbb{1}$ für jede Spalte des Einheitsmatrix $I$. Dies wird durch Vorwärts- und Rückwärtseinsetzen durchgeführt.
### Lösung des Gleichungssystems \(Ax = b\)

$P_b = \begin{pmatrix} 59 \\ 52 \\ -11 \\ -18 \end{pmatrix}$

2. Vorwärtseinsetzen: $Ly = Pb$
$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ -1 & 1 & -1.9 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{pmatrix} = \begin{pmatrix} 59 \\ 52 \\ -11 \\ -18 \end{pmatrix}$

$y_1=59$
$y_2=52$
$y_3=59-11=48$
$y_4=-59+52+20.9-18=-4.1$

3. Rückwärtseinsetzen: $Rx = y$
$\begin{pmatrix} -2 & 6 & 3 & 10 \\ 0 & 4 & 9 & -10 \\ 0 & 0 & 10 & \frac{9}{2} \\ 0 & 0 & 0 & -\frac{521}{20} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 59 \\ 52 \\ 48 \\ 4.1 \end{pmatrix}$

$x_4= −0.1574$
$x_3= 48-\frac92\cdot −0.1574=48.7083$
$x_2=\frac14 \cdot(52-(9\cdot 48.7083)-(-10\cdot −0.1574))=−96.20025$
$x_1=-\frac12\cdot(59-(6\cdot −96.20025)-(3\cdot 48.7083)-(10\cdot −0.1574)=−245.82585$

>berechnung inverse fehlt

b.) Berechnen Sie die Konditionszahlen $cond_2(A)$ und $cond_\inf(A)$

:::danger
todo
:::

# Aufgabe 8.4: Eigenschaften der LR-Zerlegung

a.) Zeigen Sie, dass die Menge der unteren Dreiecksmatrizen mit lauter Einsen auf der Hauptdiagonalen eine Untergruppe der invertierbaren Matrizen bilden (mit Matrixmulitplikation als Verknüpfung)

zu zeigen:

1. $L$ unter der Matrixmultiplikation abgeschlossen ist.
2. $L$die Identitätsmatrix enthält.
3. Zu jeder Matrix $L \in L$ existiert eine Inverse $L^{-1} \in L$.

**1. Abgeschlossenheit:**

Seien $L_1, L_2 \in L$. Dann sind $L_1$ und $L_2$ untere Dreiecksmatrizen mit Einsen auf der Hauptdiagonalen. Betrachten wir das Produkt $L_1 L_2$.

Da beides untere Dreiecksmatrizen sind, ist das Produkt $L_1 L_2$ ebenfalls eine untere Dreiecksmatrix. Zudem haben beide Einsen auf der Hauptdiagonalen. Die Hauptdiagonale von $L_1 L_2$ ist somit:

$(L_1 L_2)_{ii} = \sum_{k=1}^n (L_1)_{ik} (L_2)_{ki} = (L_1)_{ii} (L_2)_{ii} = 1 \cdot 1 = 1$

Somit ist $L_1 L_2$ ebenfalls eine untere Dreiecksmatrix mit Einsen auf der Hauptdiagonalen, d.h. $L_1 L_2 \in L$. Die Menge $L$ ist also unter der Matrixmultiplikation abgeschlossen.

**2. Identitätselement:**

Die Identitätsmatrix $I \in \mathbb{R}^{n \times n}$ ist eine untere Dreiecksmatrix mit Einsen auf der Hauptdiagonalen, also $I \in L$.

**3. Inverses Element:**

Sei $L \in L$. Da $L$ eine untere Dreiecksmatrix mit Einsen auf der Hauptdiagonalen ist, ist $L$ invertierbar, und ihre Inverse $L^{-1}$ ist ebenfalls eine untere Dreiecksmatrix (weil die Inverse einer unteren Dreiecksmatrix wieder eine untere Dreiecksmatrix ist).

Sei $L = I + N$, wobei $N$ eine strikt untere Dreiecksmatrix ist (alle Einträge auf der Hauptdiagonalen sind Null).

Da $L$ invertierbar ist, existiert eine Potenzreihe für die Inverse:

$L^{-1} = (I + N)^{-1} = I - N + N^2 - N^3 + \cdots$

Da $N$ strikt untere Dreiecksmatrix ist, bleibt jede Potenz von $N$ strikt untere Dreiecksmatrix. Das bedeutet, dass $I - N + N^2 - N^3 + \cdots$ ebenfalls eine untere Dreiecksmatrix mit Einsen auf der Hauptdiagonalen ist.

Damit ist $L^{-1} \in L$.

b.) Zeigen Sie: Wenn eine LR-Zerlegung $A=LR$ (ohne Permutation) existiert, so ist diese eindeutig.

Sei $A=\tilde A\tilde R$ eine weiere LR-Zerlegung von $A$. Dann ist $LR=\tilde L \tilde R$ und somit $\tilde L^{-1}L=\tilde R R^{-1}$. $\tilde L^{-1}L$ und $\tilde R R^{-1}$ mit $\tilde L^{-1}L$ als untere Dreiecksmatrix und $\tilde R R^{-1}$ als obere Dreiecksmatrix, weshalb gilt:
$\tilde L^{-1}L=\tilde R R^{-1}=\mathbb{1}_N$, weswegen $L=\tilde L$ und $R=\tilde R$ und somit ist die LR-Zerlegung eindeutig.