Zum Inhalt springen

Romberg-Integration

aus Wikipedia, der freien Enzyklopädie

Die Romberg-Integration ist ein Verfahren zur numerischen Bestimmung von Integralen und wurde von Werner Romberg 1955<ref>Romberg, Vereinfachte Numerische Integration, Kgl.Norske Vid. Selsk. Forsk., Band 28, 1955, S. 30–36</ref> entwickelt. Sie ist eine Verbesserung der (Sehnen)-Trapezregel durch Extrapolation.

Grundgedanke

Die Romberg-Integration basiert auf der Richardson-Extrapolation zum Limes über die Schrittweite einer summierten Quadraturformel, wie beispielsweise der Trapezregel. Die Trapezregel ist hier besonders zu erwähnen, da sie einfach zu berechnen ist und zudem eine Entwicklung in quadratischen Potenzen der Schrittweite besitzt, also eine Extrapolation in Quadraten der Schrittweite möglich ist, die deutlich schneller konvergiert als die einfache Extrapolation zum Limes. Mit Schrittweite h ist hier die Breite der Trapeze bei der Trapezregel gemeint.

Der aufwändige Teil der numerischen Integration ist oft die Auswertung der Funktionen. 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>\textstyle{h_n=\frac{b-a}{2^{n-1}}}</math>, das zugleich die Bedingungen für eine konvergente Extrapolation erfüllt. Also

<math>1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\dots</math>

Bei dieser sogenannten Romberg-Folge wächst die Anzahl der benötigten Funktionsauswertungen bei großen n schnell an, was nicht immer erwünscht ist.

Um diesem abzuhelfen, kann auch die Bulirsch-Folge verwendet werden:

<math>1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{6},\frac{1}{8},\dots</math>

Hier werden Glieder mit <math>\frac{2}{3}</math> zwischengeschaltet.

Rechenvorschrift

Man nähert das Integral <math>I[f] = \int_a^b f(x) \, \mathrm dx</math> mit der Hilfe von Trapezsummen <math>T=T(h)</math> mit verschiedenen Schrittweiten <math>h</math> an. Dabei nimmt man an, dass der Grenzwert <math>I[f] = \lim_{h \, \to \, 0 } T(h)</math> erfüllt wird.

Die Rechenvorschrift der Romberg-Integration lautet nun wie folgt<ref>{{#invoke:Vorlage:Literatur|f}}</ref>.

  1. Bestimme die Trapezsummen <math>T=T(h)</math> zu Schrittweiten <math>\left( h_i \right)_{i=1, \, \ldots \, ,m}</math>. Dies definiert <math> T_{i,1}:=T(h_i) \, , i=1, \, \ldots \, ,m \, .</math>
  2. Mittels des Neville-Aitken-Schemas wird das Interpolationspolynom bei <math>h=0</math> ausgewertet <math>

T_{i,k} := T_{i,k-1} + 

   \frac{ T_{i,k-1}-T_{i-1,k-1} }
   { \left( 
       \frac{ h_{i-k+1} }{ h_i } 
   \right)^2 -1 }
   \, \quad
   \text{mit}
   \quad
   2 \leq k \leq i
   \, .

</math>

Anmerkungen

  • Im ersten Schritt berechnet man also die Datenpunkte <math>\left( h_i, T(h_i) \right)_{i=1, \, \ldots \, ,m}</math>. Aufgrund der asymptotischen Fehlerentwicklung der Trapezsumme (es kommen nur Potenzen von <math>h^2</math> vor) wird im zweiten Schritt ein Interpolationspolynom zu den Datenpunkten <math>\left( h_i^2, T(h_i) \right)_{i=1, \, \ldots \, ,m}</math> benutzt.
  • Im zweiten Schritt wird nicht das vollständige Interpolationspolynom bestimmt, sondern nur die Auswertung an einem bestimmten Punkt: <math>h=0</math>. Dies funktioniert besonders effizient mit dem Neville-Aitken-Schema.
  • Das Neville-Aitken-Schema liefert eine Approximation des Integrals mittels <math>T_{m,m} \approx I[f]</math>.
  • Die Durchführung des Neville-Aitken-Schema muss in der „richtigen“ Reihenfolge geschehen. Das folgende Extrapolationstableau soll dies verdeutlichen (man geht spaltenweise vor: zuerst die erste Spalte bestimmen, dann die zweite etc.)
<math>

\begin{matrix} T_{1,1} \\ &\searrow \\ T_{2,1} & \rightarrow & T_{2,2} \\ \vdots & & & \ddots \\ T_{k-1,1} & \rightarrow & \cdots & \rightarrow & T_{k-1,k-1} \\ &\searrow & & \searrow & & \searrow \\ T_{k,1} & \rightarrow & \cdots & \rightarrow & T_{k,k-1} & \rightarrow & T_{k,k} \, . \end{matrix} </math>

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 Fourieranalyse periodischer Funktionen vorkommende Integral

<math> \int_{0}^{2 \pi} f(x) \cdot \cos(2^n x) \mathrm{d}x </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.

Literatur

  • Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4. überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065765-4.
  • Josef Stoer: Numerische Mathematik 1, 8. neu bearbeitete und erweiterte Auflage. Springer-Lehrbuch, ISBN 3-540-66154-9, S. 161 ff.

Weblinks

  • <templatestyles src="Webarchiv/styles.css" />{{#if:20070929103333
      | {{#ifeq: 20070929103333 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20070929103333}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20070929103333}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Romberg-Integration | {{#invoke:WLink|getEscapedTitle|Romberg-Integration}} | {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20070929103333|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz}}
    || {{#if:  || }}
  }}{{#if: Romberg-Integration
    | {{#if: {{#invoke:WLink|isBracketedLink|Romberg-Integration}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://freenet-homepage.de/p-st/projects/romberg_v1.0.tar.gz }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} – Plugin für Yacas

Einzelnachweise

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Romberg-Integration&oldid=338816“