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:

${\displaystyle 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

${\displaystyle V_{i,j}=\alpha _{i}^{j-1}}$ , para todos os índices i e j.[1] 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[2]:

${\displaystyle {\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.[2] No caso da matriz 2x2 é fácil verificar.

${\displaystyle {\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 ${\displaystyle c_{i}}$ a coluna i, então multiplicamos a coluna ${\displaystyle c_{i}}$ por ${\displaystyle -\alpha _{1}}$ e somamos com a coluna ${\displaystyle c_{i+1}}$:

${\displaystyle {\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.

${\displaystyle {\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[3] que se pode fatorar os coeficientes caindo em uma matriz de Vandermonde n-1×n-1..

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle (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 ${\displaystyle P(x_{i})=y_{i}\,}$. A solução deste problema consiste em resolver o seguinte sistema linear:

${\displaystyle {\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 ${\displaystyle a_{i}\,}$ são os coeficientes do polinômio ${\displaystyle 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,[4] causando erros importantes no cálculo dos coeficientes ${\displaystyle 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 ${\displaystyle {\mathcal {O}}(n^{2})}$ operações ao invés de ${\displaystyle {\mathcal {O}}(n^{3})}$ exigidos pela eliminação gaussiana.[5][6][7] Estes métodos consistem em primeiro construir um polinômio de Newton e depois convertê-lo para a forma canônica acima.

Referências

1. Roger A. Horn and Charles R. Johnson (1991), Topics in matrix analysis, Cambridge University Press. See Section 6.1
2. Prova em inglês e referências adicionais http://www.proofwiki.org/wiki/Vandermonde_Determinant
3. «Determinante». Wikipédia, a enciclopédia livre. 1 de junho de 2017 
4. Gautschi, Walter (1975). «Norm Estimates for Inverses of Vandermonde Matrices». Numerische Mathematik. 23: 337–347. doi:10.1007/BF01438260 
5. Higham, N. J. (1988). «Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials». IMA Journal of Numerical Analysis. 8: 473–486. doi:10.1093/imanum/8.4.473 
6. Björck, Å; V. Pereyra (1970). «Solution of Vandermonde Systems of Equations». Mathematics of Computation. 24 (112): 893–903. doi:10.2307/2004623  A referência emprega parâmetros obsoletos |coautor= (ajuda)
7. Calvetti, D and Reichel, L (1993). «Fast Inversion of Vanderomnde-Like Matrices Involving Orthogonal Polynomials». BIT. 33 (33): 473–484. doi:10.1007/BF01990529  !CS1 manut: Nomes múltiplos: lista de autores (link)