\documentclass[11pt]{article}

\usepackage{ngerman}
\usepackage{times}
\usepackage{a4wide}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ifthen}
\usepackage{tikz}
 \usetikzlibrary{calc}
\usepackage{setspace}
\usepackage{listing}
\usepackage{mathtools}

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{listings}
\usepackage{verbatim}

%\usepackage{tabularx} % For the MCQ


\usepackage[utf8x]{inputenc}
\PrerenderUnicode{ä}

\newcommand{\teiler}{\ifthenelse{\boolean{bloes}}{}{\bigskip \hrule \bigskip}}

% loesung an/aus
\newboolean{bloes}
\setboolean{bloes}{true}
%\setboolean{bloes}{false}


\pagestyle{empty}

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}

\makeatletter

%\newcounter{choicectr}
%\setcounter{choicectr}{1}
%\newenvironment{twochoices}[3][X]%
%{\stepcounter{choicectr}
% \expandafter\def\csname tcy\arabic{choicectr}\endcsname{#2}%
% \expandafter\def\csname tcn\arabic{choicectr}\endcsname{#3}%
% \tabularx{\linewidth}{@{}#1l@{}}
%}{\endtabularx}

%\newcommand{\choiceB}{
%\begin{oneparcheckboxes}
%\choice        \csname tcy\arabic{choicectr}\endcsname
%\CorrectChoice \csname tcn\arabic{choicectr}\endcsname
%\end{oneparcheckboxes}}
%\newcommand{\choiceA}{
%\begin{oneparcheckboxes}
%\CorrectChoice \csname tcy\arabic{choicectr}\endcsname
%\choice        \csname tcn\arabic{choicectr}\endcsname
%\end{oneparcheckboxes}}
%\newcommand{\choiceAB}{
%\begin{oneparcheckboxes}
%\CorrectChoice \csname tcy\arabic{choicectr}\endcsname
%\CorrectChoice \csname tcn\arabic{choicectr}\endcsname
%\end{oneparcheckboxes}}
%\newcommand{\choiceX}{
%\begin{oneparcheckboxes}
%\choice \csname tcy\arabic{choicectr}\endcsname
%\choice \csname tcn\arabic{choicectr}\endcsname
%\end{oneparcheckboxes}}


% eingabedaten
\newcommand{\ausgabe}{3. M\"arz 2020}
% Anzahl Bonus-Punkte
\newcommand{\nBonus}{6}

% aufgabenumgebung
\newcounter{problemnr}
\renewcommand{\theproblemnr}{\arabic{problemnr}}

\newsavebox{\punkte}
\newenvironment{problem}[1]%
{	\stepcounter{problemnr}%
	\ifthenelse{\equal{#1}{1}}%
	{\sbox{\punkte}{\textbf{#1 Punkt}}}%
	{\sbox{\punkte}{\textbf{#1 Punkte}}}%
	\noindent \textbf{Aufgabe {\theproblemnr}} {\hspace*{\fill} \usebox{\punkte}} \par \par} %
{\par \bigskip}

\newenvironment{zusatz}[1]%
{	\stepcounter{problemnr}%
	\ifthenelse{\equal{#1}{1}}%
	{\sbox{\punkte}{\textbf{#1 Bonus-Punkt}}}%
	{\sbox{\punkte}{\textbf{#1 Bonus-Punkte}}}%
	\noindent \textbf{Zusatzaufgabe {\theproblemnr}} {\hspace*{\fill} \usebox{\punkte}} \par \par} %
{\par \bigskip}

\newcommand{\loesung}[1]%
{ \ifthenelse{\boolean{bloes}}{\textbf{L\"osung:} \par #1 \newpage}{}} 

\newcommand{\correctChoiceB}%
{ \ifthenelse{\boolean{bloes}}{& $\square$ & $\blacksquare$}{& $\square$ & $\square$}} 

\newcommand{\correctChoiceA}%
{ \ifthenelse{\boolean{bloes}}{& $\blacksquare$ & $\square$}{& $\square$ & $\square$}} 

\newcounter{magicrownumbers}
\newcommand\rownumber{\stepcounter{magicrownumbers}(\roman{magicrownumbers}) }

\newcommand{\trueStatement}[1]
{\rownumber #1 \correctChoiceA \medskip \\} 
\newcommand{\wrongStatement}[1]
{\rownumber #1 \correctChoiceB \medskip \\} 

\newenvironment{trueOrFalse}{
%\renewcommand{\arraystretch}{2}
\setcounter{magicrownumbers}{0}
	\begin{tabular}{p{11.9cm}@{\hskip 0.9cm}cc}
& wahr&falsch \\

}{\end{tabular}}

\newcommand{\seitenwechsel}%
{ \ifthenelse{\boolean{bloes}}{}{\vfill \hfill \textbf{bitte wenden!}\newpage}}


\newcommand{\zwp}[1]{\hspace*{\fill}(\ifthenelse{\equal{#1}{1}}%
	{#1~Punkt}%
	{#1~Punkte})}

\newcommand{\tp}[1]{\textbf{(\ifthenelse{\equal{#1}{1}}{#1~Punkt}{#1~Punkte})}}


%aufzaehlungen
\newcounter{enuma}
\newenvironment{enumeratea}{\begin{list}{(\alph{enuma})}%
{\usecounter{enuma}%
\setlength{\topsep}{0mm}%
\setlength{\partopsep}{0mm}%
\setlength{\itemsep}{0mm}%
\setlength{\labelsep}{2mm}%
\setlength{\labelwidth}{5mm}%
\setlength{\leftmargin}{0mm}%
\addtolength{\leftmargin}{\labelwidth}%
\addtolength{\leftmargin}{\labelsep}%
\setlength{\itemindent}{0mm}%
}}{\end{list}}

\newenvironment{enumeratei}{\begin{list} {(\roman{enumi})}%
{\usecounter{enumi}%
\setlength{\topsep}{0mm}%
\setlength{\partopsep}{0mm}%
\setlength{\itemsep}{0mm}%
\setlength{\labelsep}{2mm}%
\settowidth{\labelwidth}{(viii)}%
\setlength{\leftmargin}{1mm}%
\addtolength{\leftmargin}{\labelwidth}%
\addtolength{\leftmargin}{\labelsep}%
\setlength{\itemindent}{0mm}%
}}{\end{list}}


\makeatother



\begin{document}
\textbf{\large Technische Universit\"{a}t Berlin}\hfill{}Wintersemester 2019/20\\
 \textbf{Fakult\"{a}t II; Institut f\"{u}r Mathematik}\\
 Prof. Dr. Volker Mehrmann, Marine Froidevaux \hfill{} \ausgabe

\bigskip\bigskip


\begin{center}\textbf{\Large Numerische Mathematik I}
  \textbf{}\\ \medskip \textbf{\large \ifthenelse{\boolean{bloes}}{L\"osung zur }{} Modulklausur}\\

\end{center}

\medskip{}


\textbf{Pers\"onliche Angaben:} \\[1cm]
\begin{tabular}[h]{ll}
  Name: & ............................................................................................................ \\[0.7cm]
  Vorname: & ............................................................................................................\\[0.7cm]
  Studiengang: & ............................................................................................................\\[0.7cm]
  Matrikelnummer: & ............................................................................................................
\end{tabular}

\vspace*{1cm}

Mit der Ver\"offentlichung des Ergebnisses meiner Klausur
(Matrikel-Nr. und Punktzahl) im Internet auf der ISIS-Seite des Kurses bin ich einverstanden (wenn ja bitte unterschreiben, sonst nicht):\\[2em]
\hspace*{4cm}
Unterschrift: .................................................................................

\bigskip

\noindent Für diese Klausur ist \textbf{kein Hilfsmittel} erlaubt. Die 
Bearbeitungszeit betr\"agt \textbf{90 Minuten}. Bitte f"ur jede neue Aufgabe 
ein eigenes Blatt anfangen.  Die einzelnen Bl\"atter sollen jeweils mit 
\textbf{Namen und Matrikelnummer beschriftet} werden. 
Alle Antworten sind ausreichend zu begr\"unden und Rechenwege anzugeben!
Es gibt insgesamt 40 Punkte und \nBonus~Bonus-Punkte, und die Klausur gilt als bestanden, wenn insgesamt mindestens 
\textbf{20 Punkte} erreicht sind. 
%Als Hilfsmittel sind Stift (kein Bleistift, kein roter Stift) und Papier, sowie ein (beidseitig, eigenh\"andig handbeschriebenes, nicht kopiertes) Formelblatt zugelassen!
Bitte den Ausweis f\"ur Studierende und einen amtlichen Lichtbildausweis bereit halten! 
\bigskip





\newcommand{\abstand}{0.8cm}
\begin{center}
	{\bf Bitte dieses Feld NICHT ausf\"ullen:}
	
\begin{tabular}{|l|c|c|c|c|c|c|c|c|}\hline
Aufgabe&1&2&3&4&5&6&Summe&Note\\[0.5em]\hline
Punkte&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}&\hspace*{\abstand}\\[3ex]\hline
Korrektor&&&&&&&&\\[3ex]\hline
\end{tabular}
\end{center}

\vspace{0,5cm}

\ifthenelse{\boolean{bloes}}{\newpage}{}

%\bigskip
\newpage
%%%%%%%%%%%%%%%%% Inerpolation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}{6}
%\begin{myquestion}[Multiple Choice]{11} 
In der gesamten Aufgabe 1 sind keine Beweise erforderlich. 

Sei im Folgenden $n\in \mathbb{N}$ und seien $(x_i, f_i)\in \mathbb{R}\times \mathbb{R}$, $i=0,\ldots,n$ gegebene Stützstellen, wobei $x_0< x_1< \ldots< x_n$. Des Weitern bezeichnen $L_0,\ldots, L_n$ und $N_0,\ldots, N_n$ jeweils die Lagrange\--Interpolations\-polynome und die Newton-Interpolationspolynome bezüglich der Stellen $x_0, \ldots, x_n$. Zudem bezeichne $\Pi_{n}$ den Vektorraum der Polynome vom Grad höchstens $n$ mit reellen Koeffizienten.

Entscheiden Sie im Folgenden, ob die gegebenen Aussagen (immer) wahr oder (im Allgemeinen) falsch sind. 
Für jede Teilaufgabe a), b), ..., f) gibt es insgesamt 1 Punkt, wenn alle Antworten richtig sind. Wenn mindestens eine Antwort fehlt oder falsch ist, gibt es für die bestimmte Teilaufgabe 0 Punkte.

\begin{enumeratea}%[leftmargin=1.7em,itemindent=0pt,itemsep=1ex]
\item Sei $n\geq 1$. Es exisitiert ein...

\begin{trueOrFalse}
%
\wrongStatement{... eindeutiges Polynom $p\in\Pi_{n+1}$, das alle $n+1$ Stützstellen interpoliert.}
%
\wrongStatement{... eindeutiger kubischer Spline, der alle  $n+1$ Stützstellen interpoliert.}
%
\trueStatement{... eindeutiger linearer Spline, der alle  $n+1$ Stützstellen interpoliert.}
%
%Es existert ein eindeutiges Fourier Polynom, das alle  $n+1$ Stützstellen interpoliert. \correctChoiceB
%\end{tabular}
\end{trueOrFalse}
\item Man möchte die $n+1$ Stützstellen mit einem Polynom $p\in \Pi_{n}$ interpolieren und das Polynom an $N$ Zwischenpunkten $y_j$, $j=1,\ldots,N$ auswerten.

%\begin{tabular}{p{11.5cm}cc}
%& wahr&falsch \\
\begin{trueOrFalse}
%
%\trueStatement{Sind $n=3$, $N=1$, $(x_0, f_0)=(0,0)$, $(x_1, f_1)=(1,1)$, $(x_2, f_2)=(2,0)$, dann gilt $p(0.5)=0.75$.}
%
\wrongStatement{Wenn $n, N\gg10$, so ist für die Auswertung an den Zwischenpunkten $y_1,\ldots, y_N$ das Neville-Aitken-Verfahren schneller als das Verfahren der dividierten Differenzen kombiniert mit dem Horner-Schema.}
%
\trueStatement{Die Auswertung von $p$ an jedem Zwischenpunkt $y_j$ kann mit dem Horner-Schema in $\mathcal{O}(n)$ (wenn $n\to\infty$) Operationen (flops) durchgeführt werden.}
%\end{tabular}
\end{trueOrFalse}

\item Sei sp$\colon \Pi_n\times \Pi_n \to \mathbb{R}$ ein durch $(f,g) \mapsto$ sp$(f,g):= \sum_{j=0}^n f(x_j) g(x_j)$ definiertes Skalarprodukt. Bezüglich dieses Skalarprodukts bilden...

\begin{trueOrFalse}
\wrongStatement{... die Monome $1, x, x^2,\ldots, x^n$ eine orthogonale Basis von $\Pi_n$.}
\trueStatement{... die Lagrange-Polynome $L_0, \ldots, L_n$  eine orthogonale Basis von $\Pi_n$.}
\wrongStatement{... die Newton-Polynome $N_0, \ldots, N_n$ eine orthogonale Basis von $\Pi_n$.}
\end{trueOrFalse}

\item Sei $n=2$.\\
\begin{trueOrFalse}
\trueStatement{Sind $x_0=0$, $x_1=1$, $x_2=3$, $f_j= 2^{x_j}$, $j=0,1,2$, so gilt für die dividierte Differenz
$f[x_0 , x_1, x_2] = \frac{2}{3}$. }
\trueStatement{Das Interpolationspolynom  $p\in\Pi_n$ ist durch
\[
p(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} f_0 + \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} f_1 + \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} f_2
\]
gegeben.}
%\wrongStatement{Wenn $n=1$, so ist das Interpolationspolynom $p\in\Pi_n$ durch \[p(x)=f_0(x-x_0) + \frac{f_1-f_0 }{x_1-x_0} (x-x_0)(x-x_1)\] gegeben.}
\end{trueOrFalse}
\item Gegeben seien ein Intervall $[a, b]\subset \mathbb{R}$ und eine beliebige stetige Funktion $f$. Seien $x_0=a$, $x_n=b$ und $f_j=f(x_j)$ für $j=0,\ldots, n$. Zudem sei $p\in\Pi_n$ das Interpolationspolynom bezüglich der Stützstellen $(x_0, f_0)$, $\ldots,$ $(x_n, f_n)$. \\
\begin{trueOrFalse}
\trueStatement{Ist die Funktion $f$ $(n+1)$-mal stetig differenzierbar und $x\in[x_0, x_n]$, dann gilt
\[
f(x)-p(x) =\frac{f^{n+1}(\xi)}{(n+1)!}\prod\limits_{j=0}^n (x-x_j)
\]
für ein $\xi \in [x_0, x_n]$.}
\wrongStatement{Sind die Stützstellen äquidistant, dann gilt für den globalen Fehler $$\max_{x\in[x_0, x_n]}|f(x)-p(x)|\to 0,\quad \text{ wenn } n\to \infty.$$ }
\trueStatement{Wenn $f\in\Pi_n$, dann gilt $p(x)=f(x)$ für alle $x\in\mathbb{R}$.  }
\end{trueOrFalse}
\item Sei $f$ eine $2\pi$-periodische stetige Funktion, $x_l=\frac{2\pi l}{n}$, $f_l=f(x_l)$ für $l=0,\ldots,n-1$ und $r,s\in\mathbb{N}$. Die diskrete Fourier-Transformierte von $f$ ist durch $\tilde f_{r,s}(x)=\sum_{k=-r}^s \tilde{c}_k e^{ikx}$ gegeben, wobei $\tilde{c}_k=\frac{1}{n}\sum_{l=0}^{n-1} f(x_l) e^{-ikx_l}$. \\
\begin{trueOrFalse}
\wrongStatement{Wenn $r$ und $s$ die Gleichung $r+s=n+1$ erfüllen, dann interpoliert $\tilde f_{r,s}$ die Funktion $f$ an den Stützstellen $(x_0, f_0), \ldots, (x_{n-1}, f_{n-1})$.}
\trueStatement{Ist $f$ eine reelle Funktion und $r=s$, dann ist die diskrete Fourier-Transformierte $\tilde f_{s,s}$ auch eine reelle Funktion.}
%\wrongStatement{Ist $f=\cos$ und $n=2$, dann gilt $\tilde f_{0,0}\equiv\frac{1}{2}$.}
\end{trueOrFalse}
%
%\item Seien $x_0, \ldots, x_n$ paarweise verschieden und sei $s$ eine kubische Spline, die die $n+1$-Stützstellen interpoliert und deren Ableitung an der Stützstellen durch $P'(x_j) = s_j$, $j=0,\ldots,n$ gegeben ist. Zudem sei $h_i\coloneqq x_i-x_{i-1}$ und $f[x_{i-1}, x_i]\coloneqq \frac{f_i-f_{i-1}}{h_i}$. Dann ist $P$ in jedem Intervall $[x_{j-1}, x_j]$ durch
%\[
%P(x)|_{[x_{j-1}, x_j]}=f_{i-1}+ \beta_i (x-x_{i-1}) + \gamma_i (x-x_{i-1})^2 + \delta_i (x-x_{i-1})^2 (x-x_{i})  
%\]
%gegeben, wobei ...\\
%\begin{trueOrFalse}
%\trueStatement{... $\beta_i=s_{i-1}$.}
%\wrongStatement{...$\gamma_i=\frac{f[x_i-1, x_i]}{h_i}$.}
%\wrongStatement{...$\delta_i=\frac{f[x_i-1, x_i]-s_{i-1}}{h_i}$.}
%\end{trueOrFalse}
%\item Noch eine 8. Frage?\\
%\begin{trueOrFalse}
%\trueStatement{Ja}
%\trueStatement{Nein}
%\wrongStatement{Vielleicht}
%\end{trueOrFalse}
%
%\item Sei $n\in\mathbb{N}$, $f(x)=x^n$ und $x_0,\ldots,x_n \in \mathbb{R}$ paarweise verschiedene Stützpunkte.\\
%\begin{trueOrFalse}
%Für die dividierte Differenz gilt
%$f[x_0 , x_1,\ldots, x_n] = 1$. \correctChoiceA\\
%\end{trueOrFalse}

%
%\item Sei $n\in\HN\setminus\lbrace 0\rbrace$ und $A\in\HR^{n, n}$.
%
%\begin{twochoices}{richtig}{falsch}
%Falls $A\in\HQ^{n, n}\subset \HR^{n, n}$, so ist $\det(A)$ eine rationale Zahl. & \choiceA \\
%Falls $A\in\HQ^{n, n}\subset \HR^{n, n}$, so sind alle Eigenwerte von $A$ rationale Zahlen. & \choiceB \\ 
%$A$ und $A^\trans$ haben das gleiche Minimalpolynom. & \choiceA \\
%
%\end{twochoices}
%
%
\end{enumeratea} 
\end{problem}
%%%%%%%%%%%%%%%%% Lineare GLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\teiler
\begin{problem}{9}
\begin{enumeratea}
\item Was ist eine Cholesky-Zerlegung und unter welchen Bedingungen besitzt eine reelle Matrix $A$ eine Cholesky-Zerlegung ? \tp{2}
\item Ist diese Zerlegung dann eindeutig? (Hier ist keine Begründung erforderlich.) \tp{1}
\item Besitzen insbesondere die folgenden Matrizen $A_1$ und $A_2$ eine Cholesky-Zerlegung? Begründen Sie Ihre Antwort! \tp{2}
\[
A_1=\begin{bmatrix}
16&4&-1\\4&-1&-2\\-1&-2&10
\end{bmatrix}, \qquad A_2=\begin{bmatrix}
2&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&2
\end{bmatrix}
\]
\item Betrachten Sie das folgende Problem:
Finde $x\in\mathbb{R}^2$, sodass $A_3x=b$, wobei $A_3= \begin{bmatrix}
1000 & 2 \\
200 & 1
\end{bmatrix}$ und $b=[2006, 403]^T$.
%Wie groß ist die Konditionszahl $\kappa_{\infty}(A_3)$? \tp{1}

Konstruieren Sie durch Zeilen-Spalten-Gleichgewichtung mit diagonalen Matrizen $D_1, D_2$ ein äquivalentes aber besser konditionniertes Problem, das $\kappa_{\infty}(D_1 A_3 D_2)\leq 10$ erfüllt. Berechnen Sie $\kappa_{\infty}(D_1 A_3 D_2)$ explizit. \tp{2}\\
%Hinweis: Für eine $2\times 2$-Matrix $M=\begin{bmatrix} a &b \\ c& d  \end{bmatrix}$ ist die Inverse $M^{-1}=\dfrac{1}{\det(A)} \begin{bmatrix} d &-b \\ -c& a  \end{bmatrix}$. 

\item Wie würden Sie das lineare Gleichungssystem 
\[
\begin{bmatrix}
 2   & 5   & 3 \\
 6   & 15 & 7 \\
 12 & 1   & 12
\end{bmatrix}  \begin{bmatrix}
 x_1 \\ x_2 \\ x_3
\end{bmatrix} 
= \begin{bmatrix}
1 \\
2 \\
 3
\end{bmatrix} 
\]
mit einem Verfahren aus der Vorlesung ohne Rechner lösen?
Beschreiben Sie Ihre Vorgehensweise. Das Gleichungssystem braucht hier nicht explizit gelöst werden! \tp{2}
\end{enumeratea}
\end{problem}
\loesung{
\begin{enumeratea}
\item Man sagt, dass $A=GG^T$ die Cholesky-Zerlegung der Matrix $A\in\mathbb{R}^{n\times n}$ ist, wenn $G$ die folgenden Bedingungen erfüllt:
\begin{itemize}
\item $G$ ist eine untere Dreiecksmatrix (alternative Definition wo $G$ eine obere Dreiecksmatrix ist, ist auch erlaubt).
\item $G$ hat positive Einträge auf der Diagonale.
\end{itemize}
Nicht jede Matrix kann in so einer Form zerlegt werden. Eine Matrix $A$ besitzt  eine Cholesky-Zerlegung genau dann, wenn sie die folgenden Bedingungen erfüllt:
\begin{itemize}
\item $A$ ist symmetrisch,
\item $A$ ist positiv definit, (d.h. $x^T Ax>0$ für jeden reellen Vektor $x\neq 0$ der zu $A$ passenden Größe. Hier braucht aber keine Definition von positiv Definitheit gegeben werden, da nicht explizit gefragt)
\end{itemize}  

\item Wenn eine Cholesky-Zerlegung existiert, dann ist sie auch eindeutig.

\item Die gegebene Matrix $A_1$ ist nicht positiv definit, da sie einen negativen Element auf der Diagonale hat. In der Tat gilt es $[0,1,0]A_1[0,1,0]^T<0$. Alternativ kann man rechnen, dass die Determinante des zweiten Hauptminors $\det\begin{bmatrix}
16 & 4\\4&-1
\end{bmatrix}=-32$ nicht positiv ist und aus dem Hauptminorkriterium folgt, dass die Matrix nicht positiv definit ist. 

Die Matrix $A_2$ ist symmetrisch (keine weitere Begründung dafür notwendig) und positiv definit, da für alle $x=[x_1, x_2, \ldots, x_4]^T\neq 0$ gilt 
$$
\begin{aligned}
 x^TA_2x& = 2x_1^2 - 2 x_1 x_2 + 2x_2^2- 2 x_2 x_3+ \ldots + 2x_4^2\\
 &=  x_1^2+(x_1-x_2)^2+ (x_2-x_3)^2+(x_3-x_4)^2+x_4^2>0,\\
 \end{aligned}
 $$
 Alternativ kann man die Determinante jedes Hauptminors berechnen
 \[
 \det A_{(1)} = 2, \quad  \det A_{(2)} = 3, \quad  \det A_{(3)} =4 \quad \det A_{(4)} = 2\cdot 4-(-1)(-4+1)= 5
 \]
 und merken, dass sie alle positiv sind. Aus dem Hauptminorkriterium folgt, dass die Matrix positiv definit ist.

\item Man skaliert zuerst die Zeilen von $A_3$ sodass alle Einträge $\leq$ 1 sind. Dafür benutzt man (z.B.) die Matrix $D_1=\text{diag}(1000^{-1}, 200^{-1})$ und erhalten $D_1A_3 = 
\begin{bmatrix}
 1 &\frac{2}{1000} \\ 1 & \frac{1}{200}
\end{bmatrix}.
 $ \tp{0.5} 
Man skaliert dann die Spalten, sodass (z.B.) der Maximal Eintrag in jeder Spalte genau gleich 1 ist.  Dafür benutzt man die Matrix $D_2=\text{diag}(1, 200)$ und bekommt 
$$B\coloneqq D_1A_3D_2 = 
\begin{bmatrix}
 1 &\frac{4}{10} \\ 1 & 1
\end{bmatrix}.
 $$\tp{0.5} 
 (Eine andere Skalierung, die auch zu einer Konditionszahl kleiner als 10 führt, ist auch erlaubt.)
Daraus folgt, $B^{-1}= \frac{10}{6} \begin{bmatrix}
 1 & -\frac{4}{10} \\ -1 & 1
\end{bmatrix}$ und daher $\kappa_{\infty}(B)= 2 \cdot \frac{10}{6}  2 = 10 \frac{2}{3}<10$. \tp{0.5} 
Das entsprechende Problem lautet: Finde $x\in\mathbb{R}^2$ sodass $D_2 x=y$ wobei $By = D_1 b$. \tp{0.5}


\item Man benutzt die LR-Zerlegung \textit{mit partieller Pivotisierung} um das lineare Gleichungssystem in die Form $LR x= Pb$ zu bekommen. \tp{1} Danach löst man das Gleichungssystem $Ly=Pb$ nach $y$ durch Vorwärts-Einsetzen und das Gleichungssystem $R x=b$ nach $ x$ durch Rückwärts-Einsetzen. \tp{1}
\end{enumeratea}
}
%\newpage
\teiler
%%%%%%%%%%%%%%%%%% Numerische Integration%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}{8}
\begin{enumeratea}
\item Berechnen Sie eine Approximation des Integrals $\int_{a}^b f(x)dx$, wobei $f(x) =-x^2+4$, $a=-2$, $b=2$. Verwenden Sie dazu die Extrapolationstechnik basierend auf der Romberg-Folge $h_1=b-a$, $h_2= \frac{b-a}{2}$, $h_3= \frac{b-a}{4}$ und den zugehörigen Trapezsummen. \tp{4}
%\item Bestimmen Sie $A$, $B$ und $\alpha\leq 0$, so dass die Quadraturformel
%\[ 
%A g(-\alpha) + B g(0) + A g(\alpha) \approx \int\limits_{-\pi}^\pi g(x) \text{d}x
%\]
%für Polynome möglichst großen Grades exakt ist. Geben Sie den Exaktheitsgrad an.
%\item Man leitet eine Quadraturformel der Form
%\[
%Q\{f\}(h):= \sum\limits_{j=0}^2 A_j f(jh)
%\]
%zur Approximation der Integralen
%\[
%I\{f\}(h)\coloneqq \frac{1}{\sqrt{2h}} \int\limits_0^{2h} \frac{1}{\sqrt{x}} f(x) dx 
%\]
%her, die für jedes Polynom zweites Grades exakt ist.

\item Es ist bekannt, dass die Simpson-Regel für die numerische Integration einer viermal stetig differenzierbaren Funktion $f$ in einem Intervall $I\coloneqq [a, b]$ den Fehler 
\[
H^5\frac{1}{90}|f^{(4)}(\xi)|\qquad \text{ für ein } \xi\in (a,b)
\] mit $H=\frac{b-a}{2}$ ergibt. Basierend auf der Simpson-Regel definieren Sie die \textit{summierte} Simpson-Regel zur numerischen Integration der Funktion $f$ im Intervall $I$ und zeigen Sie, dass es ein Verfahren vierter Ordnung ist. \tp{4}
\end{enumeratea}
\end{problem}
\loesung{
\begin{enumeratea}
\item Zuerst berechnet man die nötigen Auswertungen der Funktion $f$ : \begin{center}
\begin{tabular}{c|c c c c c}
$x$ & -2& -1& 0& 1 &2\\
\hline
$f(x)$& 0 & 3& 4& 3&0
\end{tabular}
\end{center}
Daraus folgt für die Trapezsummen $T_{h_j}\coloneqq \frac{f(-2) + 2f(-2+h_j) + \ldots +2f(2-h_j) + f(2)}{2} h_j  $
\begin{center}
\begin{tabular}{c|c c c c c}
$j$ & 1 &2&3\\
\hline
$h$ & 4& 2& 1\\
\hline
$T_h$& $\frac{0+0}{0}4=0$ & $\frac{2\cdot 4}{2}2 =8$ & $\frac{2\cdot 3+2\cdot 4+2\cdot 3}{2}1 =10$
\end{tabular}
\end{center}
Jetzt wenden wir das Neville-Aitken-Schema um das Interpolationspolynom zu den Stützstellen $(h_j^2, T_{h_j})$ in $h^2=0$ auszuwerten:
\begin{center}
\begin{tabular}{c|c c c c c}
$16$ & 0 & $\frac{8(0-16)-0(0-4)}{-12} = \frac{32}{3}$& $\frac{32(0-16)-32(0-1)}{3\cdot (1-16)}=\frac{32}{3}\frac{-15}{-15} =10+\frac{2}{3}$\\
$4$ & 8& $\frac{10(0-4)-8(0-1)}{-3} = \frac{-40+8}{-3}=\frac{32}{3}$& \\
$1$& 10 & 
\end{tabular}
\end{center}
Das Integral wird also durch $10.\overline{6}$ approximiert. (Der Wert ist in diesem Fall genau, da $\left[-\frac{x^3}{3} + 4x \right]_{-2}^2 = -\frac{8}{3}-\frac{8}{3}+4(2+2)=\frac{-16+3\cdot 16}{3} = \frac{32}{3}$)
%\item 
%Man fordert, dass
%\[
%A p(-\alpha) + B p(0) + A p(\alpha) = \int\limits_{-\pi}^\pi p(x) \text{d}x
%\]
%für alle Polynome $p$ möglichst hohen Grades erfüllt sein soll. Aus der Linearität genügt es diese Exaktheit für Monome zu fordern. Eingesetzt ergegeben folgende Gleichungen:
%\begin{center}
%\begin{tabular}{r|l}
%$1$&$2\pi=2A+B$ \\
%$x$&$0=0$\\
%$x^2$&$\frac{2}{3}\pi^3=2A\alpha^2$ \\
%$x^3$&$0=0$\\
%$x^4$&$\frac{2}{5}\pi^5=2A\alpha^4$ \\
%$x^5$&$0=0$\\
%$x^6$&$\frac{2}{7}\pi^7=2A\alpha^6$ \\
%\end{tabular}
%\end{center}
%Die drei ersten Gleichungen sind erfüllt unter der Bedingungen $B=2(\pi-A)$ und $\alpha^2 = \frac{\pi^3}{3A}$. Setzt man diese Ausdrucken in der fünfte Gleichung, bekommt man die dritte Bedingung $\frac{2}{5}\pi^5=2A\frac{\pi^6}{9A^2}$. Daraus folgt $A=\frac{5}{9}\pi$ und daher $B=\frac{8}{9}\pi$ und $\alpha = \sqrt{\frac{3}{5}}\pi$. Mit diesen Werten ist die Gleichung für $x^6$ nicht erfüllt. 
%
%Somit hat die Quadraturformel den Exaktheitsgrad 5.
%\item
%Die Quadraturformel ist exakt für jedes Polynom zweites Grades, wenn $Q\{x^k \}(h) = I\{ x^k \}(h)$ für $k=0,1,2$ und für jeden $h>0$. Die folgenden Bedingungen müssen also erfüllt werden:
%\[ 
% A_0+A_1+A_2 = Q\{1\}(h) = I\{ 1 \}(h) = \frac{1}{\sqrt{2h}} [2\sqrt{x}]_{0}^{2h} = 2
%\]
%\[
%h(A_1+2 A_2) = Q\{x\}(h) = I\{ x \}(h) = \frac{1}{\sqrt{2h}} [\frac{2}{3}x^{3/2}]_{0}^{2h} = \frac{4h}{3}
%\]
%\[
%h^2(A_1+4 A_2) = Q\{x^2\}(h) = I\{ x^2 \}(h) = \frac{1}{\sqrt{2h}} [\frac{2}{5}x^{5/2}]_{0}^{2h} = \frac{8h^2}{5}
%\]
%Aus den zwei letzten Gleichungen folgt $2A_2=\frac{8}{5}-\frac{4}{3}$...
\item Das Intervall $I= [a, b]$ wird in $N$ Teilintervallen $I_j\coloneqq[y_i, y_{i+1}]$, $i=0,\ldots, N-1$ geteilt, wobei $y_i=a+2ih$ und $h=\frac{a-b}{2N}$. Das Integral über jedem Teilintervall wird mit der Simpson-Regel approximiert.
Dann gilt für den Fehler der summierten Simpson-Regel $S_{I}\{ f\}(h)$ in $I$
\[
e \coloneqq|S_{I}\{ f\}(h) - \int\limits_I f(x) \text{d}x| = |\sum\limits_{j=0}^{N-1} S_{I_j}\{ f\}(h) - \int\limits_{I_j} f(x) \text{d}x|  \leq \sum\limits_{j=0}^{N-1} h^5 \frac{1}{90} |f^{(4)}(\xi_j)|
\]
für bestimmte $\xi_j\in (y_j, y_{j+1})$, $i=0,\ldots, N-1$.
Also
\[
e \leq \frac{\Vert f^{(4)}\Vert_{\infty, {(a,b)}}}{90}Nh^5 \leq C h^4
\]
mit $C\coloneqq \frac{\Vert f^{(4)}\Vert_{\infty, {(a,b)}}}{90}\frac{(b-a)}{2}$, und daher ist die summierte Simpson-Regel ein Verfahren vierter Ordnung.
\end{enumeratea}
}
\teiler
%%%%%%%%%%%%%5 ODE - Anfangswertproblem %%%%%%%%%%%%%%%%%%%%%%
\begin{problem}{9}
Gegeben sei die eindimensionale gewöhnliche Differentialgleichung
\[
\frac{d y}{dt}(t) = a y(t) + f(t, y(t))
\]
mit dem Anfangswert $y(0)=y_0$ und $a>0$.
\begin{enumeratea}
\item Schreiben Sie das explizite und das implizite Euler-Verfahren auf, jeweils mit konstanter Schrittweite $h$ zur Lösung der Anfangswertaufgabe. \tp{2}
\item Sei die Funktion $f$ im zweiten Argument stetig differenzierbar und existiere eine Konstante $L>0$, so dass die Ungleichung
\[
\left|\frac{\partial f}{\partial y} (t,y)\right| \leq L
\]
für jedes $t\in\mathbb{R}$ und jedes $y\in\mathbb{R}$ gelte.
Die nichtlineare Gleichung der Form
\[
u_{i+1}= \psi(i,h,u_{i+1}, u_i) \eqqcolon \varphi_i(u_{i+1}),
\] die bei der impliziten Euler-Iteration aus a) entsteht, wird nach $u_{i+1}$ mit der Fixpunktiteration
\[
x^{(j+1)}=\varphi_i(x^{(j)}), \qquad j=0,1,2,\ldots
\]  gelöst. Geben Sie mit Hilfe des Banachschen Fixpunktsatzes hinreichende Bedingungen für $a$, $L$ und $h$ an, unter denen die Fixpunktiteration für jeden Startwert $x^{(0)}\in\mathbb{R}$ konvergiert. \tp{3}
%\item Bestimmen Sie die analytische Lösung $y(t)$ der Anfangswertaufgabe für den Fall, in dem die Funktion $f$ unabhängig von $y$ ist. (Hinweis: zum Beispiel mit der Methode der Variation der Konstanten oder mit Hilfe der Duhamel-Formel) \tp{1}
\item Sei $a=1$. Für $f(t, y)= \sqrt{y}$ und $f(t,y)=y+t$ führen Sie jeweils 3 Iterationen des expliziten Euler-Verfahrens mit dem Startwert $y_0=0$ und der Schrittweite $h = 2$. \tp{2}
\item Wie hängt die Konvergenz des expliziten Euler-Verfahrens (bezüglich der Schrittweite $h$) von der Funktion $f$ ab? Geben Sie eine Begründung an. \tp{2}
\end{enumeratea}
\end{problem}
\loesung{
\begin{enumeratea}
\item Für beide Iterationen ist der Startpunkt $u_0=y_0$. Danach (für $i=0,1,2,\ldots$) sind die Iterierte durch\\
%
\begin{center}
\begin{tabular}{ll} 
Explizit Euler :&$u_{i+1}=u_i+h\Big(au_i + f\big(ih, u_i\big)\Big)$\\
Implizit Euler :&$u_{i+1}=u_i+h\Big(au_{i+1} + f\big((i+1)h, u_{i+1}\big)\Big)$
\end{tabular}
\end{center}
gegeben.
%
\item Die Unbekannte $u_{i+1}$ ist gleich der Fixpunkt $x^*$ der Funktion $$\varphi_i(x) \coloneqq  u_i+h\Big(a x + f\big((i+1)h, x\big)\Big).$$
Laut dem Banachschen Fixpunktsatz konvergiert die dazugehörige Fixpunktiteration $x^{(j+1)} \coloneqq \varphi(x^{(j)})$, $j=0,1,2,...$ für einem Startpunkt $x^{(0)}$ wenn die Funktion $\varphi$ eine Kontraktion von einem abgeschlossenem Gebiet $D\ni x^{(0)}$ in sich ist. \tp{1} Für jeden  $x\in \mathbb{R}$ gilt
\[
|\varphi'(x) |= |h(a +\frac{\partial f}{\partial x}((i+1)h, x)) | \leq h(a+L)
\]
\tp{0.5} und 
\[
\begin{aligned}
\Vert \varphi(x) - x^* \Vert&=\Vert \varphi(x) - \varphi(x^*) \Vert = h\Vert a(x-x^*)+f((i+1)h, x)-f((i+1)h, x^*) \Vert \\
&\leq  h(a\Vert x-x^* \Vert+\Vert f((i+1)h, x)-f((i+1)h, x^*) \Vert)\\
&=  h(a\Vert x-x^* \Vert+\Vert \int_{x^*}^{x} \frac{\partial f}{\partial x}((i+1)h, s) \text{d}s \Vert ) \leq h(a+ L)\Vert x-x^* \Vert.
\end{aligned}
\]
\tp{1} Daher kann man für jeden Startwert $x_0\in\mathbb{R}$ den abgeschlossenem Kugel $D\coloneqq B_{|x_0-x^*|}(x^*)$ mit Radius $|x_0-x^*|$ um dem Fixpunkt betrachten. Die Funktion $\varphi:D\to D$ ist dann eine Kontraktion wenn $h<\frac{1}{a+L}$. \tp{0.5}

%\item Zuerst betrachten wir die homogene DGL $y'(t) = ay(t)$, wofür die Lösung durch $y(t) = ke^{a t}$ mit einer Integrationskonstante $k$ gegeben ist.
%Um die Lösung des inhomogenes Problem zu finden, benutzen wir z.B. die Methode der Variation der Konstante, d.h. wir machen den Ansatz $y(t) = k(t) e^{at}$. Daraus folgt
%\[
%y'(t) = k'(t) e^{at} + a k(t) e^{at} = k'(t) e^{at} +  a y(t).
%\]
%Sodass die inhomogene DGL erfüllt ist, muss
%\[
%k'(t) e^{at} = f(t, y(t))
%\]
%gelten, also 
%\[
%k(t) =\int\limits_{0}^t e^{-as} f(s, y(s)) \text{d}s + c
%\]
%wo $c$ eine Integrationskonstante ist. Aus der Anfangsbedingung folgt $y(0)=c=y_0$ und daher
%\[
%y(t) = y_0 e^{at} + \int\limits_{0}^t e^{a(t-s)} f(s, y(s)) \text{d}s.
%\]
%Alternativ kann man die Duhamel-Formel auswendig kennen.
\item Ist $f(t,y)=\sqrt{y}$, so gilt mit der expliziten Euler-Iteration 
$y_{1} = y_0+h(ay_0+\sqrt{y_0})= 0$, $y_{2} = y_1+h(ay_1+\sqrt{h})= 0$ und änhlich $y_3=0$.\\
Ist $f(t,y)=y+t$, so gilt mit der expliziten Euler-Iteration 
$y_{1} = y_0+h(ay_0+y_0+t_0)= 0$, $y_{2} = y_1+h((a+1)y_1+h)= h^2=4$ und $y_3= h^2+h((a+1)h^2+2h) = 3h^2+2h^3= 3\cdot 4+2\cdot 8=28$.
\item Wir wissen, dass das Verfahren konvergent mit Ordnung $p$ ist, wenn es konsistent mit Ordnung $p$ ist und die Inkrementfunktion Lipschitz-stetig im Argument $y$ ist. Wir wissen auch, dass das explizite Euler-Verfahren konsistent mit erster Ordnung ist.
Hier ist die Inkrementfunktion durch
\[
\Phi_{EE}(t,y,h)\coloneqq a y+ f(t, y) 
\]
gegeben, also
\[
|\Phi_{EE}(t,y_1,h) - \Phi_{EE}(t,y_2,h)| =  |a(y_1-y_2) + f(t, y_1)- f(t, y_1)| \leq a|y_1-y_2| + |f(t, y_1)- f(t, y_2)|
\]
und die Inkrementfunktion ist genau dann Lipschitz-stetig, wenn $f$ Lipschitz-stetig ist. Also das Verfahren ist konvergent mit ersten Ordnung, wenn $f$ Lipschitz-stetg ist.
\end{enumeratea}
}
\teiler
%\newpage
%%%%%%%%%%%%%% Matlab- Aufgabe / Nichtlineare GLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}{8}
\begin{enumeratea}
\item Schreiben Sie eine MATLAB-\ \ oder Python-Funktion 
\begin{center}
\verb+newton(phi, dphi, x0, resTol, kMax)+
\end{center} zur annähernden Berechnung einer Nullstelle einer skalaren Funktion $\phi$ mit dem Newton\--Verfahren.  
Die Ein- und Ausgabeparameter sind

\begin{tabular}{ll}
Eingabeparameter\\ \hline
\verb+phi+  &Funktion $\phi$\\
\verb+dphi+ &Ableitung $\phi'$ der Funktion $\phi$\\
\verb+x0+ &Startwert $x_0$ für die erste Iteration \\
\verb+resTol+  &Abbruchtoleranz; Iteration stoppt sobald $|\phi(x)| < \verb+resTol+ $ \\
\verb+kMax+ & Maximale Anzahl von Iterationsschritten
\end{tabular}

\begin{tabular}{ll}
Ausgabeparameter \\\hline
\verb+x+& Iterationsfolge der Näherungslösung\\
\verb+res+ &  $|\phi(x_i)|$, $i=0,1,2, \ldots$, Historie der Residuumsentwicklung\\ & für die einzelnen Näherungslösungen
\end{tabular}\\
\tp{5}

\item Gegeben sei das nichtlineare Gleichungssystem
\[
\begin{aligned}
x^2 + 4y^2 &= 9,\\
xy &= 1.
\end{aligned}
\]
\begin{enumerate}
\item Formulieren Sie das Gleichungssystem als ein äquivalentes Nullstellenproblem der Form $F(z)=0$ und zeigen Sie graphisch, dass es vier Lösungen gibt. \tp{1}
\item Berechnen Sie die Jacobi-Matrix $DF(z)$ und bestimmen Sie alle $z$ für die $DF(z)$ singulär ist. \tp{1}
\item Führen Sie ausgehend vom Startpunkt $z_0 = [1,1]^T$ einen Schritt des Newtonverfahrens für $F(z)$ durch und geben Sie die
Iterierte $z_1$ an. \tp{1}
\end{enumerate}

 \end{enumeratea}
\end{problem}
\loesung{

\begin{enumeratea}
\item Eine m\"ogliche L\"osung ist
\begin{align*}
&\texttt{function [x,res]=newton(phi,dphi,x0,tol,kmax)}\\
%&\texttt{function [x,res]=newton(phi,dphi,x0,tol,kmax)}\\
& \qquad \texttt{res  = phi(x0);}\\
& \qquad \texttt{D    = dphi(x0);}\\
& \qquad \texttt{x    = x0;}\\
& \qquad \texttt{while norm(res(:,end)) > tol \&\& size(x,2)<=kmax}\\
& \qquad\qquad \texttt{x(:,end+1)  = x(end) - D$\backslash$res(:,end);}\\
& \qquad\qquad \texttt{res(:,end+1)  = phi(x(:,end));}\\
& \qquad\qquad \texttt{D = dphi(x(:,end));}\\
& \qquad \texttt{end}\\
& \qquad \texttt{res = abs(res);}\\
& \texttt{end}
\end{align*}

Weitere L\"osungen sind m\"oglich.

\item
\begin{enumerate}
\item 
 Wir definieren $z\coloneqq[x,y]^T$ und $F(z)\coloneqq [x^2+4y^2-9, xy-1]^T$ (andere äquivalente Nullstellenproblem sind auch möglich). Die 4 Lösungen entsprechen die 4 Treffpunkte zwischen einer Ellipse und der (unstetigen) Kurve $y=\frac{1}{x}$.
\begin{center}
\begin{tikzpicture}
\draw[->] (-3,0) -- (4.2,0) node[right] {$x$};
      \draw[->] (0,-3) -- (0,4.2) node[above] {$y$};
      \draw[scale=0.5,domain=-3:3,smooth,variable=\x,blue] plot ({\x},{1/2*(9-\x*\x)^(0.5)});
      \draw[scale=0.5,domain=-3:3,smooth,variable=\x,blue] plot ({\x},{-1/2*(9-\x*\x)^(0.5)});
      \draw[scale=0.5,domain=-5:-0.15,smooth,variable=\y,red]  plot ({\y},{1/\y});
      \draw[scale=0.5,domain=0.15:5,smooth,variable=\y,red]  plot ({\y},{1/\y});
\end{tikzpicture}
\end{center}
\item $DF(z)=\begin{bmatrix}
2x& 8y \\ y& x
\end{bmatrix}$ ist singulär wenn $\text{det}(DF(x))=2x^2-8y^2=0$, also wenn $x=\pm 2y$.
\item $DF([1,1]^T) = \begin{bmatrix}
2& 8 \\ 1& 1
\end{bmatrix}\qquad \Rightarrow DF([1,1]^T)^{-1} =-\frac{1}{6} \begin{bmatrix}
1& -8 \\ -1& 2
\end{bmatrix}$  

$F([1,1]^T) = [-4, 0], \qquad DF([1,1]^T)^{-1}F([1,1]^T) = [\frac{2}{3}, -\frac{2}{3}]^T$

$\Rightarrow z_1 = [1,1]^T-[\frac{2}{3}, -\frac{2}{3}]^T = [\frac{1}{3}, \frac{5}{3}]^T$  
\end{enumerate}
\end{enumeratea}


}
\teiler
%%%%%%%%%%%%%%%%%%%%%%%% Bonus- Randwertaufgaben %%%%%%%%%%%%%%%%%%% 
\begin{zusatz}{\nBonus}
\begin{enumeratea}
\item Konstruieren Sie einen Differenzenquotienten für die dritte Ableitung, der zu einem Fehler der Größenordnung $\mathcal{O}(h^k)$, $k\geq1$ führt, wenn $h\to 0$. Finden Sie dazu sowohl ganze Zahlen $l,L\in\mathbb{Z}$ als auch reelle Koeffizienten $\alpha_l,\ldots, \alpha_L$ und $\beta\in\mathbb{R}$, sodass der Differenzenquotient
\[
D_3y(x) \coloneqq \frac{\sum\limits_{j=l}^L \alpha_j y(x+jh)}{\beta h^3}
\]  
die Bedingung 
\begin{equation}
\label{eq:QuotientFehler}
|D_3y(x) - y'''(x)| =\mathcal{O}(h) \quad \text{für }h\to 0
\end{equation}
erfüllt, wenn die Funktion $y\colon \mathbb{R}\to \mathbb{R}$ oft genug differenzierbar ist. Zeigen Sie, dass die Bedingung \eqref{eq:QuotientFehler} tatsächlich erfüllt wird. \tp{4}
 
 \item Diskretisieren Sie das folgende Randwertproblem 
 \[
 \begin{aligned}
 &y''(x) = \begin{bmatrix}
 1&0\\0&2
\end{bmatrix}  y(x),\\
&y(0) = [0,0]^T, \quad y(1) = [4, 4]^T
 &\end{aligned}
 \] mit Hilfe des zentralen Differenzenquotienten für die zweite Ableitung auf dem Gitter $\{x_i\coloneqq \frac{i}{3}, i=0,1,2,3 \}$.  Schreiben Sie die diskreten Gleichungen in der Form $A u = b$, wobei $A$ eine Matrix ist und $u,b$ Vektoren sind. \tp{2}
 \end{enumeratea}
\end{zusatz}
\loesung{
\begin{enumeratea}
\item 
Es ist bekannt, dass der Differenzenquotient
\[
D_2y(x)\coloneqq \frac{y(x-h)-2 y(x) + y(x+h)}{h^2}
\]
für die zweite Ableitung zu einem Diskretisierungsfehler der Ordnung $\mathcal{O}(h^2)$ führt, d.h.
\[
|D_2y(x)-y''(x)|=\mathcal{O}(h^2), \text{ wenn } h\to 0.
\]
Wir wenden den zentralen Differenzenquotienten (Vorwärts- oder Rückwärtsquotienten sind auch ok) für die erste Ableitung auf $D_2y(x)$ an und bekommen
\[
D_3y(x) = \frac{D_2y(x+h)-D_2y(x-h)}{2h} = \frac{y(x+2h) -2y(x+h) + 2y(x-h)-y(x-2h)}{2h^3}, 
\]
also wir wählen die Parameter $l=-2$, $L=2$, $\beta=2$, $\alpha_{-2} = -1$, $\alpha_{-1} = 2$, $\alpha_{0} = 0$, $\alpha_{1} = -2$, $\alpha_{2} = 1$.


Mit der Taylor-Entwicklung $y''(x\pm h) = y''(x) \pm y'''(x)h + \mathcal{O}(h^2)$ bekommen wir also
\[
\begin{aligned}
|D_3y(x) - y'''(x)| &= 
|\frac{y''(x+h)+\mathcal{O}(h^2)-y''(x-h)+\mathcal{O}(h^2)}{2h} - y'''(x)| \\
&= |\frac{y''(x) + y'''(x)h-y''(x) + y'''(x)h+\mathcal{O}(h^2)}{2h} - y'''(x)| = \mathcal{O}(h)
\end{aligned}
\]
wenn $h\to 0$.

\item Dank der Dirichlet Randbedingungen ist die Lösung in $x_0$ und $x_3$ bekannt, daher setzen wir $u_0=y(0)=0$ und $u_3=y(1)=4$.
Sei $u$ der Vektor der approximierte Lösung in $x_1, x_2$, d.h. $u=[u_1^T,u_2^T]^T$ wobei $u_i = [u_{i,1}, u_{i,2}]^T\approx y(x_i)$ für $i=1,2$.
Wir müssen vier Gleichungen für die vier unbekannte Komponenten des Vektors $u$ erstellen.
Der zentrale Differenzenquotient für die zweite Ableitung ergibt
\[
\frac{u_{i-1}-2u_i+u_{i-1}}{h^2} \approx y''(x_i)
\]
für $i=1,2$ mit $h=1/3$. Das Einsetzen der Randbedingungen ergibt 
\[\left(
9
\begin{bmatrix}
-2&0&1&0\\
0&-2&0&1\\
1&0&-2&0\\
0&1&0&-2\\
\end{bmatrix} - \begin{bmatrix}
1&0&0&0\\
0&2&0&0\\
0&0&1&0\\
0&0&0&2\\
\end{bmatrix}\right) u = \begin{bmatrix}
0\\0\\-4\cdot 9 \\-4 \cdot 9
\end{bmatrix},
\]
also
\[
\begin{bmatrix}
-19&0&9&0\\
0&-20&0&9\\
9&0&-19&0\\
0&9&0&-20\\
\end{bmatrix} 
\begin{bmatrix}
 u_{1,1}\\ u_{1,2}\\  u_{2,1}\\ u_{2,2}
\end{bmatrix}
 = \begin{bmatrix}
0\\0\\-36 \\-36
\end{bmatrix},
\]
%\tp{1} für $A_2$ und $u$, \tp{1} für $A_1$, \tp{1} für $b$. 
Andere äquivalente Gleichungssysteme sind auch erlaubt.
\end{enumeratea}
}

\end{document}
