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 ${\displaystyle n}$ určená uspořádanou ${\displaystyle n}$- ticí reálných čísel ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ je:

${\displaystyle {\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 ${\displaystyle 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:

${\displaystyle \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 ${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle x_{n}-x_{i}}$. Současné provedení těchto operací nezmění znaménko:

${\displaystyle \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 ${\displaystyle {\boldsymbol {V}}(x_{1},\dots ,x_{n-1})}$ dává požadované vyjádření ${\displaystyle \det({\boldsymbol {V}}(x_{1},\dots ,x_{n}))}$ jako součin všech rozdílů ${\displaystyle x_{j}-x_{i}}$, kde ${\displaystyle i<j}$.

Regularita Vandermondova determinantu

Z předchozí vlastnosti bezprostředně vyplývá, že Vandermondova matice je regulární, právě když hodnoty ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ bodů o souřadnicích ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\dots ,(x_{n},y_{n})}$ a je třeba určit polynom stupně nejvýše ${\displaystyle n-1}$, který jimi prochází. Koeficienty ${\displaystyle a_{0},\dots ,a_{n-1}}$ hledaného polynomu

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle {\boldsymbol {C}}}$ doprovodná matice monického polynomu

${\displaystyle 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 ${\displaystyle x_{1},\ldots ,x_{n}}$, potom Vandermondova matice ${\displaystyle {\boldsymbol {V}}={\boldsymbol {V}}(x_{1},\ldots ,x_{n})}$diagonalizuje ${\displaystyle {\boldsymbol {C}}}$, neboť platí:

${\displaystyle {\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 ${\displaystyle n}$ s konkrétní komplexní Vandermondovou maticí řádu ${\displaystyle n}$. Hodnoty ${\displaystyle x_{i}}$ v definici Vandermondovy matice jsou komplexní odmocniny z 1. Diskrétní Fourierova transformace pak efektivně počítá hodnoty ${\displaystyle y_{i}}$ jako hodnoty polynomu s (komplexními) koeficienty ${\displaystyle a_{0},\dots ,a_{n-1}}$ v bodech ${\displaystyle x_{i}=\omega _{n}^{i-1}}$, kde ${\displaystyle \omega _{n}}$ je zvolená ${\displaystyle n}$-tá primitivní odmocnina z 1 a ${\displaystyle i\in \{1,\dots ,n\}}$.

Polynomická regrese

Ve statistice rovnice ${\displaystyle {\boldsymbol {Va}}={\boldsymbol {y}}}$ znamená, že Vandermondova matice ${\displaystyle {\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.