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 matriz 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\leq i<j\leq n}(\alpha _{j}-\alpha _{i})$

Esta fórmula é conhecida por vezes como o discriminante, mas em geral o discriminante é 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\leq i<j\leq 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 $-\alpha _{1}$ e somamos com a coluna $c_{i+1}$:

${\begin{matrix}V\end{matrix}}={\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 _{n}&\alpha _{n}^{2}&\dots &\alpha _{n}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}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{bmatrix}}$

Calculando o determinante, pelo Teorema de Laplace acaba-se por eliminar 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 10 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\leq i<j\leq 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_{i}x^{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 propuseram algoritmos numericamente estáveis que exploram a estrutura da matriz de Vandermonde para resolver o problema 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.