\subsection{Partielle Pivotisierung (Spaltenpivotisierung)}
Um zu vermeiden, da{\ss} 0--Pivots oder sehr kleine Pivots auftauchen, wird 
jeweils in der momentanen Spalte, das betragsm\"a{\ss}ig maximale Element 
gesucht und durch eine Zeilenvertauschung (Permutation) in die 
Diagonalposition gebracht. 

Grundidee:\\
\begin{tabular}{lll}
\phantom{Output:}& FOR & {$k = 1:n-1$}\\
		 &     & \multicolumn{1}{p{12cm}}{
                          Bestimme Permutationsmatrix $P_k$, so da{\ss} f\"ur 
			  $z = P_k A^{(k-1)} e_k$ gilt:
                          $|z(k)| = \|z (k:n) \|_\infty$. \newline 
			  Setze $\hat{A}^{(k-1)} = P_k A^{(k-1)}$.\newline
                          Bestimme Gau{\ss} Transformation $M_k$, so da{\ss} 
			  f\"ur $v=M_k \hat{A}^{(k-1)} e_k$ gilt:
                          $v(k+1:n) = 0.$ \newline 
			  Setze $A^{(k)} = M_k P_k A^{(k-1)}$
                         }\\
		 & END &    
\end{tabular}

Diese Vorgehensweise hei{\ss}t \underline{Spaltenpivotisierung} oder 
\underline{partielle Pivotisierung} und garantiert, da{\ss} alle 
Multiplikatoren vom Betrag $\le 1$ sind.
%
\[
 \left| (P_k M_{k-1} \cdots M_1 P_1 A)_{kk} \right| = 
 \max\limits_{k \le i \le n} \left| (P_k M_{k-1} \cdots M_1 P_1 A)_{ik}\right|,
 \; k = 1:n-1.
\]
%
Falls das Pivot $=0$ ist, so kann man einfach den Schritt der Elimination 
weglassen, da dann alle Elemente in dieser Spalte $=0$ sind.

Man erh\"alt dann den folgenden Algorithmus.
%
\begin{algorithmus}
[Gau{\ss}--Elim. mit partieller Pivotisierung, \"Au{\ss}ere Produktversion]\label{2.1.41}
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{l}{$A \in \K^{n,n}$.}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{Gau{\ss}--Transformationen
			$M_1, \dots, M_{k-1}$ und Permutationen
			$P_1, \dots , P_{n-1}$, 
			so da{\ss} $M_{n-1} P_{n-1} \cdots M_1 P_1 A = R$ 
			obere $\bigtriangleup$--Matrix. \newline
			Keiner der Multiplikatoren hat Betrag $>1$. 
			$A(k+1:n,k)$ wird durch $-M_k(k+1:n,k),\;k=1 : n-1$ 
			\"uberschrieben, 
			$A(1:k,k)$ wird durch $R(1:k,k),\; k=1:n$
			\"uberschrieben. Im Pivotvektor $piv(1:n-1)$ werden die
			Vertauschungen gespeichert.
			$P_k$ vertauscht die Zeilen $k$ und piv$(k),\;k=1:n-1$.
                     }
\end{tabular}
\begin{tabular}{llll}
\phantom{Output:}  
&FOR&\multicolumn{2}{l}{$k=1:n-1$}\\
&   &\multicolumn{2}{l}{Bestimme $\mu$ $(k \le \mu \le n)$ mit 
			$|A(\mu, k)| = \|A(k:n,k) \|_\infty$}\\
&   &\multicolumn{2}{l}{$A(k,k:n) \longleftrightarrow A(\mu, k:n)$}\\
&   &\multicolumn{2}{l}{$piv(k) = \mu$;}\\
&   &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} F\"ur die Bestimmung aller $\mu$'s: 
                   ${\cal O}(n^2)$ Vergleiche, $\frac{2n^3}{3}$ \flops.\\
F\"ur das lineare Gleichungssystem $Ax=b$ macht man also
\begin{itemize}
\item $y = M_{n-1} P_{n-1} \cdots M_1 P_1 b$
\item L\"ose $Rx = y.$
\end{itemize}
%
S\"amtliche Informationen in $A$ und $piv$.
%
\begin{example}\label{2.1.42}
%
\[
\begin{array}{rclrcl}
 A & = & \left[ 
	  \begin{array}{ccc}
           3 & 17 & 10 \\
	   2 & 4 & -2\\
    	   6 & 18 & -12
	  \end{array}
	 \right] &&&\\[3.7ex]
%
P_1 & = & \left[ 
	   \begin{array}{ccc}
	    0 & 0 & 1\\
	    0 & 1 & 0\\
	    1 & 0 & 0
	   \end{array}
	  \right] &&&\\[3.7ex]
%
P_1A& = & \left[ 
	   \begin{array}{ccc}
	    6 & 18 & -12\\
	    2 & 4 & -2\\
	    3 & 17 & 10 
	   \end{array}
	  \right] & piv(1) & = & 3\\[3.7ex]
%
M_1 & = & \left[ 
	   \begin{array}{ccc}
	    1 & 0 & 0\\
	    -\frac{1}{3} & 1 & 0\\
	    -\frac{1}{2} & 0 & 1 
	   \end{array}
	  \right] & M_1P_1A& = & \left[ 
				  \begin{array}{ccc}
				   6 & 18 & -12\\
				   0 & -2 & 2 \\
				   0 & 8 & 16 
				  \end{array}
				 \right] \\[3.7ex]
%
P_2 & = & \left[ 
	   \begin{array}{ccc}
	    1 & 0 & 0\\
	    0 & 0 & 1\\
	    0 & 1 & 0 
	   \end{array}
	  \right] & piv(2) & = & 3\\[3.7ex]
%
M_2 & = & \left[ 
	   \begin{array}{ccc}
	    1 & 0 & 0\\
	    0 & 1 & 0\\
	    0 & \frac{1}{4} & 1
	   \end{array}
	  \right] & R      & = & \left[ 
				  \begin{array}{ccc}
				   6 & 18 & -12\\
				   0 & 8 & 16\\
				   0 & 0 & 6 
				  \end{array}
				 \right]
\end{array}
\]
\end{example}
%
Was passiert mit $L$?
%
\begin{theorem}\label{2.1.43}
Man verwende Gau{\ss}--Elimination mit partieller Pivotisierung zur Berechnung 
von
%
\eq{2.1.44}
 M_{n-1} P_{n-1} \cdots M_1 P_1 A = R
\en
%
mit Algorithmus \ref{2.1.41}, so gilt
\[
 PA = LR,
\]
%
mit $P = P_{n-1} \cdots P_1$ (Permutationsmatrix),
 $L$ untere $\bigtriangleup$--Matrix mit 1--Diagonale, $|l_{ij}| \le 1$.\\
Die $k$--te Spalte von $L$ ist unterhalb der Diagonalen eine permutierte 
Version des $k$--ten Gau{\ss}-Vektors. \newline
Speziell f\"ur $M_k = I-t^{(k)} e_k^T$ gilt
\[
 L(k+1 : n,k) = g (k+1:n), \; g = P_{n-1} \cdots P_{k+1} t^{(k)}.
\]
\end{theorem}
%
\proof
Aus (\ref{2.1.44}) folgt
\[
 \tilde{M}_{n-1} \cdots \tilde{M}_1 PA = R \quad \mbox { mit }
\]
\begin{eqnarray*}
 \tilde{M}_{n-1} & = & M_{n-1},\\
 \tilde{M}_k & = & P_{n-1} \cdots P_{k+1} M_k P_{k+1} \cdots P_{n-1}, \;
                   k \le n - 2.
\end{eqnarray*}

Da $P_j$ nur Zeilen $j$ und $\mu \ge j$ vertauscht, so folgt
$P_j (1:j-1, 1:j-1) = I_{j-1}$. Also ist $\tilde{M}_k$ eine 
Gau{\ss}--Transformation mit Gau{\ss}--Vektor 
$\tilde{t}^{(k)} = P_{n-1} \cdots P_{k+1} t^{(k)}.$
\eproof
%
Durch die einfache Ersetzung von
\[
\begin{array}{rcl}
 A(k:k:n) &\longleftrightarrow& A(\mu, k:n) \mbox { durch }\\
 A(k,1:n) &\longleftrightarrow& A(\mu,1:n) \mbox{ in Algorithmus \ref{2.1.41} }
\end{array}
\]
%
gilt dann wieder $A(i,j)$ enth\"alt $L(i,j)$ f\"ur $i>j$ nach Ende des 
Algorithmus.

$\longrightarrow$ \"Ubung \ref{numI/uebung090}: Analoge GAXPY Version.

\underline{Fehleranalyse:} Da Permutationen rundungsfehlerfrei durchgef\"uhrt
werden k\"onnen, kann man analog zeigen, da{\ss} die berechnete L\"osung 
$\tilde{x}$ ~ $(A+E) \tilde{x} = b$ erf\"ullt mit
%
\eq{2.1.45}
 |E| \le n \eps \left(3 |A|+5 \tilde{P}^T |\tilde{L}|\,|\tilde{R}| \right)
 + {\cal O} (\eps^2),
\en
% 
wobei $\tilde{P}, \tilde{L}, \tilde{R}$ die berechneten $P, L, R$ sind.

Durch die Pivotisierung folgt
%
\[
\begin{array}{l}
 \| \tilde{L} \|_\infty \le n, \mbox { also folgt }\\
 \|E\|_\infty \le n \eps 
 \left( 3 \|A\|_\infty + 5n \|\tilde{R}\|_\infty \right)
 + {\cal O} (\eps^2).
\end{array}
\]
%
\underline{Problem:} Schranke f\"ur $\|\tilde{R}\|_\infty$.\\
Definiere den Wachstumsfaktor $\rho$ durch
%
\eq{2.1.46}
 \rho = \max\limits_{i,j,k} \frac{|\tilde{a}_{ij}^{(k)}|}{\|A\|_\infty},
\en
%
wobei $\tilde{A}^{(k)}$ die berechnete Version von $A^{(k)}$ ist. Dann folgt
%
\eq{2.1.47}
  \|E\|_\infty \le 8n^3 \rho \|A\|_\infty \eps + {\cal O}(\eps^2).
\en
%
Die Schranke h\"angt also wesentlich von $\rho$ ab 
($n^3$ ist i.a. vernachl\"assigbar in der Praxis, da nicht auftretend).\\
$\rho$ ist typisch von der Ordnung 10, kann aber $2^{n-1}$ sein.\\
$\longrightarrow$ \"Ubung \ref{numI/uebung021}.

Im allgemeinen ist Gau{\ss} mit partieller Pivotisierung zuverl\"assig
und kann relativ sorglos verwendet werden.
