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}}$.

Determinant

De determinant van een vierkante Vandermonde-matrix ${\displaystyle V_{n}}$ van de orde ${\displaystyle n>1}$ is:

${\displaystyle V_{n}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-2}&x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-2}&x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n}&x_{n}^{2}&\ldots &x_{n}^{n-2}&x_{n}^{n-1}\end{vmatrix}}}$

Het aantal variabelen ${\displaystyle x_{i}}$ in deze determinant is ${\displaystyle n}$.

Voor deze determinant geldt:

${\displaystyle V_{n}=\prod _{1\leq i<j\leq n}(x_{j}-x_{i})}$

Het bewijs van deze stelling gaat met volledige inductie naar het aantal variabelen ${\displaystyle n}$ in de determinant.

Voor ${\displaystyle n=2}$ is de bewering juist.

${\displaystyle V_{2}={\begin{vmatrix}1&x_{1}\\1&x_{2}\end{vmatrix}}=x_{2}-x_{1}}$

Er wordt in het volgende gebruikgemaakt van de regels voor het vegen van een determinant.

Stel dat de bewering juist is voor zekere ${\displaystyle n}$, dan geldt:

${\displaystyle V_{n+1}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-1}&x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-1}&x_{2}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}&x_{n+1}^{2}&\ldots &x_{n+1}^{n-1}&x_{n+1}^{n}\end{vmatrix}}={\begin{vmatrix}1&x_{1}&x_{1}^{2}&\ldots &x_{1}^{n-1}&0\\1&x_{2}&x_{2}^{2}&\ldots &x_{2}^{n-1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}&x_{n+1}^{2}&\ldots &x_{n+1}^{n-1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}}$

De tweede determinant ontstaat door in de eerste determinant ${\displaystyle x_{1}}$ maal de voorlaatste kolom van de laatste kolom af te trekken. Zo van achter naar voren voortgaand, ontstaat door steeds ${\displaystyle x_{1}}$ maal een kolom van de volgende kolom af te trekken:

${\displaystyle V_{n+1}={\begin{vmatrix}1&0&0&\ldots &0&0\\1&x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&\ldots &x_{2}^{n-1}-x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n+1}-x_{1}&x_{n+1}^{2}-x_{n+1}x_{1}&\ldots &x_{n+1}^{n-1}-x_{n+1}^{n-2}x_{1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}}$

Omdat op de eerste rij, behalve op de eerste plaats alleen maar 0 staat, volgt:

${\displaystyle V_{n+1}={\begin{vmatrix}x_{2}-x_{1}&x_{2}^{2}-x_{2}x_{1}&\ldots &x_{2}^{n-1}-x_{2}^{n-2}x_{1}&x_{2}^{n}-x_{2}^{n-1}x_{1}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\x_{n+1}-x_{1}&x_{n+1}^{2}-x_{n+1}x_{1}&\ldots &x_{n+1}^{n-1}-x_{n+1}^{n-2}x_{1}&x_{n+1}^{n}-x_{n+1}^{n-1}x_{1}\end{vmatrix}}}$

Uit elke rij kan een gemeenschappelijke factor worden gehaald:

${\displaystyle V_{n+1}=(x_{2}-x_{1})\ldots (x_{n+1}-x_{1}){\begin{vmatrix}1&x_{2}&\ldots &x_{2}^{n-2}&x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n+1}&\ldots &x_{n+1}^{n-2}&x_{n+1}^{n-1}\end{vmatrix}}}$

De overblijvende determinant is een Vandermonde-determinant van de orde ${\displaystyle n}$, die volgens de inductieveronderstelling de juiste vorm heeft.