Vandermonde matrix

In mathematics, a Vandermonde matrix (according to A.-T. Vandermonde ) is a matrix that has a special form described below.

For a - tuple of real numbers or, more generally, of elements in a body , the Vandermonde matrix is ​​defined by: ${\displaystyle n}$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$

${\displaystyle V(x_{1},x_{2},\ldots ,x_{n})={\begin{pmatrix}1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\cdots &x_{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n-1}\end{pmatrix}}}$

The determinant is also called the Vandermonde determinant , it has the value

${\displaystyle \det V(x_{1},x_{2},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i})}$.

In particular, the Vandermonde matrix is regular if and only if the pairs are different . ${\displaystyle x_{i}}$

Application: polynomial interpolation

The Vandermonde matrix plays an important role in the interpolation of functions : If the function values ​​are to be interpolated at the interpolation points by a polynomial of degree (or less), then the approach leads ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle (f_{1},f_{2},\ldots ,f_{n})}$ ${\displaystyle p}$ ${\displaystyle n-1}$

${\displaystyle p(x)=a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n-1}x^{n-1}}$

on the linear system of equations

${\displaystyle {\begin{pmatrix}1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\cdots &x_{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n-1}\end{pmatrix}}\cdot {\begin{pmatrix}a_{0}\\\vdots \\a_{k}\\\vdots \\a_{n-1}\end{pmatrix}}={\begin{pmatrix}f_{1}\\\vdots \\f_{i}\\\vdots \\f_{n}\end{pmatrix}}}$

with a Vandermonde matrix as the coefficient matrix. From the property of the Vandermonde determinant mentioned above, it follows in particular that the interpolation problem can be solved uniquely precisely when all the interpolation points are different in pairs.

In the standard basis of the polynomials, however, the matrix is ​​very poorly conditioned and the resolution with standard methods with a running time in is quite expensive, which is why other representations are chosen for the polynomials. More at polynomial interpolation and below. ${\displaystyle O(n^{3})}$

Other properties

The Vandermonde matrix from the above system of equations diagonalizes the accompanying matrix of the polynomial for different support points , the following applies: ${\displaystyle V}$ ${\displaystyle C}$ ${\displaystyle p(x)=\prod _{i=1}^{n}(x-x_{i})=b_{0}+b_{1}x+\ldots +b_{n-1}x^{n-1}+x^{n}}$

${\displaystyle VCV^{-1}={\rm {diag}}(x_{1},x_{2},\dots ,x_{n})}$

For large numbers , the system of equations above can also be solved using the following relationship, through which the inverse of the Vandermonde matrix is ​​closely connected to its transpose . With the introduced polynomial coefficients one forms the Hankel matrix ${\displaystyle n}$

${\displaystyle H:={\begin{pmatrix}b_{1}&b_{2}&\cdots &b_{n-1}&1\\b_{2}&b_{3}&\cdots &1&0\\\vdots &&.\cdot \\b_{n-1}&1&&0\\1&0&&&0\end{pmatrix}}}$

and the diagonal matrix . If all support points are different in pairs, it is regular. This applies ${\displaystyle D:=\operatorname {diag} (p'(x_{i}))}$ ${\displaystyle D}$

${\displaystyle VHV^{T}=D,\quad V^{-1}=HV^{T}D^{-1}.}$

literature

• Uwe Luther, Karla Rost: Matrix exponentials and inversion of confluent Vandermonde matrices. In: Electronic Transactions on Numerical Analysis. Vol. 18, 2004, ISSN  1068-9613 , pp. 91-100.

Individual evidence

1. ↑ Christoph Ableitinger, Angela Herrmann: Learning from sample solutions for analysis and linear algebra. A work and exercise book . 1st edition. Vieweg + Teubner, Wiesbaden 2011, ISBN 978-3-8348-1724-2 , pp. 113-116 .

Web links

Weisstein, Eric W .: Vandermonde Matrix . In: MathWorld (English).