Jacobiho matice (třídiagonální)

Jacobiho matice je reálná symetrická třídiagonální matice s kladnými prvky na horní a dolní sekundární diagonále.

Definice

Reálnou čtvercovou matici řádu ${\displaystyle k}$ ve tvaru

${\displaystyle {\boldsymbol {J}}={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&\\\beta _{2}&\alpha _{2}&\beta _{3}&&\\&\beta _{3}&\ddots &\ddots &\\&&\ddots &\ddots &\beta _{k}\\&&&\beta _{k}&\alpha _{k}\end{pmatrix}},\qquad \beta _{i}>0,\quad i=2,\ldots ,k,}$

nazýváme Jacobiho maticí. Speciálním (triviálním) případem je Jacobiho matice ${\displaystyle {\boldsymbol {J}}=(\alpha _{1})}$, ${\displaystyle k=1}$. Jacobiho matice mají řadu specifických vlastností.

Spektrální vlastnosti

Vlastní čísla

Vlastní čísla Jacobiho matic mají násobnost jedna. Stačí si uvědomit, že pro libovolné číslo ${\displaystyle \lambda }$ jsou druhý až poslední řádek v matici ${\displaystyle {\boldsymbol {J}}_{k}-\lambda \mathbf {I} }$ lineárně nezávislé:

${\displaystyle {\begin{pmatrix}\beta _{2}&\alpha _{2}-\lambda &\beta _{3}&&\\&\beta _{3}&\ddots &\ddots &\\&&\ddots &\ddots &\beta _{k}\\&&&\beta _{k}&\alpha _{k}-\lambda \end{pmatrix}}}$

Odtud plyne, že ${\displaystyle \operatorname {rank} ({\boldsymbol {J}}-\lambda \mathbf {I} )\geq k-1}$. Protože matice je symetrická, odpovídá její hodnost počtu nenulových vlastních čísel (včetně násobností). Každé vlastní číslo ${\displaystyle \lambda }$ má tudíž násobnost jedna.

Protože matice je symetrická, vlastní čísla jsou navíc reálná a můžeme je seřadit

${\displaystyle \lambda _{1}({\boldsymbol {J}})<\lambda _{2}({\boldsymbol {J}})<\cdots <\lambda _{k}({\boldsymbol {J}}).}$

Označíme-li ${\displaystyle {\boldsymbol {J}}'}$ vedoucí hlavní podmatici matice ${\displaystyle {\boldsymbol {J}}}$ řádu ${\displaystyle k-1}$, neboli

${\displaystyle {\boldsymbol {J}}=\left({\begin{array}{c|c}{\boldsymbol {J}}'&\left.{\begin{array}{c}0\\\vdots \\0\\\beta _{k}\end{array}}\right.\\\hline \left.{\begin{array}{cccc}0&\cdots &0&\beta _{k}\end{array}}\right.&\alpha _{k}\end{array}}\right)}$,

pak ${\displaystyle {\boldsymbol {J}}'}$ je také Jacobiho matice. Vlastní čísla těchto dvou „po sobě jdoucích“ Jacobiho matic ${\displaystyle {\boldsymbol {J}}}$ a ${\displaystyle {\boldsymbol {J}}'}$ se striktně prokládají

${\displaystyle \lambda _{1}({\boldsymbol {J}})<\lambda _{1}({\boldsymbol {J}}')<\lambda _{2}({\boldsymbol {J}})<\lambda _{2}({\boldsymbol {J}}')<\cdots <\lambda _{k-1}({\boldsymbol {J}}')<\lambda _{k}({\boldsymbol {J}})}$.

Charakteristické polynomy dvou po sobě jdoucích Jacobiho matic nemají žádný společný kořen. To lze dokázat sporem; rozvojem determinantu ${\displaystyle \det({\boldsymbol {J}}_{k}-\lambda \mathbf {I} )}$ podle posledního řádku a indukcí podle rozměru matice.

Mimo jiné také platí, že Jacobiho matice ${\displaystyle {\boldsymbol {J}}}$ a ${\displaystyle {\boldsymbol {J}}'}$nemohou být obě singulární.

Vlastní vektory

Jsou-li ${\displaystyle \lambda ,{\boldsymbol {v}}}$ vlastní číslo a jemu příslušný vlastní vektor Jacobiho matice ${\displaystyle {\boldsymbol {J}}}$, kde

${\displaystyle {\boldsymbol {v}}=(v_{1},v_{2},v_{3},\ldots ,v_{k})^{\mathrm {T} },\qquad \|{\boldsymbol {v}}\|\neq 0,}$

pak

• první prvek vlastního vektoru je nenulový, ${\displaystyle v_{1}\neq 0}$,
• poslední prvek vlastního vektoru je nenulový, ${\displaystyle v_{k}\neq 0}$,
• libovolný dvouprvkový podvektor ${\displaystyle (v_{\ell },v_{\ell +1})}$, ${\displaystyle \ell =1,\ldots ,k-1}$, je nenulový.

Všechna tři tvrzení lze dokázat sporem, prostým porovnáním prvků vektorů na obou stranách rovnosti

${\displaystyle {\begin{pmatrix}\alpha _{1}&\beta _{2}&&&\\\beta _{2}&\alpha _{2}&\beta _{3}&&\\&\beta _{3}&\ddots &\ddots &\\&&\ddots &\ddots &\beta _{k}\\&&&\beta _{k}&\alpha _{k}\end{pmatrix}}{\begin{pmatrix}v_{1}\\v_{2}\\v_{3}\\\vdots \\v_{k}\end{pmatrix}}={\begin{pmatrix}v_{1}\\v_{2}\\v_{3}\\\vdots \\v_{k}\end{pmatrix}}\lambda }$.

Z předpokladu ${\displaystyle v_{1}=0}$ a porovnání prvních prvků

${\displaystyle \alpha _{1}v_{1}+\beta _{2}v_{2}=v_{1}\lambda }$

plyne ${\displaystyle v_{2}=0}$ (neboť ${\displaystyle \beta _{2}>0}$). Indukcí pak vyplývá ${\displaystyle v_{1}=v_{2}=\ldots =v_{k}=0}$, což je ve sporu s ${\displaystyle \|{\boldsymbol {v}}\|\neq 0}$.

Užití k výpočtu vlastních čísel symetrických a hermitovských matic

Pro každou reálnou symetrickou matici ${\displaystyle {\boldsymbol {A}}\in \mathbb {R} ^{k\times k}}$, ${\displaystyle {\boldsymbol {A}}={\boldsymbol {A}}^{\mathrm {T} }}$, existuje ortogonální matice ${\displaystyle {\boldsymbol {G}}\in \mathbb {R} ^{k\times k}}$, ${\displaystyle {\boldsymbol {G}}^{-1}={\boldsymbol {G}}^{\mathrm {T} }}$, taková, že

${\displaystyle {\boldsymbol {GAG}}^{\mathrm {T} }={\boldsymbol {J}}_{\oplus },\qquad {\text{kde}}\qquad {\boldsymbol {J}}_{\oplus }=\left({\begin{array}{cccc}{\boldsymbol {J}}_{1}\\&{\boldsymbol {J}}_{2}\\&&\ddots \\&&&{\boldsymbol {J}}_{s}\end{array}}\right),\quad {\boldsymbol {J}}_{\ell }\in \mathbb {R} ^{k_{\ell }\times k_{\ell }},\quad \sum _{\ell =1}^{s}k_{\ell }=k}$

a kde ${\displaystyle {\boldsymbol {J}}_{\ell }}$ jsou Jacobiho matice. Matici ${\displaystyle {\boldsymbol {G}}}$ lze přitom zkonstruovat v konečném čase, tj. pomocí konečného počtu elementárních aritmetických operací (sčítání, odečítání, násobení, dělení a výpočtu druhé odmocniny).

Obdobně pro každou hermitovskou matici ${\displaystyle {\boldsymbol {A}}\in \mathbb {C} ^{k\times k}}$, ${\displaystyle {\boldsymbol {A}}={\boldsymbol {A}}^{\mathrm {H} }}$, existuje unitární matice ${\displaystyle {\boldsymbol {G}}\in \mathbb {C} ^{k\times k}}$, ${\displaystyle {\boldsymbol {G}}^{-1}={\boldsymbol {G}}^{\mathrm {H} }}$ taková, že

${\displaystyle {\boldsymbol {GAG}}^{\mathrm {H} }={\boldsymbol {J}}_{\oplus }}$

je stejná matice jako v předchozím případě. Speciálně je matice ${\displaystyle {\boldsymbol {J}}_{\oplus }}$ reálná symetrická i v případě komplexní hermitovské matice ${\displaystyle {\boldsymbol {A}}}$.

Vlastnosti matice ${\displaystyle {\boldsymbol {J}}_{\oplus }}$

Matice ${\displaystyle {\boldsymbol {J}}_{\oplus }}$ je stále třídiagonální, obecně však už není Jacobiho maticí, protože prvky bezprostředně nad diagonálou nebo bezprostředně pod ní mohou být nulové. Transformační matici ${\displaystyle {\boldsymbol {G}}}$ lze vždy zvolit tak, že

${\displaystyle k_{1}\geq k_{2}\geq \cdots \geq k_{s}\qquad {\text{a}}\qquad \operatorname {sp} {\boldsymbol {J}}_{1}\supseteq \operatorname {sp} {\boldsymbol {J}}_{2}\supseteq \cdots \supseteq \operatorname {sp} {\boldsymbol {J}}_{s}}$,

kde ${\displaystyle \operatorname {sp} {\boldsymbol {M}}}$ značí spektrum matice ${\displaystyle {\boldsymbol {M}}}$. Jacobiho matice ${\displaystyle {\boldsymbol {J}}_{1}}$ obsahuje všechna vlastní čísla původní matice ${\displaystyle {\boldsymbol {A}}}$, přičemž každé jen jednou, jak plyne z vlastností Jacobiho matic. Číslo ${\displaystyle s}$ je dimenzí největšího vlastního podprostoru (eigenspace), tj. ${\displaystyle s}$ je největší násobností některého z vlastních čísel matice ${\displaystyle {\boldsymbol {A}}}$.

Konstrukce matice ${\displaystyle {\boldsymbol {G}}}$ v konečném čase

Význam Jacobiho matic spočívá v možnosti spočítat ortogonální, resp. unitární matice ${\displaystyle {\boldsymbol {G}}}$ v konečném čase. Přestože je diagonalizovatelnost matice ${\displaystyle {\boldsymbol {A}}}$ vždy zaručena, protože symetrické, resp. hermitovské matice jsou normální a proto ortogonálně, resp. unitárně diagonalizovatelné, tato diagonalizace však obecně není proveditelná v konečném čase. Např. už jen z toho důvodu, že vlastní čísla coby kořeny charakteristického polynomu nemusí být možné vyjádřit v radikálech pro polynomy stupně alespoň 5 (viz též základní věta algebry).

Význam třídiagonalizace lze spatřovat v provedení dílčího výpočtu při hledání vlastních čísel symetrické, resp. hermitovské matice

${\displaystyle {\boldsymbol {A}}\;\longmapsto \;{\boldsymbol {J}}_{\oplus }\;\longmapsto \;{\boldsymbol {D}}=\mathrm {diag} (\lambda _{1},\ldots ,\lambda _{k}),}$

který lze provést v přesné aritmetice v konečném čase. Následná diagonalizace třídiagonální matice ${\displaystyle {\boldsymbol {J}}_{\oplus }}$však obecně vyžaduje iterační algoritmus s limitní konvergencí, typicky některou z variant QR algoritmu.

Matice ${\displaystyle {\boldsymbol {G}}}$ a ${\displaystyle {\boldsymbol {J}}_{\oplus }}$ lze zkonstruovat např. pomocí dobře známého Lanczosova algoritmu (Lanczosovy tridiagonalizace).

Souvislosti

Jacobiho matice hrají klíčovou v řadě teoretických i praktických aplikací^{[1][2][3][4][5]}

• řetězově zlomky,
• ortogonální polynomy,
• Gaussova kvadratura,
• Lanczosův algoritmus,
• (částečný) problém vlastních čísel (symetrických matic),
• metoda sdružených gradientů.

Reference

Literatura

• DUINTJER TEBBENS, Erik Jurjen; HNĚTYNKOVÁ, Iveta; PLEŠINGER, Martin; STRAKOŠ, Zdeněk; TICHÝ, Petr. Analýza metod pro maticové výpočty: Základní metody. 1. vyd. Praha: Matfyzpress, 2012. xvi+308 s. ISBN 978-80-7378-201-6.