Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Vandermonde matrix
Summary
In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an matrix
with entries , the jth power of the number , for all zero-based indices and . Most authors define the Vandermonde matrix as the transpose of the above matrix.
The determinant of a square Vandermonde matrix (when ) is called a Vandermonde determinant or Vandermonde polynomial. Its value is:
This is non-zero if and only if all are distinct (no two are equal), making the Vandermonde matrix invertible.
The polynomial interpolation problem is to find a polynomial which satisfies for given data points . This problem can be reformulated in terms of linear algebra by means of the Vandermonde matrix, as follows. computes the values of at the points via a matrix multiplication , where is the vector of coefficients and is the vector of values (both written as column vectors):
If and are distinct, then V is a square matrix with non-zero determinant, i.e. an invertible matrix. Thus, given V and y, one can find the required by solving for its coefficients in the equation : . That is, the map from coefficients to values of polynomials is a bijective linear mapping with matrix V, and the interpolation problem has a unique solution. This result is called the unisolvence theorem, and is a special case of the Chinese remainder theorem for polynomials.
In statistics, the equation means that the Vandermonde matrix is the design matrix of polynomial regression.
In numerical analysis, solving the equation naïvely by Gaussian elimination results in an algorithm with time complexity O(n3). Exploiting the structure of the Vandermonde matrix, one can use Newton's divided differences method (or the Lagrange interpolation formula) to solve the equation in O(n2) time, which also gives the UL factorization of . The resulting algorithm produces extremely accurate solutions, even if is ill-conditioned. (See polynomial interpolation.)
The Vandermonde determinant is used in the representation theory of the symmetric group.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.