Vandermondova matice

V lineární algebře se čtvercová matice nazývá Vandermondova matice, pokud má v každém řádku po sobě jdoucí členy geometrické posloupnosti počínaje jedničkou.

Matice je pojmenovaná po francouzském matematiku Alexandru-Théophilovi Vandermondovi (1735-1796).

Vandermondova matice je regulární, právě když má různé řádky, a tedy i různé kvocienty odpovídajících posloupností.

Definice

Vandermondova matice řádu $n$ určená uspořádanou $n$ - ticí reálných čísel $(x_{1},x_{2},\ldots ,x_{n})$ je:

{\boldsymbol {V}}(x_{1},\dots ,x_{n})={\begin{pmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n-1}&x_{n-1}^{2}&\dots &x_{n-1}^{n-1}\\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n-1}\end{pmatrix}}

s prvky $v_{ij}=x_{i}^{j-1}$

Vandermondovu matici lze obecněji definovat nad libovolným tělesem.

Vlastnosti

Vandermondův determinant

Determinant Vandermondovy matice se nazývá Vandermondův determinant a lze jej vyjádřit výrazem:

\det {\boldsymbol {V}}(x_{1},\ldots ,x_{n})=\prod _{1\leq i<j\leq n}(x_{j}-x_{i})

Důkaz

Důkaz využívá skutečnosti, že řádková ani sloupcová operace spočívající v přičtení skalárního násobku jiného řádku, resp. sloupce nemění determinant.

V prvním kroku je od každého sloupce (kromě prvního) odečten $x_{n}$ -násobek předchozího sloupce. Odečítání jsou provedena tak, že se začne od posledních sloupců, aby se odečetl sloupec, který ještě nebyl změněn). Výsledná matice je:

{\begin{pmatrix}1&x_{1}-x_{n}&x_{1}(x_{1}-x_{n})&\dots &x_{1}^{n-2}(x_{1}-x_{n})\\1&x_{2}-x_{n}&x_{2}(x_{2}-x_{n})&\dots &x_{2}^{n-2}(x_{2}-x_{n})\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n-1}-x_{n}&x_{n-1}(x_{n-1}-x_{n})&\dots &x_{n-1}^{n-2}(x_{n-1}-x_{n})\\1&0&0&\dots &0\\\end{pmatrix}}

Laplaceův rozvoj podél posledního řádku sníží řád matice o 1. Následně lze z ostatních řádků vytknout členy $x_{n}-x_{i}$ . Současné provedení těchto operací nezmění znaménko:

\det({\boldsymbol {V}}(x_{1},\dots ,x_{n}))=(x_{n}-x_{1})(x_{n}-x_{2})\cdots (x_{n}-x_{n-1}){\begin{vmatrix}1&x_{1}&\dots &x_{1}^{n-2}\\1&x_{2}&\dots &x_{2}^{n-2}\\\vdots &\vdots &\ddots &\vdots \\1&x_{n-1}&\dots &x_{n-1}^{n-2}\\\end{vmatrix}}=\det({\boldsymbol {V}}(x_{1},\dots ,x_{n-1}))\prod _{1\leq i<n}(x_{n}-x_{i})

Použitím matematické indukce na Vandermondovu matici ${\boldsymbol {V}}(x_{1},\dots ,x_{n-1})$ dává požadované vyjádření $\det({\boldsymbol {V}}(x_{1},\dots ,x_{n}))$ jako součin všech rozdílů $x_{j}-x_{i}$ , kde $i<j$ .

Regularita Vandermondova determinantu

Z předchozí vlastnosti bezprostředně vyplývá, že Vandermondova matice je regulární, právě když hodnoty $x_{1},\ldots ,x_{n}$ jsou navzájem různé.

Numerické záležitosti

Při použití přirozené báze prostoru polynomů je Vandermondova matice velmi špatně podmíněna a související výpočty pomocí standardních metod v čase $O(n^{3})$ jsou relativně pomalé. Pro polynomy se proto v numerických algoritmech volí jiné reprezentace, jak je uvedeno níže.

Aplikace

Proložení polynomu

Vandermondova matice se používá např. v případech, kdy je zadána množina $n$ bodů o souřadnicích $(x_{1},y_{1}),(x_{2},y_{2}),\dots ,(x_{n},y_{n})$ a je třeba určit polynom stupně nejvýše $n-1$ , který jimi prochází. Koeficienty $a_{0},\dots ,a_{n-1}$ hledaného polynomu

p(x)=a_{0}+a_{1}x+a_{x}x^{2}+\dots +a_{n-1}x^{n-1}

jsou řešením následující soustavy lineárních rovnic:

{\begin{pmatrix}1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n-1}\\1&x_{3}&x_{3}^{2}&\dots &x_{3}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n-1}\\\end{pmatrix}}\cdot {\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\\vdots \\a_{n-1}\\\end{pmatrix}}={\begin{pmatrix}y_{1}\\y_{2}\\y_{3}\\\vdots \\y_{n}\\\end{pmatrix}}

Diagonalizace doprovodné matice

Je-li ${\boldsymbol {C}}$ doprovodná matice monického polynomu

p(x)=\prod _{i=1}^{n}(x-x_{i})=b_{0}+b_{1}x+\ldots +b_{n-1}x^{n-1}+x^{n}

,

vyjádřeného v různých bodech $x_{1},\ldots ,x_{n}$ , potom Vandermondova matice ${\boldsymbol {V}}={\boldsymbol {V}}(x_{1},\ldots ,x_{n})$ diagonalizuje ${\boldsymbol {C}}$ , neboť platí:

{\boldsymbol {VCV}}^{-1}={\rm {diag}}(x_{1},\dots ,x_{n})

.

Diskrétní Fourierova transformace

Provedení diskrétní Fourierovy transformace (i její inverze) lze zapsat jako součin vstupního vektoru délky $n$ s konkrétní komplexní Vandermondovou maticí řádu $n$ . Hodnoty $x_{i}$ v definici Vandermondovy matice jsou komplexní odmocniny z 1. Diskrétní Fourierova transformace pak efektivně počítá hodnoty $y_{i}$ jako hodnoty polynomu s (komplexními) koeficienty $a_{0},\dots ,a_{n-1}$ v bodech $x_{i}=\omega _{n}^{i-1}$ , kde $\omega _{n}$ je zvolená $n$ -tá primitivní odmocnina z 1 a $i\in \{1,\dots ,n\}$ .

Polynomická regrese

Ve statistice rovnice ${\boldsymbol {Va}}={\boldsymbol {y}}$ znamená, že Vandermondova matice ${\boldsymbol {V}}$ je regresní maticí polynomické regrese .

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Vandermonde matrix na anglické Wikipedii a Vandermonde-Matrix na německé Wikipedii.

Literatura

BÄRTSCH, Hans-Jochen. Matematické vzorce. Praha: Academia, 2006. 832 s. ISBN 80-200-1448-9. Kapitola Matice, s. 180–198.
BEČVÁŘ, Jindřich. Lineární algebra. 1.. vyd. Praha: Matfyzpress, 2019. 436 s. ISBN 978-80-7378-392-1.
HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1.. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5.
OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online.
MOTL, Luboš; ZAHRADNÍK, Miloš. Pěstujeme lineární algebru [online]. [cit. 2023-02-20]. Dostupné online.