QUADRATURE_LEAST_SQUARES
Least Squares Quadrature Rules

QUADRATURE_LEAST_SQUARES is a C++ library which computes weights for "sub-interpolatory" quadrature rules.

A large class of quadrature rules may be computed by specifying a set of N abscissas, or sample points, X(1:N), determining the Lagrange interpolation basis functions L(1:N), and then setting a weight vector W by

        W(i) = I(L(i))
      

        I(f) \approx Q(f) = sum ( 1 <= i <= N ) W(i) * f(X(i))
      

We call this an interpolatory rule because the function f(x) has first been interpolated by

        f(x) \approx sum ( 1 <= i <= N ) L(i) * f(X(i))
      

        I(f) \approx I(sum ( 1 <= i <= N )   L(i)  * f(X(i)))
             =         sum ( 1 <= i <= N ) I(L(i)) * f(X(i))
             =         sum ( 1 <= i <= N )   W(i)  * f(X(i)).
      

For badly chosen sets of X, or high values of N, or unruly functions f(x), interpolation may be a bad way to approximate the function. An alternative is to seek a polynomial interpolant of degree D < N-1, and then integrate that. We might call this a "sub-interpolatory" rule.

As it turns out, a natural way to seek such a rule is to write out the N by D+1 Vandermonde matrix and use a least squares solver. Even though the N by N Vandermonde matrix is ill-conditioned for Gauss elimination, a least squares approach can produce usable solutions from the N by D+1 matrix.

The outline of this procedure was devised by Professor Mac Hyman of Tulane University.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

QUADRATURE_LEAST_SQUARES is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CLENSHAW_CURTIS_RULE, a C++ library which defines a multiple dimension Clenshaw Curtis quadrature rule.

QR_SOLVE, a C++ library which computes the least squares solution of a rectangular linear system A*x=b.

QUADMOM, a C++ library which computes a Gaussian quadrature rule for a weight function rho(x) based on the Golub-Welsch procedure that only requires knowledge of the moments of rho(x).

QUADRATURE_GOLUB_WELSCH, a C++ library which computes the points and weights of a Gaussian quadrature rule using the Golub-Welsch procedure, assuming that the points have been specified.

QUADRATURE_WEIGHTS_VANDERMONDE, a C++ library which computes the weights of a quadrature rule using the Vandermonde matrix, assuming that the points have been specified.

QUADRULE, a C++ library which defines quadrature rules for approximating an integral over a 1D domain.

QUADRULE_FAST, a C++ library which defines efficient versions of a few 1D quadrature rules.

TEST_INT, a C++ library which defines test integrands for 1D quadrature rules.

TRUNCATED_NORMAL_RULE, a C++ program which computes a quadrature rule for a normal probability density function (PDF), also called a Gaussian distribution, that has been truncated to [A,+oo), (-oo,B] or [A,B].

VANDERMONDE, a C++ library which carries out certain operations associated with the Vandermonde matrix.

Source Code:

• qls.cpp, the source code.
• qls.hpp, the include file.
• qls.sh, BASH commands to compile the source code.

Examples and Tests:

• qls_prb.cpp, a sample calling program.
• qls_prb.sh, BASH commands to compile and run the sample program.
• qls_prb_output.txt, the output file.

List of Routines:

• NCC_SET sets abscissas and weights for Newton-Cotes closed quadrature.
• R8MAT_MV multiplies a matrix times a vector.
• R8VEC_UNIFORM_AB returns a scaled pseudorandom R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• WEIGHTS_LS computes weights for a least squares quadrature rule.

You can go up one level to the C++ source codes.