Approximate Fekete Points in an Interval

LINE_FEKETE_RULE is a C 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.


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


LINE_FEKETE_RULE is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LEBESGUE, a C 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 C library which returns the points and weights of a Felippa quadrature rule over the interior of a line segment in 1D.

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

LINE_NCC_RULE, a C 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 C 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 C library which computes the least squares solution of a linear system A*x=b.

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.

TRIANGLE_FEKETE_RULE, a C library which defines Fekete rules for interpolation or quadrature over the interior of a triangle in 2D.

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


  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:

Examples and Tests:

List of Routines:

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

Last revised on 13 April 2014.