Kurs:Numerik I/Diskretisierung des Vektorraumes

Einleitung

Als Diskretisierung bezeichnet man die Gewinnung einer diskreten Teilmenge aus einer kontinuierlichen Daten- oder Informationsmenge. Ziel der Diskretisierung ist die Behandlung kontinuierlicher Objekte (beispielsweise geschwungener Linien) in endlicher Zeit und mit endlichem Speicherplatz.

Wiki2Reveal

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Diskretisierung in der Numerik

Diskretisierung ist ein zentrales Konzept in der numerischen Mathematik und in der Kartografie, wo damit die Zerlegung räumlicher Kontinua wie Oberflächen etc. in kleine Abschnitte bzw. einzelne Punkte bezeichnet wird.

Gitter als Diskretisierung des Raumes

Ein Gitter in der Geometrie ist eine lückenlose und überlappungsfreie Partition eines Raumes durch eine Menge von Gitterzellen. Die Gitterzellen werden definiert durch eine Menge von Gitterpunkten, die untereinander durch eine Menge von Gitterlinien verbunden sind.

Gitter und Modellbildung

Gitter werden in der Naturwissenschaft und Technik zur Vermessung, Modellierung und für numerische Berechnungen verwendet (siehe Gittermodell).

Daten und Gitterpunkte

An Gitterpunkten können Daten vorliegen, die der Messung an den jeweiligen Koordinaten der Gitterpunkte darstellen (z.B. Schwermetallmessung im Boden an der Koordinate $(x,y)$ des Gitters.

Wege in Gittern

Auch Wege im Gitter laufen bei einer Diskretisierung dann über die Gitterpunkte und nicht mehr kontinuierlich im Raum.

Festlegung der Diskretisierung

Anhand ihrer Topologie und Geometrie werden Gitter in unterschiedliche Kategorien eingeteilt. Man unterscheidet grundlegend zwischen strukturierten und unstrukturierten Gittern.

Radiale Anordung der Gitterpunkte

Rechtwinklige Anordung der Gitterpunkte

Äquidistante Anordnung von Gitterpunkte

Kartesische Gitter

Erläuterung - strukturierte Gitter

Strukturierte Gitter (englisch structured grids) haben eine regelmäßige Topologie, jedoch nicht notwendigerweise eine regelmäßige Zellgeometrie. Bei strukturierten Gittern liegen die Zellen in einem regelmäßigen Raster vor, so dass sich die Zellen eindeutig durch ganzzahlige Zahlen indizieren lassen.

Eindimensionale Gitter - Liniengitter

Eindimensionale Gitter (Liniengitter) sind immer strukturiert, die Zellen lassen sich durch $i=1,...,N$ ( $N$ = Anzahl der Elemente) durchzählen. Für zweidimensionale Gitter ist ein Element durch die Indizes (i,j), bei dreidimensionalen durch die Indizes (i,j,k) eindeutig bestimmt.

Mehrdimensionale Gitter mit äquidistanter Unterteilung

Vorteil der Verwendung strukturierter Gitter gegenüber den nachfolgend beschriebenen unstrukturierten Gitter ist, dass sich durch diese eindeutige Indizierung Nachbarzellen ohne rechnerischen Aufwand ermitteln lassen. Strukturierte Gitter bestehen immer aus einem Elementtyp, der die Flächen zwischen den Gitterpunkten definiert.

Zweidimensionale Gitter mit äquidistanter Unterteilung

Im Zweidimensionalen werden meistens Rechteckelemente und nur selten Dreieckselemente verwendet. Dreidimensionale Gitter sind fast immer Hexaeder und nur manchmal Tetraeder.

Nachteile von Dreieckselementen für die Gitter

Die Verwendung von Dreieckselementen oder Tetraeder hat den Nachteil, dass sie den Raum nur schlecht ausfüllen und mehr Elemente notwendig sind. So hat ein Tetraeder mit einer Kantenlänge von 1 nur ein Raumvolumen von 1/6, während ein Kubus ein Volumen von 1 besitzt. Daher müssen etwa für die Strömungssimulation Tetraedergitter sehr viele Zellen verwenden, um eine ausreichende Auflösung zu erreichen.

Beispiele - strukturierter Gitter

Bei den strukturierten Gittern sind auch komplexe Strukturen möglich, bei denen das Gittersystem zwar regelmäßig ist, insgesamt aber gekrümmt oder an eine komplexe Geometrie angepasst. Ebenso werden Multiblockstrukturen verwendet, bei denen das Gitter aus mehreren strukturierten Blöcken unterschiedlicher Größe gebildet wird. Solche strukturierten Gitter lassen sich nur teilautomatisch erstellen.

Gekrümmte Gitter

Bei gekrümmten Gittern (englisch curvilinear grids) sind die Gitterlinien durch parametrisierte Kurven gegeben. Der Begriff ist jedoch eher ungebräuchlich. Man spricht dann einfach von strukturierten Gittern.

Rechtwinklige Gitter

Rechtwinklige Gitter (englisch rectilinear grids) unterteilen den Raum vollständig in achsenparallele Bereiche, die nicht gleich groß sein müssen. Im dreidimensionalen Raum entstehen so Quader verschiedener oder gleicher Größe.

Gleichmäßige Gitter

Ein gleichmäßiges Gitter (englisch regular grid) unterteilt den Raum vollständig in achsenparallele rechtwinklige Bereiche, wobei Kanten entlang einer Achse immer die gleiche Länge haben.

Kartesisches Gitter

Der einfachste Fall ist ein kartesisches Gitter (englisch cartesian grid), bei denen alle Kantenlängen gleich sind. Im zweidimensionalen Raum entsteht eine Quadratfläche und im dreidimensionalen ein Volumen aus Würfeln.

Unstrukturierte Gitter

Beispiel eines unstrukturierten Dreiecksgitters.

Unstrukturierte Gitter (englisch unstructured grids) haben keine festgelegte Topologie und keine gleichmäßige Gitterzellgeometrie. Unstrukturierte Gitter sind meist das Ergebnis eines Adaptionsprozesses. Bekannt sind auch Gitter aus komplexen Zellen, sogenannte Polyedergitter. Die Zellstruktur ähnelt hier der von Seifenschaum.

Vorteile unstrukturierter Gitter

Unstrukturierte Gitter sind sehr flexibel einzusetzen und können zudem einfach automatisch erzeugt werden.

Nachteile unstrukturierter Gitter

Die Datenverwaltung ist allerdings aufwändiger als bei strukturierten Gittern. Einerseits sind die Gitterpunkte nicht wie bei strukturierten Gittern in einem regelmäßigen Muster angeordnet, sondern müssen einzeln abgespeichert werden. Andererseits ist auch nicht von vorneherein klar, welches die Nachbarzellen zu einer bestimmten Gitterzelle sind.

Nachbarschaftsinformationen für unstrukturierte Gitter

Auch diese Nachbarschaftsinformationen müssen entweder bei der Gittererzeugung explizit abgespeichert werden oder aber zur Laufzeit aufwendig berechnet werden. Unstrukturierte Gitter benötigen daher im Allgemeinen ein Mehrfaches des Speicherbedarfs von strukturierten Gittern und verursachen in der Regel einen höheren Rechenaufwand.

Gittererzeugung

Als Gittererzeugung oder Meshing bezeichnet man eine Gruppe von Verfahren in der Computergrafik sowie der Simulation der physikalischen Eigenschaften von Festkörpern und Fluiden; bei diesen Verfahren wird eine gegebene Oberfläche oder ein gegebenes Raumvolumen durch eine Menge kleinerer, meist sehr einfacher Elemente angenähert (approximiert). Das so entstehende Gitter ist eine vereinfachte Beschreibung der Fläche oder des Körpers, welches dann z. B. für weitergehende Berechnungen genutzt werden kann, etwa mittels der Finite-Elemente-Methode (FEM).

Gittererzeugung im 2D- und 3D-Raum

Bei zweidimensionalen Flächen kommen bei der Gittererzeugung am häufigsten Dreiecks- oder Viereckselemente zur Anwendung, bei dreidimensionalen Körpern in der Regel Tetraeder oder Quader.

Triangulation

Die Erzeugung eines Gitters aus Dreieckselementen wird auch als Triangulierung (oder Triangulation) bezeichnet (genau wie das entstehende Dreiecksgitter), die Erzeugung eines Gitters aus Viereckselementen heißt auch Paving. Ist die Anzahl der Außenkanten einer Fläche fest vorgegeben und von ungerader Anzahl, so ist kein reines Vierecks-Paving möglich (es bleibt mindestens ein Element mit ungerader Eckenzahl, z. B. ein Dreieck).

Dreiecksgitter

Als Dreiecksgitter, Dreiecksnetz oder Triangulierung bezeichnet man in der Trigonometrie und elementaren Geometrie die Teilung einer Fläche in Dreiecke. Graphentheoretisch gesehen sind Dreiecksgitter vom Typus „ungerichteter Graphen ohne Mehrfachkanten“, deren Teilgraphen „Kreise mit drei Knoten“ (und entsprechend drei Kanten) sind. Die Verallgemeinerung von Dreiecksnetzen sind Polygonnetze.

Eckpunkte der Triangulation

Eine Triangulation einer Menge von Punkten $P$ in der Ebene bezeichnet eine Zerlegung der konvexen Hülle der Punktmenge in Dreiecke, wobei die Eckpunkte der Dreiecke genau die Punkte aus $P$ sind. Somit ist die Triangulation ein ebener Dreiecksgraph. Ist die Menge $P$ in konvexer Lage, so ist die Anzahl der möglichen Triangulationen genau die $n-2$ -te Catalan-Zahl, wobei $n$ die Anzahl der Punkte in $P$ bezeichnet.

Dreiecksgitter mit bestimmten optimierten Eigenschaften

Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaften zu berechnen. Zum Beispiel gibt es die Delaunay-Triangulation, welche den kleinsten Innenwinkel der Dreiecke maximiert, oder die Minimum-Weight-Triangulation, welche die Gesamtlänge aller Kanten minimiert.

Eine technische Anwendung von Dreiecksgittern in der Ebene und im Raum ist der Fachwerkträger.

Adaptive und nichtadaptive Gitter

Beispiel für die Anwendung eines adaptiven Dreiecksgitters zur Berechnung der Luftströmung um einen Flugzeugflügel.

Es wird weiterhin zwischen adaptiven und nichtadaptiven Diskretisierungen unterschieden.

Aufgabe für Studierende

Betrachten Sie die obige Triangulierung der Ebene für die Tragfläche. Was können Sie bzgl. des Flächeninhaltes der Dreicke beobachten? Erläutern Sie, warum die Triangulierung in bestimmten Regionen der Diskretisierung feiner ist.

Experiment - Feinheit der Diskretisierung

Machen Sie einen Test mit einer weiteren Person, bei dem die mit zwei Stiften zwei Druckpunkte auf dem Oberarm und zwei Druckpunkte auf dem Finger immer weiter aufeinander zubewegt werden. Die zweite Person muss mit geschlossenen Augen mitteilen, wann die beiden Berührpunkte in der Wahrnehmung zu einem Punkt zusammenfallen. Die Distanz zwischen den Punkten ist ein Maß dafür, wie genau sensorische Informationen auf der Haut getrennt werden können. Erläutern Sie, warum die Distanz zwischen den beiden Berührpunkte auf dem Oberarm weiter auseinanderliegen als auf der Fingerkuppe.

Nichtadaptive Gitter

Nichtadaptive Gitter haben überall im Volumen dieselbe Auflösung. Bei kleinen geometrischen Strukturen oder Bereichen mit starken Rundungen, spitzen Winkeln oder unterschiedlich definierten Materialparametern reicht ein grobes Gitternetz mit großen Gitterzellen nicht mehr aus, um auch solche Problembereiche hinreichend genau zu diskretisieren. Eine globale Verfeinerung des Gitternetzes ist zumeist aufgrund des damit verbundenen erhöhten Speicher- und Rechenzeitaufwands nicht sinnvoll.

Adaptive Gitter

Hier greift das Verfahren der adaptiven Gittererzeugung (englisch adaptive meshing), das dort, wo ansonsten große Ergebnis-Fehler zu erwarten wären, das Gitter feiner wählt. Dies geschieht entweder durch A-priori-Wissen über das betrachtete Problem, beispielsweise kleinere Elemente an Bauteiloberflächen oder an stark gekrümmten oder dünnen Stellen, oder durch Verfahren, die anhand gegebener Fehlerabschätzungen dynamisch dort verfeinern, wo der Fehler gerade groß ist.

Instationäre Probleme und adaptive Verfeinerung der Gitter

Letzteres ist insbesondere bei instationären Problemen wichtig, wenn also die problematischen Stellen im Laufe der Zeit ihre Position verändern.

Ein anderes Verfahren zur Diskretisierung kritischer Bereiche ist die Sub-Grid-Technologie.

Anwendungen

Technik

In der technischen Konstruktionslehre zur Modellierung gekrümmter Flächen, insbesondere im Zusammenhang mit CAD (CAD)
In der Robotik zur Bestimmung von Gelenkstellungen; hierbei ergeben sich hochdynamische Dreiecksnetze, die die Bewegung wiedergeben
Im Bauwesen für die Ausmessung eines Bauwerks mit Dreiecken: Hier waren Dreiecksnetze – vor allem rechtwinklige (3:4:5) und gleichseitige – schon in den Bauhütten in der Gotik üblich. Moderne Anwendungen sind CAM-Verfahren

Vermessungswesen

In der Geodäsie als Vermessungsnetz zur Punktbestimmung, siehe Triangulation (Geodäsie): Mittels des Netzes werden trigonometrischer Punkte (TP) als Vermessungspunkte eingemessen
Für die Photogrammetrie zur Erfassung der Daten – bei zeilenweisem Abtasten sind hier Vierecksnetze verbreiteter (die sich aber problemlos in Dreiecksnetze umwandeln lassen, um sie den spezifischen Algorithmen zugänglich zu machen)
In der GIS-Technologie und anderen satellitengestützten Messmethoden zur Umrechnung der meist linearen Messserien auf ein Erdmodell

Numerische Mathematik

Als Rechengitter bezeichnet man in der numerischen Mathematik eine diskrete Zerlegung des Raumes, auf dem eine partielle Differentialgleichung gelöst werden soll. Für eine zeitliche Diskretisierung ist der Begriff weniger gebräuchlich. Die Schnittpunkte zweier Gitterlinien werden als Knoten bezeichnet, die Zellen entweder als Zellen, in Finite-Elemente-Verfahren auch als Elemente und in Finite-Volumen-Verfahren als Volumen. Das Gitter kann räumlich feststehend sein oder sich mit der Zeit bewegen oder im Laufe der Rechnung adaptiert werden.

Randbedigungen für ein Gebiet

An den Rändern des Gebiets werden gegebenenfalls Randbedingungen vorgeschrieben. Zum Beispiel zyklische Randbedindungen.

Dimensionalität des Rechengitters

Rechengitter müssen nicht eindimensional sein. Bei dreidimensionalen Gittern werden schnell sehr große Zellenzahlen erreicht. Ein einfaches rechtwinkliges Gitter, das auf einer Kante nur 100 Zellen auflöst, besitzt in der dritten Dimension bereits 1 Million Zellen.

Rechenkapazität und Gitterzellenzahl

Auf einem Computer mit 2GB Hauptspeicher können je nach Softwaresystem heute ca. 1,5–5 Millionen Zellen berechnet werden. Die in akzeptabler Zeit berechenbare Zellenzahlen hängt aber auch von dem Berechnungsaufwand für die Gitterzellen ab. Werden größere Auflösungen benötigt, dann muss die Berechnung oft auf Großrechnern oder verteilt in Rechnernetzwerken erfolgen.

Diskretisierung im Kontext der Quantentheorie und Relativitätstheorie

Auf Max Planck geht die Idee (ca. 1900) zurück, dass die Energieabgabe eine heißen Körpers kann nur in Paketen erfolgen und zusammen mit den Ergebnissen von Einstein zum photoelektrischen Effekt 1905 aufgenommen werden. Die Entwicklung der Quantentheorie und der speziellen und allgemeinen Relativitätstheorie führt dazu, dass das Raum-Zeit-Kontinuum diskret sind, d.h. dass das in der makroskopischen Welt von uns wahrgenommene Kontinuum von Raum und Zeit auf der subatomaren Skala eigentlich diskret ist.

Makroskopische Welt

In der makroskopischen Welt kann man also durch ein Quadrupel $(x,y,z,t)\in \mathbb {R} ^{4}$ vereinfacht beschreiben, dass sich ein Objekt zu einem Zeitpunkt $t\in \mathbb {R}$ an einem Ort $(x,y,z)\in \mathbb {R} ^{3}$ befindet.

Subatomare Welt - Planck-Einheiten

Betrachtet man die subatomare Welt, so entstehen kleinste räumliche und zeitliche Einheiten für den kausalen Zusammenhang:

als kleinste Längeneinheit $\approx 1,6\cdot 10^{-35}\,m$ (Planck-Länge
als kleinste Zeiteinheit $\approx 5,4\cdot 10^{-44}\,sec$ (Planck-Zeit.

Aufgabe - Messungen

Analysieren Sie die Unterschiede bzgl. Messung in der klassischen Euklischen Geometrie und der Geometrie der Raumzeit im Kontext der speziellen Relativitätstheorie!

Beispiele

Geodätisches Vermessungsnetz
Gittererzeugung in der Computergraphik
Ebenes Dreiecksnetz für eine FEM-Modellierung
Adaptives ebenes Dreiecksnetz für eine FEM-Modellierung

Literatur

Michael Bender, Manfred Brill: Computergrafik – Ein anwendungsorientiertes Lehrbuch. 2. Auflage. Hanser, 2006, ISBN 3-446-40434-1.
Hansen und Johnson: The Visualization Handbook. Elsevier, Burlington 2005, ISBN 0-12-387582-X.

Siehe auch

Wiktionary

Wiktionary: Diskretisierung – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Diskretisierung%20des%20Vektorraumes
siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.

Wikipedia2Wikiversity

Diese Seite wurde auf Basis den folgenden Wikipedia-Quellen Diskretisierung und dem Artikel über Gitterin der Geometire erstellt:

Diskretisierung https://de.wikipedia.org/wiki/Diskretisierung - Datum: 27.5.2022
Gitter (Geometrie) https://de.wikipedia.org/wiki/Gitter%20(Geometrie) Datum: 27.5.2022

unter Verwendung des Wikipedia2Wikiversity-Konverter: https://niebert.github.com/Wikipedia2Wikiversity