knowledgr.de

Numerische Analyse

Neues Wissen!

Numerische Analyse ist die Studie von Algorithmen, die numerische Annäherung (im Vergleich mit allgemeinen symbolischen Manipulationen) für die Probleme der mathematischen Analyse (im Unterschied zu die getrennte Mathematik) verwenden.

Eine der frühsten mathematischen Schriften ist der babylonische Block v. Chr. 7289, der eine sexagesimal numerische Annäherung, die Länge der Diagonale in einem Einheitsquadrat gibt. Das Imstandesein, die Seiten eines Dreiecks (und folglich, das Imstandesein zu schätzen, Quadratwurzeln zu schätzen), sind zum Beispiel, in der Zimmerarbeit und dem Aufbau äußerst wichtig.

Numerische Analyse setzt diese lange Tradition von praktischen mathematischen Berechnungen fort. Viel wie die babylonische Annäherung sucht moderne numerische Analyse genaue Antworten nicht, weil genaue Antworten häufig unmöglich sind, in der Praxis vorzuherrschen. Statt dessen ist viel numerische Analyse mit dem Erreichen ungefähre Lösungen beschäftigt, während sie angemessene Grenzen auf Fehlern aufrechterhält.

Numerische Analyse findet natürlich Anwendungen in allen Feldern der Technik und der physischen Wissenschaften, aber im 21. Jahrhundert die Lebenswissenschaften und haben sogar die Künste Elemente der wissenschaftlichen Berechnung angenommen. Gewöhnliche Differenzialgleichungen erscheinen in der Bewegung von Gestirnen (Planeten, Sterne und Milchstraßen); Optimierung kommt im Mappe-Management vor; numerische geradlinige Algebra ist für die Datenanalyse wichtig; stochastische Differenzialgleichungen und Ketten von Markov sind im Simulieren von lebenden Zellen für die Medizin und Biologie notwendig.

Vor dem Advent von modernen Computern haben numerische Methoden häufig von Handinterpolation in großen gedruckten Tischen abgehangen. Seit der Mitte des 20. Jahrhunderts berechnen Computer die erforderlichen Funktionen stattdessen. Diese dieselben Interpolationsformeln setzen dennoch fort, als ein Teil der Softwarealgorithmen verwendet zu werden, um Differenzialgleichungen zu lösen.

Allgemeine Einführung

Die gesamte Absicht des Feldes der numerischen Analyse ist das Design und die Analyse von Techniken, um ungefähre, aber genaue Lösungen harter Probleme zu geben, von denen die Vielfalt durch das folgende angedeutet wird.

Fortgeschrittene numerische Methoden sind im Bilden numerischer ausführbarer Wettervorhersage notwendig.
Die Computerwissenschaft der Schussbahn eines Raumfahrzeugs verlangt die genaue numerische Lösung eines Systems von gewöhnlichen Differenzialgleichungen.
Autogesellschaften können die Unfall-Sicherheit ihrer Fahrzeuge durch das Verwenden von Computersimulationen von Autounfällen verbessern. Solche Simulationen bestehen im Wesentlichen daraus, teilweise Differenzialgleichungen numerisch zu lösen.
Hecke-Kapital (private Investitionsmittel) verwendet Werkzeuge von allen Feldern der numerischen Analyse, um den Wert von Lagern und Ableitungen genauer zu berechnen, als andere Marktteilnehmer.
Luftfahrtgesellschaften verwenden hoch entwickelte Optimierungsalgorithmen, um Karte-Preise, Flugzeug und Mannschaft-Anweisungen und Kraftstoffbedürfnisse zu entscheiden. Dieses Feld wird auch Operationsforschung genannt.
Versicherungsgesellschaften verwenden numerische Programme für die Aktuaranalyse.

Der Rest dieser Abteilung entwirft mehrere wichtige Themen der numerischen Analyse.

Geschichte

Das Feld der numerischen Analyse datiert die Erfindung von modernen Computern um viele Jahrhunderte zurück. Geradlinige Interpolation war bereits im Gebrauch vor mehr als 2000 Jahren. Viele große Mathematiker der Vergangenheit wurden durch die numerische Analyse völlig in Anspruch genommen, wie von den Namen von wichtigen Algorithmen wie die Methode von Newton, Interpolationspolynom von Lagrange, Beseitigung von Gaussian oder die Methode von Euler offensichtlich ist.

Um Berechnung mit der Hand zu erleichtern, wurden große Bücher mit Formeln und Tischen von Daten wie Interpolationspunkte und Funktionskoeffizienten erzeugt. Mit diesen Tischen, häufig berechnet zu 16 dezimalen Plätzen oder mehr für einige Funktionen, konnte man Werte nachschlagen, um in die Formeln gegeben einzustecken und sehr gute numerische Schätzungen von einigen Funktionen zu erreichen. Die kanonische Arbeit im Feld ist die NIST Veröffentlichung, die von Abramowitz und Stegun, 1000 - plus das Seitenbuch einer sehr hohen Zahl allgemein verwendeter Formeln und Funktionen und ihrer Werte an vielen Punkten editiert ist. Die Funktionswerte sind nicht mehr sehr nützlich, wenn ein Computer verfügbar ist, aber die große Auflistung von Formeln kann noch sehr handlich sein.

Die mechanische Rechenmaschine wurde auch als ein Werkzeug für die Handberechnung entwickelt. Diese Rechenmaschinen haben sich zu elektronischen Computern in den 1940er Jahren entwickelt, und es wurde dann gefunden, dass diese Computer auch zu Verwaltungszwecken nützlich waren. Aber die Erfindung des Computers hat auch das Feld der numerischen Analyse beeinflusst, da jetzt längere und mehr komplizierte Berechnungen getan werden konnten.

Direkte und wiederholende Methoden

Für die wiederholende Methode, wenden Sie das Bisektionsverfahren auf f (x) = 3x &minus an; 24. Die Anfangswerte sind = 0, b = 3, f (a) = −24, f (b) = 57.

Wir beschließen aus diesem Tisch, dass die Lösung zwischen 1.875 und 2.0625 ist. Der Algorithmus könnte jede Zahl in dieser Reihe mit einem Fehler weniger als 0.2 zurückgeben.

Discretization und numerische Integration

In einer zweistündigen Rasse haben wir die Geschwindigkeit des Autos in drei Momenten gemessen und sie im folgenden Tisch registriert.

Ein discretization würde sagen sollen, dass die Geschwindigkeit des Autos von 0:00 bis 0:40, dann von 0:40 bis 1:20 und schließlich von 1:20 bis 2:00 unveränderlich war. Zum Beispiel ist die in den ersten 40 Minuten gereiste Gesamtentfernung ungefähr (2/3. × 140 kph) = 93.3 km. Das würde uns erlauben einzuschätzen, dass die Gesamtentfernung als 93.3 km + 100 km + 120 km = 313.3 km gereist ist, der ein Beispiel der numerischen Integration (sieh unten) mit einer Summe von Riemann ist, weil Versetzung das Integral der Geschwindigkeit ist.

Schlecht aufgeworfenes Problem: Nehmen Sie die Funktion f (x) = 1 / (x − 1). Bemerken Sie dass f (1.1) = 10 und f (1.001) = 1000: Eine Änderung in x von weniger als 0.1 verwandelt sich in eine Änderung in f (x) von fast 1000. Wenn sie f (x) bewertet, ist Nähe x = 1 ein schlecht-bedingtes Problem.

Gut aufgestelltes Problem: Im Vergleich ist die Funktion dauernd und so bewertend sie wird mindestens für x gut aufgestellt Null nicht nah zu sein.

| }\

Direkte Methoden schätzen die Lösung eines Problems in einer begrenzten Zahl von Schritten. Diese Methoden würden die genaue Antwort geben, wenn sie in der unendlichen Präzisionsarithmetik durchgeführt würden. Beispiele schließen Beseitigung von Gaussian, der QR factorization Methode ein, um Systeme zu lösen

geradliniger Gleichungen]], und die Simplexmethode der geradlinigen Programmierung. In der Praxis wird begrenzte Präzision verwendet, und das Ergebnis ist eine Annäherung der wahren Lösung (das Annehmen der Stabilität).

Im Gegensatz zu direkten Methoden, wie man erwartet, enden wiederholende Methoden in mehreren Schritten nicht. Wenn sie von einer anfänglichen Annahme anfangen, bilden wiederholende Methoden aufeinander folgende Annäherungen, die zur genauen Lösung nur in der Grenze zusammenlaufen. Ein Konvergenz-Test wird angegeben, um zu entscheiden, als eine genug genaue Lösung (hoffentlich) gefunden worden ist. Sogar mit der unendlichen Präzisionsarithmetik würden diese Methoden die Lösung innerhalb einer begrenzten Zahl von Schritten (im Allgemeinen) nicht erreichen. Beispiele schließen die Methode von Newton, das Bisektionsverfahren und die Wiederholung von Jacobi ein. In der rechenbetonten Matrixalgebra sind wiederholende Methoden allgemein für große Probleme erforderlich.

Wiederholende Methoden sind üblicher als direkte Methoden in der numerischen Analyse. Einige Methoden sind im Prinzip direkt, aber werden gewöhnlich verwendet, als ob sie nicht z.B waren. GMRES und die verbundene Anstieg-Methode. Für diese Methoden musste die Zahl von Schritten vorherrschen die genaue Lösung ist so groß, dass eine Annäherung auf dieselbe Weise bezüglich einer wiederholenden Methode akzeptiert wird.

Discretization

Außerdem müssen dauernde Probleme manchmal durch ein getrenntes Problem ersetzt werden, dessen, wie man bekannt, Lösung diesem des dauernden Problems näher kommt; dieser Prozess wird discretization genannt. Zum Beispiel ist die Lösung einer Differenzialgleichung eine Funktion. Diese Funktion muss durch eine begrenzte Datenmenge zum Beispiel durch seinen Wert an einer begrenzten Zahl von Punkten an seinem Gebiet vertreten werden, wenn auch dieses Gebiet ein Kontinuum ist.

Generation und Fortpflanzung von Fehlern

Die Studie von Fehlern bildet einen wichtigen Teil der numerischen Analyse. Es gibt mehrere Wege, auf die Fehler in der Lösung des Problems eingeführt werden kann.

Herum - davon

Herum - von Fehlern entstehen, weil es unmöglich ist, alle reellen Zahlen genau auf einer Maschine mit dem begrenzten Gedächtnis zu vertreten (der ist, was alle praktischen Digitalcomputer sind).

Stutzung und discretization Fehler

Stutzungsfehler werden begangen, wenn eine wiederholende Methode begrenzt wird oder einem mathematischen Verfahren näher gekommen wird, und sich die ungefähre Lösung von der genauen Lösung unterscheidet. Ähnlich veranlasst discretization einen discretization Fehler, weil die Lösung des getrennten Problems mit der Lösung des dauernden Problems nicht zusammenfällt. Zum Beispiel, in der Wiederholung im sidebar, um die Lösung nach ungefähr 10 Wiederholungen zu schätzen, beschließen wir, dass die Wurzel ungefähr 1.99 (zum Beispiel) ist. Wir haben deshalb einen Stutzungsfehler 0.01.

Sobald ein Fehler erzeugt wird, wird er sich allgemein durch die Berechnung fortpflanzen. Zum Beispiel haben wir bereits bemerkt, dass die Operation + auf einer Rechenmaschine (oder ein Computer) ungenau ist. Hieraus folgt dass eine Berechnung des Typs a+b+c+d+e noch ungenauer ist.

Was bedeutet es, wenn wir sagen, dass der Stutzungsfehler geschaffen wird, wenn wir einem mathematischen Verfahren näher kommen? Wir wissen, dass, eine Funktion zu integrieren, genau verlangt, dass die Summe von unendlichen Trapezoiden findet. Aber numerisch kann man die Summe von nur begrenzten Trapezoiden, und folglich die Annäherung des mathematischen Verfahrens finden. Ähnlich, um eine Funktion zu unterscheiden, nähert sich das Differenzialelement der Null, aber numerisch können wir nur einen begrenzten Wert des Differenzialelements wählen.

Numerische Stabilität und gut aufgestellte Probleme

Numerische Stabilität ist ein wichtiger Begriff in der numerischen Analyse. Ein Algorithmus wird numerisch stabil genannt, wenn ein Fehler, was für seine Ursache, nicht wächst, um während der Berechnung viel größer zu sein. Das geschieht, wenn das Problem gut bedingt ist, bedeutend, dass sich die Lösung um nur einen kleinen Betrag ändert, wenn die Problem-Daten durch einen kleinen Betrag geändert werden. Zum Gegenteil, wenn ein Problem schlecht-bedingt wird, dann wird jeder kleine Fehler in den Daten wachsen, um ein großer Fehler zu sein.

Sowohl das ursprüngliche Problem als auch der Algorithmus, der verwendet ist, um dieses Problem zu beheben, können gut bedingt und/oder schlecht-bedingt sein, und jede Kombination ist möglich.

So kann ein Algorithmus, der ein gut bedingtes Problem behebt, entweder numerisch stabil oder numerisch nicht stabil sein. Eine Kunst der numerischen Analyse soll einen stabilen Algorithmus finden, für ein gut aufgestelltes mathematisches Problem zu beheben. Zum Beispiel ist die Computerwissenschaft der Quadratwurzel 2 (der ungefähr 1.41421 ist) ein gut aufgestelltes Problem. Viele Algorithmen beheben dieses Problem durch das Starten mit einer anfänglichen Annäherung x zu, zum Beispiel x=1.4, und dann die Computerwissenschaft von verbesserten Annahmen x, x usw. Eine solche Methode ist die berühmte babylonische Methode, die durch x = x/2 + 1/x gegeben wird. Eine andere Wiederholung, die wir Methode X nennen werden, wird durch x = (x−2) + x gegeben. Wir haben einige Wiederholungen jedes Schemas in der Tabellenform unten, mit anfänglichen Annahmen x = 1.4 und x = 1.42 berechnet.

Bemerken Sie, dass die babylonische Methode schnell unabhängig von der anfänglichen Annahme zusammenläuft, wohingegen Methode X äußerst langsam mit der anfänglichen Annahme 1.4 zusammenläuft und für die anfängliche Annahme 1.42 abweicht. Folglich ist die babylonische Methode numerisch stabil, während Methode X numerisch nicht stabil ist.

:Numerical-Stabilität wird durch die Zahl der positiven Ziffern betroffen, die die Maschine behält, wenn wir eine Maschine verwenden, die die ersten vier Schwimmpunkt-Ziffern behält, wird ein gutes Beispiel auf dem Verlust der Bedeutung durch diese zwei gleichwertigen Funktionen angeführt

f (x) =x\left (\sqrt {x+1}-\sqrt {x }\\Recht)

\text {und} g (x) = \frac {x} {\\sqrt {x+1} + \sqrt {x}}.

</Mathematik>

:If vergleichen wir die Ergebnisse von

:and

\begin {alignat} {3} g (500) &= \frac {500} {\\sqrt {501} + \sqrt {500} }\\\

&= \frac {500} {22.3830+22.3607 }\\\

&= \frac {500} {44.7437} =11.1748

\end {alignat }\

</Mathematik>

: dadurch, auf die zwei über Ergebnissen zu achten, begreifen wir, dass der Verlust der Bedeutung, die auch Abziehende Absage genannt wird, eine riesige Wirkung auf die Ergebnisse hat, wenn auch beide Funktionen gleichwertig sind; um zu zeigen, dass sie einfach gleichwertig sind, müssen wir durch f (x) anfangen und mit g (x), und so enden

f (x) &=x (\sqrt {x+1}-\sqrt {x}) \\

& =x (\sqrt {x+1}-\sqrt {x}) \frac {(\sqrt {x+1} + \sqrt {x})} {(\sqrt {x+1} + \sqrt {x}) }\\\

&=x \frac {((\sqrt {x+1}) ^2-(\sqrt {x}) ^2)} {(\sqrt {x+1} + \sqrt {x}) }\

&= \frac {x} {(\sqrt {x+1} + \sqrt {x}) }\

\end {alignat} </Mathematik>

Der wahre Wert von:The für das Ergebnis ist 11.174755..., der genau g (500) = 11.1748 nach dem Runden des Ergebnisses zu 4 dezimalen Ziffern ist.

:Now stellen sich vor, dass viele Begriffe wie diese Funktionen im Programm gebraucht werden; der Fehler wird zunehmen, als man im Programm weitergeht, wenn man die passende Formel der zwei Funktionen jedes Mal nicht verwendet, wenn man entweder f (x) oder g (x) bewertet; die Wahl ist von der Gleichheit von x abhängig.

Das Beispiel wird von Mathew genommen; numerische Methoden mit matlab, 3. Hrsg.

Gebiete der Studie

Das Feld der numerischen Analyse wird in verschiedene Disziplinen gemäß dem Problem geteilt, das gelöst werden soll.

Rechenwerte von Funktionen

Eines der einfachsten Probleme ist die Einschätzung einer Funktion an einem gegebenen Punkt. Die aufrichtigste Annäherung, gerade die Zahl in die Formel einzustecken, ist manchmal nicht sehr effizient. Für Polynome verwendet eine bessere Annäherung das Schema von Horner, da es die notwendige Anzahl von Multiplikationen und Hinzufügungen vermindert. Allgemein ist es wichtig, zu schätzen und herum - von Fehlern zu kontrollieren, die aus dem Gebrauch der Schwimmpunkt-Arithmetik entstehen.

Interpolation, Extrapolation und rückwärts Gehen

Interpolation behebt das folgende Problem: In Anbetracht des Werts etwas unbekannter Funktion an mehreren Punkten, was Wert den hat Funktion an einem anderen Punkt zwischen den gegebenen Punkten?

Extrapolation ist der Interpolation sehr ähnlich, außer dass jetzt wir den Wert der unbekannten Funktion an einem Punkt finden wollen, der außerhalb der gegebenen Punkte ist.

Rückwärts Gehen ist auch ähnlich, aber es zieht in Betracht, dass die Daten ungenau sind. In Anbetracht einiger Punkte und eines Maßes des Werts etwas Funktion an diesen Punkten (mit einem Fehler) wollen wir die unbekannte Funktion bestimmen. Kleinste Quadratmethode ist eine populäre Weise, das zu erreichen.

Das Lösen von Gleichungen und Gleichungssystemen

Ein anderes grundsätzliches Problem schätzt die Lösung einer gegebenen Gleichung. Zwei Fälle sind je nachdem allgemein bemerkenswert, ob die Gleichung geradlinig ist oder nicht. Zum Beispiel ist die Gleichung geradlinig, während nicht ist.

Viel Anstrengung ist in der Entwicklung von Methoden gestellt worden, um Systeme von geradlinigen Gleichungen zu lösen. Direkte Standardmethoden, d. h., Methoden, die eine Matrixzergliederung verwenden, sind Beseitigung von Gaussian, LU Zergliederung, Zergliederung von Cholesky für den symmetrischen (oder hermitian) und positiv-bestimmte Matrix und QR Zergliederung für das Nichtquadrat matrices. Wiederholende Methoden wie die Methode von Jacobi, Methode von Gauss-Seidel, aufeinander folgende Überentspannung und verbundene Anstieg-Methode werden gewöhnlich für große Systeme bevorzugt.

Wurzelfindende Algorithmen werden verwendet, um nichtlineare Gleichungen zu lösen (sie werden so genannt, da eine Wurzel einer Funktion ein Argument ist, für das die Funktion Null nachgibt). Wenn die Funktion differentiable ist und die Ableitung bekannt ist, dann ist die Methode von Newton eine populäre Wahl. Linearization ist eine andere Technik, um nichtlineare Gleichungen zu lösen.

Das Lösen eigenvalue oder einzigartige Wertprobleme

Mehrere wichtige Probleme können in Bezug auf eigenvalue Zergliederungen oder einzigartige Wertzergliederungen ausgedrückt werden. Zum Beispiel basiert der geisterhafte Bildkompressionsalgorithmus auf der einzigartigen Wertzergliederung. Das entsprechende Werkzeug in der Statistik wird Hauptteilanalyse genannt.

Optimierung

Optimierungsprobleme bitten um den Punkt, an dem eine gegebene Funktion maximiert (oder minimiert wird). Häufig muss der Punkt auch einige Einschränkungen befriedigen.

Das Feld der Optimierung wird weiter in mehreren Teilfeldern, abhängig von der Form der objektiven Funktion und der Einschränkung gespalten. Zum Beispiel befasst sich geradlinige Programmierung mit dem Fall, dass sowohl die objektive Funktion als auch die Einschränkungen geradlinig sind. Eine berühmte Methode in der geradlinigen Programmierung ist die Simplexmethode.

Die Methode von Vermehrern von Lagrange kann verwendet werden, um Optimierungsprobleme mit Einschränkungen zu zwanglosen Optimierungsproblemen zu reduzieren.

Das Auswerten von Integralen

Numerische Integration, in einigen Beispielen auch bekannt als numerische Quadratur, bittet um den Wert eines bestimmten Integrals. Populäre Methoden verwenden eine der Formeln von Newton-Ställen (wie die Mittelpunkt-Regel oder die Regierung von Simpson) oder Quadratur von Gaussian. Diese Methoden verlassen sich auf "teilen und überwinden" Strategie, wodurch ein Integral auf einem relativ großen Satz unten in Integrale auf kleineren Sätzen zerbrochen wird. In höheren Dimensionen, wo diese Methoden untersagend teuer in Bezug auf die rechenbetonte Anstrengung werden, kann man Methoden von Monte Carlo oder quasi-Monte Carlo verwenden (sieh Integration von Monte Carlo), oder, in bescheiden großen Dimensionen, der Methode des spärlichen Bratrostes.

Differenzialgleichungen

Numerische Analyse ist mit auch Computerwissenschaft (auf eine ungefähre Weise) die Lösung von Differenzialgleichungen, sowohl gewöhnliche Differenzialgleichungen als auch teilweise Differenzialgleichungen beschäftigt.

Teilweise Differenzialgleichungen werden durch den ersten discretizing die Gleichung gelöst, es in einen endlich-dimensionalen Subraum bringend. Das kann durch eine begrenzte Element-Methode, eine begrenzte Unterschied-Methode, oder (besonders in der Technik) eine begrenzte Volumen-Methode getan werden. Die theoretische Rechtfertigung dieser Methoden ist häufig mit Lehrsätzen von der Funktionsanalyse verbunden. Das reduziert das Problem auf die Lösung einer algebraischen Gleichung.

Software

Seit dem Ende des zwanzigsten Jahrhunderts werden die meisten Algorithmen in einer Vielfalt von Programmiersprachen durchgeführt. Das Netlib Behältnis enthält verschiedene Sammlungen von Softwareroutinen für numerische Probleme, größtenteils in Fortran und C. Kommerzielle Produkte, die viele verschiedene numerische Algorithmen durchführen, schließen den IMSL und die NÖRGLER-Bibliotheken ein; eine freie Alternative ist das GNU Wissenschaftliche Bibliothek.

Es gibt mehrere populäre numerische Rechenanwendungen wie MATLAB, S-PLUS, LabVIEW, und IDL sowie freie und offene Quellalternativen wie FreeMat, Scilab, GNU-Oktave (ähnlich Matlab), ES ++ (ein C ++ Bibliothek), R (ähnlich S-PLUS) und bestimmte Varianten der Pythonschlange. Leistung ändert sich weit: Während Vektor und Matrixoperationen gewöhnlich schnelle Skalarschleifen sind, kann sich in der Geschwindigkeit durch mehr als eine Größenordnung ändern.

Viele Computeralgebra-Systeme wie Mathematica ziehen auch aus der Verfügbarkeit der willkürlichen Präzisionsarithmetik einen Nutzen, die genauere Ergebnisse zur Verfügung stellen kann.

Außerdem kann jede Spreadsheet-Software verwendet werden, um einfache Probleme in Zusammenhang mit der numerischen Analyse zu beheben.

Siehe auch

Wissenschaftliche Computerwissenschaft
Liste von numerischen Analyse-Themen
Prozess des Gramms-Schmidt
Numerische Unterscheidung
Symbolisch-numerische Berechnung
Analyse von Algorithmen
Numerische Rezepte

Referenzen

Trefethen, Lloyd N. (2006). "Numerische Analyse", 20 Seiten. In: Timothy Gowers und June Barrow-Green (Redakteure), Begleiter von Princeton der Mathematik, Universität von Princeton Presse.
(Beispiele der Wichtigkeit von der genauen Arithmetik).