Lebesgue Constants for CVT/Chebyshev Computations

**CCL**
is a MATLAB program which
estimates the Lebesgue constants for sets of points in [-1,+1]
computed in several ways. The program is probably of limited interest
except as an example of an application of the lebesgue_constant()
function.

The cvt_1d_lumping() program was used to compute sets of points of order 5, 9, 17, 33, 65, 129 and 257. These points were the Chebyshev Zero nodes, and CVT points initialized with the Chebyshev Zero nodes, with random values, and with uniform values.

For each class of points, the program computed the Lebesgue constant L(N) and the ration L2(N)=L(N)/log(N+1). The Chebyshev Zero nodes are known to have an asymptotic behavior like log(N+1). If the CVT calculations had been carried out to convergence, then the initializations should not, in general have mattered. However, even though, for a given N, the initializations didn't seem to matter "that much", the differences became extraordinarily significant when the Lebesgue constant was computed on point sets with high N. The CVT generators initialized with Chebyshev Zero nodes had a lower Lebesgue constant than the Chebyshev Zero nodes, but the other two variations had Lebesgue constants that exploded at N=129 and N=257. This could be because of the extraordinarily strong clustering of Chebyshev Zero nodes near the endpoints. A high dimensional point set that doesn't get this endpoint clustering just right will have a terrible Lebesgue constant, even though a plot or a printout of the data will seem to be very close to the Chebyshev Zero nodes...because the important details are in the data at the endpoints and -0.999... and +0.999... digits.

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

**CCL** is available in
a MATLAB version.

CVT_1D_LUMPING, a MATLAB program which allows the user to carry out a lumped version of Lloyd's iterative algorithm for a centroidal Voronoi Tessellation (CVT() in the interval [-1,+1], and is applied to investigate a relationship between CVT's and the Chebyshev Zero nodes.

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

- ccl.m, carries out all the evaluations.
- ccl_output.txt, the output file.
- chebyzero_test.m, evaluates the Lebesgue constants for Chebyshev Zero nodes.
- cvt_chebyshev_test.m, evaluates the Lebesgue constants for CVT points initialized as Chebyshev Zero nodes.
- cvt_random_test.m, evaluates the Lebesgue constants for CVT points initialized as random values.
- cvt_uniform_test.m, evaluates the Lebesgue constants for CVT points initialized as uniform values.
- lebesgue_constant.m, estimates the Lebesgue constant.
- lebesgue_function.m, evaluates the Lebesgue function.
- r8vec2_print.m, prints a pair of R8VEC's.
- timestamp.m, prints the current YMDHMS date as a timestamp;

- chebyzero_005.txt
- chebyzero_009.txt
- chebyzero_017.txt
- chebyzero_033.txt
- chebyzero_065.txt
- chebyzero_129.txt
- chebyzero_257.txt
- cvt_005_c.txt
- cvt_009_c.txt
- cvt_017_c.txt
- cvt_033_c.txt
- cvt_065_c.txt
- cvt_129_c.txt
- cvt_257_c.txt
- cvt_005_r.txt
- cvt_009_r.txt
- cvt_017_r.txt
- cvt_033_r.txt
- cvt_065_r.txt
- cvt_129_r.txt
- cvt_257_r.txt
- cvt_005_u.txt
- cvt_009_u.txt
- cvt_017_u.txt
- cvt_033_u.txt
- cvt_065_u.txt
- cvt_129_u.txt
- cvt_257_u.txt

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