Vandermonde-matrix

In de lineaire algebra, een deelgebied van de wiskunde, is een Vandermonde-matrix, vernoemd naar de 18e-eeuwse Franse wiskundige Alexandre-Théophile Vandermonde, een matrix met als opgelegde voorwaarde dat elke rij in deze matrix uit een meetkundige rij moet bestaan, dat wil zeggen, een ${\displaystyle m\times n}$-matrix van de vorm:

${\displaystyle V={\begin{bmatrix}1&\alpha _{1}&\alpha _{1}^{2}&\dots &\alpha _{1}^{n-1}\\1&\alpha _{2}&\alpha _{2}^{2}&\dots &\alpha _{2}^{n-1}\\1&\alpha _{3}&\alpha _{3}^{2}&\dots &\alpha _{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha _{m}&\alpha _{m}^{2}&\dots &\alpha _{m}^{n-1}\\\end{bmatrix}}}$

of

${\displaystyle V_{i,j}=\alpha _{i}^{j-1}}$

voor alle indices ${\displaystyle i}$ en ${\displaystyle j}$.^[1] Sommige auteurs gebruiken de getransponeerde van de bovenstaande matrix.

Een Vandermonde-matrix wordt dus volledig bepaald door de getallen ${\displaystyle \alpha _{i}(i=1,2,\ldots ,n).}$

Veeltermevaluatie

De Vandermonde-matrix komt aan bod bij het evalueren van een polynoom

${\displaystyle v(x)=\sum _{i=0}^{n}v_{i}x^{i}}$

in een aantal punten ${\displaystyle x_{0},x_{1},\dots ,x_{m}}$.

Door de Vandermonde-matrix

${\displaystyle V={\begin{bmatrix}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{m}&x_{m}^{2}&\dots &x_{m}^{n}\\\end{bmatrix}}}$

te vermenigvuldigen met de vector

${\displaystyle v=(v_{0},v_{1},\dots ,v_{n})}$

krijgt men de vector met de te berekenen waarden:

${\displaystyle V\,v=(v(x_{0}),v(x_{1}),\ldots ,v(x_{m}))}$

Als de punten ${\displaystyle x_{0},x_{1},\dots ,x_{n-1}}$ de ${\displaystyle n}$-de eenheidswortels zijn, komt dit neer op de berekening van de discrete fouriertransformatie van ${\displaystyle v}$.

Interpolatie van een polynoom

Nauw verwant met het vorige probleem is dat van de interpolatie van een polynoom: gegeven ${\displaystyle n+1}$ verschillende punten ${\displaystyle (x_{i},y_{i}),i=0,1,\ldots ,n,}$ bepaal de polynoom ${\displaystyle p(x)}$ van de graad ${\displaystyle n}$ die door de gegeven punten loopt; met andere woorden waarvoor geldt dat voor ${\displaystyle i=0,\ldots ,n}$

${\displaystyle p(x_{i})=\sum _{j=0}^{n}p_{j}x_{i}^{j}=y_{i}}$

Om de onbekende coëfficiënten ${\displaystyle p_{0},p_{1},\dots ,p_{n}}$ te vinden moet men het volgende stelsel van lineaire vergelijkingen oplossen, geschreven in matrixnotatie:

${\displaystyle {\begin{bmatrix}1&x_{0}&x_{0}^{2}&\ldots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n}\\\vdots &\vdots &\vdots &&\vdots \\1&x_{n}&x_{n}^{2}&\ldots &x_{n}^{n}\\\end{bmatrix}}{\begin{bmatrix}p_{0}\\p_{1}\\\vdots \\p_{n}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}}$.

De coëfficiëntenmatrix van dit stelsel is een Vandermonde-matrix. Een Vandermonde-matrix is echter slecht geconditioneerd, wat betekent dat er grote afwijkingen kunnen optreden in de berekende waarden ${\displaystyle p_{0},p_{1},\ldots ,p_{n}}$ bij kleine veranderingen in ${\displaystyle y_{0},y_{1},\ldots ,y_{n}}$.