Liste numerischer Verfahren

Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf.

Lineare Gleichungssysteme

• Gaußsches Eliminationsverfahren (bzw. LR-Zerlegung): Ein klassisches direktes Verfahren – für große Matrizen allerdings zu aufwändig.
• Cholesky-Zerlegung: Für symmetrische positiv definite Matrizen kann ähnlich wie die LR-Zerlegung eine symmetrische Zerlegung erstellt werden bei halbem Aufwand.
• QR-Zerlegung: Ebenfalls ein direktes Verfahren mit mindestens doppelter Laufzeit im Vergleich zum Gauß-Verfahren aber besseren Stabilitätseigenschaften. Umgesetzt mittels Householdertransformationen ist besonders für lineare Ausgleichsprobleme geeignet.
• Splitting-Verfahren: Klassische iterative Verfahren.
  • Gauß-Seidel-Verfahren: Wird auch als Einzelschrittverfahren bezeichnet.
  • Jacobi-Verfahren: Wird auch als Gesamtschrittverfahren bezeichnet.
  • Richardson-Verfahren
  • Tschebyschow-Iteration: ein Splitting-Verfahren mit zusätzlicher Beschleunigung
  • SOR-Verfahren
  • SSOR-Verfahren
• Iterative Refinement: Iterative Verbesserung eines direkten Verfahrens, Beziehung zur Grundidee der Krylow-Unterraum-Verfahren
• Krylow-Unterraum-Verfahren: Moderne iterative Verfahren, die für große, dünnbesetzte Gleichungssysteme gedacht sind. Wichtiger Spezialfall für symmetrisch positiv definite Probleme ist das Verfahren der konjugierten Gradienten.
• Mehrgitterverfahren: Ein modernes Verfahren mit linearer Komplexität speziell für Gleichungssysteme, die von partiellen Differentialgleichungen herrühren.
• Vorkonditionierung: Eine Technik, die Kondition einer Matrix in Krylow-Unterraum-Verfahren zu verbessern.
• ILU-Zerlegung: Ein wichtiges Vorkonditionierungsverfahren.

Nichtlineare Gleichungssysteme

• Bisektion: Ein sehr einfaches Verfahren zur Nullstellensuche, welches auf Halbierung eines Intervalls beruht. Konvergiert linear, der Fehler halbiert sich etwa in jedem Iterationsschritt.
• Bisektion-Exklusion: Spezielles Bisektionsverfahren für Polynome, welches alle Nullstellen innerhalb einer Startregion beliebig genau einschränkt.
• Regula falsi, Sekantenverfahren: Einfache iterative Verfahren zur Nullstellenbestimmung eindimensionaler Funktionen.
• Fixpunktverfahren: Eine Klasse linear konvergenter Verfahren zum Auffinden von Fixpunkten von Funktionen, auch im Mehrdimensionalen.
• Newton-Verfahren: Ein quadratisch konvergentes Verfahren zum Auffinden von Nullstellen differenzierbarer Funktionen. Auch im Mehrdimensionalen anwendbar, dann ist in jedem Iterationsschritt ein lineares Gleichungssystem zu lösen.
• Quasi-Newton-Verfahren: Eine Abwandlung des Newton-Verfahrens, bei dem lediglich eine Näherung der Ableitung genutzt wird.
• Halley-Verfahren, Euler-Tschebyschow-Verfahren: kubisch konvergente Verfahren zum Auffinden von Nullstellen zweimal differenzierbarer Funktionen. Auch im Mehrdimensionalen anwendbar. Dann sind in jedem Schritt zwei lineare Gleichungssysteme zu lösen.
• Gradientenverfahren: Ein langsames Verfahren zur Lösung eines Minimierungsproblems.
• Gauß-Newton-Verfahren: Ein lokal quadratisch konvergentes Verfahren zur Lösung nichtlinearer Ausgleichsprobleme.
• Levenberg-Marquardt-Algorithmus: Eine Verbindung des Gauß-Newton-Verfahren mit einer Trust-Region Strategie.
• Homotopieverfahren: Eine Methode, bei der ein frei wählbares Problem mit einfacher Lösung mit einem vorgegebenen Problem stetig verbunden wird. In vielen Fällen kann die Lösung des einfachen Problems zu einer Lösung des eigentlichen Problems verfolgt werden.
• Bairstow-Verfahren: Ein spezielles Iterationsverfahren, um komplexe Nullstellen von Polynomen mittels reeller Operationen zu bestimmen.
• Weierstraß-(Dochev-Durand-Kerner-Presic)-Verfahren, Aberth-Ehrlich-Verfahren, Trennkreisverfahren: Spezielle, aus dem Newton-Verfahren abgeleitete Methoden zur simultanen Bestimmung aller komplexen Nullstellen eines Polynoms.

Numerische Integration

• Newton-Cotes-Formeln: Einfache Quadraturformeln, die auf Polynominterpolation basieren.
• Gauß-Quadratur: Quadraturformeln mit optimaler Konvergenzordnung.
• Romberg-Integration: Eine Technik zur Verbesserung von Newton-Cotes-Formeln.
• Mittelpunktsregel
• Trapezregel
• Simpsonregel / Keplersche Fassregel
• Lie-Integration: Integrationsverfahren, das auf einem verallgemeinerten Differentialoperator aufbaut

Approximation und Interpolation

• Polynominterpolation: Interpolation durch Polynome.
• Spline-Interpolation: Interpolation durch stückweise stetige Polynome.
• Trigonometrische Interpolation: Interpolation durch trigonometrische Polynome.
• Remez-Algorithmus: Findet die optimale Approximation bezüglich der Supremumsnorm.
• De-Casteljau-Algorithmus: Der Algorithmus zur Berechnung von Bézierkurven.

Optimierung

• Bergsteigeralgorithmus: allgemeine Klasse von Optimierungsverfahren
• BFGS-Verfahren: Verfahren zur Lösung von nichtlinearen Optimierungsproblemen.
• Branch-and-Bound: Enumerationsverfahren zur Lösung ganzzahliger Optimierungsprobleme.
• Schnittebenenverfahren, Branch-and-Cut: Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme.
• Pivotverfahren: Basisaustauschverfahren der linearen Optimierung.
• Simplex-Verfahren: Familie von Pivotverfahren der linearen Optimierung.
• Downhill-Simplex-Verfahren: Ein ableitungsloses Verfahren der nichtlinearen Optimierung.
• Innere-Punkte-Verfahren: Ein iteratives Verfahren auch für nichtlineare Optimierungsprobleme.
• Logarithmisches Barriereverfahren: Ebenfalls ein iteratives Verfahren für nichtlineare Optimierungsprobleme.
• Simulierte Abkühlung: Ein heuristisches Verfahren für Optimierungsprobleme hoher Komplexität.

Numerik gewöhnlicher Differentialgleichungen

• Allgemeine lineare Verfahren: Diese Verfahrensklasse erlaubt eine einheitliche Darstellung der meisten Verfahren aus dieser Aufstellung hier
• Eulersches Polygonzugverfahren: Das einfachste Lösungsverfahren, ein 1-stufiges Einschrittverfahren.
• Einschrittverfahren: Verfahren, die nur Informationen des aktuellen Zeitschrittes benutzen, um daraus die nächste Näherung zu berechnen.
• Mehrschrittverfahren: Verfahren, die Informationen der letzten Zeitschritte nutzen. In Abhängigkeit von der Zahl der Zeitschritte sind die entsprechenden Startwerte z. B. mit einem Einschrittverfahren zu ermitteln.
• BDF-Verfahren: eine spezielle Familie von Mehrschrittverfahren für steife Anfangswertprobleme
• Adams-Bashforth-Verfahren: Familie von expliziten Mehrschrittverfahren.
• Adams-Moulton-Verfahren: Familie von impliziten Mehrschrittverfahren.
• Prädiktor-Korrektor-Verfahren: Die Kombination eines expliziten und eines impliziten Mehrschrittverfahrens gleicher Fehlerordnung. Das explizite Verfahren ergibt eine Näherung (den sogenannten Prädiktor), das implizite Verfahren verbessert den Näherungswert (der sogenannte Korrektor).
• Runge-Kutta-Verfahren: Familie von Einschrittverfahren inkl. dem klassischen Runge-Kutta-Verfahren.
• Rosenbrock-Wanner-Verfahren: Familie linear-impliziter Einschrittverfahren für steife Anfangswertprobleme
• Newton-Störmer-Verlet-Leapfrog-Verfahren: Beliebtes symplektisches Integrationsverfahren für Probleme der klassischen Dynamik, z. B. Planetenbewegung, bis Moleküldynamik, mit verbesserter Erhaltung dynamischer Invarianten.

Numerik partieller Differentialgleichungen

• Finite-Elemente-Methode: Ein modernes, flexibles Verfahren zur Lösung vor allem elliptischer partieller Differentialgleichungen.
• Diskontinuierliche Galerkin-Methode: Aktuelles, extrem vielseitiges Verfahren zur Lösung vor allem elliptischer partieller Differentialgleichungen.
• Finite-Volumen-Verfahren: Ein modernes Verfahren zur Lösung von Erhaltungsgleichungen.
• Finite-Differenzen-Methode: Ein klassisches Verfahren für beliebige partielle Differentialgleichungen.
• Randelementmethode: Ein Verfahren zur Lösung elliptischer PDGLen, wobei lediglich der Gebietsrand und nicht das Gebiet selbst (wie z. B. bei der FEM) zu diskretisieren ist.
• Spektralmethode: Ein Verfahren, das zur Diskretisierung Polynome sehr hoher Ordnung benutzt.
• Level-Set-Methode: Eine moderne Methode zur Verfolgung von bewegten Rändern.
• Finite-Punkte-Methode: ein neueres Berechnungsverfahren nur mit Punkten, aber ohne Elemente.
• Finite-Streifen-Methode: spezielle, vereinfachte Form der FEM mit Streifen als Elemente
• Orthogonale Kollokation: Verfahren für beliebige partielle Differentialgleichung, oft kombiniert mit dem Finite-Differenzen-Verfahren.
• Material-Point-Methode: Verfahren für verschiedene (insbesondere sich stark verformende) Materialien, welche durch Punkt und ein dynamisches Gitter angenähert werden

Berechnung von Eigenwerten

• QR-Algorithmus: Berechnung aller Eigenwerte, allerdings mit hohen Kosten verbunden.
• LR-Algorithmus: Auch Treppeniteration genannt, Vorläufer des QR-Verfahrens, aber weniger zuverlässig.
• Potenzmethode: Diese erlaubt die Berechnung des betragsgrößten Eigenwertes.
• Unterraumiteration: Diese ist eine mehrdimensionale Erweiterung der Potenzmethode und erlaubt die gleichzeitige Berechnung mehrerer der betragsgrößten Eigenwerte.
• Inverse Iteration: Diese erlaubt die schnelle Berechnung von Eigenwerten nahe einem Shift.
• Rayleigh-Quotienten-Iteration: Eine spezielle sehr schnell konvergierende Variante der Inversen Iteration mit Shift.
• Lanczos-Verfahren: Berechnung einiger Eigenwerte von großen dünnbesetzten Matrizen.
• Arnoldi-Verfahren: Berechnung einiger Eigenwerte von großen dünnbesetzten Matrizen.
• Jacobi-Verfahren: Berechnung aller Eigenwerte und Eigenvektoren von kleinen symmetrischen Matrizen.
• Jacobi-Davidson-Verfahren: Berechnung einiger Eigenwerte von großen dünnbesetzten Matrizen.
• Folded Spectrum Method (Spektrumsfaltung): Berechnung eines Eigenwertes und des zugehörigen Eigenvektors nahe einem Shift (aus der Mitte des Spektrums).

Sonstiges

• Schnelle Fourier-Transformation (FFT)
• Wavelet-Transformation
• Regularisierungsverfahren zur Lösung schlecht gestellter Probleme, insbesondere das klassische Tikhonov-Phillips Regularisierungsverfahren
• Multipol-Verfahren
• Gram-Schmidtsches Orthogonalisierungsverfahren
• Heron-Verfahren zur Wurzelberechnung
• Horner-Schema zur Polynomwertberechnung
• Bresenham-Algorithmus zur Linien- oder Kreisinterpolation in der Computergrafik
• Extrapolation
• Summationsverfahren und Folgentransformationen für divergente Folgen und Reihen
• Konvergenzbeschleunigung für konvergente Folgen und Reihen von reellen oder komplexen Zahlen, Vektoren und Matrizen
• CORDIC ist ein effizienter iterativer Algorithmus, mit dessen Hilfe sich viele transzendente Funktionen in Mikrocomputern und digitalen Schaltungen implementieren lassen.