In current textbooks the use of Chebyshev nodes with Newton interpolation is advocated as the most efficient numerical interpolation method in terms of approximation accuracy and computational effort. However, we show numerically that the approximation quality obtained by Newton interpolation with Fast Leja (FL) points is competitive to the use of Chebyshev nodes, even for extremely high degree interpolation. This is an experimental account of the analytic result that the limit distribution of FL points and Chebyshev nodes is the same when letting the number of points go to infinity. Since the FL construction is easy to perform and allows to add interpolation nodes on the fly in contrast to the use of Chebyshev nodes, our study suggests that Newton interpolation with FL points is currently the most efficient numerical technique for polynomial interpolation. Moreover, we give numerical evidence that any reasonable function can be approximated up to machine accuracy by Newton interpolation with FL points if desired, which shows the potential of this method.
The Shape-From-Shading (SFS) problem is a fundamental and classic problem in computer vision. It amounts to compute the 3-D depth of objects in a single given 2-D image. This is done by exploiting information about the illumination and the image brightness. We deal with a recent model for Perspective SFS (PSFS) for Lambertian surfaces. It is defined by a Hamilton-Jacobi equation and complemented by state constraints boundary conditions. In this paper we investigate and compare three state-of-the-art numerical approaches. We begin with a presentation of the methods. Then we discuss the use of some acceleration techniques, including cascading multigrid, for all the tested algorithms. The main goal of our paper is to analyze and compare recent solvers for the PSFS problem proposed in the literature.