Symetrická zobrazení Rozklady matic a pseudoinverze Matematika I – 10b Něco málo maticového počtu Jan Slovák Masarykova univerzita Fakulta informatiky 19. 11. 2012 Symetrická zobrazení Rozklady matic a pseudoinverze Obsah přednášky 1 Symetrická zobrazení 2 Rozklady matic a pseudoinverze Symetrická zobrazení Rozklady matic a pseudoinverze Uvažujme opět reálný vektorový prostor V se skalárním součinem. Zobrazení f : V → V se nazývá symetrické, jestliže pro všechny vektory u, v ∈ V platí f (u), v = u, f (v) . V libovolné ortonormální bázi můžeme předchozí vztah v souřadnicích vyjádřit takto: (A · x)T · y = xT · (A · y) = xT · (AT y). Volbou souřadnic bázových vektorů (tj. jedna jednička a zbytek nuly) se dostaneme ke vztahům aij = aji pro jednotlivé komponenty matice A, tzn. ke vztahu A = AT . Theorem Zobrazení f : V → V na vektorovém prostoru se skalárním součinem je symetrické právě tehdy, když v některé (a pak už všech) ortonormální bázi má symetrickou matici. Symetrická zobrazení Rozklady matic a pseudoinverze Adjungovaná zobrazení Jestliže zvolíme pevně jeden vektor v ∈ V , dosazování vektorů za druhý argument nám dává zobrazení V → V ∗ = Hom(V , R) V v → (w → v, w ∈ R). Nedegenerovanosti skalárního součinu zaručuje, že je to bijekce. Je vidět, že vektory ortonormální báze jsou zobrazeny na formy tvořící bázi duální. Lieární f : V → W zadává tzv. duální zobrazení f ∗ : W ∗ → V ∗ mezi formami, definované pro všechny w∗ ∈ W ∗, v ∈ V f ∗ (w∗ )(v) = w∗ (f (v)). V libovolných bazích na V a W a jejich duálních bazích na V ∗ a W ∗ pak tentýž definiční vztah má tvar (píšeme A∗ pro matici zobrazení f ∗, xT souřadnice formy w∗, y souřadnice v) (A∗ xT ) · y = xT · (A · y) a proto duální zobrazení má v duálních bazích matici AT . Symetrická zobrazení Rozklady matic a pseudoinverze V případě vektorových prostorů se skalárním součinem, převádí výše uvedené bijekce duální zobrazení f ∗ na tobrazení f ∗ : W → V zadané formulí f (u), v = u, f ∗ (v) a tomuto zobrazení se říká adjungované zobrazení k f . Předchozí výpočet v souřadnicích pro symetrická zobrazení nám ve skutečnosti sdělil, že je-li A matice zobrazení f v ortonormální bázi, pak matice adjungovaného zobrazení f ∗ je matice transponovaná AT . Můžeme proto také přeformulovat definici takto: Symetrické je takové zobrazení f : V → V , které je rovno svému adjungovanému zobrazení f ∗. Často se takovým zobrazením také proto říká samoadjungovaná. Symetrická zobrazení Rozklady matic a pseudoinverze Theorem (Spektrální rozklad symetrického zobrazení) Pro každé symetrické zobrazení f : V → V na vektorovém prostoru se skalárním součinem existuje ortonormální báze z vlastních vektorů. Jsou-li λ1, . . . , λk všechna různá vlastní čísla f a P1, . . . , Pk příslušné kolmé a navzájem kolmé projektory na vlastní podprostory, pak f = λ1P1 + · · · + λkPk. Zde o projektoru P : V → V říkáme, že je kolmý, je-li Im P ⊥ Ker P. Dva kolmé projektory P, Q jsou vzájemně kolmé, je-li Im P ⊥ ImQ. Věta opět vyplývá ze zkoumání invariance ortogonálních doplňků a vlastních čísel. Symetrická zobrazení Rozklady matic a pseudoinverze Jestliže pro libovolný podprostor W ⊂ V a symetrické zobrazení f : V → V platí f (W ) ⊂ W , pak také platí pro všechny v ∈ W ⊥, w ∈ W f (v), w = v, f (w) = 0. To ale znamená, že také f (W ⊥) ⊂ W ⊥. Představme si dále, že A je matice symetrického zobrazení a A · x = λx pro nějaký komplexní vektor x ∈ Cn. Rozšíříme si definici skalárního součinu , na Cn vztahem x, y = xT · ¯y kde ¯y je vektor v Cn s komplexně konjugovanými souřadnicemi. Zjevně platí i pro rozšířené zobrazení x → A · x vztah A · x, y = x, A · y a pro náš vlastní vektor x tedy dostáváme λ x, x = ¯λ x, x . Kladným reálným číslem x, x můžeme krátit a proto musí být ¯λ = λ, tj. vlastní čísla jsou skutečně reálná. Symetrická zobrazení Rozklady matic a pseudoinverze Komplexních kořenů má charakteristický polynom det(A − λE) tolik, kolik je dimenze čtvercové matice A, a všechny jsou ve skutečnosti reálné. Lemma Ortogonální doplněk k invariantnímu podprostoru pro symetrické zobrazení je také invariantní. Navíc jsou všechna vlastní čísla symetrické matice A reálná. Ze samotné definice je zřejmé, že zúžení symetrického zobrazení na invariantní podprostor je opět symetrické. Předchozí tvrzení nám tedy zaručuje, že bude vždy existovat báze V z vlastních vektorů. Skutečně, zúžení f na ortogonální doplněk invariantního podprostoru je opět ortogonální zobrazení, takže můžeme do báze přibírat jeden vlastní vektor za druhým, až dostaneme celý rozklad V . Vlastní vektory příslušející různým vlastním číslům jsou navíc kolmé, protože z rovností f (u) = λu, f (v) = µv vyplývá λ u, v = f (u), v = u, f (v) = µ u, v . Symetrická zobrazení Rozklady matic a pseudoinverze Nezáporná zobrazení a odmocniny Nezáporná reálná čísla jsou právě ta, která umíme psát jako druhé mocniny. Zobecnění takového chování pro matice a zobrazení lze vidět u součinů B = AT · A (tj. složení zobrazení f ∗ ◦ f ): B · x, x = AT · A · x, x = A · x, A · x ≥ 0 pro všechny vektory x. Navíc zjevně BT = (AT · A)T = AT · A = B. Symetrickým maticím B s takovou vlastností říkáme nezáporné a pokud nastane nulová hodnota pouze pro x = 0, pak jim říkáme kladné. Obdobně hovoříme o kladných a nezáporných zobrazeních f : V → V . Symetrická zobrazení Rozklady matic a pseudoinverze Pro každé nezáporné zobrazení f : V → V umíme najít jeho odmocninu, tj. zobrazení g takové, že g ◦ g = f . Nejjednodušeji to uvidíme v ortonormální bázi, ve které bude mít f diagonální matici. Taková podle našich předchozích úvah vždy existuje a matice A zobrazení f v ní bude mít na diagonále nezáporná reálná vlastní čísla zobrazení f . Kdyby totiž bylo některé z nich záporné, nebyla by splněna podmínka nezápornosti již pro některý z bázových vektorů. Pak ovšem stačí definovat zobrazení g pomocí matice B s odmocninami příslušných vlastních čísel na diagonále. Symetrická zobrazení Rozklady matic a pseudoinverze I při počítání s reálnými čísly užíváme pro zjednodušení rozklady na součiny. Nejjednodušším je vyjádření každého reálného čísla jednoznačně ve tvaru a = sgn(a) · |a|, tj. jako součin znaménka a abolutní hodnoty. Obdobné rozklady se užívají u matic a mají dalekosáhlé důsledky pro numeriku. Zde jen naznačíme. Symetrická zobrazení Rozklady matic a pseudoinverze LU rozklad Gausova eliminace spočívá v postupném násobení naší matice invertibilními maticemi Pi , které postihovaly přičítání násobků řádků pod právě zpravovávaným. Předpokládejme pro jednoduchost, že nepotřebujeme při eliminaci přehazovat řádky, tj. všechny naše matice Pi mohou být dolní trojúhelníkové s jedničkami na diagonálách. Konečně, inverzní matice k takovýmto Pi jsou opět dolní trojúhelníkové s jedničkami na diagonálách a dostáváme U = P · A = Pk · · · P1 · A kde U je horní trojúhelníková matice a tedy A = L · U kde L je dolní trojúhelníková matice s jedničkami na diagonále a U je horní trojúhelníková. Symetrická zobrazení Rozklady matic a pseudoinverze Přímým důsledkem Gausovy eliminace bylo také zjištění, že až na volbu vhodných bází na definičním oboru a oboru hodnot, je každé zobrazení f : V → W zadáno maticí v blokově diagonálním tvaru s jednotkovou maticí s rozměrem daným dimenzí obrazu f nulovými bloky všude kolem. To lze přeformulovat takto: Každou matici A typu m/n nad polem skalárů K lze rozložit na součin A = P · E 0 0 0 · Q. Pro čtvercové matice jsme ukázali při diskusi vlastností lineárních zobrazení f : V → V na komplexních vektorových prostorech, že každou čtvercovou matici A dimenze m umíme rozložit na součin A = P · B · P−1 kde B je blokově diagonální s Jordanovými bloky příslušnými k vlastním číslům na diagonále. Všimněme si, že násobení maticí P a její inverzí z opačných stran odpovídá v tomto přípaě právě změně báze na vektorovém prostoru V . Symetrická zobrazení Rozklady matic a pseudoinverze Věta o singulárním rozkladu Jestliže se omezíme na ortonormální báze, ale chceme znát více informací o struktuře obecných lineárních zobrazení, musíme postupovat o hodně rafinovaněji, než v případě bazí libovolných: Theorem Nechť A je reálná matice typu m/n. Pak existují čtvercové ortogonální matice U a V dimenzí m a n, a reálná diagonální matice s nezápornými prvky D dimenze r, r ≤ min{m, n}, takové, že A = USV T , S = D 0 0 0 , kde r je hodnost matice AAT . Přitom je S určena jednoznačně až na pořadí prvků a prvky diagonální matice D jsou druhé odmocniny vlastních čísel di matice AAT . Symetrická zobrazení Rozklady matic a pseudoinverze Geometrická interpretace singulárního rozkladu Diagonálním hodnotám matice D z předchozí věty se říká singulární hodnoty matice A. Pro přísluąné zobrazení ϕ : Rn → Rm mají jednoduchý geometrický význam: Nechť K ⊂ Rn je jednotková sféra pro standardní skalární součin. Obrazem ϕ(K) pak vždy bude (případně degenerovaný) m-rozměrný elipsoid. Singulární čísla matice A jsou přitom velikosti hlavních poloos a věta navíc říká, že původní sféra vždy připouští ortogonální sdružené průměry, jejichž obrazem budou právě všechny poloosy tohoto elipsoidu. Pro čtvercové matice je vidět, že A je invertibilní právě, když všechna singulární čísla jsou nenulová. Poměr největšího a nejmenšího singulárního čísla je důležitým parametrem pro robustnost řady numerických výpočtů s maticemi, např. pro výpočet inverzní matice. Symetrická zobrazení Rozklady matic a pseudoinverze Definition Nechť A je reálná matice typu m/n a nechťA = USV T je její singulární rozklad, S = D 0 0 0 . Matici A(−1) := VS UT s S = D−1 0 0 0 nazýváme pseudoinverzní matice k matici A. Jak ukazuje následující věta, je pseudoinverze důležité zobecnění pojmu inverzní matice. Symetrická zobrazení Rozklady matic a pseudoinverze Theorem Nechť A je reálná matice typu m/n. Platí 1 Je-li A invertibilní (zejména tedy čtvercová), pak A(−1) = A−1 . 2 pro pseudoinverzi A(−1) platí, že A(−1)A i AA(−1) jsou symetrické a AA(−1) A = A, A(−1) AA(−1) = A(−1) . 3 Uvažme pro danou matici A systém lineárních rovnic Ax = b, b ∈ Rm. Pak y = A(−1)b ∈ Rn minimalizuje vzdálenost Ax − b pro všechny x ∈ Rn. Symetrická zobrazení Rozklady matic a pseudoinverze Lineární regrese Aproximační vlastnost (3) předchozí věty je velice užitečná v případech, kdy máme najít co nejlepší přiblížení (neexistujícího) řešení přeurčeného systému Ax = b, kde A je reálná matice typu m/n a m je větší než n. Např. máme experimentem dáno mnoho naměřených hodnot bj a chceme najít lineární kombinaci několika funkcí fi , která bude co nejlépe aproximovat hodnoty bj . Skutečné hodnoty zvolených funkcí v bodech yj ∈ R zadají matici aij = fi (yj ) a naším úkolem je tedy určit koeficienty xj ∈ R tak, aby m i=1(bi − ( n j=1 xj aij ))2 byla minimální. Jinými slovy, hledáme lineární kombinaci funkcí fi takovou, abychom ”dobře” proložili zadané hodnoty bi . Díky předchozí větě jsou hledané optimální koeficienty A(−1)b.