In der numerischen Analyse setzt numerische Integration eine breite Familie von Algorithmen ein, für den numerischen Wert eines bestimmten Integrals und durch die Erweiterung zu berechnen, der Begriff wird auch manchmal gebraucht, um die numerische Lösung von Differenzialgleichungen zu beschreiben. Dieser Artikel konzentriert sich auf Berechnung von bestimmten Integralen. Der Begriff numerische Quadratur (häufig abgekürzt zur Quadratur) ist mehr oder weniger ein Synonym für die numerische Integration, besonders wenn angewandt zu eindimensionalen Integralen. Die numerische Integration über mehr als eine Dimension wird manchmal als cubature beschrieben, obwohl die Bedeutung der Quadratur für die höhere dimensionale Integration ebenso verstanden wird.

Das grundlegende durch die numerische Integration betrachtete Problem soll eine ungefähre Lösung eines bestimmten Integrals schätzen:

:

Wenn eine glatte wohl erzogene Funktion ist, die über eine kleine Zahl von Dimensionen integriert ist, und die Grenzen der Integration begrenzt werden, gibt es viele Methoden, dem Integral mit der willkürlichen Präzision näher zu kommen.

Gründe für die numerische Integration

Es gibt mehrere Gründe dafür, numerische Integration auszuführen.

Der integrand f (x) kann nur an bestimmten Punkten, bekannt sein

solcher, wie erhalten, durch die Stichprobenerhebung.

Einige eingebettete Systeme und andere Computeranwendungen können numerische Integration aus diesem Grund brauchen.

Eine Formel für den integrand kann bekannt sein, aber es kann schwierig oder unmöglich sein, eine Antiableitung zu finden, die eine Elementarfunktion ist. Ein Beispiel solch eines integrand ist f (x) = exp (x), dessen Antiableitung (die Fehlerfunktion, Zeiten eine Konstante) in der elementaren Form nicht geschrieben werden kann.

Es kann möglich sein, eine Antiableitung symbolisch zu finden, aber es kann leichter sein, eine numerische Annäherung zu schätzen, als, die Antiableitung zu schätzen. Das kann der Fall sein, wenn die Antiableitung als eine unendliche Reihe oder Produkt gegeben wird, oder wenn seine Einschätzung eine spezielle Funktion verlangt, die nicht verfügbar ist.

Methoden für eindimensionale Integrale

Numerische Integrationsmethoden können allgemein als sich verbindende Einschätzungen des integrand beschrieben werden, um eine Annäherung an das Integral zu bekommen. Der integrand wird an einem begrenzten Satz von Punkten genannt Integrationspunkte bewertet, und eine belastete Summe dieser Werte wird verwendet, um dem Integral näher zu kommen. Die Integrationspunkte und Gewichte hängen von der spezifischen Methode verwendet und die von der Annäherung erforderliche Genauigkeit ab.

Ein wichtiger Teil der Analyse jeder numerischen Integrationsmethode soll das Verhalten des Annäherungsfehlers als eine Funktion der Zahl von integrand Einschätzungen studieren.

Eine Methode, die einen kleinen Fehler für eine kleine Zahl von Einschätzungen nachgibt, wird gewöhnlich höher betrachtet.

Das Vermindern der Anzahl von Einschätzungen des integrand vermindert die Anzahl von arithmetischen Operationen beteiligt,

und reduziert deshalb die Gesamtrunde - vom Fehler.

Außerdem

jede Einschätzung nimmt Zeit in Anspruch, und der integrand kann willkürlich kompliziert werden.

Eine Art 'der rohen Gewalt' der numerischen Integration kann getan werden, wenn der integrand (d. h. piecewise dauernd und von der begrenzten Schwankung), durch das Auswerten des integrand mit der sehr kleinen Zunahme vernünftig wohl erzogen ist.

Quadratur-Regeln auf dem Interpolieren von Funktionen gestützt

Eine große Klasse von Quadratur-Regeln kann durch das Konstruieren von interpolierenden Funktionen abgeleitet werden, die leicht sind zu integrieren. Normalerweise sind diese interpolierenden Funktionen Polynome.

Die einfachste Methode dieses Typs ist, die interpolierende Funktion eine unveränderliche Funktion sein zu lassen (ein Polynom der Grad-Null), der den Punkt ((a+b)/2, f ((a+b)/2)) durchführt. Das wird die Mittelpunkt-Regel oder Rechteck-Regel genannt.

:

Die interpolierende Funktion kann eine Affine-Funktion (ein Polynom des Grads 1) sein

der die Punkte (a, f (a)) und (b, f (b)) durchführt.

Das wird die trapezoide Regel genannt.

:

Für jede dieser Regeln können wir eine genauere Annäherung dadurch machen, den Zwischenraum [a, b] in eine Nummer n von Subzwischenräumen zu zerbrechen, eine Annäherung für jeden Subzwischenraum schätzend, dann alle Ergebnisse zusammenzählend. Das wird eine zerlegbare Regel genannt, hat Regel erweitert, oder hat Regel wiederholt. Zum Beispiel kann die zerlegbare trapezoide Regel als festgesetzt werden

:

wo die Subzwischenräume die Form [k h, (k+1) h], mit h = (ba)/n und k = 0, 1, 2..., n1 haben.

Die Interpolation mit Polynomen, die an Punkten ebenso unter Drogeneinfluss in [a, b] bewertet sind, gibt die Formeln von Newton-Ställen nach, von denen die Rechteck-Regel und die trapezoide Regel Beispiele sind. Die Regierung von Simpson, die auf einem Polynom des Auftrags 2 basiert, ist auch eine Formel von Newton-Ställen.

Quadratur-Regeln mit Punkten ebenso unter Drogeneinfluss haben das sehr günstige Eigentum dessen. Die entsprechende Regel mit jedem unterteilten Zwischenraum schließt alle aktuellen Punkte ein, so können jene Integrand-Werte wiederverwendet werden.

Wenn wir den Zwischenräumen zwischen Interpolationspunkten erlauben sich zu ändern, finden wir eine andere Gruppe von Quadratur-Formeln wie die Quadratur-Formeln von Gaussian. Eine Gaussian Quadratur-Regel ist normalerweise genauer als eine Regel von Newton-Ställen, die dieselbe Zahl von Funktionseinschätzungen verlangt, wenn der integrand glatt ist (d. h., wenn es genug differentiable ist). Andere Quadratur-Methoden mit unterschiedlichen Zwischenräumen schließen Quadratur von Clenshaw-Curtis ein (auch hat Quadratur von Fejér genannt) Methoden, die wirklich nisten.

Quadratur-Regeln von Gaussian nisten nicht, aber die zusammenhängenden Quadratur-Formeln von Gauss-Kronrod tun.

Anpassungsfähige Algorithmen

Wenn f (x) viele Ableitungen an allen Punkten nicht hat, oder wenn die Ableitungen groß werden, dann ist Quadratur von Gaussian häufig ungenügend. In diesem Fall wird ein dem folgenden ähnlicher Algorithmus besser leisten:

def calculate_definite_integral_of_f (f, initial_step_size):

Dieser Algorithmus berechnet das bestimmte Integral einer Funktion

von 0 bis 1, anpassungsfähig, durch die Auswahl kleinerer Schritte nahe

problematische Punkte.

x = 0.0

h = initial_step_size

Akkumulator = 0.0

während x

h = 1.0 - x

quad_this_step =

wenn error_too_big_in_quadrature_of_over_range (f, [x, x+h]):

h = make_h_smaller (h)

sonst:

Akkumulator + = quadrature_of_f_over_range (f, [x, x+h])

x + = h

wenn error_too_small_in_quadrature_of_over_range (f, [x, x+h]):

h = make_h_larger (h) # Vermeiden, auf winzigen Schritten Zeit zu verschwenden.

geben Sie Akkumulator zurück

</Quelle>

Einige Details des Algorithmus verlangen sorgfältigen Gedanken. Für viele Fälle, den Fehler von der Quadratur über einen Zwischenraum für eine Funktion f (x) schätzend, ist nicht offensichtlich. Eine populäre Lösung ist, zwei verschiedene Regeln der Quadratur zu verwenden, und ihren Unterschied als eine Schätzung des Fehlers von der Quadratur zu verwenden. Das andere Problem entscheidet, was "zu groß" oder "sehr klein" bedeuten. Ein Kriterium für "den zu großen" ist, dass der Quadratur-Fehler nicht größer sein sollte als t &middot; h, wo t, eine reelle Zahl, die Toleranz ist, möchten wir für den globalen Fehler untergehen. Andererseits, wenn h bereits winzig ist, kann es nicht lohnend sein, es noch kleiner zu machen, selbst wenn der Quadratur-Fehler anscheinend groß ist. Ein Kriterium ist, dass die Summe von Fehlern auf allen Zwischenräumen weniger sein sollte als t. Dieser Typ der Fehleranalyse wird gewöhnlich "a posteriori" genannt, da wir den Fehler schätzen, die Annäherung geschätzt.

Die Heuristik für die anpassungsfähige Quadratur wird von Forsythe besprochen u. a. (Abschnitt 5.4).

Extrapolationsmethoden

Die Genauigkeit einer Quadratur-Regel des Typs von Newton-Ställen ist allgemein eine Funktion der Zahl von Einschätzungspunkten.

Das Ergebnis ist gewöhnlich als Zahl von Einschätzungspunkt-Zunahmen, genauer

oder, gleichwertig, als die Breite der Schritt-Größe zwischen den Punkt-Abnahmen.

Es ist natürlich zu fragen, was das Ergebnis darin bestehen würde, wenn der Schritt-Größe erlaubt würde, sich Null zu nähern.

Darauf kann durch das Extrapolieren des Ergebnisses von zwei oder mehr Nichtnullschritt-Größen, das Verwenden von Reihe-Beschleunigungsmethoden wie Extrapolation von Richardson geantwortet werden.

Die Extrapolationsfunktion kann eine polynomische oder vernünftige Funktion sein.

Extrapolationsmethoden werden ausführlicher von Stoer und Bulirsch (Abschnitt 3.4) beschrieben und werden in vielen der Routinen in der QUADPACK Bibliothek durchgeführt.

Konservative (a priori) Fehlerbewertung

Lassen Sie f eine begrenzte erste Ableitung über [a, b] haben. Der Mittelwertlehrsatz für f, wo x

für einen y in [a, x] je nachdem x. Wenn wir in x von bis b an beiden Seiten integrieren und die absoluten Werte nehmen, erhalten wir

:

= \left | \int_a^b (x - a) f' (y_x) \, dx \right | </math>

Wir können weiter dem Integral auf der rechten Seite näher kommen, indem wir den absoluten Wert in den integrand bringen, und den Begriff in f' durch einen gebundenen oberen ersetzen:

: (**)

(Sieh Supremum.) Folglich, wenn wir dem integrierten  f (x) näher kommen, ist dx durch die Quadratur-Regel (b  a) f (a) unser Fehler nicht größer als die rechte Seite (**). Wir können das in eine Fehleranalyse für die Summe von Riemann (*) umwandeln, einen gebundenen oberen gebend

:

für den Fehlerbegriff dieser besonderen Annäherung. (Bemerken Sie, dass das genau der Fehler ist, den wir für das Beispiel berechnet haben.), Mehr Ableitungen verwendend, und indem wir die Quadratur zwicken, können wir eine ähnliche Fehleranalyse mit einer Reihe von Taylor tun (eine teilweise Summe mit dem Rest-Begriff verwendend), für f. Diese Fehleranalyse gibt einen strengen oberen hat zum Fehler gebunden, wenn die Ableitungen von f verfügbar sind.

Diese Integrationsmethode kann mit der Zwischenraum-Arithmetik verbunden werden, um Computerbeweise und nachgeprüfte Berechnungen zu erzeugen.

Integrale über unendliche Zwischenräume

Unendliche Zwischenräume

Eine Weise, ein Integral über den unendlichen Zwischenraum, zu berechnen

:

\int_ {-\infty} ^ {+ \infty} f (x) \, dx,

</Mathematik>soll

es in ein Integral über einen begrenzten Zwischenraum durch irgendwelche von mehreren möglichen Änderungen von Variablen zum Beispiel umgestalten:

:

\int_ {-\infty} ^ {+ \infty} f (x) \, dx = \int_ {-1} ^ {+1} f\left (\frac {t} {1-t^2} \right) \frac {1+t^2} {(1-t^2) ^2} \, dt,

</Mathematik>

Das Integral über den begrenzten Zwischenraum kann dann durch gewöhnliche Integrationsmethoden bewertet werden.

Halbunendliche Zwischenräume

Ein Integral über einen halbunendlichen Zwischenraum kann in ein Integral über einen begrenzten Zwischenraum durch irgendwelche von mehreren möglichen Änderungen von Variablen zum Beispiel ebenfalls umgestaltet werden:

:

\int_a^ {+ \infty} f (x) \, dx = \int_0^1 f\left (+ \frac {1-t} {t }\\Recht) \frac {dt} {t^2}. </Mathematik>

Ähnlich

:

\int_ {-\infty} ^a f (x) \, dx = \int_0^1 f\left (-\frac {1-t} {t }\\Recht) \frac {dt} {t^2} </Mathematik>

Mehrdimensionale Integrale

Die Quadratur-Regeln besprochen werden alle bis jetzt entworfen, um eindimensionale Integrale zu schätzen.

Integrale in vielfachen Dimensionen, zu schätzen

eine Annäherung soll das vielfache Integral als wiederholte eindimensionale Integrale durch das Appellieren an den Lehrsatz von Fubini ausdrücken.

Diese Annäherung verlangt, dass die Funktionseinschätzungen exponential als die Zahl von Dimensionszunahmen wachsen. Wie man bekannt, überwinden zwei Methoden diesen so genannten Fluch von dimensionality.

Monte Carlo

Methoden von Monte Carlo und Methoden von quasi-Monte Carlo sind leicht, für mehrdimensionale Integrale, zu gelten

und kann größere Genauigkeit für dieselbe Zahl von Funktionseinschätzungen nachgeben als wiederholte Integrationen mit eindimensionalen Methoden.

Eine große Klasse von nützlichen Methoden von Monte Carlo ist die so genannte Kette von Markov Algorithmen von Monte Carlo,

die den Algorithmus der Metropole-Hastings und Gibbs einschließen, der ausfällt.

Spärlicher Bratrost

Spärlicher Bratrost wurde von Smolyak für die Quadratur von hohen dimensionalen Funktionen ursprünglich entwickelt. Die Methode basiert immer auf einer dimensionaler Quadratur-Regel, aber führt eine hoch entwickeltere Kombination von Univariate-Ergebnissen durch.

Verbindung mit Differenzialgleichungen

Das Problem, den integrierten zu bewerten

:

kann auf ein Anfangswert-Problem für eine gewöhnliche Differenzialgleichung reduziert werden. Wenn das obengenannte Integral von mir (b) angezeigt wird, dann befriedigt die Funktion I

:

Methoden, die für gewöhnliche Differenzialgleichungen wie Runge-Kutta-Methoden entwickelt sind, können auf das neu formulierte Problem angewandt werden und so gepflegt werden, das Integral zu bewerten. Zum Beispiel gibt die normale vierte Ordnung Runge-Kutta auf die Differenzialgleichung angewandte Methode die Regierung von Simpson von oben nach.

Die Differenzialgleichung I&thinsp; '  (x) = &fnof; (x) hat eine spezielle Form: Die Rechte enthält nur die abhängige Variable (hier x) und nicht die unabhängige Variable (hier I). Das vereinfacht die Theorie und Algorithmen beträchtlich. Das Problem, Integrale zu bewerten, wird so am besten in seinem eigenen Recht studiert.

Siehe auch

• Numerische gewöhnliche Differenzialgleichungen
• Stutzungsfehler (numerische Integration)
• Quadratur von Clenshaw-Curtis
• Quadratur von Gauss-Kronrod
• Summe von Riemann oder Riemann integrierter
• Trapezoide Regel
• Philip J. Davis und Philip Rabinowitz, Methoden der numerischen Integration.
• George E. Forsythe, Michael A. Malcolm und Cleve B. Moler. Computermethoden für die Mathematische Berechnung. Englewood Klippen, New Jersey: Prentice-Saal, 1977. (Sieh Kapitel 5.)
• Josef Stoer und Roland Bulirsch. Einführung in die Numerische Analyse. New York: Springer-Verlag, 1980. (Sieh Kapitel 3.)

Links

• Integration: Hintergrund, Simulationen, usw. am Holistischen Numerischen Methode-Institut

Kostenlose Software für die numerische Integration

Numerische Integration ist eines der am intensivsten studierten Probleme in der numerischen Analyse.

Der vielen Softwaredurchführungen verzeichnen wir einige freie und offene Quellsoftwarepakete hier:

• QUADPACK (ein Teil von SLATEC): Beschreibung http://www.netlib.org/slatec/src/qpdoc.f, Quellcode http://www.netlib.org/slatec/src. QUADPACK ist eine Sammlung von Algorithmen in Fortran für die numerische auf der Quadratur von Gaussian gestützte Integration.
• interalg: Ein solver vom OpenOpt/FuncDesigner Fachwerk, das auf der Zwischenraum-Analyse gestützt ist, hat Präzision, Lizenz versichert: BSD (frei zu irgendwelchen Zwecken)
• GSL: GNU Scientific Library (GSL) ist eine numerische Bibliothek, die in C geschrieben ist, der eine breite Reihe von mathematischen Routinen wie Integration von Monte Carlo zur Verfügung stellt.
• Numerische Integrationsalgorithmen werden in der GAMS Klasse H2 gefunden.
• ALGLIB ist eine Sammlung von Algorithmen, in C# / C ++ / Delphi / Visuell Grundlegend / usw., für die numerische Integration (schließt Bulirsch-Stoer und Runge-Kutta Integratoren ein).
• Kuba ist eine Bibliothek der kostenlosen Software von mehreren mehrdimensionalen Integrationsalgorithmen.
• Cubature codieren für die anpassungsfähige mehrdimensionale Integration.
• Formeln von Cubature für die 2. Einheitsplattenabstammung, Quellcode für den Produkttyp Gaussian cubature mit hohen Präzisionskoeffizienten und Knoten.
• Abszissen der hohen Präzision und Gewichte für die Gaussian Quadratur für n = 2..., 20, 32, 64, 100, 128, 256, 512, 1024 enthalten auch Quellcode der c Sprache laut der LGPL-Lizenz.