Matriz de Vandermonde

Em álgebra linear, uma matriz de Vandermonde, cujo nome faz referência a Alexandre-Théophile Vandermonde, é uma matriz em que os termos de cada linha estão em progressão geométrica.

Uma matrix de Vandermonde de ordem m × n tem a forma geral:

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

ou

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

para todos os índices i e j. Alguns autores usam a transposta da matriz acima, ou seja, as colunas estão em progressão geométrica.

Determinante

O determinante de uma matriz de Vandermonde de tamanho n×n se expressa da seguinte forma:

$\begin{vmatrix} V \end{vmatrix}=\prod_{1 \le i<j\le n}(\alpha_j-\alpha_i)$

Esta fórmula é conhecida por vezes como o discriminante, mas em geral ele é definido como o quadrado da fórmula acima.

Demonstra-se essa fórmula por indução. No caso da matriz 2x2 é fácil verificar.

$\begin{vmatrix} V \end{vmatrix}=v_{1,1}v_{2,2} - v_{1,2}v_{2,1}=\alpha_2-\alpha_1=\prod_{1\le i<j\le 2} (\alpha_j-\alpha_i)$

Agora, provemos para a matriz nxn supondo válido para as matrizes n-1 x n-1. Seja c_i a coluna i, então multiplicamos a coluna c_i por − α_i e somamos com a coluna c_{i + 1}:

$\begin{vmatrix} V \end{vmatrix}=\begin{vmatrix} 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_n & \alpha_n^2 & \dots & \alpha_n^{n-1}\\ \end{vmatrix}=\begin{vmatrix} 1 & 0 & 0 & \dots & 0\\ 1 & \alpha_2-\alpha_1 & \alpha_2(\alpha_2-\alpha_1) & \dots & \alpha_2^{n-2}(\alpha_2-\alpha_1)\\ 1 & \alpha_3-\alpha_1 & \alpha_3(\alpha_3-\alpha_1) & \dots & \alpha_3^{n-2}(\alpha_3-\alpha_1)\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & \alpha_n-\alpha_1 & \alpha_n(\alpha_n-\alpha_1) & \dots & \alpha_n^{n-2}(\alpha_n-\alpha_1)\\ \end{vmatrix}$

Calculando o determinante, por propriedade se elimina a primeira linha e a primeira coluna, achando assim uma matriz de n-1×n-1, logo.

$\begin{vmatrix} V \end{vmatrix}=\begin{vmatrix} \alpha_2-\alpha_1 & \alpha_2(\alpha_2-\alpha_1) & \dots & \alpha_2^{n-2}(\alpha_2-\alpha_1)\\ \alpha_3-\alpha_1 & \alpha_3(\alpha_3-\alpha_1) & \dots & \alpha_3^{n-2}(\alpha_3-\alpha_1)\\ \vdots & \vdots & &\vdots \\ \alpha_n-\alpha_1 & \alpha_n(\alpha_n-\alpha_1) & \dots & \alpha_n^{n-2}(\alpha_n-\alpha_1)\\ \end{vmatrix}$

Segue da propriedade que se pode fatorar os coeficientes caindo em uma matriz de Vandermonde n-1×n-1..

$\begin{vmatrix} V \end{vmatrix}= (\alpha_2-\alpha_1)(\alpha_3-\alpha_1)\dots(\alpha_n-\alpha_1) \begin{vmatrix} 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-2}\\ 1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{n-2}\\ 1 & \alpha_4 & \alpha_4^2 & \dots & \alpha_4^{n-2}\\ \vdots & \vdots & \vdots & &\vdots \\ 1 & \alpha_n & \alpha_n^2 & \dots & \alpha_n^{n-2}\\ \end{vmatrix}$

E por hipótese de indução temos que

$\begin{vmatrix} V \end{vmatrix}=\prod_{1 \le i<j\le n}(\alpha_j-\alpha_i)$

Interpolação polinomial

Os pontos vermelhos denotam os pares (x_i,y_i), enquanto a curva azul mostra o gráfico do polinômio interpolador.

A matriz de Vandermonde surge naturalmente do problema de interpolação polinomial, ou seja: dado um conjunto de n pares ordenados $(x_i,y_i)\,$ com i variando entre 1 e n, encontrar o polinômio P(x) com n graus de liberdade (ou seja, o seu grau máximo é n-1) tal que $P(x_i)=y_i\,$. A solução deste problema consiste em resolver o seguinte sistema linear:

$\begin{bmatrix} 1 & x_1 & x_1^2 & \dots & x_1^{n-1}\\ 1 & x_2 & x_2^2 & \dots & x_2^{n-1}\\ 1 & x_3 & x_3^2 & \dots & x_3^{n-1}\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & x_n & x_n^2 & \dots & x_n^{n-1}\\ \end{bmatrix}\cdot \begin{bmatrix} a_0\\ a_1\\ a_2\\ \vdots \\ a_{n-1}\\ \end{bmatrix} = \begin{bmatrix} y_0\\ y_1\\ y_2\\ \vdots \\ y_{n-1}\\ \end{bmatrix}$

Onde $a_i\,$ são os coeficientes do polinômio $P(x)=\sum_{i=0}^{n-1} a_ix^i\,$. O fato de a matriz de Vardemonte ter determinante não nulo implica que o problema tem solução e que ela é única.

O número de condicionamento da matriz pode ser grande, causando erros importantes no cálculo dos coeficientes a_i se o sistema for resolvido usando eliminação gaussiana. Diversos autores proposeram algoritmos numericamente estável que exploram a estrutura da matriz de Vandermonde para resolver o problem em $\mathcal O(n^2)$ operações ao invés de $\mathcal O(n^3)$ exigidos pela eliminação gaussiana. Estes métodos consistem em primeiro construir um polinômio de Newton e depois convertê-lo para a forma canônica acima.