Das Kefk Network Wiki befindet sich im Testbetrieb.
Liste numerischer Verfahren
Aus Kefk.
Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf.
Inhaltsverzeichnis |
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.
- Splitting-Verfahren: Klassische iterative Verfahren.
- Gauß-Seidel-Verfahren: Wird auch als Einzelschrittverfahren bezeichnet.
- Jacobi-Verfahren: Wird auch als Gesamtschrittverfahren bezeichnet.
- Richardson-Verfahren
- SOR-Verfahren
- SSOR-Verfahren
- Krylow-Unterraum-Verfahren: Moderne iterative Verfahren, die für große, dünnbesetzte Gleichungssysteme gedacht sind.
- 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 zu verbessern.
- ILU-Zerlegung: Ein wichtiges Vorkonditionierungsverfahren.
Nichtlineare Gleichungssysteme
- Bisektion: Ein sehr einfaches Verfahren, 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: Ein einfaches iteratives 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.
- 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.
- 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.
- Verfahren des steilsten Abstiegs: Ein langsames Verfahren zur Lösung des Minimierungsproblems.
- Bairstow-Verfahren: Ein spezielles Iterationsverfahren, um komplexe Nullstellen von Polynomen mittels reeller Operationen zu bestimmen.
- Weierstrass-(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-Extrapolation: Eine Technik zur Verbesserung von Newton-Cotes-Formeln.
- Mittelpunktsregel
- Trapezregel
- Simpsonregel
- 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ézier-Kurven.
Ausgleichsprobleme
- QR-Zerlegung: Geeignet für lineare Ausgleichsprobleme (auch Householder-Verfahren).
- Gauß-Newton-Verfahren: Ein iteratives Verfahren zur Lösung nichtlinearer Ausgleichsprobleme.
- Kurvenfitten: Allgemein Ermitteln von Parameterwerten durch Anpassung an Messkurven.
Optimierung
- Branch-and-Bound: Enumerationsverfahren zur Lösung ganzzahliger Optimierungsprobleme.
- Schnittebenenverfahren, Branch-and-Cut: Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme.
- Simplex-Verfahren: Ein direktes Verfahren der linearen Programmierung.
- 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
- 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.
- 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.
Numerik partieller Differentialgleichungen
- Finite-Elemente-Methode: Ein modernes, flexibles Verfahren zur Lösung vor allem elliptischer partieller Differentialgleichungen.
- Finite-Volumen-Verfahren: Ein modernes Verfahren zur Lösung von Erhaltungsgleichungen.
- Finite-Differenzen-Verfahren: 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 neuartiges Verfahren, das zur Diskretisierung Polynome sehr hoher Ordnung benutzt.
- Level-Set-Methode: Eine moderne Methode zur Verfolgung von bewegten Rändern.
- Leapfrog-Verfahren: Abgewandeltes Eulerverfahren mit Termen nur zweiter Ordnung (z.B. für Planetenbewegung), bei dem die Zeitschritte für Ort und Geschwindigkeit um die halbe Integrationschrittweite versetzt sind. Dadurch wird höhere Genauigkeit und Zeitsymmetrie erreicht.
- 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.
Berechnung von Eigenwerten
- QR-Algorithmus: Berechnung aller Eigenwerte, allerdings mit hohen Kosten verbunden.
- LR-Algorithmus: Auch Treppeniteration genannt, ein dem QR-Verfahren vergleichbarer aber weniger stabiler Algorithmus.
- 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 eines Shifts.
- 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.
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
- 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 Funktion in Mikrocomputern und digitalen Schaltungen implementieren lassen.
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Liste_numerischer_Verfahren, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
