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. 

Portály: Matematika