Macierz Vandermonde’a

Macierz Vandermonde’a – macierz kwadratowa n × n {\displaystyle n\times n} postaci:

A = ( 1 x 1 x 1 2 ⋯ x 1 n − 1 1 x 2 x 2 2 ⋯ x 2 n − 1 ⋮ ⋮ ⋮ ⋱ ⋮ 1 x n x n 2 ⋯ x n n − 1 ) . {\displaystyle A=\left({\begin{matrix}1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n-1}\end{matrix}}\right).}

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

det A = ∏ 1 ⩽ i < j ⩽ n ( x j − x i ) . {\displaystyle \det A=\prod _{1\leqslant i<j\leqslant n}(x_{j}-x_{i}).}

Przykład: Macierz

A = ( 1 1 1 1 1 2 4 8 1 3 9 27 1 4 16 64 ) {\displaystyle 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 ) ⋅ ( x 3 − x 1 ) ⋅ ( x 4 − x 1 ) ⋅ ( x 3 − x 2 ) ⋅ ( x 4 − x 2 ) ⋅ ( x 4 − x 3 ) = 1 ⋅ 2 ⋅ 3 ⋅ 1 ⋅ 2 ⋅ 1 = 12 {\displaystyle \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 ) , … , ( x n − 1 , y n − 1 ) } {\displaystyle \{(x_{0},y_{0}),(x_{1},y_{1}),\dots ,(x_{n-1},y_{n-1})\}} istnieje dokładnie jeden wielomian W ( x ) {\displaystyle W(x)} o stopniu mniejszym niż n {\displaystyle n} i taki, że dla każdego k y k = W ( x k ) . {\displaystyle ky_{k}=W(x_{k}).}

Dowód:

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

( a 0 , a 1 , … , a n − 1 ) T = V − 1 ( y 0 , y 1 , … , y n − 1 ) T {\displaystyle (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 ) . {\displaystyle O(n^{3}).} Zastosowanie postaci Lagrange’a wielomianu interpolacyjnego

W ( x ) = ∑ k = 0 n − 1 y k ∏ i ≠ k ( x − x i ) ∏ i ≠ k ( x k − x i ) {\displaystyle 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 2 ) . {\displaystyle O(n^{2}).}

Zobacz też

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

Linki zewnętrzne

  • Eric W.E.W. Weisstein Eric W.E.W., Vandermonde Matrix, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).