# Quadrature formula of highest algebraic accuracy

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)