\documentclass[a4paper,11pt]{article}
\usepackage{german, amssymb}
\usepackage[latin1]{inputenc}
\usepackage{pictex} %Zur Einbindung von Grafiken
\usepackage{graphicx} %Zur Einbindung von Grafiken
\usepackage{a4wide} %für bessere Ausnutzung des Blatts
\usepackage{fancyhdr} %für Kopfzeilen

\usepackage{pxfonts}

% Abkürzungen für oft benutzte mathematische Funktionen
\newcommand\diverg{{\rm div\>}}			% Divergenz, div ist schon vergeben
\newcommand\rot{{\rm rot\>}}			  % Rotation
\newcommand\grad{{\rm grad\>}}			% Gradient
\newcommand\reell{{ \mathbb{R} }}		% Menge der Reellen Zahlen

%opening
\title{Zusammenfassung \\ \textbf{Numerische Mathematik für Elektrotechniker} \\ \begin{small}RWTH Aachen, SS 2006, Prof. Dr. W. Dahmen \end{small}}
\author{\copyright 2006 by Sebastian Strache, Ralf Wilke\\
\begin{small}Korrekturen bitte an Ralf.Wilke@rwth-aachen.de\end{small}}
\pagestyle{fancy}


\begin{document}

\maketitle 
\tableofcontents

\section{Vorwort}

Das folgende Dokument ist das Ergebnis unserer Zusammenfasssung der Algorithmen und Ideen für NuMa. Es darf
ausschließlich kostenlos weitergegeben werden. Es wird keine Garantie für die Richtigkeit gewährt;
Verwendung auf eigene Gefahr. \\

\section{Kondition und Stabilität}

	\subsection{Elementare Fehlerfortpflanzung}
		Sei $x \mapsto f(x)$ gegeben.\\
	 	Zwischen dem rel. Fehler der Eingabegröße $r_x = \left|\frac{\tilde{x}-x}{x}\right|$ und dem rel. Fehler der Ausgabe
		 $r_f = \left|\frac{f(\tilde{x})-f(x)}{f(x)}\right|$ gibt es den Zusammenhang:
		$$ \left|\frac{f(\tilde{x})-f(x)}{f(x)}\right| = 
		\underbrace{\left|\frac{f'(\zeta) \cdot x}{f(x)}\right|}_{Verstaerkungsfaktor \ \ \ \kappa_{rel}: \ Kondition} \cdot \left|\frac{\tilde{x}-x}{x}\right|$$
		In erster Näherung ist damit $$\kappa_{rel}(x) = \left|\frac{x \cdot f'(x)}{f(x)}\right|$$
		
	\subsection{Anwendung}
		Sei $f(x)$, ein $x_0$ und ein relativer Fehler $\alpha$ von $x_0$ gegeben.\\
		\textbf{Aufgabe: } Schätzen Sie den rel. Fehler von $f(x_0)$ ab. \\
		\textbf{Lösung: } $\kappa_{rel}(x_0)$ wie oben berechnen. Der rel. Fehler von $f(x_0)$ ist $r_f = \kappa_{rel}(x_0) * \alpha$
		

\section{Lineare Gleichungssysteme}

	\subsection{LR-Zerlegung}
    
    \subsubsection{ohne Pivotisierung}
		Wie Gauß. Erzeugung durch Abzug der Spalten voneinander. In $L$ stehen die Faktoren, mit denen die Spalten
		multipliziert wurden. In $R$ stehen die restlichen Einträge, die Ergebnis vom Gauß-Algorithmus sind.
		\begin{enumerate}
			\item $ A = L \cdot R $
			\item $ L \cdot y = b $ Vorwärtseinsetzen
			\item $ R \cdot x = y $ Rückwärtseinsetzen
		\end{enumerate}
	
		\subsubsection{mit Pivotisierung}
		\textbf{Vorteil: } Verbesserung der Stabilität\\
		\textbf{Aufwand: } $\frac{1}{3} n^{3}$\\
		
		\textbf{Idee: } Durch Vertauschen von Zeilen wird A so geändert, dass der für das Gauß-Verfahren aktuelle Eintrag der in der Spalte betragsgrößte ist. Dadurch wird die Kondition des Algorithmus verbessert.
		
		\begin{enumerate}
			\item $$P \cdot A = L \cdot R$$
			$P$ ist Permutationsmatrix. Sie entsteht aus der Identität $I$ durch Vertauschen der
			in $A$ getauschten Zeilen. Dabei schreibt man am einfachsten die Identität zu Anfang des Verfahrens auf und vollzieht an ihr alle Permutations mit.
			
			\item $$\det P = (-1)^{Anzahl \ der \ Vertauschungen}$$
			\item $L \cdot y = P \cdot b$
			\item $R \cdot x = y$
		\end{enumerate}
		$$\det A = \det P^{-1} \cdot \det R$$
		
		\subsubsection{mit Äquilibirierung}
		\textbf{Idee: } Erstellen einer Diagonal-Matrix $D$, welche $\frac{1}{Zeilennorm}$ enthält. Dadurch werden die Zeilen im Verhältnis zu ihren Einträgen skaliert, was die Kondition des Algorithmus verbessert. Äquilibierung wird meist als Ergänzung zur Pivotisierung verwendet.
		
		\begin{enumerate}
			\item Zeilennormen $\left\| . \right\|_{\infty}$ bestimmen = Addieren der Zeileneinträge
			\item D = Diagonalmatrix mit $\frac{1}{Zeilennorm}$ auf der Diagonale
			\item $D \cdot A = D \cdot b$ berechnen
			\item mit oder ohne Pivotisierung weiterbehandeln \\
			Dabei beachten: $$L \cdot y = P \cdot \underbrace{D \cdot \ b}_{schon \ berechnet}$$
			$$ R \cdot x = y$$ 
		\end{enumerate}
	
		\subsection {Cholesky Verfahren}
		\textbf{Aufwand:} $\frac{1}{6} n^{3}$
		
		Zerlegung $$A = LDL^T$$
		Einträge von $L$ und $D$ berechnen sich mit folgenden Formeln
		$$d_{k,k} = a_{k,k} - \sum \limits_{j=1}^{k-1} l_{k,j}^2 \cdot d_{j,j}$$
		$$l_{i,k} = \frac{1}{d_{k,k}} \cdot (a_{i,k}- \sum \limits_{j=1}^{k-1} l_{i,j} \cdot d_{j,j} \cdot l_{k,j})\\ \ mit\ \ i > k$$
		\begin{enumerate}
			\item Berechnung 1. Spalte $i = 1$ : $d_{1,1}, l_{2,1}, l_{3,1}, l_{4,1}$
			\item Berechnung 2. Spalte $i = 2$ : $d_{2,2}, l_{3,2}, l_{4,2}$
			\item Berechnung 3. Spalte $i = 3$ : $d_{3,3}, l_{4,3}$
			\item Berechnung 3. Spalte $i = 3$ : $d_{4,4}$
			\item $L \cdot y = b$
			\item $D \cdot z = y$
			\item $L^{T} \cdot x = z$			
		\end{enumerate}
		
		\subsection{Givens-Rotation}
		Auch QR-Zerlegung genannt\\
		\textbf{Aufwand: } $\frac{4}{3} n^{3} $ \\
		\textbf{Idee: } Erzeugung von Nullen in der Matrix durch Drehung eines 2x2-Vektors derart, dass eine Koordinate auf eine
		Koordinaten-Achse fällt und damit 0 ist.\\
		\textbf{Vorteil:} Q ändert die Kondition nicht. Das bedeutet, wir können Nullen erzeugen, ohne die Konditionszahl zu verändern.
		
		\begin{math}
		\left(
		\begin{array}{cc}
			c & s \\
			-s & c \\
		\end{array}
		\right)
		\end{math}
		Dies ist die Drehmatrix. \\
		Aus geometrischen Überlegungen zeigt sich: $c = \frac{x}{r}$ , $s = \frac{y}{r}$ und $r = \sqrt{x^2+y^2}$. \\
		y ist der Wert, der durch die Drehung zu 0 werden soll. \\
		Ist das Problem größer als die 2x2 Matrix, so ist diese in eine Einheitsmatrix so einzubetten. Dabei ist die cs-Matrix
		so einzubringen, dass sie dass für diesen Schritt gewählte y zu 0 dreht.\\
		Ziel der Verfahrens ist es, eine obere Dreiecksform zu erzielen. \\ \\
		\textbf{Tipp:} Sei $Z_{1,neu}$ die erste neue Zeile nach der Multiplikation mit der cs-Matrix und $Z_{2,neu}$ die zweite.\\
		Es gilt: $$Z_{1,neu} = c \cdot Z_1 + s \cdot Z_2$$
		$$Z_{2,neu} = -s \cdot Z_1 + c \cdot Z_2$$		
		

		\textbf{Ergänzende Worte}\\
		Gegeben: $A \in \reell^{n \times k}$, $x \in \reell^k$, $b \in R^n$ \\
		Ziel: Finde ein $x \in \reell^k$, so dass $\left\|Ax - b \right\|_2 =$ minimal.	\\ \\
		
		\textit{Geometrische Interpretation:}\\
		$ U := \{y = Ax \in \reell^n | x \in \reell^k\}$ ist ein Unterraum im $\reell^n$ (der Dimension Rang(A)),\\
		zum Beispiel: $A \in \reell^{3 \times 2}$ und ${y = Ax}$ ist Ebene im $\reell^3$. \\ \\
		Dann ist $$\min\{\left\|Ax - b\right\|_2 \ | \ x \in \reell^k\} = \min\{\left\|y-b\right\|_2 \ | \ y \in U \} $$
		der Abstand vom Punkt b zu diesem Untervektorraum. \\
		Mit anderen Worten: Wir suchen den Lotfußpunkt $Ax_0$ von b auf U. Dann ist $\left\|Ax_0 - b \right\|_2$ das gesuchte Minimum. \\ \\
		Die Givens-Roation ist eine Drehung des $\reell^n$, die bewirkt, dass der gedrehte Unterraum 
		$GU = \{(GA)x \ | \ x \in \reell^k\}$ nicht "`irgendwie schief"' im $\reell^n$ rumhängt, sondern von den ersten Einheitsvektoren (1,0, \ldots, 0), (0,1,0, \ldots, 0) etc. aufgespannt wird. \\
		Im Beispiel ist $GU$ die x-y-Ebene im $\reell^3$. Das ist insofern praktisch, weil
		\begin{enumerate}
		\item $$\left\|Ax-b\right\|_2 = \left\|G(Ax-b)\right\|_2 = \left\|(GA)x - Gb\right\|_2$$
		\item Der Lotfußpunkt von $Gb$ dirket auf einen von den ersten Einheitsvektoren aufgespannten Untervektorraum direkt abgelesen werden kann.
		\end{enumerate}
		
		Ist nämlich wie im Beispiel $GU = \{(a,b,0) \ \| \ a,b \in \reell\}$ und $Gb = (c,d,e)$, so ist der Lotfußpunkt von $Gb$ auf $GU$ der Punkt $(c,d,0)$, und der Abstand von $Gb$ zu $GB$ ist $\left\|Gb-(c,d,0)\right\|_2 = \|e\|$.
		Allerdings will man ja nicht nur den Abstand herausbekommen, sondern auch das $x$, welches $\left\|Ax-b\right\|_2$ minimiert.\\
		Dazu nun eine analytische Interpretation: \\
		$$\left\|(GA)x - Gb\right\|_2 = \sqrt{\sum_{k=1}^n (k-te \ Komponente)^2}$$
		liefert, dass man den Parameter $x$ so wählen muss, um alle Komponenten, auf die $x$ wirkt, zu 0 zu machen. Dann wird die Norm minimal, und es ist das $x$ gefunden, welches $\left\|Ax-b\right\|_2$ minimiert. \\ \\
		
	 	
		\textbf{Wissenswertes zu orthogonalen Matrizen} \\
		\begin{itemize}
		\item $Q^TQ = QQ^T = I = E$
		\item Eigenschaften: $\det(Q) = +- 1$
		\item $\left\|Qx\right\|_2 = \left\|x\right\|_2 \forall x \in \reell \Rightarrow \left\|Q\right\|_2 = 1$
		\item $\left\|QA\right\|_2 = \left\|A\right\|_2 \forall x \in \reell$
		\item Das Produkt orthogonaler Matrizen ist eine orthogonale Matrix.
		\end{itemize}
	
		
		
		\subsection{Verstärkungsfaktoren:}
		$$\Phi_j(x) = \frac{\partial f(x)}{\partial x_j} \cdot \frac{x_j}{f(x)}$$
		$$\underbrace{\frac{f(\tilde{x})-f(x)}{f(x)}}_{rel.\ Fehler\ der\ Ausgabe} =
		\underbrace{\sum \limits_{j=1}^n \Phi_j(x)}_{Fehlerverstaerkung}
		\underbrace{\frac{\bar{x_y}-x_j}{x_j}}_{rel.\ Fehler\ der\ Eingabe}$$

		$$\kappa_{rel}(x) = \max_j \left| \Phi_j(x) \right|$$
		
		

		\subsection{Normen}
		\begin{itemize}
		\item Betragsnorm: $\left\|v\right\|_1 = \sum \limits_{i=1}^n \left|v_i\right|$
		\item Maximumsnorm: $$\left\|v\right\|_\infty = \max_{j = 1,\ldots,n} \left| v_j\right|$$
		\item Zeilensummennorm: $$\left\|A\right\|_\infty = \max_{i=1,\ldots,n} \sum \limits_{j=1}^n \left| a_{i,j}\right|$$
		\item Spaltensummennorm: $$\left\|A\right\|_1 = \max_{j=1,\ldots,n} \sum \limits_{i=1}^n \left| a_{i,j}\right|$$
		\item $\left\|A\right\|_2 = \sqrt{\lambda_{max} (A^T A)}$
		\item $$\frac{\left\|Ax\right\|}{\left|x\right\|} \leq \kappa(A) \cdot \frac{\left\|\Delta b\right\|}{\left\|b\right\|}$$
		\item $\kappa(A) = \left\|A\right\| \cdot \left\|A^{-1}\right\|$ \\
		$\kappa(A) \cdot \frac{\left\|\Delta A\right\|}{\left\|A\right\|} < 1$
		\item $(A + \Delta A)\cdot (x+\Delta x) = b + \Delta b$ \\
		$\Rightarrow \frac{\left\|\Delta x\right\|}{\left|x\right\|} \leq 
		\frac{K(A)}{1-\kappa(A) \cdot \frac{\left\|\Delta A\right\|}{\left\|A\right\|}} \cdot
		\left(\frac{\left\|\Delta A\right\|}{\left\|A\right\|} +
		\frac{\left\|\Delta b\right\|}{\left\|b\right\|}\right)$
		\item $r(x) = b - A\tilde{x}$ Residuum
		\item $e(x) = x - \tilde{x}$ abs. Fehler
		\item Wenn $A$ symmetrische, positiv definite Matrix ist, so ist
		$$\kappa_2(A) = \sqrt{\kappa_2(A^TA)} = \sqrt{\frac{\lambda_{max}(A^TA)}{\lambda_{min}(A^TA)}}$$
		\end{itemize}

	\section{Lineare Ausgleichrechnung}
		
		\subsection{Normalengleichung}
		\textbf{Idee: } Gegeben sei eine Wertetabelle, sowie eine vermutete Abbildungsvorschrift (Funktion) mit 2 Parametern $\alpha$ und $\beta$. Ziel ist es, die Parameter so zu bestimmen, dass die Funtionen die Einträge der Wertetabelle möglichst gut nachbildet (und natürlich auch "`gute"' Zwischenstellen liefert).
		$z$ sei Vektor der Unbekannten in der zu bestimmenden Funktion, nicht der Vektor der Messdaten.\\
		$$\left\|Az-b\right\|_2 \rightarrow min$$
		
		\begin{itemize}
		\item Einsetzen der Wertetabelle in die Funktion $\Rightarrow$ System von $n \geq 2$ Gleichungen in $\alpha$ und $\beta$. Hieraus erstellt man durch Aufschreiben in Matrix-Form $Az = b$
		
		\item $Az = b	\Rightarrow A^TAz = A^Tb$
		\item $A^TA$ und $A^Tb$ berechnen und dann lösen
		Die Multiplikation mit $A^T$ sorgt dafür, dass genau so viele Zeilen "`verschwinden"', dass $A^TA$ eine
		$2 \times 2$-Matrix ist. Somit ist aus dem (vielfach) überbestimmten Gleichungssystem eines geworden, welches für 
		$z = \left(\begin{array}{c}\alpha \\ \beta \end{array} \right)$ eine eindeutige Lösung liefert.
	
		\item Mit Cholesky lösen $\Rightarrow \kappa = \kappa(A)^2$ (nicht unbedingt zu empfehlen)
		\item Mit Givens (QR) lösen $\Rightarrow \kappa = \kappa(A)$.\\
		Residuum ist $\left\|b_2\right\|_2$ mit $b_2$ als Teil von $b$, welcher dem "`Nullteil"' von $QR$ gegenübersteht.
		\end{itemize}
		
		Kondition eines linearen Ausgleichsproblems bzgl. eines Störung in b ergibt: \\
		$$\frac{\left\|\tilde{x}-x^*\right\|_2}{\left\|x\right\|_2} \leq
		\frac{\kappa_2(A)}{\cos \Theta} \cdot \frac{\left\|\tilde{b}-b\right\|_2}{\left\|b\right\|_2}$$
		$$\kappa_2(A) = \sqrt{\kappa_2(A^TA)}$$
		$$\kappa(A^TA) = \frac{\lambda_{max}(A^TA)}{\lambda_{min}(A^TA)}$$
		$$\cos \Theta = \frac{\left\|Ax^*\right\|}{\left\|b\right\|_2}$$
		
	
		
		\subsection{Merkmale für "`positiv definit"'}
		\begin{itemize}
		\item alle Eigenwerte $>$ 0
		\item Choleski-Zerlegung $A=LDL^T$ exisitiert mit allen Einträgen aus D $>$ 0
		\end{itemize}
		
	\section{Nichtlin. Gleichungssysteme, iterative. Lösungsverfahren}
	
		\subsection{Banach'scher Fixpunktsatz}
		Ordnung p = 1 \\
		Umformen nach $ x = \ldots = \Phi(x)$. D sei Gebiet.\\
		Bedingungen, damit Fixpunktproblem $(x_*,x_*) = \Phi(x_*,y_*)$ eine eindeutige Lösung in D besitzt sind:
		\begin{enumerate}
		\item D geschlossen und konvex, oder $\subset \reell^n$
		\item $\Phi$ ist Selbstabbildung auf D $\Phi(D) \subset D$ \\
		Dabei ist zur Ermittlung der Schranken des Wertebereichs nur \textbf{eine} Schranke zu finden, so dass $\Phi$ noch Selbstabbildung ist. Es ist also nicht unbedingt die \textbf{kleinste} Schranke zu finden. Damit kann bei der Bestimmung des Wertebereichs der \textit{worst case} eines jeden Terms angenommen werden, auch wenn hierzu $x$ gleichzeitig verschiedene Werte annehmen müsste.
		
		
		\item $\Phi$ ist Kontraktion auf D: \ \ \ \  $|\Phi'(x)| \leq L < 1$, \ \ \ im Mehrdim.: \ 
		$\left\| \underbrace{\Phi'(x)}_{Jacobi-Matrix} \right\| \leq L < 1$, $x \in D$\\
Die Abschätzung kann man einfach dadurch ausführen, dass man wie oben den \textit{worst case} für alle enthaltenen Terme annimmt. Dabei kann $x$ auch hier gleichzeitig verschiedene Werte annehmen. Man findet dadurch \textbf{eine} Schranke. Ist diese kleiner 1, so hat man damit die Kriterien zur Anwendung des Banach'schen Fixpunktsatzes erfüllt. Falls nicht, so muss man eine weitere Schranke suchen. Viel Spaß...
		
		\end{enumerate}
		\textbf{Verfahren:} $$ x_{k+1} = \Phi(x_k)$$ mit Startwert $x_k \in D$ beliebig.
		
		\subsubsection{Fehlerabschätzung}
		Es sei ein Fixpunkt-Problem $\Phi(x) = x$ eines Gleichungssystems gegeben. Außerdem sei ein Startwert $x^0$ und eine Genauigkeit $\epsilon$ vorgegeben. \\
		\textbf{Frage: } Wieviele Iterationen $k$ sind nötig, um die Genauigkeit $\epsilon$ zu erreichen? \\
		\begin{itemize}
		\item Berechne $x_1 = \Phi(x_0)$
		\item Mit der \textbf{a-priori}-Fehlerabschätzung
		$$ \left\|x_k-x^*\right\|_\infty \leq \frac{L^k}{1-L} \cdot \left\|x_1-x_0\right\|_\infty $$
		ergibt sich hier mit $L$ als Lipschitzkonstante von $\Phi$
		$$k >= \ln \left( \frac{\left\|x^1-x^0\right\|_\infty}{\epsilon (1-L)}\right) \cdot \frac{1}{\ln \left(\frac{1}{L}\right)}$$
Man kann also nach nur \textit{einem} Iterations-Schritt schon abschätzen, wie viele Durchläufe man für eine vorgegeben Genauigkeit durchführen muss.

		\item Die \textbf{a-posteriori}-Fehlerabschätzung lautet bei der Bildung von $\Phi(x_k)$
		$$ \left\|x_k -x^*\right\|_\infty \leq \frac{L}{L-1} \left\|x_k -x_{k-1}\right\|$$
		
		
		
		\end{itemize}
		
		
		
		\subsection{Newton}
		\textbf{Idee: } Gesucht ist Nullstelle von $f$. Durch iterative Addition/Subtraktion von $\frac{f}{f'}$ zum Startwert $x_0$ hofft man, näher an die Nullstelle zu kommen.
		\textbf{Voraussetzungen: } Genau wie beim Banach'schen Fixpunktsatz
		
		\textbf{Verfahren für skalare Funktion:} \\
		
		$$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$
		Wenn die gesuchte Nullstelle eine Nullstelle zweiter Ordnung ist, so kann lokal quadratische Konvergenz
		erreicht werden, indem das Verfahren modifiziert wird zu:
		$$x_{k+1} = x_k - 2 \cdot \frac{f(x_k)}{f'(x_k)}$$
		
		
		
		\textbf{Verfahren für Systeme (normal)}
		\begin{enumerate}
		\item Berechne $f(x^k), f'(x^k)$ (Jacobi-Matrix)
		\item Löse $\underbrace{f'(x_0,y_0)}_{Jacobi-Matrix} \cdot \Delta \vec x_0 = f(x_0,y_0)$
		\item $\vec x_1 = \Delta \vec x_0 + \vec x_0$
		\end{enumerate}
		
		
		\textbf{für Systeme (vereinfacht)} \\
		Die Vereinfachung besteht darin, dass die Jacobi-Matrix nur für den Startwert $x_0$ einmal
		berechnet und in der folgenden Iteration fortwährend verwendet wird. \\
		
		
		
		
		
		\subsubsection{A-posteriori Fehlerabschätzung}
		%   XXXXXXXXXXX  ??  XXXXXXXXXXXXXx
		%\textbf{p=1} \\ 
		%$ x^* - x_k \approx \frac{A_k}{1-A_k} \cdot (x_k-x_{k-1)}$ mit $A_k = \frac{x_k - x_{k-1}}{x_{k-1}-x_{k-2}}$ \\
		
		\textbf{Quadratische Konvergenz} \\
		$ x^* - x_k \approx x_{k+1} - x_k$\\
		d.h. der Abstand des letzten Wertes $x_k$ von der wahren Nullstelle ist ungefähr gleich dem Abstand des letzten Wertes $k_k$ zum aktuellen $k_{k1+}$
		
		
		\subsection{Gauß-Newton}
		\textbf{nichtlineares Problem iterativ über lineare Probleme lösen}
		
		\begin{enumerate}
		\item $F(x_k), \ F'(x_k)$
		\item Lösen des linearen Ausgleichsproblems $\left\|F'(x_k) \cdot \Delta s_k - F(x_k)\right\|_2 \rightarrow$ min
		\item $x_{k+1} = x_k + \Delta s_k$
		\end{enumerate}
		
	
	\section{Polynomiteration}
	
		\subsection{Lagrange'sche Grundpolynome}
		$$l_i = \prod \limits_{i=0}^k \frac{x - x_k}{x_i-x_k} \ \ \  k = 1, \ldots, n  \ \ \ \ l_i(x_k) = \delta_{i,k} \ \ \ i \neq k$$
		$$p_{n-1} (x) = \sum \limits_{k=1}^n f(x_k) \cdot l_k(x)$$
		
		\textbf{Zur Ermittlung es Polynoms bei gegebener Wertetabelle siehe Übung 7} \\
		
		
		\subsection{Newton-Form}
		$$\omega_k(x) = \prod \limits_{i=1}^k(x-x_i) \ \ \ k = 1, \ldots, n \ \ \ \omega_o = 1$$
		
		\textbf{dividierte Differenzen} \\
		$$f[x_0, \ldots, x_n] = \frac{f[x_1, \ldots, x_n] - f[x_0, \ldots, x_{n-1}]}{x_n - x_0}$$
		$$f[x_i] = F(x_i) = f_i$$
		$$ P_{n-1}(x) = \sum \limits_{k=0}^{n-1} c_k \omega_k(x) \ \ \  mit \ \ \ c_k = f[x_1, \ldots, k_{k+1}]$$
		
		\subsection{Fehlerabschätzung auf $[a,b]$}

		\textbf{A-Priori:} \\
		$$ \left|f(x) - P(f|x_0, x_1 \ldots, x_n)(x)\right| \leq \max_{x \in [a,b]} \left|\frac{f^{(n+1)}(x)}{(n+1)!}\right| \cdot 
		\max _{x \in [a,b]} \left| \omega_{n+1}(x) \right|$$

		\textbf{A-Priori:} \\
		$$ k \geq \ln \left( \frac{\epsilon(1-L)}{\left\|x_1-x_0\right\|} \right) \cdot \frac{1}{\ln (L)}$$
		
		\subsection{Neville-Aitken-Schema}
		\textbf{Idee: } Es sei eine Werte-Tabelle gegeben. Aufgabe ist es, an einer weiteren Stelle den Wert zu ermitteln.\\
		Die Umsetzung des Schemas in LaTeX ist mir zu komplziert. Vielleicht nach der Klausur.
		

		$$P_{i,k} = \frac{x-x_{i-k}}{x_i-x{i-k}} \cdot P_{i,k-1} + \frac{x_i - x}{x_i - x_{i-k}} \cdot P_{i-1, k-1}$$
		$$ = P_{i,k-1} + \frac{u_i-u}{u_i-u_{i-k}} \cdot (P_{i-1,k-1}-P_{i,k-1})$$
		für $0 \leq k \leq i \leq n$.\\
		u = x $P_{i,0} = f(\omega_i)=f(x_i)$

\textbf{Todo: horner schema}

	\section{Bewertung}
		\subsection{Newton}

		\begin{itemize}
		\item bei Änderung einer Stützstelle muss nur eine Reihe geändert werden. (Nicht wie bei Lagrange,
		wo alles neu berechnet werden muss.
		\item Stützstellen müssen nicht sortiert sein.
		\end{itemize}
		
		
		\subsection{Neville-Aitken-Schema}
		Gut, wenn nur 1 Stelle gesucht wird
		
		\subsection{Horner-Schema}
		Gut, wenn viele Stellen gesucht werden (geringere Rechenaufwand)

	
\end{document}