Kalmanfilter auf Graphen. - Ilmenau. - 49 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Der Kalmanfilter ist ein beliebtes statistisches Hilfsmittel zur Vorhersage in zahlreichen Modellen verschiedenster Anwendungsgebiete. Ziel dieser Arbeit ist es, den Kalmanfilter auf einem Graphenmodell anzuwenden. Hierzu wird ein Zustandsraummodell auf einem gerichteten azyklischen Graphen definiert. Die Ecken werden univariaten Zuständen und Beobachtungen entsprechen, die Kanten Übergängen zwischen diesen. Es wird ein Algorithmus zur Vorhersage dieser Zustände, bedingt auf die Beobachtungen vorgestellt, welcher auf den Ecken des Graphen iteriert. Seine Vorgehensweise entspricht der des Kalmanfilters. Hierbei wird die vorteilhafte inverse Wurzelform ausgenutzt. Weiterhin wird auf den Zusammenhang der bedingten Unabhängigkeiten in Graphenmodellen auf gerichteten azyklischen Graphen mit der Besetztheit der Wurzel der inversen Kovarianzmatrix eingegangen. Es wird vorgestellt, wie sich diese innerhalb des Algorithmus verhält, um ein Ausnutzen in der Anwendung zu ermöglichen. Oft ist es möglich, Gaußsche lineare Zustandsraummodelle in ein solches Graphenmodell zu überführen. Inwieweit die Anwendung des in dieser Arbeit vorgestellten Algorithmus darauf möglich und sinnvoll ist, wird diskutiert.
Ein Fourier-Schätzer für die multivariate Volatilität von Handelsobjekten. - Ilmenau. - 93 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Die Volatilität von Handelsobjekten ist ein zentraler Parameter in der Finanzmathematik und Ökonometrie. Wir untersuchen den Schätzer von Malliavin und Mancino (2009) für die multivariate instantane Volatilität von Preisprozessen, die als stetige Semimartingale modelliert werden. Das Verfahren basiert auf Fourier-Methoden und baut auf einer Identität zwischen den Fourier-Koeffizienten der Volatilität und den Fourier-Stieltjes-Koeffizienten der Preisprozesse auf. Die Volatilität wird aus ihren geschätzten Fourier-Koeffizienten als stochastische Funktion auf der gesamten Zeitmenge rekonstruiert. Der resultierende nichtparametrische Kurvenschätzer kann durch zwei Eingabegrößen angepasst werden und ist auf diskrete ungleichmäßig beabstandete, asynchrone Beobachtungen der Preisprozesse anwendbar. Unter gewissen Bedingungen wird seine Konsistenz bewiesen, wobei das Resultat von Malliavin und Mancino auf den Fall nicht periodischer Volatilität ausgedehnt wird. In einer Simulationsstudie wird der Einfluss der Eingabegrößen für verschiedenartige Volatilitätsfunktionen untersucht und ein Bias für gewisse Parameterwahlen unter asynchronen Beobachtungen festgestellt.
The cut cover problem in acyclic digraphs. - Ilmenau. - 27 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Die Arbeit untersucht Überdeckungen der Kantenmenge eines Digraphen mit k Schnitten (im Folgenden als k-Cut Cover bezeichnet). Eine äquivalente Eigenschaft ist die k-Färbbarkeit der Kanten so, dass keine zwei aufeinanderfolgenden Kanten uv, vw dieselbe Farbe erhalten. Eine Eckenfärbung mit höchstens M(k) Farben ist hinreichend für die Existenz eines k-Cut Covers, wobei M(k) der zentrale Binomialkoeffizient „k über [k/2]“ ist. Für symmetrische Digraphen erweisen sich diese beiden Eigenschaften als äquivalent. Hieraus folgt, dass das Problem zu entscheiden, ob ein (symmetrischer) Digraph ein k-Cut Cover besitzt, für k ≥ 3 NP-vollständig ist. Insbesondere untersucht diese Arbeit minimale Cut Covers in azyklischen Digraphen. Jeder azyklische Digraph mit maximalem Eingrad M(k)-1 hat ein k-Cut Cover, da er eine Eckenfärbung mit M(k) Farben besitzt. Es wird gezeigt, dass diese Schranke bestmögliche ist, und dies löst ein von Alon, Bollobás, Gyárfás, Lehel und Scott gestelltes Problem. Für die abgeänderte Bedingung, dass für jeden Knoten entweder sein Eingrad oder Ausgrad nach oben beschränkt ist, wird das minimale k, welches ein k-Cut Cover im Allgemeinen garantiert, bis auf höchstens zwei mögliche Werte bestimmt. Außerdem werden Cut Covers in Potenzen von gerichteten Pfaden betrachtet. Es wird gezeigt, dass ein k-Cut Cover in der d-ten Potenz beliebig langer gerichteter Pfade genau dann existiert, wenn d ≤ (c-o(1)) 2^k, für eine Konstante c ∈ [1/e, 1/2]. Ein Cut Cover in einem Digraphen kann auf alle Digraphen übertragen werden, die homomorph zu ihm sind. Die Existenz eines Homomorphismus zu einer Potenz eines gerichteten Pfades ist in polynomialer Zeit überprüfbar und äquivalent zu einer Gleichgewichtsbedingung für die Anzahl der Vorwärts- und Rückwärtskanten von ungerichteten Kantenzügen. Das Problem, zu entscheiden, ob ein azyklischer Digraph ein 3-Cut Cover besitzt, ist NP-vollständig, sogar für planare Digraphen mit maximalem Ein- und Ausgrad 3, die einen Homomorphismus zur dritten Potenz des gerichteten Pfades auf 12 Ecken besitzen.
Numerical solutions ased on the ADI iteration for large-scale control problems: the Lyapunov, Riccati, and Lur’e equations. - Ilmenau. - 55 Seiten
Technische Universität Ilmenau, Masterarbeit 2024
Wir stellen eine Reihe von Methoden vor, die auf der ADI-Iteration basieren, für die numerische Lösung der Lyapunov-Gleichungen, der algebraischen Riccati-Gleichungen und der Lur'e-Gleichungen. Diese Matrixgleichungen spielen eine wichtige Rolle in der Kontrolltheorie, und wir konzentrieren uns auf großskalige, spärliche Probleme. Die LRCF-ADI-Iteration, welche die Eigenschaften sowohl des ADI-Modells als auch der niedrigrangigen Cholesky-Faktoren integriert, wird zur Lösung der Lyapunov-Gleichung verwendet. Die LRCF-NM, welche die Kleinman-Newton-Iteration und die LRCF-ADI-Iteration kombiniert, wird zur Lösung der algebraischen Riccati-Gleichung verwendet. Die stabilisierende Lösung dieser Gleichung kann das entsprechende LQR-Problem lösen. Der Störungsansatz, der die LRCF-NM anwendet, wird zur Lösung der Lur'e-Gleichungen im Falle von Singularität verwendet. Die maximale Lösung dieser Gleichungen kann das entsprechende linear-quadratische optimale Steuerungsproblem lösen. In dieser Arbeit demonstrieren wir durch zwei Beispiele, wie diese Methoden die entsprechenden Matrixgleichungen numerisch lösen.
Path following and obstacle avoidance algorithms for underactuated unmanned surface vessel. - Ilmenau. - 29 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2024
Die Entwicklung von autonomen Steuerungen von unbemannten Schiffen in flachen Gewässern ist ein wichtiges Forschungsgebiet im Bereich der Binnenschiffahrt. Ein übliches Szenario in dem sich ein solches unbemanntes Schiff befinden könnte, ist die Fahrt entlang eines Pfades, welcher durch Koordinatenpunkte vorgegeben ist. Nun befinden sich entlang des Pfades noch Hindernisse, welche es zu vermeiden gilt und gleichzeitig herrscht noch eine Strömung mit konstanter Richtung und Stärke, wie zum Beispiel auf einem Fluss. Das Ziel ist es nun, einen Algorithmus mit Sicherheitsgarantien zu entwickeln, welcher das Schiff erfolgreich entlang des Pfades steuert. Zuerst wird das 3-Freiheitsgrade Kinematikmodell und das Konzept von Lyapunov Stabilität dynamischer Systeme eingeführt. Anschließend beschäftigt sich diese Arbeit mit der Vorstellung von LOS und ILOS, 2 gängigen Algorithmen zur Pfadverfolgung, welche auch bezüglich ihres Verhaltens bei Strömung untersucht werden. Des Weiteren wird ein bestehender Stabilitätsbeweis für LOS mitgeliefert. Daraufhin wird ein Algorithmus zur Hindernisvermeidung, sowie ein zugehöriger Stabilitätsbeweis vorgestellt. Anschließend wird ein hybrider Algorithmus entwickelt, welcher sowohl Pfadverfolgung, als auch Hindernisvermeidung gewährleisten kann, für welchen wir mithilfe der vorangegangenen Resultate auch Sicherheitsgarantien beweisen konnten. Dieser Algorithmus wird dann mithilfe von Matlab implementiert, und in verschiedenen simulierten Szenarien werden bestehende und gelöste Probleme des Algorithmus aufgezeigt. Schlussendlich wird dadurch ein Algorithmus für autonome Schiffahrt unter vereinfachten Bedingungen entwickelt.
An algebraic framework for time-varying linear systems. - Ilmenau. - 22 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Diese Arbeit untersucht lineare differentiell-algebraische Gleichungen mit zeitabhängigen Koeffizienten. Lösungen sind Vektoren von glatten reellen Funktionen, definiert auf den reellen Zahlen, mit Ausnahme einer diskreten Teilmenge. Zwei Lösungen werden identifiziert, wenn sie fast überall bezüglich des Lebesgue-Maßes übereinstimmen. Wir zeigen in der vorliegenden Arbeit, dass dieser Ansatz die notwendige algebraische Struktur für unsere Untersuchungen liefert und die Fehler eines früheren Ansatzes korrigiert. Darüber hinaus deckt dieser Ansatz den Spezialfall von reellen meromorphen Koeffizienten ab, in welchem die Teichmüller-Nakayama-Form zur Vereinfachung der Systemanalyse verwendet werden kann. Des Weiteren beschäftigen wir uns mit der Steuerbarkeit des zeitabhängigen Systems, was zum Hauptergebnis der Arbeit führt – einer algebraischen Charakterisierung von Steuerbarkeit. Dieser Satz ist bekannt, wir liefern jedoch einen überarbeiteten Beweis in unserem Framework.
Die skalare und multikriterielle Rundungseigenschaft. - Ilmenau. - 35 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Die vorliegende Arbeit beschäftigt sich mit der Rundungseigenschaft, welche eine Methode zum Lösen ganzzahliger skalarwertiger Optimierungsprobleme liefert. Diese Arbeit verwendet dabei vorrangig den Levelmengenansatz von Hübner, 2013, um für verschiedene Klassen von Optimierungsproblemen diese Eigenschaft nachzuweisen. Weiterhin werden diese Ideen teilweise auf multikriterielle Optimierungsprobleme ausgeweitet.
Charakterisierung der Baumweite eines Graphen durch Graphsuche. - Ilmenau. - 21 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
Das Konzept der Baumweite ist eines der weniger intuitiven Konzepte in der Graphentheorie. Deswegen ist es durchaus nützlich, sich alternative Charakterisierungen dieser Größe anzusehen. Zu diesem Zweck soll das Suchen auf Graphen mit bestimmten Voraussetzungen dienen. Ziel dieser Arbeit ist es, einen kurzen Überblick über die Geschichte der Graphsuche zu geben, die Voraussetzungen für die Graphsuche zu definieren, so dass ein Zusammenhang zur Baumweite hergestellt wird, und einen Beweis für diesen Zusammenhang darzustellen.
Das S-Lemma und die Konvexität der Bildmenge zweier homogener quadratischer Funktionen. - Ilmenau. - 26 Seiten
Technische Universität Ilmenau, Bachelorarbeit 2023
In dieser Arbeit beschäftigen wir uns mit dem S-Lemma und dessen Beweis von Yakubovich, welcher die Konvexität der Bildmenge zweier homogener quadratischer Funktionen ausnutzt, dem Dines Theorem. Daneben betrachten wir in Trust-Region Subproblemen eine exemplarische Anwendung des S-Lemmas. Außerdem werden wir weitere Konvexitätsaussagen, als Verallgemeinerungen des Dines Theorems, sehen und damit einhergehend auch Verallgemeinerungen des S-Lemmas erhalten.
On the Hamiltonicity of 5-regular Line Graphs with Additional Properties. - Ilmenau. - 26 Seiten
Technische Universität Ilmenau, Masterarbeit 2023
In der vorliegenden Masterarbeit wird eine Abschwächung einer Vermutung von Thomassen gezeigt. Thomassen hatte vermutet, dass 4-zusammenhängende Kantengraphen hamiltonsch sind - das ist, sie besitzen einen aufspannenden Kreis. Hier zeigen wir, dass, mit einer wesentlich einschränkenden Bedingung an Ecken des Grades 3 im Urbild des Kantengraphen, 5-reguläre, 4-zusammenhängende Kantengraphen hamiltonsch sind. Weiterhin gibt es eine Vermutung, die von L. Lovász im Jahr 1969 aufgestellt wurde. Diese besagt, dass - bis auf wenige Ausnahmen - alle vertex-transitiven Graphen hamiltonsch sind, wobei man einen Graphen vertex-transitiv nennt, wenn seine Automorphismengruppe transitiv auf den Ecken des Graphen wirkt. Durch Ausnutzen des obigen Resultates und nach Klassifikation der 5-regulären vertex-transitiven Kantengraphen können wir dann zeigen, dass vertex-transitive, 5-reguläre Kantengraphen, in deren Urbild Kreise der Länge 4 enthalten sind, hamiltonsch sind.Abschließend fokussieren wir uns auf ein Resultat von Jaeger, der 1979 eine sehr nützliche Äquivalenz zeigte, in der er die Kantenmengen, die innerhalbe eines gegebenen Graphen zu einem eulerschen Teilgraphen erweitert werden können, klassifizierte. Dies nutzen wir, um Resultate, die bereits nützlich dafür waren, Abschwächungen von Thomassens Vermutung zu zeigen, zu verschärfen.