\documentclass[12pt,a4paper]{report}
\usepackage{latexsym,amssymb,german,a4wide,verbatim,xr}
\usepackage{fancyhdr} 
%\usepackage{pgffor}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{calc}



\lstset{
 %frame=tb,
  language=Matlab,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  %columns=flexible,
  basicstyle={\small\ttfamily},
  %numbers=none,
  %numberstyle=\tiny\color{gray},
  %keywordstyle=\color{blue},
  %commentstyle=\color{dkgreen},
  %stringstyle=\color{mauve},
  %breaklines=true,
  %breakatwhitespace=true,
  tabsize=3
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Layout
%\addtolength{\topmargin}{-15ex}
%\addtolength{\textheight}{20ex}
\pagestyle{fancy}
\setlength{\headheight}{28pt}
\lhead{Technische Universität Berlin\\Numerische Mathematik I - WS 2019/2020}
\rhead{Prof.~V.~Mehrmann\\M.~Froidevaux}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\vcenteredinclude}[1]{\begingroup
\setbox0=\hbox{\includegraphics[height=3cm]{#1}}%
\parbox{\wd0}{\box0}\endgroup}


\newcommand{\CurrentWeekNb}{13}
\newcommand{\vertiii}[1]{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert #1 
    \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}}
\newcounter{taskNb}
\stepcounter{taskNb}

\begin{document}
\begin{center}
%{\LARGE Numerische Mathematik}\\[1.5ex]
%%{\large \CurrentWeekNb. \"Ubungsblatt}\\ 
{\Large \CurrentWeekNb. \"Ubungsblatt}\\ 
{Lineare Gleichungssysteme: Kondition, LR- und Cholesky-Zerlegung}\\
%\\{Diese Aufgaben müßen spätestens am 24.10.19 in der Vorlesung abgegeben werden.}
%{Abgabe:} Spätestens am 24.10.19 in der Vorlesung\\[0.5cm]
\end{center}
%\begin{center}
\hfill{Abgabe: Spätestens am 30.1.20 am Anfang der Vorlesung}\\[0.5cm]
%\end{center}
%
%%\def\exerciseList{001, 002, 003}
%\begin{enumerate}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% Aufgabe 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{Theorieaufgabe \arabic{taskNb} (3+1+1+3 Punkte):} \stepcounter{taskNb} 
%
Gegeben sei die reelle $n\times n$-Matrix $M$, die in folgender Weise partitioniert sei:
\[
M= \begin{bmatrix}
A & B\\B^T& C
\end{bmatrix}.
\]
Dabei ist $A$ eine invertierbare $m\times m$ Matrix.
%Man berechne zunächst die LR-Zerlegung von $M$ und zeige:
\begin{enumerate}[label=(\alph*)]
 %\item $C-B^TA^{-1}B$ ist positiv definit.
 \item Man betrachtet zunächst den speziellen Fall, wo $m=n-1$ und $A$ eine obere Dreiecksmatrix ist (das gilt nur für (a)). Man berechne eine LR-Zerlegung von $M$ und zeige, dass $M$ genau dann invertierbar ist, wenn $C-B^TA^{-1}B\neq 0$ ist.
 \end{enumerate}
 Sei $M$ jetzt symmetrisch positiv definit und sei $M=GG^T$ die Cholesky-Zerlegung von $M$, wobei $G$ eine untere Dreieicksmatrix ist, die zu $M$ entsprechend partitioniert sei:
 \[
G=\begin{bmatrix}
G_{11} & 0\\G_{21}& G_{22}
\end{bmatrix}.
 \]  Man zeige weiter:
 \begin{enumerate}[resume,label=(\alph*)]
% \item Jede Matrix $M'=NN^T$, wobei $N$ eine nicht-singuläre Matrix ist, ist positiv definit.
 \item $G_{22}G_{22}^T=C-B^TA^{-1}B$.
 \item $C-B^TA^{-1}B$ ist positiv definit.
 %\item $\Vert G \Vert ^2 =\Vert G^T \Vert ^2 \geq \max\limits_{i=1,\ldots, n} g_{ii}^2$ wobei $g_{ii}$ die Diagonalelemente von $G$ bezeichnet.
% \item \[ \kappa_2(G)\geq \max\limits_{1\leq i,k\leq n} \left\Vert\frac{g_{ii}}{g_{kk}} \right\Vert \]
 \item $\kappa_2(G)=\kappa_2(G^T)=\sqrt{\kappa_2(M)}\leq\kappa_2(M)$.\\ %Hinweis: Dafür kann der Sprektralsatz benutzt werden.
\end{enumerate}
%
%Gegeben sei eine Matrix $A\in\mathbb{C}^{n+1, n+1}$ mit 
%\[
%A= \begin{bmatrix}
%R & v\\w^T& 0
%\end{bmatrix}, \quad R\in\mathbb{C}^{n,n}, \quad v,w\in\mathbb{C}^{n}
%\]
%Zusätzlich sei $R$ eine invertierbare obere Dreiecksmatrix.
%\begin{itemize}
%\item Geben Sie die LR-Zerlegung der Matrix $A$ an.
%\item Zeigen Sie, dass $A$ genau dann nichtsingulär ist, wenn $w^T R^{-1}v\neq 0$.
%\end{itemize}
%
\textbf{Theorieaufgabe \arabic{taskNb} (2 Punkte):}\stepcounter{taskNb} 
%
Im Gauß-Eliminationsverfahren können die Operationen auf die Zeilen einer Matrix $A$ als Matrixmultiplikation von der linken Seite $A' = M_jA$ dargestellt werden. Z.B. wenn $A\in\mathbb{R}^{3\times 3}$ und
\[
M_1= \begin{bmatrix}
1&0&0\\-m_1&1&0\\-m_2& 0&1
\end{bmatrix},
\]
dann ist $A'$ die Matrix, die man erhält, wenn man in der Matrix $A$ von der zweiten Zeile das $m_1$-fache der ersten Zeile abzieht, und von der dritten Zeile das $m_2$-fache der ersten Zeile abzieht.
Rechnen Sie die Inverse der Matrix $M$.\\
Zeigen Sie, dass die Matrix $L\in \mathbb{R}^{n\times n}$ einer LR-Zerlegung ohne Pivotisierung $A=LR$ als Produkt $L=\prod\limits_{j=1}^{n-1} M_j^{-1}$ ausgedruckt werden kann, wobei $M_j$ nur nicht-Null Einträge auf der Diagonale und in der $j$-ten Spalte hat.\\[0.3cm]
%
\textbf{Theorieaufgabe \arabic{taskNb} (3 Punkte):} \stepcounter{taskNb} 
Ist die Matrix 
\[
A=\begin{bmatrix}
4 & 2 & 6\\ 2 &10 &0 \\ 6& 0&35
\end{bmatrix}
\]
symmetrisch und positiv definit?
Wenn ja, berechnen Sie ihre Cholesky-Zerlegung. Ansonsten berechnen Sie ihre LR-Zerlegung.
 \\[0.3cm]
%
\textbf{Theorieaufgabe \arabic{taskNb} (3 Punkte):} \stepcounter{taskNb}
Gegeben sei die Matrix 
\[
A=\begin{bmatrix}
1&2\\-2000&1000
\end{bmatrix}.
\]
\begin{enumerate}[label=(\alph*)]
\item Berechnen Sie $\kappa_{\infty}(A)$.
\item Skalieren Sie die Matrix durch Linksmultiplikation mit einer Diagonalmatrix $D$, so dass beide Zeilen ungefähr gleiche $\infty$-Norm haben.
\item Berechnen Sie $\kappa_{\infty}(DA)$ und vergleichen Sie mit $\kappa_{\infty}(A)$. Was stellen Sie fest?
\end{enumerate}
\textbf{Programmieraufgabe (4 Punkte):} Implementieren Sie den Algorithmus der Cholesky-Zerlegung aus der Vorlesung in einer Funktion
\begin{lstlisting}
  function G = cholesky(A)
\end{lstlisting}
und testen Sie ihn mit: 
\begin{lstlisting}
  L = rand(15,15);
  A=L*L';         % A ist s.p.d.
  G = cholesky(A);
  err=max(max(A-G*G'))
\end{lstlisting}
Untersuchen Sie die Komplexität des Algorithmus (Anzahl der nötigen Flops), indem Sie die Rechenzeit für verschiedene Matrizen der Größe $n$ messen, wobei $n$ in 
\begin{lstlisting}
  nSamples = round(logspace(1,3.2,10));
\end{lstlisting}
ist. Messen Sie für jedes $n$ die Rechenzeit bei 3 verschiedenen zufällig gebauten symmetrischen positiv definiten $n\times n$-Matrizen. Plotten Sie anschließend die durchschnittliche Rechenzeit $\bar{t}$ in einem Log-log-Plot (d.h. log($\bar{t}$) versus log($n$)). Schätzen Sie die Zuwachsrate der Kurve mit Hilfe der Funktion \texttt{polyfit} (siehe z.B. PA2) und interpretieren Sie den Unterschied mit der analytisch gerechneten Komplexität $\mathcal{O}(n^3/3)$.

\end{document}

