% Stand 03.04.2000, Matthias Bollhoefer
% Modified by Marine Foridevaux on 10.8.2019
% new LaTeX 2e
\documentclass[12pt,a4paper]{report}
\usepackage{latexsym,amssymb,german,a4wide,verbatim,xr}
\usepackage{fancyhdr} 
%\usepackage{pgffor}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{xcolor}
\usepackage{mathtools}

% use labels from a different document
%\usepackage{xr}
% optional \externaldocument[blablbla]{...} to avoid multiple labels \ref{blablablaLABEL}
% is used to get the correct references from the external document
%\externaldocument{../vorles/vorles}

% include graphical environment
%\usepackage{graphics}

% include self defined matrix symbols
%\usepackage{matrix}

%\newcommand*{\pathToExercises}{../../Material_NumerikI_Matthias}
% use selfdefined commands
%\input{\pathToExercises/vorles/meinstil.def}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{\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}}
\newcommand{\CurrentWeekNb}{5}
\newcounter{taskNb}
\stepcounter{taskNb}

\begin{document}
%\thispagestyle{AbgabeDatum}
\begin{center}
%{\LARGE Numerische Mathematik}\\[1.5ex]
%%{\large \CurrentWeekNb. \"Ubungsblatt}\\ 
{\Large Sketches of solutions for the exercise sheet \#\CurrentWeekNb }\\ 
{$\hookrightarrow$ Homeworks must be submitted by Thursday 21.11.19.}
\end{center}
%
%%\def\exerciseList{001, 002, 003}
\begin{enumerate}
\item[] \textbf{Solution \arabic{taskNb}} \stepcounter{taskNb}
Notation: $y^{(j)}(x):= \frac{\text{d}^j y}{\text{dx}^j}(x)$\\
Taylor expansions:
\[
\begin{aligned}
y(x+2h) & = \sum\limits_{j=0}^6 \frac{(2h)^j}{j!}y^{(j)}(x)  + \mathcal{O}(h^7) \\
y(x-2h) & = \sum\limits_{j=0}^6 (-1)^j\frac{(2h)^j}{j!}y^{(j)}(x)  + \mathcal{O}(h^7) \\
y(x+h) & = \sum\limits_{j=0}^6 \frac{h^j}{j!}y^{(j)}(x)  + \mathcal{O}(h^7) \\
y(x-h) & = \sum\limits_{j=0}^6 (-1)^j\frac{h^j}{j!}y^{(j)}(x)  + \mathcal{O}(h^7)
\end{aligned}
\]
Thus,
\[
\begin{aligned}
D^2 y(x) := a_2 y(x+2h)& + a_1 y(x+h) + a_0 y(x) + a_{-1} y(x-h) +a_{-2} y(x-2h) = \\
&(a_2 + a_1 + a_0 + a_{-1} + a_{-2}) y(x) \\
+& (2 a_2 + a_1 - a_{-1} - 2 a_{-2}) h y'(x) \\
+& (4 a_2 + a_1 + a_{-1} + 4 a_{-2}) \frac{h^2}{2} y''(x)\\
+& (8 a_2 + a_1 - a_{-1} - 8 a_{-2}) \frac{h^3}{3!} y'''(x) \\
+& (16 a_2 + a_1 + a_{-1} + 16 a_{-2}) \frac{h^4}{4!} y^{(4)}(x) \\
+& (32 a_2 + a_1 - a_{-1} - 32 a_{-2}) \frac{h^5}{5!} y^{(5)}(x) \\
+& (64 a_2 + a_1 + a_{-1} + 64 a_{-2}) \frac{h^6}{6!} y^{(6)}(x)\\
+& l(a_2, a_1, a_0, a_{-1}, a_{-2})\mathcal{O}(h^7)
\end{aligned}
\]
where $l(a_2, a_1, a_0, a_{-1}, a_{-2})$ represents a linear combination of the unknowns.

We want to find $a_2, a_1, a_0, a_{-1}, a_{-2}$ so that $|D^2 y(x) - y''(x)|=\mathcal{O}(h^4)$ for all (small) $h$, all $y$, all $x$. Clearly , we need that the factors in front of $y(x)$ and $y'(x)$ are zero.

Further we need the factor in front of $y''(x)$ to be 1. This implies that the unknowns $a_2, a_1, a_0, a_{-1}, a_{-2}$ must be of the order $-2$ in $h$. Therefore we need the factors in front of $y'''(x)$ and $y^{(4)}(x)$ to be zero as well, otherwise they would bring an error of the order $1$ and, respectively, $2$ in $h$.

This fixes 5 conditions on the 5 unknowns, which we can express in a linear system
\[
\begin{bmatrix}
1 & 1& 1&1&1\\
2&1&0&-1&-2\\
4&1&0&1&4\\
8&1&0&-1&-8\\
16&1&0&1&16
\end{bmatrix}
 \begin{bmatrix}
a_2\\a_1\\a_0\\a_{-1}\\ a_{-2}
\end{bmatrix}
= \begin{bmatrix}
0\\0\\ 2/h^2\\0\\ 0.
\end{bmatrix}
\]

We solve it (e.g. with the help of Matlab) and find $a_2=a_{-2}=-\frac{1}{12h^2}, a_1=a_{-1}=\frac{16}{12h^2}, a_0=\frac{-30}{12h^2}$.

We verify that these values satisfy
\[
 32 a_2 + a_1 - a_{-1} - 32 a_{-2} = 0
\]
 and 
\[
64 a_2 + a_1 + a_{-1} + 64 a_{-2} =\frac{8}{3h^2}. 
\]

Therefore we have $|D^2 y(x) - y''(x)|=\frac{8}{3h^2}\frac{h^6}{6!} y^{(6)}(x)+ \mathcal{O}(h^5) =  \mathcal{O}(h^4)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[] \textbf{Solution \arabic{taskNb}} \stepcounter{taskNb} 
We start by integrating the ODE
\[
u'(x) = \int\limits_{0}^{x} u''(s) \text{d}s + c_1 = -\int\limits_{0}^{x} f(s) \text{d}s + c_1 =: -F(x) + c_1.
\]
We integrate again and get (using integration by parts) 
\[
\begin{aligned}
u(x) &= -\int\limits_0^{x} F(s) \text{d}s + c_1x + c_2 = -[sF(s)]_{0}^x+\int\limits_0^{x} s f(s) \text{d}s + c_1x +c_2\\
&= -xF(x)+\int\limits_0^{x} s f(s) \text{d}s + c_1x +c_2 = -x\int\limits_{0}^{x} f(s) \text{d}s+\int\limits_0^{x} s f(s) \text{d}s + c_1x +c_2.
\end{aligned}
\]
We set the constants $c_1, c_2$ using the boundary conditions:
\[
u(0)=c_2=0, \qquad u(1)= -\int\limits_{0}^{1} f(s) \text{d}s +\int\limits_{0}^{1} f(s) \text{d}s+c_1 = 0,
\]
thus $c_1 = \int\limits_{0}^{1} f(s) \text{d}s -\int\limits_{0}^{1} f(s) \text{d}s$.
We conclude by replacing $c_1, c_2$ in the formula of $u(x)$.

Since the Green function is positive for all $x\in (0,1)$, the integral is positive when $f$ is. Therefore the solution $u(x)$ is also positive for all $x\in (0,1)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[] \textbf{Solution \arabic{taskNb}} \stepcounter{taskNb} 
\[
\delta = b-Au= \text{res}(u)
\]
\begin{align*}
\kappa(A):= &\max_{b, \delta \neq 0} \frac{\rho_V}{\rho_R}=\max_{b, \delta \neq 0} \frac{\Vert x^*-\tilde{x} \Vert \Vert   b \Vert}{\Vert x^* \Vert \Vert \delta \Vert}=\max_{b, \delta \neq 0} \frac{\Vert A^{-1}(b-(b+\delta)) \Vert \Vert   b \Vert}{\Vert A^{-1}b \Vert \Vert \delta \Vert} \\ &= \max_{ \delta \neq 0} \frac{\Vert A^{-1}\delta \Vert }{ \Vert \delta \Vert}  \max_{b \neq 0}\frac{\Vert   b \Vert}{\Vert A^{-1}b \Vert}= \vertiii{A^{-1}}  \max_{x^* \neq 0}\frac{\Vert  Ax^* \Vert}{\Vert x^* \Vert} 
=\vertiii{A^{-1}}  \vertiii{A} 
\end{align*}
\end{enumerate}
%%
\end{document}


