Namespaces
Variants
Actions

Difference between revisions of "Best quadrature formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
b0159401.png
 +
$#A+1 = 32 n = 0
 +
$#C+1 = 32 : ~/encyclopedia/old_files/data/B015/B.0105940 Best quadrature formula,
 +
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}}
 +
 
''optimal quadrature formula''
 
''optimal quadrature formula''
  
 
An approximate integration formula that guarantees the minimum error for a given class of functions, relative to all formulas of a specified type. As an example, consider the quadrature formula
 
An approximate integration formula that guarantees the minimum error for a given class of functions, relative to all formulas of a specified type. As an example, consider the quadrature formula
  
<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/b/b015/b015940/b0159401.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$ \tag{* }
 +
\int\limits _ { a } ^ { b }
 +
\rho (x) f (x)  dx  = \
 +
\sum _ {k = 1 } ^ { n }
 +
\sum _ {i = 0 } ^ { m }
 +
p _ {ki} f ^ { (i) } (x _ {k} ) + R (f),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159402.png" /> is a weight function. The remainder (error) term <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159403.png" /> depends both on the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159404.png" />, and on the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159405.png" /> consisting of the interpolation nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159406.png" /> (it is usually assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159407.png" />) and the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159408.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b0159409.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594010.png" />. Fixing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594012.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594013.png" /> denote some set of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594014.png" /> (and hence also some set of quadrature formulas), defined by some restrictions on the interpolation nodes and coefficients (in particular, one might consider the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594015.png" /> of coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594016.png" /> for a fixed node vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594017.png" />). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594018.png" /> be some class of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594019.png" />, it being assumed that the integral and the sum in (*) exist. The best quadrature formula of type (*) for the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594020.png" /> relative to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594021.png" /> is defined by a vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594022.png" /> for which
+
where $  \rho (x) $
 +
is a weight function. The remainder (error) term $  R (f) = R (f, X _ {n} , P _ {nm} ) $
 +
depends both on the function $  f (x) $,  
 +
and on the vector $  (X _ {n} , P _ {nm} ) $
 +
consisting of the interpolation nodes $  x _ {k} $(
 +
it is usually assumed that $  x _ {k} \in [a, b] $)  
 +
and the coefficients $  p _ {ki} $,  
 +
$  k = 1 \dots n $;  
 +
$  i = 0 \dots m $.  
 +
Fixing $  n \geq  1 $
 +
and $  m \geq  0 $,  
 +
let $  A $
 +
denote some set of vectors $  (X _ {n} , P _ {nm} ) $(
 +
and hence also some set of quadrature formulas), defined by some restrictions on the interpolation nodes and coefficients (in particular, one might consider the set $  A = A ( \overline{X}\; _ {n} ) $
 +
of coefficients $  p _ {ki} $
 +
for a fixed node vector $  \overline{X}\; _ {n} $).  
 +
Let $  \mathfrak M $
 +
be some class of functions $  f (x) $,  
 +
it being assumed that the integral and the sum in (*) exist. The best quadrature formula of type (*) for the class $  \mathfrak M $
 +
relative to the set $  A $
 +
is defined by a vector $  (X _ {n}  ^ {*} , P _ {nm}  ^ {*} ) $
 +
for which
  
<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/b/b015/b015940/b01594023.png" /></td> </tr></table>
+
$$
 +
\sup _ {f \in \mathfrak M }  |
 +
R (f, X _ {n}  ^ {*} , P _ {nm}  ^ {*} ) | =
 +
$$
  
<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/b/b015/b015940/b01594024.png" /></td> </tr></table>
+
$$
 +
= \
 +
\inf _ {(X _ {n} , P _ {nm} ) \in A }  \sup _ {f
 +
\in \mathfrak M }  | R (f, X _ {n} , P _ {nm} ) | .
 +
$$
  
The construction of best quadrature formulas is intimately connected with certain problems in [[Spline approximation|spline approximation]]; in many cases it reduces to minimizing the norm of a monospline (see [[#References|[1]]]). Best quadrature formulas, together with sharp estimates for the remainder term, are known for many important classes of continuous and differentiable functions. From a more general point of view, the problem of finding best quadrature formulas and the corresponding errors for a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594025.png" /> may be viewed as the problem of optimal recovery of a functional
+
The construction of best quadrature formulas is intimately connected with certain problems in [[Spline approximation|spline approximation]]; in many cases it reduces to minimizing the norm of a monospline (see [[#References|[1]]]). Best quadrature formulas, together with sharp estimates for the remainder term, are known for many important classes of continuous and differentiable functions. From a more general point of view, the problem of finding best quadrature formulas and the corresponding errors for a class $  \mathfrak M $
 +
may be viewed as the problem of optimal recovery of a functional
  
<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/b/b015/b015940/b01594026.png" /></td> </tr></table>
+
$$
 +
J (f)  = \int\limits _ { a } ^ { b }  \rho (x) f (x)  dx,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594027.png" />, on the basis of the information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594029.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594030.png" />. The concept of a best quadrature formula generalizes in a natural way to functions of several variables (cubature formulas).
+
where $  f \in \mathfrak M $,  
 +
on the basis of the information $  \{ f ^ { (i) } (x _ {k} ) \} $,  
 +
$  k = 1 \dots n $;  
 +
$  i = 0 \dots m $.  
 +
The concept of a best quadrature formula generalizes in a natural way to functions of several variables (cubature formulas).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.M. Nikol'skii,  "Quadrature formulae" , H.M. Stationary Office , London  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.M. Krylov,  "Approximate calculation of integrals" , Macmillan  (1962)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  P.J. Laurent,  "Approximation et optimisation" , Hermann  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Zhensykbaev,  "Monosplines of minimal norm and quadrature formulas"  ''Uspekhi Mat. Nauk'' , '''36''' :  4  (1981)  pp. 107–159  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.M. Nikol'skii,  "Quadrature formulae" , H.M. Stationary Office , London  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.M. Krylov,  "Approximate calculation of integrals" , Macmillan  (1962)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  P.J. Laurent,  "Approximation et optimisation" , Hermann  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Zhensykbaev,  "Monosplines of minimal norm and quadrature formulas"  ''Uspekhi Mat. Nauk'' , '''36''' :  4  (1981)  pp. 107–159  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
The terminology  "best formula"  is often encountered in the literature on numerical analysis, but, as was observed in [[#References|[a2]]], p. 75, it should be taken with a large dose of salt, because, after all, any quadrature formula, no matter how the weights <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594031.png" /> and the nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015940/b01594032.png" /> are chosen, will exactly integrate an infinite-dimensional family of functions.
+
The terminology  "best formula"  is often encountered in the literature on numerical analysis, but, as was observed in [[#References|[a2]]], p. 75, it should be taken with a large dose of salt, because, after all, any quadrature formula, no matter how the weights $  p _ {k i }  $
 +
and the nodes $  x _ {k} $
 +
are chosen, will exactly integrate an infinite-dimensional family of functions.
  
 
A few recent textbooks are listed below.
 
A few recent textbooks are listed below.

Latest revision as of 10:58, 29 May 2020


optimal quadrature formula

An approximate integration formula that guarantees the minimum error for a given class of functions, relative to all formulas of a specified type. As an example, consider the quadrature formula

$$ \tag{* } \int\limits _ { a } ^ { b } \rho (x) f (x) dx = \ \sum _ {k = 1 } ^ { n } \sum _ {i = 0 } ^ { m } p _ {ki} f ^ { (i) } (x _ {k} ) + R (f), $$

where $ \rho (x) $ is a weight function. The remainder (error) term $ R (f) = R (f, X _ {n} , P _ {nm} ) $ depends both on the function $ f (x) $, and on the vector $ (X _ {n} , P _ {nm} ) $ consisting of the interpolation nodes $ x _ {k} $( it is usually assumed that $ x _ {k} \in [a, b] $) and the coefficients $ p _ {ki} $, $ k = 1 \dots n $; $ i = 0 \dots m $. Fixing $ n \geq 1 $ and $ m \geq 0 $, let $ A $ denote some set of vectors $ (X _ {n} , P _ {nm} ) $( and hence also some set of quadrature formulas), defined by some restrictions on the interpolation nodes and coefficients (in particular, one might consider the set $ A = A ( \overline{X}\; _ {n} ) $ of coefficients $ p _ {ki} $ for a fixed node vector $ \overline{X}\; _ {n} $). Let $ \mathfrak M $ be some class of functions $ f (x) $, it being assumed that the integral and the sum in (*) exist. The best quadrature formula of type (*) for the class $ \mathfrak M $ relative to the set $ A $ is defined by a vector $ (X _ {n} ^ {*} , P _ {nm} ^ {*} ) $ for which

$$ \sup _ {f \in \mathfrak M } | R (f, X _ {n} ^ {*} , P _ {nm} ^ {*} ) | = $$

$$ = \ \inf _ {(X _ {n} , P _ {nm} ) \in A } \sup _ {f \in \mathfrak M } | R (f, X _ {n} , P _ {nm} ) | . $$

The construction of best quadrature formulas is intimately connected with certain problems in spline approximation; in many cases it reduces to minimizing the norm of a monospline (see [1]). Best quadrature formulas, together with sharp estimates for the remainder term, are known for many important classes of continuous and differentiable functions. From a more general point of view, the problem of finding best quadrature formulas and the corresponding errors for a class $ \mathfrak M $ may be viewed as the problem of optimal recovery of a functional

$$ J (f) = \int\limits _ { a } ^ { b } \rho (x) f (x) dx, $$

where $ f \in \mathfrak M $, on the basis of the information $ \{ f ^ { (i) } (x _ {k} ) \} $, $ k = 1 \dots n $; $ i = 0 \dots m $. The concept of a best quadrature formula generalizes in a natural way to functions of several variables (cubature formulas).

References

[1] S.M. Nikol'skii, "Quadrature formulae" , H.M. Stationary Office , London (1966) (Translated from Russian)
[2] N.M. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[3] P.J. Laurent, "Approximation et optimisation" , Hermann (1972)
[4] A.A. Zhensykbaev, "Monosplines of minimal norm and quadrature formulas" Uspekhi Mat. Nauk , 36 : 4 (1981) pp. 107–159 (In Russian)

Comments

The terminology "best formula" is often encountered in the literature on numerical analysis, but, as was observed in [a2], p. 75, it should be taken with a large dose of salt, because, after all, any quadrature formula, no matter how the weights $ p _ {k i } $ and the nodes $ x _ {k} $ are chosen, will exactly integrate an infinite-dimensional family of functions.

A few recent textbooks are listed below.

References

[a1] H. Brass, "Quadraturverfahren" , Vandenhoeck & Ruprecht (1977)
[a2] P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1984)
[a3] H. Engels, "Numerical quadrature and cubature" , Acad. Press (1980)
How to Cite This Entry:
Best quadrature formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Best_quadrature_formula&oldid=46044
This article was adapted from an original article by N.P. KorneichukV.P. Motornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article