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\le 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). +more 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\le 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.

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í. +more Koeficienty a_0,\dots,a_{n-1} hledaného polynomu.

:p(x)=a_0+a_1x+a_xx^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_1x+\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{V C V}^{-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. +more 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

Literatura

Kategorie:Matice