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.