\subsection{Die $QR$--Zerlegung.}

Die $QR$--Zerlegung einer Matrix $A \in \K^{m,n} (m \ge n)$ ist gegeben durch
\[
 A = QR
\]
mit $Q \in \K^{m,m}$ unit\"ar, $R \in \K^{m,n}$ obere $\bigtriangleup$--Matrix
$R = \left[ \begin{array}{c}
 \utri \\
  O \end{array}\right]$.\\
Falls $A$ vollen Rang hat, dann bilden die ersten $n$ Spalten von $Q$ eine
Orthonormalbasis f\"ur Bild $(A)$. Mit Hilfe der $QR$--Zerlegung kann man also
Orthonormalbasen f\"ur Mengen von Vektoren bestimmen.

\underline{L\"osung von Gleichungssystemen.}
%
\[
\begin{array}{rclcl}
 A x  &=& b &                     & A \in \K^{n,n}\\
 QR x &=& b & \Longleftrightarrow &c=Q^H b, \; Rx = c
\end{array}
\]
%
Anwendung von $Q^H$ auf $b$ nur Matrix--Vektor Multiplikation 
oder in faktorisierter Householder Form, mehrere innere Produkte. 
$Rx = c$ durch r\"uckw\"arts Aufl\"osen.

\underline{L\"osung von Ausgleichproblemen als n\"achstes:}

Wie erh\"alt man eine $QR$--Zerlegung?\\
Nacheinander Anwendung von Householder--Matrizen.
%
\[
 \left[ 
  \begin{array}{ccccc}
   {*}& * & * & * & *\\
   {*}& * & * & * & *\\
   {*}& * & * & * & *\\
   {*}& * & * & * & *\\
   {*}& * & * & * & *\\
   {*}& * & * & * & * 
  \end{array}
 \right], \; 
 P_1 A =  
 \left[ 
  \begin{array}{ccccc}
   {*}& * & * & * & *\\
   {0}& * & * & * & *\\
   {0}& * & * & * & *\\
   {0}& * & * & * & *\\
   {0}& * & * & * & *\\
   {0}& * & * & * & * 
  \end{array}
 \right], \; 
 P_2 P_1 A =  
 \left[ 
  \begin{array}{ccccc}
   {*}& * & * & * & *\\
   {0}& * & * & * & *\\
   {0}& 0 & * & * & *\\
   {0}& 0 & * & * & *\\
   {0}& 0 & * & * & *\\
   {0}& 0 & * & * & * 
  \end{array}
 \right], \;
 \mbox{ usw. }
\]
%
\begin{algorithmus}[Householder $QR$--Zerlegung]\label{2.3.6}\qquad\\
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{
			$A \in \K^{m,n}$ mit $m \ge n$.}\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{
			Householder--Matrizen $P_1, \dots , P_n$, so da{\ss}
			f\"ur $Q = P_1 \cdots P_n, Q^H A = R$ obere 
			$\bigtriangleup$--Matrix.
			Der obere $\bigtriangleup$--Teil von $A$ wird durch 
			$R$ \"uberschrieben und die Komponenten $j+1:m$ 
			des $j$--ten Householdervektors werden auf 
			$A(j+1:m,j), \;j < m$ \"uberschrieben.
		     }\\[1.5ex]
&FOR&\multicolumn{2}{l}{$j=1:n$}\\
&   &\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))$;}\\
&   &IF &$j < m$\\
&   &   &$A(j+1:m,j) = v(j+1:m)$;\\
&   &END&\\
&END&   &    
\end{tabular}
\end{algorithmus}
\underline{Kosten:} $2n^2 (m - \frac{n}{3})$ \flops.\\
\underline{Fehleranalyse:} $\tilde{Q}^*(A+E) = \tilde{R}$, wobei berechnetes
 $\tilde{Q}$ exakt unit\"ar und ${Q}^* \tilde{Q} = I+F, \; \|F\|_2 \approx \eps$, 
 $\|E\|_2 \approx  \eps \|A\|_2.$\\
$A$ sieht am Ende des Algorithmus wie folgt aus
%
\[
\left[ \begin{array}{ccccc}
 r_{11}   & r_{12}  &\cdots& \cdots    &r_{1,n}\\
 v^{(1)}_2& r_{22}  &      &           & \vdots\\
 v^{(1)}_3&v^{(2)}_3&\ddots&           & \vdots\\
 \vdots   & \vdots  &\ddots&r_{n-1,n-1}& \vdots\\
 \vdots   & \vdots  &      &v^{(n-1)}_n&r_{n,n}\\
 \vdots   & \vdots  &      & \vdots    &v^{(n)}_{n+1}\\
 \vdots   & \vdots  &      &\vdots     &\vdots\\
 v^{(1)}_m&v^{(2)}_m&\cdots&v_m^{(n-1)}&v^{(n)}_m
 \end{array}\right]
\]
%
Die $j$--te Komponente von $v^{(j)}$ ist jeweils 1. 
Falls $Q$ ben\"otigt wird, kostet das
\[
 4(m^2n - mn^2 + \frac{n^3}{3}) \flops. 
\]
%
