%% 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{} \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