Matriz de Vandermonde

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.1 Alguns autores usam a transposta da matriz acima, ou seja, as colunas estão em progressão geométrica.

Determinante[editar | editar código-fonte]

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

 \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 o discriminante é definido como o quadrado da fórmula acima.

Demonstra-se essa fórmula por indução2 . 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 -\alpha_{1} 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[editar | editar código-fonte]

Os pontos vermelhos denotam os pares (xi,yi), 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,3 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áveis 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.4 5 6 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. a b Prova em inglês e referências adicionais http://www.proofwiki.org/wiki/Vandermonde_Determinant
  3. Gautschi, Walter. (1975). "Norm Estimates for Inverses of Vandermonde Matrices". Numerische Mathematik 23: 337–347. DOI:10.1007/BF01438260.
  4. 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.
  5. Björck, Å; V. Pereyra. (1970). "Solution of Vandermonde Systems of Equations". Mathematics of Computation 24: 893–903. DOI:10.2307/2004623.
  6. Calvetti, D and Reichel, L. (1993). "Fast Inversion of Vanderomnde-Like Matrices Involving Orthogonal Polynomials". BIT 33: 473–484. DOI:10.1007/BF01990529.