\documentclass[a4paper]{article}

\usepackage{ngerman}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{moreverb}
\usepackage{latexsym}

\title{4. "Ubungsblatt Numerik}
\date{Version vom \today}
\author{B"uch, Lutz (Gruppe 7)\\Rieck, Bastian (Gruppe 1)}

%
%\renewcommand{\familydefault}{\sfdefault}
%

\begin{document}

\maketitle

\section*{Aufgabe 1}

Durch schrittweises Einsetzen der Bedingungen kann man die Koeffizienten
des Polynoms $p(x,y) = a + bx + cy + dxy$ bestimmen:

\begin{align*}
a & = 1\\
b & = 1\\
c & = 3\\
d & = -2\\
\Rightarrow p(x,y) & = 1 + x + 3y - 2xy
\end{align*}

Man rechnet leicht nach, dass dieses Polynom den Voraussetzungen
gen"ugt. Der Gradient von $p(x,y)$ ist:

\begin{displaymath}
\nabla p(x,y) =
\begin{pmatrix}
1-2y\\
3-2x
\end{pmatrix}
\end{displaymath}

\hfill $\Box$

\section*{Aufgabe 2}

Das Polynom $g$ interpoliert $f$ an $x_0,x_1, \dots, x_{n-1}$:

\begin{align*}
g(x_0) & = y_0\\
g(x_1) & = y_1\\
\vdots\\
g(x_{n-1}) & = y_{n-1}
\end{align*} 

Das Polynom $h$ interpoliert $f$ an $x_1, x_2, \dots, x_n$:

\begin{align*}
h(x_1) & = y_1\\
h(x_2) & = y_2\\
\vdots\\
h(x_n) & = y_n
\end{align*}


Betrachten wir zun"achst $q(x)$ an den Stellen $x_0$ und $x_n$:

\begin{align*}
q(x_0) & = g(x_0) + \frac{\overbrace{x_0 - x_0}^{ = 0}}{x_n - x_0}( g(x_0) - h(x_0)\\
       & = g(x_0)\\
       & = y_0\\
q(x_n) & = g( x_n ) + \frac{x_0 - x_n}{x_n-x_0}( g(x_n) - h(x_n) )\\
       & = g( x_n ) - g(x_n) + h(x_n)\\
       & = h(x_n)\\
       & = y_n       
\end{align*}

Es gilt ebenso:

\begin{displaymath}
g(x_i) - h(x_i) = 0 \hphantom{x} \forall i \in \{ 1, \dots, n - 1 \}
\end{displaymath}

Und somit:

\begin{displaymath}
q(x_i) = g(x_i) \hphantom{x} \forall i \in \{ 1, \dots, n - 1 \}
\end{displaymath}


Also interpoliert $q$ die Funktion $f$ an den Stellen $x_0, \dots, x_n$.

\hfill $\Box$

\section*{Aufgabe 3}

F"ur $x_0 = 0, y_0 =, x_1 = 1, y_1 = 4$ ergibt sich mit der
Langrangebasis:

\begin{align*}
l_0(x) & = \frac{ x - x_1 }{ x_0 - x_1 } = 1 - x\\
l_1(x) & = \frac{ x - x_0 }{ x_1 - x_0 } = x\\
\Rightarrow P(x) & = y_0 \cdot l_0(x) + y_1 \cdot l_1( x )\\
		 & = 0 \cdot l_0(x) + 4 \cdot l_1( x )\\
		 & = 4x
\end{align*}

Und mit der Newtonbasis:

\begin{align*}
n_0(x) & = 1\\
n_1(x) & = (x-x_0) = x
\end{align*}

Die Koeffizienten sind dabei:

\begin{align*}
c_0 & = y_0 = 0\\
c_1 & = \frac{ y_1 - y_0 }{x_1 - x_0} = 4
\end{align*}

Und somit:

\begin{displaymath}
N(x) = 4x
\end{displaymath}

F"ugt man den $x_2 = -1, y_2 = 2$ mit dazu, so gibt es eine neue
Lagrangebasis:

\begin{align*}
l_0(x) & = \frac{(x-x_1)(x-x_2)}{(x_0 - x_1)(x_0 - x_2)} = x^2 - 1\\
l_1(x) & = \frac{(x-x_0)(x-x_2)}{(x_1 - x_0)(x_1 - x_2)} = \frac{1}{2}
( x^2 + x )\\
l_2(x) & = \frac{(x-x_0)(x-x_1)}{(x_2 - x_0)(x_2 - x_1)} = \frac{1}{2}(
x^2 - x)\\
\Rightarrow P(x) & = 0 \cdot l_0(x) + 4 \cdot l_1(x) + 2 \cdot l_2( x )\\
		 & = 3x^2 + x
\end{align*}

Zur bereits bekannten Newtonbasis wird noch $(x-x_0)(x-x_1) = x^2 - x$
hinzugef"ugt und der neue Koeffizient $c_2$ berechnet:

\begin{displaymath}
c_2 = \frac{ \frac{y_2 - y_0}{ x_2 - x_0} - \frac{ y_1 - y_0 }{ x_1 -
x_0 } }{x_2 - x_1} = \frac{ -2 - 4 }{ -2 } = 3
\end{displaymath}

Damit ist das neue Newtonpolynom:

\begin{displaymath}
N(x) = \underbrace{4x}_{\textrm{bereits berechnet}} + \hphantom{x} 3 \cdot (x^2 - x) = 3x^2 + x
\end{displaymath}

Offensichtlich ist das Berechnen der Lagrangebasis viel aufw"andiger als
die Berechnung eines neuen Newtonpolynoms mit dem entsprechenden
Koeffizienten. Besonders f"ur die Implementierung im Computer ist die
Bestimmung der Newtonbasis effizienter und weniger fehleranf"allig. Dies
trifft besonders dann zu, wenn viele zus"atzliche St"utzstellen zu
erwarten sind.

\section*{Aufgabe 4}

\subsection*{1.}

Nach dem Satz von Cayley-Hamilton ist jede Matrix eine Nullstelle ihres
charakteristischen Polynoms. Also ist die inverse Matrix jeder
invertierbaren Matrix als Linearkombination der Potenzen der Matrix f"ur
Exponenten kleiner der Zeilenzahl darstellbar.

% http://rootprompt.org/article.php3?article=403
% http://www.sci.usq.edu.au/staff/robertsa/LaTeX/ltxmaths.html

\subsection*{3.}

$A$ ist symmetrisch und positiv definit. Insbesondere ist $A$ somit
diagonalisierbar mit Eigenwerten $\lambda_i > 0$. Da das Diagonalisieren
einen Basiswechsel darstellt und nichts an den Eigenschaften von $A$
"andert, sei im Folgenden davon ausgegangen, dass $A$ diagonalisiert
ist:

\begin{displaymath}
\tilde{A} = 
\begin{pmatrix}
\lambda_1 & 0 & 0 & \dots & 0\\
0 & \lambda_2 & 0 \dots  & 0\\
\ddots\\
0 & 0 & \dots & \lambda_n\\
\end{pmatrix}
\end{displaymath}

Dabei ist $A = T\tilde{A}T^{-1}$, wobei $T$ die Transformationsmatrix
aus Eigenvektoren ist, die $A$ in eine diagonalisierte Matrix
"uberf"uhrt. Die Wurzel von $\tilde{A}$ kann nun durch komponentenweises
Wurzelziehen berechnet werden. Dies ist m"oglich, da $\tilde{A}$ eine
diagonalisierte Matrix ist. Um $A^{\frac{1}{2}}$ zu berechnen, muss die
Basistransformation r"uckg"angig gemacht werden:

\begin{displaymath}
A^{\frac{1}{2}} = T\tilde{A}^{\frac{1}{2}}T^{-1}
\end{displaymath} 

Damit ist die positiv definite Matrix eindeutig bestimmt.

\hfill $\Box$ 

\end{document}