Macierz Vandermonde’a

Macierz Vandermonde’a – macierz kwadratowa $n\times n$ postaci:

$A=\left(\begin{array}{ccccc}1& x_1& x_1^2& \cdots & x_1^{n-1}\\ 1& x_2& x_2^2& \cdots & x_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^{n-1}\end{array}\right).$

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

$\det A=\prod _{1⩽i<j⩽n}(x_j-x_i).$

Przykład: Macierz

$A=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 2& 4& 8\\ 1& 3& 9& 27\\ 1& 4& 16& 64\end{array}\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),\dots ,(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,\dots ,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,\dots ,a_{n-1}{)}^T=V^{-1}(y_0,y_1,\dots ,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^3).$ Zastosowanie postaci Lagrange’a wielomianu interpolacyjnego

$W(x)=\sum _{k=0}^{n-1}{y}_k\frac{\prod _{i\ne k}(x-x_i)}{\prod _{i\ne k}(x_k-x_i)}$

pozwala na wykonanie tego w czasie $O(n^2).$

Zobacz też

• interpolacja
• macierz odwrotna
• macierz transponowana
• metoda eliminacji Gaussa
• metoda LU

Linki zewnętrzne

• Szablon:MathWorld