Rozdzial 3 Normy wektorów i macierzy W tym rozdziale zakladamy, że K Ä…" C. 3.1 Ogólna definicja normy Niech È : Km,n [0, + ") bedzie przeksztalceniem spelniajacym warunki: (i) "A " Km,n È(A) = 0 Ð!Ò! A = 0, (ii) "A " Km,n "u " K È(u " A) = |u| · È(A), (iii) "A, B " Km,n È(A + B) d" È(A) + È(B) (nierówność trójkata albo subaddytywność). Każde takie przeksztalcenie È nazywamy norma w Km,n i oznaczamy È(A) = A . Norma jest miara wielkoÅ›ci macierzy. Dlatego A - B uznajemy za miare odlegloÅ›ci miedzy macierzami A i B. Powiemy, że norma jest monotoniczna gdy warunek |A| d" |B| (tzn. gdy |ai,j| d" |bi,j| "i, j) implikuje A d" B . JeÅ›li norma w Kn,n spelnia A " B d" A · B , "A, B " Kn,n, to mówimy, że norma jest submultiplikatywna. 21 22 ROZDZIAL 3. NORMY WEKTORÓW I MACIERZY 3.2 Normy wektorów 3.2.1 Normy p-te Wektory w Kn sa szczególnymi macierzami. W tym przypadku, ważnymi przykladami norm sa normy Schura, zdefiniowane dla danej p, 1 d" p d" ", jako 1/p n x = |xi|p dla 1 d" p < ", p i=1 x = max |xi|. " 1d"id"n Nietrudno zauważyć, że x = limp " x , "x " Kn. " p Warunki (i) i (ii) normy sa trywialnie spelnione przez normy Schura. Warunek (iii) latwo sprawdzić dla p = 1, ". Dla p = 1 mamy bowiem n n n x + y = |xi + yi| d" |xi| + |yi| = x + y , 1 1 1 i=1 i=1 i=1 a dla p = " x + y = max |xi + yi| d" max |xi| + max |yi| = x + y . 1 " " 1d"id"n 1d"id"n 1d"id"n (W obu przypadkach zastosowaliÅ›my nierówność trójkata |u + v| d" |u| + |v| dla liczb zespolonych u i v.) Dla innych wartoÅ›ci p warunek (iii) jest dużo trudniej pokazać. Dlatego ograniczymy sie tu jedynie do przypadku p = 2. Lemat 3.1 (Nierówność Schwarza) Dla dowolnych u, v " Kn mamy |uH " v| d" u · v . 2 2 Dowód. Dla t " K mamy 2 0 d" u + v " t = (u + v " t)H · (u + v " t) 2 Å»· Å» = uH " u + t t " vH " v + uH " v " t + vH " u " t 2 2 = u + |t|2 · v + |t| · |uH " v| · É(Õ+È) + É-(Õ+È) , 2 2 gdzie t = |t| · ÉÈ, uH " v = |uH " v| · ÉÕ, É = cos 1 + 1 · sin 1. 3.2. NORMY WEKTORÓW 23 Biorac teraz È = -Õ mamy 2 2 0 d" u + 2|t| · |uH " v| + |t|2 · v , 2 2 a biorac È = Ä„ - Õ mamy 2 2 0 d" u - 2|t| · |uH " v| + |t|2 · v . 2 2 Stad dla dowolnej Ä " R otrzymujemy 2 2 0 d" u + 2Ä|uH " v| + Ä2 v . 2 2 Ponieważ prawa strona ostatniej nierównoÅ›ci jest, jako funkcja Ä, trójmianem kwadratowym o wartoÅ›ciach nieujemnych, to 2 2 0 e" " = 4 |u " v|2 - u · v , 2 2 co implikuje |uH " v| d" u · v i koÅ„czy dowód. 2 2 Na podstawie nierównoÅ›ci Schwarza mamy teraz 2 2 2 u + v = u + v + uH " v + vH " u 2 2 2 2 2 = u + v + 2 (uH " v) 2 2 2 2 d" u + v + 2|uH " v| 2 2 2 2 d" u + v + 2 u v 2 2 2 2 = ( u + v )2 , 2 2 czyli nierówność trójkata dla · . 2 3.2.2 Pożyteczne (nie)równoÅ›ci Nietrudno pokazać nastepujace nierównoÅ›ci laczace normy p-te Schura dla p = 1, 2, ". Mianowicie, dla każdego u " Kn mamy u d" u d" n · u , " 1 " " u d" u d" n · u , " 2 " " u d" u d" n · u , 2 1 2 24 ROZDZIAL 3. NORMY WEKTORÓW I MACIERZY przy czym ostatnia z tych nierównoÅ›ci jest konsekwencja nierównoÅ›ci Schwa- rza, 1/2 1/2 n n n n " u = |ui| = |ui| · |1| d" |ui|2 12 = n · u . 1 2 i=1 i=1 i=1 i=1 Dodatkowo zauważamy, że nierównoÅ›ci tych nie można poprawić. Na przy- klad, dla pierwszego wersora e1 mamy e1 = 1 "p, a dla 1 = [1, 1, . . . , 1] " p " Kn mamy 1 = n 1 = n 1 . 1 2 " Kula jednostkowa w Kn (ze wzgledu na norme · ) nazywamy zbiór wektorów K = { u " Kn : u d" 1} . Z podanych powyżej nierównoÅ›ci wynika w szczególnoÅ›ci, że K1 ‚" K2 ‚" K ", gdzie Kp jest kula jednostkowa w normie p-tej Schura. Zauważmy jeszcze, że normy p-te sa monotoniczne oraz, że dla dowolnej macierzy permutacji P " Kn,n i wektora x " Kn P " x = x , p p tzn. norma p-ta wektora jest niezmiennicza ze wzgledu na przestawienia kolejnoÅ›ci jego wspólrzednych. 3.3 Normy macierzy 3.3.1 Normy p-te Normy p-te macierzy sa definiowane (indukowane) przez normy p-te wek- torów w nastepujacy sposób: A " x p A = sup p x 0 =x"Kn p = sup { A " x : x " Kn, x = 1} . p p Zauważmy, że używamy tego samego oznaczenia dla norm wektora jak i ma- cierzy. Jest to uzasadnione, gdyż norma p-ta macierzy jest uogólnieniem 3.3. NORMY MACIERZY 25 normy p-tej wektora. Dla A = [u1, . . . , um]T " Km,1 = Km mamy bowiem m A = sup|t|=1 A " t = ( |ui|p)1/p. (Tutaj t " K!) p p i=1 Wprost z definicji wynika, że normy indukowane macierzy spelniaja wa- runek zgodnoÅ›ci (z norma wektorowa), tzn. "A " Km,n "x " Kn A " x d" A · x . p p p Normy te sa również submultiplikatywne, "A " Km,l "B " Kl,n A " B d" A · B . p p p RzeczywiÅ›cie, dla x " Kl mamy (A " B) " x = A " (B " x) d" A · B " x p p p p d" A · B · x , p p p skad (A " B) " x p sup d" A · B . p p x p x = 0 Dla macierzy permutacji P " Km,m i Q " Kn,n mamy P " A " QT = A , p p co oznacza, że przestawienie kolumn i wierszy macierzy nie zmienia jej p- tej normy. RzeczywiÅ›cie, ponieważ przestawienie wspólrzednych nie zmienia normy p-tej wektora, mamy P " A " QT " x p A " QT " x p A " y p sup = sup = . x p QT " x p y = 0 y p x = 0 x = 0 3.3.2 Pożyteczne (nie)równoÅ›ci Dla niektórych p, norme można wyrazić w sposób pozwalajacy ja latwo ob- liczyć. Lemat 3.2 Dla dowolnej macierzy A = (ai,j) " Km,n (a) A = max1d"id"m n |ai,j|, " j=1 (b) A = max1d"jd"n m |ai,j|. 1 i=1 26 ROZDZIAL 3. NORMY WEKTORÓW I MACIERZY Dowód. (a) Dla x = [x1, . . . , xn]T " Kn mamy n n A " x = max ai,j · xj d" max |ai,j| · |xj| " 1d"id"m 1d"id"m j=1 j=1 ëÅ‚ öÅ‚ n íÅ‚ d" x · max |ai,j|Å‚Å‚ . " 1d"id"m j=1 j Z drugiej strony, wezmy x" = (x") taki, że x" = É-Õ , 1 d" j d" n, gdzie Õj j j j jest argumentem liczby as,j, tzn. as,j = |as,j|ÉÕ , a s jest tym indeksem i, n dla którego suma |ai,j| jest najwieksza. Wtedy x" = 1 oraz " j=1 n n n j j A " x" e" as,j · x" = |as,j|ÉÕ É-Õ = |as,j|, " j j=1 j=1 j=1 a stad A e" max1d"id"m n |ai,j|. " j=1 (b) Dla dowolnego x mamy m n m n A " x = ai,j · xj d" |ai,j| · |xj| 1 i=1 j=1 i=1 j=1 n m m = |xj| · |ai,j| d" max |ai,j| · x . 1 1d"jd"n j=1 i=1 i=1 Z drugiej strony, dla x" takiego, że x" = 0 dla j = s, x" = 1 dla j = s, gdzie
j j m s jest tym indeksem j dla którego suma |ai,j| jest najwieksza, mamy i=1 m x" = 1 oraz A " x = |ai,s|, a stad A e" max1d"jd"n m |ai,j|. 1 1 1 i=1 i=1 Z powyższego lematu latwo widać, że AT = AH = A , " " 1 AT = AH = A . 1 1 " Szczególna role odgrywa norma druga · , ze wzgledów, które beda jasne 2 pózniej. Niestety, nie wyraża sie ona w tak prosty sposób jak · i · . 1 " W odróżnieniu od tych ostatnich, norma druga ma jednak dodatkowa ważna wlasność; mianowicie, dla dowolnej A " Km,n AT = AH = A . 2 2 2 3.3. NORMY MACIERZY 27 Równość ta wynika bezpoÅ›rednio z faktu, że A = sup sup yH " A " z , 2 z y gdzie suprema wziete sa po z " Kn i y " Km takich, że z = 1 = y . 2 2 RzeczywiÅ›cie, dla dowolnych y i z o jednostkowych normach mamy |yH " A " z| d" y · A " z = A " z d" A , 2 2 2 2 przy czym w pierwszej nierównoÅ›ci zastosowaliÅ›my nierówność Schwarza. Z drugiej strony, dla z o jednostkowej normie i takiego, że A " z = 0 mamy
2 A " z (A " z)H " A " z 2 A " z = = d" sup yH " A " z , 2 A " z 2 A " z 2 y =1 2 gdzie podstawiliÅ›my y = A " z/ A " z . 2 3.3.3 Norma Frobeniusa Norme Frobeniusa (albo Euklidesowa) macierzy A " Km,n definiujemy jako ëÅ‚ öÅ‚1/2 m n íÅ‚ A = |ai,j|2Å‚Å‚ . F i=1 j=1 Zaleta normy · jest jej latwa obliczalność , natomiast wada, że nie jest F to norma indukowana przez żadna norme wektorowa. Zwiazek miedzy norma Frobeniusa i norma druga pokazuje nastepujacy lemat. Lemat 3.3 Dla dowolnej A " Km,n mamy A d" A d" min(m, n) · A . 2 F 2 Dowód. Wykorzystujac nierówność Schwarza, dla dowolnego x " Kn o jednostkowej normie drugiej mamy ëÅ‚ öÅ‚2 2 m n m n 2 íÅ‚ A " x = ai,j · xj d" |ai,j| · |xj|Å‚Å‚ 2 i=1 j=1 i=1 j=1 ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ m n n íÅ‚ d" |ai,j|2Å‚Å‚ íÅ‚ |xj|2Å‚Å‚ = A , F i=1 j=1 j=1 28 ROZDZIAL 3. NORMY WEKTORÓW I MACIERZY a stad A d" A . 2 F Z drugiej strony, przedstawiajac A jako A = [a1, a2, . . . , an] , aj " Km, mamy A e" A " ej = aj , gdzie ej jest j-tym wersorem. Stad 2 2 2 n 1 1 2 2 2 A e" · aj = · A , 2 2 F n n j=1 " czyli A d" n · A . Ale również F 2 " " A = AT d" m · AT = m · A , F F 2 2 co koÅ„czy dowód. Zauważymy jeszcze jedna wlasność norm p-tych macierzy. Niech macierz A bedzie dana w postaci blokowej, A = [A1, A2, . . . , As] . Wtedy s Ak = sup Ak " xk = sup Aj " xj p p xk =1 p xk =1,xj= 0,j=k j=1
p p d" sup A " x = A . p p x =1 p Podobnie, jeÅ›li îÅ‚ Å‚Å‚ A1 ïÅ‚ śł A2 ïÅ‚ śł ïÅ‚ śł A = . ïÅ‚ śł . ðÅ‚ ûÅ‚ . At to t p p Ak = sup Ak " x d" sup Aj " x p p p p x =1 x =1 p p j=1 p p = sup A " x = A . p p x =1 p Stad dostajemy wniosek, że jeÅ›li A jest w postaci blokowej to dla każdego bloku Ai,j mamy Ai,j d" A , 1 d" p d" ". p p OczywiÅ›cie, ta wlasność zachodzi również dla normy Frobeniusa.