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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{\CurrentWeekNb}{7}
\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}\\ 
{Polynominterpolation}\\
%\\{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}
\hfill {Abgabe: Spätestens am 5.12.19 am Anfang der Vorlesung}\\[0.5cm]
%
%%\def\exerciseList{001, 002, 003}
%\begin{enumerate}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%% Aufgabe 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textbf{Theorieaufgabe \arabic{taskNb} (3 Punkte):} \stepcounter{taskNb} 
Es seien $x_0,\ldots,x_n\in \mathbb{R}$ paarweise verschieden, d.h. $x_i\neq x_j$ für alle $i\neq j$. 
Zeigen Sie, dass dann die Abbildung $\langle \cdot, \cdot \rangle: \Pi_n\times \Pi_n\to \mathbb{R}$ gegeben durch $$\langle P,Q\rangle =\sum\limits_{i=0}^{n} P(x_i)Q(x_i)$$ ein Skalarprodukt auf $\Pi_n$ definiert. Geben Sie eine Orthogonalbasis an.
\\[0.3cm]
%
\textbf{Theorieaufgabe \arabic{taskNb} (4 Punkte):} \stepcounter{taskNb} 
Gegeben seien paarweise verschiedene Stützstellen $x_i$, $i=0,\ldots, n$. 
Zeigen Sie, dass folgende Mengen eine Basis der Polynome vom Grade höchstens $n$ sind. 
Formulieren Sie die Interpolationsaufgabe $p(x_i) =f_i$, $i=0,\ldots,n$ als lineares Gleichungssystem in den Koeffizienten des interpolierenden Polynoms in der jeweiligen Basis und berechnen Sie explizit die Matrix.
\begin{enumerate}
\item Monome $\mathcal{M}=\{x^0,x^1,\ldots,x^n\}$
\item Lagrange-Polynome $\mathcal{L}=\{L_i\ |\ i= 0,\ldots,n\}$ mit 
$L_i(x) =\prod^n\limits_{\substack{j=0,\\j\neq i}} \frac{x-x_j}{x_i-x_j},  i= 0, \ldots, n$,
\item Newton-Polynome $\mathcal{N}=\{N_i\ |\ i=0,\ldots,n\}$, $N_0(x) = 1$,  $N_i(x)=\prod_{j=0}^{i-1}(x-x_j)$,  $i= 1,\ldots ,n$
\end{enumerate}
%
%\textbf{Theorieaufgabe \arabic{taskNb} (? Punkte):} \stepcounter{taskNb} 
%Sei $p(x)$ ein Polynom dritten Grades, das die Funktion $f(x)=\frac{1}{a^2-x}$ in den Stützstellen $\{-4,-3,-2,-1\}$ interpoliert. Bestimmen Sie alle Werte von $a$, so dass $|f(x)-p(x)|\leq 10^{-5}$ f\"ur alle $x\in[-4,-1]$.\\[0.3cm]
\textbf{Theorieaufgabe \arabic{taskNb} (5 Punkte):} \stepcounter{taskNb} 
Berechnen Sie das Interpolationspolynom zu den Stützstellen
\begin{center}
\begin{tabular}{c|c|c|c}
$x_i$&-3&-1&2\\
\hline
$f_i$& 10& -6& 15
\end{tabular}
\end{center}
einmal mithilfe der Lagrange-Basisfunktionen und einmal mithilfe der Newton-Basisfunktionen.\\[0.3cm]
%
\textbf{Programmieraufgabe (7 Punkte):}
Bestimmen Sie mit dem Horner-(Newton-)Schema die Interpolationspolynome $P$ zu den Funktionen $f_1(x) =\frac{1}{1+25x^2}$ und $f_2(x) = \sqrt{|x|}$. Verwenden Sie hierzu als Stützstellen jeweils
\begin{enumerate}[label=\alph*)]
\item $x_i=-1+ih$, $i=0, \ldots,n$, $h=2/n$, 
\item $x_i=\cos\left(\frac{(2i+1)\pi}{2(n+1)}\right)$, $i=0, \ldots,n$
\end{enumerate}
für $n=2,4,6,\ldots, 20$.
%Dabei ist zu achten, dass die Implementierung des Schemas der Dividierten Differenzen nicht mehr als ... flops brauchen soll.
Werten Sie das Polynom an den Stellen $y_{i,j}=x_i+j\frac{x_{i+1}-x_i}{21}$, $j=1,\ldots, 20$, $i=0,\ldots, n-1$ aus. Vergleichen Sie als Schätzung für den maximalen Fehler $||p-f_m||_{\infty, [-1,1]}$, $m=1,2$
\[
\max_{\substack{i\in\{0,\ldots,n-1\},\\ j\in\{1,\ldots,20\}}}|P(y_{i,j})-f_m(y_{i,j})|.
\]
Plotten Sie die Interpolationspolynome zu den  Stützstellen in a), b) für $n=20$.  Interpretieren  Sie die Ergebnisse.

\end{document}


