A Recursive Algorithm to Determining Lagrange Basis Polynomial Using Chebyshev Nodes

Interpolation is the process of estimating unknown values that are located between known values. Usually this process is done using different kinds of continuous functions. One of the most common types of continuous functions which can be used for interpolation, are polynomials. In approximation theory polynomial interpolation is utilized to approximating a complex function using a polynomial. In this issue polynomial coefficients can be determined using different computing methods. The basic procedure to determining the coefficients, is solution of vandermonde system. The system however, has only theoretical significance, since its solution by numerical methods is ill-advised on all counts (computational effort, storage requirement, accuracy). This is the reason to using some alternative methods such as Newton and Lagrange. These methods are two well-known representations of the unique interpolation polynomial. Newton representation is based on determining divided differences, while the other one is a very elegant alternative representation of Newtons general formula that does not require the computation of finite or divided differences. Lagrange representation can be utilized for any sets of interpolating points. In some cases Lagrange representation is used for interpolating between equidistant nodes. For example in GNSS positioning it is a common issue to find the satellites position using the coordinates are given in 15 minutes constant interval. generally computing Lagrange basis polynomial using current method requires O(n2) operations. So when we use polynomials with high degrees for interpolation, we expect a significant increase of computational effort. According to this issue in the last article we introduced a recursive algorithm to obtaining Lagrange coefficients using equidistant nodes. By the use of this algorithm, we had a significant improvement in computations speed. Despite the usage of equidistant interpolation, it is not a good idea to use evenly spaced points to approximating a function. Because in such a situation interpolated polynomial has wild oscillations near the edges of interpolation interval and does not converge to the main function, specially in high order polynomials. This nonconvergence is called Runge phenomenon. To avoiding this problem, other sets of interpolating points should be used, with more density at the end points of interval. The simplest examples of such a point sets, are the families of Chebyshev points. These points are set of zeros of the Chebyshev polynomial. By using Chebyshev nodes, interpolation will be more accurate. Since unwanted oscillations are gone. Due to the mentioned advantages of Chebyshev nodes, in this paper we are going to introduce a recursive algorithm  to obtaining Lagrange coefficients using these sets of points. computing Lagrange basis polynomial using this method requires O(n) operations unlike the current method. So by the use of recursive algorithm, we expect speed increase in computations process. To investigating this issue we obtained Lagrange basis polynomial for all integer numbers within [1,1000] interval. All of coefficients were computed for different polynomial degrees from 1 to 10 using MATLAB. In the following we recorded calculating times for both of computing algorithms and also for different polynomial degrees. After checking computing times we found a significant increase in processing speed by the use of recursive method. Although this method reduces processing time for all polynomial degrees, it is more effective when we use polynomials with high degrees. In other words when we use a polynomial with degree of one, the recursive algorithm is 1/3 times faster in comparison with usual algorithm; But when we use a polynomial in degree of 10, it is 3 times faster. So we conclude that it is logical to use this algorithm specially when we use high degree polynomials for interpolation.