line_fekete_rule

line_fekete_rule, a MATLAB code 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.

Licensing:

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

Languages:

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 MATLAB code 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_fekete_rule_test

line_felippa_rule, a MATLAB code which returns the points and weights of a felippa quadrature rule over the interior of a line segment in 1d.

line_grid, a MATLAB code which computes a grid of points over the interior of a line segment in 1d.

line_ncc_rule, a MATLAB code 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 MATLAB code which computes a newton cotes open (nco) quadrature rule, using equally spaced points, over the interior of a line segment in 1d.

quadrature_weights_vandermonde, a MATLAB code which computes the weights of a quadrature rule using the vandermonde matrix, assuming that the points have been specified.

triangle_fekete_rule, a MATLAB code which defines fekete rules for quadrature or interpolation over a triangle.

vandermonde, a MATLAB code 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:

• cheby_van1.m returns the Chebyshev Vandermonde matrix.
• legendre_van.m returns the Legendre Vandermonde matrix.
• line_fekete_chebyshev.m approximates Fekete points, using the Chebyshev polynomials and the Chebyshev weight function.
• line_fekete_monomial.m approximates Fekete points, using the monomials and the uniform weight function.
• line_monomial_moments.m returns the moments of monomials over [A,B].
• r8vec_print.m prints an R8VEC.