Kapitola 15

Několik aplikací

Diskrétní a rychlá Fourierova transformace

Diskrétní Fourierova transformace spočívá ve změně reprezentace polynomu s koeficienty v nějakém tělese T. Obvyklá reprezentace polynomu stupně n − 1

f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1}

sestává ze zadání koeficientů a_{0}, a_{1}, …, a_{n−1} ∈ T. Stejně tak ale můžeme zadat polynom f pomocí jeho hodnot v n různých bodech x_{0}, x_{1}, …, x_{n−1} ∈ T. Předepíšeme-li hodnoty f(x_{i}) = b_{i} ∈ T pro i = 0, …, n − 1, pak podle Tvrzení 4.15 existuje právě jeden polynom f stupně n − 1 s koeficienty v tělese T, který má v bodech x_{0}, …, x_{n−1} předepsané hodnoty. Jeho koeficienty a_{0}, …, a_{n−1} najdeme jako řešení soustavy lineárních rovnic

a_{0} + a_{1}x_{0} + ⋯ + a_{n−1}x_{0}^{n−1} = b_{0}
a_{0} + a_{1}x_{1} + ⋯ + a_{n−1}x_{1}^{n−1} = b_{1}
⋮
a_{0} + a_{1}x_{n−1} + ⋯ + a_{n−1}x_{n−1}^{n−1} = b_{n−1}.

Matice této soustavy je Vandermondova matice

V_{x_{0},x_{1},...,x_{n−1}} = ( \begin{matrix}1 & x_{0} & x_{0}^{2} & ⋯ & x_{0}^{n−1} \\ 1 & x_{1} & x_{1}^{2} & ⋯ & x_{1}^{n−1} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & x_{n−1} & x_{n−1}^{2} & ⋯ & x_{n−1}^{n−1} \end{matrix} ) .

Jednoznačnost polynomu f vyplývá z regularity Vandermondovy matice v případě, že body x_{0}, x_{1}, …, x_{n−1} jsou navzájem různé, kterou jsme dokázali v Úloze 9.3.

Předpokládejme nyní, že máme vynásobit dva polynomy f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1} a g(x) = c_{0} + c_{1}x + c_{2}x^{2} + ⋯ + c_{n−1}x^{n−1} stupně nejvýše n − 1. Jejich součin fg je polynom stupně nejvýše 2n − 2. Budeme jej znát, pokud budeme znát 2n − 1 koeficientů součinu fg nebo hodnoty součinu fg ve 2n − 1 různých bodech x_{0}, x_{1}, …, x_{2n−2}. Známe-li hodnoty obou polynomů f(x_{i}) = b_{i} a g(x_{i}) = c_{i} v těchto 2n − 2 bodech, můžeme snadno spočítat hodnoty součinu fg(x_{i}) = b_{i}c_{i} v těchto bodech. Potřebujeme k tomu pouze 2n−1 násobení, zatímco při výpočtu koeficientů d_{j} při klasické reprezentaci součinu

(fg)(x) = d_{0} + d_{1}x + ⋯ + d_{2n−2}x^{2n−2}

pomocí vztahů

d_{k} = ∑_{i=0}^{k}a_{i}c_{k−i}, k = 0, 1, …, 2n − 2,

potřebujeme celkem

2(1 + 2 + ⋯ + n) = n(n + 1)

násobení a řádově stejný počet sčítání. Násobení polynomů je tak mnohem rychlejší, pokud máme polynomy zadány pomocí jejich hodnot v dostatečně mnoha bodech.

Problém samozřejmě spočívá v ceně přechodu od zadání polynomu pomocí koeficientů k jeho zadání pomocí hodnot v předepsaných bodech a obráceně. Hodnotu polynomu f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1} v bodě x_{i} můžeme spočítat pomocí vyjádření

f(x_{i}) = a_{0} + a_{1}x_{i} + a_{2}x_{i}^{2} + ⋯ + a_{n−1}x_{i}^{n−1} =
= a_{0} + x(a_{1} + x(a_{2} + x(⋯ + x(a_{n−1}) ⋯))).

Tomuto vyjádření se říká Hornerovo schéma. Vyžaduje n − 1 násobení a stejný počet sčítání. Potřebujeme-li spočítat hodnotu polynomu f v n různých bodech, musíme tak použít celkem n(n−1) násobení a n(n−1) sčítání. To je řádově stejný počet násobení jako při přímém výpočtu koeficientů součinu a úplně stejný počet sčítání. Protože násobení je mnohem náročnější na čas než sčítání, můžeme říct, že výpočet hodnoty polynomu stupně n − 1 v n bodech je přibližně stejně časově náročný jako spočítat součin dvou polynomů stupně n − 1 pomocí přímého výpočtu koeficientů.

Všimněme si, že hodnoty polynomu f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1} v bodech x_{0}, …, x_{n−1} můžeme spočítat jako souřadnice součinu matic

( \begin{matrix}1 & x_{0} & x_{0}^{2} & ⋯ & x_{0}^{n−1} \\ 1 & x_{1} & x_{1}^{2} & ⋯ & x_{1}^{n−1} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & x_{n−1} & x_{n−1}^{2} & ⋯ & x_{n−1}^{n−1} \end{matrix} ) ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) ,

což můžeme rovněž zapsat ve tvaru

(f(x_{0}), f(x_{1}), …, f(x_{n−1}))^{T} = V_{x_{0},x_{1},...,x_{n−1}}(a_{0}, a_{1}, …, a_{n−1})^{T} .

Výpočtu hodnot polynomu f v bodech x_{0}, …, x_{n−1} budeme říkat evaluační transformace a budeme ji označovat T_{x_{0},x_{1},...,x_{n−1}}(f).

Pokud naopak chceme z hodnot polynomu f stupně n − 1 v n bodech najít koeficienty polynomu, musíme vyřešit soustavu n lineárních rovnic o n neznámých s regulární maticí, což při výpočtu pomocí Gaussovy eliminace vyžaduje dokonce řádově n^{3} násobení a řádově stejný počet sčítání. K tomu je ještě třeba přidat cenu výpočtu prvků Vandermondovy matice, která je maticí soustavy.

Abychom mohli využít “rychlejšího” násobení polynomů při jejich zadání pomocí hodnot v dostatečně mnoha bodech, potřebujeme mnohem ryhlejší algoritmy pro výpočet hodnoty polynomu v bodě než je výpočet pomocí Hornerova schématu. Stejně tak potřebujeme mnohem rychlejší algoritmus pro výpočet koeficientů polynomu, známe-li jeho hodnoty v dostatečně mnoha bodech, než je algoritmu založený na Gaussově eliminaci použité na Vandermondovu matici. Tyto algoritmy si nyní ukážeme.

Podstata urychlení Hornerova schématu spočívá ve vhodném výběru bodů x_{0}, x_{1}, …, x_{n−1} ∈ T, ve kterých hodnoty polynomu f počítáme. Pokud předpkládáme, že n = 2k je sudé číslo, pak můžeme polynom f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n−1}x^{n−1} napsat ve tvaru

f(x) = g(x^{2}) + xh(x^{2}),

kde

g(y) = a_{0} + a_{2}y + a_{4}y^{2} + ⋯ + a_{n−2}y^{k−1}

a

h(y) = a_{1} + a_{3}y + a_{5}y^{2} + ⋯ + a_{n−1}y^{k−1}.

Oba polynomy g, h mají poloviční stupeň oproti polynomu f, počítáme ale jejich hodnoty stále v n bodech x_{0}^{2}, …, x_{n−1}^{2} a protože polynomy jsou dva, žádné snížení počtu násobení zatím není vidět. Pokud ale navíc předpokládáme, že body x_{0}, …, x_{n−1} jsou zvolené symetricky, tj. že platí

x_{k+i} = −x_{i}

pro i = 0, 1, …, k −1, tak vidíme, že jsme nejenom snížili stupeň obou polynomů na polovinu, ale rovněž jsme snížili na polovinu počet bodů, ve kterých musíme počítat hodnoty obou polynomů. To už vede k podstatnému snížení počtu potřebných algebraických operací, jak ukazuje následující tvrzení.

Tvrzení 15.1 Předpokládáme, že f(x) = a_{0}+a_{1}x+a_{2}x^{2}+⋯+a_{n−1}x^{n−1} je polynom stupně n − 1 s koeficienty v tělese T, číslo n = 2k je sudé, a prvky x_{0}, x_{1}, …, x_{n−1} ∈ T splňují podmínku x_{k+i} = −x_{i} pro i = 0, 1, …, k − 1. Označíme-li C(n) počet operací, které jsou třeba k výpočtu hodnot nějakého polynomu v n bodech x_{0}, x_{1}, …, x_{n−1}, pak

C(1) = 0, a C(n) = 2 · C(\frac{n}{2}) + 4 · \frac{n}{2}.

Důkaz. Protože platí x_{k+i}^{2} = x_{i}^{2} pro i = 0, …, k − 1, potřebujeme spočítat hodnoty polynomů g, h pouze v k = n/2 bodech. To vyžaduje celkem 2 · C(n/2) operací. Kromě toho potřebujeme n/2 násobení pro výpočet čtverců x_{i}^{2} pro i = 0, 1, …, n/2 − 1. Dále n/2 násobení, n/2 sčítání a n/2 odčítání, abychom zkombinovali hodnoty g(x_{i}^{2}) a h(x_{i}^{2}) do hodnot f(x_{i}) pro i = 0, 1, …, n − 1. □

Vhodná volba evaluačních bodů je popsána v následující definici.

Definice 15.2 Prvek ω tělesa T se nazývá primitivní n-tá odmocnina z 1, pokud ω^{n} = 1(= ω^{0}) a mocniny

ω, ω^{2}, …, ω^{n−1}

jsou navzájem různé. Množina prvků {1, ω, ω^{2}, …, ω^{n−1}} se nazývá Fourierovy body. Evaluační transformace T_{1,ω,...,ω^{n−1}} ve Fourierových bodech 1 = ω^{0}, ω, ω^{2}, …, ω^{n−1} se nazývá diskrétní Fourierova transformace (DFT).

Příklad 15.3 1.Prvek

ω = cos \frac{2π}{n} + ı sin2πn

je primitivní n-tá odmocnina z 1 v tělese komplexních čísel C, jak vyplývá z Moivreovy věty. Fourierovy body

ω^{k} = cos \frac{k · 2π}{n} + ı sink · 2πn, k = 0, 1, …, n − 1

tvoří vrcholy pravidelného n-úhelníka vepsaného do jednotkové kružnice tak, aby bod (1, 0) byl jedním z vrcholů tohoto n-úhelníka.

2. V konečném tělese Z_{17} je prvek ω = 4 primitivní čtvrtou odmocninou z 1, neboť v tomto tělese platí 4^{4} = 256 = 1 mod17 a mocniny

4^{1} = 4, 4^{2} = 16, 4^{3} = 13

jsou navzájem různé. Vandermondova matice

V_{1,4,16,13} = ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & 4 & 16 & 13 \\ 1 & 16 & 1 & 16 \\ 1 & 13 & 16 & 4 \end{matrix} )

popisuje diskrétní Fourierovu transformaci T_{1,4,16,13}.

3. V tělese Z_{41} je číslo 14 primitivní osmou odmocninou z 1, odpovídající Fourierovy body jsou 1, 14, −9, −3, −1, −14, 9, 3.

Je-li ω ∈ T primitivní n-tá odmocnina z 1 pro sudé n = 2k, pak n Fourierových bodů 1, ω, ω^{2}, …, ω^{n−1} splňuje podmínku

(ω^{k+i} )^{2} = ω^{2k+2i} = ω^{n+2i} = ω^{n}ω^{2i} = 1 · (ω^{i})^{2} = (ω^{i})^{2}.

pro i = 0, 1, …, k − 1. Navíc je očividně ω^{2} primitivní (n/2)-tá odmocnina z 1 a v případě, že n = 4l splňuje k = n/2 sudých mocnin 1, ω^{2}, ω^{4}, ⋯, ω^{2k−1}, také stejnou podmínku symetrie

((ω^{2})^{l+i} ))^{2} = ω^{4l+4i} = ω^{4i} = ((ω^{2})^{i})^{2}.

K výpočtu hodnot polynomů g, h v n/2 bodech ω_{i}^{2}, i = 0, 1, …, k = n/2 můžeme použít stejný trik s výpočtem hodnot 4 polynomů ve l = n/4 bodech. A tak dále.

Pokud je tedy n = 2^{m} a ω ∈ T primitivní n-tá odmocnina z 1, můžeme rekurzivně spočítat hodnotu diskrétní Fourierovy transformace T_{1,ω,...,ω^{n−1}}. Tomuto výpočtu se říká rychlá Fourierova transformace (FFT). Následující výpočet ukazuje, jak moc FFT zrychluje výpočet hodnoty polynomu v n = 2^{m} bodech.

Tvrzení 15.4 Je-li n = 2^{m} a ω ∈ T primitivní n-tá odmocnina z 1, pak FFT vyžaduje

C(n) = 2 · n · log_{2} n

aritmetických operací.

Důkaz. Opakovaným použitím Tvrzení 15.1 dostaneme

C(n) = C(2^{m}) = 2 · C(2^{m−1}) + 4 · 2^{m−1} =
= 2(2 · C(2^{m−2}) + 4 · 2^{m−2}) + 4 · 2^{m−1} =
= 2^{2} · C(2^{m−2}) + 2 · 4 · 2^{m−1} =
= 2^{3} · C(2^{m−3}) + 3 · 4 · 2^{m−1} =
⋮
= 2^{m} · C(1) + m · 4 · 2^{m−1} =
= log_{2} n · 4 · \frac{n}{2} =
= 2 · n · log_{2} n.

□

Diskrétní Fourierova transformace a její spojitá verze nazývaná prostě Fourierova transformace jsou hojně používány v elektrotechnice, jedno využití spočívá v odstraňování šumu v signálech. V počítačové algebře je rychlá Fourierova transformace používána v systémech pro symbolickou manipulaci k násobení polynomů velkého stupně.

K tomu potřebujeme znát inverzní diskrétní Fourierovu transformaci, pomocí které ze znalosti hodnoty polynomu v n = 2^{m} bodech spočítáme jeho koeficienty. Tato inverzní diskrétní Fourierova transformace

T_{1,ω,···,ω^{n−1}}^{−1}

odpovídá výpočtu inverzní matice V_{1,ω,···,ω^{n−1}}^{−1} k matici V_{1,ω,···,ω^{n−1}}. Lze ukázat, že

V_{1,ω,···,ω^{n−1}}^{−1} = n^{−1} ( \begin{matrix}1 & 1 & 1 & ⋯ & 1 \\ 1 & ω^{−1} & ω^{−2} & ⋯ & ω^{−(n−1)} \\ 1 & ω^{−2} & ω^{−4} & ⋯ & ω^{−2(n−1)} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & ω^{−(n−1)} & ω^{−2(n−1)} & ⋯ & ω^{(n−1)^{2}} \end{matrix} ) .

Protože ω^{−1} ∈ T je rovněž primitivní n-tá odmocnina z 1, můžeme pro výpočet inverzní diskrétní Fourierovy transformace rovněž použít rychlou Fourierovu transformaci.

Rychlou Fourierovu transformaci poprvé uveřejnili pánové J.W. Cooley a J.W. Tuckey v roce 1965 a od té doby se stala jedním z nejpoužívanějších algoritmů.

Vyhledávač Google

Popularita vyhledávač Google spočívá také v tom, že uspořádá vyhledané stránky k danému dotazu podle “důležitosti”. Ukážeme si, jak je tato “důležitost” jednotlivých webových stránek definována a jak ji lze vypočítat.

Řekneme, že důležitost nějaké webové stránky je přímu úměrná součtu důležitostí stránek, které na ni odkazují. To na první pohled vypadá na definici kruhem. Zkusíme ji ale vyjádřit matematicky. Označíme x_{i} důležitost i-té webové stránky pro i = 1, 2, …, N, kde N je celkový počet webových stránek, které bereme v úvahu. Dále ještě potřebujeme nějak zachytit strukturu vzájemných odkazů mezi jednotlivými stránkami. Pokud j-tá stránka odkazuje na i-tou stránku, tak napíšeme, že

a_{ij} = 1.

V opačném případě, tj. pokud j-tá stránka neodkazuje na i-tou stránku, položíme

a_{ij} = 0.

Struktura vzájemných odkazů mezi jednotlivými webovými stránkami je tak popsána pomocí čtvercové matice A = (a_{ij}) řádu N. Tuto matice můžeme nazvat matice incidence webu.

Je-li K konstanta přímé úměrnosti použitá v neformální definici důležitosti i-té stránky, pak můžeme tuto definici formalizovat následovně:

x_{i} = K · ∑_{j=1}^{N}a_{ij}x_{j} pro i = 1, 2, …, N.

Přepsáním dostaneme

∑_{j=1}^{N}a_{ij}x_{j} = \frac{1}{K} · x_{i} pro i = 1, 2, …, N.

Označíme x = (x_{1}, x_{2}, …, x_{N})^{T} vektor důležitostí jednotlivých stránek, pak poslední rovnost zapíšeme ve tvaru

Ax = \frac{1}{K} x.

Vidíme tedy, že koeficient přímé úměrnosti K je převrácenou hodnotou nějakého vlastního čísla matice A (matice incidence webu) a vektor důležitostí x je vlastním vektorem příslušným tomuto vlastnímu číslu.

Matice incidence webu A má N (komplexních) vlastních čísel a ke každému vlastnímu číslu existuje nekonečně mnoho nenulových odpovídajících vlastních vektorů. Potřebujeme proto nějak vybrat vhodné vlastní číslo matice A, nejlépe tak, aby bylo kladné reálné, a k němu najít vhodný vlastní vektor, opět by bylo nejlepší, aby to byl vektor s kladnými reálnými souřadnicemi, nebo aspoň s nezápornými.

V tomto místě nastupuje Perronova-Frobeniova teorie nezáporných matic. Jako první si uvedeme definici spektrálního poloměru matice.

Definice 15.5 Je-li B čtvercová komplexní matice, pak číslo

ρ(A) = max{|λ| : λ ∈ σ(B)}

nazýváme spektrální poloměr matice B. Kružnici se středem v počátku a poloměrem ρ(B) nazýváme spektrální kružnice matice B.

Spektrální poloměr každé čtvercové komplexní matice je tedy nezáporné reálné číslo. Takovým maticím říkáme kladná (pozitivní) matice. Pokud jsou všechny prvky matice nezáporná reálná čísla, pak mluvíme o nezáporné matici. Matice, jejichž prvky jsou kladná reálná čísla, mají následující důležitou vlastnost.

Věta 15.6 Pro pozitivní čtvercovou matici B řádu n platí

1. ρ(B) ∈ σ(B),

2. pokud je x ≠ 0 vlastní vektor matice B příslušný vlastnímu číslu ρ(B), pak jsou buď všechny souřadnice vektoru x kladné a nebo jsou všechny souřadnice vektoru x záporné,

3. algebraická násobnost vlastního čísla ρ(B) je 1,

4. dimenze prostoru N (B−ρ(B)I_{n}) se rovná 1, tj. každý nenulový vlastní vektor příslušný vlastnímu číslu ρ(B) je reálným násobkem libovolného jiného nenulového vlastního vektoru příslušného k témuž vlastnímu číslu.

Z těchto vlastností vyplývá existence jednoznačně určeného kladného vlastního vektoru p = (p_{1}, …, p_{n})^{T} odpovídajícího spektrálnímu poloměru ρ(B), pro který platí p_{i} > 0 pro každé i = 1, …, n a dále

p_{1} + p_{2} + ⋯ + p_{n} = 1.

Tento jednoznačně určený kladný vlastní vektor nazýváme Perronův vektor kladné matice B a vlastní číslo ρ(B) nazýváme Perronův kořen matice B.

Perronův kořen a vektor nemůžeme přímo využít k výpočtu vektoru důležitosti webových stránek, protože matice incidence webu není kladná, je pouze nezáporná. Proto musíme použít následující zesílení předchozí věty, kterému se říká Perronova-Frobeniova věta.

Věta 15.7 Je-li B nezáporná čtvercová matice řádu n, pro kterou platí, že B^{M} je kladná matice pro dostatečně velký exponent M, pak platí

1. ρ(B) ∈ σ(B),

2. pokud je x ≠ 0 vlastní vektor matice B příslušný vlastnímu číslu ρ(B), pak jsou buď všechny souřadnice vektoru x kladné a nebo jsou všechny souřadnice vektoru x záporné,

3. algebraická násobnost vlastního čísla ρ(B) je 1,

4. dimenze prostoru N (B−ρ(B)I_{n}) se rovná 1, tj. každý nenulový vlastní vektor příslušný vlastnímu číslu ρ(B) je reálným násobkem libovolného jiného nenulového vlastního vektoru příslušného k témuž vlastnímu číslu.

Také v případě nezáporných matic take existuje jednoznačně určený vlastní (Perronův) vektor p = (p_{1}, …, p_{n})^{T} odpovídajícího spektrálnímu poloměru ρ(B), pro který platí p_{i} > 0 pro každé i = 1, …, n a dále

p_{1} + p_{2} + ⋯ + p_{n} = 1.

Matice incidence webu A je sice nezáporná, s velkou pravděpodobností ale nesplňuje druhý z předpokladů Perronovy-Frobeniovy věty, totiž že A^{M} je kladná matice pro dostatečně velký exponent M. Toto už je ale drobný problém.

Tato idea porovnávání významu lidí nebo věcí na základě vlivu, který na sebe vzájemně mají, má mnoho nejrůznějších aplikací ve statistice i v dalších oborech. Anglicky se jí říká Kendall-Wei theory of ranking a pochází z padesátých let minulého století.

Soustavy obyčejných lineárních diferenciálních rovnic

Soustavou obzčejných lineárních diferenciálních rovnic s konstatními koeficienty rozumíme soustavu rovnic následujícího tvaru.

u′_{1} = a_{11}u_{1} + a_{12}u_{2} + ⋯ + a_{1n}u_{n},

u′_{2} = a_{21}u_{1} + a_{22}u_{2} + ⋯ + a_{2n}u_{n},
⋮
u′_{n} = a_{n1}u_{1} + a_{n2}u_{2} + ⋯ + a_{nn}u_{n},

spolu s počátečními podmínkami

u_{1}(0) = c_{1},
u_{2}(0) = c_{2},
⋮
u_{n}(0) = c_{n}.

Předpokládáme, že matice A = (a_{ij}) je reálná matice, funkce u_{i} = u_{i}(t) jsou reálné funkce reálné proměnné a c_{i} jsou reálná čísla pro i = 1, …, n. Označíme-li c = (c_{1}, …, c_{n})^{T} a u = (u_{1}(t), …, u_{n}(t)), můžeme soustavu zapsat v maticovém tvaru

u′ = Au, a u(0) = c.

V úvodu předchozí kapitoly jsme si řekli, že jedna obyčejná diferenciální rovnice u′(t) = αu(t) s počáteční podmínkou u(0) = c má jednoznačně určené řešení u(t) = c·e^{αt}. Můžeme se proto pokusit najít analogický vzorec pro řešení soustavy o n neznámých funkcích.

Pokud je matice A diagonalizovatelná a

A = λ_{1}E_{1} + ⋯ + λ_{k}E_{k}

je její spektrální rozklad podle Věty 10.15, můžeme se pokusit definovat matici funkcí reálné proměnné t jako

e^{At} = e^{λ_{1}t}E_{1} + ⋯ + e^{λ_{k}t}E_{k}.

Matici funkcí reálné proměnné můžeme derivovat tak, že derivujeme každou funkci zvlášť. Takto definovaná matice reálných funkcí má následující vlastnosti.

Tvrzení 15.8 Je-li A diagonalizovatelná matice řádu n a

A = λ_{1}E_{1} + ⋯ + λ_{k}E_{k}

její spektrální rozklad, pak matice funkcí

e^{At} = e^{λ_{1}t}E_{1} + ⋯ + e^{λ_{k}t}E_{k}.

má následující vlastnosti

\frac{d e^{At}}{d t} = A · e^{At},
A · e^{At} = e^{At} · A,
e^{−At}e^{At} = e^{At}e^{−At} = I_{n},
I_{n} = e^{0}.

Dále vektor funkcí u = e^{At}c je jediným řešením soustavy obyčejných lineárních rovnic u′ = Au s počátečními podmínkami u_{i}(0) = c_{i} pro i = 1, 2, …, n.

Důkaz. Abychom dokázali první rovnost, dosadíme za e^{At} podle definice. Dostaneme

\frac{d e^{At}}{d t} = ∑_{i=1}^{k}λ_{i}e^{λ_{i}t}E_{i} = (∑_{i=1}^{k}λ_{i}E_{i})(∑_{i=1}^{k}e^{λ_{i}t}E_{i}) = A · e^{At}.

V důkazu druhé rovnosti postupujeme podobně.

A · e^{At} = (∑_{i=1}^{k}λ_{i}E_{i})(∑_{j=1}^{k}e^{λ_{j}t}E_{j}) = ∑_{i=1}^{k}λ_{i}e^{λ_{i}t}E_{i}E_{i} =

= (∑_{j=1}^{k}e^{λ_{j}t}E_{j})(∑_{i=1}^{k}λ_{i}E_{i}) = e^{At} · A.

Také třetí rovnost dokážeme analogicky.

e^{−At}e^{At} = (∑_{i=1}^{k}λ_{i}e^{−λ_{i}t}E_{i})(∑_{j=1}^{k}λ_{j}e^{λ_{j}t}E_{j}) = ∑_{i=1}^{k}e^{−λ_{i}t}e^{λ_{i}t}E_{i}^{2} =

= ∑_{i=1}^{k}E_{i} = I_{n} = (∑_{j=1}^{k}λ_{j}e^{λ_{j}t}E_{j})(∑_{i=1}^{k}λ_{i}e^{−λ_{i}t}E_{i}) = e^{At}e^{−At}.

Poslední, čtvrtá rovnost vyplývá ihned přímo z definice e^{At} a vlastností spektrálních projektorů E_{i}.

e^{0} = ∑_{i=1}^{k}e^{0}E_{i} = ∑_{i=1}^{k}E_{i} = I_{n}.

Z první rovnosti ihned dostaneme, že vektor funkcí

u = c · e^{At}

je řešením soustavy u′ = Au, u(0) = c.

Je-li nějaký další vektor funkcí v(t) řešením téže soustavy, tj. platí-li v′ = Av a v(0) = c, spočítáme napřed

e^{−Av} = ∑_{i=1}^{k}e^{−λ_{i}t}E_{i}v.

Odtud dostaneme

\frac{d (e^{−At}v)}{d t} = − ∑_{i=1}^{k}λ_{i}e^{−λ_{i}t}E_{i}v + ∑_{i=1}^{k}e^{−λ_{i}t}E_{i}v′ = −A · e^{−At}v + e^{−At}v′ =
= −e^{−At}Av + e^{−At}v′ = e^{−At}(−Av + v′) = 0.

Odtud plyne, že všechny funkce v e^{−At}v jsou konstantní. V bodě t = 0 mají hodnoty

e^{0}v(0) = I_{n}c = c,

a tedy e^{−At}v = c. Vynásobíme poslední rovnost zleva maticí e^{At} a dostaneme

v = e^{At}e^{−At}v = e^{At}c = u.

Tím je dokázána jednoznačnost řešení u = e^{At}c. □

Mnoho fyzikálních nebo biologických procesů lze modelovat pomocí soustavy diferenciálních rovnic u′ = Au, u(0) = c. Ukážeme si jeden příklad.

Úloha 15.1 V čase t = 0 vstříkneme do buňky číslo 1 jednotkové množství nějaké látky (léku). Látka se šíří z buňky číslo 1 do buňky číslo 2 buněčnou membránou. Předpokládáme, že rychlost šíření látky z buňky 1 do buňky 2 je přímo úměrná její koncentraci v buňce 1. Koeficient přímé úměrnosti označíme α. Stejně tak předpokládáme, že rychlost šíření látky z buňky 2 do buňky 1 je přímo úmerná koncentraci této látky v buňce 2, koeficient přímé úměrnosti označíme β. Z fyzikálního významu koeficientů α, β vyplývá předpoklad α, β > 0. Určete koncentrace látky v obou buňkách v libovolném čase t > 0.

Řešení. Označíme koncentraci látky v první buňce v čase t jako u_{1}(t). Podobně u_{2}(t) označuje koncentraci látky v druhé buňce. Z uvedených předpokladů vyplývají následující rovnice pro funkce u_{1}(t) a u_{2}(t)

u′_{1}(t) = βu_{2}(t) − αu_{1}(t),
u′_{2}(t) = αu_{1}(t) − βu_{2}(t),

a počáteční podmínky u_{1}(0) = 1, u_{2}(0) = 0.

V maticovém tvaru soustavu zapíšeme jako u′ = Au a u(0) = c, kde

A = ( \begin{matrix}−α & β \\ α & −β \end{matrix} ) , u = ( \begin{matrix}u_{1} \\ u_{2} \end{matrix} ) , a c = ( \begin{matrix}1 \\ 0 \end{matrix} ) .

Podle předchozího Tvrzení 15.8 můžeme zapsat řešení ve tvaru u = e^{At}c. Matice A má charakteristickou rovnici tvaru

(−α − λ)(−β − λ) − αβ = λ^{2} + (α + β)λ = 0.

Vlastní hodnoty matice A jsou proto λ_{1} = 0 a λ_{2} = −(α + β). Protože jsou vlastní hodnoty různé, je matice A diagonalizovatelná podle Tvrzení 10.13.

Vlastní vektory příslušné vlastnímu číslu λ_{1} dostaneme jako řešení homogenní soustavy lineárních rovnic s maticí

A − 0I_{2} = A = ( \begin{matrix}−α & β \\ α & −β \end{matrix} ) ,

která má řešení ve tvaru násobků vektoru (β, α)^{T}.

Podobně najdeme vlastní vektory příslušné vlastnímu číslu λ_{2} = −(α+β) jako řešení homogenní soustavy lineárních rovnic s maticcí

A + (α + β)I_{2} = ( \begin{matrix}β & β \\ α & α \end{matrix} ) ,

která má řešení ve tvaru násobků vektoru (1, −1)^{T}.

Podle důkazu Spektrální věty pro diagonalizovatelné matice 10.15 můžeme k výpočtu spektrálních projektorů E_{1} a E_{2} použít regulární matici

P = ( \begin{matrix}β & 1 \\ α & −1 \end{matrix} ) .

Spočítáme inverzní matici

P^{−1} = ( \frac{α}{α+β} −\frac{β}{α+β}^{\frac{1}{α+β} \frac{1}{α+β}} )

a matice

E_{1} = P ( \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ) P^{−1} = ( \begin{matrix}\frac{β}{α+β} & \frac{β}{α+β} \\ \frac{α}{α+β} & \frac{α}{α+β} \end{matrix} ) = \frac{1}{α + β} ( \begin{matrix}β & β \\ α & α \end{matrix} ) .

Podobně

E_{2} = P ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) P^{−1} = \frac{1}{α + β} ( \begin{matrix}α & −β \\ −α & β \end{matrix} ) .

Proto

e^{At} = \frac{1}{α + β} [e^{0t} ( \begin{matrix}β & β \\ α & α \end{matrix} ) + e^{−(α+β)t} ( \begin{matrix}α & −β \\ −α & β \end{matrix} )]

a tedy

u = ( \begin{matrix}u_{1}(t) \\ u_{2}(t) \end{matrix} ) = \frac{1}{α + β} [( \begin{matrix}β & β \\ α & α \end{matrix} ) + e^{−(α+β)t} ( \begin{matrix}α & −β \\ −α & β \end{matrix} )] ( \begin{matrix}1 \\ 0 \end{matrix} ) =

= ( \begin{matrix}\frac{β}{α+β} + \frac{α}{α+β} e^{−(α+β)t} \\ \frac{α}{α+β} − \frac{α}{α+β} e^{−(α+β)t} \end{matrix} ) .

Limita pro t → ∞ se pak rovná

lim_{t→∞} u_{1}(t) = \frac{β}{α + β} , lim_{t→∞} u_{2}(t) = \frac{α}{α + β} .

□

Filtry odstraňující šum

V závěru předchozí kapitoly jsme si ukázali rozklad matice A = UDV^{T}, kde U a V jsou ortogonální matice, a

D = ( \begin{matrix}D_{r×r} & 0 \\ 0 & 0 \end{matrix} )

pro regulární matici D_{r×r} řádu r. Tento rozklad je užitečný při odstraňování šumu v nějakých datech. Předpokládáme, že naše data jsou v podobě matice A tvaru m × n. Napíšeme si její rozklad

A = U ( \begin{matrix}D_{r×r} & 0 \\ 0 & 0 \end{matrix} ) V^{T} = ∑_{i=1}^{r}σ_{i}u_{i}v_{i}^{T} ,

kde u_{i} je i-tý sloupec ortogonální matice U řádu m a v_{j} je j-tý sloupec orotogonální matice V řádu n a σ_{1} ≥ σ_{2} ≥ ⋯ ≥ σ_{r} > 0 jsou singulární hodnoty matice A.

Označíme si u_{i}v_{i}^{T} = Z_{i} pro i = 1, …, r. Podle Příkladu 8.8 předpis

< B|C >= tr(B^{T} C)

definuje skalární součin na prostoru R^{m×n} reálných matic tvaru m × n.

Spočítáme, že

< Z_{i}|Z_{i} >= 1

pro i = 1, 2, …, r a

< Z_{i}|Z_{j} >= 0,

pokud i ≠ j. To znamená, že posloupnost matic Z_{1}, Z_{2}, …, Z_{r} je ortonormální a vyjádření

A = ∑_{i=1}^{r}σ_{i}Z_{i}

je Fourierův rozklad matice A podle Definice 8.15.

Čím větší je singulární hodnota σ_{i}, tím větší část našich dat je ve “směru” matice Z_{i}. Pokud předpokládáme, že šum je v datech obsažen “náhodně”, nezávisle na směru, můžeme předpokládat, že v každém směru je přibližně stejné množství šumu. Zvolíme nějaké k. Potom ve výrazu

σ_{k+1} Z_{k+1} + ⋯ + σ_{r}Z_{r}

je obsažena poměrně malá část dat a větší část šumu, zatímco ve výrazu

σ_{1}Z_{1} + ⋯ σ_{k}Z_{k}

je obsažena mnohem větší část dat než šumu. To vysvětluje, že pokud místo matice

A = ∑_{i=1}^{r}σ_{i}Z_{i}

pracujeme dále s maticí

A′ = ∑_{i=1}^{k}σ_{i}Z_{i}

bude mít nová matice A′ větší poměr data/šum než původní matice A.

Volba vhodného k závisí na konkrétní aplikaci. Dobrým počátečním krokem je zvolit takové k, aby rozdíl σ_{k} − σ_{k+1} byl co největší.

Tato myšlenka odfiltrování šumu z dat se používá například v některých vyhledávačích, ve filtrech odstraňujících spamy, atd.

Vyhledávače

Představme si, že máme posloupnost slov (termínů) T_{1}, …, T_{m}, jejichž výskyt v dokumentech D_{1}, …, D_{n} nás zajímá. Každý dokument D_{j} prohlédneme a najdeme frekvenci (počet výskytů) f_{ij} každého termínu T_{i} v dokumentu D_{j}. Získáme tak frekvenční matici F = (f_{ij}) tvaru m × n. Každému dokumentu D_{j} tak rovněž přiřadíme vektor f_{j} = F_{∗j}, sloupcový vektor matice F. Většina prvků matice F se bude rovnat 0.

Nzní položíme dotaz q = (q_{1}, …, q_{n})^{T}, kde q_{i} = 1, pokud nás zajímá termín T_{i} a q_{i} = 0, pokud nás termín T_{i} nezajímá. Jako míru toho, jak se vektor (dotaz) q liší od frekvenčního vektoru f_{j} dokumentu T_{j} můžeme zvolit standardní skalární součin

cosα_{j} = \frac{q^{T} f_{j}}{∥q∥ · ∥d_{j}∥} = \frac{q^{T} Fe_{j}}{∥q∥ · ∥Fe_{j}∥} ,

kde e_{j} je j-tý vektor standardní báze prostoru R^{n×1}. Pokud je | cosα_{j}| ≥ τ pro nějakou zvolenou hranici τ, tak dokument D_{j} považujeme za relevantní a zařadíme jej do odpovědi na dotaz q. Volba vhodného τ je záležitostí zkušenosti a umění.

Pokud jsou sloupce matice F předem normalizovány, tj. mají délku 1, pak vektor

q^{T} F = (cosα_{1}, cosα_{2}, …, cosα_{n})

umožňuje posoudit relevanci každého dokumentu D_{j}.

Musíme ale předpokládat, že frekvenční matice F je zatížena šumem, který pochází z překlepů v dokumentech, nejednoznačnosti v používání jazyka, atd. Souřadnice vektoru q^{T} F proto nejsou příliš spolehlivou mírou relevance dokumentů pro dotaz q. Použijeme proto předchozí metodu odstraňování šuku pomocí SDV-rozkladu. Napíšeme si matici F = UDV^{T} ve tvaru

F = UDV^{T} = ∑_{i=1}^{n}σ_{i}u_{i}v_{i}^{T} ,

a místo matice F budeme dále pracovat pouze s maticí

F_{k} = ∑_{i=1}^{k}σ_{i}u_{i}v_{i}^{T} .

Místo čísel cosα_{j} tak dostaneme čísla

cosβ_{j} = \frac{q^{T} F_{k}e_{j}}{∥q∥ · ∥F_{k}e_{j}∥} .