Ingenieurmathematik (Master)

Veranstaltungsnummern 734001003 (Vorlesung) und 734001004 (Übungen), Modulbeschreibung M01

Vorlesung: Benedikt Wirth, Übungen: Orestis Vantzos

Termine

Vorlesung	Dienstag, 8:15 - 9:45 Uhr	Hörsaal XVII, Nußallee 17
	Mittwoch, 10:05 - 11:35 Uhr	Hörsaal XVII, Nußallee 17
Übung	Mittwoch, 12:00 - 14:00 Uhr (14tägig)	CIP-Pool, Nußallee 17

Voraussichtliche Übungstermine

13.04.2011

20.04.2011

04.05.2011

24.05.2011 (13:30)

08.06.2011

22.06.2011

06.07.2011

Skript

Skript (bis auf letztes Thema)

Handschriftliche Notizen zu Eikonalgleichung und Viskositätslösungen

13.04.2010, Programmieraufgabe I: Eindimensionale Datenfilterung

Implementieren Sie das in der Vorlesung beschriebene Finite-Differenzen-Verfahren zur Datenglättung in MATLAB. Experimentieren Sie mit dem Parameter β.

Wenn Sie die Werte aus der Datei filter1d.csv mittels

[x,f] = textread('filter1d.csv','%f,%f');

verwenden (die Werte sind hier bereits auf einem äquidistanten Gitter gegeben) und β=10^-6 wählen, sollten Sie den Graphen filter1d.pdf erhalten.

Beispiellösung: filter1d.m.

20.04.2010, Programmieraufgabe II: Bildglättung

Implementieren Sie das in der Vorlesung beschriebene Finite-Differenzen-Verfahren zur 2D-Bildglättung in MATLAB. Überlegen Sie sich hierzu eine Nummerierung der Unbekannten und stellen Sie die Matrizen für den Differentialoperator auf.

Als Eingabe verwenden Sie das Bild filter2d.pgm mittels

f = imread('filter2d.pgm');

Wenn Sie &beta=10^-4 wählen, sollten Sie das Bild filter2d_result.pgm erhalten.

Beispiellösung: filter2d.m.

04.05.2010, Programmieraufgabe III: Bildglättung 2

Implementieren Sie das TV-L2-Verfahren und wenden Sie dies auf das Bild aus Aufgabe II sowie auf das Testbild an. Experimentieren Sie mit den Parametern. Beachten Sie auch die Hilfestellungen im Skript (Schema 1.29, Bemerkung 1.30, Bemerkung 1.31).

Beachten Sie auch die Hinweise zu dieser Aufgabe, wobei Sie den letzten Punkt (den Vergleich der Ergebnisse für die beiden Energien) vorerst weglassen können.
Da der Algorithmus in MATLAB doch recht langsam ist, hier noch das Luftbild und das Testbild in kleinerer Auflösung.

Beispiele:
TV-L2 (kleines Luftbild), β=0.25, τ=0.2, Abbruch bei <10^-4, Dauer 10s, 2090 Iterationen.
TV-L2 (großes Luftbild), β=0.35, τ=0.2, Abbruch bei <10^-3, Dauer 58s, 661 Iterationen.

Beispiellösung: bvl2.m rof.m.

Zusatzaufgabe (Finite Elemente)

Berechnen Sie wie in der Vorlesung die Masse- und die Steifigkeitsmatrix für V_h = span{ sin(kπx) | k=1,2,3 } auf dem Intervall [0,1].

24.05.2010, Programmieraufgabe IV: Finite Elemente

Implemetieren Sie das in der Vorlesung besprochene 2D Finite-Elemente-Verfahren. Benutzen Sie zur Assemblierung das Verfahren mittels Referenzdreieck aus der Vorlesung (anstelle des im Skript abgedruckten Verfahrens). Wenden Sie es auf die Beispieldaten an, die auf einem Dreiecksgitter gegeben sind. Zum Laden der Daten verwenden und kommentieren Sie den Beispielcode.

Beachten Sie auch den Hinweis zur Assemblierung von Matrizen im Skript (Seite 52).

Beispiellösung: FE.m.

01.06.2010, Programmieraufgabe V: Elastizität (Steifigkeits- und Massematrix)

Leiten Sie (genau wie in der Vorlesung für das skalare Problem) die Steifigkeitsmatrix zu

her. Verwenden Sie als Basis für den Finite-Elemente-Raum

wobei

Tipp: Teilen sie die Matrix in vier Blöcke auf,
,
wobei (M^kl)_ij der Eintrag der Matrix für die Basisfunktionen ψ_ik und ψ_jl ist. Danach implementieren Sie die Steifigkeitsmatrix in Matlab.

22.06.2010, Programmieraufgabe VI: Elastizität

Implementieren Sie zusätzlich die Massematrix und schreiben Sie ein Programm, das für eine (in Form einer Triangulierung) vorgegebene Geometrie zu gegebenen Randwerten die Verschiebung berechnet und visualisiert.

Zu den Randwerten:

Dirichlet-Randwerte werden wie in den vorigen Programmen auch gehandhabt. Falls homogene Dirichlet-Randwerte vorkommen, listet die Datei name.DichichletBC die Nummern der betroffenen Knoten auf.
Nicht-Null-Neumann-Randwerte (Oberflächenkräfte) fließen in die rechte Seite durch das Integral über Γ₁ ein. Die Datei name.nonzeroNeumanBC enthält pro Kantenstück ein Zeile, in der die ersten beiden Spalten die Indizes des Start- und Endpunktespunktes enthalten und die dritte und vierte Spalte den x- und y-Wert von g.

Testen Sie den Löser an folgenden Beispielen:

Einem Block, an dem an beiden Seiten gezogen wird. Vergleiche Sie das Ergebnis mit der analytischen Lösung aus der Vorlesung.
Dateien: Gitter, Dirichlet-Randwerte, Neumann-Randwerte.
Bemerkung: Das Ergebnis aus der Vorlesung erhalten Sie nur für λ=0 und diesen Dirichlet-Randwerten. Können Sie erklären warum?
Einem Bauteil mit und ohne Querverstrebung. Untersuchen Sie verschiedene Werte für μ und λ und vergleichen Sie die Verschiebungen.
Dateien ohne Querverstrebung: Gitter, Dirichlet-Randwerte, Neumann-Randwerte.
Dateien mit Querverstrebung: Gitter, Dirichlet-Randwerte, Neumann-Randwerte.
Bemerkung: Versuchen Sie z.B. λ=1600 und μ=270.

In der Beispiellösung sind λ und μ zwar auf den einzelnen Dreiecken konstant, aber sie können von Dreieck zu Dreieck verschieden sein.

Zum Testen Ihrer Lösung können Sie dieses Programm einmal mit der Beispiellösung und einmal mit Ihrer Lösung laufen lassen.

06.07.2010, Programmieraufgabe VII: Elastizität, Dijkstra

Teil 1 (Elastizität, optional)

Ändern Sie Ihre Implementierung der Steifigkeitsmatrix so ab, dass auf jedem Element andere elastische Koeffizienten μ und λ benutzt werden können (d. h. inhomogene Koeffizienten). Erweitern Sie den Löser auf nicht-konstante Werte für die Volumenkraft f sowie für die Parameter λ und μ. Wenden Sie den Löser auf das Beispiel eines Hauses (hohe Steifigkeit, große Masse) auf einem Hügel (geringere Steifigkeit, niedrigere Masse bzw. Dichte) an. Die Volumenkraft f ist in der Datei name.f für jeden Knoten aufgelistet (Zeile=Nummer des Punktes). Die Parameter λ und μ sind in der Datei name.lm für jedes Dreieck gelistet (Zeile = Nummer des Dreiecks, erster Wert λ, zweiter Wert μ).
Dateien: Gitter, Dirichlet-Randwerte, Volumenkraft, Parameter λ und μ.

Teil 2 (Dijkstra)

Implementieren Sie den Dijkstra-Algorithmus. Gehen Sie in folgenden Schritten vor:

Die Knoten eines Graphen sind durchnumeriert von 1 bis n. Ein Graph wird abgespeichert als zwei Matrizen. Die ite Zeile der ersten Matrix enthält die Nummern aller Nachbarknoten von Knoten i (die Zeile wird mit Nullen aufgefüllt). Die ite Zeile der zweiten Matrix enthält die zugehörigen Abstände zu den Nachbarknoten. Als Beispielgraphen benutzen Sie die Dateien nodeNeighbours.txt, nodeDistances.txt, die Sie mit "dlmread('nodeNeighbours.txt',' ')" und "dlmread('nodeDistances.txt',' ')" einlesen können. Zeichnen Sie den zugehörigen Graphen auf!
Für eine effiziente Implementierung benötigen Sie eine Heap-Datenstruktur, d.h. eine Art Liste, zu der Sie mit wenig Rechenzeit einen Knoten des Graphen hinzufügen können und aus der Sie mit wenig Rechenzeit den Knoten mit kleinstem Wert aulesen können. Solche Datenstrukturen gibt es bereits fertig implementiert: Suchen Sie im Internet nach "matlab heap" (Sie finden dann hoffentlich eine File-Exchange Seite, auf der Code für einen Fibonacci Heap bereitgestellt wird). Laden Sie die entsprechenden Dateien herunter.
Der Heap kann bisher nur eine Liste von Zahlen verwalten, jedoch keine Liste von Graphknoten - der Code muss daher abgeändert werden. Die Datei "cFibHeapNode" enthält die Implementierung jedes Listeneintrags. Die Variable "key" ist dabei der Wert, nach dem die Liste sortiert wird. Fügen Sie eine Variable "graphNode" hinzu und ändern Sie die Initialisierungsmethode so ab, dass sie sowohl den Wert von "key" als auch den Wert von "graphNode" übergeben bekommt. Die Datei "cFibHeap" enthält die eigentliche Implementierung der Liste. Ändern Sie die Methode "insert" so ab, dass sie nicht nur den Wert von "key", sondern auch den von "graphNode" übergeben bekommt. Ändern Sie auch die Methoden "findMin" und "extractMin" so ab, dass sie nicht nur den Wert von "key", sondern auch den von "graphNode" ausgeben.
Nun können Sie den Dijkstra-Algorithmus implementieren. Eine leere Liste and Graphknoten erzeugen Sie mit "KnotenListe=cFibHeap", Knoten einfügen können Sie mit "cFibHeap.insert(...)", den Knoten mit dem niedrigsten Wert können Sie auslesen und entfernen mit "cFigHeap.extractMin".
Finden Sie mit dem Dijkstra-Algorithmus den kürzesten Weg von Knoten 1 zu Knoten 4. Dazu müssen Sie sich während des Algorithmus für jeden Knoten merken, über welchen Seiner Nachbarn der kürzeste Weg läuft.
Suchen Sie auf http://www.openstreetmap.org/ einen Kartenausschnitt, auf dem gerade noch Poppelsdorf und die gesamte Nußallee zu sehen sind. Exportieren Sie die Karte dann als "OpenStreetMap XML Data" (der "Export"-Knopf ist über der Karte).
Suchen Sie in der exportierten Datei folgende Straßen heraus: Sebastianstraße, Kekuléstraße, Karlrobert-Kreiten-Straße, Katzenburgweg, Carl-Troll-Straße, Meckenheimer Allee, Nußallee. Wenn Sie in der Datei beispielsweise nach "Katzenburgweg" suchen, gibt es eine Stelle der Form
```
 < way id="54135363" user="YvonneBentele" uid="94327" visible="true" version="2" changeset="5611031" timestamp="2010-08-27T20:12:37Z">
  < nd ref="682650250"/>
  < nd ref="682650269"/>
  < nd ref="682650283"/>
  < nd ref="682650294"/>
  < nd ref="682650250"/>
  < tag k="addr:city" v="Bonn"/>
  < tag k="addr:country" v="DE"/>
  < tag k="addr:housenumber" v="3"/>
  < tag k="addr:postcode" v="53115"/>
  < tag k="addr:street" v="Katzenburgweg"/>
  < tag k="building" v="yes"/>
  < tag k="source" v="Yahoo!Sat"/>
 < /way>
```
"way" steht hierbei dafür, dass eine Straße definiert wird; die Straße besteht aus den Knoten, die weiter oben mit "nd" gelistet sind (in dieser Reihenfolge). Achtung: Manchmal ist der letzte Knoten nur eine Wiederholung des ersten, und manchmal tauchen in der Datei mehrere Straßenabschnitte auf!
Erstellen Sie aus diesen Straßen einen Graphen (d.h. zwei Dateien wie im ersten Punkt). Jeder Knoten einer Straße (z.B. der Knoten oben mit der Nummer "682650283") soll auch ein Knoten im Graphen sein. Dabei sind zwei Knoten natürlich benachbart, wenn sie in der Straßendefinition aufeinanderfolgen. Die Abstände der Knoten zueinander können sie einfach berechnen: Jeder Knoten hat eine Nummer, z.B. "682650283". Wenn Sie in der Datei nach dieser Nummer suchen, finden Sie einen Eintrag
```
 < node id="682650283" lat="50.7251273" lon="7.0895145" user="EvanE" uid="184969" visible="true" version="2" changeset="4309912" timestamp="2010-04-03T06:10:35Z"/>
```
"lat" gibt den Breitengrad, "lon" den Längengrad an. Aus der Position der Knoten können sie leicht ihren Abstand berechnen. Plotten Sie außerdem in Matlab alle Knoten und Straßen (Sie erhalten eine kleine Stadtkarte).
Berechnen Sie den kürzesten Weg von Poppelsdorf zum CIP-Pool und geben Sie ihn auf Ihrer Karte aus.