LINE_FEKETE
Approximate Fekete Points in an Interval

LINE_FEKETE is a FORTRAN77 library which approximates the location of Fekete points in an interval [A,B]. A family of sets of Fekete points, indexed by size N, represents an excellent choice for defining a polynomial interpolant.

Given a desired number of points N, the best choice for abscissas is a set of Lebesgue points, which minimize the Lebesgue constant, which describes the error in polynomial interpolation. Sets of Lebesgue points are difficult to define mathematically. Fekete points are a related, computable set, defined as those sets maximizing the magnitude of the determinant of the Vandermonde matrix associated with the points. Analytic definitions of these points are known for a few cases, but there is a general computational procedure for approximating them, which is demonstrated here.

Usage:

[ nf, xf, wf, vf ] = line_fekete_monomial ( n, a, b, m, x )

• n is the dimension of the polynomial space (typically, the maximum degree minus 1);
• a and b are the endpoints of the interval;
• m is the number of sample points; m must be at least n.
• x is a vector of m sample points;

• nf the number of approximate Fekete points, which should be n;
• xf the approximate Fekete points.
• wf the Fekete weights;
• vf the associated nf by n Vandermonde matrix;

Licensing:

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

Languages:

LINE_FEKETE 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:

LEBESGUE, a FORTRAN90 library which is given a set of nodes in 1D, and plots the Lebesgue function, and estimates the Lebesgue constant, which measures the maximum magnitude of the potential error of Lagrange polynomial interpolation.

LINE_FELIPPA_RULE, a FORTRAN77 library which returns the points and weights of a Felippa quadrature rule over the interior of a line segment in 1D.

LINE_GRID, a FORTRAN77 library which computes a grid of points over the interior of a line segment in 1D.

LINE_NCC_RULE, a FORTRAN77 library which computes a Newton Cotes Closed (NCC) quadrature rule for the line, that is, for an interval of the form [A,B], using equally spaced points which include the endpoints.

LINE_NCO_RULE, a FORTRAN77 library which computes a Newton Cotes Open (NCO) quadrature rule, using equally spaced points, over the interior of a line segment in 1D.

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

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

TRIANGLE_FEKETE, a FORTRAN90 library which defines Fekete rules for quadrature or interpolation over a triangle.

VANDERMONDE, a FORTRAN77library which carries out certain operations associated with the Vandermonde matrix.

Reference:

1. Len Bos, Norm Levenberg,
   On the calculation of approximate Fekete points: the univariate case,
   Electronic Transactions on Numerical Analysis,
   Volume 30, pages 377-397, 2008.
2. Alvise Sommariva, Marco Vianello,
   Computing approximate Fekete points by QR factorizations of Vandermonde matrices,
   Computers and Mathematics with Applications,
   Volume 57, 2009, pages 1324-1336.

Source Code:

• line_fekete.f, the source code.
• line_fekete.sh, BASH commands to compile the source code.

Examples and Tests:

• line_fekete_prb.f, a sample calling program.
• line_fekete_prb.sh, BASH commands to compile and run the sample program.
• line_fekete_prb_output.txt, the output file.

List of Routines:

• CHEBY_VAN1 returns the Chebyshev Vandermonde-like matrix for [A,B].
• LEGENDRE_VAN returns the LEGENDRE_VAN matrix.
• LINE_FEKETE_CHEBYSHEV: approximate Fekete points in an interval [A,B].
• LINE_FEKETE_LEGENDRE computes approximate Fekete points in an interval [A,B].
• LINE_FEKETE_MONOMIAL computes approximate Fekete points in an interval [A,B].
• LINE_MONOMIAL_MOMENTS computes monomial moments in [A,B].
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8VEC_LINSPACE creates a vector of linearly spaced values.
• R8VEC_PRINT prints an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the FORTRAN77 source codes.