\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}
\usepackage{pgfplots}
\pgfplotsset{compat=1.12}


\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}{14}
\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: Nichtlineare Gleichungssysteme}\\
%\\{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 6.2.20 am Anfang der Vorlesung}\\[0.5cm]
%\end{center}
%
%%\def\exerciseList{001, 002, 003}
%\begin{enumerate}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% Aufgabe 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{Theorieaufgabe \arabic{taskNb} (3+2+1+1 Punkte):} \stepcounter{taskNb} 
%
In der Newton-Methode ist die Auswertung der Jacobi-Matrix in jedem Schritt sehr teuer. Alternativ kann man die Jacobi-Matrix und ihre LR-Zerlegung $DF(x_0)=LR$ nur im ersten Schritt berechnen und die Iteration 
\begin{equation}
\label{eq:Newton-Corde}
x_{n+1} = x_n - DF(x_0)^{-1} F(x_n) = x_n - R^{-1}L^{-1} F(x_n), \quad n=0,1,2,3,\ldots
\end{equation}
verwenden.
\begin{enumerate}[label=\alph*)]
%\item Zeigen Sie, dass \eqref{eq:Newton-Corde} eine Fixpunkt-Iteration ist.
\item Sei $F\colon \mathbb{R}^m\to \mathbb{R}^m$ stetig differenzierbar und $\bar{x}\in\mathbb{R}^m$ eine einfache Nullstelle von $F$, d.h. $F(\bar{x})=0$ und $DF(\bar{x})$ ist invertierbar. Zeigen Sie, dass ein $\epsilon>0$ existiert, sodass die durch \eqref{eq:Newton-Corde} definierte Folge $(x_n)^{\infty}_{n=0}$ mit einem Startwert $x_0$, $|\bar{x}-x_0|<\epsilon$ gegen $\bar{x}$ zumindest linear konvergiert.
%die Iteration zu einer Nullstelle $\bar{x}$ von $F$ konvergiert, wenn der Startwert $x_0$ nah genug an $\bar{x}$ ist.
\item Konvergiert diese Methode im Allgemeinen quadratisch, wenn $F$ hinreichend oft stetig differenzierbar und $\bar{x}$ eine einfache Nullstelle ist? Hier können Sie den Fall $m=1$ betrachten.
\item Geben Sie eine geometrische Interpretation der Methode an, indem Sie den Verlauf der Methode angewandt auf die Funktion $F(x)=0.3(x+1)^2-\cos(x)$ mit dem Startwert $x_0=2.6$ skizzieren.
\begin{center}
\begin{tikzpicture}
      \draw[->] (-1.5,0) -- (3.2,0) node[right] {$x$};
      \draw[->] (0,-1) -- (0,3.2) node[above] {$y$};
      \draw[scale=1,domain=-1:2.7,smooth,variable=\x,blue] plot ({\x},{0.3*(\x+1)*(\x+1)-cos(\x)});
      \draw[-] (2.6,-0.1) -- (2.6,0.1) {};
      \node at (2.6,-0.3) {$x_0$};
      \node[align=right,blue] at (5,3) {$y=0.3(x+1)^2-\cos(x)$};
      \node[align=right] at (-5,3) {};
      \draw[-] (-1,-0.1) -- (-1,0.1) {};
      \node at (-1,-0.3) {$-1$};
      \draw[-] (-0.1,1) -- (0.1,1) {};
      \node at (-0.3,1) {$1$};
%\begin{axis}[
%     axis lines=middle,clip=false,
%            xmin=-1,xmax=3.2,ymin=-1,ymax=3.2,
%            ytick={1},
%            xtick={1,2.2},
%            xticklabels={$1$,$x_0$},
%            xticklabel style={black},
%            xlabel=$x$,
%            ylabel=$y=...$]
%     % \addplot[domain=-1:2.5,samples=200,orange]{0.3*(x+1)*(x+1)-cos(x)}
%     %                           node[right,pos=0.9,font=\footnotesize]{$f(x)=...$};
%      \addplot[domain=-2:2,samples=200,magenta]{cos(deg(pi*x))}
%                                node[right,pos=1,font=\footnotesize]{$f(x)=\cos \pi x$};
%    \end{axis}
\end{tikzpicture}
\end{center}
\item Sind mit dieser Methode im Allgemeinen weniger Flops nötig als mit der Newton-Iteration? 
\end{enumerate}
%
%\textbf{Theorieaufgabe \arabic{taskNb} (1+1 Punkte):} \stepcounter{taskNb}
%Führen Sie ein eine Iteration des Newton-Verfahrens aus, um das nichtlineare Gleichungssystem
%\[
%\begin{aligned}
%\exp(x^2-y^2)-3=0\\
%x+y-\sin(2(x+y))=0
%\end{aligned}
%\]
%zu lösen. Benutzen Sie die Startwerte $x_0=\pi$ und $ y_0=\pi$. An welchen Stellen ist das Differential singulär?\\[0.3cm]
%
\textbf{Theorieaufgabe \arabic{taskNb} (2+4 Punkte):}\stepcounter{taskNb}
Gegeben sei das nichtlineare Gleichungssystem
\[
x_1 = 0,\ \frac{10 x_1}{x_1+0.1}+2x_2^2=0,
\]
dessen eindeutig bestimmte Lösung $(x_1, x_2) = (0, 0)$ ist.
\begin{enumerate}[label=\alph*)]
\item Führen Sie ausgehend von dem Startvektor $(0,\pi)$ einen Newton-Schritt durch.
\item Konvergiert das Newton-Verfahren in diesem Beispiel für alle genügend nahe an der Lösung liegenden Startvektoren? Geben Sie die maximale Teilmenge aller Punkte in der offenen Kugel um den Ursprung mit Radius 1/10,  d.h. $$U_{1/10}(0)=\{(x_1,x_2)\ |\ \Vert (x_1, x_2)\Vert_2<1/10\}$$ an,  sodass das Verfahren auf dieser Menge konvergiert. Geben Sie auch die (maximale) Ordnung der Konvergenz an.
\end{enumerate}
%
\textbf{Theorieaufgabe \arabic{taskNb} (1+2 Punkte):}\stepcounter{taskNb}
Gegeben sei die Gleichung $F(x)=x+\ln(x)=0.$ 
\begin{enumerate}[label=\alph*)]
 \item Sei $\Phi(x)=-\ln(x)$. Die Fixpunktiteration $x_{k+1}=\Phi(x_{k})$, $K=0,1,2$ liefert für $x_0=\frac{1}{2}$ die Werte $x_1\approx 0.6931$, $x_2\approx 0.3665$, $x_3\approx 1.0037$. Warum konvergiert die Fixpunktiteration nicht?
 \item Machen Sie Vorschläge für eine Funktion $\Phi$, sodass die Fixpunktiteration gegen eine Nullstelle von $F$ konvergiert. 
\end{enumerate}
%
\textbf{Programmieraufgabe (4 Punkte):} 
Schreiben Sie ein MATLAB-Programm für das Newton-Verfahren zur Bestimmung einer Nullstelle einer Funktion $f$ und ein MATLAB-Programm zur Fixpunktiteration angewandt auf $x=f(x)+x$. Verwenden Sie als Beispielprobleme die Funktionen
\begin{enumerate}
 \item $f(x)=e^x-\sin(x)$ 
 \item $f(x)=\sin(x)-e^x, $
 \item $f(x) = \arcsin(e^x)-x,\  x <0$
 \item $f(x)=\ln(\sin(x))-x$
\end{enumerate}
und als Startwerte $x_0=-\pi/4,\ -5\pi/4,\ -9\pi/4$. 
Vergleichen Sie die Ergebnisse bzgl. Rechengenauigkeit, Rechenaufwand und Konvergenz. 
Verwenden Sie hierfür das auf der Homepage bereitgestellte Hauptfile (script.m) und die Masken der zu schreibenden Unterprogramme \texttt{newton.m} und \texttt{fixpunkt.m}. 
Außerdem müssen die vier Funktionen $f(x)$ (rechte Seiten der Gleichung $0=f(x)$) und ihre Ableitungen am Anfang der Datei \texttt{script.m} implementiert werden.

NB: Diese Programmieraufgabe wurde in Matlab konzipiert und danach auch in Python übersetzt. Wegen unterschiedlicher Implementierungen der mathematischen Funktionen in 3. und 4. in beiden Sprachen, könnte es eventuell zu unterschiedlichen Ergebnissen kommen. Bitte eventuelle Probleme bei der Ausführung der Newton- und Fixpunktiterationen für die Funktionen 3. und 4. im Jupyter-Notebook melden. 
\end{document}

