LaTeX-examples/documents/Numerik/Klausur5/Aufgabe2.tex

\section*{Aufgabe 2}
Zeige die Aussage für $2\times2$ Matrizen durch Gauß-en mit
Spaltenpivotwahl.

\subsection*{Lösung}
\subsubsection*{Behauptung:}
Für alle tridiagonalen Matrizen gilt:
\begin{enumerate}
    \item[(i)] Die Gauß-Elimination erhält die tridiagonale Struktur
    \item[(ii)] $\rho_n(A) := \frac{\alpha_\text{max}}{\max_{i,j} |a_{ij}|} \leq 2$
\end{enumerate}

\subsubsection*{Beweis:}
\paragraph{Teil 1: (i)}
\begin{align}
    A &= \begin{gmatrix}[p]
        * & *       &        & \\
        * & \ddots  & \ddots & \\
          & \ddots  & \ddots &  * \\
          &         &   *    & *
        \rowops
            \add[\cdot \frac{-a_{21}}{a_{11}}]{0}{1}
        \end{gmatrix}
\end{align}

Offensichtlich ändert diese Operation nur Zeile 2. $a_{21}$ wird zu 0,
$a_{22}$ ändert sich irgendwie, alles andere bleibt unverändert.
Die gesammte Matrix ist keine tridiagonale Matrix mehr, aber die 
um Submatrix  in $R^{(n-1) \times (n-1)}$ ist noch eine.

Muss man zuvor Zeile 1 und 2 tauschen (andere Zeilen kommen nicht in
Frage), so ist später die Stelle $a_{21} = 0$, $a_{22}$ ändert sich
wieder irgendwie und $a_{23}$ ändert sich auch. Dies ändert aber nichts
an der tridiagonalen Struktur der Submatrix.

\paragraph{Teil 2: (ii) für $A \in \mathbb{R}^{2 \times 2}$}
Sei $\begin{pmatrix}a_{11} & a_{12}\\a_{21} & a_{22} \end{pmatrix} \in \mathbb{R}^{2 \times 2}$
beliebig. 

O.B.d.A sei die Spaltenpivotwahl bereits durchgeführt, also $|a_{11}| \geq |a_{21}|$.

Nun folgt:

\begin{align}
    \begin{gmatrix}[p]
        a_{11} & a_{12}\\
        a_{21} & a_{22}
        \rowops
        \add[\cdot \frac{-a_{21}}{a_{11}}]{0}{1}
    \end{gmatrix}\\
    \leadsto
    \begin{gmatrix}[p]
        a_{11} & a_{12}\\
        0      & a_{22} - \frac{a_{12} \cdot a_{21}}{a_{11}}
    \end{gmatrix}
\end{align}

Wegen $|a_{11}| \geq |a_{21}|$ gilt: 
\begin{align}
    \|\frac{a_{21}}{a_{11}}\| \leq 1
\end{align}

Also insbesondere

\begin{align}
    \underbrace{a_{22} - a_{12} \cdot \frac{a_{21}}{a_{11}}}_{\leq \alpha_\text{max}} \leq 2 \cdot \max_{i,j}|a_{ij}|
\end{align}

Damit ist Aussage (ii) für $A \in \mathbb{R}^{2 \times 2}$ gezeigt.

\paragraph{Teil 3: (ii) für allgemeinen Fall}

Aus Teil 2 folgt die Aussage auch direkt für größere Matrizen.
Der worst case ist, wenn man beim Addieren einer Zeile auf eine 
andere mit $\max_{i,j}|a_{ij}|$ multiplizieren muss um das erste nicht-0-Element
der Zeile zu entfernen und das zweite auch $\max_{i,j}|a_{ij}|$ ist.
Dann muss man aber im nächsten schritt mit einem Faktor $\leq \frac{1}{2}$
multiplizieren, erhält also nicht einmal mehr $2 \cdot \max_{i,j}|a_{ij}|$.