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,\dots ,x_n)$ je:

$𝑽(x_1,\dots ,x_n)=\left(\begin{array}{ccccc}1& x_1& x_1^2& \dots & x_1^{n-1}\\ 1& x_2& x_2^2& \dots & x_2^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 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{array}\right)$

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 𝑽(x_1,\dots ,x_n)=\prod _{1\le i<j\le 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:

$\left(\begin{array}{ccccc}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)\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 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{array}\right)$

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 (𝑽(x_1,\dots ,x_n))=(x_n-x_1)(x_n-x_2)\cdots (x_n-x_{n-1})\left|\begin{array}{cccc}1& x_1& \dots & x_1^{n-2}\\ 1& x_2& \dots & x_2^{n-2}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_{n-1}& \dots & x_{n-1}^{n-2}\end{array}\right|=\det (𝑽(x_1,\dots ,x_{n-1}))\prod _{1\le i<n}(x_n-x_i)$

Použitím matematické indukce na Vandermondovu matici $𝑽(x_1,\dots ,x_{n-1})$ dává požadované vyjádření $\det (𝑽(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,\dots ,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:

$\left(\begin{array}{ccccc}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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_n& x_n^2& \dots & x_n^{n-1}\end{array}\right)\cdot \left(\begin{array}{c}{a}_0\\ a_1\\ a_2\\ ⋮\\ a_{n-1}\end{array}\right)=\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\\ ⋮\\ y_n\end{array}\right)$

Diagonalizace doprovodné matice

Je-li $𝑪$ doprovodná matice monického polynomu

$p(x)=\prod _{i=1}^n(x-x_i)=b_0+b_{1}x+\dots +b_{n-1}{x}^{n-1}+x^n$ ,

vyjádřeného v různých bodech $x_1,\dots ,x_n$, potom Vandermondova matice $𝑽=𝑽(x_1,\dots ,x_n)$diagonalizuje $𝑪$, neboť platí:

${𝑽𝑪𝑽}^{-1}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(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 $𝑽𝒂=𝒚$ znamená, že Vandermondova matice $𝑽$ je regresní maticí polynomické regrese .

Odkazy

Literatura

• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace elektronické monografie
• Šablona:Citace elektronické monografie

Šablona:Autoritní data Šablona:Portály