Algorithmik kontinuierlicher Systeme - Cheatsheet

Grundlagen der Numerik

Definition:

Basiswissen zur numerischen Lösung mathematischer Probleme; Fokus auf Algorithmen zur Lösungsfindung bei Differentialgleichungen, Eigenwertproblemen, Interpolation und Integration.

Details:

• Approximation mathematischer Funktionen
• Lösen von Gleichungssystemen (lineare und nichtlineare)
• Fehleranalyse und -schätzung
• Stabilität und Konvergenz von Algorithmen
• Numerische Integration und Differentiation
• Anwendung finiter Differenzenmethoden
• Eigenwerte und Eigenvektoren
• Interpolation und Kurvenanpassung
• Auswertung der Leistung und Effizienz von Algorithmen

Iterative Verfahren

Definition:

Iterative Verfahren sind Algorithmen, die sukzessive Approximationen nutzen, um schrittweise eine Lösung für ein Problem zu finden. Häufig eingesetzt zur Lösung von linearen und nichtlinearen Gleichungen sowie Optimierungsproblemen.

Details:

• Anfangswert (Initialisierung) notwendig.
• Verfahren konvergiert, wenn die Folge der Approximationen gegen einen Wert strebt.
• Konvergenzgeschwindigkeit: linear, sublinear, oder superlinear.
• Zwei Haupttypen: stationäre (Jacobi, Gauss-Seidel) und nicht-stationäre Verfahren (Gradientenverfahren, Newton-Verfahren).
• Abbruchkriterium, wenn geforderte Genauigkeit oder maximale Iterationsanzahl erreicht.

Numerische Lösungen von ODEs und PDEs

Definition:

Numerische Methoden, um Differentialgleichungen (ODEs) und partielle Differentialgleichungen (PDEs) zu lösen.

Details:

• ODEs: Methoden wie Euler-Verfahren, Runge-Kutta-Verfahren
• PDEs: Finite-Differenzen-Methoden, Finite-Elemente-Methoden
• Fehleranalyse und Konvergenz
• Stabilität der numerischen Lösungen
• Diskretisierung des Zeit- und Raumdomänen
• Implementierung in Programmiersprachen wie C++ oder Python

Gittergenerierung und Interpolation

Definition:

Gittergenerierung: Erstellen eines Netzes/Gitters zur Diskretisierung kontinuierlicher Systeme. Interpolation: Verfahren zur Schätzung von Werten innerhalb eines Datensatzes basierend auf bekannten Werten.

Details:

• Delaunay-Triangulation: Erzeugt Gitternetz aus Dreiecken zur Flächenabdeckung.
• Uniformes Gitter: Gleichmäßige Verteilung der Gitternpunkte.
• Adaptives Gitter: Verdichtung bei höheren Fehlern oder Detailreichtum.
• Lineare/Nichtlineare Interpolation: Berechnung von Zwischenwerten; linear: Zwischenpunkte auf gerader Linie, nichtlinear: Splines, Polynom-Interpolation.
• Bilineare Interpolation: Erweiterung auf zwei Dimensionsachsen.
• Fehlerabschätzung: Genauigkeit der Interpolation bewerten.

Fehlerschätzung und Konvergenzanalyse

Definition:

Abschätzung des Fehlers und Überprüfung der Konvergenz bei numerischen Algorithmen, um die Genauigkeit und Zuverlässigkeit zu gewährleisten.

Details:

• Fehlerschätzung: Differenz zwischen approximierter Lösung und exakter Lösung.
• Absolute Fehler: \(|x_{\text{approx}} - x_{\text{exakt}}|\).
• Relative Fehler: \(|\frac{x_{\text{approx}} - x_{\text{exakt}}}{x_{\text{exakt}}}|\).
• Konvergenzanalyse: Untersuchung, ob eine numerische Methode gegen die exakte Lösung konvergiert, wenn die Anzahl der Iterationen oder der Grad der Diskretisierung erhöht wird.
• Konvergenzrate: Beschreibt, wie schnell die approximierte Lösung der exakten Lösung näher kommt, oft in der Form \(O(n^{-p})\).

Grundlagen der Digitalisierung

Definition:

Grundlagen der Umwandlung von analogen Signalen in digitale Form zum Zwecke der Verarbeitung, Speicherung oder Übertragung. Wesentliche Konzepte beinhalten Abtastung, Quantisierung und Codierung.

Details:

• Abtastung (Sampling): Konvertierung eines kontinuierlichen Signals in diskrete Werte.
• Quantisierung: Zuordnung der abgetasteten Werte zu einer begrenzten Anzahl von Pegelwerten.
• Nyquist-Theorem: Stichprobenrate muss mindestens das Doppelte der höchsten Frequenz des Signals betragen.
• Alias-Effekt: Verzerrung durch zu niedrige Abtastfrequenz.
• Codierung: Konvertierung der quantisierten Werte in ein digitales Bitmuster.
• Gängigste Abtastfrequenz für Audio: 44,1 kHz (CD-Qualität).
• Formel für Sampling: \[ x[n] = x(nT) \] wobei \( T \) die Abtastperiode ist.

Stabilitäts- und Konsistenzanalyse

Definition:

Stabilität: Verhalten numerischer Verfahren bei kleinen Störungen. Konsistenz: Annäherung eines numerischen Verfahrens an die exakte Lösung bei feiner werdender Diskretisierung.

Details:

• Stabilität: Ein numerisches Verfahren ist stabil, wenn kleine Fehler im Verlauf der Berechnungen nicht zu großen Abweichungen führen.
• Formale Beschreibung: Ein Verfahren ist stabil, wenn für jede Folge von Störungen \ \( \tau_n \ ) gilt, dass \ \( e^{tA} \tau_n \ ) beschränkt bleibt.
• Konsistenz: Ein Verfahren ist konsistent, wenn die Diskretisierungsfehler gegen Null gehen, wenn die Schrittweite gegen Null geht.
• Formale Beschreibung: Ein Verfahren ist konsistent, wenn der lokale Diskretisierungsfehler \ \( \tau_n \rightarrow 0 \ ) für \ \( h \rightarrow 0 \ ) geht.
• Von-Neumann-Kriterium zur Stabilität: Für ein lineares Verfahren ist stabil, wenn der Spektralradius der Iterationsmatrix kleiner oder gleich 1 ist.
• Zusammenhang: Ein konsistentes und stabiles Verfahren ist nach dem Lax-Äquivalenzsatz konvergent.

Fourier Transformation und Filtertechniken

Definition:

Mathematische Methode zur Analyse von Signalen in Frequenzkomponenten und Anwendung in der Signalverarbeitung.

Details:

• Fourier-Transformation (FT): Wandelt zeit- oder raumbasierte Daten in ihre Frequenzkomponenten um.
• Formel: \(\hat{f}(\xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi i \xi x} \,dx\)
• Inverse Fourier-Transformation (IFT): Rücktransformation von Frequenz- auf Zeit-/Raumdomäne.
• Formel: \(f(x) = \int_{-\infty}^{+\infty} \hat{f}(\xi) e^{2\pi i \xi x} \,d\xi\)
• Filtertechniken: Dienen zur Beeinflussung bestimmter Frequenzanteile (z.B. Tiefpass, Hochpass, Bandpass).
• Beispiele:
  • Ideal Low-Pass Filter
  • High-Pass Filter
• Filterung oft durch Multiplikation im Frequenzbereich.