\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ngerman}

\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\headsep}{0cm}
\setlength{\tabcolsep}{0.1cm}
\addtolength{\topmargin}{-1.5cm}

\begin{document}

  \section*{Numerik: "Ubungsblatt 3}  

  \begin{enumerate}

    \item % 1
    \begin{enumerate}
      \item % a
      Es ist zu zeigen, da"s 

      \begin{align*}
        \|A\| &= \max_{\mathbf{x} \ne 0}
                 \frac{\|A \mathbf{x}\|}{\|\mathbf{x}\|}\\
              &= \sqrt{\lambda_{max}}
      \end{align*}
      
      wobei $\lambda_{max}$ der gr"o"ste Eigenwert der Matrix $A^{T}A$
      ist. $\|A\|$ kann umgeformt werden zu

      \begin{align*}
        \|A\| &= \max_{\|\mathbf{x}\| = 1}
                 \|A \mathbf{x} \| \\
              &= \max_{\|\mathbf{x}\|=1}
                 \sqrt{(A \mathbf{x})^{T}(A \mathbf{x})} \\
              &= \max_{\|\mathbf{x}\|=1}
                 \sqrt{\mathbf{x}^{T} A^{T} A  \mathbf{x}} \mbox{. (*)}
      \end{align*}

      Die im Ausdruck (*) auftretende Matrix $A^{T}A$ mu"s aufgrund des
      Hinweises \emph{symmetrisch} sein. Daher gilt, da"s ihre
      Eigenwerte $\lambda_{i}$ reell sind. Die $n$
      zugeh"origen Eigenvektoren $\mathbf{y}_{i}$ mit $1 \le i \le n$
      bilden eine Orthonormalbasis des $\mathbb{R}^{n}$. Damit ist es
      nun m"oglich, einen beliebigen Vektor $\mathbf{x} \in \;
      \mathbb{R}^{n}$ eindeutig als Linearkombination der Eigenvektoren
      $\mathbf{y}_{i}$ darzustellen. Es ist also

      \begin{align*}
        \mathbf{x} &= \sum_{i=1}^{n} c_{i} \mathbf{y}_{i}
      \end{align*}

      und $\mathbf{x}^{T}A^{T}A\mathbf{x}$ kann damit umgeformt werden
      zu

      \begin{align*}
        \mathbf{x}^{T}A^{T}A\mathbf{x} &=
        \left( \sum_{i=1}^{n} c_{i} \mathbf{y}_{i} \right)^{T}A^{T}A
        \left( \sum_{j=1}^{n} c_{j} \mathbf{y}_{j} \right) \\
        \mbox{\footnotesize{($A^{T}A\mathbf{y}_{i} = \lambda_{i}
        \mathbf{y}_i$)}}
        &= \left( \sum_{i=1}^{n} c_{i} \mathbf{y}_{i} \right)^{T}
        \left( \sum_{j=1}^{n} c_{j} \lambda_{j}\mathbf{y}_{j} \right) \\
        \mbox{\footnotesize{($\mathbf{y}_{i}$ bilden Orthonormalbasis
        des $\mathbb{R}^{n}$, daher $\mathbf{y}_{i}^{T}\mathbf{y}_{j}=
        \delta_{ij}$)}}
        &= \sum_{i=1}^{n} c_{i}^{2} \lambda_{i} \mbox{.}
      \end{align*}

      Da weiter die Bedingung $\|\mathbf{x}\| = 1$ g"ultig sein mu"s,
      gilt f"ur die Matrixnorm

      \begin{align*}
        \|A\|
        &= \max_{\|\mathbf{x}\|=1}
        \sqrt{ \sum_{i=1}^{n} c_{i}^{2} \lambda_{i} } \\
        & \le \max_{\|\mathbf{x}\|=1}
        \sqrt{ \lambda_{max} \sum_{i=1}^{n} c_{i}^{2} } \\
        &= \sqrt{\lambda_{max}} \mbox{.}
      \end{align*}

      Echte Gleichheit wird erreicht, wenn $\mathbf{x} = \mathbf{y}_1$
      und $c_{1} = 1$, sowie $c_{2} = \ldots = c_{n} = 0$. Dann nimmt
      $\sqrt{\lambda_{max}}$ den maximalen Wert an und es ist

      \begin{align*}
        \|A\| &= \max_{\|\mathbf{x}\|=1} \|A \mathbf{x}\| \\
        &= \sqrt{\lambda_{max}} \mbox{,}
      \end{align*}

      wobei $\lambda_{max}$ der gr"o"ste Eigenwert von $A^{T}A$ ist.
      $\blacksquare$
      

      \item % b
      \emph{Orthogonale Matrizen} sind die reellen unit"aren Matrizen
      und haben daher unter anderem die Eigenschaft $A^{T} = A^{-1}$,
      aus der folgt, da"s $AA^{T} = A^{T}A = E$. Die
      \emph{Konditionszahl} $k(A)$ einer Matrix $A$ berechnet man
      "uber die Formel $k(A) = \|A\| \cdot \|A^{-1}\|$. Die
      \emph{Matrixnorm} $\|A\|$ einer Matrix $A$ ist gleich der
      Quadratwurzel des gr"o"sten Eigenwerts $\lambda_{max}$ der
      Matrix $A^{T}A$, es gilt also $\|A\| = \sqrt{\lambda_{max}}$.
      Aus den Eigenschaften der \emph{orthogonalen Matrizen} folgt nun,
      da"s die Matrix $A^{T}A = E$. Da der einzige Eigenwert des
      Operators $E$ (Identit"at) $\lambda = \lambda_{max} = 1$ ist,
      gilt f"ur alle \emph{orthogonalen Matrizen} $A$, da"s $\|A\| =
      \|A^{-1}\| = \sqrt{\lambda_{max}} = \sqrt{1} = 1$. Somit ist die
      \emph{Konditionszahl} einer \emph{orthogonalen Matrix} immer
      $k(A) = \|A\| \cdot \|A^{-1}\| = \sqrt{1} \cdot \sqrt{1} = 1$.
      $\blacksquare$
    \end{enumerate}

    \item % 2
    Sei der Vektor $\mathbf{b}$ der Zeilensummen der $n \times n$
    Vandermonde-Matrix $V$ definiert als

    \begin{align*}
      \mathbf{b} =
      \left(
        \begin{matrix}
          b_{1} \\          
          b_{2} \\
          \vdots \\
          b_{n}
        \end{matrix}
      \right)
      \mbox{.}
    \end{align*}
    
    Damit ergibt sich f"ur das $i$-te Element von $\mathbf{b}$ der Wert
    
    \begin{align*}
      b_{i} = \sum^{n-1}_{j = 0} (i+1)^{j} = \frac{(i+1)^{n} - 1}{i}
      \mbox{.}
    \end{align*}

    F"ur das Gleichungssystem $V\mathbf{x} = \mathbf{b}$ ergibt sich
    so die L"osung

    \begin{align*}
      \mathbf{x} = 
      \left(
        \begin{matrix}
          x_{1} \\
          x_{2} \\
          \vdots \\
          x_{n}          
        \end{matrix}
      \right)
      =
      \left(
        \begin{matrix}
          1 \\
          1 \\
          \vdots \\
          1          
        \end{matrix}
      \right)
      \mbox{.}
    \end{align*}
    
    \item % 3
    (Siehe Programm \texttt{vandermonde.m} im Anhang.) Mit Hilfe der
    eingebauten \textsf{Octave}-Funktion \texttt{cond()}\footnote{
    \texttt{cond()} berechnet die Konditionszahl mit 
    $\|A\| \cdot \|A^{-1}\|$.} ergibt sich  f"ur $n = 10$
    die Konditionszahl $2.6871 \times 10^{13}$ und f"ur $n = 20$ die
    Konditionszahl $3.0972 \times 10^{26}$.
  \end{enumerate}

\end{document}



















