\subsection{Vollst\"andige Pivotisierung}
Um den Wachstumsfaktor zu verkleinern gibt es eine Variante, in der das Pivot
aus der gesamten Matrix $A^{(k-1)} (k:n,k:n)$ ausgew\"ahlt wird, 
d.h. wir bestimmen die Zerleung
%
\[
 M_{n-1} P_{n-1} \cdots M_1 P_1 A Q_1 \cdots Q_{n-1} = R
\]
%
mit Permutationsmatrizen $P_i, Q_i$, die so bestimmt werden, da{\ss}
%
\[
 \left| (P_k A^{(k-1)} Q_k)_{kk} \right| = \max \limits_{k \le i, j \le n}
 \left| (P_k A^{(k-1)} Q_k)_{ij} \right|.
\]
%

\begin{theorem}\label{2.1.48}
Bei Verwendung von Gau{\ss}--Elimination 
mit vollst\"andiger Pivotisierung zur Berechnung von
%
\eq{2.1.49}
M_{n-1} P_{n-1} \cdots M_1 P_1 A Q_1 \cdots Q_{n-1} = R
\en
%
gilt
\[
 PAQ = LR
\]
%
mit $P=P_{n-1} \cdots P_1$, 
    $Q = Q_1 \cdots Q_{n-1}$ 
    und $L$ ist untere $\bigtriangleup$--Matrix mit 1--Diagonale 
   und $|l_{ij} |\le 1$. F\"ur $M_k = I-t^{(k)} e^T_k$ gilt
%
\[
 L(k+1:n,k) = g(k+1:n) \mbox { mit } g = P_{n-1} \cdots  P_{k+1} t^{(k)}.
\]
%
\end{theorem}
%
\proof
Analog zu Satz \ref{2.1.43}.
\eproof
%
\begin{algorithmus}[Gau{\ss}--Elim. mit vollst\"andiger Pivotisierung]
\label{2.1.50}
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{l}{$A \in \K^{n,n}$.}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{$LR$--Zerlegung von $PAQ$ mit 
		     	$P,Q$ Produkte von elementaren Permutationsmatrizen,
			$A(1:k,k)$ wird durch $R(1:k,k), \; k=1:n$ und
			$A(k+1:n,k)$ durch $L(k+1:n,k),\; k=1:n-1$ 
			\"uberschrieben. $P_k$ vertauscht Zeilen $k$ und 
			$p(k)$, $Q_k$ vertauscht Spalten $k$ und $q(k)$.
                     }\\[9.5ex]
&FOR&\multicolumn{2}{l}{$k=1:n-1$}\\
&   &\multicolumn{2}{l}{Bestimme $\mu, \lambda$, so da{\ss}
     $|A(\mu, \lambda)| = \max \left\{ |A(i,j)|: \;i,j=k:n \right\}$}\\
&   &\multicolumn{2}{l}{$A(k,1:n) \longleftrightarrow A(\mu, 1:n)$}\\
&   &\multicolumn{2}{l}{$A(1:n,k) \longleftrightarrow A(1:n,\lambda)$}\\
&   &\multicolumn{2}{l}{$p(k) = \mu$;}\\
&   &\multicolumn{2}{l}{$q(k) = \lambda$;}\\
&   &IF & $A(k,k) \neq 0$\\
&   &   & $t= GAUSS(A(k:n,k))$;\\
&   &   & $A(k+1:n,k) = t$;\\
&   &   & $A(k:n,k+1:n) = GAUSSAPP(A(k:n,k+1:n), t)$;\\
&   &END&\\ 
&END&   & 
\end{tabular}
\end{algorithmus}
\underline{Kosten} $\frac{2n^3}{3}$ \flops und Vergleiche. Vergleiche
nicht vernachl\"assigbar.
\begin{itemize}
\item Vollst\"andige Pivotisierung erlaubt $LR$--Zerlegung f\"ur 
$\rnk A = r < n.$
\item In exakter Arithmetik gilt f\"ur Algorithmus \ref{2.1.50}
%
\[
 \left|a^{(k)}_{ij}\right| \le k^{\frac{1}{2}} (2 \cdot 3^{\frac{1}{2}} \cdots
 k^{\frac{1}{k-1}})^{\frac{1}{2}} \max |a_{ij}|.
\]
%
Die Schranke ist sehr langsam wachsend mit $k$. Mit der empirischen Tatsache,
da{\ss} $\rho \approx 10$, kann man aussagen, da{\ss} Gau{\ss}--Elimination
mit vollst\"andiger Pivotisierung r\"uckw\"arts stabil ist, d.h. 
die Methode l\"ost exakt
%
\[
 (A+E) \hat{x} = b
\]
%
f\"ur kleines $E$. Wilkinsons Vermutung Schranke $=n$ ist nicht richtig.
\end{itemize}
%
