Romberg-Extrapolation

Romberg-Extrapolation

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

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 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 h_n=\frac{b-a}{2^n}, das zugleich die Bedingungen für eine konvergente Extrapolation erfüllt. Also

1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\dots

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:

1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{6},\frac{1}{8},\dots

Hier werden Glieder mit \frac{2}{3} zwischengeschaltet.

Rechenvorschrift

 I = \int_a^b f(x)\mathrm{d}x  = \lim_{n \to \infty} I_{n,1}

mit

 I_{n,k} = I_{n+1,k-1} + \frac{I_{n+1,k-1} - I_{n,k-1} }{\left(\frac{h_n}{h_{n+1}}\right)^{2(k-1)} - 1  }

dabei ist

 I_{1,1} =  \frac{h_1}{2} (f(a)+f(b))     (Trapezregel)
 I_{n,1} =  \frac{h_n}{2} \left( f(a)+ f(b) + 2\sum_{i=1}^{\frac{h_1}{h_n}-1} f \left( a + i\,h_n \right) \, \right)  (aufsummierte Trapezregel mit mehrfachen Intervallen)

und

 k \in [ 1 , n+1] \quad  \in \mathbb{N}
h_1= b-a \,
hn die im n-ten Schritt verwendete Schrittweite (siehe oben)

das Fehlerglied hat den Wert:

 E = \frac{I_{1, n + 1} -  I_{1, n}} { I_{1, n} }

Vorgehensweise


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


  1. Zuerst wird I1,1 berechnet.
  2. Beginne eine zyklische Berechnung (Hauptzyklus) mit der Zyklusvariablen n mit n = 1 und berechne In + 1,1. Nutze dabei Werte aus den vorhergehenden Zyklen aus, abhängig von der verwendeten Schrittweiten-Folge.
  3. Extrapoliere in einem Unterzyklus mit
    k = 2 bis n + 1 und s = 2 + n - k
    den Wert Is,k nach obiger Regel
  4. Berechne die Genauigkeit. 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 (Romberg-Folge):

  • Berechnen von I1,1 nach der Trapezregel
  • Hauptzyklus starten mit n = 1
  • Berechnen von In + 1,1 = I2,1 nach der Trapezregel (2 Intervalle, 21 = 2). Es muss nur der mittlere Funktionswert neu berechnet werden:

I_{2,1} = h_2 \left( f(a)+f(b) + 2\sum_{i=1}^{2^{2-1}-1} f( a + i\,h_2) \, \right)  \quad       = \frac{b-a}{2 \cdot 2} \left( f(a)+f(b) + 2 f(a+h_2) \right)   \quad      = \frac{I_{1,1}}{2}+h_2*f(a+h_2)

  • Unterzyklus: k geht von 2 bis 2 .
    • 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  }
    • \  E = \frac{I_{1, 2} -  I_{1, 1}} { I_{1, 1} }
  • Neuer Durchgang des Hauptzyklus mit n = 2 .
  • Berechnen von \ I_{n+1,1} = I_{3,1} nach der Trapezregel (4 Intervalle, 22 = 4, zwei neue Funktionswerte).

  I_{3,1}      = \frac{I_{2,1}}{2}+h_3 \sum_{i=1}^{2}f(a+(2i-1)\,h_3)

  • Unterzyklus: k geht von 2 bis 3 .
    • \ k = 2 und s = 2 \ ; \quad  I_{s,k} = I_{2,2} = \frac{4^1 * I_{3,1} - I_{2,1} }{4^1 - 1  }
    • \ k = 3 und s = 1 \ ; \quad  I_{s,k} = I_{1,3} = \frac{4^2 * I_{2,2} - I_{1,2} }{4^2 - 1  }
    • \ E = \frac{I_{1, 3} -  I_{1, 2}} { I_{1, 2} }
  • Neuer Durchgang des Hauptzyklus mit n= 3 .
  • Berechnen von In + 1,1 = I4,1 nach der Trapezregel 8 Intervalle, 23 = 8, 4 neue Funktionswerte).
  • Unterzyklus: k geht von 2 bis 4 .
    • \ k = 2 und s = 3 \ ; \quad I_{s,k} = I_{3,2} = \frac{4^1 * I_{4,1} - I_{3,1} }{4^1 - 1  }
    • \ k = 3 und s = 2 \ ; \quad I_{s,k} = \frac{4^2 * I_{3,2} - I_{2,2} } {4^2 - 1  }
    • \ k = 4 und s = 1 \ ; \quad I_{s,k} = \frac{4^3 * I_{2,3} - I_{1,3} }{4^3 - 1  }
    • \ E = \frac{I_{1, 4} -  I_{1, 3}} { I_{1, 3} }
  • Neuer Durchgang des Hauptzyklus mit n = 4
usw.

Quellcode

// java source code
public interface numericalIntegrationInterface
{
  public double computeFunction(double x);
}

public class numericalIntegration
{
  // a ... integral from
  // b ... integral to
  double a,b;

  // the function of which we want to compute the area
  numericalIntegrationInterface f;

  public numericalIntegration(double rangeFrom, double rangeTo, numericalIntegrationInterface function)
  {
    a = rangeFrom;
    b = rangeTo;
    if (a > b)
    {
      double temp = a;
      a = b;
      b = temp;
    }
    f = function;
  }

  private int pow(int a, int b)
  {
    if (b == 0)
      return 1;

    if (b == 1)
      return a;

    int result = a;

    for (int i = 1; i < b; i++)
      result *= a;

    return result;
  }

  private double computeI_n_k(int n, int k, double I[][])
  {
    return (pow(4,k-1)*I[n+1][k-1]-I[n][k-1])/(pow(4,k-1) - 1.0);
  }

  private double computeI_n_1(int n)
  {
    double temp = 0;
    int steps = pow(2,n);
    
    for (int i = 1; i <= steps-1; i++)
      temp += f.computeFunction(a + ((i * (b-a))/ steps ) );
    
    return ((b-a)/(2*steps)) * (f.computeFunction(a) + f.computeFunction(b) + 2*temp);
  }
  
  private double computeError(int n, double I[][])
  {
    return (I[1][n+1] - I[1][n])/I[1][n];
  }
  
  public double computeAreaRomberg(double maxError, int minIt, int maxIt)
  {
    if (a == b) return 0.0;

    double I[][] = new double[maxIt+2][maxIt+2];   
    double error = Double.MAX_VALUE;
    
    int n,s,k;
    
    I[1][1] = ((b-a)/2.0) * (f.computeFunction(a) + f.computeFunction(b));
    
    for (n = 1; (n <= minIt || error > maxError) && n <= maxIt; n++)
    {
      I[n+1][1] = computeI_n_1(n); 
      
      for (k = 2; k <= n+1; k++)
      {
        s = 2 + n - k;        
        I[s][k] = computeI_n_k(s,k,I);
      }
      
      error = Math.abs(computeError(n,I));      
    }
    
    return I[n][1];
  }
}

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

 \int_{0}^{2 \pi} f(x) \cdot \cos(2^n x) \mathrm{d}x

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.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Extrapolation De Richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson, qui l a introduit au début du XXe siècle. Ce procédé est notamment… …   Wikipédia en Français

  • Extrapolation de richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson, qui l a introduit au début du XXe siècle. Ce procédé est notamment… …   Wikipédia en Français

  • Extrapolation de Richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson[1],[2], qui l a introduit au début du XXe siècle. Ce procédé est… …   Wikipédia en Français

  • Romberg-Schema — 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 1 Grundgedanke 2… …   Deutsch Wikipedia

  • Romberg-Verfahren — 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 1 Grundgedanke 2… …   Deutsch Wikipedia

  • Romberg-Integration — 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 1 Grundgedanke 2… …   Deutsch Wikipedia

  • Romberg's method — In numerical analysis, Romberg s method Harv|Romberg|1955 generates a triangular array consisting of numerical estimates of the definite integral: int a^b f(x) , dx by using Richardson extrapolation Harv|Richardson|1910 repeatedly on the… …   Wikipedia

  • Extrapolation — Unter Extrapolation wird die Bestimmung eines (oft mathematischen) Verhaltens über den gesicherten Bereich hinaus verstanden. Eine statistische Extrapolation bezeichnet man auch als Hochrechnung. Eine andere Herangehensweise ist die Interpolation …   Deutsch Wikipedia

  • Methode de Romberg — Méthode de Romberg En analyse numérique, la méthode d intégration de Romberg est une méthode récursive de calcul numérique d intégrale, basée sur l application du procédé d extrapolation de Richardson à la méthode des trapèzes. Cette technique d… …   Wikipédia en Français

  • Méthode De Romberg — En analyse numérique, la méthode d intégration de Romberg est une méthode récursive de calcul numérique d intégrale, basée sur l application du procédé d extrapolation de Richardson à la méthode des trapèzes. Cette technique d accélération permet …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”