Namespaces
Variants
Actions

Difference between revisions of "Romberg method"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Undo revision 48584 by Ulf Rehmann (talk))
Tag: Undo
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
r0825701.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/R082/R.0802570 Romberg method,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''Romberg rule''
 
''Romberg rule''
  
A method for calculating a definite integral based on [[Richardson extrapolation|Richardson extrapolation]]. Suppose a value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825701.png" /> of some functional is to be calculated; also, let a calculated approximate value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825702.png" /> depend on a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825703.png" /> so that as a result of the computations one obtains an approximate equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825704.png" />. Let some information be known concerning the behaviour of the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825705.png" /> as a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825706.png" />, namely,
+
A method for calculating a definite integral based on [[Richardson extrapolation|Richardson extrapolation]]. Suppose a value $  I $
 +
of some functional is to be calculated; also, let a calculated approximate value $  T ( h) $
 +
depend on a parameter $  h $
 +
so that as a result of the computations one obtains an approximate equality $  I \cong T ( h) $.  
 +
Let some information be known concerning the behaviour of the difference $  I - T ( h) $
 +
as a function of $  h $,  
 +
namely,
 +
 
 +
$$ \tag{1 }
 +
I - T ( h)  =  \alpha h  ^ {m} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825707.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
where  $  m $
 +
is a positive integer and  $  \alpha $
 +
depends on the functional to be approximated, on the function on which this functional is calculated, on the approximating method, and (weakly) on  $  h $.  
 +
If simultaneously with  $  T ( h) $,
 +
$  T ( 2h) $
 +
is calculated, then by Richardson's method one obtains for  $  I $
 +
the approximation
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825708.png" /> is a positive integer and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r0825709.png" /> depends on the functional to be approximated, on the function on which this functional is calculated, on the approximating method, and (weakly) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257010.png" />. If simultaneously with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257012.png" /> is calculated, then by Richardson's method one obtains for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257013.png" /> the approximation
+
$$ \tag{2 }
 +
I  \cong \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
\frac{2  ^ {m} T ( h) - T ( 2h) }{2 ^ {m} - 1 }
 +
.
 +
$$
  
This approximation is the better, the weaker the dependence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257015.png" /> in (1) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257016.png" />. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257017.png" /> is independent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257018.png" />, then (2) becomes an exact equality.
+
This approximation is the better, the weaker the dependence of $  \alpha $
 +
in (1) on $  h $.  
 +
In particular, if $  \alpha $
 +
is independent of $  h $,  
 +
then (2) becomes an exact equality.
  
 
Romberg's method is used to calculate an integral
 
Romberg's method is used to calculate an integral
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257019.png" /></td> </tr></table>
+
$$
 +
= \int\limits _ { 0 } ^ { 1 }  f ( x)  dx .
 +
$$
  
The interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257020.png" /> is chosen to facilitate the writing; it can be any finite interval, however. Let
+
The interval $  [ 0 , 1 ] $
 +
is chosen to facilitate the writing; it can be any finite interval, however. Let
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
T _ {k0}  = 2  ^ {-} k- 1
 +
\left [ f ( 0) + 2
 +
\sum _ { j= } 1 ^ { {2  ^ {k}} - 1 }
 +
f ( j 2  ^ {-} k ) + f ( 1) \right ] ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257022.png" /></td> </tr></table>
+
$$
 +
= 0 , 1 , .  . . .
 +
$$
  
 
Calculations by Romberg's method reduce to writing down the following table:
 
Calculations by Romberg's method reduce to writing down the following table:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257023.png" /></td> </tr></table>
+
$$
  
where in the first column one finds the quadrature sums (3) of the [[Trapezium formula|trapezium formula]]. The elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257024.png" />-nd column are obtained from the elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257025.png" />-st column by the formula
+
\begin{array}{ccccc}
 +
T _ {00}  &T _ {01}  &\dots  &T _ {0, n- 1 }  &T _ {0n}  \\
 +
T _ {10}  &T _ {11}  &\dots  &T _ {1 , n- 1 }  &{}  \\
 +
\dots  &\dots  &\dots  &{}  &{}  \\
 +
T _ {n- 2 ,0 }  &T _ {n- 2 ,1 }  &{T _ {n-} 2,2 }  &{}  &{}  \\
 +
T _ {n- 1 , 0 }  &T _ {n- 1 ,1 }  &{}  &{}  &{}  \\
 +
T _ {n0}  &{}  &{}  &{}  &{}  \\
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257026.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$
 +
 
 +
where in the first column one finds the quadrature sums (3) of the [[Trapezium formula|trapezium formula]]. The elements of the  $  ( l+ 2 ) $-
 +
nd column are obtained from the elements of the  $  ( l+ 1) $-
 +
st column by the formula
 +
 
 +
$$ \tag{4 }
 +
T _ {k , l+ 1 }  = \
 +
 
 +
\frac{2 ^ {2l + 2 } T _ {k+ 1 , l }  - T _ {kl} }{2 ^ {2l + 2 } - 1 }
 +
,\ \
 +
k = 0 \dots n- l- 1 .
 +
$$
  
 
When writing down the table, the main calculating effort is concerned with calculating the elements of the first column. The calculation of the elements of the following columns is a bit more complicated than the calculation of finite differences.
 
When writing down the table, the main calculating effort is concerned with calculating the elements of the first column. The calculation of the elements of the following columns is a bit more complicated than the calculation of finite differences.
  
Each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257027.png" /> in the table is a quadrature sum approximating the integral:
+
Each element $  T _ {kl} $
 +
in the table is a quadrature sum approximating the integral:
 +
 
 +
$$ \tag{5 }
 +
I  \cong  T _ {kl} .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257028.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
The nodes of the quadrature sum  $  T _ {kl} $
 +
are the points  $  j 2  ^ {-} k- l $,
 +
$  j = 0 \dots 2  ^ {k+} l $,
 +
and its coefficients are positive numbers. The quadrature formula (5) is exact for all polynomials of degree not exceeding  $  2l + 1 $.
  
The nodes of the quadrature sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257029.png" /> are the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257031.png" />, and its coefficients are positive numbers. The quadrature formula (5) is exact for all polynomials of degree not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257032.png" />.
+
Under the assumption that the integrand has a continuous derivative on  $  [ 0 , 1 ] $
 +
of order  $  2l + 2 $,
 +
the difference  $  I - T _ {kl} $
 +
can be represented in the form (1), where  $  m = 2l + 2 $.  
 +
Hence it follows that the elements of the $  ( l+ 2 ) $-
 +
nd column, calculated by formula (4), are better Richardson approximations than the elements of the  $  ( l+ 1 ) $-
 +
st column. In particular, the following representation is valid for the error of the quadrature trapezium formula
  
Under the assumption that the integrand has a continuous derivative on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257033.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257034.png" />, the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257035.png" /> can be represented in the form (1), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257036.png" />. Hence it follows that the elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257037.png" />-nd column, calculated by formula (4), are better Richardson approximations than the elements of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257038.png" />-st column. In particular, the following representation is valid for the error of the quadrature trapezium formula
+
$$
 +
I - T _ {k0}  = \
 +
-
 +
\frac{f ^ { \prime\prime } ( \xi ) }{12}
 +
h  ^ {2} ,\ \
 +
h = 2  ^ {-} k ,\  \xi \in [ 0 , 1 ] ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257039.png" /></td> </tr></table>
+
and the Richardson method provides a better approximation to  $  I $:
  
and the Richardson method provides a better approximation to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257040.png" />:
+
$$
 +
T _ {k1}  = \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257041.png" /></td> </tr></table>
+
\frac{4 T _ {k+ 1 , 0 }  - T _ {k0} }{3}
 +
,\ \
 +
k = 0 \dots n- 1 .
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257042.png" /> turns out to be a quadrature sum of the [[Simpson formula|Simpson formula]], and since for the error of this formula the following representation holds:
+
$  T _ {k1} $
 +
turns out to be a quadrature sum of the [[Simpson formula|Simpson formula]], and since for the error of this formula the following representation holds:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257043.png" /></td> </tr></table>
+
$$
 +
I - T _ {k1}  = \
 +
-
 +
\frac{f ^ { ( iv ) } ( \eta ) }{180}
 +
h  ^ {4} ,\ \
 +
h = 2  ^ {-} k- 1 ,\  \eta \in [ 0 , 1 ] ,
 +
$$
  
 
one can again use the Richardson method, etc.
 
one can again use the Richardson method, etc.
  
In Romberg's method, to approximate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257044.png" /> one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257045.png" />; also, one assumes the continuous derivative <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257046.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257047.png" /> to exist. A tentative idea of the precision of the approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257048.png" /> can be obtained by comparing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257049.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r082/r082570/r08257050.png" />.
+
In Romberg's method, to approximate $  I $
 +
one takes $  T _ {0n} $;  
 +
also, one assumes the continuous derivative $  f ^ { ( 2n) } ( x ) $
 +
on $  [ 0 , 1 ] $
 +
to exist. A tentative idea of the precision of the approximation $  T _ {0n} $
 +
can be obtained by comparing $  T _ {0n} $
 +
to $  T _ {1 , n- 1 }  $.
  
 
This method was for the first time described by W. Romberg [[#References|[1]]].
 
This method was for the first time described by W. Romberg [[#References|[1]]].

Revision as of 14:55, 7 June 2020


Romberg rule

A method for calculating a definite integral based on Richardson extrapolation. Suppose a value $ I $ of some functional is to be calculated; also, let a calculated approximate value $ T ( h) $ depend on a parameter $ h $ so that as a result of the computations one obtains an approximate equality $ I \cong T ( h) $. Let some information be known concerning the behaviour of the difference $ I - T ( h) $ as a function of $ h $, namely,

$$ \tag{1 } I - T ( h) = \alpha h ^ {m} , $$

where $ m $ is a positive integer and $ \alpha $ depends on the functional to be approximated, on the function on which this functional is calculated, on the approximating method, and (weakly) on $ h $. If simultaneously with $ T ( h) $, $ T ( 2h) $ is calculated, then by Richardson's method one obtains for $ I $ the approximation

$$ \tag{2 } I \cong \ \frac{2 ^ {m} T ( h) - T ( 2h) }{2 ^ {m} - 1 } . $$

This approximation is the better, the weaker the dependence of $ \alpha $ in (1) on $ h $. In particular, if $ \alpha $ is independent of $ h $, then (2) becomes an exact equality.

Romberg's method is used to calculate an integral

$$ I = \int\limits _ { 0 } ^ { 1 } f ( x) dx . $$

The interval $ [ 0 , 1 ] $ is chosen to facilitate the writing; it can be any finite interval, however. Let

$$ \tag{3 } T _ {k0} = 2 ^ {-} k- 1 \left [ f ( 0) + 2 \sum _ { j= } 1 ^ { {2 ^ {k}} - 1 } f ( j 2 ^ {-} k ) + f ( 1) \right ] , $$

$$ k = 0 , 1 , . . . . $$

Calculations by Romberg's method reduce to writing down the following table:

$$ \begin{array}{ccccc} T _ {00} &T _ {01} &\dots &T _ {0, n- 1 } &T _ {0n} \\ T _ {10} &T _ {11} &\dots &T _ {1 , n- 1 } &{} \\ \dots &\dots &\dots &{} &{} \\ T _ {n- 2 ,0 } &T _ {n- 2 ,1 } &{T _ {n-} 2,2 } &{} &{} \\ T _ {n- 1 , 0 } &T _ {n- 1 ,1 } &{} &{} &{} \\ T _ {n0} &{} &{} &{} &{} \\ \end{array} $$

where in the first column one finds the quadrature sums (3) of the trapezium formula. The elements of the $ ( l+ 2 ) $- nd column are obtained from the elements of the $ ( l+ 1) $- st column by the formula

$$ \tag{4 } T _ {k , l+ 1 } = \ \frac{2 ^ {2l + 2 } T _ {k+ 1 , l } - T _ {kl} }{2 ^ {2l + 2 } - 1 } ,\ \ k = 0 \dots n- l- 1 . $$

When writing down the table, the main calculating effort is concerned with calculating the elements of the first column. The calculation of the elements of the following columns is a bit more complicated than the calculation of finite differences.

Each element $ T _ {kl} $ in the table is a quadrature sum approximating the integral:

$$ \tag{5 } I \cong T _ {kl} . $$

The nodes of the quadrature sum $ T _ {kl} $ are the points $ j 2 ^ {-} k- l $, $ j = 0 \dots 2 ^ {k+} l $, and its coefficients are positive numbers. The quadrature formula (5) is exact for all polynomials of degree not exceeding $ 2l + 1 $.

Under the assumption that the integrand has a continuous derivative on $ [ 0 , 1 ] $ of order $ 2l + 2 $, the difference $ I - T _ {kl} $ can be represented in the form (1), where $ m = 2l + 2 $. Hence it follows that the elements of the $ ( l+ 2 ) $- nd column, calculated by formula (4), are better Richardson approximations than the elements of the $ ( l+ 1 ) $- st column. In particular, the following representation is valid for the error of the quadrature trapezium formula

$$ I - T _ {k0} = \ - \frac{f ^ { \prime\prime } ( \xi ) }{12} h ^ {2} ,\ \ h = 2 ^ {-} k ,\ \xi \in [ 0 , 1 ] , $$

and the Richardson method provides a better approximation to $ I $:

$$ T _ {k1} = \ \frac{4 T _ {k+ 1 , 0 } - T _ {k0} }{3} ,\ \ k = 0 \dots n- 1 . $$

$ T _ {k1} $ turns out to be a quadrature sum of the Simpson formula, and since for the error of this formula the following representation holds:

$$ I - T _ {k1} = \ - \frac{f ^ { ( iv ) } ( \eta ) }{180} h ^ {4} ,\ \ h = 2 ^ {-} k- 1 ,\ \eta \in [ 0 , 1 ] , $$

one can again use the Richardson method, etc.

In Romberg's method, to approximate $ I $ one takes $ T _ {0n} $; also, one assumes the continuous derivative $ f ^ { ( 2n) } ( x ) $ on $ [ 0 , 1 ] $ to exist. A tentative idea of the precision of the approximation $ T _ {0n} $ can be obtained by comparing $ T _ {0n} $ to $ T _ {1 , n- 1 } $.

This method was for the first time described by W. Romberg [1].

References

[1] W. Romberg, "Vereinfachte numerische Integration" Norske Vid. Sels. Forh. , 28 : 7 (1955) pp. 30–36
[2] F.L. Bauer, H. Rutishauser, E. Stiefel, "New aspects in numerical quadrature" N.C. Metropolis (ed.) et al. (ed.) , Experimental Arithmetic, high-speed computing and mathematics , Proc. Symp. Appl. Math. , 15 , Amer. Math. Soc. (1963) pp. 199–218
How to Cite This Entry:
Romberg method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Romberg_method&oldid=49568
This article was adapted from an original article by I.P. Mysovskikh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article