Vandermonde-matrix

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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×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.[1] (Sommige auteurs gebruiken de getransponeerde van de bovenstaande matrix.)

Een (vierkante) Vandermonde-matrix wordt dus volledig bepaald door de getallen  \alpha_i (i = 1, 2, ... n).

Veeltermevaluatie[bewerken]

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

 v(x) = \sum^{n}_{i=0} {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)

verkrijgt men de vector met de te berekenen waarden:

 V\,v= (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.

Veelterminterpolatie[bewerken]

Nauw verwant met het vorige probleem is dat van de veelterminterpolatie: gegeven n + 1 verschillende punten (x_i,y_i), i = 0, 1, \dots , n, bepaal de veelterm p(x) van graad n die door de gegeven punten loopt, met andere woorden waarvoor geldt dat

p(x_i) = \sum^n_{j=0} p_j x_i^j = y_i,\;  i=0,\ldots,n.

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

Determinant[bewerken]

De determinant van Vandermonde V_n van de orde n, n>1, is:

V_n = \begin{vmatrix}
  1 & x_1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\
  1 & x_2 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
  1 & x_n & x_n^2 & \cdots & 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 \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 = 
\begin{vmatrix}
  1 & x_1\\
  1 & x_2 
\end{vmatrix}
=x_2-x_1

Stel dat de bewering juist is voor zekere n; dan geldt:

V_{n+1} = 
\begin{vmatrix}
  1 & x_1 & x_1^2 & \cdots & x_1^{n-1} & x_1^{n} \\
  1 & x_2 & x_2^2 & \cdots & x_2^{n-1} & x_2^{n} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
  1 & x_{n+1} & x_{n+1}^2 & \cdots & x_{n+1}^{n-1} & x_{n+1}^{n}
\end{vmatrix}
=
\begin{vmatrix}
  1 & x_1 & x_1^2 & \cdots & x_1^{n-1} & 0 \\
  1 & x_2 & x_2^2 & \cdots & 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 & \cdots & x_{n+1}^{n-1} & x_{n+1}^{n}-x_{n+1}^{n-1}x_1
\end{vmatrix}

De tweede vorm ontstaat door van de laatste kolom x_1 maal de voorlaatste af te trekken. Omdat de determinant van een matrix gelijk is aan de determinant van de gespiegelde matrix, kunnen ook de kolommen geveegd worden. Zo voortgaand, van achter naar voren, steeds van een kolom x_1 maal de voorgaande kolom aftrekkend, ontstaat:

V_{n+1} = 
\begin{vmatrix}
  1 & 0 & 0 & \cdots & 0 & 0 \\
  1 & x_2-x_1 & x_2^2-x_2x_1 & \cdots & 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 & \cdots & 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_2x_1 & \cdots & 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 & \cdots & 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 gehaald worden:

V_{n+1} = (x_2-x_1)\ldots(x_{n+1}-x_1)
\begin{vmatrix}
  1 & x_2 & \cdots & x_2^{n-2} & x_2^{n-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
 1 & x_{n+1} & \cdots & 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.

Voetnoten[bewerken]

  1. (en) Roger A. Horn en Charles R. Johnson (1991),Topics in matrix analysis,, Cambridge University Press. Zie paragraaf 6.1