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


%*** page setup *****************************************************

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


%*** document begins here *******************************************
\begin{document}

  % header (first page only)
  \begin{flushright}
    \fbox{\emph{"Ubungsgruppe Roland Eikemper,
                Mittwoch 13.15 Uhr - 14.00 Uhr,
                Raum H41/S8}} \\
  \end{flushright}
  
  \begin{flushright}
    Nils Gehlenborg (\emph{neil@mangojelly.org}) \\
  \end{flushright}

  % title (first page only)
  \section*{Numerik: "Ubungsblatt 5}
  

  \begin{enumerate}

    \item % 1
    Das Relaxationsverfahren $\mathbf{x_{k+1}} = \mathbf{x_{k}} + B (
    \mathbf{b} - A\mathbf{x_{k}} )$ ist konsistent\footnote{Konsistent
    bedeutet, da"s jeder Fixpunkt der Iteration schon eine L"osung von
    $A\mathbf{x} = \mathbf{b}$ ist.}, denn f"ur $\mathbf{x_{k}} =
    \mathbf{x_{f}}$ ($\mathbf{x_{f}}$ ist ein Fixpunkt der Iteration),
    gilt $\mathbf{x_{f}} = \mathbf{x_{f}}+ B( \mathbf{b} -
    A\mathbf{x_{f}} ) \Leftrightarrow \mathbf{0} = B( \mathbf{b} -
    A\mathbf{x_{f}} )$, und da $B$ nicht singul"ar ist, hat das
    Gleichungssystem $\mathbf{0} = B( \mathbf{b} - A\mathbf{x_{f}} )$
    die eindeutige L"osung $\mathbf{b} - A\mathbf{x_{f}} = \mathbf{0}$, 
    aus der folgt, da"s der Fixpunkt $\mathbf{x_{f}}$ eine L"osung von
    $A\mathbf{x} = \mathbf{b}$ ist. $\blacksquare$
    
    
    \item % 2
    Wenn es $N$ Seiten im World Wide Web gibt, dann hat die $N \times N$
    Google-Matrix $G = (g_{ij})$ die Form

    \begin{align*}
      G =
      \left(
      \begin{matrix}
        1 & 0 & \hdots & 0                & \hdots & 0 & 0 \\
        0 & 1 & \hdots & \frac{-d}{n_{k}} & \hdots & 0 & 0 \\
        \vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\
        0 & 0 & \hdots & 0                & \hdots & 1 & 0 \\
        0 & 0 & \hdots & \frac{-d}{n_{k}} & \hdots & 0 & 1 \\
      \end{matrix}
      \right) \mbox{.}
    \end{align*}

    Die transponierte Google-Matrix $G^{T} = (g_{ji})$ ist demnach von
    der Form
    
    \begin{align*}
      G^{T} =
      \left(
      \begin{matrix}
        1 & 0 & \hdots & 0 & 0 \\
        0 & 1 & \hdots & 0 & 0 \\
        \vdots & \vdots & \ddots & \vdots & \vdots \\
        0 & \frac{-d}{n_{k}} & \hdots & 0 & \frac{-d}{n_{k}} \\
        \vdots & \vdots & \ddots & \vdots & \vdots \\
        0 & 0 & \hdots & 1 & 0 \\
        0 & 0 & \hdots & 0 & 1 \\
      \end{matrix}
      \right) \mbox{.}
    \end{align*}

    $G^{T}$ enth"alt also in der $k$-ten Zeile die Links, die von
    der $k$-ten Seite auf andere Seiten linken\footnote{In der $k$-ten
    Zeile und der $l$-ten Spalte steht der Anteil vom Rang der $k$-ten
    Seite, der an die $l$-te Seite weitergegeben wird, n"amlich
    $\frac{-d}{n_{k}}$.}. Die Anzahl der Links auf der $k$-ten Seite
    ist $n_{k}$, so da"s in der $k$-ten Zeile von $G^{T}$ neben der
    Eins auf der Diagonalen und $N - n_{k} - 1$ Nullen genau $n_{k}$
    Eintr"age der Form $\frac{-d}{n_{k}}$ stehen. Daraus folgt, da"s
    $G^{T}$ \emph{stark diagonal dominant} ist, denn f"ur jede Zeile
    der Matrix $G^{T}$ gilt

    \begin{align*}
      |g_{kk}| &> \sum_{l=1}^{N} \left|g_{kl}\right| \\
      \Leftrightarrow
      1 &> \sum_{l=1}^{n_k} \left|\frac{-d}{n_{k}}\right| +
      \sum_{m=n_k+1}^{N-1}
      0 \\
      \Leftrightarrow
      1 &> n_{k} \left|\frac{-d}{n_{k}}\right| + 0 \\
      \Leftrightarrow
      1 &> \left|-d\right| \\
      \Leftrightarrow
      1 &> d
    \end{align*}
    
    wegen $d \in (0,1)$. $\blacksquare$
    
    Damit ist der \emph{Spektralradius} von $G^{T}$  kleiner als
    $1$, woraus folgt, da"s der gr"o"ste Eigenwert von $G^{T}$ kleiner
    als $1$ ist. Da die Eigenwerte von $G^{T}$ gleich den Eigenwerten
    von $G$ sind, ist der Spektralradius von $G$ ebenfalls kleiner $1$.
    Das ist ein hinreichendes Kriterium f"ur die Konvergenz der
    Google-Iteration.
    
    \item % 3 
    (Siehe Programm \texttt{gauss\_seidel.m} im Anhang.)
 
  \end{enumerate}

\end{document}
