Macierz Vandermonde'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Macierz Vandermonde'a - macierz kwadratowa 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[edytuj | edytuj kod]

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 yk = W(xk).

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(n3). 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(n2).

Zobacz też[edytuj | edytuj kod]