LA 13. cviˇcen´ı Ortogonalita, Gramm-Schmituv ˚ ortonormalizaˇcn´ı proces ´ s Posp´ısˇ il, Martin Hasal,2011 Lukaˇ
´ ı system ´ vektoru˚ 1 Ortogonaln´ ˇ ˇ v obecnem ´ tvaru ´ Poznamka: Motivace - pˇripomenme si Kosinovu vetu cos φ =
(u, v) ∥u∥.∥v∥
kde • φ je uhel mezi vektory u, v ∈ Rn ´ • (u, v) =
n ∑
´ ı souˇcin ui vi je standartn´ı skalarn´
i=1
√ • ∥u∥ =
n ∑ i=1
´ u2i je standartn´ı eukleidovska´ norma (delka vektoru) ˚
Pˇredstavme si, zˇ e uhel vektoru˚ je 90 stupnˇ u, ´ ˚ tedy π2 . Pak cos π2 = 0. 0=
(u, v) ⇔ 0 = (u, v) ∥u∥.∥v∥
ˇ by se dala postavit i opaˇcneˇ - pokud skalarn´ ´ ı souˇcin dvou vektoru˚ je Tedy Kosinova veta ´ roven nule, pak jsou tyto vektory na sebe kolme. ´ ´ ımi. V dalˇs´ım uˇcivu budeme uvaˇzovat vzajemn eˇ kolme´ vektory a naz´yvat je ortogonaln´ ≈ Definice 1.0.1 Necht’ je d´an vektorovy´ prostor V se skal´arn´ım souˇcinem (u, v). Mnoˇzinu vektoru˚ {v1 , . . . , vn } nazveme • ortogon´aln´ı, pokud { ∀i, j = 1, . . . , n : (vi , vj )
= 0 pokud i ̸= j ̸= 0 pokud i = j
• ortonorm´aln´ı, pokud { ∀i, j = 1, . . . , n : (vi , vj )
= 0 pokud i ̸= j = 1 pokud i = j
(1)
´ ı, pokud skalarn´ ´ ı souˇcin ´ Poznamka: Jednoduˇssˇ eji rˇeˇceno - mnoˇzina vektoru˚ je ortogonaln´ ´ ´ ı souˇcin stejn´ych libovolneho vektoru s jin´ym vektorem z dane´ mnoˇziny je nula a skalarn´ ´ ı souˇcin vˇzdy stejn´ych vektoru˚ roven jedne, ´ vektoru˚ je ruzn´ ˚ y od nuly. Nav´ıc, pokud je skalarn´ ´ ı. pak je mnoˇzina ortonormaln´ ≈ ´ ı mnoˇziny vektoru˚ se naz´yvaj´ı ortogonaln´ ´ ı vektory. Podobneˇ i ´ Poznamka: Prvky ortogonaln´ ´ ı mnoˇziny. pro ortonormaln´ ≈ Pˇr´ıklad 1.0.1 Rozhodnˇete, zda mnoˇzina vektoru˚ M = {[1, 1, 0], [0, 1, 1], [1, 0, 1]} je ortogon´aln´ı vzhledem ke skal´arn´ımu souˇcinu (u, v) = 2u1 v1 + 4u2 v2 + 2u3 v3 Pro jednoduchost si nejprve oznaˇcme vektory mnoˇziny f1 = [1, 1, 0] f2 = [0, 1, 1] f3 = [1, 0, 1] Jelikoˇz skal´arn´ı souˇcin je symetrick´a biline´arn´ı forma (tj. (u, v) = (v, u)), pak staˇc´ı pouze testovat tyto dvojice (napˇr´ıklad) (f1 , f2 ) = 2.1.0 + 4.1.1 + 2.0.1 = 4 (f1 , f3 ) = 2.1.1 + 4.1.0 + 2.0.1 = 2 (f2 , f3 ) = 2.0.1 + 4.1.0 + 2.1.1 = 2 Tedy ne, vektory nejsou ortogon´aln´ı, dan´a mnoˇzina vektoru˚ nen´ı ortogon´aln´ı.
ˇ a´ skalarn´ ´ ımu soucinu ˇ 2 Norma pˇr´ıslusn ´ ı souˇcin (u, v). Pak zobrazen´ı Uvaˇzujme skalarn´ √ ∥u∥ = (u, u) ´ ımu souˇcinu. Tato norma se naz´yva´ Eukleidovska´ jest normou pˇr´ısluˇsnou k tomuto skalarn´ norma. ˇ ´ Poznamka: V nekter e´ literatuˇre se takto definovana´ norma naz´yva´ norma indukovana´ ´ ım souˇcinem. skalarn´ ≈
(2)
ˇ ı proces 3 Gramm-Schmidtuv ˚ ortonormalizacn´ ´ ı mnoˇziny z mnoˇziny linearn ´ eˇ Tento sˇ ikovn´y algoritmus slouˇz´ı pro vytvoˇren´ı ortonormaln´ ´ nezavisl´ych vektoru. ˚ Oznaˇcme ´ eˇ nezavisl´ ´ • G = {g1 , . . . , gn } - puvodn´ ı mnoˇzina linearn ych vektoru˚ ˚ ´ ıch vektoru˚ • E = {e1 , . . . , en } - hledana´ mnoˇzina ortonormaln´ Pak Gramm-Schmituv ˚ ortonormalizaˇcn´ı proces bude vypadat takto: • Nejdˇr´ıve ”normalizujeme” prvn´ı vektor mnoˇziny G e1 =
g1 ∥g1 ∥
• A pro dalˇs´ı vektory postupujeme tak, zˇ e vˇzdy vezmeme z mnoˇziny G jeden vektor a ´ ı. A pak tento vektor opet ˇ normalzajist´ıme, aby nova´ mnoˇzina vektoru˚ byla ortogonaln´ izujeme. i−1 ∑ gi − (gi , ej )ej ′ j=1 ozn ei ei = , i = 2, . . . , n = i−1 ∑ ∥e′i ∥ ∥gi − (gi , ej )ej ∥ j=1
´ ´ ´ ´ Poznamka: Ukolem cviˇcen´ı nen´ı ukazat, zˇ e kde se tento zazrak vzal, jestli vubec funguje a ˚ ˇ udel ˇ ame ´ ˇ y pˇr´ıklad a ukaˇ ´ zeme, zˇ e ˇreˇsen´ı pˇr´ıkladu je spravn ´ e. ´ Nebo radeji ˇ proˇc. Radeji pekn´ ˇ ame ´ ˇ s´ı. udel dva pˇr´ıklady - jeden jednoduch´y a druh´y komplikovanejˇ ≈ Pˇr´ıklad 3.0.2 Pomoc´ı Gramm-Schmidtova ortonormalizaˇcn´ıho procesu vytvoˇrte z vektoru˚ g1 = [1, 0] g2 = [1, 1] ortonorm´aln´ı mnoˇzinu E vzhledem k standartn´ımu skal´arn´ımu souˇcinu (u, v) = u1 v1 + u2 v2 Fajne by bylo, kdyby mnoˇzina G = {g1 , g2 } byla ortogon´aln´ı. Jenˇze nen´ı, protoˇze napˇr. (g1 , g2 ) = ([1, 0], [1, 1]) = 1.1 + 0.1 = 1 ̸= 0 (g2 , g2 ) = ([1, 1], [1, 1]) = 1.1 + 1.1 = 2 ̸= 1 Tak jdeme na ten ortonormalizaˇcn´ı proces, nejdˇr´ıve prvn´ı vektor [1, 0] [1, 0] e1 = √ = = [1, 0] 1 12 + 0 2
(3)
A pak druhy´ vektor. Pro lepˇs´ı srozumitelnost a kratˇs´ı vypoˇ ´ cet nejdˇr´ıve spoˇcteme e′2
= g2 −
2−1 ∑
(g2 , ej )ej = g2 − (g2 , e1 )e1 = [1, 1] − ([1, 1], [1, 0]).[1, 0] =
j=1
= [1, 1] − (1.1 + 1.0).[1, 0] = [1, 1] − [1, 0] = [0, 1] Nyn´ı zbyv´ ´ a normalizovat tento vektor e2 =
e′2 [0, 1] [0, 1] =√ = = [0, 1] ′ 2 2 ∥e2 ∥ 1 0 +1
Na m´ıstˇe by byla jistˇe i zkouˇska - ovˇerˇ it, zˇ e nalezen´e vektory e1 , e2 jsou skuteˇcnˇe ortonorm´aln´ı: (e1 , e1 ) = ([1, 0], [1, 1]) = 1.1 + 0.0 = 1 (e2 , e2 ) = ([0, 1], [0, 1]) = 0.0 + 1.1 = 1 (e1 , e2 ) = ([1, 0], [0, 1]) = 1.0 + 0.1 = 0 Pozn´amka: Jednoduch´e? Ano, ale pouze tento pˇr´ıklad. Druhy´ bude brut´alnˇejˇs´ı. Slibuji.
≈
Pˇr´ıklad 3.0.3 Pomoc´ı Gramm-Schmidtova ortonormalizaˇcn´ıho procesu vytvoˇrte z vektoru˚ f1 = [1, 1, 0] f2 = [0, 1, 1] f3 = [1, 0, 1] ortonorm´aln´ı mnoˇzinu E vzhledem ke skal´arn´ımu souˇcinu (u, v) = 2u1 v1 + 4u2 v2 + 2u3 v3 Pozn´amka: Nejdˇr´ıve pozor! Eukleidovsk´a norma pˇr´ısluˇsn´a k dan´emu skal´arn´ımu souˇcinu m´a tvar √ √ ∥u∥ = (u, u) = 2u21 + 4u22 + 2u23 Tedy v algoritmu budeme normalizovat vzhledem k t´eto normˇe.
≈
Prvn´ı vektor nebude probl´em e1 =
f1 1 [1, 1, 0] = √ [1, 1, 0] =√ 2 2 2 ∥f1 ∥ 6 2.1 + 4.1 + 0
Druhy´ vektor spoˇc´ıt´ame tak, zˇ e si pro jednoduchost nejdˇr´ıve pˇredpoˇc´ıt´ame ortogon´aln´ı vektor e′2 a tento vektor posl´eze normalizujeme. e′2
= f2 −
2−1 ∑
1 1 (f2 , ej )ej = f2 − (f2 , e1 )e1 = [0, 1, 1] − ([0, 1, 1], √ [1, 1, 0]) √ [1, 1, 0] = 6 6 j=1
2 2 1 1 = [0, 1, 1] − .(2.0.1 + 4.1.1 + 2.1.0).[1, 1, 0] = [0, 1, 1] − .[1, 1, 0] = [− , , 1] 6 3 3 3 (4)
A pak ho normalizujeme e2 =
[− 32 , 13 , 1] [− 23 , 13 , 1] e′2 3 2 1 1 √ √ = = = √ [− , , 1] = √ [−2, 1, 3] ′ ∥e2 ∥ 30 30 3 3 30 2. 49 + 4. 91 + 2.1 9
Tˇret´ı vektor n´am uˇz malinko zkomplikuje zˇ ivot, nicm´enˇe po koneˇcn´em poˇctu kroku˚ se jistˇe dopracujeme ke spr´avn´emu rˇ eˇsen´ı e′3 = f3 −
3−1 ∑
(f3 , ej )ej = f3 − (f3 , e2 )e2 − (f3 , e1 )e1 =
j=1
1 1 1 1 = [1, 0, 1] − ([1, 0, 1], √ [−2, 1, 3]) √ [−2, 1, 3] − ([1, 0, 1], √ [1, 1, 0]) √ [1, 1, 0] = 30 30 6 6 2 3 1 1 1 1 0 1 = [1, 0, 1]−(2.1.(− √ )+4.0. +2.1. √ ) √ [−2, 1, 3]−(2.1. √ +4.0. √ +2.1. √ ) √ [1, 1, 0] = 30 30 30 30 6 6 6 6 2 2 1 = [1, 0, 1] − [−2, 1, 3] − [1, 1, 0] = . . . = [4, −2, 4] 30 6 5 a normalizace 1 [4, −2, 4] e′ 1 e3 = 3′ = √ 5 = . . . = √ [2, −1, 2]. ∥e3 ∥ 16 4 16 20 2. + 4. + 2. 25
25
25
ˇ ısla a vlastn´ı vektory 4 Vlastn´ı c´ Vlastn´ı cˇ ´ısla a vlastn´ı vektory matic jsou dalˇs´ı v´yznamnou charakteristikou matic. Vyuˇz´ıvaj´ı ˇ se napˇr´ıklad pˇri studiu konvergence nekter´ ych numerick´ych metod, jakoˇz i pˇri ˇreˇsen´ı ho´ ıch rovnic s konstantn´ımi koeficienty. mogenn´ıch soustav diferencialn´ Definice 4.0.2 Necht’ • V je vektorovy´ prostor • A ∈ L je line´arn´ı transformace nad vektorovym ´ prostorem V Jestliˇze existuje nenulovy´ vektor e ∈ V a skal´ar λ ∈ R tak, zˇ e Ae = λe
(1)
pak • cˇ ´ıslo λ nazyv´ ´ ame vlastn´ı cˇ´ıslo transformace A • vektor e nazyv´ ´ ame vlastn´ı vektor transformace A pˇr´ısluˇsny´ k vlastn´ımu cˇ ´ıslu λ ˇ y vektorov´y prostor, pak lze matici A ztotoˇznit ´ Poznamka: No, pokud V je koneˇcneˇ rozmern´ ´ ım zobrazen´ım A (je to matice transformace vzledem k nejak ˇ e´ bazi) ´ - podobneˇ jako s linearn´ u klasifikace kvadratick´ych forem. Tedy v dalˇs´ım v´ykladu muˇ ˚ zeme hovoˇrit o vlastn´ıch cˇ ´ıslech a vlastn´ıch vektorech matic ale ´ ı zobrazen´ı kteremu ´ budeme m´ıt na mysli linearn´ odpov´ıda´ dana´ matice. ≈ (5)
ˇ ısla 5 Jak hledat (a naj´ıt) vlastn´ı c´ Rovnici (1) lze malinko vylepˇsit Ae IAe Ae Ae − λIe (A − λI)e
= = = = =
vyn´asob´ıme zleva I plat´ı IA = AI = A, Iλ = λI odeˇcteme λIe vytkneme e, plat´ı (A + B)v = Av + Bv
λe Iλe λIe o o
´ ı zobrazen´ı (pokud A, I jsou ´ Poznamka: Pokud (A − λI) budeme povaˇzovat za linearn´ ´ ı zobrazen´ı, pak i (A − λI) je linearn´ ´ ı zobrazen´ı), pak e jsou de-facto vektory jadra ´ linearn´ (= vektory ktere´ se zobraz´ı na nulov´y prvek). ≈ ˇ Pˇripomenme si dveˇ velke´ pecky z minul´ych cviˇcen´ı: • soustavy s nulovou pravou stranou maj´ı nekoneˇcneˇ mnoho ˇreˇsen´ı, nebo pouze jedno - nulove´ ˇreˇsen´ı ´ ı matic´ı maj´ı prav ´ eˇ jedno ˇreˇsen´ı • soustavy s regularn´ ´ ı. A my nechceme, aby vektor e byl nulov´y, proto matice (A − λI) mus´ı b´yt singularn´ ´ ı matice maj´ı nulov´y determinant, tedy Jenomˇze singularn´ det (A − λI) = 0 ´ ı vlastn´ıch cˇ ´ısel. Neveˇr´ıte? A je to tam! Odvodili jsme algoritmus pro hledan´ Pˇr´ıklad 5.0.4 Naleznˇete vlastn´ı cˇ ´ısla a vlastn´ı vektory matice
1 1 0 A= 1 1 0 0 0 1 Nejdˇr´ıve si odvod´ıme, cˇ emu se rovn´a det (A − λI) 1 1 0 1 0 0 1−λ 1 0 1−λ 0 = det (A − λI) = det 1 1 0 − λ 0 1 0 = det 1 0 0 1 0 0 1 0 0 1−λ Uˇzit´ım Sarusova pravidla dost´av´ame: = (1−λ).(1−λ).(1−λ)+1.0.0+0.1.0−0.(1−λ).0−1.1.(1−λ)−(1−λ).0.0 = (1−λ)3 −(1−λ) = ˚ zeme vytknout muˇ = (1 − λ).((1 − λ)2 − 1) = (1 − λ).(1 − 2λ + λ2 − 1) = (1 − λ).(λ2 − 2λ) = λ(1 − λ)(λ − 2) Pozn´amka: T´eto vˇeci se rˇ´ık´a charakteristick´y polynom. Pˇresnˇeji rˇ eˇceno - charakteristicky´ poly´ nom je polynom, ktery´ vznikne upravou vyrazu det (A − λI). ≈ ´ (6)
Charakteristicky´ polynom jsem schv´alnˇe upravil na tvar souˇcinu line´arn´ıch funkc´ı. Jelikoˇz pokud poloˇz´ıme rovno nule det (A − λI) = 0
⇔
λ(1 − λ)(λ − 2) = 0
ze souˇcinu λ(1 − λ)(λ − 2) = 0 pˇr´ımo plyne, zˇ e λ je rovno 0, 1 nebo 2. Pak jeden z cˇ initelu˚ na lev´e stranˇe bude nulovy, ´ tedy i cely´ souˇcin bude nulovy´ a roven prav´e stranˇe. A tak je to spr´avn´e, tak to m´a byt. Tedy vlastn´ı cˇ ´ısla bychom mˇeli. Kuk na rovnici (A − λI)e = o Coˇz po dosazen´ı λ je soustava line´arn´ıch rovnic... rˇ eˇsiteln´a Gaussovou eliminaˇcn´ı metodou. Pomoc´ı determinantu˚ ne, protoˇze matice (A − λI) je sigul´arn´ı, tato matice bude m´ıt nulovy´ determinant a parametrick´e rˇ eˇsen´ı (ech, ale to je pˇreci to, o co n´am od zaˇca´ tku sˇ lo). Tak dosad’me postupnˇe jednotliv´a vlastn´ı cˇ ´ısla a rˇ eˇsme: 1. Dosad’me prvn´ı vlastn´ı cˇ ´ıslo λ1 = 0 a jelikoˇz A − 0.I = A budeme rˇ eˇsit soustavu Ae = o Tak jo... tak rˇ eˇsme:
1 1 0 0 1 1 0 0 1 1 0 0 ∼ 0 0 0 0 0 0 1 0 0 0 1 0
Tedy rˇ eˇsen´ım jest e1 = [−t, t, 0]T , t ∈ R 2. Dosad’me druh´e vlastn´ı cˇ ´ıslo λ2 = 1 a rˇ eˇsme 0 1−1 1 0 0 1 0 0 1 0 0 0 1 1−1 0 0 ∼ 1 0 0 0 ∼ 0 1 0 0 0 0 1−1 0 0 0 0 0 0 0 0 0 Tedy rˇ eˇsen´ım jest e2 = [0, 0, t]T , t ∈ R 3. Dosad’me tˇret´ı vlastn´ı cˇ ´ıslo λ3 1−2 1 0 1 1−2 0 0 0 1−2
= 2 a rˇ eˇsme −1 1 0 0 1 −1 0 0 0 0 ∼ 1 −1 0 0 ∼ 0 0 0 0 0 0 0 −1 0 0 0 1 0
Tedy rˇ eˇsen´ım jest e3 = [t, t, 0]T , t ∈ R
(7)
Poloˇzme napˇr´ıklad t = 1, pak vlastn´ımi cˇ ´ısly a pˇr´ısluˇsnymi vlastn´ımi vektory matice A ´ jsou dvojice −1 0 1 λ1 = 0, v1 = 1 λ2 = 1, v2 = 0 λ3 = 2, v3 = 1 0 1 0 Pozn´amka: Japato parametrick´e rˇ eˇsen´ı? To je jasn´e - parametricky n´am to vyjde vˇzdy, protoˇze soustava je se singul´arn´ı matic´ı. Ale tak to m´a vyj´ıt! Uvaˇzujme rovnici (A − λI)e = o t.(A − λI)e = t.o (A − λI)(t.e) = o
pˇren´asobme libovolnym ´ t ∈ R, t ̸= 0 t je skal´ar
Pak je jasn´e, zˇ e i vektor t.e je pˇr´ısluˇsnym ´ vlastn´ım vektorem.
≈
ˇ ´ ı vlastn´ıch cˇ ´ısel a vlastn´ıch vektoru: Tedy zhrnme postup hledan´ ˚ 1. z det (A − λI) odvod´ıme charakteristick´y polynom ´ 2. nalezneme koˇreny charakteristickeho polynomu - to jsou vlastn´ı cˇ ´ısla 3. pro jednotliva´ vlastn´ı cˇ ´ısla nalezneme pˇr´ısluˇsne´ vlastn´ı vektory jako ˇreˇsen´ı rovnice (A − λi )ei = o
6 Lokalizace spektra ´ cne´ pro v´ypoˇcet, pˇredchoz´ı algoritmus je ´ Poznamka: Jelikoˇz determinanty jsou pˇr´ıliˇs naroˇ ˇ pro velke´ matice prakticky nepouˇziteln´y. A nekdy staˇc´ı pouze odhadnout kde se pˇribliˇzneˇ ´ ı. K tomu slouˇz´ı velice jednoducha´ veta ˇ - Gerˇsgorinova. vlastn´ı cˇ ´ısla nachazej´ ≈ Vˇeta 6.0.1 (Gerˇsgorinova) Necht’ A ∈ Cn,n (komplexn´ı cˇ tvercov´a matice A rˇ a´ du n). Oznaˇcme [a]ij prvek matice A na i-t´em rˇ a´ dku a j-t´em soupci. D´ale oznaˇcme cˇ ´ısla ri = |ai1 | + . . . + |ai,i−1 | + |ai,i+1 | + . . . + |ain | a mnoˇziny Si = {z ∈ C : |z − aii | ≤ ri pro i = 1, . . . , n. Pak vlastn´ı cˇ ´ısla matice A leˇz´ı v mnoˇzinˇe (jsou prvky mnoˇziny) S = S1 ∪ . . . ∪ Sn (8)
´ ˇradku, ´ ´ Poznamka: V´ypoˇcet ri je vlastneˇ souˇcet absolutn´ıch hodnot prvku˚ v i-tem krom ´ ıho. diagonaln´ ≈ ´ na v´yznam linearn´ ´ ıch nerovnic s absolutn´ı hodnotou ze stˇredn´ı ´ Poznamka: Vzpom´ınate sˇ koly? |z − ai i| ≤ ri ´ ”Vzdalenost z od bodu aii je menˇs´ı nebo rovna jako ri ”. Jedna´ se o kruh se stˇredem v bodeˇ ˇ aii a polomerem ri . ≈ ˇ vypadat pˇr´ıliˇs jednoduˇse, je to velmi robustn´ı nastroj ´ ´ Poznamka: Aˇckoliv muˇ pro ˚ ze tato veta ˇ ˇ horn´ı odhad nejvetˇs´ıho vlastn´ıho c´ısla. ≈ Pˇr´ıklad 6.0.5 Necht’ je d´ana matice
[ A=
2 −1 −1 2
]
Tato symetrick´a cˇ tvercov´a matice A je pozitivnˇe definitn´ı, spektrum matice dle Gerˇsgorinovy vˇety je obsaˇzeno v mnoˇzinˇe Ω = {x ∈ C : |x − 2| ≤ 1}
Je vidˇet, zˇ e pokud vezmeme libovoln´e cˇ ´ıslo z t´eto mnoˇziny, tak bude kladn´e.
7 Reference ´ Linearn´ ´ ı algebra, skriptum, Ostrava [1] Z. Dostal, ´ LA1 - 12. cviˇcen´ı [2] V. Vondrak,
(9)
