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 $m\times n$-matrix van de vorm:

$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

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

voor alle indices $i$ en $j$. Sommige auteurs gebruiken de getransponeerde van de bovenstaande matrix.

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

Veeltermevaluatie

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

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

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

Door de Vandermonde-matrix

$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

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

krijgt men de vector met de te berekenen waarden:

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

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

Interpolatie van een polynoom

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

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

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

${\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 $p_{0},p_{1},\ldots ,p_{n}$ bij kleine veranderingen in $y_{0},y_{1},\ldots ,y_{n}$.

Determinant

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

$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 $x_{i}$ in deze determinant is $n$.

Voor deze determinant geldt:

$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 $n$ in de determinant.

Voor $n=2$ is de bewering juist.

$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 $n$, dan geldt:

$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 $x_{1}$ maal de voorlaatste kolom van de laatste kolom af te trekken. Zo van achter naar voren voortgaand, ontstaat door steeds $x_{1}$ maal een kolom van de volgende kolom af te trekken:

$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:

$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:

$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 $n$, die volgens de inductieveronderstelling de juiste vorm heeft.

Bronnen, noten en/of referenties