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=\left[\begin{array}{ccccc}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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\alpha }_m& {\alpha }_m^2& \dots & {\alpha }_m^{n-1}\end{array}\right]$

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,\dots ,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=\left[\begin{array}{ccccc}1& x_0& x_0^2& \dots & x_0^n\\ 1& x_1& x_1^2& \dots & x_1^n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_m& x_m^2& \dots & x_m^n\end{array}\right]$

te vermenigvuldigen met de vector

$v=(v_0,v_1,\dots ,v_n)$

krijgt men de vector met de te berekenen waarden:

$Vv=(v(x_0),v(x_1),\dots ,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,\dots ,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,\dots ,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:

$\left[\begin{array}{ccccc}1& x_0& x_0^2& \dots & x_0^n\\ 1& x_1& x_1^2& \dots & x_1^n\\ ⋮& ⋮& ⋮& & ⋮\\ 1& x_n& x_n^2& \dots & x_n^n\end{array}\right]\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_n\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_n\end{array}\right]$.

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,\dots ,p_n$ bij kleine veranderingen in $y_0,y_1,\dots ,y_n$.

Determinant

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

$V_n=\left|\begin{array}{cccccc}1& x_1& x_1^2& \dots & x_1^{n-2}& x_1^{n-1}\\ 1& x_2& x_2^2& \dots & x_2^{n-2}& x_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_n& x_n^2& \dots & x_n^{n-2}& x_n^{n-1}\end{array}\right|$

Het aantal variabelen $x_i$ in deze determinant is $n$.

Voor deze determinant geldt:

$V_n=\prod _{1\le i<j\le 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=\left|\begin{array}{cc}1& x_1\\ 1& x_2\end{array}\right|=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}=\left|\begin{array}{cccccc}1& x_1& x_1^2& \dots & x_1^{n-1}& x_1^n\\ 1& x_2& x_2^2& \dots & x_2^{n-1}& x_2^n\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_{n+1}& x_{n+1}^2& \dots & x_{n+1}^{n-1}& x_{n+1}^n\end{array}\right|=\left|\begin{array}{cccccc}1& x_1& x_1^2& \dots & x_1^{n-1}& 0\\ 1& x_2& x_2^2& \dots & x_2^{n-1}& x_2^n-x_2^{n-1}{x}_1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_{n+1}& x_{n+1}^2& \dots & x_{n+1}^{n-1}& x_{n+1}^n-x_{n+1}^{n-1}{x}_1\end{array}\right|$

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}=\left|\begin{array}{cccccc}1& 0& 0& \dots & 0& 0\\ 1& x_2-x_1& x_2^2-x_2{x}_1& \dots & x_2^{n-1}-x_2^{n-2}{x}_1& x_2^n-x_2^{n-1}{x}_1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 1& x_{n+1}-x_1& x_{n+1}^2-x_{n+1}{x}_1& \dots & x_{n+1}^{n-1}-x_{n+1}^{n-2}{x}_1& x_{n+1}^n-x_{n+1}^{n-1}{x}_1\end{array}\right|$

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

$V_{n+1}=\left|\begin{array}{ccccc}{x}_2-x_1& x_2^2-x_2{x}_1& \dots & x_2^{n-1}-x_2^{n-2}{x}_1& x_2^n-x_2^{n-1}{x}_1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ x_{n+1}-x_1& x_{n+1}^2-x_{n+1}{x}_1& \dots & x_{n+1}^{n-1}-x_{n+1}^{n-2}{x}_1& x_{n+1}^n-x_{n+1}^{n-1}{x}_1\end{array}\right|$

Uit elke rij kan een gemeenschappelijke factor worden gehaald:

$V_{n+1}=(x_2-x_1)\dots (x_{n+1}-x_1)\left|\begin{array}{ccccc}1& x_2& \dots & x_2^{n-2}& x_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_{n+1}& \dots & x_{n+1}^{n-2}& x_{n+1}^{n-1}\end{array}\right|$

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