%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[10pt,twoside,twocolumn,german]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=2cm,bmargin=2cm,lmargin=2cm,rmargin=2cm,headheight=5mm,headsep=5mm,footskip=5mm}
\pagestyle{headings}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{varioref}
\usepackage{amsmath}
\usepackage{makeidx}
\makeindex
\usepackage{graphicx}
\usepackage{amssymb}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{gastex}
%\renewcommand{\thesubsubsection}{\alph{subsubsection})}
\usepackage[linktocpage,pdfpagelabels,colorlinks,hyperindex]{hyperref}
%\usepackage[dvips,ps2pdf,pdfpagelabels]{hyperref}
\usepackage[T1]{fontenc}
\usepackage{ae,aecompl}

\usepackage{babel}
\makeatother
\begin{document}

\title{Formelsammlung\\
Grundlagen der Modellierung und Simulation}


\author{<Marco.Moeller@macrolab.de>}


\date{Stand: 16.10.2005 - Version: 1.0.0\\
\noun{Erhältlich unter \url{http://privat.macrolab.de}}}

\maketitle
Diese Formelsammlung basiert auf der Vorlesung {}``Einführung in
Computational Engineering (für Inf.) / Grundlagen der Modellierung
und Simulation (für CE)'' von Prof. Dr. Oskar von Stryk an der Technischen
Universität Darmstadt im Sommersemester 2005.

Die folgende Formelsammlung steht zum kostenlosen Download zur Verfügung.
Das Urheberrecht und sonstige Rechte an dem Text verbleiben beim Verfasser,
der keine Gewähr für die Richtigkeit und Vollständigkeit der Inhalte
übernehmen kann.

\tableofcontents{}


\section{Einführung}


\subsection{Begriffsbildung}

\begin{description}
\item [Abstraktes~Modell]formale Beschreibung, typischerweise (aber nicht
nur) mit den Mitteln der Mathematik
\item [Mathematische~Modellierung]Prozess der formalen Herleitung und
Analyse eines mathematischen Modells
\item [Simulation]Nachahmung von Eigenschaften eines technischen Systems
oder naturwissenschaftlichen Phänomens auf einem Computer
\end{description}

\subsection{\label{sub:Systemstruktur-eines-Modells}Systemstruktur eines Modells}

In Abbildung \vref{cap:Schaubild-eines-Systems} sieht man exemplarisch
ein System. Es hat folgende Komponenten:%
\begin{figure}[h]

\caption{\label{cap:Schaubild-eines-Systems}Schaubild eines Systems}

\hfill{}\begin{picture}(73,60)(0,-60) \put(14,-57){\framebox(49,46){}}

\drawline[AHnb=1](38.5,-4)(38.5,-10)

\node[Nframe=n,NLangle=0.0](n4)(38.5,-1.0){$\vec{p}$}

\node[NLangle=0.0,Nmr=0.0](n0)(20.0,-20.0){$K_1$}

\node[NLangle=0.0,Nmr=0.0](n1)(45.0,-18.0){$K_2$}

\node[NLangle=0.0,Nmr=0.0](n2)(25.0,-38.0){$K_4$}

\node[NLangle=0.0,Nmr=0.0](n3)(55.0,-43.0){$K_3$}

\node[Nframe=n,Nlangle=0.0](n5)(5.0,-20.0){$\vec{u}$}

\node[Nframe=n,Nlangle=0.0](n6)(5.0,-38.0){$\vec{z}$}

\node[Nframe=n,Nlangle=0.0](n7)(70.0,-43.0){$\vec{y}$}

\drawedge[curvedepth=-2.82](n0,n2){}

\drawedge[curvedepth=-3.37](n2,n0){}

\drawedge(n0,n1){}

\drawedge(n5,n0){}

\drawedge(n6,n2){}

\drawedge(n3,n7){}

\drawedge[curvedepth=-2.82](n1,n3){}

\drawedge[curvedepth=-3.35](n3,n1){}

\drawedge(n2,n3){}

\drawloop[loopdiam=8.34,loopangle=-67.75](n3){}

\end{picture}\hfill{}
\end{figure}


\begin{description}
\item [Systemzustand]$\vec{x}$
\end{description}
\begin{itemize}
\item vollständige Charakterisierung des Systemverhaltens
\end{itemize}
\begin{description}
\item [Stellgrößen]$\vec{u}$ 
\end{description}
\begin{itemize}
\item Systemeingang - steuerbar
\end{itemize}
\begin{description}
\item [Störgrößen]$\vec{z}$ 
\end{description}
\begin{itemize}
\item Systemeingang - nicht kontrollierbar
\end{itemize}
\begin{description}
\item [Systemparameter]$\vec{p}$
\end{description}
\begin{itemize}
\item konstant für einen Simulationslauf
\item Wahl dieser Parameter anhand:

\begin{itemize}
\item Bestimmung der Zeitkonstanten im Vergleich zur Analytischer Lösung
/ Realer Daten
\item Minimierung der Quadrate der Abweichung zur Analytischer Lösung /
Realer Daten
\end{itemize}
\end{itemize}
\begin{description}
\item [Systemausgang]$\vec{y}$
\end{description}
\begin{itemize}
\item mess- / beobachtbare Größen
\end{itemize}

\subsection{Klassifikation von Modellen}


\subsubsection{Allgemein}

\begin{description}
\item [diskret]ein solches Modell nutzt diskrete / kombinatorische Beschreibung
\item [kontinuierlich]ein solches Modell nutzt kontinuierliche / reellwertige
Beschreibung
\item [deterministisch]die Berechnungen im Modell enthalten keine Zufallsgrößen
\item [stochastisch]es sind Zufallsentscheidungen / größen im Modell involviert
\end{description}

\subsubsection{Zeitachse}

\begin{description}
\item [Kontinuierlich]Achse hat keine Unterbrechungen
\item [diskret~äquidistant]Achse ist in gleich große Stücke zerlegt
\item [diskret~nicht~äquidistant]Achse ist unterbrochen, aber in unterschiedlichen
Schrittweiten
\item [kontinuierlichdiskret]es gibt Ausgezeichnete Punkte auf der Achse,
aber der Zwischenraum ist vorhanden
\item [zeitdiskret]Die Zeitachse ist Unterteilt
\item [ereignisdiskret]Die Ereignisse lassen sich voneinander Trennen,
diese ersetzen die Zeiachse sozusagen
\end{description}

\subsubsection{Zustandsraum}

\begin{description}
\item [diskrete~Werteskala]Zusandsmenge ist endlich, bzw. man kann nicht
zwischen je zwei Zuständen noch einen Zwischenzustand finden
\item [kontinuierliche~Werteskala]Zustandsmenge ist Reellwertig
\item [räumlich~verteilte~Variablen]Zustandsmenge ist isomorph zu $\mathbb{R}^{n}$
\end{description}

\subsubsection{Art der Dynamik}

\begin{description}
\item [instationär]Objekt ist in Bewegung
\item [stationär~/~quasi-stationär]Objekt ist Ortsgebunden
\item [Beschreibungsunschärfe]~

\begin{description}
\item [deterministisch]Nächste Bewegung ist Vorhersagbar
\item [stochastisch]Nächster Zustand ist zufällig
\item [fuzzy]Kontinuierliche Logik
\end{description}
\end{description}

\subsection{Aufgabenstellungen}

\begin{description}
\item [Direktes~Problem]Eingänge und Systemmodell ist bekannt, Ausgang
ist Unbekannt
\item [Inverse~Probleme]Alles bekannt bis auf eines der folgenen: Systemmodell,
Eingänge, Systemparameter
\end{description}

\subsection{Teilschritte einer Simulationsstudie}


\subsubsection{Problemspezifikation}

\begin{itemize}
\item Ausfgabenformulierung
\item Kriterienfestlegung
\item Datenerhebung
\end{itemize}

\subsubsection{Modellbildung}

\begin{itemize}
\item Strukturfestlegung
\item Modellgleichungen

\begin{itemize}
\item Festlegung der Zustandsvariablen ist der Ausgangspunkt jeder Modellbildung
\end{itemize}
\item Modellvereinfachung
\end{itemize}

\subsubsection{Implementierung}

\begin{itemize}
\item Modellumsetzung
\item Berechnungsverfahren
\item Laufzeitoptimierung
\end{itemize}

\subsubsection{Validierung}

\begin{itemize}
\item Fehlersuche

\begin{itemize}
\item Modellierungsfehler

\begin{itemize}
\item vereinfachende Modellannahmen
\item ungenauigkeiten in Modellparametern
\end{itemize}
\item Approximationsfehler des iterativen Berechnungsverfahrens
\item Rundungsfehler (Rundung aufgrund der Zahlendarstellung im Computer)
\item Programmier-, Implementierungsfehler
\end{itemize}
\item Konsistenzprüfung
\item Daten-, Parameterabgleich
\end{itemize}

\paragraph{Gesamtfehler}

\begin{itemize}
\item Fehlerquellen

\begin{itemize}
\item Modellierungsfehler $\left|P-M\right|$
\item Diskretisierungsfehler $\left|M-D\right|$
\item Abbruchfehler $\left|D-L\right|$
\item Visualisierungsfehler $\left|L-V\right|$
\end{itemize}
\item Gesamtfehler setzt sich aus Einzelfehlern zusammen\[
\left|P-L\right|\le\left|P-M\right|+\left|M-D\right|+\left|D-L\right|+\left|L-V\right|\]

\item Akzeptanz einer Lösung $L$ zu gegebenen Problem $P$, wenn in allen
$4$ Schritten vergleichbar kleine Fehler gemacht wurden
\end{itemize}
\begin{description}
\item [Validierung]Sicherstellen, dass ein Simulationsmodell das reale
System in Rahmen der Zielsetzung ausreichend gut abbildet.
\end{description}

\paragraph{Elemente einer Validierung}

\begin{itemize}
\item Syntaktische Fehlerfreiheit der Implementierung (Debugging)
\item Numerische Korrektheit der Implementierung (Reproduktion einer analytischen
Lösung)
\item Plausibilität der Simulationsergebnisse und Verfahrensparameter ({}``naturgetreues''
Verhalten)
\item Zulässigkeit der Modellannahmen, logische Konsistenz (Anwendbarkeit
zur Problemlösung)
\item Ausreichende Detailliertheit des Modells (korrekte Modellstruktur)
\item Richtigkeit der Modellparameter (Parameteranpassung anhand realer
Daten)
\end{itemize}

\subsubsection{Simulationsläufe}

\begin{itemize}
\item Parametervariation
\item Strukturvariation
\item Vorhersage und Optimierung
\end{itemize}

\subsubsection{Ergebnispräsentation}

\begin{itemize}
\item Datenauswertung
\item Visualisierung und Animation

\begin{itemize}
\item Zeitverlauf
\item Phasenraumplot (Auftragen der Zustandsgrößen gegeneinander)
\item Spezialvisualisierungen
\item Animation
\end{itemize}
\item Dokumentation
\end{itemize}

\section{Diskrete Modellierung und Simulation}


\subsection{Terminologie}

\begin{description}
\item [System\index{System}]Ansammlung von Objekten, die zeitabhängig
nach spezifizierten Regeln miteinander interagieren
\item [Modell\index{Modell}]eine abstrakte, logische und mathematische
Darstellung der Objekte und Wechselbeziehungen in einem System
\item [Entität](entity) Objekt in einem System, das innerhalb des Modells
explizit dargestellt wird (z.B. Bedieneinheit, Kunde, Maschine, Transporter,
Werkstück)
\item [Attribut](attribute) Variable, die den Zustand einer Entität beschreibt
(z.B. Bearbeitungszustand, Belegung, Position)
\item [Ereignis](event) Beschreibung der Aktualisierung des Modellzustands
(z.B. Betreten eines Puffers, Maschinenbelegung) (Realisierung z.B.
mit Ereignisroutine für jeden Ereignistyp) 
\item [Ereignisliste]eine Liste mit Zeitpunkt und Typ der geplanten Ereignisse,
nach Ereigniszeitpunkten aufsteigend geordnet
\item [Aktivität](activity) zeitlich erstreckter Vorgang zwischen den initiierenden
und abschließenden Ereignissen einer Operation, die den Zustand einer
Entität transformiert (z.B. Aufenthalt in einem Puffer)
\item [Simulationsuhr](simulation clock) eine Variable, die den aktuellen
Stand der Simulationszeit angibt
\item [Zeitführungsroutine](timingroutine) eine Prozedur zur Auswahl des
nächsten Ereignisses aus der Ereignisliste und Vorstellen der Simulationsuhr
auf den nächsten Ereigniszeitpunkt
\item [Ergebnisroutine]eine Prozedur zur Berechnung der statistischen Schätzwerte
der Ergebnisvariablen anhand statistischer Zähler und zur Ausgabe
des Ergebnisprotokolls am Ende des Simulationslaufs
\item [Steuerprogramm]ein Programmteil, der wiederholt die Zeitführungsroutine
zur Bestimmung des nächsten Ereignistyps aufruft und die zugehörige
Ereignisroutine aufruft, bis Simulationslauf beendet
\end{description}

\subsection{DEVS}

\begin{description}
\item [DEVS]Discret Event Simulation
\item [Beschreibung]siehe Abbildung \vref{cap:Funktionsweise-einer-DEVS}
\end{description}
%
\begin{figure*}

\caption{\label{cap:Funktionsweise-einer-DEVS}Funktionsweise einer DEVS}

\hfill{}\includegraphics[%
  scale=0.35]{devs.gif}\hfill{}
\end{figure*}



\subsection{Warteschlangentheorie}


\subsubsection{Grundbegriffe Statistik\index{Statistik}}

\begin{description}
\item [Zufallsgröße\index{Zufallsgröße}]$\underbar{x}$
\item [Wahrscheinlichkeit\index{Wahrscheinlichkeit}]$Pr\left[\underbar{x}\le x\right]$
das $\underbar{x}$ kleiner oder gleich $x$
\item [Verteilungsfunktion\index{Verteilungsfunktion}]$F\left(x\right)=Pr\left[\underbar{x}\le x\right]$
\end{description}
\begin{itemize}
\item $F\left(a\right)-F\left(b\right)=Pr\left[a<\underbar{x}\le b\right]$
\item $F\left(-\infty\right)=0$
\item $F\left(\infty\right)=1$
\end{itemize}
\begin{description}
\item [Stetige~Verteilung]falls der Wertebereich von $\underbar{x}$ überabzählbar
unendlich ist, z.B. Reell.
\item [Wahrscheinlichkeitsdichte\index{Wahrscheinlichkeitsdichte}]$f\left(x\right)$
\end{description}
\begin{itemize}
\item ist nur für stetige Verteilung definiert
\item $f\left(x\right)dx=Pr\left[x<\underbar{x}\le x+dx\right]$
\item $F\left(x\right)=\int_{-\infty}^{x}f\left(s\right)ds$
\end{itemize}
\begin{description}
\item [Moment\index{Moment}]das $n$-te Moment einer Verteilunsfunktion
$E\left[\underbar{x}^{n}\right]=\int_{-\infty}^{\infty}s^{n}dF\left(s\right)$
\item [Erwartungswert\index{Erwartungswert}]$E\left[x\right]==\int_{-\infty}^{\infty}sdF\left(s\right)$
\end{description}
\begin{itemize}
\item Entspricht erstem Moment
\item auch Mittelwert\index{Mittelwert} genannt
\end{itemize}

\paragraph{Varianz\index{Varianz}}

\[
\sigma^{2}=E\left[\left(\underbar{x}-E\left[\underbar{x}\right]\right)^{2}\right]=\int_{-\infty}^{\infty}\left(s-E\left[\underbar{x}\right]\right)^{2}dF\left(s\right)\]


\begin{itemize}
\item Auch Streuungsquadrat\index{Streuungsquadrat}
\item $E\left[\left(\underbar{x}-a\right)^{2}\right]=\sigma^{2}\left(\underbar{x}\right)+\left(E\left[\underbar{x}\right]-a\right)^{2}$
\end{itemize}
\begin{description}
\item [Bedingte~Wahrscheinlichkeit\index{Bedingte Wahrscheinlichkeit}]$Pr\left[A|B\right]=\frac{Pr\left[A\wedge B\right]}{Pr\left[B\right]}$
\end{description}
\begin{itemize}
\item Wahrscheinlichkeit das $A$ eintritt wenn mann bereits weiss, das
$B$ eintritt
\item $Pr\left[A\wedge B\right]$ Wahrscheinlichkeit das $A$ und $B$ zusammen
eintreten
\end{itemize}
\begin{description}
\item [Unabhängigkeit\index{Unabhängigkeit}]zweier Ereignisse $A$ und
$B$, wenn $Pr\left[A|B\right]=Pr\left[A\right]$
\item [negativ~exponentielle~Verteilung\index{Verteilung}\index{exponentielle Verteilung}\index{negativ exponentielle Verteilung}]$F\left(x\right)=\begin{cases}
1-e^{-\mu x} & x\ge0\\
0 & x<0\end{cases}$
\end{description}
\begin{itemize}
\item Wahrscheinlichkeitsdichte $f\left(x\right)=\begin{cases}
\mu e^{-\mu x} & x\ge0\\
0 & x<0\end{cases}$
\item Varianz $\sigma^{2}\left(\underbar{x}\right)=\mu^{-2}$
\item Dies ist die einzige Verteilungsfunktion die Gedächnislos ist. D.h.
es gilt\[
Pr\left[\underbar{x}\le a+x|\underbar{x}>a\right]=Pr\left[\underbar{x}\le x\right]\]

\item Wenn im Mittel zwischen zwei Aufträgen $t$ Zeiteinheiten vergehen,
dann muss man im Mittel trotzdem noch $t$ Zeiteinheiten warten, unabhängig
davon, wieviel Zeit schon vergangen ist.
\end{itemize}

\subsubsection{Warteschlange Allgemein\index{Warteschlange}}

\begin{description}
\item [Anschauung]siehe Abbildung \vref{cap:WarteschlangeAnschaulich}%
\begin{figure*}

\caption{\label{cap:WarteschlangeAnschaulich}Warteschlangenmodell - Anschaulich}

\hfill{}\includegraphics{warteschlange1.gif}\hfill{}
\end{figure*}

\item [Beschreibung]siehe Abbildung \vref{cap:WarteschlangeAbstrakt}%
\begin{figure*}

\caption{\label{cap:WarteschlangeAbstrakt}Warteschlangenmodell - Abstrakt}

\hfill{}\includegraphics[%
  bb=0bp 0bp 933bp 330bp,
  clip,
  scale=0.5]{Warteschlange2.png}\hfill{}
\end{figure*}

\item [Charakterisierung]$A/B/c/N/K$

\begin{description}
\item [Kundenpopulation]$K$
\item [Ankunftszwischenzeitverteilung]$A$
\item [Warteschlangenlänge]$N$
\item [Bedienstationenanzahl]$c$
\item [Bedienzeitverteilung]$B$
\item [Abkürzungen](typische)
\end{description}
\begin{itemize}
\item $M$ (negativ) exponentialverteilt
\item $D$ deterministisch oder konstant verteilt
\item $G$ beliebig verteilt
\item z.B. $M/M/1=M/M/1/\infty/\infty$\\
$M/G/1=M/G/1/\infty/\infty$
\end{itemize}
\item [Ankunftsrate\index{Ankunftsrate}](mittlere) $\lambda=E\left[A\right]$
\item [Bedienrate](mittlere) pro Station $\mu=E\left[B\right]$
\item [Streuung~Bedienrate]$\sigma^{2}=\textrm{Var}\left(B\right)$
\item [Kunden~im~System]$L\left(t\right)$ zum Zeitpunkt $t$
\item [Langzeitverhalten]$L\left(t\right)\rightarrow L\left(\infty\right)$
stationäre Verteilung
\end{description}
\begin{itemize}
\item Ziel der Warteschlangentheorie ist es diese Größe zu bestimmen
\item $L$ Erwartungswert von $L\left(\infty\right)$
\item $p$ Langzeitausnutzung der Server
\item $w$ Langzeitaufenthaltzeit im System
\item Gesetz von Little\\
$L=\lambda\cdot w$
\end{itemize}

\subsubsection{M/M/1}

\begin{description}
\item [Bedingung]für die Stationarität $E\left[A\right]=\lambda<\mu=E\left[B\right]$
\item [Langzeitausnutzung]des Servers $\rho=\frac{\lambda}{\mu}$
\item [Kunden~im~System]$L=\frac{\rho}{1-\rho}$
\item [Langzeitaufenthaltszeit]$w=\frac{1}{\mu-\lambda}$
\item [Dichtefunktion]von $L\left(\infty\right)$ \[
d_{L\left(\infty\right)}\left(\xi\right)=P\left(L\left(\infty\right)=\xi\right)=\left(1-\rho\right)\cdot\rho^{\xi}\]

\end{description}
\begin{itemize}
\item dies ist die \emph{geometrische Verteilung\index{geometrische Verteilung}}
\end{itemize}
\begin{description}
\item [Eigenschaften]~
\end{description}
\begin{itemize}
\item Warteschlangen werden länger, wenn bei konstanten Erwartungswert die
Streuung der Bedienzeiten wächst
\item Jede Pufferlänge tritt mit gewisser Wahrscheinlichkeit einmal auf,
d.h. Puffer laufen stets gelegentlich voll
\item $n$ Server mit einer gemeinsamen Warteschlange sind besser als $n$
Server mit $n$ Warteschlangen
\end{itemize}

\subsubsection{M/G/1}

\begin{itemize}
\item $\rho=\frac{\lambda}{\mu}$
\item $L=\rho+\frac{\rho^{2}\left(1+\frac{\sigma^{2}}{\mu^{2}}\right)}{2\left(1-\rho\right)}$
\item $w=\frac{1}{\mu}+\frac{\lambda\left(1+\frac{\sigma^{2}}{\mu^{2}}\right)}{2\mu^{2}\left(1-\rho\right)}$
\end{itemize}

\subsubsection{M/D/1:$\sigma=0$}

\begin{itemize}
\item $\rho=\frac{\lambda}{\mu}$
\item $L=\rho+\frac{\rho^{2}}{2\left(1-\rho\right)}$
\item $w=\frac{1}{\mu}+\frac{\rho}{2\mu\left(1-\rho\right)}$
\end{itemize}

\subsubsection{M/M/c}

\begin{itemize}
\item $\rho=\frac{\lambda}{c\mu}$
\item $L=c\rho+\frac{\rho}{1-\rho}Pr\left[L\left(\infty\right)\ge c\right]$
\item $w=\frac{L}{\lambda}$
\item $P_{0}=\left(\frac{\left(c\rho\right)^{c}}{\left(1-\rho\right)\cdot c!}+\sum_{i=0}^{c-1}\frac{\left(c\rho\right)^{i}}{i!}\right)^{-1}$
\item $Pr\left[L\left(\infty\right)\ge c\right]=\frac{\left(c\rho\right)^{c}}{\left(1-\rho\right)\cdot c!}P_{0}$
\end{itemize}

\subsection{Petrinetze}


\subsubsection{Definition}

\begin{description}
\item [Petrinetz\index{Petrinetz}]$PN=\left(P,T,A,M'\right)$
\end{description}
\begin{itemize}
\item Gerichteter, bipartiter Graph - mit 2 Arten von Knoten (Plätzen und
Transitionen)
\item Zeichnung siehe Abbildung \vref{cap:Petrinetz-Grundelemente}%
\begin{figure}

\caption{\label{cap:Petrinetz-Grundelemente}Petrinetz Grundelemente}

\hfill{}\begin{picture}(31,46)(0,-46)

\node[ExtNL=y,NLangle=0.0,NLdist=2.0](n0)(8.33,-8.47){Platz}

\node[ExtNL=y,NLangle=0.0,NLdist=2.0,Nh=2.0,Nmr=0.5](n1)(8.33,-22.27){Transition}

\drawedge[ELdist=6.0](n0,n1){Kante}

\node[ExtNL=y,NLangle=0.0,NLdist=2.0](n2)(8.33,-36.47){Platz mit Markierung}

\rmark[rdist=2.0](n2)

\drawedge[ELdist=6.0](n1,n2){Kante}

\end{picture}\hfill{}
\end{figure}

\end{itemize}
\begin{description}
\item [Plätze\index{Plätze}]$P=\left\{ p_{1},\ldots,p_{n}\right\} $
\end{description}
\begin{itemize}
\item beschreiben mögliche Zustände, Darstellung als Kreis
\item Englisch: \emph{places\index{places}}
\end{itemize}
\begin{description}
\item [Transitionen\index{Transitionen}]$T=\left\{ t_{1},\ldots,t_{m}\right\} $
\end{description}
\begin{itemize}
\item beschreiben mögliche Ereignisse, Darstellung als Rechteck
\end{itemize}
\begin{description}
\item [gerichtete~Kanten]$A=\left\{ \left(a_{1},a_{1}'\right),\ldots,\left(a_{k},a_{k}'\right)\right\} $
\end{description}
\begin{itemize}
\item Verbinden Plätze und Transitionen
\item Englisch: \emph{directed edges}
\end{itemize}
\begin{description}
\item [Markierungen\index{Markierungen}]$M=\left(m_{1},\ldots,m_{n}\right)\in\mathbb{N}^{n}$
\end{description}
\begin{itemize}
\item definieren den aktuellen Zustand des Petrinetzses mit\\
$m_{i}=$ Anzahl der Markierungen in Platz $p_{i}$ 
\item werden in Plätzen gespeichert, Darstellung als schwarze Punkte im
Kreis
\item Anfangsmarkierung $M'$
\item Englisch: \emph{tokens\index{tokens}}
\end{itemize}
\begin{description}
\item [dynamik~eines~Petrinetzes]ist wie folgt charakterisiert
\end{description}
\begin{itemize}
\item Markierungen werden erzeugt, gelöscht oder verschoben durch Schalten
von Transitionen (firing of transitions)
\item Transition ist Schaltbereit (bzw. aktiviert) wenn alle ihre Eingangsplätze
markiert sind (bzw. mind. eine Marke enthalten)
\item Schaltbereite Transitionen können schalten (feuern), wobei eine Marke
aus jedem Eingangsplatz weggenommen und in jedem Ausgangsplatz eine
Marke hinzugefügt wird.
\item Feuern ist im allgemeinen ein nichtdeterministischer Vorgang
\end{itemize}
\begin{description}
\item [Typen]von Petrinetzen

\begin{description}
\item [Zeidiskrete](kausale) Modelle: Petrinetz beschreibt logisch, \emph{was}
in welcher Sequenz passiert
\item [Zeitkontinuierliche]Modelle: zusätzliche Vorhersage, \emph{wann}
ein Ereigniss auftritt.
\item [Stochastische]Petrinetze: zufallsverteilte Verzögerungsdauern der
Schaltregeln
\end{description}
\end{description}

\subsubsection{Mathematische Darstellung zeitdiskreter Petrinetze}

Die Struktur eines Petrinetzes mit $p$ Plätzen und $t$ Transitionen
kann durch zwei $t\times p$-Matrizen $W^{-}$und $W^{+}$ dargestellt
werden. In $W^{-}$ werden für alle Verbindungen eines Platze mit
einer Transition (in dieser Reihenfolge / pre-weights) 1en und sonst
0en eingetragen. In $W^{+}$ werden für alle Verbindungen einer Transition
mit einem Platz (in dieser Reihenfolge / post-weights) 1en und sonst
0en eingetragen. Die Inzidenzmatrix ergibt sich wie folgt\[
W=W^{+}-W^{-}\]



\subsubsection{Simulation zeitdiskreter Petrinetze}

\begin{description}
\item [Markierungsvektor]zum Zeitpunkt $r$\[
m\left(r\right)=\left(m_{1}\left(r\right),\ldots,m_{n}\left(r\right)\right)^{T}\]

\item [Kapazitätsvektor]$k=\left(k_{1},\ldots,k_{n}\right)^{T}$
\end{description}
\begin{itemize}
\item Es soll gelten $m_{i}\left(r\right)\le k_{i}$ für $i\in\left\{ 1,\ldots,n\right\} $
\end{itemize}
\begin{description}
\item [Aktivierungsfunktion]\[
u_{j}\left(r\right)=\begin{cases}
1 & \textrm{Transition }t_{j}\textrm{ aktiviert}\\
0 & \textrm{sonst}\end{cases}\]

\end{description}
\begin{itemize}
\item In allen {}``Vor-Plätzen'' müssen hinreichend viele Markierungen
verfügbar sein
\item In allen {}``Nach-Plätzen'' darf die maximale Kapazität nach Schalten
der Transition nicht überschritten werden
\end{itemize}
\begin{description}
\item [Schaltfunktion]$m\left(r\right)=m\left(r-1\right)+W\cdot u\left(r\right)$
\end{description}

\subsubsection{Charakteristika von Petrinetzen}


\paragraph{Erreichbarkeit\index{Erreichbarkeit} (Reachability\index{Reachability})}

\begin{itemize}
\item Ein Zustand heißt erreichbar von einem Anfangszustand, falls es eine
Sequenz vom Anfangszustand zu diesem exisitert
\item Der Erreichbarkeitsgraph (Graph mit möglichen zuständen des Petrinetzes
als Knoten und mit Transitionen beschrifteten gerichteten Kanten dazwischen.

\begin{itemize}
\item ob gewünschte Zustände erreicht, bzw. unerwünschte Zustände nicht
erreicht werden können
\item ob Vorgägner gefährlicher Zustände umgangen werden können
\end{itemize}
\item ist NP Hart in Speicher und Zeit
\end{itemize}

\paragraph{Beschränktheit\index{Beschränktheit}}

\begin{itemize}
\item Ein Petrinetz heißt beschränkt (bounded), falls in keinem Platz (zu
keinem Zeitpunkt) mehr als eine gewisse Maximalanzahl von $k_{i}$
Markierungen vonhanden ist.
\item Falls $k_{i}=1$, nennt man das Petrinetz \emph{sicher\index{sicher}}
(\emph{safe}\index{safe})
\end{itemize}

\paragraph{Verklemmung\index{Verklemmung} (Deadlock\index{Deadlock})}

\begin{itemize}
\item Eine Verklemmung (deadlock) eines Petrinetzes ist eine Transition
(oder eine Menge von Transitionen), die nicht schalten können.
\item Diese können \emph{nie} schalten.
\end{itemize}

\paragraph{Lebendigkeit\index{Lebendigkeit} (Liveness\index{Liveness})}

\begin{itemize}
\item Eine Transition heißt tod (dead, non-live), falls sie bei keiner Folgemarkierung
mehr aktivierbar ist.
\item Diese kann \emph{nicht mehr} schalten.
\end{itemize}

\section{Zeitkontinuierliche Simulierung und Simulation}


\subsection{Einleitung}


\subsubsection{Örtlich konzentrierter Systemzustand}

Die bestimmende Gleichung einer Funktion einer unabhängigen Veränderlichen
heißt gewöhnliche Differentialgleichung, d.h. die Gleichung hängt
nur von der Funktion selber und ihren Ableitungen ab.

Systeme mit örtlich konzentrierten Systemzustand werden durch gewöhnliche
Differentialgleichungen beschrieben.


\subsubsection{Örtlich verteilter Systemzustand}

Die bestimmende Gleichung einer Funktion von mehr als einer unabhängigen
veränderlichen heißt partielle Differentialgleichung.

Systeme mit örtlich verteilten Systemzustand werden durch partielle
Differentialgleichungen beschrieben.


\subsection{Beschreibung zeitkontinuierlicher Systeme}


\subsubsection{Allgemein}

\begin{description}
\item [Beschreibung]der Begriffe siehe Abschnitt \vref{sub:Systemstruktur-eines-Modells}.
\end{description}
\begin{itemize}
\item Im Nachfolgenden werden Vektorpfeile der Einfachheit halber weggelassen.
\end{itemize}

\paragraph{Zustandsgleichung / Systemfunktion}

\begin{eqnarray*}
\dot{x}\left(t\right) & = & \frac{dx\left(t\right)}{dt}\\
 & = & \left(\begin{array}{c}
\dot{x}_{1}\left(t\right)\\
\vdots\\
\dot{x}_{n}\left(t\right)\end{array}\right)\\
 & = & \left(\begin{array}{c}
f_{1}\left(x\left(t\right),u\left(t\right),t\right)\\
\vdots\\
f_{n}\left(x\left(t\right),u\left(t\right),t\right)\end{array}\right)\\
 & = & f\left(x\left(t\right),u\left(t\right),t\right)\end{eqnarray*}



\paragraph{Ausgangsgleichung}

\begin{eqnarray*}
y\left(t\right) & = & g\left(x\left(t\right),u\left(t\right),t\right)\\
 & = & \left(\begin{array}{c}
g_{1}\left(x\left(t\right),u\left(t\right),t\right)\\
\vdots\\
g_{m}\left(x\left(t\right),u\left(t\right),t\right)\end{array}\right)\end{eqnarray*}


\begin{description}
\item [Zustandsgrößen]$x=\left(x_{1},\ldots,x_{n}\right)^{T}$
\item [Stellgrößen]$u=\left(u_{1},\ldots,u_{l}\right)^{T}$
\item [Ausgangsgrößen]$y=\left(y_{1},\ldots,y_{m}\right)^{T}$
\end{description}

\subsubsection{Verschiedene Systemdynamiken}

\begin{description}
\item [Höhere~Ordnung]Jedes System von Differentialgleichungen höherer
Ordnung kann auf ein System 1. Ordnung transformiert werden.\\
Hierzu wird bei einem System $k$-ter Ordnung $\left(x_{1}=x,\: x_{2}=\dot{x},\: x_{3}=\ddot{x},\ldots,\: x_{k}=x^{\left(k\right)}\right)^{T}$
als Systemzustandmit entsprechender Systemfunktion genommen.
\item [autonomes~System]Ein System das nicht explizit von $t$ abhängt
wird als \emph{autonom\index{autonom}} bezeichnet.\\
Jedes System lässt sich durch Hinzunahme von $t$ zu den Systemzuständen
mit $\dot{t}=1$ in ein autonomes System transformieren.
\item [lineare~Systemdynamik]hat folgende Gestalt\begin{eqnarray*}
\dot{x} & = & f\left(x,u\right)=Ax+Bu\\
y & = & g\left(x,u\right)=Cx+Du\end{eqnarray*}
mit konstanten (oder rein zeitabhängigen) Koeffizientenmatrizen\begin{eqnarray*}
A\in\mathbb{K}^{n\times n} &  & B\in\mathbb{K}^{n\times l}\\
C\in\mathbb{K}^{m\times n} &  & D\in\mathbb{K}^{m\times l}\end{eqnarray*}

\end{description}

\subsection{Modellanalyse\index{Modellanalyse}}


\subsubsection{Lösbarkeit\index{Lösbarkeit}}

\begin{description}
\item [Lösungstrajektorie]Man zeichne in ein $x,t$ Diagramm ($x$ kann
Dimension größer $1$ haben, dann dafür mehrere Achsen verwenden)
in jeden Punkt einen Pfeil mit der Steigung $f\left(x,t\right)=\dot{x}$
ein (\emph{Richtungsfeld}\index{Richtungsfeld}). Wenn man nun im
Punkt $x\left(0\right)$ ($n$ Integrationskonstanten) startet und
immer den Pfeilrichtungen folgt, erhält mein eine \emph{Lösungstrajektorie\index{Lösungstrajektorie}}.
\item [eindeutige~Lösung]$x\left(t\right)$ mit $t>0$ für ein autonomes
DGL-System $1$ter Ordnung existiert falls für alle (zulässigen) $x_{1},x_{2}\in\mathbb{K}^{n}$
die folgende Lipschitzbedingung erfüllt ist. Es exisitert ein $L\in\mathbb{K}$
so dass für alle (zulässigen) $x_{1},x_{2}\in\mathbb{K}^{n}$ gilt\[
\left\Vert f\left(x_{1}\right)-f\left(x_{2}\right)\right\Vert \le L\left\Vert x_{1}-x_{2}\right\Vert \]
 mit einer belibigen Norm $\left\Vert .\right\Vert $.
\end{description}

\subsubsection{Gleichgewichtslösung\index{Gleichgewichtslösung}}

Außer der Existenz einer (eindeutigen) Lösung von \[
\dot{x}=f\left(x,u\right),\; x\left(0\right)=x_{0}\in K^{n}\]
 ist die Existenz eines \emph{stationären Zustandes} $x\left(t\right)\rightarrow x_{s}$
für $t\rightarrow\infty$ für konstantes $u\left(t\right)=u_{s}$
von Interesse.

\begin{description}
\item [Notwendig]$0=f\left(x_{s},u_{s}\right)$
\item [Lineares~System]$Ax_{s}=-Bu_{s}$ eindeutig Lösbar mit $x_{s}=-A^{-1}Bu_{s}$
wenn $\det\left(A\right)\neq0$
\end{description}
\begin{itemize}
\item Lösbar sobald $\textrm{Rang}\left(A\right)=\textrm{Rang}\left(A|Bu_{s}\right)$
\end{itemize}
\begin{description}
\item [Nichtlineares~System]ist zudem notwendig das die Determinante der
Jakobimatrix im Lösungsumfeld $\left(x_{s}\right)$ nicht 0 ist.\[
\exists\varepsilon:\forall\left\Vert x-x_{s}\right\Vert <\varepsilon:\det\frac{\partial f\left(x,u_{s}\right)}{\partial x}\neq0\]

\end{description}
\begin{itemize}
\item Es kann keine, eine, mehrere, unendlich viele oder keine Lösung geben.
\end{itemize}

\subsubsection{\label{sub:Jacobi-Matrix}Jacobi-Matrix\index{Jacobi-Matrix}}


\paragraph{Definition}

\[
\frac{\partial f}{\partial x}=\left(\begin{array}{ccc}
\frac{\partial f_{1}}{\partial x_{1}} & \cdots & \frac{\partial f_{1}}{\partial x_{n}}\\
\vdots & \ddots & \vdots\\
\frac{\partial f_{n}}{\partial x_{1}} & \cdots & \frac{\partial f_{n}}{\partial x_{n}}\end{array}\right)\]



\paragraph{Vorwärtsdifferentenquotient\index{Vorwärtsdifferentenquotient}}

\begin{itemize}
\item Approximation der $j$-ten Spalte der Matrix\[
\frac{\partial f}{\partial x_{j}}\approx\frac{1}{\delta\left(x_{j}\right)}\left(f\left(x+e_{j}\delta\left(x_{j}\right)\right)-f\left(x\right)\right)\]

\item $e_{j}$ ist der $j$-te Einheitsvektor
\item Schrittweite $\delta\left(x_{j}\right)=\varepsilon\left(1+\left|x_{j}\right|\right)$
\item Wahl der Toleranz $\varepsilon$ bei {}``gut skalierter'' Funktion
$f$: $\varepsilon=\sqrt{\varepsilon_{mach}}$ mit $\varepsilon_{mach}$
relative \emph{Maschienengenauigkeit}\index{Maschienengenauigkeit},
z.B. $\varepsilon_{mach}\approx2.2*10^{-16}$ bei double precision
\item Aufwand: Approximation erfordert im wesentlichen $n+1$ Auswertungen
von $f$
\item Genauigkeit:\begin{eqnarray*}
 & \left|\frac{\partial f_{i}\left(x\right)}{\partial x_{j}}-\frac{1}{\delta\left(x_{j}\right)}\left(f_{i}\left(x+e_{j}\delta\left(x_{j}\right)\right)-f_{i}\left(x\right)\right)\right|\\
 & \le\left|\delta\left(x_{j}\right)\right|\cdot\left|\frac{\partial^{2}f_{j}\left(x\right)}{\partial x_{j}^{2}}\right|\end{eqnarray*}
d.h. maximal die Hälfte der gültigen Dezimalstellen von $f$
\end{itemize}
\begin{description}
\item [Besetztheisstruktur\index{Besetztheisstruktur}]einer Jacobi-Matrix
gibt wieder, in welchen Stellen der Matrix von 0 verschiedene Werte
stehen.
\end{description}
\begin{itemize}
\item Dies gibt die Kopplungen der DGL wieder
\item sehr große Systeme können nur durch Ausnutzung der (hoffentlich dünnen)
Besetztheitsstruktur der Jakobimatrix effizient numerisch simuliert
werden.
\end{itemize}
\begin{description}
\item [Schrittweise~Aufdatierung\index{Schrittweise Aufdatierung}]({}``Updates'')
einer Approximation der Jacobi-Matrix (sogenanntes {}``Quasi Newton
Verfahren'')
\end{description}
\begin{itemize}
\item im Allgemeinen: Rang $1$ Verfahren z.B. nach Broyden:\\
Approximation der Jacobimatrix $J^{\left(k\right)}\approx\frac{\partial f}{\partial x}\left(x^{\left(k\right)}\right)$
durch schrittweise Aufaddierung einer $n\times n$ Matrix vom Rang
$1$ (rank $1$ update)
\end{itemize}
\begin{eqnarray*}
 & J^{\left(k\right)}= & J^{\left(k-1\right)}+\frac{1}{\left\Vert \alpha^{\left(k-1\right)}\cdot\Delta x^{\left(k-1\right)}\right\Vert }\cdot\\
 &  & \underbrace{f\left(x^{\left(k\right)}\right)-f\left(x^{\left(k-1\right)}\right)}_{n\times1\textrm{ Spaltenvektor}}\cdot\underbrace{\left.\alpha^{\left(k-1\right)}\cdot\Delta x^{\left(k-1\right)}\right.^{T}}_{1\times n\textrm{ Zeilenvektor}}\end{eqnarray*}


\begin{itemize}
\item $\alpha^{\left(k-1\right)}\cdot\Delta x^{\left(k-1\right)}=x^{\left(k\right)}-x^{\left(k-1\right)}$
\item Bei symmetrischer Jacobi-Matrix: Rang 2-Verfahren
\end{itemize}
\begin{description}
\item [Symbolisches~Differenzieren\index{Symbolisches Differenzieren}]durch
systematisches Anwenden von Ketten-, Produkt etc. Regeln
\end{description}
\begin{itemize}
\item z.B. mit Maple, Mathematica, Macsyma
\item Vorteil: kein Approximierungsfehler, nur Rundungsfehler
\item Nachteil: liefert lange, unübersichtliche Formeln; hoher Berechnungsaufwand
\end{itemize}
\begin{description}
\item [Automatisches~Differenzieren\index{Automatisches Differenzieren}]sind
spezielle Algorithmen zur Transformation eines C-, Fortran oder Matlab-
Programms von $f\left(x\right)$ in Programm zur Auswertung der Jacobi-Matrix
\end{description}
\begin{itemize}
\item Vorteil: kein Approximatinsfehler, nur Rundungsfehler
\item Schwierigkeiten u.a. bei Fallunterscheidungen (if-then-else)
\end{itemize}

\subsubsection{Linearisierung\index{Linearisierung} um die Ruhelage}

\[
\left(\Delta x\right)^{\bullet}\approx\underbrace{\left.\frac{\partial f}{\partial x}\right|_{x_{s},u_{s}}}_{A}\cdot\Delta x+\underbrace{\left.\frac{\partial f}{\partial u}\right|_{x_{s},u_{s}}}_{B}\cdot\Delta u\]


\begin{itemize}
\item $x_{s},u_{s}$ sind Koordinaten der jeweiligen Ruhelage um die linearisiert
wird
\item Fällt ein Ruhezustand mit einer Sprung- oder Knickstelle (oder anderen
Ausnahmestelle) zusammen, so kann man um ihn nicht linearisieren (und
auch nicht in einer {}``engeren'' Umgebung).
\item Es lässt sich auch um eine Referenztrajektorie linearisiern. Formeln
sehen genauso aus wie hier. Interpretierbar als Linearisierung um
zeitveränderliche Ruhelage
\end{itemize}

\subsubsection{Lösen\index{Lösen einer linearen DGL} einer linearisierten (linearen)
DGL}

\begin{description}
\item [Gegeben]$\dot{x}=A\cdot x$
\item [Lösungsansatz]$x\left(t\right)=c\cdot e^{\lambda t}$
\end{description}
\begin{itemize}
\item $x,c\in\mathbb{C}^{n}$ $\lambda\in\mathbb{C}$
\end{itemize}
\begin{description}
\item [Zwischentherm]$\left(\lambda\cdot E-A\right)\cdot c=0$
\end{description}
\begin{itemize}
\item Eigenwerte von $A$ als Lösungen für $\lambda$ bestimmen. $n$ komplexe
Lösungen für folgende Gleichung:\[
\det\left(\lambda_{i}\cdot E-A\right)=0\]

\end{itemize}
\begin{description}
\item [Lösung]$x\left(t\right)=\sum_{i=1}^{n}c_{i}e^{\lambda_{i}t}$
\end{description}
\begin{itemize}
\item $\lambda_{i}$ sind Eigenwerte - $n$ Stk.
\item $c_{i}$ sind Eigenvektoren - Anhand von Anfangsbedingungen genauer
zu bestimmen - $n$ Stk.
\item Nur falls $A$ diagonalisierbar. Ansonsten Jordanketten Bilden:

\begin{itemize}
\item Hauptvektoren \[
\left(\lambda E-A\right)v^{\left(k\right)}=v^{\left(k-1\right)}\]
\[
e^{\lambda_{i}t}\left(c_{1}v_{1}+c_{2}\left(v_{2}+tv_{1}\right)+c_{3}\left(v_{3}+tv_{2}+t^{2}v_{1}\right)\right)\]

\end{itemize}
\end{itemize}

\subsubsection{Stabilität\index{Stabilität}}

Für den Fall das $A$ eine rein reelle Matrix war gilt:

\begin{description}
\item [aperiodische~Dämpfung]wenn alle Eigenwerte reell und negativ sind
\end{description}
\begin{itemize}
\item Stabil
\end{itemize}
\begin{description}
\item [aperiodisch~ungedämpft]wenn alle Eigenwerte reell und mind. einer
positiv ist
\end{description}
\begin{itemize}
\item instabil
\end{itemize}
\begin{description}
\item [gedämpfte~Oszilation]wenn alle Realanteile der Eigenwerte negativ
sind und komplexe Eigenwerte immer konjungiert nocheinmal auftauchen.
\end{description}
\begin{itemize}
\item stabil
\end{itemize}
\begin{description}
\item [ungedämpfte~Oszillation\index{Oszillation}]wenn mindestens ein
Realanteil eines Eigenwertes positiv ist und komplexe Eigenwerte immer
konjungiert nocheinmal auftauchen.
\end{description}
\begin{itemize}
\item instabil
\end{itemize}
\begin{description}
\item [instabil]bedeutet das bei einer begrenzen Eingabe eine theoretisch
unbegrenzte Ausgabe erfolgen kann.
\end{description}

\subsubsection{Zeitcharakteristik\index{Zeitcharakteristik}}

\begin{description}
\item [Zeitcharakteristika]$T_{i}$
\end{description}
\begin{itemize}
\item sind für aperiodische Vorgänge die Dauer, bis sich der Wert um den
Faktor $e$ (bzw. $\frac{1}{e}$) verändet hat
\item sind für periodische Vorgänge die Periodendauer
\item können mit Hilfe der Eigenwerte $\lambda_{i}$ bestimmt werden
\end{itemize}
\begin{description}
\item [reeller~EW]$T_{i}=\frac{1}{\left|\lambda_{i}\right|}$
\item [imaginärer~EW]$T_{i}=\frac{2\pi}{\left|\lambda_{i}\right|}$
\end{description}

\paragraph{konjungiert komplexer EW}

\[
T_{i}=\textrm{min}\left\{ \frac{1}{\left|\Re\left(\lambda_{i}\right)\right|},\frac{2\pi}{\left|\Im\left(\lambda_{i}\right)\right|}\right\} \]



\paragraph{Minmale Zeitcharakteristik}

\[
T_{min}=\min\left\{ T_{i}|i=1,\ldots,n\right\} \]



\paragraph{Maximale Zeitcharakteristik}

\[
T_{max}=\max\left\{ T_{i}|i=1,\ldots,n\right\} \]


\begin{description}
\item [Simulationsdauer\index{Simulationsdauer}]für nichtlineares System
(Faustregel)
\end{description}
\begin{itemize}
\item stabiles System: $t_{f}=5\cdot T_{max}$
\item instabiles System bis z.B. ein gewünschter Wert über-/unterschritten
wurde
\end{itemize}
\begin{description}
\item [Diskretisierungsschrittweite\index{Diskretisierungsschrittweite}]$h=\Delta t\le\alpha\cdot T_{min}$ 
\end{description}
\begin{itemize}
\item mit $\alpha\in\left[\frac{1}{20},\frac{1}{5}\right]$
\end{itemize}

\subsubsection{Steife\index{Steife DGL} DGL}

\begin{description}
\item [Definition]Eine DGL wird steif genannt wenn sie sehr unterschiedliche
Zeitcharakteristika enthält
\end{description}
\begin{itemize}
\item $s>10^{3}\ldots10^{7}$
\end{itemize}
\begin{description}
\item [Steifheitsmaß\index{Steifheitsmaß}]$s=\frac{T_{max}}{T_{min}}$
\end{description}
\begin{itemize}
\item numerische Lösung benötigt Rechenzeit Proportional zu $s$
\end{itemize}
\begin{description}
\item [Integration]von steifen DGLn am besten mit implizieten Verfahren
\end{description}

\subsubsection{Unstetige Rechte Seite}

Die rechte Seite $f$ der Differentialgleichung $\dot{x}=f\left(x,u\right)$
(oder eine ihrer Ableitungen) kann \emph{unstetig\index{unstetig}}
sein, z.B. wegen

\begin{itemize}
\item unstetiger Steuerung $u\left(t\right)$, z.B. Ventil auf/zu
\item modellinhärenter Unstetigkeiten (z.B. Kollision von Roboterarm, Abtrennung
einer Raketenbrennstufe)
\item Einige numerische Methoden benötigen (mehrfach) stetig ableitbare
rechte Seite. Hier Vorsicht walten lassen bzw. berücksichtigen.
\item Verbesserung der numerischen Simulation durch Detektion der Unstetigkeit
und abschnittsweiser Berechnung.
\end{itemize}

\subsection{Grundlagen der numerischen Simulation}


\subsubsection{Zahlendarstellung}

\begin{description}
\item [Normalisierte~Gleitpunktzahl]Zahl bei dem genau eine Stell vor
dem Komme ungleich 0 ist. Die entsprechende Kommaverschiebung wird
im Exponenten des Faktors untergebracht.
\end{description}
\[
\underbrace{3.001109}_{Mantisse}\cdot\left.\underbrace{10}_{Basis}\right.^{\overbrace{9}^{Exponent}}\]


\[
z=\pm\left(d_{1}B^{0}+d_{2}B^{-1}+\ldots+d_{t}B^{-t+1}\right)B^{E}\]


\begin{description}
\item [Basis]$B$ feste Zahl, z.B. 10 (Dezimal) oder 2 (Binär)
\end{description}
\begin{itemize}
\item bei Basis $B=2$ braucht $d_{1}$ nicht expliziet gespeichert werden,
da es durch die Normalisierung $1$ sein \emph{muss}
\end{itemize}
\begin{description}
\item [Exponent]$E$ ganze Zahl und beschränkt $E_{min}\le E\le E_{max}$
\end{description}
\begin{itemize}
\item mehr Bits für den Exponenten ergibt größeren Zahlenbereich
\end{itemize}
\begin{description}
\item [Ziffern]$d_{i}\in\left\{ 0,1,2,\ldots,B-1\right\} $
\end{description}
\begin{itemize}
\item $z$ normalisiert wenn $d_{1}\neq0$
\end{itemize}
\begin{description}
\item [Mantisse]$M=d_{1}d_{2}\ldots d_{t}$ 
\end{description}
\begin{itemize}
\item Länge der Mantisse $t$ (konstant)
\item mehr Bits für die Mantisse ergibt größeren (relative) Genauigkeit
\end{itemize}

\paragraph{Eigenschaften}

\begin{itemize}
\item Es gibt eine größte und eine kleinste darstellbare Zahl
\item Auf heutigen Computer ist $B=2$ quasi Standard
\item bei Basis $B=2$ braucht $d_{1}$ nicht expliziet gespeichert werden,
da es durch die Normalisierung $1$ sein \emph{muss}
\item Es wird noch ein weiteres Bit für das Vorzeichen gebraucht: $s$
\end{itemize}

\paragraph{Binär}

\begin{itemize}
\item $z=\left(-1\right)^{s}\cdot\left(1+M\right)\cdot2^{E}$
\item Einige besondere Belegungen sind reserviert für Unendlich und co:
siehe IEEE 754
\end{itemize}
\begin{description}
\item [relative~Maschienengenauigkeit\index{relative Maschienengenauigkeit}\index{Maschienengenauigkeit}](machine
precision) heißt der Abstand der Zahlen im Intervall $\left[1,2\right]$
\end{description}
\begin{itemize}
\item IEEE single precision $eps=2^{-23}\approx1,19\cdot10^{-7}$
\item IEEE double precision $eps=2^{-52}\approx2,2\cdot10^{-16}$
\end{itemize}

\subsubsection{Rundungsfehler\index{Rundungsfehler}}

\begin{description}
\item [Rundung\index{Rundung}]$\textrm{rd}\left(g\right)$ Abbilden einer
Zahl auf die {}``am nächsten liegende'' darstellbare Zahl\[
\forall g:\left|x-\textrm{rd}\left(g\right)\right|\le\left|x-g\right|\]

\end{description}
\begin{itemize}
\item Es gibt unterschiedliche Rundungsarten nach IEEE 754

\begin{itemize}
\item R1 immer aufrunden (nach rechts)
\item R2 immer abrunden (nach links)
\item R3 Runden durch abschneiden (nach Null)
\item R4 Runden zur nächsten Zahl (zum Nächsten)
\end{itemize}
\end{itemize}
\begin{description}
\item [relative~Rundungsfehler\index{relative Rundungsfehler}\index{Rundungsfehler}]$\varepsilon=\frac{\textrm{rd}\left(x\right)-x}{x}$
\end{description}
\begin{itemize}
\item $\textrm{rd}\left(x\right)=x\cdot\left(1+\varepsilon\left(x\right)\right)$
\item mit $\left|\varepsilon\left(x\right)\right|\le\textrm{eps}$
\item Für die elementaren arithmetischen Operationen ($+,-,\cdot,\/$) gilt
zumindest näherungsweise\\
$f_{gerundet}\left(x,y\right)\approx f\left(x,y\right)\cdot\left(1+\varepsilon_{f}\right)$
mit $\left|\varepsilon_{f}\right|\le\textrm{eps}$
\end{itemize}

\subsubsection{Fortpflanzung\index{Fortpflanzung} von Rundungsfehlern}

\begin{itemize}
\item Assoziativ- und Distributivgesetz gelten nicht für Gleitpunktarithmetik:\\
\[
\textrm{gl}\left(\textrm{gl}\left(x+y\right)+z\right)\neq\textrm{gl}\left(x+\textrm{gl}\left(y+z\right)\right)\]
 ($\textrm{gl}$ ist Gleitpunktimplementierung der entsprechenden
Funktion)
\item In allen Ausdrücken \[
\textrm{gl}\left(x\diamond y\right)=\left(x\diamond y\right)\cdot\left(1+\varepsilon\right)\]
 sukzessive ersetzen.\\
Daraus Ermittlung einer Darstellung\[
\textrm{gl}\left(f\right)=f\cdot\left(1+\left(\ldots\right)\varepsilon_{1}+\left(\ldots\right)\varepsilon_{2}+\ldots\right)\]
 mit von Eingangsdaten abhängigen Verstärkungsfaktoren
\end{itemize}

\subsubsection{Kondition\index{Kondition}\index{Fehler}\index{Fehler!absoluter}\index{Fehler!relativer}}

\begin{description}
\item [Gegeben]$f:D\subseteq\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ sei
mindestens einmal stetig differenzierbar
\item [absuluter~Fehler~in~$x$]~
\end{description}
\[
\Delta x_{j}=\left|\tilde{x}_{j}-x_{j}\right|\]



\paragraph{absuluter~Fehler~in~$y$}

\begin{eqnarray*}
\Delta y_{j} & = & \left|\tilde{y}_{j}-y_{j}\right|=\left|f_{i}\left(\tilde{x}\right)-f_{i}\left(x\right)\right|\end{eqnarray*}


\begin{description}
\item [relativer~Fehler~in~$x$]$\varepsilon_{x_{j}}=\frac{\Delta x_{j}}{x_{j}}$
\end{description}

\paragraph{relativer~Fehler~in~$y$}

\[
\varepsilon_{y_{j}}=\frac{\Delta y_{j}}{y_{j}}=\sum_{k=1}^{n}\underbrace{\frac{x_{k}}{f_{j}\left(x\right)}\frac{\partial f_{j}\left(x\right)}{\partial x_{k}}}_{Konditionszahlen}\cdot\varepsilon_{x_{k}}\]


\begin{description}
\item [Konditionszahlen\index{Konditionszahlen}](siehe vorherige Formel)
nennt man die Verstärkungsfaktoren des relativen Fehlers in den Eingangsdaten.
\end{description}
\begin{itemize}
\item sind diese groß ist das Problem schlecht Konditioniert
\item sind diese klein ist das Problem gut Konditioniert
\item hängen \emph{nicht} von der Implementierung der Funktion ab, sondern
nur von deren Eigenschaften

\begin{description}
\item [Multiplikation]$\varepsilon_{\cdot}=\varepsilon_{x_{1}}+\varepsilon_{x_{2}}$
\item [Division]$\varepsilon_{/}=\varepsilon_{x_{1}}-\varepsilon_{x_{2}}$
\item [Addition~/~Subtraktion]~\[
\varepsilon_{\pm}=\frac{x_{1}}{x_{1}\pm x_{2}}\varepsilon_{x_{1}}-\frac{x_{2}}{x_{1}\pm x_{2}}\varepsilon_{x_{2}}\]

\end{description}
\begin{itemize}
\item Subtraktion (speziell von gleich großen Zahle) ist extrem schlecht
Konditioniert: \emph{Auslöschung}
\end{itemize}
\begin{description}
\item [Wurzel]$\varepsilon_{\sqrt{\ }}=\frac{\varepsilon_{x_{1}}}{2}$
\end{description}
\end{itemize}
\begin{description}
\item [Numerische~Stabilität\index{Numerische Stabilität}\index{Stabilität}]ein
gut Konditioniertes Problem kann bei schlechter Implementierung trotzdem
extreme Fehlerverstärkung haben
\end{description}
\begin{itemize}
\item Formel Umformen! Umständlich kann besser als direkt sein! Subtraktionen
vermeiden!
\end{itemize}

\subsection{Berechnung nichtlinearer Gleichgewichtslösungen}


\subsubsection{Newton Verfahren\index{Newton Verfahren} - Basisversion}

\begin{description}
\item [Gesucht]$x_{s}$ mit $0=f\left(x_{s}\right)$
\item [Start]$\left(k=0\right)$ Wahr eines Startvektors $x^{\left(0\right)}$
\end{description}
\begin{itemize}
\item z.B. aus Kentnissen über das dem Modell zugrundelegene physikalische
Modell
\item Ausprobieren
\item Herantasten von der bekannten Lösung eines einfacheren Problems (\emph{Fortsetzungsmethode}\index{Fortsetzungsmethode})
\end{itemize}
\begin{description}
\item [Iterationsschritt]$\left(k\rightarrow k+1\right)$
\end{description}
\begin{itemize}
\item Berechnung von $f\left(x^{\left(k\right)}\right)$
\item Berechnung der Jakobimatrix $\frac{\partial f}{\partial x}\left(x^{\left(k\right)}\right)$

\begin{itemize}
\item siehe Abschnitt \vref{sub:Jacobi-Matrix}
\item oder Jakobimatrix durch \emph{konstante Matrix}, z.B. $\frac{\partial f}{\partial x}\left(x^{\left(0\right)}\right)$
bzw. deren Approximation ersetzen

\begin{itemize}
\item Verfahren nicht mehr quadratisch, höchstens linear konvergent
\item Wenn konvergent, dann heufig schneller als {}``normales'' Newtonverfahren
\end{itemize}
\end{itemize}
\item Berechnung der Korrektur (Suchrichtung) $\Delta x^{\left(k\right)}$
durch lösen des linearen Gleichungssystems\[
\frac{\partial f}{\partial x}\left(x^{\left(k\right)}\right)\cdot\Delta x^{\left(k\right)}=-f\left(x^{\left(k\right)}\right)\]

\item Berechnung der neuen Näherung $x^{\left(k+1\right)}=x^{\left(k\right)}+\Delta x^{\left(k\right)}$
\end{itemize}
\begin{description}
\item [Terminierungstest]Falls {}``nahe genug'' an der Lösung oder {}``kein
Fortschritt'' \emph{Stop}, ansonsten $k$ um 1 erhöhen und nächsten
Iterationsschritt.
\end{description}
\begin{itemize}
\item {}``Nahe genug'' an der Lösung

\begin{itemize}
\item keine nennenswerte Änderung in $x^{\left(k+1\right)}$\[
\left\Vert \Delta x^{\left(k\right)}\right\Vert \le\varepsilon_{1}\cdot\left(1+\left\Vert x^{\left(k\right)}\right\Vert \right)\]

\item Funktionswerte klein genug\[
\left\Vert f\left(x^{\left(k+1\right)}\right)\right\Vert \le\varepsilon_{2}\]

\end{itemize}
\item {}``kein Fortschritt'' mehr

\begin{itemize}
\item keine nennenswerte Abnahme mehr\[
\left\Vert f\left(x^{\left(k+1\right)}\right)\right\Vert \ge\left\Vert f\left(x^{\left(k\right)}\right)\right\Vert -\varepsilon_{3}\]

\item zu viele Iterationsschritte\[
k+1\ge k_{max}\]

\end{itemize}
\item Für $\varepsilon_{j},j=1,2,3$ geeignete Toleranzen z.B. $\varepsilon_{j}=10^{-4},\ldots,10^{-8}$
\end{itemize}

\subsubsection{Problembereiche}


\paragraph{Einzugsbereich bei mehreren Lösungen}

\begin{itemize}
\item Es können einige Nullstellen durch andere in Ihrere Umgebung versteck
sein, so dass sie nur gefunden werden wenn der Startwert in einem
(kleinen) Bereich liegt.
\end{itemize}

\paragraph{Divergenz\index{Divergenz} und Singularitäten\index{Singularitäten}}

\begin{itemize}
\item Singularitäten in der Nähe von Nullstellen können diese {}``Verstecken''
\end{itemize}

\paragraph{hoch Nichtlineare Probleme}

\begin{itemize}
\item Divergenz obwohl Startwert {}``nahe'' an Nullstelle
\end{itemize}
\begin{description}
\item [Abhilfe]durch {}``kleineren'' Schritt zur Berechnung von $x^{\left(k+1\right)}$\[
x^{\left(k+1\right)}=x^{\left(k\right)}+\alpha^{\left(k\right)}\cdot\Delta x^{\left(k\right)}\]

\end{description}
\begin{itemize}
\item mit $0<\alpha_{min}\le\alpha^{\left(k\right)}\le1$
\item Bestimmung der Schrittweite durch Näherungsweise Minimierung von\begin{eqnarray*}
\varphi\left(\alpha\right) & = & \left\Vert f\left(x^{\left(k\right)}+\alpha\cdot\Delta x^{\left(k\right)}\right)\right\Vert _{2}^{2}\\
 & = & \sum_{i=1}^{n}\left(f_{i}\left(x^{\left(k\right)}+\alpha\cdot\Delta x^{\left(k\right)}\right)\right)^{2}\end{eqnarray*}

\item Fausregel: $\alpha$ nur so {}``klein wie nötig'' und {}``so groß
wie möglich'', denn nur für $\alpha\approx1$ quadratische Konvergenz
\end{itemize}

\subsection{Numerische Lösung der nichtlinearen Zustandsdifferentialgleichungen}


\subsubsection{Einleitung}

\begin{description}
\item [Bahn\index{Bahn}](Pfad, Weg) kontinuierlich, räumliche Punktfolge
\item [Trajektorie\index{Trajektorie}]Bahn mit {}``zeitlichen Beschränkungen''
\end{description}
\begin{itemize}
\item z.B. außer Position auch Geschwindigkeit (und Beschleunigung) an jedem
Punkt der Bahn (evtl. Impliziet über $t$ Achse) gegeben
\end{itemize}
\begin{description}
\item [Einsatzgebiet]der numerischen Lösung überall dort wo nichtlinearitäten
vorliegen bzw. keine expliziete Lösung gefunden wird (werden kann)
\end{description}

\paragraph{Klassen Numerischer Integrationsverfahren\index{Integrationsverfahren}}

jeweils explizit und implizit:

\begin{itemize}
\item Einschrittverfahren - nur diese sind hier erwähnt
\item Mehrschrittverfahren
\item Extrapolationsverfahren
\end{itemize}

\paragraph{Kriterien für Integratorenwahl\index{Integratorenwahl}}

\begin{itemize}
\item Rechenaufwand (Berechnungseffizienz)
\item Genauigkeit (Approximationsfehler)
\item Eignung für steife Systeme (Stabilität). Bei steifen DGL impliziete
Verfahren bevorzugen!
\item Implementierungsaufwand (Eigenprogrammierung oder Verwendung einer
Bibliothek)
\end{itemize}

\paragraph{Ordnung\index{Ordnung eines Integrationsverfahrens} des Verfahrens
($n$)}

\begin{itemize}
\item Approximationsfehler bei gegebener Schrittweite $h_{k}$ für Methoden
höhere Ordnung ist sehr viel kleiner: $O\left(h^{n}\right)$
\item Berechnungsaufwand dafür höher: $n$ Funktionsauswertungen von $f$
\item Rechte Seite muss mindesten $n$ mal stetig differenzierbar sein.

\begin{itemize}
\item Wenn es nur $m<n$ mal stetig differenzierbar ist bleibt der Berechnungsaufwand
gleich, aber der Approximationsfehler liegt nur noch bei $O\left(h^{m}\right)$
\end{itemize}
\item Diese Genauigkeitsaussagen gelten nicht für sehr große oder sehr kleine
Schrittweiten. Bei sehr kleinen dominieren Rundungsfehler.
\end{itemize}

\subsubsection{Einschrittverfahren\index{Einschrittverfahren}}

\begin{description}
\item [Gegeben]$x_{k}\approx x\left(t_{k}\right)$
\item [Gesucht]$x_{k+1}\approx x\left(t_{k+1}\right)$
\item [Ansatz]für Einschrittverfahren\[
x_{k+1}=x_{k}+h\cdot\Phi\left(t_{k},x_{k},x_{k+1},h,f\right)\]

\item [Konsistenzbedingung]für Einschrittverfahren\[
\lim_{h\rightarrow0}\Phi\left(t_{k},x_{k},x_{k+1},h,f\right)=f\left(x_{k}\right)\]

\end{description}

\subsubsection{Explizites Euler Verfahren\index{Euler Verfahren!Explizites}}

\[
x_{k+1}=x_{k}+h\cdot f_{k}\]


\begin{itemize}
\item Rechenaufwand gering, nur 1 Auswertung pro Schritt. Für Echtzeitsysteme
interessant
\item Genauigkeit: Approximationsfehler $O\left(h^{1}\right)$

\begin{itemize}
\item Für hohe Genauigkeiten kleine Schrittweite nötig $\Rightarrow$ Stabilitätsprobleme
\end{itemize}
\item Schrittweite $h=\Delta t$
\item Gesamtfehler $\varepsilon_{k}=\left|x_{k}-x\left(k\cdot h\right)\right|$

\begin{itemize}
\item Bei zu kleiner Schrittweite dominieren Rundungsfehler
\item Bei zu großer Schrittweite dominieren Einzelschritt- und Fortpfanzungsfehler
\item $\Rightarrow$ Notwendigkeit für Adaptive Schrittweitensteuerung
\end{itemize}
\item Einzelschritt- und Fortpflanzungsfehler \[
\varepsilon_{k}'\le\sum_{i=1}^{k}\varepsilon_{i}^{E}+\sum_{i=1}^{k-1}\varepsilon_{i}^{F}\]


\begin{itemize}
\item $\varepsilon_{i}^{E}$ Einzelschrittfehler
\item $\varepsilon_{i}^{E}$ Fortpflanzungsfehler
\end{itemize}
\end{itemize}

\subsubsection{Implizites Euler Verfahren\index{Implizites Euler Verfahren}}

\[
x_{k+1}=x_{k}+h\cdot f_{k+1}\]


\begin{itemize}
\item Ein Verfahrensschritt erfordert die (näherungsweise) Lösung der nichtlinearen
Gleichung \[
0=x_{k+1}-x_{k}-h_{k}\cdot f\left(x_{k+1}\right)\]
nach $x_{k+1}$ 
\item Rechenaufwand: sehr hoch
\item Genauigkeit: Approximatinsfehler $O\left(h^{1}\right)$

\begin{itemize}
\item Für hohe Genauigkeit kleine Schrittweite nötig, aber bessere Stabilitätseigenschaften
als explizites Euler Verfahren
\end{itemize}
\end{itemize}

\subsubsection{Heun Verfahren}

\begin{itemize}
\item Ist ein Prädiktor-Korrektor Verfahren

\begin{itemize}
\item Prädiktor Schritt:\[
x_{k+1}^{P}=x_{k}+h_{k}\cdot f_{k}\]

\item Kottektor Schritt: Mittelung des Gradienten\[
x_{k+1}=x_{k}+h_{k}\cdot\frac{1}{2}\left(f_{k}+f\left(x_{k+1}^{P}\right)\right)\]

\end{itemize}
\item Insgesamt:\begin{eqnarray*}
s_{1} & = & f\left(x_{k}\right)\\
s_{2} & = & f\left(x_{k}+h_{k}\cdot s_{1}\right)\\
x_{k+1} & = & x_{k}+\frac{h_{k}}{2}\left(s_{1}+s_{2}\right)\end{eqnarray*}

\item Ist ein zweistufiges Einzelschrittverfahren - Rechenaufwand zwei Funktionsauswertungen
von $f$
\item Genauigkeit: Approximationsfehler $O\left(h^{2}\right)$

\begin{itemize}
\item Heun Verfahren ist $2.$ Ordnung
\end{itemize}
\end{itemize}

\subsubsection{Runge-Kutta-Verfahren 4. Ordnung}


\paragraph{Allgemeiner Ansatz}

\begin{eqnarray*}
s_{1} & = & f\left(x_{k}\right)\\
s_{2} & = & f\left(x_{k}+h\cdot\alpha_{1}\cdot s_{1}\right)\\
s_{3} & = & f\left(x_{k}+h\cdot\beta_{1}\cdot s_{1}+h\cdot\alpha_{2}\cdot s_{2}\right)\\
s_{4} & = & f\left(x_{k}+h\cdot\gamma_{1}\cdot s_{1}+h\cdot\beta_{2}\cdot s_{2}+h\cdot\alpha_{3}\cdot s_{3}\right)\\
x_{k+1} & = & x_{k}+h\cdot\underbrace{\left(\delta_{1}\cdot s_{1}+\delta_{2}\cdot s_{2}+\delta_{3}\cdot s_{3}+\delta_{4}\cdot s_{4}\right)}_{\Phi}\end{eqnarray*}
man versucht nun die unbekannten Koeffizienten\[
\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\gamma_{1},\delta_{1},\delta_{2},\delta_{3},\delta_{4}\]
so zu bestimmen, dass

\begin{itemize}
\item die Konsistenzbedingung \[
\lim_{h\rightarrow0}\Phi\left(t_{k},x_{k},x_{k+1},h,f\right)=f\left(x_{k}\right)\]
 erfüllt ist:\[
\Rightarrow\delta_{1}+\delta_{2}+\delta_{3}+\delta_{4}=1\]

\item der Approximationsfehler möglichst klein wird (d.h. $O\left(h^{4}\right)$
\end{itemize}

\paragraph{klassisches RK-Verfahren 4. Ordnung}

\begin{eqnarray*}
s_{1} & = & f\left(x_{k}\right)\\
s_{2} & = & f\left(x_{k}+\frac{h}{2}\cdot s_{1}\right)\\
s_{3} & = & f\left(x_{k}+\frac{h}{2}\cdot s_{2}\right)\\
s_{4} & = & f\left(x_{k}+h\cdot s_{3}\right)\\
x_{k+1} & = & x_{k}+\frac{h}{6}\cdot\left(s_{1}+2\cdot s_{2}+2\cdot s_{3}+s_{4}\right)\end{eqnarray*}


\begin{itemize}
\item Rechenaufwand: vier Auswertungen von $f$
\item Genauigkeit: Approximationsfehler $O\left(h^{4}\right)$
\end{itemize}

\subsubsection{Schrittweitensteuerung\index{Schrittweitensteuerung}}


\paragraph{Konstante Schrittweite $h_{k}$}

\begin{itemize}
\item ungenau, wenn gesuchte Lösung sich lokal sehr stark ändert
\item ineffizient, wenn gesuchte Lösung sich lokal sehr wenig ändert
\end{itemize}

\paragraph{Idee der Schrittweitensteuerung}

\begin{itemize}
\item Wahl von $h_{k}$ {}``so groß wie möglich'' und {}``so klein wie
nötig'' und das neu von Schritt zu Schritt
\item Wahl von $h_{k},$ so dass globaler Approximationsfehlers nach einem
Schritt unterhalb einer Fehlerschranke liegt
\end{itemize}

\paragraph{Einschrittverfahren der Ordnung $p$}

\begin{itemize}
\item Berechnung von $2$ Näherungen für $x_{k+1}$: einmal für Schrittweite
$h_{k}$ und einmal für Schrittweite $\frac{h_{k}}{2}$
\item Daraus Schätzung des lokalen Fehlers
\item Anpassung von $h_{k}$ so dass lokale Fehlerschätzung unter Schranke
liegt.
\item Aufwand: $3p$ Funktionsauswertungen
\end{itemize}

\paragraph{zwei Verfahren unterschiedlicher Ordnung}

\begin{itemize}
\item z.B. $p$ und $p+1$
\item Berechnung von $2$ Näherungen für $x_{k+1}$ für dieselbe Schrittweite
$h_{k}$
\item Bei geeigneter {}``Einbettung'' der beiden Verfahren, z.B. Runge-Kutta-Verfahren
4. und 5. Ordnung zusammen nur $p+1$ Funktionsauswertungen nötig
\item Ansatz viel effizienter als {}``Einschrittverfahren der Ordnung $p$''
\end{itemize}

\subsubsection{Klassifikation zeitkontinuierlicher Simulationswerkzeuge}


\paragraph{Level 0}

\begin{itemize}
\item Direkte Programmierung

\begin{itemize}
\item Fortran
\item C
\item Pascal
\item Matlab
\end{itemize}
\end{itemize}

\paragraph{Level 1}

\begin{itemize}
\item Simulationssprachen

\begin{itemize}
\item ASCL
\item VHDL
\item Dare-P
\item Desire
\end{itemize}
\item Simulationsframeworks

\begin{itemize}
\item Simulink
\item C++ Klassenbibliothek
\end{itemize}
\end{itemize}

\paragraph{Level 2}

\begin{itemize}
\item Graphische Modellierung

\begin{itemize}
\item Simulink
\item WorkingModel
\item Aspen
\item Stella
\end{itemize}
\item Spezialsimulatoren

\begin{itemize}
\item KSIM
\end{itemize}
\end{itemize}

\paragraph{Level 3}

\begin{itemize}
\item Multidisziplinäre Modellgenerierung

\begin{itemize}
\item Modellica
\item VHDL-A
\end{itemize}
\end{itemize}

\subsection{Integration von Zustands-DGLn mit Unstetigkeiten}

\begin{description}
\item [Ausgangsproblem]$\dot{x}=f\left(x,u,t\right)$
\end{description}

\paragraph{Annahme}

\begin{itemize}
\item $f\left(x,u,t\right)$ sei abschnittsweise mehrfach stetig differenzierbar
\item An den Übergängen der Abschnitte ist $f$ möglicherweise unstetig,
bzw. nicht häufig genug stetig differenzierbar
\item Die Übergänge werden durch formulierbare Ereignisse (events) ausgelöst,
die zustandsabhängig oder zeitgesteuert sein können
\end{itemize}
\begin{description}
\item [Schaltfunktion]Die (Um-) Schaltpunkte (events) $t_{s,i},\: i=1,\ldots,n_{S}$
werden im Allgemeinen als (einfache) Nullstellen reellwertiger Schaltfunktionen
\[
q_{k}\left(x\left(t_{s,i}\right),t_{s,i}\right)=0,\; k\in\left\{ 1,\ldots,n_{q}\right\} \]
 charakterisiert. Bei der numerischen Integration müssen nun die Vorzeichen
der Schaltunktionen beobachtet werden, d.h.
\end{description}
\begin{itemize}
\item wenn zwischen der letzten berechneten Näherung $x_{k}=\tilde{x}\left(t_{k}\right)$
und der neuen Näherung $x_{k+1}=\tilde{x}\left(t_{k+1}\right)$ ein
Vorzeichenwechsel in (mind.) einer Schaltfunktion stattfindet,
\item muss der dazwischenliegende erste Schaltzeitpunkt bestimmt werden
(und zwar in der Genauigkeitsanforderung des Benutzers und der Ordnung
des Verfahrens implizit gegebenen Genauigkeit)

\begin{itemize}
\item Kompination von numerischer Integration und (eindimensionaler) Nullstellensuche
\end{itemize}
\item Vorraussetzung: Schrittweite $h_{k}$ klein genug, so dass kein doppelter
Vorzeichenwechsel in derselben Schaltfunktion stattfindet.
\end{itemize}

\section{Modulare Modellbildung und Simulation komplexer Systeme}


\subsection{Modulare Modellbildung}


\subsubsection{Modul}

\begin{itemize}
\item Darstellung siehe Abbildung \vref{cap:Modul}.%
\begin{figure*}

\caption{\label{cap:Modul}Abstrakte, graphische Darstellung eines Moduls}

\hfill{}\includegraphics[%
  scale=0.4]{Modul.png}\hfill{}
\end{figure*}

\item Zerlegung des zu modellierenden Systems in Module
\item Jedes Modul ist über Schnittstellen $S_{i}$ mit übrigen Modulen verbunden
\item Schnittstellen zeigen aus Modulen heraus
\item Export der Beschreibungsvariablen des Moduls über Schnitstellen $S_{i}$
\item für jedes Modul eigene Modellgleichungen, die die Schnittstellenvariablen
verknüpfen
\item Verschaltung von Modulen durch Verknüpfungen von Schnittstellen in
einem Knoten

\begin{itemize}
\item dabei Unterscheidung zwischen Fluß- und Potentialvariablen
\end{itemize}
\end{itemize}
\begin{description}
\item [Flußvariablen]Summe ist $0$ in einem Knoten\[
\sum_{k=1}^{n}i_{k}=0\]

\item [Potentialvariablen]Der Wert der Variablen ist gleich\[
u_{1}=u_{2}=\ldots=u_{m}\]

\end{description}

\paragraph{Konventionen}

\begin{itemize}
\item Pro Schnittstelle je eine Potential und Flussvariable möglich
\item Schnittstellen können zu Multiplexkanälen gebündelt werden

\begin{itemize}
\item z.B. $x,y,z$ Position (Potentialvariablen) und Kräfte (Flussvariablen)
\end{itemize}
\end{itemize}

\subsubsection{Automatische Gleichungsgenerierung}

\begin{itemize}
\item Name der Globalen Variablen ist {}``Modulname.InternerName'' bzw.
{}``Modulname.SchnittstellenName''
\item Export der Modellgleichung des Moduls mit Globalen Valiablennamen
\item Hinzuname der Kopplungsgleichungen (für Potential und Flussvariablen)
\item Das entstandene System nennt sich \emph{Differentialalgebrasiches\index{Differentialalgebrasiches System}
System} - DAE\index{DAE}
\end{itemize}

\subsubsection{Differentialalgebrasiches\index{Differentialalgebrasiches System}
System}

\begin{itemize}
\item Ein so automatisch aufgestelltes DAE System enthält im allgemeinen
noch redundante Gleichungen. Dieses kann durch algebraische Umformungen
noch reduziert und vereinfacht werden
\item sehr große Zahl von Gleichungen entsteht
\item viele Kopplungen leicht eliminierbar
\item nichtlineare Gesetze unter Umständen nicht eleminierbar
\item resultierendes DGL-System nach (theoretischer) vollständiger Elimination
sehr unhandlich

\begin{itemize}
\item hierzu z.B. einige Hilfsgleichungen (Modellgleichungen) Ableiten und
ineinander einsetzen. $\Rightarrow$ {}``Rumtricksen''
\end{itemize}
\item Allgemeines DAE-System\begin{eqnarray*}
\dot{x}_{d} & = & f\left(x_{d},x_{a}\right)\\
0 & = & h\left(x_{d},x_{a}\right)\end{eqnarray*}


\begin{itemize}
\item $x_{d}$ differentielle Variablen
\item $x_{a}$ algebraische Variablen
\item $\dim\left(f\right)=\dim\left(x_{d}\right)$\\
$\dim\left(h\right)=\dim\left(x_{a}\right)$
\end{itemize}
\end{itemize}

\subsubsection{Prinzipien der modularen Modellierung}

\begin{itemize}
\item \emph{Zerlegung} des Systems in Module mit Ein/Ausgangsschnittstellen
\item Zuordnung einer \emph{Potential/Flussvariablen} pro Schnittstelle
\item Formulierung von \emph{Gleichungen} pro Modul unter ausschließlicher
Benutzung von Schnittstellen/Konstanten (evtl. interner temporärer
Variablen - Zwischenergebnisse)
\item \emph{Kopplung} zweier Module über (kompatible) Schnittstellen induziert
eine Potential- und eine Flussgleichung
\end{itemize}

\subsection{Numerische Integration von Zustands-DAEs}


\subsubsection{Problemstellung}

\begin{itemize}
\item Bisher betrachtete Bewegungsgleichungen eines dynamischen Systems

\begin{itemize}
\item basieren auf einem minimalen Satz von Zustandsvariablen (\emph{Minimalkoordinaten\index{Minimalkoordinaten}})
\item führen auf Systeme gewöhnlicher DGLn (ordinary differential equations,
\emph{ODE}s\index{ODE}), die numerisch effiziernt integriert werden
können
\item aber nicht alle Systeme sind leicht in Minimalkoordinaten formulierbar
\end{itemize}
\item Rechnergestützte, modulare Modellierung

\begin{itemize}
\item führt auf Systeme differential-algebraischer Gleichungen (DAEs)
\item Integration von DAEs ist aufwendiger als von ODEs
\end{itemize}
\end{itemize}

\subsubsection{Eigenschaften von DAEs}

\begin{itemize}
\item DGLn mit Nebenbedingungen\begin{eqnarray*}
\dot{x}_{d} & = & f\left(x_{d},x_{a}\right)\\
0 & = & h\left(x_{d},x_{a}\right)\end{eqnarray*}

\item benötigt konsistente Anfangswerte, d.h.\begin{eqnarray*}
x_{d}\left(0\right) & = & x_{d,0}\\
x_{a}\left(0\right) & = & x_{a,0}\\
0 & = & h\left(x_{d,0},x_{a,0}\right)\end{eqnarray*}

\item Totale Differentiation der Nebenbedingung nach der Zeit $t$\[
0=\frac{\partial h\left(x_{d},x_{a}\right)}{\partial x_{d}}\cdot\underbrace{\frac{dx_{d}}{dt}}_{f\left(x_{d},x_{a}\right)}+\frac{\partial h\left(x_{d},x_{a}\right)}{\partial x_{a}}\cdot\frac{dx_{a}}{dt}\]

\item Wenn Jakobimatrix von $h$ nach $x_{a}$ invertierbar ist, kann formal
nach $x_{a}$ aufgelöst werden\[
\dot{x_{a}}=-\left(\frac{\partial h\left(x_{d},x_{a}\right)}{\partial x_{a}}\right)^{-1}\cdot\frac{\partial h\left(x_{d},x_{a}\right)}{\partial x_{d}}\cdot f\left(x_{d},x_{a}\right)\]

\item Mit dieser und der Gleichung $\dot{x_{d}}=f\left(x_{d},x_{a}\right)$
erhält man so wieder eine ODE die wie bisher gelöst werden kann
\end{itemize}

\subsubsection{Index einer DAE}

\begin{itemize}
\item Kriterium für die Schwierigkeit der numerischen Lösung einer DAE ist
der sogenannte \emph{Index\index{Index}}
\item Es gibt verschiedene Index-Definitionen. Wichtigster und häufigster
ist:\\
Differentieller Index $j$ einer DAE ist die kleinste Anzahl der nötigen
Differentiationen, so dass \[
\frac{d^{j}}{dt^{j}}h\left(x_{d},x_{a}\right)\]
 explizit nach $\dot{x_{a}}$ auflösbar ist.
\item Je größer des Index ist, um so schwieriger ist die numerische Integration!
\item Möglichkeit der \emph{Bifurkation\index{Bifurkation}} (Verzweigung)
der Lösung
\end{itemize}

\subsubsection{Lösung mit ODE Löser und implizieten Gleichungslöser}

\begin{itemize}
\item $x_{a}$ als Funktion von $x_{d}$ auffassen\[
0=h\left(x_{d}\left(t\right),x_{a}\left(t\right)\right)\]
 und $x_{d}\left(t\right)$ bekannt $\Rightarrow$ $x_{a}=x_{a}\left(x_{d}\right)$
\item ODE-Integrationsverfahren kombiniert mit nichtlinearen Gleichungslöser
\item Besser: Spezailverfahren für DAEs
\end{itemize}

\subsubsection{Drift\index{Drift}}

\begin{itemize}
\item Bei numerischer unvermeidlicher Abweichung von exakter Lösung für
$x_{a}$ {}``driftet'' die numerische Lösung ab
\item Abhilfe: (impliziter) Prädiktor/Korrektor-Ansatz
\end{itemize}

\subsubsection{Impliziter DAE-Lösungsansatz}

\begin{itemize}
\item Impliziter Ansatz (z.B. Euler)\begin{eqnarray*}
{\scriptstyle \frac{x_{d}\left(t+\Delta t\right)-x_{d}\left(t\right)}{\Delta t}} & = & f\left(x_{d}\left(t+\Delta t\right),x_{a}\left(t+\Delta t\right)\right)\\
0 & = & h\left(x_{d}\left(t+\Delta t\right),x_{a}\left(t+\Delta t\right)\right)\end{eqnarray*}

\item Numerische Lösung mit Newton-Verfahren nach $x_{d}\left(t+\Delta t\right),x_{a}\left(t+\Delta t\right)$\begin{eqnarray*}
0 & = & {\scriptstyle \Delta t\cdot f\left(x_{d}\left(t+\Delta t\right),x_{a}\left(t+\Delta t\right)\right)-x_{d}\left(t+\Delta t\right)-x_{d}\left(t\right)}\\
0 & = & {\scriptstyle h\left(x_{d}\left(t+\Delta t\right),x_{a}\left(t+\Delta t\right)\right)}\end{eqnarray*}

\item Benötigt Invertierbarkeit der entsprechenden Jakobimatrix:\[
\left(\begin{array}{cc}
\Delta t\frac{\partial f}{\partial x_{d}}-E & \Delta t\frac{\partial f}{\partial x_{a}}\\
\frac{\partial h}{\partial_{d}} & \frac{\partial h}{\partial_{a}}\end{array}\right)\]


\begin{itemize}
\item Vorraussetzung: Index 1
\item DAEs vonhöherem Index müssen auf Index 1 reduziert werden
\end{itemize}
\end{itemize}

\subsubsection{Weiterer Ansatz für DAE-Integratoren}

\begin{itemize}
\item Einbettung in steifes ODE-System für $\varepsilon$ sehr klein\begin{eqnarray*}
\dot{x}_{d} & = & f\left(x_{d},x_{a}\right)\\
\varepsilon\cdot\dot{x}_{a} & = & h\left(x_{d},x_{a}\right)\end{eqnarray*}

\item Untersuchung von (implizieten) Runge-Kutta und Extrapolationsverfahren
für Grenzfall $\varepsilon=0$ liefern effiziente und zuverlässige
DAE-Integratoren
\item Sehr verbreitet sind auch implizite Mehrschrittverfahren: z.B.: BDF-Verfahren,
DASSL
\end{itemize}

\subsubsection{Visualisierung algebraischer Abhängigkeiten}

\begin{itemize}
\item Hierbei handelt es sich um einen bipartiten Graphen mit gerichteten
und ungerichteten Kanten

\begin{itemize}
\item Für jede Gleichung wird das Gleichungsymbol in einen Kreis geschrieben
und als Knoten verwendet
\item Für jede in den Gleichungen vorkommende Variable gibt es einen Knoten
(aber ohne Umkreisung) 
\end{itemize}
\item Die gerichteten Kanten zwischen den Variablen und Gleichungen deuteten
an, dass die Gleichung nach dieser Variablen auflösbar ist
\item Falls eine Variable zwar in einer Gleichung vorkommt, diese aber nicht
nach ihr auflösbar ist, wird eine ungerichtete Kante verwendet
\item Alle Variablen, von denen mindestens zwei Formeln abhängen und mindestens
eine Formel nach auflösbar ist lassen sich durch Gleichsetzen oder
Einsetzen eliminieren
\item Interessante Fragestellung: Lässt sich diesem Graphen der Index ansehen?
\end{itemize}

\subsubsection{Prinzipielle Bearbeitungsschritte bei einer automatischen Modellgenerierung}

\begin{enumerate}
\item System{}``schaltbild''

\begin{itemize}
\item Gleichungsgenerierung
\end{itemize}
\item DAE-System

\begin{itemize}
\item Elinination der Potential und Flussgleichungen
\end{itemize}
\item vereinfachtes DAE-System

\begin{itemize}
\item Indexreduktion
\end{itemize}
\item Index-1-DAE-System

\begin{itemize}
\item Partition und Schleifenreduktion
\end{itemize}
\item vereinfachtes Index1-DAE-System

\begin{itemize}
\item ODE- bzw. DAE-Löser
\end{itemize}
\item numerische Lösung
\end{enumerate}
\printindex{}
\end{document}
