Romberg-Integration
aus Freepedia, der freien Wissensdatenbank
Die Romberg-Integration ist ein Verfahren zur numerischen Bestimmung von Integralen und wurde von Werner Romberg entwickelt. Sie ist eine Verbesserung der (Sehnen)-Trapezregel durch Extrapolation.
Inhaltsverzeichnis |
Grundgedanke
Der aufwändige Teil der numerischen Integration sind oft die Funktionsauswertungen. Um deren Anzahl minimal zu halten, ist es somit ratsam, einen Schrittweitenverlauf zu wählen, der die Weiterverwendung von bereits berechneten Funktionswerten erlaubt. Ein Beispiel für eine solche Schrittweite wäre <math>h_k=2^{-k}</math>, das zugleich die Bedingungen für eine konvergente Extrapolation erfüllt.
Rechenvorschrift
- <math> I = \int_a^b f(x) = \lim_{n \to \infty} I_{n,k} </math>
mit
- <math> I_{n,k} = \frac{4^{k-1}I_{n+1,k-1} - I_{n,k-1} }{4^{k-1} - 1 } </math>
dabei ist
- <math> I_{1,1} = \frac{b-a}{2}(f(a)+f(b)) </math> (Trapezregel)
- <math> I_{n,1} = \frac{b-a}{2 * 2^n} \left( f(a)+ f(b) + 2 \sum_{i=1}^{2^n-1} f \left( a + i * \frac{b-a}{2 * 2^n} \right) \, \right) </math>
und
- <math> k \in [ 1 , n+1] \quad \in \mathbb{N} </math>
das Fehlerglied hat den Wert:
- <math> E = \frac{I_{1, n + 1} - I_{1, n}} { I_{1, n} } </math>
Vorgehensweise
1. Zuerst wird <math>I_{1,1}</math> berechnet.
2. Beginne eine zyklische Berechnung (Hauptzyklus) mit der Zyklusvariablen n mit n = 1 und berechne <math>I_{n+1,1}</math>
3. Extrapoliere in einem Unterzyklus mit
k = 2 bis n + 1 und s = 2 + n - k
den Wert <math>I_{s, k} </math> nach obiger Regel
4. Berechnen. Ist die gewünschte Genauigkeit noch nicht erreicht, so erhöhe n um 1 und setze den Hauptzyklus mit einem neuen Durchgang fort.
Die Berechnung startet also wie folgt:
- Berechnen von <math>I_{1,1}</math> nach der Trapezregel
- Hauptzyklus starten mit n = 1
- Berechnen von <math>I_{n+1,1} = I_{2,1}</math> nach der Trapezregel (2 Intervalle).
- Unterzyklus: k geht von 2 bis 2 .
- <math>k = 2 \ ;\ s = 2 + n - k = 1\ ;\quad I_{s,2} = I_{1,2} = \frac{4^1 * I_{2,1} - I_{1,1} }{4^1 - 1 } </math>
- <math>\ E = \frac{I_{1, 2} - I_{1, 1}} { I_{1, 1} } </math>
- Neuer Durchgang des Hauptzyklus mit n = 2 .
- Berechnen von <math>\ I_{n+1,1} = I_{3,1}</math> nach der Trapezregel (4 Intervalle).
- Unterzyklus: k geht von 2 bis 3 .
- <math>\ k = 2</math> und <math>s = 2 \ ; \quad I_{s,k} = I_{2,2} = \frac{4^1 * I_{3,1} - I_{2,1} }{4^1 - 1 } </math>
- <math>\ k = 3</math> und <math>s = 1 \ ; \quad I_{s,k} = I_{1,3} = \frac{4^2 * I_{2,2} - I_{1,2} }{4^2 - 1 } </math>
- <math>\ E = \frac{I_{1, 3} - I_{1, 2}} { I_{1, 2} } </math>
- Neuer Durchgang des Hauptzyklus mit n= 3 .
- Berechnen von <math>I_{n+1,1} = I_{4,1}</math> nach der Trapezregel (8 Intervalle).
- Unterzyklus: k geht von 2 bis 4 .
- <math>\ k = 2</math> und <math>s = 3 \ ; \quad I_{s,k} = I_{3,2} = \frac{4^1 * I_{4,1} - I_{3,1} }{4^1 - 1 } </math>
- <math>\ k = 3</math> und <math>s = 2 \ ; \quad I_{s,k} = \frac{4^2 * I_{3,2} - I_{2,2} } {4^2 - 1 } </math>
- <math>\ k = 4</math> und <math>s = 1 \ ; \quad I_{s,k} = \frac{4^3 * I_{2,3} - I_{1,3} }{4^3 - 1 } </math>
- <math>\ E = \frac{I_{1, 4} - I_{1, 3}} { I_{1, 3} } </math>
- Neuer Durchgang des Hauptzyklus mit i = 4
- usw.
Anmerkungen
Eine Unterschreitung der hier definierten Fehlerschranke bedeutet nicht immer, dass das Integral korrekt berechnet wurde. Dies gilt besonders für periodische Funktionen und Funktionen mit einem periodischen Anteil. So führt z.B. das bei der Fourier-Analyse periodischer Funktionen vorkommende Integral
- <math> \int_{0}^{2 \pi} f(x) * cos(2^n x) dx </math>
u. U. zu einem Fehler, wenn man nicht mindestens n+1 Integrationsstufen berechnet. In den ersten n Integrationsstufen fallen alle Stützstellen mit den Nullstellen der Funktion zusammen. Als Integral erhält man daher immer den Wert Null, egal ob es stimmt oder nicht. Ein Computerprogramm sollte also immer eine Mindestanzahl an Integrationsstufen erzwingen.
Fazit
Der große Vorteil der Romberg Quadratur gegenüber anderen Verfahren besteht in der Möglichkeit den Fehler im Nachhinein zu kontrollieren und schon erreichte Ergebnisse weiterzuverwenden, wenn die Genauigkeit noch nicht erreicht ist. Die Gauß-Quadratur stellt dem gegenüber zwar ein optimales Verfahren in Bezug auf die Anzahl der Funktionsauswertungen dar, die zugehörige Fehlerabschätzung ist aber wegen den Ableitungen hoher Ordnung, die in der Fehlerabschätzung auftreten, oft praktisch nicht durchführbar.
