\subsection{Gram--Schmidt Orthogonalisierung}

Klassischer Gram--Schmidt (CGS): 
Die $Q_1 R_1$ Zerlegung wie in Satz \ref{2.3.8} kann
man nat\"urlich auch \"uber Gram--Schmidt erhalten. Sei $\rnk(A) = n$. Der
klassische Gram--Schmidt ist dann gegeben durch
%
\begin{eqnarray*}
 r_{ik} & = & q^*_i a_k, \; i=1:k-1\\
 q_k & = & (a_k - \sum^{k-1}_{i=1} r_{ik} q_i) / r_{kk}.
\end{eqnarray*}
%
Numerisch gesehen ist dieser Algorithmus sehr schlecht, da die Orthogonalit\"at
der $q_k$ durch Rundungsfehler zerst\"ort wird. Eine leichte Umsortierung
ergibt den sogenannten modifizierten Gram--Schmidt (MGS), der numerisch
wesentlich besser ist.\\
Definiere $A^{(k)} \in \K^{m,n-k+1}$ durch
\[
 A - \sum^{k-1}_{i=1} q_i r_i^* = \sum^n_{i=k} q_i r_i^* = [0 \,\,A^{(k)}].
\]
%
Mit $A^{(k)} = \bigl[ \underbrace{z}_{1} \,\, \underbrace{B}_{n-k} \bigr]$
gilt: 
%
$r_{kk} = \|z\|_2, \;q_k = z/r_{kk}$ und $[r_{k,k+1}, \dots r_{k,n}] = q^*_k B.$\\
Damit k\"onnen wir
\[
 A^{(k+1)} = B -q_k [r_{k,k+1}, \dots, r_{k,n} ]
\]
%
als \"au{\ss}eres Produkt bestimmen und weitermachen.
%
\begin{algorithmus}[Modifizierter Gram--Schmidt]\label{2.3.9} \quad\newline
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{
			$A \in \K^{m,n}$ Rang $(A) = n$.}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{
			Zerlegung $A = Q_1 R_1, Q_1 \in \K^{m,n}$
			mit orthonormalen Spalten, $R_1 \in \K^{n,n}$ obere
			$\bigtriangleup$--Matrix.
		     }\\[3ex]
&FOR&\multicolumn{2}{l}{$k=1:n$}\\
&   &\multicolumn{2}{l}{$R(k,k)  = \|A(1:m,k)\|_2$;}\\
&   &\multicolumn{2}{l}{$Q(1:m,k)= A(1:m,k)/R(k,k)$;}\\
&   &FOR&$j=k+1:n$\\
&   &   &$R(k,j)  = Q(1:m,k)^** A(1:m,j)$;\\
&   &   &$A(1:m,j)= A(1:m,j)-Q(1:m,k)*R(k,j)$;\\
&   &END&\\
&END&       
\end{tabular}
\end{algorithmus}
\underline{Kosten:} $2mn^2$ \flops.\\
\underline{Fehler:} $\tilde{Q}_1^* \tilde{Q}_1 = I + E, \|E\|_2 \approx\eps 
                    \kappa_2 (A)$\\
Zum Vergleich bei Householder $\|E\|_2 =\eps$.

\underline{Kostenvergleich:} Zur Berechnung einer Orthonormalbasis 
f\"ur Bild$(A)$
ist der modifizierte Gram--Schmidt schneller als $QR$.
%
