Diskussion:Romberg-Integration

irgendwie finde ich da diesen einen alten text hier http://de.wikipedia.org/w/index.php?title=Romberg-Integration&oldid=6131108 besser als das was da jetzt steht, da versteht man wenigstens was das prinzip ist. momentan sinds halt ne menge formeln, aber wer das prinzip verstanden hat wird die sich auch noch selbst herleiten koennen

Quellcode

Hallo, zum Quellcode habe ich folgende Vorschläge:

• Man sollte erwähnen, dass es sich um die Sprache Java handelt
• In der deutschen Wikipedia dürfen die Kommentare im Quelltext doch ruhig deutsch sein, oder?
• Die Hilfsmethode pow irritiert doch nur. Warum nicht (int) Math.pow()?
• Es scheint naheliegender, computeAreaRomberg als statische Methode zu implementieren, vgl. Math-Klasse in Java. Für die Berechnung extra ein Objekt zu konstruieren, ist zumindest ungewöhnlich.
• Schließlich erscheint es mir sinnvoll, die eigentliche interessante computeAreaRomberg-Methode ganz an den Anfang zu stellen

JM2C, --Winne 12:52, 16. Jul 2006 (CEST)

Es wäre schon wahnsinnig gescheit auch anzuführen dass der code aus dem pool von C sharp kommt, da wohl nicht jeder damit familär ist. Ausserdem denke ich nicht dass spezifischer code sinnvoll ist, sondern eine generalisierung anzustreben wäre, um das ganze wikipedrisch zu machenSlicky 19:44, 23. Jul 2006 (CEST)

Rekursion

Mir hat die rekursive Formel nicht so wirklich weitergeholfen. Was haltet ihr davon diese Formel zu übernehmen und eventuell eine solche Veranschaulichung zu verwenden wie hier?: http://numlab.mathematik.uni-bielefeld.de/Integration/Integration_text.html#RombergIntegration

Indizierung

Ich habe beim Einfügen des Schemas die Indizierung aus den bisherigen Formeln übernommen. Allerdings kenne ich die Indizierung etwas anders und finde sie wesentlich logischer, z.B. so:

${\begin{matrix}I_{1,1}\\&\searrow \\I_{2,1}&\rightarrow &I_{2,2}\\&\searrow &&\searrow \\I_{3,1}&\rightarrow &I_{3,2}&\rightarrow &I_{3,3}\\&\searrow &&\searrow &&\searrow \\I_{4,1}&\rightarrow &I_{4,2}&\rightarrow &I_{4,3}&\rightarrow &I_{4,4}\\&\searrow &&\searrow &&\searrow &&\searrow \\I_{5,1}&\rightarrow &I_{5,2}&\rightarrow &I_{5,3}&\rightarrow &I_{5,4}&\rightarrow &I_{5,5}\\\end{matrix}}$

Dadurch ist es möglich die Formel auf folgende Weise anzugeben, was die bereits bemängelte Rekursion mit den vielen verschiedenen Variablen n,k,s etwas vereinfachen würde.

$I_{i,j}=I_{i,j-1}+{\frac {I_{i,j-1}-I_{i-1,j-1}}{4^{j-1}-1}}$

Vgl, auch die Formel die im oben vorgeschlagenen Skript aus Bielefeld angegeben wird. -- B-Navigator 17:04, 17. Aug 2006 (CEST)

Nützlich für das Verständnis ist vor allem eine anschauliche Interpretation der Indizes. Ich gehe mal davon aus, dass $I_{n,k}$ eine Annäherung mit Fehler $O(h_{n}^{k})$ bezeichnen soll. Habe ich das richtig verstanden? In dem Falle wäre die gewählte Indizierung durchaus sinnvoll, aber nur, wenn das auch irgendwo so steht. --Carsten Milkau 12:26, 14. Jul. 2009 (CEST)

Ich persönlich finde den Vorschlag etwas schöner, weil in der Schreibweise vom Artikel $I_{n-1,k+1}$ eine bessere Näherung darstellt als $I_{n,k}$. Das sieht verwirrend aus. Was ich aber wichtiger finde: $I_{n,1}$ ist eine Näherung, deren Fehler ein Polynom in $h_{n}^{2}$ ist. (Dazu muss man sich die Trapezregel genauer ansehen.) Demzufolge ist in der vorgeschlagenen Schreibweise $I_{n,k}$ eine Näherung mit Fehler $O(h_{n}^{2k})$, und daraus ergibt sich dann auch die Iteration, die B-Navigator eingebracht hat. --DerPhimor (Diskussion) 17:03, 1. Jul. 2013 (CEST)

Der Artikel enthält im Bereich Rechenvorschrift und Vorgehensweise paar Fehler. Der Fehler E müsste außerdem bzgl der Stufe n angegeben werden und so wie es beschrieben ist, wird der Fehler immer aus der ersten Zeile berechnet. (Indizes vertauscht, ist das gleiche bei Vorgehensweise) In der Berechnung von $I_{n,1}$ ist die Schranke der Indizes sehr verwirrend eingetragen und führt beim Benutzen der Bulirsch-Folge zu Indizes mit Kommas. Tut mir leid, dass ich nur nörgel, aber wollte es gerade benutzen für eine Prüfung und es verwirrt sehr. (nicht signierter Beitrag von Cramgnutrah (Diskussion | Beiträge) 17:49, 15. Apr. 2014 (CEST))

Anmerkungen

Der Absatz irritiert mich sehr. Wenn der Nenner in der Fehlerschranke 0 wird, sollte doch klar sein, dass das ein Problem ist. Damit ist doch nicht "die Fehlerschranke unterschritten", nur weil gleichzeitig der Zähler auch verschwindet. Stimmt die Formel für den Fehler überhaupt? Man könnte sich ja behelfen, in dem man eine Konstante c zur Funktion addiert. Alle Werte werden dann um c·(b-a) größer, aber im Zähler des Fehlers hebt sich das weg, im Nenner nicht, und der Fehler wird anscheinend kleiner. Seltsam.--LotharT (Diskussion) 10:15, 8. Jul. 2016 (CEST)

RelativeDistance(a,b)

Ich nutze zum Integrieren eines kleinen Intervalls auch gern die Romberg-Integration, deren rekursive Berechnung ich genau dann abbreche, wenn zwei aufeinander folgende berechnete Integralsummen (S_i-1, S_i+0) relativ dicht beieinander liegen. Wie dicht sie konkret beieinander liegen sollen, wird dabei über die geforderte Genauigkeit bestimmt (z.B. ForcedPrecision=+10^-06 für ca. 6 korrekte Dezimalstellen), welche dem Romberg-Integrations-Algorithmus als Parameter mitzugegeben ist. Mathematisch ausgedrückt, breche ich die rekursive Romberg-Integration, wie fast jede andere konvergierende rekursive Berechnung meistens genau ab, wenn folgende logische Bedingung erfüllt ist:

   (-ForcedPrecision <= getRelativeDistance(Si-1, Si-0) <= +ForcedPrecision)

oder logisch äquivalent

   (abs(getRelativeDistance(Si-1, Si-0)) <= +ForcedPrecision)

Dabei hat die von mir verwendete Mini-Funktion getRelativeDistance(a,b) folgende, wie ich finde, positive mathematische Eigenschaften:

(0) (getRelativeDistance(a,b) == getRelativeDistance(x,y)) gdw ((x = c * a) und (y = c * b) mit (c # 0)) // größenunabhängig eben relativ
(1) (-2.0 <= getRelativeDistance(a,b) <= +2.0) // nach oben und unten begrenzt
(2) (a > b) gdw (getRelativeDistance(a,b) > 0) // kleiner werdende Summenfolge
(3) (a < b) gdw (getRelativeDistance(a,b) < 0) // groeßer werdende Summenfolge
(4) (abs(getRelativeDistance(a,b)) = 2.0) gdw (sgn(a) # sgn(b)) und (abs(a) = abs(b)) // verschiedene Vorzeichen, gleiche Beträge ==> maximale relative Entfernung
(5) (abs(getRelativeDistance(a,b)) > 1.0) gdw (sgn(a) # sgn(b)) und (abs(a) # abs(b)) // verschiedene Vorzeichen, verschiedene Beträge ==> große relative Entfernung
(6) (abs(getRelativeDistance(a,b)) = 1.0) gdw ((a # b) und ((a = 0) oder (b = 0))) // genau ein Wert ist 0 ==> mittlere relative Entfernung
(7) (abs(getRelativeDistance(a,b)) > 0.0) gdw (sgn(a) = sgn(b)) und (abs(a) # abs(b)) // gleiche Vorzeichen, verschiedene Beträge ==> kleine relative Entfernung
(8) (abs(getRelativeDistance(a,b)) = 0.0) gdw (sgn(a) = sgn(b)) und (abs(a) = abs(b)) // gleiche Vorzeichen, gleiche Beträge ==> gar keine relative Entfernung

Wird ein Integrationsergebnis mit dem Wert 0 erwartet (z.B. Integral(sin(von 0*PI bis 2*PI)), dann kann es sein, dass die rekursiv berechneten Integrationssummen zwar betragsmäßig immer kleiner werden, aber stets wechselnde Vorzeichen haben, also von beiden Seiten gegen den Wert 0 konvergieren (z.B. S_i+0=+1/1; S_i+1=-1/2; S_i+2=+1/4; S_i+3=-1/8; ...), womit immer Eigenschaft (5) zuschlagen und somit zu einer Endlosrekursion führen würde. Dem kann aber ganz einfach dadurch abgeholfen werden, in dem man einen ausreichend großen konstanten positiven Wert (hier z.B. C=+1) auf die jeweils berechneten Integrationssummen aufaddiert (also S_i+0=C+1/1; S_i+1=C-1/2; S_i+2=C+1/4; S_i+3=C-1/8; ...), so dass die berechneten Integrationssummen nun stets das gleiche Vorzeichen haben und sich dem Wert C#0, statt dem Wert 0 von beiden Seiten annähern, welchen man dann natürlich aber hinterher vom zurückgebenen Integrationsergebnis wieder abziehen muss.

In der derzeitigen 64Bit-Computer-Realität, und somit fernab von jeder theoretischen Mathematik zeigt sich jedoch, dass die Eigenschaft (6) auch dann zu schlägt, wenn keiner der beiden betrachteten Werte gleich 0 aber der absolute Größenunterschied der beiden Werte a und b dafür sehr groß ist. Mathematisch völlig unerwartet und mathematisch falsch aber trotzdem Realität ist, dass z.B. bei den Werten a=+10⁺³⁰ b=+10⁺¹⁰ oder a=10⁺⁰¹ und b=10^-15 die Differenz (a - b) = a ist, so als wäre der Wert (b # 0) gar nicht von dem Wert (a >> b) abgezogen worden. Das liegt daran, dass bei einem 64 Bit langen Fließkommawert vom Typ double nur 48 Bit Platz für die Mantisse vorgesehen sind und damit meist nur 14, maximal 15, aber jedenfalls nicht endlos viele Dezimalstellen zur Verfügung stehen. Wenn sich die beiden Werte a und b aber erst nach der 15ten Dezimalstelle unterscheiden, entspricht sowohl die Differenz (a-b) als auch die Summe (a+b) dem Wert mit dem größeren Betrag und der betragsmäßig kleinere Wert wird so behandelt, als wäre er gleich 0. Dieser durchaus praxisrelevante Fall dürfte aber bei der rekursiven Romberg-Integration kleiner Intervalle nicht auftreten, da sich zwei aufeinander folgende rekursiv berechnete Intergalsummen S_i-1 und S_i-0 keinesfalls so massiv voneinander unterscheiden sollten.

Wenn die geforderte Genauigkeit einen sinnvollen Wert z.B. ((MaximalPrecision=+10^-14) <= ForcedPrecision <= (MinimalPrecision=+10^-01)) hat, sind eigentlich nur noch die Eigenschaften (7) und (8) von besonderem Interesse. Was nun noch zu zeigen bleibt, ist der PseudoCode der von mir verwendeten Mini-Funktion getRelativeDistance:

double getRelativeDistance(double S_i-1, double S_i-0)
{

   if(Si-1 = Si-0) then
       return(0);
   else
       return((Si-1 - Si-0) / max(abs(Si-1), abs(Si-0)));
   end;

}

Ich würde mich freuen, wenn ich mit der Mini-Funktion getRelativeDistance(a,b), wenigstens das Problem, wann die rekursive Romberg-Integration eines kleinen Intervalls am sinnvollsten abzubrechen ist, weitestgehend gelöst hätte. --Aragorn321 (Diskussion) 12:27, 15. Nov. 2016 (CET)

Optimiertes versus Originales Romberg-Integrations-Verfahren

Der originale Romberg-Integrations-Algorithmus hat noch mehrere versteckte, teilweise schon angesprochene Probleme, die seine Praxistauglichkeit auch im Computerzeitalter stark beeinträchtigen.

Eines davon sind Funktionen, deren Anstiege sich in einzelnen Punkten schlagartig ändern. Man stelle sich dazu nur einmal vor, man möchte mit dem Romberg-Integrations-Algorithmus das Integral von a bis b einer Funktion berechnen, die von (a < c) bis c linear ansteigt und von c bis (b > c) linear abfällt, also quasi ein Dreieck mit dem Scheitelpunkt bei c. Da sich lineare Funktionen mit dem Romberg-Integrations-Algorithmus eigentlich sehr leicht und schnell integrieren lassen, weil hier schon (S2 = S1) ist und deshalb die Rekursion bereits bei Rekursionstiefe 2 abgebrochen wird, erwartet man eigentlich keine Probleme. Das stimmt auch, aber nur, wenn man das gesamte Intervall [a,b] vorher vollständig in die beiden disjunkte Teilintervalle [a,c] und [c,b] zerlegt und auf beide Teilintervalle den rekursiven Romberg-Integrations-Algorithmus separat ansetzt und beide erhaltenen Ergebnisse hinterher addiert. Kennt man den Wert von c (also die versteckte Tretmine) aber nicht, was in der Praxis leider oft der Fall ist, kann es durchaus sein, dass der Romberg-Integrations-Algorithmus statt der tatsächlich erforderlichen handvoll von Funktionswerten in Wirklichkeit aber Milliarden von Funktionswerten berechnet, weil er locker Rekursionstiefen von 30 und mehr erreicht, nur um die geforderte Genauigkeit zu erreichen.

Hinweis: 2¹⁰ = 1.024 > 1 Tausend; 2²⁰ = 1.048.576 > 1 Million; 2³⁰ = 1.073.741.824 > 1 Milliarde;

Es gibt aber auch massive Probleme bei stetigen Funktionen, deren Anstiege sich also nicht schlagartig ändern. Man betrachte dazu nur mal die Funktion y=f(x^1/100) also die 100ste Wurzel von x im Bereich von (a=0) bis (b=1000). Im Teilintervall [0,1] steigt die Funktion erst sehr stark an um danach im zweiten Teilintervall [1,1000] immer flacher zu werden. Das erste steilere Teilintervall läßt sich äußerst schlecht integrieren und es werden große Rekursionstiefen erreicht, wohingegen das zweite flachere Teilintervall wesentlich leichter integrierbar ist und deshalb auch nur kleine Rekursionstiefen erreicht werden. Dieses Prinzip der vollständigen Zerlegung eines großen Gesamtintervalls in mehrere kleinere und disjunkte Teilintervalle unterschiedlicher Länge läßt sich zwar immer mehr auf die Spitze treiben: z.B. (x₀=0, x₁=2^-30, x₂=2^-29, x₃=2^-28, ..., x₃₀=2^-1, x₃₁=2⁰, x₃₂=2⁺¹... x₄₁=2⁺¹⁰) wo das j-te Teilintervall T_j der Bereich zwischen x_j-1 und x_j-0 ist. Natürlich muss hier für alle j gelten (x_j-1 < x_j-0). Trotzdem macht das Teilintervall mit dem sich am stärksten ändernden Anstieg, also in unserem Fall das erste Teilintervall, oft noch die meisten Probleme beim Integrieren.

Dies ändert sich schlagartig, wenn man nicht mehr "spaltenweise" vorgeht, also die einzelnen Teilintervalle zuerst separat mit dem originalen Romberg-Integrations-Algorithmus und der geforderten Genauigkeit berechnet und danach erst die erhaltenen Teilergebnisse aufaddiert, sondern wenn man quasi genau anders herum also "zeilenweise" vorgeht. Man berechnet für alle Teilintervalle T_j zuerst nur die Integrationssumme S_1,j , also jeweils nur den ersten Rekursionsschritt, wo pro Teilintervall nur ein einziges Trapez berechnet wird. Alle so erhaltenen Teilsummen S_1,j addiert man zu der ersten Gesamtsumme oder Zeilensumme S₁=Σ(S_1,j). Im zweiten Schritt errechnet man für alle Teilintervalle T_j die Integrationssumme S_2,j , also jeweils nur den zweiten Rekursionsschritt, wo jetzt schon zwei Trapeze (also allgemein doppelt soviel, wie im vorherigen Rekursionsschritt) pro Teilintervall berechnet werden. Daraus generiert man nun die zweite Gesamtsumme oder Zeilensumme S₂=Σ(S_2,j). So macht man "zeilenweise" weiter. Man läßt jetzt aber sinnvollerweise den gesamten Algorithmus bereits schon dann terminieren, wenn (abs(getRelativeDistance(S_i-1, S_i-0) <= +ForcedPrecision) ist. Es sind also nicht mehr die Teilsummen S_i,j der einzelnen Teilintervalle T_j, die das Abbruchkriterium bestimmen, sondern nur noch die berechneten Gesamt- oder Zeilensummen S_i.

Dieses "zeilengetriebe" Vorgehen spart schon sehr viele überflüssige Funktionswertberechnungen ein. Aber richtig effektiv wird dieses optimierte Romberg-Integrations-Verfahren erst dann, wenn man sich in einem IgnoriereMichFlag pro Teilintervall aufhebt, ob es überhaupt noch einen Sinn macht, für dieses Teilintervall T_j noch weitere Rekursionsstufen zu berechnen. Es könnte ja durchaus sein, dass die aktuelle Teilsumme S_i,j oder die Differenz zweier aufeinander folgender Teilsummen DS_i,j = (S_i-0,j - S_i-1,j) relativ zur aktuellen Gesamtsumme S_i-0 inzwischen schon so klein geworden ist, dass deren Addition auf einem 64 Bit großen Fließkommawert (also in der heutigen 64-Bit-Realität) keinerlei Effekt mehr hat, und somit die Eigenschaft (6) der obigen Mini-Funktion (getRelativeDistance(S_i , S_i,j) <= ForcedPrecision) z.B. für die 2 Teilintervalle [-2^-10,-2^-09] , [+2^-09,+2^-10] der Standard-Gauß-Funktion, oder (getRelativeDistance(S_i , DS_i,j) <= ForcedPrecision) z.B. für die 3 Teilintervalle [-2^-19,-2^-20] , [-2^-20,+2^-20] , [+2^-20,+2^-19] der Standard-Gauß-Funktion ab sofort vermutlich ständig zuschlägt. Das werden pro Rekursionsschritt in der Regel immer mehr Teilintervalle, deren Neuberechnungen absofort ignoriert werden können.

Man kann in der Praxis daher oft, ohne irgendwelche Genauigkeitsverluste hinnehmen zu müssen, durch eine geschickte integrationsunterstützende und vollständige Zerlegung des Gesamtintervalls in unterschiedlich lange diskunkte Teilintervalle, das originale Romberg-Integrations-Verfahren durchaus um den Faktor 10⁺⁰⁶ und mehr beschleunigen, wenn man schwierig zu integrierende Abschnitte möglichst klein und leicht zu integrierende Abschnitte dagegen möglichst groß wählt. Man würde also nicht mehr zig Milliarden von Funktionswerten berechnen, von denen die allermeisten absolut überflüssig sind, sondern man würde nur noch wenige Tausende Funktionswerte berechnen, die aber nun fast alle erforderlich sind.

Über weitere inhaltliche Verbesserungsvorschläge bzgl. des Romberg-Integrations-Verfahrens würde ich mich freuen. --Aragorn321 (Diskussion) 16:30, 15. Nov. 2016 (CET)

Fourier-Integral hat die Nullstellen an den falschen Stellen

Im Abschnitt der im Artikel aktuell "Anmerkungen" heißt steht, dass das Romberg-Verfahren schlecht funktioniert für solch geartete Funktionen, weil die Stützstellen der Trapezregel mit den Nullstellen des Cosinus-Anteils des Integranden zusammenfällt. Meines Erachtens nach stimmt das aber nicht, bspw wären die Stützstellen der Trapezregel in der dritten Iteration $0,\pi /2,\pi ,3\pi /4,2\pi$ wovon aber keine eine Nullstelle von $\cos(2^{n}x)$ ist. Vielmehr sollte der Integrand $f(x)\sin(2^{n}x)$ lauten, denn dann fallen die Nullstellen tatsächlich mit den Stützstellen zusammen. (nicht signierter Beitrag von 134.99.156.75 (Diskussion) 10:40, 10. Jun. 2021 (CEST))