\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Mathematik f\"ur Bioinformatiker III (Numerik)}
\author{\"Ubungsblatt 5}
\date{14.11.2001}
\maketitle



\begin{enumerate}

\item Sei, wie in der Vorlesung,
\[
  x_{k+1} = x_k + B (b - A x_k)
\]
ein Relaxationsverfahren (iteratives Verfahren) zum L\"osen der
Gleichung $Ax=b$.  Zeigen Sie, dass das Verfahren f\"ur beliebiges
nichtsingul\"ares $B$ konsistent ist.  (Konsistent bedeutet, dass
jeder Fixpunkt der Iteration schon eine L\"osung von $Ax=b$ ist.)

\item Eine Matrix $A=(a_{ij})$ hei\ss t \emph{stark diagonal dominant},
  falls f\"ur jedes $i=1,\dots,n$ gilt
\[
  \lvert a_{ii} \rvert
  > \sum_{j=1}^n \lvert a_{ij} \rvert .
\]
Starke Diagonal-Dominanz ist eine hinreichende Bedingung daf\"ur, dass
der Spektralradius der Jacobi- oder Gau\ss--Seidel-Iterationsmatrix
kleiner als $1$ ist.

Sei nun $A$ die Google-Matrix, d.h.\ die Matrix zum Gleichungssystem
\[
  r_i - d \sum_{j \text{ linkt }i} \frac{r_j}{n_j} = \frac{1-d}N,
\]
wobei $r_i$ der Rank der $i$-ten Webseite ist, $i = 1, \dots, N$, $d
\in (0,1)$ der D\"ampfungs- oder Durchhaltefaktor, und $n_j$ die Zahl
der von Seite $j$ ausgehenden Links.

Zeigen Sie, dass die Transponierte der Google-Matrix stark diagonal
dominant ist.  Schlie\ss en Sie daraus, dass die Google-Iteration,
also das Jacobi-Verfahren f\"ur die Google-Matrix, konvergiert.
  
\item \textbf{Programmieraufgabe:} Schreiben Sie eine
  \textsf{Octave}-Funktion \verb+gauss_seidel(A,b)+, die die L\"osung
  der Gleichung $Ax=b$ durch Gau\ss--Seidel-Iteration berechnet.
  Geben Sie au\ss erdem den Spektralradius der Iterationsmatrix aus.
  
  Testen Sie Ihr Programm mit dem Beispiel der 2.\ Aufgabe vom
  \"Ubungsblatt~3, wo $A$ eine Van\-der\-monde--Matrix ist und $b$ die
  Zeilensummen von $A$ enth\"alt.  
\end{enumerate}

\noindent
\textbf{Abgabe:} Montag, 19.11.2001, um 12:30 f\"ur alle
\"Ubungsgruppen ins Postfach \emph{Oliver} des Mathematischen
Instituts, 3. Stock, C-Geb\"aude.

\medskip\noindent
\textbf{Hinweis:} Bitte notieren sie rechts oben auf Ihrer L\"osung,
an welchem \emph{Wochentag} und in welchem \emph{Raum} Sie an der
\"Ubungsgruppe teilnehmen.

\end{document}
