\begin{enumerate}

\item Wir k\"onnen $B$ schreiben als 
\[
B=\underbrace{\pmatrix{1&0\cr
           0&0\cr
           \vdots&\vdots\cr
           0&0\cr
           0&1}}_U \underbrace{\pmatrix{0&b_{1n}\cr
           0&0\cr
           \vdots&\vdots\cr
           0&0\cr
           b_{n1}&0}^\top}_{V^\top}
\]

\item Sei $Cx=0$. Wir setzen $y=A^{-1}Ux$. 
      Dann erhalten wir
\[
(A+UV^\top) y= Ux+ UV^\top A^{-1}Ux = U(I+V^\top A^{-1}U)x=UCx=0.
\]
Daraus kann nur folgen, dass $y=0$ ist. Dann muss aber bereits $Ux=0$ sein.
Somit ist
\[
0=Cx= x+V^\top A^{-1}Ux=x.
\]
Damit ist $x$ selbst auch $0$. Also ist $C$ nichtsingul\"ar.
Die Formel selbst k\"onnen wir durch direktes Nachrechnen verifizieren.
\begin{eqnarray*}
(A+UV^\top) (A^{-1}-A^{-1}UC^{-1}V^\top A^{-1})
 &=& I + UV^\top A^{-1} - UC^{-1}V^\top A^{-1} \\
  && - UV^\top A^{-1}UC^{-1}V^\top A^{-1}\\
 &=& I + U(I - C^{-1}  - V^\top A^{-1}UC^{-1})V^\top A^{-1}\\
 &=& I + U(I - (I  + V^\top A^{-1}U)C^{-1})V^\top A^{-1}\\
 &=& I + U(I - CC^{-1})V^\top A^{-1}\\
 &=&0.
\end{eqnarray*}
\item Die Berechnung einer $LU$--Zerlegung f\"ur $A+B$ ohne Pivotisierung
      erfordert im wesentlichen 2 Divisionen, 4 Multiplikationen und 2
      Additionen pro Schritt. Man muss dabei ber\"ucksichtigen, dass bei
      der Eliminationen immer in der letzten Zeile und Spalte sukzessive ein
      zus\"atzlicher Eintrag entsteht, der aber zuvor $0$ war.
      Zusammengenommen ergibt das im wesentlichen
      $8n\flops$. Die Dreiecksfaktoren haben jetzt ebenfalls in der letzten
      Zeile bzw. Spalten lauter Nichtnull--Eintr\"age.
      Damit verteuert sich das Vorw\"artseinsetzen auf i.w. $4n\flops$
      und das R\"uckw\"artseinsetzen auf $5n\flops$. Also haben wir
      folgende Tabelle.

\begin{center}
\begin{tabular}{ll}
$A=LU$  & $8n\flops$\\
$Ly=b$  & $4n\flops$\\
$Ux=y$  & $5n\flops$\\
\end{tabular}
\end{center}



      Zusammengenommen kostet also das L\"osen von $(A+B)x=b$ mit Hilfe
      einer $LU$--Zerlegung von $A+B$ insgesamt
\[
\fbox{$\displaystyle 17n \flops$}
\]
     Bei gleicher Vorgehensweise f\"ur $A$ selbst erhalten wir pro Schritt
     $3$ \flops, also insgesamt $3n$\flops.
     Die L\"osung von $(A+B)x=b$ mit Hilfe der Sherman--Morrison--Woodbury
     Formel k\"onnte jetzt so ablaufen.
\[
x = (I-A^{-1}UC^{-1}V^\top ) A^{-1}b
\]
Wir setzen $y=A^{-1}b$ und $W=A^{-1}U$ und erhalten
\[
x = y-W(I-V^\top W)^{-1} V^\top y.
\]
Wir l\"osen zun\"achst $Ay=b$. Vorw\"arts--/R\"uckw\"artseinsetzen kosten
insgesamt $5n\flops$. 
Das L\"osen von $AW=U$ ist etwas billiger.
F\"ur die erste Spalte brauchen wir $n\flops$ f\"ur das Vorw\"artseinsetzen
und $3n\flops$ f\"ur das R\"uckw\"artseinsetzen.
F\"ur die zweite Spalte brauchen wir uberhaupt kein Vorw\"artseinsetzen
und das R\"uckw\"artseinsetzen kostet $2n\flops$.
Die Erzeugung von $C$ nach Berechnung von $W$ ist praktisch gratis
($V^\top W$ ben\"otigt nur 4\flops), genauso
wie das L\"osen mit $C$ (d.h. konstante Anzahl \flops).
Ebenso in konstanter Zeit l\"asst sich $V^\top y$ berechnen.
Haben wir dann erst mal $z=C^{-1} V^\top y$ in konstanter Zeit berechnet,
so erhalten wir $x$ aus $x=y+Wz$. Da $W$ in der Regel voll ist, kostet
das noch mal $4n\flops$. Fassen wir zusammen.
\begin{center}
\begin{tabular}{ll}
$A=LU$  & $3n\flops$\\
$Ay=b$  & $5n\flops$ ($2n\flops$ / $3n\flops$)\\
$AW=U$ & $6n\flops$ ($n\flops$ / $3n\flops$, \\
      & \phantom{$6n\flops$ } 0 $\flops$ / $2n\flops$)\\
$V^\top y$, $V^\top W$, $C=I-V^\top W$,  & konstante \flops\\
$C^{-1}$, $z=C^{-1}V^\top y$ & konstante \flops\\
$x=y+Wz$ & $4n\flops$
\end{tabular}
\end{center}

Wir erhalten also insgesamt 
\[
\fbox{$\displaystyle 18n \flops$}.
\]
Dies ist ein klein wenig ung\"unstiger.
Wir k\"onnen im Prinzip noch ein bisschen Zeit sparen, wenn wir $A+B$ schreiben
als
\[
\underbrace{(A-\pmatrix{b_{n1} & 0 & 0\cr 0 &0&0\cr 0&0&b_{1n}})}_{\tilde{A}}
 + \underbrace{\pmatrix{b_{n1} & 0 & b_{1n}\cr 0 &0&0\cr b_{n1}&0&b_{1n}}}_{\tilde{B}}
\]
schreiben. Denn $\tilde{B}$ hat Rang 1 und l\"asst sich z.B. in der Form
\[
\tilde{B}=\underbrace{\pmatrix{1\cr
           0\cr
           \vdots\cr
           0\cr
           1}}_U \underbrace{\pmatrix{b_{1n}\cr
           0\cr
            \vdots\cr
           0\cr
           b_{n1}}^\top}_{V^\top}
\]
schreiben.
Analoge \"Uberlegungen f\"uhren auf folgende Tabelle.

\begin{center}
\begin{tabular}{ll}
$\tilde{A}=LU$  & $3n\flops$\\
$\tilde{A}y=b$  & $5n\flops$\\
$\tilde{A}W=U$  & $4n\flops$ ($n\flops$ / $3n\flops$)\\
$V^\top y$, $V^\top W$, $C=1-V^\top W$,  $z=\frac{V^\top y}{C}$& konstant\\
$x=y+Wz$ & $2n\flops$
\end{tabular}
\end{center}

Also in diesem Falle h\"atten wir insgesamt sogar nur \fbox{$14n \flops$}.
\end{enumerate}
