\section{Die Singul\"arwertzerlegung}
Eines der wichtigsten Hilfsmittel in allen Bereichen der numerischen
Mathematik ist heutzutage die Singul\"arwertzerlegung einer Matrix. 
%
\begin{theorem}\label{6.3.1}
Sei $A$ eine reelle $m \times n$ Matrix. Dann gibt es orthogonale Matrizen
$U = [u_1, \cdots, u_m] \in \R^{m,m}$ und
$V=[v_1, \cdots, v_n] \in \R^{n,n}$,
so da{\ss}
%
\eq{6.3.2}
 U^T AV = \mbox { diag } (\sigma_1, \cdots, \sigma_p) \in \R^{m,n},\; p = \min (m,n)
\en
%
wobei $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_p \ge 0.$
\end{theorem}
%
\proof
Seien $x \in \R^n, y \in \R^n$ Vektoren mit $\|x\|_2=\|y\|_2 = 1$, so da{\ss}
$Ax = \sigma y, \sigma = \| A \|_2$. Dies ist m\"oglich,
da $\|A\|_2 =\sup_{\|x\|_2=1} {\| Ax\|_2}$ angenommen wird. \\
Da jede Menge von orthogonalen Vektoren zu einer Basis des ganzen Raumes
erg\"anzt werden kann, gibt es $V_1 \in \R^{n,(n-1)}$ und $U_1 \in \R^{m,(m-1)}$, so da{\ss}\\
$V = [x, V_1] \in \R^{n,n}, U = [y, U_1] \in \R^{m,m}$ orthogonal sind. Dann gilt
%
\eqa\label{6.3.3}
 U^T AV & = & \left[ \begin{array}{c}
           y^T\\ U_1^T \end{array}\right] A \left[ \begin{array}{cc}
           x & V_1 \end{array}\right] = \left[ \begin{array}{c}
           y^T\\ U_1^T \end{array}\right] \left[ \begin{array}{cc}
           \sigma y, & AV_1 \end{array}\right] \\
        & = & \left[ \begin{array}{cc}
              \sigma & w^T\\
              0 & B \end{array}\right] = : A_1. \nonumber
\ena
%
Da 
%
\eq{6.3.4}
 \left \| A_1  \left[ \begin{array}{c}
       \sigma\\w \end{array} \right] \right \|^2_2 \ge (\sigma^2 + w^T w)^2,
\en
%
so folgt, da{\ss}
%
\eq{6.3.5}
 \|A_1\|^2_2 \ge \sigma^2 + w^Tw.
\en
%
Aber $\sigma^2 = \|A\|^2_2 = \|A_1\|^2_2.$ Also folgt $w=0.$
Per Induktion folgt das Resultat.
\eproof
%

Die Werte $\sigma_i$ hei{\ss}en Singularwerte, die $u_i, v_i$ linke und rechte
Singul\"arvektoren. Es gilt
%
\eq{6.3.6}
 Av_i = \sigma_i u_i, A^T u_i = \sigma_i v_i,\;
 i = 1, \cdots, \min (m,n)
\en
$\longrightarrow$ \"Ubung\\
Die Singul\"arwerte sind die L\"angen der Halbachsen der Hyperellipsoide
$E = \{ Ax : \| x\| = 1 \}.$\\
$\longrightarrow$ \"Ubung\\
Sei $\sigma_1 \ge \cdots \ge \sigma_r > \sigma_{r+1} = \cdots = \sigma_p = 0$,
so gilt
\begin{eqnarray*}
 \mbox { rang } (A) & = & r\\
 \mbox { Kern } (A) & = & \mbox { span } \{v_{r+1}, \cdots, v_n \} \\
 \mbox { Bild } (A) & = & \mbox { span } \{ u_1, \cdots, u_r \} \\
 \|A\|^2_p & = & \sigma^2_1 + \cdots + \sigma^2_p \quad p = \min \{m,n\}\\
 \|A\|_2 & = & \sigma_1\\
 \mbox { cond }_2 (A) & = & \frac{\sigma_1}{\sigma_p}
\end{eqnarray*}
%
Die Singul\"arwertzerlegung 
wird daher zur Rangbestimmung verwendet. Weitere Anwendungen, Bildverarbeitung,
Ausgleichsprobleme, Abspaltung von Kern und Co-Kern.
%
\begin{theorem}\label{6.3.7}
Sei $A = U \Sigma V^T$ die SWZ von $A \in \R^{m,n}$. Sei $k < r =$ rang $(A)$ und
%
\eq{6.3.8}
 A_k = \sum\limits^k_{i=1} \sigma_i u_i v_i^T.
\en
Dann gilt
%
\eq{6.3.9}
 \min\limits_{\mbox {rang}(B)=k} \|A-B\|_2 = \|A-A_k\|_2 = \sigma_{k+1}.
\en
%
\end{theorem}
\proof
$U^T A_k V =$ diag $(\sigma_1, \cdots, \sigma_k, , 0 \cdots, 0) \Longrightarrow$
rang $(A_k) = k$ und\\
$U^T (A-A_k) V =$ diag $(0, \cdots, 0, \sigma_{k+1}, \cdots, \sigma_p) \Longrightarrow
\|A-A_k\|_2 = \sigma_{k+1}.$\\
Angenommen rang $(B) = k$ f\"ur $B\in \R^{m,n}$. Dann gibt es orthonormale
Vektoren $x_1, \cdots, x_{n-k}$ die Kern $(B)$ aufspannen. Kern $(B) = $ span
$\{x_1, \cdots, x_{n-k} \}$. Aus Dimensionsgr\"unden gilt
%
\eq{6.3.10}
 w = \mbox {span} \{x_1, \cdots, x_{n-k}\} \cap \mbox {span} 
 \{v_1, \cdots, v_{k+1}\}  \neq \{0\}
\en
%
$(z = \sum \alpha_i v_i \quad \alpha_i = v^T_i z)$.\\
Sei $z \in W, \|z\|_2 = 1.$ Da $Bz = 0$ und\\
$Az = \sum\limits^{k+1}_{i=1} \sigma_i (v^T_i z) u_i$, so folgt
%
\eq{6.3.11}
 \|A-B\|^2_2 \ge \| (A-B) z \|^2_2 = \|Az \|^2_2 =
 \sum\limits^{k+1}_{i=1} \sigma^2_i (v_i^T z) \ge \sigma^2_{k+1}.
\en
%

\subsection{Die Berechnung der Singul\"arwertzerlegung}

Man k\"onnte die Berechnung der Singul\"arwertzerlegung direkt auf ein symmetrisches Eigenwertproblem
zur\"uckf\"uhren, denn falls $A = U \Sigma V^T \in \R^{m,n},\; m \ge n$,
so gilt\\
$AA^T = U \Sigma V^T V \Sigma^T U^T = U\Sigma^2 U^T = U$ diag 
$(\sigma^2_1, \cdots, \sigma^2_n) U^T$ und da $AA^T$ symmetrisch ist dies eine 
Schurform mit spezieller Anordnung. Analog\\
$A^TA = V \Sigma^2 V^T = V$ diag $(\sigma^2_1, \cdots, \sigma^2_n, 0, \cdots, 0)V^T$.
Man k\"onnte also $A^TA$ und $AA^T$ bilden, aber wie wir schon beim
Ausgleichsproblem gesehen haben, w\"urde dieses zur Quadrierung der Kondition f\"uhren.\\
Besser ist daher der Algorithmus von Golub/Kahan der auf den symmetrischen
QR--Algorithmus aufbaut.\\
(1) Schritt transformiere $A$ auf Bidiagonalform mit Householder--Transformationen.
%






\begin{algorithmus}[Householder--Bidiagonalisierung]\label{6.3.12} ~\newline
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{$A \in \R^{m,n}, m \ge n$}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{Der obere Bidiagonalteil von 
$A$ wird dem oberen
Bidiagonalteil von $B = U^T AV$ \"uberschrieben, $B$ obere Bidiagonalmatrix.
%
\[
  U= U_1 \cdots U_{n-1} (\cdot U_n), \; V = V_1 \cdots V_{n-2}
\]
Produkt von Householder--Matrizen. Der wesentliche Teil von $U_j$ ist in 
$A(j+1:m,j)$
und der wesentliche Teil von $V_j$ in $A(j,j+2:m)$ gespeichert.
}\\[3ex]
& FOR & \multicolumn{2}{l}{$j = 1:n-1$}\\
&     & \multicolumn{2}{l}{$v(j:m) = HOUSE (A(j:m,j))$;}\\
&     & \multicolumn{2}{l}{$A(j:m,j:n) = ROWHOUSE (A (j:m, j:n), v(j:m))$;}\\
&     & \multicolumn{2}{l}{$A(j+1:m,j) = v(j+1:m);$}\\
&     & IF & $j \le n-2$\\
&     &    & $v(j+1:n) = HOUSE(A(j,j+1:n)^T)$;\\
&     &    & $A(j:m, j+1:n) = COLHOUSE(A(j:m,j+1:n), v(j+1:n))$;\\
&     &    & $A(j,j+2:n) = v(j+2:n)^T$;\\
&     & END&\\
& END & &\\
& IF  & \multicolumn{2}{l}{$m>n$}\\
&     & \multicolumn{2}{l}{$v(n:m) = HOUSE (A(n:m,n))$;}\\
&     & \multicolumn{2}{l}{$A(n:m,n) = ROWHOUSE (A (n:m, n), v(n:m))$;}\\
&     & \multicolumn{2}{l}{$A(n+1:m,n) = v(n+1:m);$}\\
& END & &
\end{tabular}
\end{algorithmus}
\underline{Kosten:} $4mn^2 - 4n^3/3$ flops\\
Falls $U,V$ explizit ben\"otigt werden, diese erh\"alt man mit $4m^2n - 4n^3/3$ f\"ur $U$
und $4n^3/3$ f\"ur $V$.

\underline{Fehleranalyse:} $B = U^T (A+E) V$ mit $U^TU = I, V^TV = I, 
\| E \|_F \le cn^2$ eps $\|A\|_F.$
%%
%ich weiss nicht, ob die nachfolgenden Seiten hier an richtiger Stelle sind.

Vorgehen:
\[
\begin{array}{l}
 \left[ \begin{array}{cccc}
  x & x & x & x\\
  x & x & x & x\\
  x & x & x & x\\
  x & x & x & x\\
  x & x & x & x \end{array}\right] {U_1 \atop \longrightarrow} 
%
 \left[ \begin{array}{cccc}
  x & x & x & x\\
  0 & x & x & x\\
  0 & x & x & x\\
  0 & x & x & x\\
  0 & x & x & x \end{array}\right]  {V_1 \atop \longrightarrow}\\
%
   \left[ \begin{array}{cccc}
  x & x & 0 & 0\\
  0 & x & x & x\\
  0 & x & x & x\\
  0 & x & x & x\\
  0 & x & x & x \end{array}\right] {U_2 \atop \longrightarrow}
%
   \left[ \begin{array}{cccc}
  x & x & 0 & 0\\
  0 & x & x & x\\
  0 & 0 & x & x\\
  0 & 0 & x & x\\
  0 & 0 & x & x \end{array}\right] {V_2 \atop \longrightarrow}
%
  \left[ \begin{array}{cccc}
  x & x & 0 & 0\\
  0 & x & x & 0\\
  0 & 0 & x & x\\
  0 & 0 & x & x\\
  0 & 0 & x & x \end{array}\right]\\
%
 {U_3 \atop \longrightarrow}  \left[ \begin{array}{cccc}
  x & x & 0 & 0\\
  0 & x & x & 0\\
  0 & 0 & x & x\\
  0 & 0 & 0 & x\\
  0 & 0 & 0 & x \end{array}\right] {U_4 \atop \longrightarrow}
%
 \left[ \begin{array}{cccc}
  x & x & 0 & 0\\
  0 & x & x & 0\\
  0 & 0 & x & x\\
  0 & 0 & 0 & x\\
  0 & 0 & 0 & 0 \end{array}\right].
\end{array}
\]
%
(2) Wende symmetrischen QR--Algorithmus implizit auf $T = B^TB$ (tridiagonal) an,
%
\[
 B = \left[ \begin{array}{cccc}
     d_1 & f_1 & & \\
         & \ddots & \ddots & \\
         &        & \ddots & f_{n-1}\\
         &        &        & d_n \\ \hline 
         \multicolumn{4}{c}{0}
       \end{array}\right],\; B^T B = \left[ \begin{array}{cccc}
     d^2_1 & f_1d_1 & & \\
     f_1 d_1 & d^2_2 + f^2_1 & f_2 d_2 & \\
     \ddots & \ddots & \ddots  &\\
     & & & f_{n-1}d_{n-1}\\
     & & f_{n-1}d_{n-1} & d^2_n + f^2_ {n-1} \end{array}\right]
\]
%
Berechne Eigenwert $\lambda$ von
%
\[
 T(n-1:n, n-1:n) = \left[ \begin{array}{cc}
   d_{n-1}^2 + f^2_{n-2} & d_{n-1} f_{n-1}\\
   d_{n-1} f_{n-1} & d^2_n + f^2_{n-1} \end{array}\right]
\]
%
der n\"aher an $d^2_n + f^2_{n-1}$ liegt.\\
Berechne die beiden Elemente von
\[
 (T-\lambda I) e_1 = \left[ \begin{array}{c}
  d_1^2-\lambda\\
  d_1 f_1 \end{array}\right]
\]
%
und eine Givensrotation $G = \left[ \begin{array}{cc}
                           c_1 & s_1\\
                           -s_1 & c_1 \end{array}\right]$
\[
 \left[ \begin{array}{cc}
                           c_1 & s_1\\
                           -s_1 & c_1 \end{array}\right]^T
 \left[ \begin{array}{c}
       d^2_1  -\lambda\\
       d_1  f_1 \end{array}\right] = \left[ \begin{array}{c}
       *\\0 \end{array}\right]
\]
und transformiere
%
\[
 BG_1 = \left[ \begin{array}{ccccc}
    * & * & & & \\
    \circledast & * & * & & \\
    & & \ddots & \ddots & \\
    & & & \ddots & *\\
    & & & & *\end{array}\right]
\]
%
wieder auf Bidiagonalform.\\
$\longrightarrow$ \"Ubung
%





\subsubsection{Berechnung und Anwendung von Givensrotationen}
Bestimme $c,s\in \R$ mit $c^2+s^2=1$, so da{\ss}
\[
 \left[ 
  \begin{array}{cc}
   c & -s\\
   s & c \end{array}\right]
 \left[ \begin{array}{c}
       a\\
       b
\end{array}\right] = \left[ \begin{array}{c}
       *\\0 \end{array}\right].
\]

Wichtige Details:\newline
Stabilit\"at der Berechnung von $c,s$.
      Im Prinzip ist $c=\pm b/\sqrt{a^2+b^2},s=\mp a/\sqrt{a^2+b^2}$.
      Man berechnet aber den Quotienten $t=a/b$ bzw. $t=b/a$ und macht 
      Fallunterscheidung. Aus Stabilit\"atgr\"unden sollte $|t|\leqslant 1$ 
      gelten.

\begin{algorithmus}[Erzeugung der Givens--Parameter]\label{G1}
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{$a,b \in \R$.}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{$c,s \in \R$ mit $c^2+s^2=1$,
			 so da{\ss} $ \left[ 
  \begin{array}{cc}
   c & -s\\
   s & c \end{array}\right]
 \left[ \begin{array}{c}
       a\\
       b
\end{array}\right] = \left[ \begin{array}{c}
       *\\0 \end{array}\right]
$.
		     }\\[3ex]
&FUNCTION&\multicolumn{2}{l}{$[c,s]=GIVENS(a,b)$}\\
&        &IF   & $|b|>|a|$\\
&        &     & $t=-a/b$;\\
&        &     & $s=1/\sqrt{1+t^2}$;\\
&        &     & $c=s*t$;\\
&        &ELSE & \\
&        &     & $t=-b/a$;\\
&        &     & $c=1/\sqrt{1+t^2}$;\\
&        &     & $s=c*t$;\\
&        &END &\\ 
&END GIVENS&   & 
\end{tabular}
\end{algorithmus}
\underline{Kosten:} 5 flops, 1 $\sqrt{}$.\\


\begin{algorithmus}[Vormultiplikation mit Givens--Rotation]\label{G2} 
\begin{tabular}{lll}
\underline{Input:} & \multicolumn{2}{p{13.5cm}}{$A\in\K^{2,n}, c,s\in\R, 
			c^2+s^2=1$.}\\
\underline{Output:}& \multicolumn{2}{p{13.5cm}}{
			$A$ \"uberschrieben mit $
 \left[ 
  \begin{array}{cc}
    c & -s\\
   s & c \end{array}\right]A$.
		     }\\[3ex]
&FUNCTION & $A=ROWROT(A,c,s)$\\
&         & $A = [c, -s; s, c] * A$;  \\
&END ROWROT&    
\end{tabular}
\end{algorithmus}
\underline{Kosten:} $6n$ \flops.\\
\underline{Fehler:} $gl(\tilde{G}A) = G(A+E)$, 
                    $\;\|E\|_2 = {\cal O}(\eps\|A\|_2)$

\begin{algorithmus}[Nachmultiplikation mit Givens--Rotation]\label{G3} 
\begin{tabular}{lll}
\underline{Input:} & \multicolumn{2}{p{13.5cm}}{$A\in\K^{m,2}, c,s\in\R, 
			c^2+s^2=1$.}\\
\underline{Output:}& \multicolumn{2}{p{13.5cm}}{
			$A$ \"uberschrieben mit $
 A\left[ 
  \begin{array}{cc}
    c & s\\
   -s & c \end{array}\right]$.
		     }\\[3ex]
&FUNCTION & $A=COLROT(A,c,s)$\\
&         & $A = A *[c, s; -s, c]$;  \\
&END COLROT&    
\end{tabular}
\end{algorithmus}
\underline{Kosten:} $6m$ \flops.\\
\underline{Fehler:} $gl(A\tilde{G}) = (A+E)G$, 
                    $\;\|E\|_2 = {\cal O}(\eps\|A\|_2)$

%
Diese 3 Algorithmen werden verwendet um bestimmte einzelne Eintr\"age
einer Matrix zu eliminieren.\\
Dieses ist ideal f\"ur den SWZ-Schritt.













\begin{algorithmus}[Golub/Kahan SWZ--Schritt]\label{6.3.13} ~\newline
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{ Bidiagonalmatrix 
$B \in \R^{m,n}$, die keine Nullen
auf Diagonale und Superdiagonale hat.
}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{$B$ \"uberschrieben mit der 
Bidiagonalmatrix $\bar{B} = \bar{U}^T B \bar{V}, \bar{U}, \bar{V}$ orthogonal 
und $\bar{V}$
ist im wesentlichen die orthogonale Matrix die man erhalten w\"urde,
wennman die symmetrische Version des QR--Algorithmus auf
$T=B^TB$ anwenden w\"urde.}\\[3ex]
&\multicolumn{3}{p{13.5cm}}{Sei $\mu$ der Eigenwert der rechten unteren 
	$2 \times 2$ Matrix von $B^TB$ der n\"aher
	am letzten Diagonalelement von $B^TB$ ist.}\\
& \multicolumn{3}{l}{$y = B(1,1)^2 - \mu$}\\
& \multicolumn{3}{l}{$z = B(1,1)*B(1,2)$}\\
& FOR & \multicolumn{2}{l}{$k = 1:n-1$}\\
&     & \multicolumn{2}{l}{$[c,s]=GIVENS(y,z)$;}\\
&     & \multicolumn{2}{l}{$l=\max\{1,k-1\}$}\\
&     & \multicolumn{2}{l}{$B(l:k+1,k:k+1)=COLROT(B(l:k+1,k:k+1),c,s)$;}\\
&     & \multicolumn{2}{l}{$y = B(k,k);$}\\
&     & \multicolumn{2}{l}{$z = B(k+1,k)$;}\\
&     & \multicolumn{2}{l}{$[c,s]=GIVENS(y,z)$;}\\
&     & \multicolumn{2}{l}{$l=\min\{k+2,n\}$}\\
&     & \multicolumn{2}{l}{$B(k:k+1,k:l)=ROWROT(B(k:k+1,k:l),c,s)$;}\\
&     & IF & $k< n-1$\\
&     &    & $y = B(k,k+1);$\\
&     &    & $z = B(k,k+2);$\\
&     & END& \\
&END  &    & \\
\end{tabular}
\end{algorithmus}

\underline{Kosten:} $30n$ \quad flops, $2n \quad \sqrt{~}$\\
Akkumulation von $U$ \quad $6mn$ flops\\
Akkumulation von $V$ \quad $6n^2$ flops\\
\underline{Fehler:} Wie bei $QR$.\\
\underline{Deflation wie bei $QR$--Algorithmus}

Die Anfangsreduktion auf Bidiagonalform und die Iterationsfolge zusammen
mit Deflation wird zusammengefaat im SWZ--Algorithmus. 
% 
\begin{algorithmus}[SWZ Berechnung--Golub/Reinsch]\label{6.3.14} ~\newline
\begin{tabular}{lllll}
\underline{Input:} & \multicolumn{4}{p{13.5cm}}{$A \in \R^{m,n}, m \ge n, 
                     \varepsilon = c \cdot \eps, c$ klein.
}\\
\underline{Output:}& \multicolumn{4}{p{13.5cm}}{$A$ \"uberschrieben mit $U^TAV = D+E \quad U, V$ orthogonal,
$D$ diagnonal, $\|E\|_2 \approx\eps \|A\|_2$.}\\[4ex]
&\multicolumn{4}{p{13.5cm}}{Bidiagonalisiere $A$ mit
Algorithmus \ref{6.3.12}. $q=0$;
}\\
&WHILE& \multicolumn{3}{l}{$q<n$}  \\
&     & \multicolumn{3}{p{11.5cm}}{Setze $A(i,i+1)$ zu Null, falls \newline $
 |A(i,i+1)| \le \varepsilon (|A(i,i)| + |A(i+1,i+1)|), \; i = 1 : n-1.$}\\
&     & \multicolumn{3}{l}{Bestimme gr\"o{\ss}tes $q$ und kleinstes $p$, 
        so da{\ss} in}\\
&     & \multicolumn{3}{l}{
        $ {\displaystyle
          B = \left[ 
                \begin{array}{ccc}
                 B_{11} &  0     & 0\\
		 0      & B_{22} & 0\\
		 0      & 0      & B_{33} 
                \end{array}
               \right] 
               \begin{array}{l}
                p \\
                n-p-q\\
                q+m-n 
               \end{array}}
          \atop
          {\displaystyle p \quad n-p-q \quad q\qquad\quad }
       $}\\
&     &\multicolumn{3}{l}{$B_{33}$ diagonal ist, und $B_{22}$ nur 
	Nebendiagonalelemente  $\neq 0$ hat.}\\
&     & IF & \multicolumn{2}{l}{$q < n$}\\
&     &    & \multicolumn{2}{p{11.5cm}}{Setze in $B_{22}$ alle $A(i,i)$ 
                    zu Null, falls  $|A(i,i)| \le \varepsilon \|B_{22}\|$.}\\
&     &    & IF & Diagonalelement von $B_{22}$ Null\\
&     &    &    & mache Spezialschritt (unten)\\
&     &    & END&\\
&     &    &\multicolumn{2}{l}{Wende Algorithmus \ref{6.3.13} auf $B_{22}$ an}\\
&     &END &\\
&END &\\
& \multicolumn{4}{l}{Spezialschritt:}\\
& \multicolumn{4}{p{13.5cm}}{Sei $k$ der gr\"o{\ss}te Index, so da{\ss} f\"ur 
                             die Eintr\"age in $B_{22}$ 
			     $A(k,k)=0$ ist und $A(l,l)\neq 0, l>k$.}\\
& \multicolumn{4}{l}{
       Schiebe Eintrag an Position $(k,k+1)$ nach rechts heraus}\\
& FOR & \multicolumn{3}{l}{$j=k+1:n-p-q$}\\
&     & \multicolumn{3}{l}{Eliminiere Eintrag in Position $(k,j)$}\\
&     & \multicolumn{3}{l}{$[c,s]=GIVENS(A(j,j),A(k,j));$}\\
&     & \multicolumn{3}{l}{$A([j,k],j)=ROWROT(A([j,k],j),c,s);$}\\
&     & \multicolumn{3}{l}{Neuer Eintrag in Position $(k,j+1)$ kommt herein}\\
&     & IF & \multicolumn{2}{l}{$j<n-p-q$}\\
&     &    & \multicolumn{2}{l}{$A([j,k],j+1)=ROWROT(A([j,k],j+1),c,s);$}\\
&     & END& \\
& END &\\
& \multicolumn{4}{l}{
       Schiebe Eintrag an Position $(k-1,k)$ nach oben heraus}\\
& FOR & \multicolumn{3}{l}{$j=k-1:-1:p+1$}\\
&     & \multicolumn{3}{l}{Eliminiere Eintrag in Position $(j,k)$}\\
&     & \multicolumn{3}{l}{$[c,s]=GIVENS(A(j,j),A(j,k));$}\\
&     & \multicolumn{3}{l}{$A(j,[j,k])=COLROT(A(j,[j,k]),c,s);$}\\
&     & \multicolumn{3}{l}{Neuer Eintrag in Position $(j-1,k)$ kommt herein}\\
&     & IF & \multicolumn{2}{l}{$j>p+1$}\\
&     &    & \multicolumn{2}{l}{$A(j-1,[j,k])=COLROT(A(j-1,[j,k]),c,s);$}\\
&     & END& \\
& END &
\end{tabular}
\end{algorithmus}
\underline{Koten:}
\begin{tabular}{l|l}
& flops \\ \hline
$\Sigma$      & $4mn^2 - 4n^3/3$\\
$\Sigma,V$    & $4mn^2 + 8n^3$\\
$\Sigma, U$   & $4m^2n - 8mn^2$\\
$\Sigma, U, V$& $4m^2n + 8mn^2 + 9n^3$ 
\end{tabular}
%

Den Spezialschritt verdeutlichen wir an folgendem Beispiel\\
Zuerst schieben wir den Eintrag $(k,k+1)$ nach rechts heraus
\begin{small}
\[
\left[ 
     \begin{array}{cc|c|cc}
      {*}& * &   &   &   \\
         & * & \circledast &   &  \\ \hline
         &   & 0 & \circledast & \\ \hline
         &   &   & * & * \\
         &   &   &   & * 
     \end{array}
    \right] \mapsto
    \left[ 
     \begin{array}{cc|c|cc}
      {*}& * &   &   &   \\
         & * & \circledast &   &   \\ \hline
         &   & 0 & 0 & \circledast   \\ \hline
         &   &   & \circledast & \circledast   \\
         &   &   &   & *  
     \end{array}
    \right] \mapsto
    \left[ 
     \begin{array}{cc|c|cc}
      {*}& * &   &   &   \\
         & * & * &   &   \\ \hline
         &   & 0 & 0 & 0 \\ \hline
         &   &   & \circledast & \circledast \\
         &   &   &   & \circledast 
     \end{array}
    \right] 
\]
\end{small}
Dann schieben wir den Eintrag $(k-1,k)$ nach oben heraus
\begin{small}
\[
\left[ 
     \begin{array}{cc|c|cc}
      {*}& * &   &   &   \\
         & * & \circledast &   &  \\ \hline
         &   & 0 & 0 & 0 \\ \hline
         &   &   & \circledast & \circledast \\
         &   &   &   & \circledast 
     \end{array}
    \right] \mapsto
    \left[ 
     \begin{array}{cc|c|cc}
      {*}& \circledast & \circledast  &   &   \\
         & \circledast & 0 &   &   \\ \hline
         &   & 0 & 0  &  0  \\ \hline
         &   &   & \circledast & \circledast   \\
         &   &   &   & \circledast
     \end{array}
    \right] \mapsto
    \left[ 
     \begin{array}{cc|c|cc}
      \circledast& \circledast & 0  &   &   \\
         & \circledast & 0 &   &   \\ \hline
         &   & 0 & 0 & 0 \\ \hline
         &   &   & \circledast & \circledast \\
         &   &   &   & \circledast 
     \end{array}
    \right] 
\]
\end{small}

%
\begin{example}\label{6.3.15}~\newline
$\displaystyle
 A = \left[ \begin{array}{cccc}
     1 & 1 & 0 & 0\\
     0 & 2 & 1 & 0\\
     0 & 0 & 3 & 1\\
     0 & 0 & 0 & 4 \end{array}\right]
$ \quad
\begin{tabular}{r|l|l|l}
Iteration & ${\cal O}(a_{21})$ & ${\cal O}(a_{23})$ & ${\cal O}(a_{34})$ \\ \hline
$1$ & $10^0$ & $10^0$ & $10^0$\\[0.2cm]
$2$ & $10^0$ & $10^0$ & $10^0$\\[0.2cm]
$3$ & $10^0$ & $10^0$ & $10^0$\\[0.2cm]
$4$ & $10^0$ & $10^{-1}$ & $10^{-2}$\\[0.2cm]
$5$ & $10^0$ & $10^{-3}$ & $10^{-8}$\\[0.2cm]
$6$ & $10^0$ & $10^{-1}$ & $10^{-27}$\\[0.2cm]
$7$ & $10^0$ & $10^{-1}$ & --\\[0.2cm]
$8$ & $10^0$ & $10^{-4}$ & --\\[0.2cm]
$9$ & $10^{-1}$ & $10^{-14}$ & --\\[0.2cm]
$10$ & $10^{-1}$ & -- & --\\[0.2cm]
$11$ & $10^{-4}$ & -- & --\\[0.2cm]
$12$ & $10^{-12}$ & -- & --\\[0.2cm]
$13$ & -- & -- & --
\end{tabular}
\end{example}
%
Also kubische Konvergenz.\\
Weiteres siehe Golub / van Loan.
