Liste numerischer Verfahren

Überblick über numerische Verfahren

Numerische Verfahren sind Methoden der numerischen Mathematik. Sie liefern Näherungen für mathematische Probleme, die sich oft nicht oder nicht praktisch exakt berechnen lassen. Die Liste ordnet solche Methoden nach ihren Anwendungsgebieten: Gleichungssysteme, Integration, Approximation, Optimierung, gewöhnliche und partielle Differentialgleichungen sowie Eigenwerte. Wichtige Unterscheidungen sind direkte Verfahren, die eine Lösung in endlich vielen Rechenschritten anstreben, und iterative Verfahren, die eine Näherung schrittweise verbessern.

Lineare und nichtlineare Gleichungssysteme

Für lineare Gleichungssysteme sind das Gaußsche Eliminationsverfahren und die LR-Zerlegung klassische direkte Verfahren; bei großen Matrizen sind sie allerdings aufwendig. Die Cholesky-Zerlegung nutzt bei symmetrischen positiv definiten Matrizen eine symmetrische Zerlegung und benötigt etwa den halben Aufwand. Die QR-Zerlegung hat mindestens die doppelte Laufzeit des Gauß-Verfahrens, besitzt aber bessere Stabilitätseigenschaften; mit Householdertransformationen eignet sie sich besonders für lineare Ausgleichsprobleme.

Zu den klassischen iterativen Splitting-Verfahren gehören Gauß-Seidel als Einzelschrittverfahren, Jacobi als Gesamtschrittverfahren, Richardson, Tschebyschow-Iteration, SOR und SSOR. Iterative Refinement verbessert ein Ergebnis eines direkten Verfahrens. Krylow-Unterraum-Verfahren sind moderne iterative Verfahren für große, dünnbesetzte Systeme; für symmetrisch positiv definite Probleme ist das Verfahren der konjugierten Gradienten wichtig. Mehrgitterverfahren haben lineare Komplexität und sind speziell für Systeme aus partiellen Differentialgleichungen bestimmt. Vorkonditionierung verbessert die Kondition einer Matrix in Krylow-Unterraum-Verfahren; die ILU-Zerlegung ist ein wichtiges Vorkonditionierungsverfahren.

Nichtlineare Gleichungssysteme betreffen insbesondere die Suche nach Nullstellen. Die Bisektion halbiert wiederholt ein Intervall, konvergiert linear und halbiert den Fehler ungefähr je Iterationsschritt. Die Bisektion-Exklusion schränkt für Polynome alle Nullstellen innerhalb einer Startregion beliebig genau ein. Regula falsi und Sekantenverfahren sind einfache iterative Verfahren für eindimensionale Funktionen. Fixpunktverfahren suchen auch mehrdimensional Fixpunkte und konvergieren linear.

Das Newton-Verfahren findet Nullstellen differenzierbarer Funktionen quadratisch konvergent. Mehrdimensional muss pro Schritt ein lineares Gleichungssystem gelöst werden. Quasi-Newton-Verfahren verwenden lediglich eine Näherung der Ableitung. Halley- und Euler-Tschebyschow-Verfahren sind kubisch konvergent für zweimal differenzierbare Funktionen; mehrdimensional benötigen sie je Schritt zwei lineare Gleichungssysteme. Weitere Verfahren sind Gauß-Newton für nichtlineare Ausgleichsprobleme, Levenberg-Marquardt als Verbindung von Gauß-Newton und Trust-Region-Strategie sowie Homotopieverfahren, die ein einfach lösbares Problem stetig mit dem vorgegebenen Problem verbinden. Bairstow bestimmt komplexe Polynomnullstellen mit reellen Operationen; Weierstraß-(Dochev-Durand-Kerner-Presic)-, Aberth-Ehrlich- und Trennkreisverfahren bestimmen alle komplexen Nullstellen simultan.

Integration, Approximation und Optimierung

Numerische Integration, auch Quadratur, nähert Integrale an. Newton-Cotes-Formeln beruhen auf Polynominterpolation; dazu zählen Mittelpunktsregel, Trapezregel sowie Simpsonregel beziehungsweise Keplersche Fassregel. Gauß-Quadratur besitzt eine optimale Konvergenzordnung. Romberg-Integration verbessert Newton-Cotes-Formeln. Weitere Verfahren sind Monte-Carlo-Simulation und Lie-Integration, die auf einem verallgemeinerten Differentialoperator aufbaut.

Bei der Interpolation wird eine Funktion durch eine passende Näherungsfunktion beschrieben: Polynominterpolation verwendet Polynome, Spline-Interpolation stückweise stetige Polynome und trigonometrische Interpolation trigonometrische Polynome. Der Remez-Algorithmus findet die optimale Approximation bezüglich der Supremumsnorm. Der De-Casteljau-Algorithmus berechnet Bézierkurven.

Optimierungsverfahren suchen beispielsweise ein Minimum oder lösen ganzzahlige beziehungsweise lineare Optimierungsprobleme. Gradientenverfahren dienen der Optimierung ohne Nebenbedingungen; als Verfahren zur Lösung eines Minimierungsproblems werden sie als langsam bezeichnet. BFGS löst nichtlineare Optimierungsprobleme. Branch-and-Bound ist ein Enumerationsverfahren für ganzzahlige Optimierung; Schnittebenenverfahren und Branch-and-Cut sind für ganzzahlige lineare Optimierung vorgesehen. Active-Set-Methoden behandeln Nebenbedingungen. Pivotverfahren tauschen Basen in der linearen Optimierung aus; das Simplex-Verfahren ist eine Familie solcher Verfahren. Downhill-Simplex arbeitet ableitungslos bei nichtlinearer Optimierung. Penalty-Verfahren führen Probleme mit Nebenbedingungen auf solche ohne Nebenbedingungen zurück; Barriereverfahren sind deren innere Variante. Innere-Punkte-Verfahren sind die lineare Form logarithmischer Barriereverfahren. Simulierte Abkühlung ist heuristisch für Probleme hoher Komplexität.

Gewöhnliche Differentialgleichungen

Verfahren für gewöhnliche Differentialgleichungen berechnen Näherungen entlang von Zeitschritten. Allgemeine lineare Verfahren erlauben eine einheitliche Darstellung der meisten genannten Verfahren. Das Eulersche Polygonzugverfahren ist das einfachste Lösungsverfahren und ein 1-stufiges Einschrittverfahren.

Einschrittverfahren verwenden nur Informationen aus dem aktuellen Zeitschritt für die nächste Näherung. Dazu gehört die Familie der Runge-Kutta-Verfahren einschließlich des klassischen Runge-Kutta-Verfahrens. Mehrschrittverfahren nutzen Informationen aus den letzten Zeitschritten; nötige Startwerte werden beispielsweise mit einem Einschrittverfahren bestimmt. BDF-Verfahren sind spezielle Mehrschrittverfahren für steife Anfangswertprobleme. Adams-Bashforth-Verfahren sind explizite, Adams-Moulton-Verfahren implizite Mehrschrittverfahren.

Prädiktor-Korrektor-Verfahren kombinieren ein explizites und ein implizites Mehrschrittverfahren gleicher Fehlerordnung: Der Prädiktor erzeugt eine Näherung, der Korrektor verbessert sie. Rosenbrock-Wanner-Verfahren sind linear-implizite Einschrittverfahren für steife Anfangswertprobleme. Das Newton-Störmer-Verlet-Leapfrog-Verfahren ist ein symplektisches Integrationsverfahren für klassische Dynamik, etwa Planetenbewegung bis Moleküldynamik; es erhält dynamische Invarianten besser.

Partielle Differentialgleichungen

Zur Numerik partieller Differentialgleichungen gehören Diskretisierungsverfahren, die ein kontinuierliches Problem durch endlich viele Rechenwerte ersetzen. Die Finite-Elemente-Methode ist ein modernes, flexibles Verfahren vor allem für elliptische partielle Differentialgleichungen. Die Diskontinuierliche Galerkin-Methode ist ebenfalls vor allem dafür vorgesehen und extrem vielseitig. Die Finite-Differenzen-Methode ist ein klassisches Verfahren für beliebige partielle Differentialgleichungen; die orthogonale Kollokation ist ebenfalls dafür geeignet und wird oft mit ihr kombiniert.

Finite-Volumen-Verfahren lösen Erhaltungsgleichungen. Bei der Randelementmethode für elliptische PDGLen wird nur der Gebietsrand statt des gesamten Gebiets diskretisiert. Spektralmethoden verwenden Polynome sehr hoher Ordnung. Die Level-Set-Methode verfolgt bewegte Ränder. Die Finite-Punkte-Methode arbeitet nur mit Punkten, ohne Elemente; die Finite-Streifen-Methode ist eine vereinfachte Form der FEM mit Streifen als Elementen. Die Material-Point-Methode nähert verschiedene, insbesondere stark verformende Materialien durch Punkte und ein dynamisches Gitter an.

Eigenwerte und weitere Grundverfahren

Eigenwertverfahren bestimmen Eigenwerte und teilweise Eigenvektoren einer Matrix. Der QR-Algorithmus berechnet alle Eigenwerte, ist aber kostenintensiv. Der LR-Algorithmus, auch Treppeniteration, ist ein weniger zuverlässiger Vorläufer. Die Potenzmethode bestimmt den betragsgrößten Eigenwert; die Unterraumiteration erweitert sie mehrdimensional und bestimmt mehrere betragsgrößte Eigenwerte gleichzeitig. Inverse Iteration berechnet Eigenwerte nahe einem Shift schnell, und die Rayleigh-Quotienten-Iteration ist eine besonders schnell konvergierende Variante davon. Lanczos-, Arnoldi- und Jacobi-Davidson-Verfahren berechnen einige Eigenwerte großer dünnbesetzter Matrizen. Das Jacobi-Verfahren berechnet alle Eigenwerte und Eigenvektoren kleiner symmetrischer Matrizen. Die Folded Spectrum Method (Spektrumsfaltung) bestimmt einen Eigenwert und Eigenvektor nahe einem Shift aus der Mitte des Spektrums.

Weitere Verfahren sind Schnelle Fourier-Transformation (FFT), Wavelet-Transformation, Multipol-Verfahren und Gram-Schmidtsches Orthogonalisierungsverfahren. Regularisierungsverfahren lösen schlecht gestellte Probleme; genannt wird besonders die klassische Tikhonov-Phillips-Regularisierung. Das Heron-Verfahren berechnet Wurzeln, das Horner-Schema Polynomwerte und der Bresenham-Algorithmus Linien oder Kreise in der Computergrafik. Extrapolation, Summationsverfahren und Folgentransformationen behandeln divergente Folgen und Reihen; Konvergenzbeschleunigung betrifft konvergente Folgen und Reihen reeller oder komplexer Zahlen, Vektoren und Matrizen. CORDIC ist ein effizienter iterativer Algorithmus zur Implementierung vieler transzendenter Funktionen in Mikrocomputern und digitalen Schaltungen.