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 zodanig dat

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} met coëfficiënten  v_0, v_1, \dots , v_n in een aantal punten  t_0, t_1, \dots , t_n .

Het probleem is dus: Bereken


r_0 = v(t_0), r_1 = v(t_1),  \dots ,  r_n = v(t_n) \!

waar r_0, r_1, \dots , r_n de vectoren vormen, die men bekomt door de vermenigvuldiging van de Vandermonde-matrix V:

V=\begin{bmatrix}
1 & t_0 & t_0^2 & \dots & t_0^n\\
1 & t_1 & t_1^2 & \dots & t_1^n\\
\vdots & \vdots & \vdots & \ddots &\vdots \\
1 & t_n & t_n^2 & \dots & t_n^n\\
\end{bmatrix}

met de vector v:

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

Wanneer de punten t_0, t_1, \dots ,t_{n-1} de n-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 van de orde n, Vn, 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:

\displaystyle V_n = \prod_{1 \le i < j \le n} \left({x_j - x_i}\right)

Het bewijs van deze stelling gaat met volledige inductie naar het aantal variabelen x_i in de determinant.

Voetnoten[bewerken]

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