TÓPICOS DE ÁLGEBRA LINEAR Paulo Lopes dos Santos Departamento de Engenharia Electrotécnica e Computadores Faculdade de Engenharia da Universidade do Porto Rua Dr Roberto Frias, s/n 4200-464 Porto, Portugal Email: [email protected] Setembro 2007 Tópicos de Algebra Linear 1 Conteúdo 1 Vectores Linearmente Independentes 2 2 Subespaços e Bases 4 3 Subespaços Associados a Matrizes e Decomposição QR 6 4 Decomposição em Valores Singulares 11 5 Norma Quadrática de Matrizes 16 6 Aproximação de uma Matriz por Outra de Caracterı́stica Inferior 22 7 Projecções Ortogonais de Subespaços 25 8 Projecções Oblı́quas de Subespaços 32 9 Projecções nos Subespaços gerados pelas linhas duma matriz 33 10 Produto de Kronecker e Vectorização de Matrizes 34 11 Norma de Frobenius 39 Tópicos de Algebra Linear 1 2 Vectores Linearmente Independentes Sejam v1 , v2 , . . . , vn vectores em IRn . Diz-se que estes vectores são linearmente independentes se, para um conjunto de escalares αi ∈ IR, i = 1, . . . , n n X αi vi = 0n ⇒ α1 = α2 = · · · = αn = 0, i=1 · n v11 v12 ¸ em que 0n é o vector de IR com todas as entradas nulas. Se v1 = ∈ IR2 e v2 = · ¸ · ¸ v21 z1 2 ∈ IR , então, qualquer ponto z = , pertencente ao subespaço S ⊆ IR2 gerado v22 z2 por v1 e v2 , pode ser expresso através da combinação linear · ¸ · ¸ · ¸ · ¸· ¸ · ¸ v11 v21 z1 v11 v21 α1 z1 α1 v1 + α2 v2 = z ⇔ α1 + α2 = ⇔ = . v12 v22 z2 v12 v22 α2 z2 · ¸ v11 v21 Se a matriz V = for não singular e se z = 02 , então v12 v22 · ¸ · ¸−1 · ¸ · ¸ α1 v11 v21 z1 0 = = α2 v12 v22 z2 0 e, consequentemente, só para α1 = α2 = 0 é que v1 e v2 se anulam. Concluı́mos, assim, que v1 e v2 são independentes se e só se (sse) V for uma matriz não singular, ou seja, sse det V 6= 0. Como det V = v11 v22 − v21 v12 então det V = 0 ⇔ v11 v22 − v21 v12 v21 v22 =0⇔ = =k⇒ v11 v12 ½ v21 = kv11 ⇔ v2 = kv1 v22 = kv12 significando isto que v1 e v2 são independentes sse não forem colineares. v2 v1 u2 u1 Figura 1: v1 e v2 são linearmente independentes e u1 e u2 são linearmente dependentes Em IR2 o máximo que conseguimos é um conjunto de dois vectores linearmente independentes. Qualquer conjunto com mais de dois vectores não é de vectores linearmente independentes. Tópicos de Algebra Linear 3 Exemplo 1 : 2 Seja {v· 1 , v2 , v¸ 3 } um conjunto · ¸de vectores não nulos em IR . Acabamos de ver ½·que se os vec¸¾ v11 v21 v11 v21 tores v1 = e v2 = forem linearmente independentes então det 6= v12 v22 v12 v22 0 Nestas condições, · ¸ · ¸−1 · ¸ α1 v11 v21 v31 = 6= 02 α2 v12 v22 v32 é a solução da equação · α1 v1 + α2 v2 = v3 ⇔ v11 v21 v12 v22 ¸· α1 α2 ¸ · = v31 v32 ¸ e, consequentemente, α1 v1 + α2 v2 − v3 = 02 significando isto que {v1 , v2 , v3 } nunca pode ser um conjunto de vectores independentes. x2 v32 α1 v1 α1 v12 v3 α2 v22 α 2 v2 v22 v12 v2 v1 x1 v21 α2 v21 v11 v31 α1 v11 Figura 2: v1 ,v2 e v3 são vectores no mesmo plano e, por isso, são linearmente dependentes Pode-se provar de forma idêntica que, no espaço IRn nunca se conseguem mais do que n vectores linearmente independentes. Tópicos de Algebra Linear 2 4 Subespaços e Bases Seja S um subconjunto do espaço vectorial E, isto é, S ⊆ E. Se, para quaisquer elementos v1 e v2 pertencentes a S e quaisquer escalares α1 e α2 a combinação linear α1 v1 + α2 v2 pertencer a S, então S é um subespaço de E. Deste modo, todas as combinações lineares dos vectores {v1 , v2 , . . . , vm } com vi ∈ IRn formam um subespaço de IRn . Esse subespaço é designado como ( S = span {v1 , v2 , . . . , vm } = x:x= m X ) αi vi , ∀αi ∈IR . i=1 Dizemos, então, que qualquer conjunto de vectores {v1 , v2 , . . . , vm } gera um subespaço. Exemplo 2 : Todas as combinações lineares do vector v1 são vectores colineares com v1 . Isto significa que o subespaço gerado pelo vector v1 (span {v1 }) é a recta que o contém. x2 span{v1 } v1 x1 Figura 3: O subespaço gerado por v1 é a recta span{v1 } Exemplo 3 : O subespaço definido pelo conjunto de vectores {v1 , v2 } é o plano que contém v1 e v2 (span{v1 , v2 }) se estes vectores forem linearmente independentes. Se forem dependentes é a recta que os contém. A dimensão dum subespaço é o número de vectores linearmente independentes que são necessários para o gerar. Assim, qualquer recta que passe pela origem é um subespaço de Tópicos de Algebra Linear 11111111111111111111 00000000000000000000 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 x 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 spa 00000000000000000000 11111111111111111111 n{ v ,v } 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 v 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 v 00000000000000000000 11111111111111111111 00000000000000000000 11111111111111111111 x 11111111111111111111 00000000000000000000 5 3 1 2 1 x1 2 2 Figura 4: O subespaço gerado por v1 e v2 é o plano span{v1 , v2 } dimensão um, pois, pode ser gerada por um único vector. Qualquer plano que contenha a origem é um subespaço de dimensão dois (pode ser gerado por dois vectores linearmente independentes). Seja S um subespaço de IRn com dimensão p. Qualquer conjunto de vectores independentes {v1 , v2 , . . . , vp } pertencentes a S é uma base de S. Deste modo, qualquer elemento x ∈ S pode ser representado pela combinação linear x = β1 v1 + β2 v2 + · · · + βp vp em que β1 , β2 , . . . , βp são as componentes (coordenadas) de x relativamente à base {v1 , v2 , . . . , vp }. Notemos que qualquer subespaço S tem um número infinito de bases. No entanto, o número de elementos de cada base é sempre igual à dimensão de S. Sejam x, y ∈ IRn . Se xT y = y T x = 0 dizemos que x e y são ortogonais o que representamos por x⊥y. Se y T x = 0 para todo x ∈ S ⊂ IRn , então y é ortogonal a S o que designamos por Tópicos de Algebra Linear 6 y⊥S. O conjunto de todos os vectores perpendiculares a S é o complemento ortogonal de S e é representado por S⊥ . Formalmente, podemos definir S⊥ por © ª S⊥ = y ∈ IRn : y T x = 0, ∀x ∈ S . Pode-se provar que S⊥ é um subespaço de IRn mesmo que S o não seja. Sejam S e V subespaços de IRn . A soma de S e V, designada por S ∨ V, é o subespaço gerado por todos os elementos de S e V. A sua definição formal é S ∨ V = {x + y : x ∈ S ∧ y ∈ V} . É importante assinalar que este subespaço não é a união de S e V (S∪V não é um subespaço). Se S ∩ V = {0}, designamos S ∨ V por soma directa. Se, para quaisquer vectores x ∈ S, y ∈ V, y T x = 0, dizemos que S é ortogonal a V o que representamos por S⊥V. Neste caso, S ∨ V é a soma ortogonal directa e é representada por S ⊕ V. Para qualquer subespaço S ∈ IRn existe uma única decomposição IRn = S ⊕ S⊥ . Isto significa que para todo z ∈ IRn existe uma única decomposição z = x + y em que x ∈ S e y ∈ S⊥ . 3 Subespaços Associados a Matrizes e Decomposição QR Dado um conjunto de vectores em IRn como é que podemos verificar se são linearmente independentes? A forma mais simples é formar uma matriz cujas colunas (ou linhas) são as coordenadas desses vectores e calcular a sua caracterı́stica (recordemos que a caracterı́stica duma matriz é o seu número de linhas ou colunas linearmente independentes). Exemplo 4 : Sejam v1 = 1 2 3 4 5 e v2 = M = £ v1 1 3 2 6 ¤ v2 = 3 9 4 12 5 15 3 6 9 12 15 dois vectores em IR5 . Se formarmos a matriz Tópicos de Algebra Linear 7 podemos ver que car(M ) = 1 e concluir que v1 e v2 são linearmente dependentes (é fácil ver que v2 = 3v1 e que, consequentemente, estes dois vectores são colineares). Como car(M T ) = car(M ) chegarı́amos ao mesmo resultado através do cálculo da caracterı́stica de · M T = v1T v2T ¸ · = 1 2 3 4 5 3 6 9 12 15 ¸ . Uma forma interessante de vermos uma matriz A ∈ IRn×m , é encarar as suas colunas (ou as suas linhas) como um conjunto de vectores que geram um subespaço em IRn (ou IRm no caso das linhas). Deste modo, podemos associar a A dois subespaços: • 1 - Subespaço gerado pelas suas colunas (column-space) que designaremos por im(A) (imagem de A); • 2 - Subespaço gerado pelas suas linhas (row-space) que designaremos por im(AT ) (imagem de AT ); Consideremos agora um vector x ∈ IRm . Se multiplicarmos A por x vamos obter um vector em IRn , isto é, v = Ax ∈ IRn Podemos, então, afirmar que a matriz A define uma transformação do espaço IRm para IRn (IRm → IRn ). Sendo A = £ a1 a2 · · · am ¤ em que ai ∈ IRn , i = 1, . . . , m e x1 x2 x = .. . xm então v = Ax = £ a1 a2 · · · am ¤ x1 x2 .. . xm = a1 x1 + a2 x2 + · · · + am xm , Tópicos de Algebra Linear 8 ou seja, v = Ax é uma combinação linear das colunas de A, cujos coeficientes são os elementos x1 , x2 , . . . , xm de x. Deste modo, v pertence sempre ao subespaço gerado pelas colunas de A, isto é, im(A). Se as colunas de A forem linearmente independentes, então constituem uma base para im(A). Nestas condições, diz-se que A é uma matriz de caracterı́stica completa (car(A) = m = número de colunas). Identicamente, AT define uma transformação IRn → IRm , sendo a imagem dessa transformação (im(AT )) o subespaço gerado pelas linhas de A. Se as linhas de A constituı́rem uma base de im(AT ), então AT e, consequentemente A, são matrizes de caracterı́stica completa. Assim, A ∈ IRn×m é uma matriz de caracterı́stica completa se e só se car(A) = n ou car(A) = m ⇔ car(A) = min(n, m) Notemos que, sendo v = Ax uma combinação linear das colunas de A, podemos exprimir v através duma outra combinação linear de outro conjunto de vectores que gere a imagem de A. Isto significa que podemos escrever v = Ax = Āx̄ em que im(Ā) = im(A) e x̄ são os coeficientes da referida combinação linear das colunas de Ā. Aqui a única restrição é car(Ā) = car(A) e, consequentemente, o número de colunas de Ā, igual ao número de linhas de x̄, não tem que ser igual ao número de colunas de A. Frequentemente procuramos que as colunas de Ā sejam uma base que, termos numéricos, seja o mais robusta possı́vel. A robustez máxima é alcançada quando as colunas de Ā constituem uma base ortonormal, isto é, quando são um conjunto de vectores com módulo unitário e perpendiculares entre si. Matrizes cujas colunas formam uma base ortonormal são chamadas matrizes ortonormais e são frequentemente designadas pela letra Q. Notemos que se Q ∈ IRn×m for uma matriz ortonormal então QT Q = I m Se Q for uma matriz quadrada (m = n) então QT Q = Im = In ⇔ Q−1 = QT . É esta propriedade que faz com que estas matrizes sejam numericamente muito robustas e que frequentemente se procure representar im(A) através destas matrizes. Uma das formas Tópicos de Algebra Linear 9 mais utilizadas na álgebra linear para atingir este objectivo é a decomposição QR, onde uma matriz A ∈ IRn×m com n ≥ m e car(A) = r, é decomposta no produto de matrizes · ¸ R 0r×(m−r) A = Q = QR R 0(n−r)×r 0(n−r)×(m−r) £ ¤ em que Q = QR Q̄R ∈ IRn×n com QR ∈ IRn×r e Q̄R ∈ IRn×(n−r) . Q é uma matriz ortonormal (QT Q = In ) e, consequentemente, QR e Q̄R também o são (QTR QR = Ir e Q̄TR Q̄R = In−r ), sendo im(Q̄R ) o complemento ortogonal de im(QR ) o que representamos por Q¯R = Q⊥ . R ∈ IRr×r é uma matriz triangular superior. R Exemplo 5 : Transformação QR na resolução do sistema de equações Ax = y Consideremos o sistema de equações Ax = y em que A ∈ IRn×n , x, y ∈ IRn e car(A) = n. Fazendo uma decomposição QR teremos QRx = y ⇔ Rx = QT y ficando este sistema de equações reduzido a r11 r12 · · · r1n x1 ȳ1 0 r22 · · · r2n x2 ȳ2 .. .. . . .. .. = .. . . . . . . 0 0 · · · rnn xn ȳn em que ȳ = ȳ1 ȳ2 .. . = QT y. ȳn Como R é uma matriz triangular superior, as soluções xn , xn−1 , . . . , x1 podem ser calculadas recursivamente por substituição à retaguarda (back substitution), começando por xn = ȳn . rnn Com este processo, substituı́mos a inversão de A pela transposição de Q e pela inversão da matriz triangular superior R, que são operações numericamente mais robustas. Exemplo 6 : Resolução do problema de mı́nimos quadrados O problema de mı́nimos quadrados consiste no cálculo de vector θ ∈ IRm que minimiza kY − Xθk2 = (Y − Xθ)T (Y − Xθ) Tópicos de Algebra Linear 10 com Y ∈ IRn , X ∈ IRn×m , n ≥ m e car(X) = m. Efectuando a seguinte decomposição QR de X R X = Q − − −− 0(n−m)×m Q ∈ IRn×n , R ∈ IRm×m e, uma vez que Q é uma matriz ortonormal quadrada e que consequentemente QQT = In , teremos kY − Xθk2 = (Y − Xθ)T (Y − Xθ) = (Y − Xθ)T QQT (Y − Xθ) = ° £ T ¤T £ T ¤ ° Q (Y − Xθ) Q (Y − Xθ) = °QT Y − QT Xθ)°2 = °· °· ¸ · ¸ ° ¸ · ¸ ° ° ° ° Ȳ1 ° Ȳ1 R R T ° ° ° ° ° Ȳ2 − Q Q 0(n−m)×m θ° = ° Ȳ2 − 0(n−m)×m θ° = 2 2 °· ¸° h i · Ȳ − Rθ ¸ ° Ȳ1 − Rθ ° 1 ° ° = (Ȳ1 − Rθ)T Y¯2 T = ° ° Y¯2 Y¯2 2 ° ° ° ° T = (Ȳ1 − Rθ)T (Ȳ1 − Rθ) + Y¯2 Y¯2 = °Ȳ1 − Rθ°2 + °Y¯2 °2 em que · ¸ Ȳ1 = QT Y, Ȳ2 Ȳ1 ∈ IRm , Ȳ2 ∈ IRn−m . A solução do problema de mı́nimos quadrados será, então, a solução do sistema de equações Rθ̂ = Ȳ1 idêntico ao do exemplo anterior. Como, para θ = θ̂, Ȳ1 − Rθ = 0m , então min kY − Xθk2 = kY2 k2 . Existem várias formas de obter uma decomposição QR sendo, talvez, as transformações de Householder e a ortogonalização de Gram-Schimdt, os métodos mais utilizados. Além de im(A), também se define o subespaço Núcleo de A (kernel ou null space em inglês) designado por ker(A) e que é definido por ker(A) = {x : Ax = 0n } , ou seja, o subespaço de IRm que é transformado na origem (de IRn ) pela matriz A ∈ IRn×m . Como este subespaço é formado por todos os vectores perpendiculares às linhas de A, podemos afirmar que ker(A)⊥im(AT ), sendo, por isso, ker(A) ∩ im(AT ) = 0m×m . Por outro lado, Tópicos de Algebra Linear 11 como a dimensão do núcleo duma matriz é igual ao seu número de colunas (m) menos a sua £ ¤ caracterı́stica, então, dim [ker(A)] + dim im(AT ) = m e, consequentemente, ker(A) ⊕ im(AT ) = Rm ⇒ ker(A) = im(AT )⊥ . Identicamente, o núcleo de AT , designado por ker(AT ), é o complemento ortogonal de im(A). 4 Decomposição em Valores Singulares Na decomposição QR é explicitada uma base ortonormal para a imagem duma matriz A. Nesta secção iremos ver a decomposição em valores singulares onde, além duma base ortonormal para este subespaço, também são explicitadas bases ortonormais para a imagem de AT e para os núcleos de A e AT . Antes de introduzirmos esta decomposição vamos recordar a diagonalização de matrizes simétricas. Lema 1 Se B ∈ IRn×n for uma matriz simétrica, isto é, se B T = B, então pode ser decomposta na forma B = UB ΛB UBT em que ΛB = λ1 0 0 λ2 .. .. . . 0 0 ··· ··· ... 0 0 .. . (1) · · · λn UB UBT = UBT UB = In (2) ou seja, ΛB é uma matriz diagonal e UB uma matriz ortonormal. Demonstração: Como B é simétrica os seus valores próprios são reais e é diagonalizável. Para simplificar, vamos admitir todos os valores próprios de B são distintos. Nestas condições podemos escrever B = T ΛB T −1 Tópicos de Algebra Linear 12 em que ΛB está definida em (1) e T é uma matriz cujas colunas são os vectores próprios de B. Definindo UB = T ⇔ UB−1 = det(T )T −1 det(T ) podemos escrever B = T ΛB T −1 = UB ΛB UB−1 . (3) Como B = B T podemos concluir que B = UB ΛB UB−1 = UB−T ΛB UBT ⇒ UB−1 = UBT ⇔ UB UBT = UBT UB = In . Se B tiver valores próprios repetidos as suas multiplicidades algébrica e geométrica são iguais, continuando a expressão(3) a ser válida para estes casos. 2 Estamos agora em condições de apresentar a decomposição em valores singulares. Teorema 1 : Decomposição em valores singulares (svd) Se A ∈ IRn×m tiver caracterı́stica r ≤ min(n, m) então existem duas matrizes ortonormais U ∈ IRn×n e V ∈ IRm×m tal que · ¸ S+ 0r×(m−r) A = U VT 0(n−r)×r 0(n−r)×(m−r) σ1 0 · · · 0 0 σ2 · · · 0 r×r S+ = .. .. . . .. ∈ IR . . . . 0 0 · · · σr (4) (5) com σ1 ≥ σ2 ≥ · · · ≥ σr > 0. Demonstração: Como a matriz AT A ∈ Rm×m é simétrica e, pelo menos, semidefinida positiva, pode ser decomposta na forma AT A = V ΛA V T λ1 0 0 λ2 ΛA = .. .. . . 0 0 V V T = V T V = Im ··· ··· .. . 0 0 .. . · · · λm λi ≥ 0, i = 1, . . . , m. Tópicos de Algebra Linear 13 Sendo car(A) = r ≤ m, podemos definir λ1 ≥ λ2 ≥ · · · > λr > 0, λr+1 = λr+2 = · · · = λm = √ 0 e σi = λi , i = 1, . . . , m. As colunas de V são vectores próprios de AT A, isto é, V = £ v1 v2 · · · vm AT Avi = λi vi = σi2 vi , ¤ i = 1, . . . , m. Se Vr ∈ IRm×r for a matriz cujas colunas são os vectores próprios associados aos valores próprios não nulos e V̄r ∈ IRm×(m−r) a matriz com as restantes colunas de V , ou seja, Vr = V̄r = £ £ v1 v2 · · · vr ¤ vr+1 vr+2 · · · vm (6) ¤ , (7) então ¤ AT Av1 AT Av2 · · · AT Avr (8) σ12 0 · · · 0 2 £ 2 ¤ ¤ 0 σ2 · · · 0 £ 2 σ1 v1 σ22 v2 · · · σr2 vr = .. = .. . . .. v1 v2 · · · vr = S+ Vr . . . . 2 0 0 · · · σm £ ¤ £ ¤ = AT A vr+1 vr+2 · · · vm = AT Avr+1 AT Avr+2 · · · AT Avm = £ ¤ 0m 0m · · · 0m = 0m×(m−r) (9) = AT AVr = AT A AT AV̄r £ v1 v2 · · · vr ¤ = £ onde S+ é a matriz definida em (5). Seja Ur = AVr S+−1 ∈ IRn×r . (10) Pré-multiplicando Ur pelo seu transposto UrT Ur = (AVr S+−1 )T (AVr S+−1 ) = (S+−1 VrT AT )(AVr S+−1 ) = S+−1 VrT (AT AVr )S+−1 = S+−1 VrT (Vr S+2 )S+−1 = S+−1 (VrT Vr )(S+2 S+−1 ) = S+−1 S+ = Ir verificamos que Ur é uma matriz ortonormal cujas colunas geram um subespaço de dimensão r em IRn . Se Ūr for uma matriz ortonormal cuja imagem é o complemento ortogonal da imagem de Ur (Ūr = Ur⊥ ), então 0(n−r)×r = ŪrT Ur = ŪrT AVr S+−1 ⇒ ŪrT A = 0(n−r)×m , Tópicos de Algebra Linear 14 isto é, a imagem de Ūr também é o complemento ortogonal de A, o que nos permite concluir que im(Ur ) = im(A) e que, consequentemente, as colunas de Ur são uma base ortonormal de im(A). Definindo U = £ Ur | Ūr ¤ (11) podemos calcular · T ¸ · T ¸ · T ¸ £ ¤ ¤ Ur Ur A £ Ur AVr UrT AV̄r T Vr | V̄r = U AV = A Vr | V̄r = . (12) ŪrT A ŪrT ŪrT AVr ŪrT AV¯r Como UrT Ur = Ir , então, substituindo, nesta equação, Ur pelo seu valor definido em (10), teremos UrT AVr S+−1 = Ir ⇒ UrT AVr = S+ . Por outro lado, fazendo a mesma substituição no bloco (1, 2) da última matriz na expressão (12), podemos escrever UrT AV̄r = (AVr S+−1 )T AV̄r = S+−1 VrT (AT AV̄r ) = 0(n−r)×(m−r) pois, de (9), AT AV̄r = 0m×(m−r) . Finalmente, como as colunas de Ūr geram o complemento ortogonal do subespaço gerado pelas colunas de A, ŪrT AVr = 0(n−r)×r ŪrT AV¯r = 0(n−r)×(m−r) . Deste modo, T U AV = · S+ 0r×(m−r) ¸ 0(n−r)×r) 0(n−r)×(m−r) . Como U U T = In e V V T = Im , pré-multiplicando e pós-multiplicando U T AV por U e V T , respectivamente, obtemos · ¸ S+ 0r×(m−r) T T U (U AV )V = U V T = (U U T )A(V V T ) = A 0(n−r)×r) 0(n−r)×(m−r) ficando assim concluı́da a demonstração. 2 Normalmente define-se · ¸ S+ 0r×(m−r) S= ∈ IRn×m 0(n−r)×r 0(n−r)×(m−r) Tópicos de Algebra Linear 15 e exprime-se a decomposição em valores singulares na forma A = U SV T . Se n > m, ou seja, se σ1 0 · · · 0 σ2 · · · . .. . . . . . . S = 0 0 ··· 0 0 ··· . .. .. .. . . 0 0 ··· e se n < m, σ1 0 · · · 0 σ2 · · · S = .. .. . . . . . 0 0 ··· A tiver mais colunas do que linhas, então 0 0 .. . σm 0 .. . 0 0 0 .. . σn 0 ··· 0 ··· .. .. . . 0 ··· 0 0 .. . 0 Os elementos da diagonal principal de S estão ordenados por ordem decrescente, isto é, σ1 ≥ σ2 ≥ · · · ≥ σp , com p = min(n, m), e são designados por valores singulares de A. Na demonstração da decomposição em valores singulares vimos que estes são as raı́zes quadradas positivas de valores próprios de AT A. É fácil demonstrar que os valores singulares são as raı́zes quadradas positivas dos valores próprios de AT A quando n ≥ m e dos valores próprios de AAT quando n ≤ m. S+ , definida em (5), é a matriz dos valores singulares não nulos. Como car(S) = car(S+ ), então car(A) = car(S+ ), ou seja, a caracterı́stica duma matriz é igual ao número de valores singulares não nulos pois, U e V são matrizes não singulares1 . Vimos, também, que V é uma matriz (ortonormal) cujas colunas são os vectores próprios de AT A. pode-se provar, identicamente, que U é uma matriz cujas colunas são os vectores próprios de AAT . As colunas de U e V também são designadas por vectores singulares de A. As de U , são os vectores singulares á esquerda e as de V , os vectores singulares à direita. Utilizando as decomposições de V e U definidas em (6)-(7) e (11), respectivamente, podemos rescrever a decomposição em valores singulares na forma ¸ · · ¸· T ¸ £ ¤ VrT £ ¤ S+ 0r×(m−r) Vr Ur | Ūr = = Ur S+ | 0n×(m−r) A = V̄rT V̄rT 0(n−r)×r 0(n−r)×(m−r) = Ur S+ VrT . 1 Recordemos que matrizes não singulares são matrizes de caracterı́stica completa e que se G for uma matriz de caracterı́stica completa então a caracterı́stica de F = GH é igual à caracterı́stica de H. Tópicos de Algebra Linear 16 Chegamos assim à forma reduzida da decomposição em valores singulares. • Se, na transformação IRm → IRn z = Ax, definirmos x̄ = S+ VrT x, teremos z = Ax = Ur x̄. Com car(A) = car(Ur ), A e Ur têm a mesma imagem e , consequentemente, as colunas de Ur são uma base ortonormal do subespaço gerado pelas colunas de A (im(A)). Como AT = Vr S+ UrT , concluı́mos, identicamente, que im(Vr ) = im(AT ) e que as colunas de Vr são uma base ortnormal para o subespaço gerado pelas linhas de A. • Dado que as colunas de V̄r são perpendiculares às de Vr , AV¯r = Ur S+ VrT V̄r = 0n×(m−r) , o que nos permite afirmar que as colunas de V̄r pertencem ao núcleo de A (ker(A)). Como car(V̄r )=car (ker(A)) = m − r, então im(V̄r ) = ker(A), sendo as colunas de V̄r uma base ortonormal do núcleo de A. Analogamente, as colunas de Ūr são uma base ortonormal do núcleo de AT . Resumindo, im(Ur ) = im(A) im(Vr ) = im(AT ) im(V̄r ) = ker(A) im(Ūr ) = ker(AT ). 5 Norma Quadrática de Matrizes Os vectores dum espaço IRn são habitualmente definidos pela combinação linear dos vectores 0 0 . . . 0 ∈ IRn i = 1, . . . , n, ei = 1 igésima linha 0 . .. 0 Tópicos de Algebra Linear 17 que formam a base canónica de IRn . Seja U = £ u1 u2 · · · un ¤ ∈ IRn uma matriz ortonormal. Como £ In = e1 e2 · · · en ¤ = UT U = UT £ u1 u2 · · · un ¤ = £ U T u1 U T u2 · · · U T un ¤ podemos concluir que U T ui = ei . Isto significa que a transformação U T x roda os eixos da base ortonormal {u1 , . . . , un } para os eixos da base canónica {e1 , . . . , en }. Por outras palavras, a transformação U T x é uma rotação que alinha os eixos u1 , . . . , un com e1 , . . . , en . Assim, chamaremos alinhador à matriz U T . Exemplo 7 : Alinhador no espaço IR2 Se U= £ u1 u2 ¤ for uma matriz ortogonal em IR2 então · T ¸ · T ¸ · ¸ u1 u1 u1 1 T U u1 = u1 = = e1 = T T u2 u2 u1 0 · T ¸ · T 2 ¸ · ¸ u1 u1 u 0 T U u2 = u2 = = e2 = T T u2 u1 u2 1 pois, sendo U uma matriz ortonormal, as suas colunas u1 e u2 têm módulo unitário e são mutuamente ortogonais. Podemos, então, concluir, que esta transformação roda todos os vectores de um ângulo θ (ângulo que u1 faz com e1 (ver figura 5). Seja agora x = α1 u1 + α2 u2 O vector z = U T x será · T T T z = U (α1 u1 + α2 u2 ) = α1 U u1 + α2 U u2 = α1 e1 + α2 e2 = α1 α2 ¸ ou seja, z é um vector cujas coordenadas são as de x no referencial definido pelos vectores u1 e u2 (ver figura 5). Verificamos, assim, que os eixos de u1 e u2 foram alinhados pelos de e1 e e2 e que, consequentemente, U T é o alinhador do referencial constituı́do pelos vectores u1 e u2 . Tópicos de Algebra Linear 18 UT α1 u1 1 u2 1 φ u1 x θ 1 −1 e 2 = U T u2 e1 = U T u1 α1 e1 1 φ −1 α2 e2 α 2 u2 −1 −1 UT x Figura 5: U T é o alinhador de {u1 , u2 } no espaço IR2 Como U = £ u1 u2 · · · un ¤ = U In = U £ e1 e2 · · · en ¤ , então U e i = ui , i = 1, . . . , n. Vemos, deste modo, que a transformação y = U x roda os eixos da base canónica {e1 , . . . , en } para os da base ortonormal {u1 , . . . , un }. Como os eixos da base canónica são pendurados nos da base ortonormal, chamaremos cabide a U . Exemplo 8 : Cabide no espaço IR2 Dado que a matriz U , definida no exemplo anterior, é ortonormal, U −1 = U T . Consequentemente z = U T x e x = U z são transformações inversas. Se a transformação definida por U T roda as colunas u1 e u2 de U para e1 e e2 , respectivamente, então a que é definida por U roda e1 e e2 para u1 e u2 . O vector ¸ · α1 z = α2 é transformado no vector x = Uz = £ u1 u2 ¤ · α1 α2 ¸ = α1 u1 + α2 u2 . Podemos, então, afirmar que as coordenadas α1 e α2 de z foram penduradas em u1 e u2 pelo cabide U . Tópicos de Algebra Linear 19 U e2 α1 u1 1 u2 = U e 2 1 e1 −1 α1 e1 1 φ −1 α2 e2 z −1 u 1 = U e1 φ θ 1 Uz α2 u2 −1 Figura 6: U é o cabide em {u1 , u2 } no espaço IR2 Seja D ∈ IRn×n d1 0 0 d2 D = .. .. . . 0 0 uma matriz diagonal, isto é, ··· 0 ··· 0 . . .. . .. · · · dn Se multiplicarmos D, á direita, pelo vector α1 α2 x = .. . αn obtemos xd = d1 α1 d2 α2 .. . dn αn onde as coordenadas nos eixos de e1 , e2 , . . . , en estão multiplicadas pelos elementos d1 , d2 , . . . , dn , respectivamente, de D. podemos afirmar, então, que as coordenadas de x foram deformadas pelos elementos de D e designaremos D por deformador . Exemplo 9 : Deformador no espaço IR2 Seja D = · 1 0 0 0, 5 ¸ Tópicos de Algebra Linear 20 uma matriz diagonal em IR2×2 e C2 (1) = {x : kxk2 = 1}, isto é, a circunferência de raio unitário. A transformação z = Dx transforma esta circunferência numa elipse E2 (1, 0.5) com semi-eixos de comprimento 1 e 0, 5. Vemos, assim, que a circunferência C2 foi deformada pelo deformador D. D 1 e2 C2 (1) e2 e1 −1 1 0, 5 e1 −1 1 −0, 5 −1 Figura 7: D é um deformador no espaço IR2 Como, através da decomposição em valores singulares, podemos decompor uma matriz na forma A = Ur S+ VrT onde Ur e Vr são matrizes ortonormais e S+ é uma matriz diagonal, podemos ver a transformação z = Ax = Ur S+ VrT x como a sequência das seguintes operações: • Alinhamento dos eixos de v1 , v2 , . . . , vr com os eixos de e1 , e2 , . . . , er da base canónica efectuado pelo alinhador VrT • Deformação da novas coordenadas de x pelo deformador S+ . • Suspensão das novas coordenadas deformadas de x no cabide Ur . Por outras palavras, os eixos v1 , v2 , . . . , vr são deformados de σ1 , σ2 , . . . , σr e rodados para u1 , u 2 , . . . , u r . Tópicos de Algebra Linear 21 Exemplo 10 : Transformação de uma elipse de IR2 para IR2 por uma matriz A matriz · A = 1, 44 0, 92 0, 08 1, 44 ¸ com a seguinte decomposição em valores singulares · ¸· ¸· ¸ 0, 8 −0, 6 2 0 0, 6 0, 8 A = 0, 6 0, 8 0 1 −0, 8 0, 6 transforma a elipse com os eixos alinhados com · ¸ · ¸ 0.6 0.8 v1 = e v2 = −0.8 0.6 de comprimentos 4 e 2, respectivamente, numa outra elipse com os eixos alinhados com · ¸ · ¸ 0.8 −0.6 u1 = e u2 = 0.6 0.8 e comprimentos 8 e 2. Exemplo 11 : Transformação da hiperesfera de raio unitário A hiperesfera de ordem m de raio unitário é transformada pela matriz A ∈ IRn×m com decomposição em valores singulares σ1 0 £ ¤ 0 σ2 A = u1 u2 · · · ur .. .. . . 0 0 ··· ··· ... 0 0 .. . · · · σr v1T v2T .. . vrT numa elipsoide de ordem r, com semi-eixos de comprimentos σ1 , σ2 , . . . , σr alinhados com os vectores u1 , u2 , . . . , ur . A norma quadrática duma matriz A ∈ IRn×m é designada por kAk2 e definida por kAk2 = sup kAxk2 kxk2 =1 isto é, é o módulo do maior vector z = Ax quando x tem módulo unitário. Como a hiperesfera de ordem m de raio unitário é transformada por A numa elipsóide com semi-eixos de comprimentos iguais aos seus valores singulares, então o maior vector z = Ax desta transformação tem o módulo igual ao do maior valor singular de A e, consequentemente, kAk2 = σ1 Tópicos de Algebra Linear 22 A 1 σ 3 u3 σ 1 u1 1 1 σ2 u2 Figura 8: Transformação da esfera unitária numa elipsóide em IR3 por uma matriz A ∈ IR3×3 com vectores singulares à esquerda u1 , u2 e u3 e valores singulares σ1 , σ2 e σ3 . Exemplo 12 : Norma quadrática duma matriz 2 por 2 Como a matriz ¸ · 1, 44 0, 92 A = 0, 08 1, 44 com a seguinte decomposição em valores singulares · ¸· ¸· ¸ 0, 8 −0, 6 2 0 0, 6 0, 8 A = 0, 6 0, 8 0 1 −0, 8 0, 6 transforma a circunferência unitária numa elipse com semi-eixos de comprimentos 2 e 1, então kAk2 = 2 = maior valor singular de A 6 Aproximação de uma Matriz por Outra de Caracterı́stica Inferior Seja A uma matriz com caracterı́stica r pertencente a IRn×m em que n > m. A sua decomposição em valores singulares A = U SV T Tópicos de Algebra Linear 23 A 1 σ2 u2 = u2 1 −1 σ1 u1 = 2u1 2 = kAk2 −1 Figura 9: A norma da matriz A é o comprimento do maior semi-eixo da elipse em que é transformada a circunferência de raio unitário permite-nos chegar à decomposição diática, dada por A = m X σi ui viT i=1 Para x = αj vj , um vector na direcção de vj , teremos Ax = m X i=1 σi ui viT x = m X σi αj ui viT vj = σj αj uj vjT vj = σj αj uj i=1 pois vj tem módulo unitário e é perpendicular a vi para i 6= j. Esta expressão evidencia o facto mencionado na secção anterior, de que os pontos no eixo de vj são reescalados (deformados) de um factor σj e rodados para o eixo de uj . Consideremos, agora, um vector x com componentes em todos os eixos vi , i = 1, . . . , m, ou seja, x = α1 v1 + α2 v2 + · · · + αr vr + αr+1 vr+1 + · · · + αm vm . Se car(A) = r e r < m, então σr+1 = σr+2 = · · · = σm = 0, significando isto que as componentes αr+1 vr+1 , αr+2 vr+2 , . . . , αm vm estão no núcleo de A sendo, por isso, eliminadas na transformação Ax. Teremos, assim, Ax = σ1 α1 u1 + σ2 α2 u2 + · · · + σr αr ur . Tópicos de Algebra Linear 24 Se os valores singulares σk+1 , . . . , σr forem muito pequenos, podemos fazer Ax ≈ α1 σ1 u1 + σ2 α2 u2 + · · · + σk αk uk = Ak x, em que Ak = £ u1 u2 ¤ · · · uk σ1 0 0 σ2 .. .. . . 0 0 ··· ··· .. . 0 0 .. . · · · σk v1T v2T .. . . vkT O erro desta aproximação é Ax − Ak x = (A − Ak ) x = σk+1 αk+1 uk+1 + σk+2 αk+1 uk+2 + · · · + αr σr ur , sendo q kAx − Ak xk2 = 2 2 2 2 σk+1 αk+1 + σk+2 αk+2 + · · · + σr2 αr2 pois uk+1 , uk+2 , . . . , ur são vectores de norma unitária mutuamente ortogonais. Como (Ax − Ak x)T Ak x = (σk+1 αk+1 uk+1 + · · · + αr σr ur )T (σ1 α1 u1 + · · · + αk σk uk ) = = σk+1 αk+1 uTk+1 (σ1 α1 u1 + · · · + αk σk uk ) + · · · + +σr αr uTr (σ1 α1 u1 + · · · + αk σk uk ) = = σk+1 αk+1 σ1 α1 uTk+1 u1 + · · · + σk+1 αk+1 σk αk uTk+1 uk + · · · + +σr αr σ1 α1 uTr u1 + · · · + σr αr σk αk uTr uk = 0, Ax − Ak x e Ak x são ortogonais. Isto significa que Ak x é a projecção ortogonal de Ax no subespaço gerado por u1 , u2 , . . . , uk , sendo, por isso, a sua melhor aproximação neste subespaço e , consequentemente, im(Ak ) é a melhor aproximação de dimensão k do subespaço im(A). Se z ∈ IRn for decomposto na forma z = β1 u1 + β2 u2 + · · · + βn un , podemos concluir , de forma semelhante, que ATk z é a melhor aproximação de AT z no subespaço gerado por v1 , v2 , . . . vk sendo im(ATk ) a melhor aproximação de dimensão k de im(AT ) Como im(Ak ) e im(ATk ) são as melhores aproximações de im(A) e im(AT ), respectivamente, podemos afirmar que Ak é a melhor aproximação com caracterı́stica k de A. Tópicos de Algebra Linear 7 25 Projecções Ortogonais de Subespaços Sejam x e y dois vectores em IRn . A projecção ortogonal de y em x, que designaremos por y\x é um vector na direcção de x com módulo kyk2 cos φ em que φ é o ângulo entre y e x. Sendo o produto interno entre x e y dado por y 1 y − y\x x y\x φ ex 1 −1 −1 Figura 10: Projecção ortogonal de y em x. xT y = kxk2 kyk2 cos φ, podemos exprimir y\x na forma y\x = ex xT y kxk2 em que ex é um vector unitário na direcção de x, ou seja, ex = x . kxk2 Substituindo ex pelo seu valor em (13), teremos y\x = x xT y T = xkxk−2 2 x y. kxk22 Como kxk22 = xT x podemos, finalmente, escrever, ¡ ¢−1 T y\x = x xT x x y. (13) Tópicos de Algebra Linear 26 Como y − y\x é perpendicular a x, então y\x é a melhor aproximação na direcção de x. Notemos, ainda, que a projecção y\x é uma combinação linear de x, isto é, y\x = xθ̂ em que θ̂ = ¡ xT x ¢−1 xT y. Vemos, assim, que θ̂ é o estimador de mı́nimos quadrados θ̂ = min ky − xθk2 . θ Se x for um vector na direcção de um dos vectores da base canónica, isto é, se x = Kx ei , Kx ∈ IR, então £ ¤−1 ¡ ¢−1 y\x = (Kx ei ) (Kx ei )T (Kx ei ) (Kx ei )T y = Kx ei Kx2 eTi ei Kx eTi y = ¡ ¢−1 T = Kx (Kx )−2 Kx ei eTi ei ei y = ei eTi y = 0 0 ··· 0 ··· 0 y1 0 .. .. .. .. .. .. .. .. . . . . . . . . i 0 0 ··· 1 · · · 0 yi yi = = . . . = yi ei .. .. .. .. .. .. .. ... . . . . yn 0 0 ··· 0 0 0 ··· i Como esta expressão é independente de Kx a projecção y\x , depende unicamente da direcção de x, ou seja, y\z = y\x para qualquer z na direcção de x. Vemos, deste modo, que projectar y em x é o mesmo que projectar y no subespaço gerado por x. Vamos agora ver o que acontece quando x é um vector com direcção arbitrária. Comecemos por definir uma base ortonormal {u1 , . . . , un } em que x = Kx u1 . A seguir podemos efectuar as seguintes operações • Alinhar u1 com e1 . • Projectar y em e1 no novo referencial. • Pendurar e1 em u1 . Tópicos de Algebra Linear 27 y y2 1 Kx e1 y1 e1 e1 −1 y1 1 −1 Figura 11: Projecção ortogonal de y no eixo de e1 . y u2 e 2 y x T U y U T u2 u1 e1 u2 e2 UT x U u1 U T y\U T x u1 e1 x y\x Figura 12: Projecção ortogonal de y em x: 1 - O plano é rodado para alinhar o eixo de x com o de e1 . 2 - y rodado é projectado no eixo de e1 . 3 - O plano é rodado para a posição inicial. Estas operações traduzem-se na seguinte expressão y\x = P y em que P = £ u1 u 2 ¤ · · · un 1 0 .. . 0 ··· 0 ··· .. .. . . 0 0 ··· 0 0 .. . 0 uT1 uT2 .. . = u1 uT1 (14) uTn Pode-se provar que P = x(xT x)−1 xT . Como (14) é a decomposição em valores singulares de P , concluı́mos que esta matriz tem caracterı́stica 1. Notemos que P é uma matriz simétrica (P T = P ) e idempotente (P 2 = P ). Tópicos de Algebra Linear 28 Suponhamos, agora, que pretendemos projectar y no plano gerado pelo par de vectores linearmente independentes x1 e x2 . Seja {u1 , u2 } uma base ortonormal desse plano incluı́da na base ortonormal {u1 , u2 , . . . , un }. Uma vez mais, a projecção pode ser feita através das seguintes operações: • Alinhar u1 e u2 com e1 e e2 , respectivamente. • Projectar y no novo referencial no plano gerado e1 e e2 . • Pendurar e1 e e2 em u1 e u2 , respectivamente. tal como anteriormente, estas projecções traduzem-se na expressão y\X = P y em que P = eX= £ £ ¤ · · · un u1 u 2 u3 0 ··· 0 0 ··· 0 0 ··· 0 .. .. .. . . . 0 0 0 ··· 0 1 0 0 .. . 0 1 0 .. . ¤ x1 x2 . Pode-se provar que uT1 uT2 uT3 .. . = u1 uT1 + u2 uT2 (15) uTn P = X(X T X)−1 X T sendo (15) a decomposição em valores singulares de P . Podemos alargar este conceito de projecção de um vector num plano, ao da projecção dum subespaço noutro subespaço. Neste contexto, a projecção da imagem de Y na imagem de X em que Y = X = £ £ y1 · · · y` ¤ x1 · · · xm ∈ IRn×` , n > ` ¤ ∈ IRn×m , n > m é a imagem da matriz Y \X = P Y (16) em que P = £ Ur Ūr ¤ · Ir 0r×(m−r) 0(n−r)×r 0(n−r)×(m−r) ¸· UrT ŪrT ¸ = Ur UrT (17) Tópicos de Algebra Linear 29 Se as colunas x1 , . . . , xm de X forem linearmente independentes, então r = m e P = X(X T X)−1 X T pois X T X é uma matriz não singular. Nestas condições, a projecção de Y em X é a combinação linear das colunas de X Y \X = X θ̂, em que θ̂ tem uma só solução, dada por ¡ ¢−1 T θ̂ = X T X X Y, (18) que podemos reconhecer como sendo o estimador de mı́nimos quadrados θ̂ = min kY − Xθk2 . θ (19) A projecção Y \X existe sempre mesmo quando as colunas de X não são linearmente independentes. No entanto, (19) deixa de ter uma única solução pois X T X é singular. Como obter uma solução θ nestas condições? Se X = Ur S+ VrT (20) for a forma reduzida da decomposição em valores singulares de X, e se em (18) substituirmos ¡ T ¢−1 T X X X por X † = Vr S+−1 UrT , (21) obtemos a estimador θ̂ = X † Y (22) que adiante provaremos ser o menor estimador de mı́nimos quadrados de θ. Pode-se provar que X † é a única matriz que obedece às seguintes condições (condições de Moore-Penrose): 1. XX † X = X 2. X † XX † = X † ¢T ¡ 3. XX † = X † X Tópicos de Algebra Linear 30 ¡ ¢T 4. X † X = XX † X † é designada como o inverso generalizado ou pseudo-inverso de X. Se car(X) = m, então X † = (X T X)−1 X T e X † X = Im . Se car(X) = n, então teremos X † = X T (XX T )−1 e XX † = In . Vamos agora provar que θ̂ definido em (22) é o menor estimador de mı́nimos quadrados. Lema 2 Se X ∈ IRn×m onde n > m for uma matriz com caracterı́stica r < m e y ∈ IRn com n > `, então ¡ ¢ θ̄(Ψ) = X † y + Im − X † X Ψ, ∀Ψ ∈ IRm é a solução geral do problema de mı́nimos quadrados min ky − Xθk2 . θ ∈ IRm×` (23) e θ̂ = θ̄(0m×` ) = X † y é a única solução de norma mı́nima, isto é, é a única solução tal que ° ° kθ̂k2 ≤ °θ̄(Ψ)°2 , ∀Ψ ∈ IRm . Demonstração: Todas soluções de (23) devem ser coeficientes de todas as combinações lineares de X que © ª geram y\X , isto é, o conjunto Θ = θ̄ : X θ̄ = y\X . Utilizando a forma reduzida da decomposição em valores singulares de X em (20) e as definições de P e de X † em (17) e (21), respectivamente, X θ̂ = XX † y = (Ur S+ VrT )(Vr S+−1 UrT )y = Ur S+ (VrT Vr )S+−1 UrT y = = Ur (S+ S+−1 )UrT y = Ur UrT y = P y = y\X . Vemos, deste modo, que θ̂ = X † y ∈ Θ sendo, por isso, uma solução de (23). As outras ³ ´ soluções são do tipo θ̂ + Υ tal que X θ̂ + Υ = y\X . Como X θ̂ = y\X , então XΥ = 0n×` . Isto significa que Υ pode ser qualquer vector no núcleo de X, ker(X). Υ pode então ser gerado através da projecção ortogonal de um vector qualquer Ψ ∈ IRm em ker(X). Vimos, anteriormente, que ker(X) é o complemento ortogonal de im(X T ) em que im(X T ) é Tópicos de Algebra Linear 31 o subespaço gerado pelas linhas de X. Se Vr for uma base ortonormal de im(X T ), então, de (16) e de (17), a projecção de Ψ em im(X T ) é dada por Ψ\X T = Vr VrT Ψ, sendo Υ = Ψ\(X T )⊥ = Ψ − Ψ\X T a projecção ortogonal de Ψ em (X T )⊥ . Se Vr for a base calculada na decomposição em valores singulares de X, então podemos gerar Υ através de ¡ ¢ ¡ ¢ Υ = Ψ − Ψ\X T = Ψ − Vr VrT Ψ = Im − Vr VrT Ψ = Im − X † X Ψ, ∀Ψ ∈ IRm . pois, X † X = Vr S+−1 UrT Ur S+ VrT = Vr VrT . A solução geral de (23) será ¡ ¢ θ̄(Ψ) = θ̂ + Im − X † X Ψ, ∀Ψ ∈ IRm em que Ψ é qualquer matriz de IRm . Como θ̂ = |{z} X † y = Vr S+−1 UrT y = Vr ȳ ∈ im(X T ) | {z } −1 T Vr S+ Ur ȳ e ¡ ¢ Υ = Im − X † X Ψ ∈ ker(X), então θ̂ e Υ são perpendiculares pois ker(X) é o complemento ortogonal de im(X T ). Teremos, assim, ° ° ° ° °θ̄(Ψ)°2 = kθ̂k22 + kΥk2 = kθ̂k22 + °(Im − X † X)Ψ°2 2 2 2 e, finalmente, ° ° ° ° kθ̂k2 = °X † y °2 ≤ °θ̄(Ψ)°2 onde só se verifica igualdade para Ψ = 0m , ficando assim concluı́da a demonstração. 2 Tópicos de Algebra Linear 32 O estimador de mı́nimos quadrados de norma mı́nima pode ser expresso através de θ̂ = X † Y = Vr S+−1 Ur Y = r X uT v i Y i i=1 σi Esta expressão mostra que, se o menor valor singular σr for muito menor que os outros, pequenas perturbações na matriz que provoquem pequenas alterações em ur ou vr causam, seguramente, perturbações muito significativas em θ̂. Se, no entanto, os valores singulares não forem muito diferentes uns dos outros, as perturbações nos diferentes vectores singulares tendem-se a compensar umas às outras, não fazendo variar significativamente θ̂. Vemos, assim, que a sensibilidade de θ̂ depende, fundamentalmente, da diferença entre os valores singulares de X. O número de condição de X definido por κ(X) = kXk2 kX † k2 = σ1 σr é utilizado como medida de sensibilidade de θ. Por definição é superior ou igual a 1. Se for muito grande, então X é uma matriz mal condicionada. Se se mantiver pequeno X é bem condicionada. Uma matriz ortonormal tem número de condição igual a 1 e, por isso, é perfeitamente condicionada. 8 Projecções Oblı́quas de Subespaços Seja y ∈ IRn dado por y = a1 x1 + a2 x2 onde a1 e a2 ∈ IR, x1 e x2 ∈ IRn . A projecção oblı́qua de y em x1 segundo x2 , designada por y\xx21 , é a1 x1 . Se y não estiver no plano gerado por x1 e x2 , a projecção oblı́qua de y em x1 segundo x2 é a projecção oblı́qua de y\h y\h x1 x2 i = x1 θ̂1 + x2 θ̂2 onde ¸ · £ ¤† θ̂1 x1 x2 y = θ̂2 x1 x2 i em x1 segundo x2 . Como Tópicos de Algebra Linear 33 y y\xx12 = a2 x1 x2 x1 y\xx21 = a1 x1 Figura 13: y\xx21 é a projecção oblı́qua de y em x1 segundo a direcção de x2 . y\xx12 é a projecção oblı́qua de y em x2 segundo a direcção de x1 . então y\xx21 = x1 θ̂1 . Dum modo geral, dizemos que a projecção de Y ∈ IRn×` em X1 ∈ IRn×m1 segundo X2 ∈ IRn×m2 com n > ` e n > m1 + m2 é 2 Y \X X1 = X1 θ̂1 onde · ¸ £ ¤† θ̂1 X1 X2 Y. = θ̂2 9 Projecções nos Subespaços gerados pelas linhas duma matriz Quando o número de colunas duma matriz é superior ao das linhas (m > n) as projecções são no subespaço gerado pelas linhas. Como, transpondo uma matriz, trocamos as linhas pelas colunas, tudo o que se disse sobre projecções nos subespaços gerados pelas colunas continua válido desde que todas as matrizes sejam transpostas. Se, no fim de todas as projecções, voltarmos a transpor as matrizes, obtemos ¡ ¢T Y /X = Y T \X T = Y X † X = θ̂X = Y Vr VrT em que θ̂ é o estimador de mı́nimos quadrados de menor norma dado por θ̂ = Y X † . Se car(X) = n, então X † = X T (XX T )−1 e Y /X = Y X T (XX T )−1 X Tópicos de Algebra Linear 34 A projecção oblı́qua de Y em X1 segundo X2 é definida como ³ ´T T T X2 2 = Y \ = θ̂1 X1 Y /X X1 XT 1 onde £ θ̂2 θ̂2 10 ¤ · = Y X1 X2 ¸† Produto de Kronecker e Vectorização de Matrizes Em controlo, especialmente nas áreas de estimação e redução de ordem do modelo, é frequente ter que se resolver equações de Lyapunov. Estas, são equações matriciais, do tipo ΠA1 + A2 Π + A3 ΠA4 + Q = 0n×n . (24) Embora sejam lineares na incógnita Π ∈ IRn×n , não podem ser resolvidas de uma forma directa porque, nuns termos a incógnita aparece multiplicada à direita , noutros é multiplicada à esquerda, podendo ainda ser multiplicada simultaneamente à direita e á esquerda noutros termos. Estas equações podem ser resolvidas de forma iterativa. No entanto, o facto de serem lineares na incógnita Π, indicia que existem métodos não iterativos para a sua resolução. Nesta secção iremos constatar que isso é verdade. Para esse efeito, iremos transformar a equação matricial num sistema de n2 equações lineares a n2 incógnitas que pode ser resolvido por qualquer algoritmo de resolução de sistemas de equações lineares. Esta transformação irá utilizar o produto de Kronecker e, por isso, antes de a estudarmos iremos ver em que é que consiste e quais são as suas propriedades. O produto de Kronecker é uma forma ordenada e compacta de exprimir uma matriz (ou vector) cujos elementos são os produtos de todos os elementos de outras duas matrizes (ou vectores). Trata-se dum operação bilinear muito utilizada nos modelos de sistemas não lineares. Dadas as matrizes A ∈ IRn×m e B ∈ IR`×p , o produto de Kronecker entre A e B, designado por A ⊗ B, tem a11 B a12 B a21 B a22 B A ⊗ B = .. .. . . an1 B an2 B a seguinte definição · · · a1m B · · · a2m B n`×mp , .. .. ∈ IR . . · · · anm B e goza das seguinte propriedades: Tópicos de Algebra Linear 35 Propriedade 1 - Associativa (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C) Propriedade 2 - Distributiva (A + B) ⊗ (C + D) = A ⊗ C + A ⊗ D + B ⊗ C + B ⊗ D Propriedade 3 - Transposição (A ⊗ B)T = AT ⊗ B T Propriedade 4 - Produto misturado (A ⊗ B)(C ⊗ D) = AC ⊗ BD Propriedade 5 - Matriz inversa (A × B)−1 = (A−1 ⊗ B −1 ) ∀A ∈ IRn×n , B ∈ IRm×m Propriedade 6 - Valores e vectores próprios ½ AvA = λA vA ⇒ (A ⊗ B)(vA ⊗ vB ) = λA λB (vA ⊗ vB ), BvB = λB vB ∀A ∈ IRn×n , B ∈ IRm×m , isto é, se λA for um valor próprio de A ∈ IRn×n associado ao vector próprio vA ∈ IRn e se λB for um valor próprio de B ∈ IRm×m associado ao vector próprio vB ∈ IRm , então λA λB é um valor próprio de A ⊗ B ∈ IRnm×nm associado ao vector próprio vA ⊗ vB ∈ IRnm . Propriedade 7 A ⊗ B ∈ IRnm×nm é uma matriz definida positiva se A ∈ IRn×n e B ∈ R I m×m forem matrizes simétricas, e ambas definidas positivas ou definidas negativas. Iremos, em seguida, demonstrar a propriedade 4 (produto misturado) deixando a demonstração das outras como exercı́cio para o leitor. Demonstração da Propriedade 4: A matriz A ⊗ B, com A ∈ IRn×m e B ∈ IR`×p a11 B a12 B · · · a1m B .. .. .. .. . . . . A ⊗ B = ai1 B ai2 B · · · aim B = . .. .. .. .. . . . an1 B an2 B · · · anm B pode ser expressa na forma AI B(1, :) .. . AI B(i, :) .. . AI B(n, :) Tópicos de Algebra Linear 36 em que AI B(i, :) = £ ai1 B ai2 B · · · aim B ¤ ∈ IR`×mp representa o bloco constituı́do pelas linhas (i − 1)` + 1 a i` de A ⊗ B. Por outro lado C ⊗ D com C ∈ IRm×q e D ∈ IRp×r pode ser expressa na forma c11 D · · · c1j D · · · c1q D c21 D · · · c2j D · · · c2q D £ ¤ C ⊗ D = .. .. .. .. .. = CJ D(:, 1) · · · CJ D(:, j) · · · CJ D(:, q) . . . . . . cm1 D · · · cmj D · · · cmq D Nesta matriz, o bloco c1j D c2j D CJ D(:, j) = .. . cmj D ∈ IRmp representa o bloco constituı́do pelas colunas (j − 1)r + 1 a jr de C ⊗ D. O bloco constituı́do pelas linhas (i−1)`+1 a i` e as colunas (j −1)r +1 a jr de (A⊗B)(C ⊗D) que designaremos por AI BCJ D(i, j), será o produto dos blocos AI B(i, :) e CJ D(:, j) que acabamos de definir, ou seja AI BCJ D(i, j) = AI B(i, :)CJ D(:, j) = m X aik Bckj D = " m X k=1 Como Pm k=1 # aik ckj BD. k=1 aik ckj é o elemento da linha i e coluna j de CA, então AI BCJ D(i, j) também vai ser o bloco constituı́do pelas linhas (i − 1)` + 1 a i` e as colunas (j − 1)r + 1 a jr de AC ⊗ BD que designaremos por AICJ BD(i, j). Como, qualquer que sejam i e j, AI BCJ D(i, j) = AICJ BD(i, j) então (A ⊗ B)(C ⊗ D) = AC ⊗ BD, ficando assim demonstrada a propriedade. 2 A operação vectorização consiste em transformar uma matriz num vector, empilhando as suas colunas umas em cima das outras. Assim, dada a matriz A= £ a1 a2 · · · ai · · · am ¤ , ai ∈ IRn , i = 1, . . . , m, Tópicos de Algebra Linear 37 a sua vectorização, designada por vec(A) é o vector a1 a2 .. . vec(A) = ai .. . ∈ IRnm . am Iremos, agora, enunciar uma propriedade que é fundamental para a determinação duma solução não iterativa de equações de Lyapunov idênticas à (24). Propriedade 8 vec(ABC) = (C T ⊗ A)vec(B), ∀A ∈ IRn×m , B ∈ IRm×` , C ∈ IR`×p Demonstração: Sejam A= aT1 aT2 .. . , B= £ b1 b2 · · · b` ¤ aTn , C= c11 c12 · · · c1p c21 c22 · · · c2p .. .. .. .. . . . . c`1 c`2 · · · c`p com ai ∈ IRm , i = 1, . . . , n e bi ∈ IRm , i = 1, . . . , `. O produto destas três matrizes é ABC = = = c11 c12 · · · c1j · · · c1p £ ¤ c21 c22 · · · c2j · · · c2p b1 b2 · · · b` .. .. .. .. .. .. = . . . . . . T an c`1 c`2 · · · c`j · · · c`p c11 c12 · · · c1j · · · c1p aT1 b1 aT1 b2 · · · a1 b` aT2 b1 aT2 b2 · · · a` c21 c22 · · · c2j · · · c2p . .. .. .. .. .. = .. .. .. .. . . . . . . . . . .. T T c`1 c`2 · · · c`j · · · c`p an b1 an b2 · · · an b` P` P` P P` ` T aT1 bi cij · · · aT1 bi ci2 · · · aT1 bi ci1 i=1 a1 bi cip i=1 i=1 i=1 P P P P` ` ` ` T T T T i=1 a2 bi cip i=1 a2 bi cij · · · i=1 a2 bi ci2 · · · i=1 a2 bi ci1 .. .. .. .. .. .. . . . . . . P` P` P` P` T T T T i=1 an bi cip i=1 an bi cij · · · i=1 an bi ci2 · · · i=1 an bi ci1 aT1 aT2 .. . . Tópicos de Algebra Linear 38 Vemos, daqui, que a coluna j de P` T i=1 a1 bi cij P ` aT b c 2 i ij ABC(:, j) = i=1 . . . P` aT bi cij i=1 n £ = c1j c2j em que cj = c1j c2j .. . ABC que designaremos por ABC(:, j) é c1j aT1 c2j aT1 · · · c`j aT1 b1 c1j aT c2j aT · · · c`j aT b2 2 2 2 = .. .. .. .. .. = . . . . . T T c1j an c2j an · · · c`j aTn b` aT1 T ¤ a2 · · · c`j ⊗ .. vec(B) = (cTj ⊗ A)vec(B) . aTn ∈ IR` c`j é a coluna j de C. Teremos então T (c1 ⊗ A)vec(B) ABC(:, 1) ABC(:, 2) (cT2 ⊗ A)vec(B) .. .. . . vec(ABC) = = T = ABC(:, j) (cj ⊗ A)vec(B) .. .. . . T ABC(:, p) (cp ⊗ A)vec(B) T T c1 ⊗ A c1 cT2 ⊗ A cT2 .. . . = T vec(B) = .. ⊗ A vec(B) = (C T ⊗ A)vec(B). cj ⊗ A . cT .. . j .. cTp cTp ⊗ A 2 Consideremos agora a equação (24). Podemos rescrever esta equação na forma In ΠA1 + A2 ΠIn + A3 ΠA4 + Q = 0n×n . Como vec(A + B) = vec(A) + vec(B), então vec (In ΠA1 + A2 ΠIn + A3 ΠA4 + Q) = = vec(In ΠA1 ) + vec(A2 ΠIn ) + vec(A2 ΠA4 ) + vec(Q) = vec(0n×n ) = 0n2 . Tópicos de Algebra Linear 39 Utilizando a propriedade 8, teremos vec(In ΠA1 ) = (AT1 ⊗ In )vec(Π) vec(A2 ΠIn ) = (In ⊗ A2 )vec(Π) vec(A3 ΠA4 ) = (AT4 ⊗ A3 )vec(Π) e, consequentemente, (AT1 ⊗ In )vec(Π) + (In ⊗ A2 )vec(Π) + (AT4 ⊗ A3 )vec(Π) + vec(Q) = 0n2 ⇔ ¡ ¢ ⇔ AT1 ⊗ In + In ⊗ A2 + AT4 ⊗ A3 vec(Π) = −vec(Q) Se AT1 ⊗ In + In ⊗ A2 + AT4 ⊗ A3 for uma matriz não singular a solução é única e é dada por ¡ ¢−1 vec(P ) = − AT1 ⊗ In + In ⊗ A2 + AT4 ⊗ A3 vec(Q). 11 Norma de Frobenius A norma de Frobenius duma matriz A ∈ IRn×m , também conhecida como norma de HilbertSchmidt, é definida de seguinte forma v uX n u m X kAkF = kvec(A)k2 = t a2ij . j=1 i=1 Esta definição mostra que a norma de Frobenius é muito semelhante à Euclidiana pois resulta num produto interno definido no espaço das matrizes através de < A, B >= vec(A)T vec(B). Veremos, em seguida, como é que podemos calcular a norma de Frobenius através dos valores singulares. Lema 3 Se σ1 , σ2 , . . . , σp forem os valores singulares da matriz A ∈ IRn×m com p = min(n, m), então v u p p uX σi2 = traço(AT A) kAkF = t i=1 (25) Tópicos de Algebra Linear 40 Demonstração: Vimos, anteriormente, que A pode ser decomposto na forma A = Up Sp VpT em que Up ∈ IRn×p e V ∈ IRm×p são matrizes ortonormais e Sp é uma matriz diagonal cujos elementos da diagonal principal são os valores singulares de A, Se σ1 , σ2 , . . . , σp . Utilizando a propriedade 8 para vectorizar A teremos vec(A) = (Vp ⊗ Up )vec(Sp ). (26) Podemos agora calcular a norma de Frobenius de A através de kAk2F = kvec(A)k22 = [(Vp ⊗ Up )vec(Sp )]T [(Vp ⊗ Up )vec(Sp )] = = vec(Sp )T (Vp ⊗ Up )T (Vp ⊗ Up )vec(Sp ) Utilizando as propriedades 3 e 4 do produto de Kronecker e recordando que Up e Vp são matrizes ortonormais, (Vp ⊗ Up )T (Vp ⊗ Up ) = (VpT ⊗ UpT )(Vp ⊗ Up ) = (VpT Vp ) ⊗ (UpT Up ) = Ip ⊗ Ip = Ip2 , sendo, por isso, kAk2F T T T = vec(Sp ) (Vp ⊗ Up ) (Vp ⊗ Up )vec(Sp ) = vec(Sp ) vec(Sp ) = p X σi2 , i=1 pois, sendo Sp uma matriz diagonal cujos elementos da diagonal principal são os valores singulares de A, os únicos elementos não nulos de vec(Sp ) são estes valores singulares. Recorrendo, de novo, à decomposição (26) traço(AT A) = traço(Vp Sp UpT Up Sp VpT ) = traço(Vp Sp2 VpT ) pois Up é uma matriz ortonormal. Como a operação traço é comutativa desde que as dimensões das matrizes sejam compatı́veis, então T traço(A A) = traço(Vp Sp2 VpT ) = traço(VpT Vp Sp2 ) = p X σi2 i=1 pois Vp é ortonormal e Sp2 é uma matriz diagonal cujos elementos da diagonal principal são os quadrados dos valores singulares de A. 2
Download
