Namespaces
Variants
Actions

Quadrature formula of highest algebraic accuracy

From Encyclopedia of Mathematics
Jump to: navigation, search


A formula of the type

$$ \tag{1 } \int\limits _ { a } ^ { b } p ( x) f ( x) dx \approx \ \sum _ {j = 1 } ^ { N } C _ {j} f ( x _ {j} ), $$

where the weight function $ p ( x) $ is assumed to be non-negative on $ [ a, b] $, where the integrals

$$ \mu _ {k} = \ \int\limits _ { a } ^ { b } p ( x) x ^ {k} dx,\ \ k = 0, 1 \dots $$

exist and where, moreover, $ \mu _ {0} > 0 $. The nodes $ x _ {j} $ of formula (1) are the roots of a polynomial of degree $ N $ orthogonal on $ [ a, b] $ with the weight function $ p ( x) $, and the weights are defined by the condition that (1) be an interpolatory formula. A quadrature formula of this type has algebraic accuracy $ 2N - 1 $, i.e. it is exact for all algebraic polynomials $ f ( x) $ of degree $ \leq 2N - 1 $ and is not exact for $ x ^ {2N} $; it is known as a quadrature formula of Gaussian type.

This concept can be generalized as follows. Consider the quadrature formula

$$ \tag{2 } \int\limits _ { a } ^ { b } p ( x) f ( x) dx \approx \ \sum _ {j = 1 } ^ { m } A _ {j} f ( a _ {j} ) + \sum _ {j = 1 } ^ { n } C _ {j} f ( x _ {j} ) $$

with $ N = m + n $ nodes, where the nodes $ a _ {1} \dots a _ {m} $ are pre-assigned (fixed) while $ x _ {1} \dots x _ {n} $ are so chosen that (2) be a quadrature formula of highest algebraic accuracy. Let

$$ \sigma ( x) = \ \prod _ {j = 1 } ^ { m } ( x - a _ {j} ),\ \ \omega ( x) = \ \prod _ {j = 1 } ^ { n } ( x - x _ {j} ). $$

Formula (2) is exact for all polynomials of degree $ \leq m + 2n - 1 $ if and only if it is an interpolatory quadrature formula and the polynomial $ \omega ( x) $ is orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $ to all polynomials of degree $ \leq n - 1 $. This reduces the question of the existence of a quadrature formula that is exact for all polynomials of degree $ \leq 2n - 1 $ to the problem of determining a polynomial $ \omega ( x) $ of degree $ n $ that is orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $, and to examining the properties of its roots. If the roots of $ \omega ( x) $ are real, simple, lie in $ [ a, b] $, and none of them is one of the fixed nodes, the required quadrature formula exists. If, moreover,

$$ \int\limits _ { a } ^ { b } p ( x) \sigma ( x) \omega ^ {2} ( x) dx \neq 0, $$

then the algebraic accuracy of the formula is $ m + 2n - 1 $.

Under the above assumptions concerning the weight function $ p ( x) $, a polynomial $ \omega ( x) $ of degree $ n $, orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $, is defined uniquely (up to a non-zero constant factor) in the following special cases.

1) $ m = 1 $, $ n $ is arbitrary. The single fixed node is an end-point of the interval $ [ a, b] $, with the only condition that it be finite.

2) $ m = 2 $, $ n $ is arbitrary. The two fixed nodes are the end-points of the interval $ [ a, b] $, provided they are finite.

3) $ m $ is arbitrary, $ n = m + 1 $. The fixed nodes are the roots of a polynomial $ P _ {m} ( x) $ that is orthogonal on $ [ a, b] $ with the weight function $ p ( x) $.

In cases 1) and 2), the polynomial $ \omega ( x) $ is orthogonal relative to the weight function $ \sigma ( x) p ( x) $, which is of fixed sign on $ [ a, b] $, and therefore its roots are real, simple, lie inside $ ( a, b) $, and are consequently distinct from $ a, b $. The quadrature formula (2) exists, its coefficients are positive and its algebraic accuracy is $ m + 2n - 1 $. Quadrature formulas corresponding to the cases 1) and 2) are called Markov formulas.

In case 3), the weight function $ \sigma ( x) p ( x) $ changes sign on $ [ a, b] $ and this complicates the inspection of the roots of $ \omega ( x) $. If $ [ a, b] = [- 1, 1] $ and $ p ( x) = ( 1 - x ^ {2} ) ^ \alpha $, where $ - 1/2 < \alpha \leq 3/2 $, then the roots of $ \omega ( x) $ lie inside $ (- 1, 1) $ and separate the roots of $ P _ {m} ( x) $: Between any two consecutive roots of $ \omega ( x) $ there is exactly one root of $ P _ {m} ( x) $( see [2]). With this weight function, the quadrature formula (2) exists and is exact for all polynomials of degree $ \leq 3m + 1 $; however, one cannot state that its algebraic accuracy is $ 3m + 1 $. For $ \alpha = - 1/2 $ and $ \alpha = 1/2 $ the nodes and the coefficients of the quadrature formula can be specified explicitly (see [3]); the algebraic accuracy in the former case is increased to $ 4m - 1 $, and in the second case to $ 4m + 1 $. For $ p ( x) = 1 $ and the interval $ [ 0, 1] $, the nodes and the coefficients have been computed for the quadrature formula (2) (with fixed nodes of type 3)) for $ m = 1 ( 1) 40 $( i.e. $ m $ varying from 1 to 40 with step 1) (see [4]); the algebraic accuracy is $ 3m + 1 $ if $ m $ is even and $ 3m + 2 $ if $ m $ is odd. A quadrature formula (2) with fixed nodes of type 3) also exists for the interval $ [- 1, 1] $ and the weight function $ ( 1 - x) ^ \alpha ( 1 + x) ^ {- \alpha } $ for $ \alpha = \pm 1/2 $, and the nodes and the coefficients can be explicitly specified (see [3]).

References

[1] V.I. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[2] G. Szegö, "Ueber gewisse orthogonale Polynome, die zu einer oszillierenden Belegungsfunktion gehören" Math. Ann. , 110 : 4 (1934) pp. 501–513
[3] I.P Mysovskikh, "A special case of quadrature formulas containing pre-assigned nodes" Izv. Akad. Nauk BelorussSSR. Ser. Fiz.-Tekhn. Navuk , 4 (1964) pp. 125–127 (In Russian)
[4] A.S. Kronrod, "Nodes and weights of quadrature formulas" , Consultants Bureau (1965) (Translated from Russian)
[a1] P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1975)
How to Cite This Entry:
Quadrature formula of highest algebraic accuracy. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadrature_formula_of_highest_algebraic_accuracy&oldid=55409
This article was adapted from an original article by I.P. Mysovskikh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article