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=\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]$

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:

$\left|\begin{array}{c}V\end{array}\right|=\prod _{1\le i<j\le 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.

$\left|\begin{array}{c}V\end{array}\right|=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 $-{\alpha }_1$ e somamos com a coluna $c_{i+1}$:

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

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.

$\left|\begin{array}{c}V\end{array}\right|=\left|\begin{array}{cccc}{\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)\\ ⋮& ⋮& & ⋮\\ {\alpha }_n-{\alpha }_1& {\alpha }_n({\alpha }_n-{\alpha }_1)& \dots & {\alpha }_n^{n-2}({\alpha }_n-{\alpha }_1)\end{array}\right|$

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

$\left|\begin{array}{c}V\end{array}\right|=({\alpha }_2-{\alpha }_1)({\alpha }_3-{\alpha }_1)\dots ({\alpha }_n-{\alpha }_1)\left|\begin{array}{ccccc}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}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& {\alpha }_n& {\alpha }_n^2& \dots & {\alpha }_n^{n-2}\end{array}\right|$

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

$\left|\begin{array}{c}V\end{array}\right|=\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:

$\left[\begin{array}{ccccc}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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_n& x_n^2& \dots & x_n^{n-1}\end{array}\right]\cdot \left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ ⋮\\ a_{n-1}\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ y_2\\ ⋮\\ y_{n-1}\end{array}\right]$

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 $𝒪(n^2)$ operações ao invés de $𝒪(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.

Predefinição:Classes de matriz