Macierz Vandermonde’a – macierz kwadratowa
n
×
n
{\displaystyle n\times n}
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
edytuj
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})\}}
wielomian
W
(
x
)
{\displaystyle W(x)}
stopniu mniejszym niż
n
{\displaystyle n}
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})}
V
{\displaystyle V}
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}).}
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}).}
Linki zewnętrzne
edytuj
