Macierz Vandermonde'a

Macierz Vandermonde'a - macierzą kwadratową n x n postaci:

$A = \left( \begin{matrix} 1 & x_1 & x^2_1 & \cdots & x^{n-1}_1 \\ 1 & x_2 & x^2_2 & \cdots & x^{n-1}_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x^2_n & \cdots & x^{n-1}_n \end{matrix} \right)$

Wyznacznik tej macierzy nazywany jest wyznacznikiem Vandermonde'a i jest wielomianem postaci:

$\det\ A = \prod_{1 \leqslant i<j \leqslant n} (x_j - x_i)$

Przykład: Macierz

$A = \left( \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 1 & 4 & 16 & 64 \\ \end{matrix} \right)$

jest macierzą Vandermonde'a. Jej wyznacznik jest równy

$\det\ A = (x_2 - x_1) \cdot (x_3 - x_1) \cdot (x_4 - x_1) \cdot (x_3 - x_2) \cdot (x_4 - x_2) \cdot (x_4 - x_3) = 1 \cdot 2 \cdot 3 \cdot 1 \cdot 2 \cdot 1 = 12$

Jednoznaczność wielomianu interpolacyjnego

Macierz Vandermonde'a pozwala udowodnić następujące twierdzenie o jednoznaczności wielomianu interpolacyjnego: Dla dowolnego zbioru różnych punktów: $\{(x_0, y_0), (x_1, y_1), \ldots, (x_{n-1}, y_{n-1})\}$ istnieje dokładnie jeden wielomian W(x) o stopniu mniejszym niż n i taki, że dla każdego k y_k = W(x_k).

Dowód:

Ponieważ punkty są różne, to wyznacznik macierzy Vandermonde'a stworzonej z punktów $(x_0, x_1, \ldots, x_{n-1})$ jest różny od 0, więc macierz jest odwracalna. Niech $V$ oznacza tę macierz. Rozwiązanie układu równań:

$(a_0, a_1, \ldots, a_{n-1})^{T} = V^{-1} (y_0, y_1, \ldots, y_{n-1})^{T}$

pozwala na wyliczenie współczynników wielomianu.

Stosując metodę eliminacji Gaussa można rozwiązać ten układ w czasie O(n³). Zastosowanie postaci Lagrange'a wielomianu interpolacyjnego

$W(x) = \sum_{k=0}^{n-1} y_k \frac{\prod_{i \neq k} (x - x_i)}{\prod_{i \neq k} (x_k - x_i)}$

pozwala na wykonanie tego w czasie O(n²).

Zobacz też

• Interpolacja
• Metoda eliminacji Gaussa
• Metoda LU
• macierz odwrotna
• macierz transponowana