Namespaces
Variants
Actions

Difference between revisions of "Kronrod-Patterson quadrature formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 32 formulas out of 34 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 34 formulas, 32 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|partial}}
 
A [[Quadrature formula of highest algebraic accuracy|quadrature formula of highest algebraic accuracy]] of the type
 
A [[Quadrature formula of highest algebraic accuracy|quadrature formula of highest algebraic accuracy]] of the type
  
<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/k/k120/k120130/k1201301.png" /></td> </tr></table>
+
\begin{equation*} \int _ { a } ^ { b } p ( x ) f ( x ) d x \approx Q _ { 2 ^ {i}  ( n + 1 ) - 1 } [ f ] = \end{equation*}
  
<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/k/k120/k120130/k1201302.png" /></td> </tr></table>
+
\begin{equation*} = \sum _ { \nu = 1 } ^ { n } \alpha _ { i \nu }\, f ( x _ { \nu } ) + \sum _ { \rho = 1 } ^ { i } \sum _ { \nu = 1 } ^ { 2 ^ { \rho - 1 } ( n + 1 ) } \beta _ { i \rho \nu }\, f ( \xi _ { \nu } ^ { \rho } ), \end{equation*}
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201303.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201304.png" /> are the nodes of a [[Gauss quadrature formula|Gauss quadrature formula]] and the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201305.png" /> are fixed in the construction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201306.png" /> [[#References|[a2]]]. Nested sequences of Kronrod–Patterson formulas are used for the numerical approximation of definite integrals with practical error estimate, in particular in the non-adaptive routines of the numerical integration package QUADPACK [[#References|[a4]]] and in the standard numerical software libraries.
+
$i \geq 1$, where $x _ { 1 } , \ldots , x _ { n }$ are the nodes of a [[Gauss quadrature formula|Gauss quadrature formula]] and the nodes of $Q _ { 2 ^{ i - 1} ( n + 1 ) - 1 }$ are fixed in the construction of $Q _ { 2 ^{ i}  ( n + 1 ) - 1 }$ [[#References|[a2]]]. Nested sequences of Kronrod–Patterson formulas are used for the numerical approximation of definite integrals with practical error estimate, in particular in the non-adaptive routines of the numerical integration package QUADPACK [[#References|[a4]]] and in the standard numerical software libraries.
  
The algebraic accuracy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201307.png" /> is at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201308.png" />. The free nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k1201309.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013010.png" /> are precisely the zeros of the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013011.png" /> which satisfies
+
The algebraic accuracy of $Q _ { 2 ^{ i}  ( n + 1 ) - 1 }$ is at least $3.2 ^ { i - 1 } ( n + 1 ) - 2$. The free nodes $\xi _ { 1 } ^ { i } , \ldots , \xi _ { 2 ^ { i - 1 } ( n + 1 ) } ^ { i } $ of $Q _ { 2 ^{ i}  ( n + 1 ) - 1 }$ are precisely the zeros of the polynomial $E _ { 2 ^{i-1}(n+1)} ^ { i } $ which satisfies
  
<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/k/k120/k120130/k12013012.png" /></td> </tr></table>
+
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013012.png"/></td> </tr></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/k/k120/k120130/k12013013.png" /></td> </tr></table>
+
\begin{equation*} k = 0 , \ldots , 2 ^ { i - 1 } ( n + 1 ) - 1, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013014.png" /> is the system of [[Orthogonal polynomials|orthogonal polynomials]] associated with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013016.png" /> is the [[Gauss–Kronrod quadrature formula|Gauss–Kronrod quadrature formula]], and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013017.png" /> is the Stieltjes polynomial (cf. [[Stieltjes polynomials|Stieltjes polynomials]]). For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013020.png" />, the Chebyshev polynomial of the second kind (cf. [[Chebyshev polynomials|Chebyshev polynomials]]), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013021.png" />, the Chebyshev polynomial of the first kind. In this case, all Kronrod–Patterson formulas are Gauss quadrature formulas (cf. [[Gauss quadrature formula|Gauss quadrature formula]]). Hence, the algebraic accuracy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013022.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013023.png" />, the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013025.png" /> interlace and the formulas have positive weights. Similar properties are known for the more general Bernstein–Szegö weight functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013026.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013027.png" /> is a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013028.png" /> which is positive on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013029.png" />, see [[#References|[a3]]].
+
where $\{ P _ { n } \}$ is the system of [[Orthogonal polynomials|orthogonal polynomials]] associated with $p$, $Q _ { 2 n+1} $ is the [[Gauss–Kronrod quadrature formula|Gauss–Kronrod quadrature formula]], and $E _ { n + 1 } ^ { 1 }$ is the Stieltjes polynomial (cf. [[Stieltjes polynomials|Stieltjes polynomials]]). For $[ a , b ] = [ - 1,1 ]$ and $p ( x ) = \sqrt { 1 - x ^ { 2 } }$, $P _ { n } = U _ { n }$, the Chebyshev polynomial of the second kind (cf. [[Chebyshev polynomials|Chebyshev polynomials]]), and $E  ^{ i } _ { 2 ^{ i - 1}  ( n + 1 ) } = T _ { 2 ^{ i - 1}  ( n + 1 ) }$, the Chebyshev polynomial of the first kind. In this case, all Kronrod–Patterson formulas are Gauss quadrature formulas (cf. [[Gauss quadrature formula|Gauss quadrature formula]]). Hence, the algebraic accuracy of $Q _ { 2 ^{ i}  ( n + 1 ) - 1 }$ is $2 ^ { i + 1 } ( n + 1 ) - 3$, the nodes of $Q _ { 2 ^{ i - 1} ( n + 1 ) - 1 }$ and $Q _ { 2 ^{ i}  ( n + 1 ) - 1 }$ interlace and the formulas have positive weights. Similar properties are known for the more general Bernstein–Szegö weight functions $p ( x ) = \sqrt { 1 - x ^ { 2 } } / \rho _ { m } ( x )$, where $\rho _ { m }$ is a polynomial of degree $m$ which is positive on $[ a , b ] = [ - 1,1 ]$, see [[#References|[a3]]].
  
Only very little is known for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013030.png" />, which is the most important case for practical calculations. Tables of sequences of Kronrod–Patterson formulas have been given in [[#References|[a2]]], [[#References|[a4]]]. A numerical investigation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013031.png" /> and Jacobi weight functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k120/k120130/k12013033.png" />, can be found in [[#References|[a5]]].
+
Only very little is known for $p \equiv 1$, which is the most important case for practical calculations. Tables of sequences of Kronrod–Patterson formulas have been given in [[#References|[a2]]], [[#References|[a4]]]. A numerical investigation for $ i  = 2$ and Jacobi weight functions $p ( x ) = ( 1 - x ) ^ { \alpha } ( 1 + x ) ^ { \beta }$, $\alpha , \beta &gt; - 1$, can be found in [[#References|[a5]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,  P. Rabinowitz,  "Methods of numerical integration" , Acad. Press  (1984)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T.N.L. Patterson,  "The optimum addition of points to quadrature formulae"  ''Math. Comput.'' , '''22'''  (1968)  pp. 847–856</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  F. Peherstorfer,  "Weight functions admitting repeated positive Kronrod quadrature"  ''BIT'' , '''30'''  (1990)  pp. 241–251</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Piessens,  et al.,  "QUADPACK: a subroutine package in automatic integration" , Springer  (1983)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Rabinowitz,  S. Elhay,  J. Kautsky,  "Empirical mathematics: the first Patterson extension of Gauss–Kronrod rules"  ''Internat. J. Computer Math.'' , '''36'''  (1990)  pp. 119–129</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  P.J. Davis,  P. Rabinowitz,  "Methods of numerical integration" , Acad. Press  (1984)  (Edition: Second)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  T.N.L. Patterson,  "The optimum addition of points to quadrature formulae"  ''Math. Comput.'' , '''22'''  (1968)  pp. 847–856</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  F. Peherstorfer,  "Weight functions admitting repeated positive Kronrod quadrature"  ''BIT'' , '''30'''  (1990)  pp. 241–251</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  R. Piessens,  et al.,  "QUADPACK: a subroutine package in automatic integration" , Springer  (1983)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  P. Rabinowitz,  S. Elhay,  J. Kautsky,  "Empirical mathematics: the first Patterson extension of Gauss–Kronrod rules"  ''Internat. J. Computer Math.'' , '''36'''  (1990)  pp. 119–129</td></tr></table>

Revision as of 16:59, 1 July 2020

A quadrature formula of highest algebraic accuracy of the type

\begin{equation*} \int _ { a } ^ { b } p ( x ) f ( x ) d x \approx Q _ { 2 ^ {i} ( n + 1 ) - 1 } [ f ] = \end{equation*}

\begin{equation*} = \sum _ { \nu = 1 } ^ { n } \alpha _ { i \nu }\, f ( x _ { \nu } ) + \sum _ { \rho = 1 } ^ { i } \sum _ { \nu = 1 } ^ { 2 ^ { \rho - 1 } ( n + 1 ) } \beta _ { i \rho \nu }\, f ( \xi _ { \nu } ^ { \rho } ), \end{equation*}

$i \geq 1$, where $x _ { 1 } , \ldots , x _ { n }$ are the nodes of a Gauss quadrature formula and the nodes of $Q _ { 2 ^{ i - 1} ( n + 1 ) - 1 }$ are fixed in the construction of $Q _ { 2 ^{ i} ( n + 1 ) - 1 }$ [a2]. Nested sequences of Kronrod–Patterson formulas are used for the numerical approximation of definite integrals with practical error estimate, in particular in the non-adaptive routines of the numerical integration package QUADPACK [a4] and in the standard numerical software libraries.

The algebraic accuracy of $Q _ { 2 ^{ i} ( n + 1 ) - 1 }$ is at least $3.2 ^ { i - 1 } ( n + 1 ) - 2$. The free nodes $\xi _ { 1 } ^ { i } , \ldots , \xi _ { 2 ^ { i - 1 } ( n + 1 ) } ^ { i } $ of $Q _ { 2 ^{ i} ( n + 1 ) - 1 }$ are precisely the zeros of the polynomial $E _ { 2 ^{i-1}(n+1)} ^ { i } $ which satisfies

\begin{equation*} k = 0 , \ldots , 2 ^ { i - 1 } ( n + 1 ) - 1, \end{equation*}

where $\{ P _ { n } \}$ is the system of orthogonal polynomials associated with $p$, $Q _ { 2 n+1} $ is the Gauss–Kronrod quadrature formula, and $E _ { n + 1 } ^ { 1 }$ is the Stieltjes polynomial (cf. Stieltjes polynomials). For $[ a , b ] = [ - 1,1 ]$ and $p ( x ) = \sqrt { 1 - x ^ { 2 } }$, $P _ { n } = U _ { n }$, the Chebyshev polynomial of the second kind (cf. Chebyshev polynomials), and $E ^{ i } _ { 2 ^{ i - 1} ( n + 1 ) } = T _ { 2 ^{ i - 1} ( n + 1 ) }$, the Chebyshev polynomial of the first kind. In this case, all Kronrod–Patterson formulas are Gauss quadrature formulas (cf. Gauss quadrature formula). Hence, the algebraic accuracy of $Q _ { 2 ^{ i} ( n + 1 ) - 1 }$ is $2 ^ { i + 1 } ( n + 1 ) - 3$, the nodes of $Q _ { 2 ^{ i - 1} ( n + 1 ) - 1 }$ and $Q _ { 2 ^{ i} ( n + 1 ) - 1 }$ interlace and the formulas have positive weights. Similar properties are known for the more general Bernstein–Szegö weight functions $p ( x ) = \sqrt { 1 - x ^ { 2 } } / \rho _ { m } ( x )$, where $\rho _ { m }$ is a polynomial of degree $m$ which is positive on $[ a , b ] = [ - 1,1 ]$, see [a3].

Only very little is known for $p \equiv 1$, which is the most important case for practical calculations. Tables of sequences of Kronrod–Patterson formulas have been given in [a2], [a4]. A numerical investigation for $ i = 2$ and Jacobi weight functions $p ( x ) = ( 1 - x ) ^ { \alpha } ( 1 + x ) ^ { \beta }$, $\alpha , \beta > - 1$, can be found in [a5].

References

[a1] P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1984) (Edition: Second)
[a2] T.N.L. Patterson, "The optimum addition of points to quadrature formulae" Math. Comput. , 22 (1968) pp. 847–856
[a3] F. Peherstorfer, "Weight functions admitting repeated positive Kronrod quadrature" BIT , 30 (1990) pp. 241–251
[a4] R. Piessens, et al., "QUADPACK: a subroutine package in automatic integration" , Springer (1983)
[a5] P. Rabinowitz, S. Elhay, J. Kautsky, "Empirical mathematics: the first Patterson extension of Gauss–Kronrod rules" Internat. J. Computer Math. , 36 (1990) pp. 119–129
How to Cite This Entry:
Kronrod-Patterson quadrature formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kronrod-Patterson_quadrature_formula&oldid=50288
This article was adapted from an original article by Sven Ehrich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article