Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can I do an integral, possibly using Gaussian quadrature, when the abscissas are fixed (for reasons that I don't want to get into right now); i.e., is it possible to calculate the weights for fixed abscissas that I don't get to choose?

share|improve this question

closed as too localized by Gerry Myerson, t.b., sdcvvc, Michael Greinecker, William Aug 31 '12 at 6:39

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Question has also been posted to MathOverflow, so I vote to close it here. –  Gerry Myerson Aug 5 '11 at 1:11

2 Answers 2

up vote 4 down vote accepted

In fact, if the abscissas $x_i$ of a weighted interpolatory quadrature rule

$$\int_a^b w(x) f(x)\;\mathrm dx\approx\sum_i w_if(x_i)$$

are given, and you need to generate the corresponding weights $w_i$, there are algorithms by Sylvan Elhay and Jaroslav Kautsky (based on earlier work by Kautsky and Gene Golub for the case of quadratures with both fixed and free knots) that are based on symmetric eigenvalue methods a la Golub-Welsch, and are slightly more stable than the usual approach of solving the Vandermonde system generated by the moments $\int_a^b w(x) x^k\mathrm dx$. They have published a FORTRAN implementation of their methods in the ACM Collected Algorithms; translating that into your favorite computing language (if you're not using FORTRAN, that is) is entirely up to you.


On the other hand, if you do have exact values for the $x_i$ and the moments $m_i=\int_a^b w(x) x^k\mathrm dx$ available, and you can do exact arithmetic, solving the Vandermonde system is feasible.

In particular, remember that for a weighted $n$-point quadrature rule with $n$ preset abscissas, it is customary to demand that the quadrature rule be able to exactly integrate functions of the form $w(x)p(x)$, where $p(x)$ is a polynomial with an degree from $0$ to $n-1$. ($n-1$ points uniquely determine a corresponding $n$-th degree polynomial passing through those points). However, it may well be that due to the special configuration/distribution of the points, the quadrature rule could do much better than expected. (Two examples come to mind: Simpson's rule is meant to be exact for quadratics, but is able to integrate cubics exactly, and the $n$-point Clenshaw-Curtis rule, whose $x_i$ are the extrema of Chebyshev polynomials, behaving favorably with regards to accuracy.) Newton-Cotes is but a special case of this, where the $x_i$ are equispaced over the integration interval.

Thus, to obtain the weights $w_i$ from the $x_i$ and the $m_i$, one needs to solve the primal Vandermonde system

$$\begin{pmatrix}1&1&1&\cdots&1\\x_1&x_2&x_3&\cdots&x_n\\x_1^2&x_2^2&x_3^2&\cdots&x_n^2\\\vdots&\vdots&\vdots&\ddots&\vdots\\x_1^{n-1}&x_2^{n-1}&x_3^{n-1}&\cdots&x_n^{n-1}\end{pmatrix}\cdot\begin{pmatrix}w_1\\w_2\\w_3\\\vdots\\w_n\end{pmatrix}=\begin{pmatrix}m_1\\m_2\\m_3\\\vdots\\m_n\end{pmatrix}$$

Gaussian elimination will work here, but it is more economical to use the Björck-Pereyra algorithm, which is based on Newton interpolation. This takes $O(n^2)$ effort as opposed to the $O(n^3)$ effort needed by Gaussian elimination.

But, again, for inexact arithmetic, the methods by Elhay and Kautsky will (generally) give more accurate values for the weights.


As a last warning, you will want to check the signs of the weights, whether you compute them through the Vandermonde route or the Elhay-Kautsky route. Beware if the weights are not of the same sign; it usually means that the underlying interpolating polynomial is quite oscillatory, and there might be cancellation of significant digits when the quadrature formula is used.

share|improve this answer

Absolutely. Section 4.5 of Numerical Recipes describes how, as will many numerical analysis books. Obsolete versions are free.

share|improve this answer
    
Thanks for the feedback. If I'm understanding you correctly you're referring to the section titled "Orthogonal Polynomials with Nonclassical Weights". Is this correct? I'm not 100% sure I understand, though. What I am constrained to use is the roots of the polynomials in Eq. (4.5.6). The section above is for when we know the modified moments of Eq. (4.5.30). I don't really see how to get from one to the other. –  jackj Aug 4 '11 at 23:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.