TÓPICOS DE ÁLGEBRA LINEAR
Paulo Lopes dos Santos
Departamento de Engenharia Electroté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
Tópicos de Algebra Linear
1
Conteúdo
1 Vectores Linearmente Independentes
2
2 Subespaços e Bases
4
3 Subespaços Associados a Matrizes e Decomposição QR
6
4 Decomposição em Valores Singulares
11
5 Norma Quadrática de Matrizes
16
6 Aproximação de uma Matriz por Outra de Caracterı́stica Inferior
22
7 Projecções Ortogonais de Subespaços
25
8 Projecções Oblı́quas de Subespaços
32
9 Projecções nos Subespaços gerados pelas linhas duma matriz
33
10 Produto de Kronecker e Vectorização de Matrizes
34
11 Norma de Frobenius
39
Tópicos de Algebra Linear
1
2
Vectores Linearmente Independentes
Sejam v1 , v2 , . . . , vn vectores em IRn . Diz-se que estes vectores sã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 é o vector de IR com todas as entradas nulas. Se v1 =
∈ IR2 e v2 =
·
¸
·
¸
v21
z1
2
∈ IR , então, qualquer ponto z =
, pertencente ao subespaço S ⊆ IR2 gerado
v22
z2
por v1 e v2 , pode ser expresso através da combinaçã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 não singular e se z = 02 , então
v12 v22
·
¸
·
¸−1 ·
¸ · ¸
α1
v11 v21
z1
0
=
=
α2
v12 v22
z2
0
e, consequentemente, só para α1 = α2 = 0 é que v1 e v2 se anulam. Concluı́mos, assim,
que v1 e v2 são independentes se e só se (sse) V for uma matriz não singular, ou seja, sse
det V 6= 0. Como
det V = v11 v22 − v21 v12
entã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 são independentes sse não forem colineares.
v2
v1
u2
u1
Figura 1: v1 e v2 são linearmente independentes e u1 e u2 são linearmente dependentes
Em IR2 o máximo que conseguimos é um conjunto de dois vectores linearmente independentes. Qualquer conjunto com mais de dois vectores não é de vectores linearmente
independentes.
Tópicos de Algebra Linear
3
Exemplo 1 :
2
Seja {v·
1 , v2 , v¸
3 } um conjunto
·
¸de vectores não nulos em IR . Acabamos de ver
½·que se os vec¸¾
v11
v21
v11 v21
tores v1 =
e v2 =
forem linearmente independentes então det
6=
v12
v22
v12 v22
0 Nestas condições,
·
¸
·
¸−1 ·
¸
α1
v11 v21
v31
=
6= 02
α2
v12 v22
v32
é a solução da equaçã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 são vectores no mesmo plano e, por isso, são linearmente dependentes
Pode-se provar de forma idêntica que, no espaço IRn nunca se conseguem mais do que n
vectores linearmente independentes.
Tópicos de Algebra Linear
2
4
Subespaços e Bases
Seja S um subconjunto do espaço vectorial E, isto é, S ⊆ E. Se, para quaisquer elementos v1
e v2 pertencentes a S e quaisquer escalares α1 e α2 a combinação linear α1 v1 + α2 v2 pertencer
a S, então S é um subespaço de E. Deste modo, todas as combinações lineares dos vectores
{v1 , v2 , . . . , vm } com vi ∈ IRn formam um subespaço de IRn . Esse subespaço é designado
como
(
S = span {v1 , v2 , . . . , vm } =
x:x=
m
X
)
αi vi , ∀αi ∈IR
.
i=1
Dizemos, então, que qualquer conjunto de vectores {v1 , v2 , . . . , vm } gera um subespaço.
Exemplo 2 :
Todas as combinações lineares do vector v1 são vectores colineares com v1 . Isto significa
que o subespaço gerado pelo vector v1 (span {v1 }) é a recta que o contém.
x2
span{v1 }
v1
x1
Figura 3: O subespaço gerado por v1 é a recta span{v1 }
Exemplo 3 :
O subespaço definido pelo conjunto de vectores {v1 , v2 } é o plano que contém v1 e v2
(span{v1 , v2 }) se estes vectores forem linearmente independentes. Se forem dependentes é a
recta que os contém.
A dimensão dum subespaço é o número de vectores linearmente independentes que são
necessários para o gerar. Assim, qualquer recta que passe pela origem é um subespaço de
Tó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 subespaço gerado por v1 e v2 é o plano span{v1 , v2 }
dimensão um, pois, pode ser gerada por um único vector. Qualquer plano que contenha
a origem é um subespaço de dimensão dois (pode ser gerado por dois vectores linearmente
independentes).
Seja S um subespaço de IRn com dimensão p. Qualquer conjunto de vectores independentes {v1 , v2 , . . . , vp } pertencentes a S é uma base de S. Deste modo, qualquer elemento
x ∈ S pode ser representado pela combinação linear
x = β1 v1 + β2 v2 + · · · + βp vp
em que β1 , β2 , . . . , βp são as componentes (coordenadas) de x relativamente à base {v1 , v2 , . . . , vp }.
Notemos que qualquer subespaço S tem um número infinito de bases. No entanto, o número
de elementos de cada base é sempre igual à dimensão de S.
Sejam x, y ∈ IRn . Se xT y = y T x = 0 dizemos que x e y são ortogonais o que representamos
por x⊥y. Se y T x = 0 para todo x ∈ S ⊂ IRn , então y é ortogonal a S o que designamos por
Tópicos de Algebra Linear
6
y⊥S. O conjunto de todos os vectores perpendiculares a S é o complemento ortogonal de S
e é representado por S⊥ . Formalmente, podemos definir S⊥ por
©
ª
S⊥ = y ∈ IRn : y T x = 0, ∀x ∈ S .
Pode-se provar que S⊥ é um subespaço de IRn mesmo que S o não seja.
Sejam S e V subespaços de IRn . A soma de S e V, designada por S ∨ V, é o subespaço
gerado por todos os elementos de S e V. A sua definição formal é
S ∨ V = {x + y : x ∈ S ∧ y ∈ V} .
É importante assinalar que este subespaço não é a união de S e V (S∪V não é um subespaç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 é ortogonal a V o que representamos por S⊥V. Neste caso,
S ∨ V é a soma ortogonal directa e é representada por S ⊕ V.
Para qualquer subespaço S ∈ IRn existe uma única decomposição IRn = S ⊕ S⊥ . Isto
significa que para todo z ∈ IRn existe uma única decomposição z = x + y em que x ∈ S e
y ∈ S⊥ .
3
Subespaços Associados a Matrizes e Decomposição
QR
Dado um conjunto de vectores em IRn como é que podemos verificar se são linearmente
independentes? A forma mais simples é formar uma matriz cujas colunas (ou linhas) são as
coordenadas desses vectores e calcular a sua caracterı́stica (recordemos que a caracterı́stica
duma matriz é o seu nú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


Tópicos de Algebra Linear
7
podemos ver que car(M ) = 1 e concluir que v1 e v2 são linearmente dependentes (é fácil ver
que v2 = 3v1 e que, consequentemente, estes dois vectores são colineares).
Como car(M T ) = car(M ) chegarı́amos ao mesmo resultado através do cá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 , é encarar as suas colunas (ou as
suas linhas) como um conjunto de vectores que geram um subespaço em IRn (ou IRm no caso
das linhas). Deste modo, podemos associar a A dois subespaços:
• 1 - Subespaço gerado pelas suas colunas (column-space) que designaremos por im(A) (imagem de A);
• 2 - Subespaç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 é,
v = Ax ∈ IRn
Podemos, então, afirmar que a matriz A define uma transformação do espaço IRm para IRn
(IRm → IRn ). Sendo
A =
£
a1 a2 · · · am
¤
em que ai ∈ IRn , i = 1, . . . , m e


x1
 x2 


x =  .. 
 . 
xm
então
v = Ax =

£
a1 a2 · · · am
¤



x1
x2
..
.
xm



 = a1 x1 + a2 x2 + · · · + am xm ,

Tópicos de Algebra Linear
8
ou seja, v = Ax é uma combinação linear das colunas de A, cujos coeficientes são os elementos
x1 , x2 , . . . , xm de x. Deste modo, v pertence sempre ao subespaço gerado pelas colunas de A,
isto é, im(A). Se as colunas de A forem linearmente independentes, então constituem uma
base para im(A). Nestas condições, diz-se que A é uma matriz de caracterı́stica completa
(car(A) = m = número de colunas). Identicamente, AT define uma transformação IRn →
IRm , sendo a imagem dessa transformação (im(AT )) o subespaço gerado pelas linhas de A.
Se as linhas de A constituı́rem uma base de im(AT ), então AT e, consequentemente A, são
matrizes de caracterı́stica completa. Assim, A ∈ IRn×m é uma matriz de caracterı́stica
completa se e só se
car(A) = n ou car(A) = m ⇔ car(A) = min(n, m)
Notemos que, sendo v = Ax uma combinação linear das colunas de A, podemos exprimir
v através duma outra combinação linear de outro conjunto de vectores que gere a imagem
de A. Isto significa que podemos escrever
v = Ax = Āx̄
em que im(Ā) = im(A) e x̄ são os coeficientes da referida combinação linear das colunas
de Ā. Aqui a única restrição é car(Ā) = car(A) e, consequentemente, o número de colunas
de Ā, igual ao número de linhas de x̄, não tem que ser igual ao número de colunas de A.
Frequentemente procuramos que as colunas de Ā sejam uma base que, termos numéricos,
seja o mais robusta possı́vel. A robustez máxima é alcançada quando as colunas de Ā
constituem uma base ortonormal, isto é, quando são um conjunto de vectores com módulo
unitário e perpendiculares entre si. Matrizes cujas colunas formam uma base ortonormal são
chamadas matrizes ortonormais e são frequentemente designadas pela letra Q. Notemos
que se Q ∈ IRn×m for uma matriz ortonormal então
QT Q = I m
Se Q for uma matriz quadrada (m = n) então
QT Q = Im = In ⇔ Q−1 = QT .
É esta propriedade que faz com que estas matrizes sejam numericamente muito robustas e
que frequentemente se procure representar im(A) através destas matrizes. Uma das formas
Tópicos de Algebra Linear
9
mais utilizadas na álgebra linear para atingir este objectivo é a decomposição QR, onde uma
matriz A ∈ IRn×m com n ≥ m e car(A) = r, é 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 é uma matriz
ortonormal (QT Q = In ) e, consequentemente, QR e Q̄R também o sã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 é uma matriz triangular superior.
R
Exemplo 5 : Transformação QR na resolução do sistema de equações Ax = y
Consideremos o sistema de equações
Ax = y
em que A ∈ IRn×n , x, y ∈ IRn e car(A) = n. Fazendo uma decomposição QR teremos
QRx = y ⇔ Rx = QT y
ficando este sistema de equações reduzido a


 

r11 r12 · · · r1n
x1
ȳ1
 0 r22 · · · r2n   x2   ȳ2 


 

 ..
.. . .
..   ..  =  .. 
 .
. .  .   . 
.
0
0 · · · rnn
xn
ȳn
em que



ȳ = 

ȳ1
ȳ2
..
.



 = QT y.

ȳn
Como R é uma matriz triangular superior, as soluções xn , xn−1 , . . . , x1 podem ser calculadas
recursivamente por substituição à retaguarda (back substitution), começando por xn =
ȳn
.
rnn
Com este processo, substituı́mos a inversão de A pela transposição de Q e pela inversão da
matriz triangular superior R, que são operações numericamente mais robustas.
Exemplo 6 : Resolução do problema de mı́nimos quadrados
O problema de mı́nimos quadrados consiste no cálculo de vector θ ∈ IRm que minimiza
kY − Xθk2 = (Y − Xθ)T (Y − Xθ)
Tópicos de Algebra Linear
10
com Y ∈ IRn , X ∈ IRn×m , n ≥ m e car(X) = m. Efectuando a seguinte decomposição QR
de X

R
X = Q  − − −− 
0(n−m)×m

Q ∈ IRn×n ,
R ∈ IRm×m
e, uma vez que Q é 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 =
°·
°·
¸ ·
¸ °
¸
·
¸ °
°
°
° Ȳ1
° Ȳ1
R
R
T
°
°
°
°
° Ȳ2 − Q Q 0(n−m)×m θ° = ° Ȳ2 − 0(n−m)×m θ° =
2
2
°·
¸°
h
i · Ȳ − Rθ ¸
° Ȳ1 − Rθ °
1
°
° = (Ȳ1 − Rθ)T Y¯2 T
=
°
°
Y¯2
Y¯2
2
°
° °
°
T
= (Ȳ1 − Rθ)T (Ȳ1 − Rθ) + Y¯2 Y¯2 = °Ȳ1 − Rθ°2 + °Y¯2 °2
em que
·
¸
Ȳ1
= QT Y,
Ȳ2
Ȳ1 ∈ IRm ,
Ȳ2 ∈ IRn−m .
A solução do problema de mı́nimos quadrados será, então, a solução do sistema de equações
Rθ̂ = Ȳ1
idêntico ao do exemplo anterior. Como, para θ = θ̂, Ȳ1 − Rθ = 0m , então min kY − Xθk2 =
kY2 k2 .
Existem várias formas de obter uma decomposição QR sendo, talvez, as transformações de
Householder e a ortogonalização de Gram-Schimdt, os métodos mais utilizados.
Além de im(A), também se define o subespaço Núcleo de A (kernel ou null space em
inglês) designado por ker(A) e que é definido por
ker(A) = {x : Ax = 0n } ,
ou seja, o subespaço de IRm que é transformado na origem (de IRn ) pela matriz A ∈ IRn×m .
Como este subespaço é formado por todos os vectores perpendiculares às linhas de A, podemos afirmar que ker(A)⊥im(AT ), sendo, por isso, ker(A) ∩ im(AT ) = 0m×m . Por outro lado,
Tópicos de Algebra Linear
11
como a dimensão do núcleo duma matriz é igual ao seu número de colunas (m) menos a sua
£
¤
caracterı́stica, então, dim [ker(A)] + dim im(AT ) = m e, consequentemente,
ker(A) ⊕ im(AT ) = Rm ⇒ ker(A) = im(AT )⊥ .
Identicamente, o núcleo de AT , designado por ker(AT ), é o complemento ortogonal de im(A).
4
Decomposição em Valores Singulares
Na decomposição QR é explicitada uma base ortonormal para a imagem duma matriz A.
Nesta secção iremos ver a decomposição em valores singulares onde, além duma base ortonormal para este subespaço, também são explicitadas bases ortonormais para a imagem de AT
e para os núcleos de A e AT . Antes de introduzirmos esta decomposição vamos recordar a
diagonalização de matrizes simétricas.
Lema 1
Se B ∈ IRn×n for uma matriz simétrica, isto é, se B T = B, entã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 é uma matriz diagonal e UB uma matriz ortonormal.
Demonstração:
Como B é simétrica os seus valores próprios são reais e é diagonalizável. Para simplificar,
vamos admitir todos os valores próprios de B são distintos. Nestas condições podemos
escrever
B = T ΛB T −1
Tópicos de Algebra Linear
12
em que ΛB está definida em (1) e T é uma matriz cujas colunas são os vectores pró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 próprios repetidos as suas multiplicidades algébrica e geométrica são iguais,
continuando a expressão(3) a ser válida para estes casos.
2
Estamos agora em condições de apresentar a decomposição em valores singulares.
Teorema 1 : Decomposição em valores singulares (svd)
Se A ∈ IRn×m tiver caracterı́stica r ≤ min(n, m) entã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.
Demonstração:
Como a matriz AT A ∈ Rm×m é simé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.
Tó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 são vectores próprios de AT A, isto é,
V
=
£
v1 v2 · · · vm
AT Avi = λi vi = σi2 vi ,
¤
i = 1, . . . , m.
Se Vr ∈ IRm×r for a matriz cujas colunas são os vectores próprios associados aos valores
próprios nã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)
entã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+ é a matriz definida em (5). Seja
Ur = AVr S+−1 ∈ IRn×r .
(10)
Pré-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 é uma matriz ortonormal cujas colunas geram um subespaço de dimensão
r em IRn . Se Ūr for uma matriz ortonormal cuja imagem é o complemento ortogonal da
imagem de Ur (Ūr = Ur⊥ ), então
0(n−r)×r = ŪrT Ur = ŪrT AVr S+−1 ⇒ ŪrT A = 0(n−r)×m ,
Tópicos de Algebra Linear
14
isto é, a imagem de Ūr também é o complemento ortogonal de A, o que nos permite concluir
que im(Ur ) = im(A) e que, consequentemente, as colunas de Ur são uma base ortonormal de
im(A). Definindo
U =
£
Ur | Ū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)
ŪrT A
ŪrT
ŪrT AVr ŪrT AV¯r
Como UrT Ur = Ir , então, substituindo, nesta equação, Ur pelo seu valor definido em (10),
teremos
UrT AVr S+−1 = Ir ⇒ UrT AVr = S+ .
Por outro lado, fazendo a mesma substituição no bloco (1, 2) da última matriz na expressã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 Ūr geram o complemento
ortogonal do subespaço gerado pelas colunas de A,
ŪrT AVr = 0(n−r)×r
Ū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 , pré-multiplicando e pó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 demonstração.
2
Normalmente define-se
·
¸
S+
0r×(m−r)
S=
∈ IRn×m
0(n−r)×r 0(n−r)×(m−r)
Tópicos de Algebra Linear
15
e exprime-se a decomposiçã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, então

0
0 
.. 

. 

σm 

0 
.. 
. 
0
0
0
..
.
σn
0 ···
0 ···
.. ..
. .
0 ···
0
0
..
.





0
Os elementos da diagonal principal de S estão ordenados por ordem decrescente, isto é,
σ1 ≥ σ2 ≥ · · · ≥ σp , com p = min(n, m), e são designados por valores singulares de A. Na
demonstração da decomposição em valores singulares vimos que estes são as raı́zes quadradas
positivas de valores próprios de AT A. É fácil demonstrar que os valores singulares são as
raı́zes quadradas positivas dos valores próprios de AT A quando n ≥ m e dos valores
próprios de AAT quando n ≤ m. S+ , definida em (5), é a matriz dos valores singulares
não nulos. Como car(S) = car(S+ ), então car(A) = car(S+ ), ou seja, a caracterı́stica duma
matriz é igual ao número de valores singulares não nulos pois, U e V são matrizes não
singulares1 . Vimos, também, que V é uma matriz (ortonormal) cujas colunas são os vectores
próprios de AT A. pode-se provar, identicamente, que U é uma matriz cujas colunas são
os vectores próprios de AAT . As colunas de U e V também são designadas por vectores
singulares de A. As de U , são os vectores singulares á esquerda e as de V , os vectores
singulares à direita.
Utilizando as decomposições de V e U definidas em (6)-(7) e (11), respectivamente,
podemos rescrever a decomposição em valores singulares na forma
¸
·
·
¸· T ¸
£
¤ VrT
£
¤
S+
0r×(m−r)
Vr
Ur | Ū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 não singulares são matrizes de caracterı́stica completa e que se G for uma
matriz de caracterı́stica completa então a caracterı́stica de F = GH é igual à caracterı́stica de H.
Tópicos de Algebra Linear
16
Chegamos assim à forma reduzida da decomposição em valores singulares.
• Se, na transformação IRm → IRn z = Ax, definirmos x̄ = S+ VrT x, teremos z = Ax = Ur x̄.
Com car(A) = car(Ur ), A e Ur têm a mesma imagem e , consequentemente, as colunas
de Ur são uma base ortonormal do subespaç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
são uma base ortnormal para o subespaço gerado pelas linhas de A.
• Dado que as colunas de V̄r são perpendiculares à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 núcleo de A (ker(A)). Como
car(V̄r )=car (ker(A)) = m − r, então im(V̄r ) = ker(A), sendo as colunas de V̄r uma base
ortonormal do núcleo de A. Analogamente, as colunas de Ūr são uma base ortonormal do
núcleo de AT .
Resumindo,
im(Ur ) = im(A)
im(Vr ) = im(AT )
im(V̄r ) = ker(A)
im(Ūr ) = ker(AT ).
5
Norma Quadrática de Matrizes
Os vectores dum espaço IRn são habitualmente definidos pela combinação linear dos vectores
 
0
 0 
 . 
 . 
 . 
 
 0  ∈ IRn
i = 1, . . . , n,
ei =  
 1  igésima linha
 
 0 
 . 
 .. 
0
Tópicos de Algebra Linear
17
que formam a base canó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 transformação U T x roda os eixos da base ortonormal {u1 , . . . , un } para
os eixos da base canónica {e1 , . . . , en }. Por outras palavras, a transformação U T x é uma
rotação que alinha os eixos u1 , . . . , un com e1 , . . . , en . Assim, chamaremos alinhador à
matriz U T .
Exemplo 7 : Alinhador no espaço IR2
Se
U=
£
u1 u2
¤
for uma matriz ortogonal em IR2 entã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 têm módulo unitário e são
mutuamente ortogonais. Podemos, então, concluir, que esta transformação roda todos os
vectores de um ângulo θ (ângulo que u1 faz com e1 (ver figura 5). Seja agora
x = α1 u1 + α2 u2
O vector z = U T x será
·
T
T
T
z = U (α1 u1 + α2 u2 ) = α1 U u1 + α2 U u2 = α1 e1 + α2 e2 =
α1
α2
¸
ou seja, z é um vector cujas coordenadas sã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 é o alinhador do referencial constituı́do pelos vectores
u1 e u2 .
Tó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 é o alinhador de {u1 , u2 } no espaço IR2
Como
U =
£
u1 u2 · · · un
¤
= U In = U
£
e1 e2 · · · en
¤
,
então
U e i = ui ,
i = 1, . . . , n.
Vemos, deste modo, que a transformação y = U x roda os eixos da base canónica {e1 , . . . , en }
para os da base ortonormal {u1 , . . . , un }. Como os eixos da base canónica são pendurados
nos da base ortonormal, chamaremos cabide a U .
Exemplo 8 : Cabide no espaço IR2
Dado que a matriz U , definida no exemplo anterior, é ortonormal, U −1 = U T . Consequentemente z = U T x e x = U z são transformações inversas. Se a transformação definida por U T
roda as colunas u1 e u2 de U para e1 e e2 , respectivamente, então a que é definida por U
roda e1 e e2 para u1 e u2 . O vector
¸
·
α1
z =
α2
é transformado no vector
x = Uz =
£
u1 u2
¤
·
α1
α2
¸
= α1 u1 + α2 u2 .
Podemos, então, afirmar que as coordenadas α1 e α2 de z foram penduradas em u1 e u2 pelo
cabide U .
Tó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 é o cabide em {u1 , u2 } no espaço IR2
Seja D ∈ IRn×n

d1 0
 0 d2

D =  .. ..
 . .
0 0
uma matriz diagonal, isto é,

··· 0
··· 0 

. .
..
. .. 
· · · dn
Se multiplicarmos D, á direita, pelo vector


α1
 α2 


x =  .. 
 . 
αn
obtemos



xd = 

d1 α1
d2 α2
..
.





dn αn
onde as coordenadas nos eixos de e1 , e2 , . . . , en estão multiplicadas pelos elementos d1 , d2 , . . . , dn ,
respectivamente, de D. podemos afirmar, então, que as coordenadas de x foram deformadas
pelos elementos de D e designaremos D por deformador .
Exemplo 9 : Deformador no espaço IR2
Seja
D =
·
1 0
0 0, 5
¸
Tópicos de Algebra Linear
20
uma matriz diagonal em IR2×2 e C2 (1) = {x : kxk2 = 1}, isto é, a circunferência de raio
unitário. A transformação z = Dx transforma esta circunferência numa elipse E2 (1, 0.5)
com semi-eixos de comprimento 1 e 0, 5. Vemos, assim, que a circunferê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 é um deformador no espaço IR2
Como, através da decomposição em valores singulares, podemos decompor uma matriz
na forma
A = Ur S+ VrT
onde Ur e Vr são matrizes ortonormais e S+ é uma matriz diagonal, podemos ver a transformação
z = Ax = Ur S+ VrT x
como a sequência das seguintes operações:
• Alinhamento dos eixos de v1 , v2 , . . . , vr com os eixos de e1 , e2 , . . . , er da base canónica
efectuado pelo alinhador VrT
• Deformação da novas coordenadas de x pelo deformador S+ .
• Suspensão das novas coordenadas deformadas de x no cabide Ur .
Por outras palavras, os eixos v1 , v2 , . . . , vr são deformados de σ1 , σ2 , . . . , σr e rodados para
u1 , u 2 , . . . , u r .
Tópicos de Algebra Linear
21
Exemplo 10 : Transformaçã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 decomposiçã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 : Transformação da hiperesfera de raio unitário
A hiperesfera de ordem m de raio unitário é transformada pela matriz A ∈ IRn×m com
decomposiçã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 quadrática duma matriz A ∈ IRn×m é designada por kAk2 e definida por
kAk2 =
sup kAxk2
kxk2 =1
isto é, é o módulo do maior vector z = Ax quando x tem módulo unitário. Como a hiperesfera
de ordem m de raio unitário é transformada por A numa elipsóide com semi-eixos de comprimentos iguais aos seus valores singulares, então o maior vector z = Ax desta transformação
tem o módulo igual ao do maior valor singular de A e, consequentemente,
kAk2 = σ1
Tópicos de Algebra Linear
22
A
1
σ 3 u3
σ 1 u1
1
1
σ2 u2
Figura 8: Transformação da esfera unitária numa elipsóide em IR3 por uma matriz
A ∈ IR3×3 com vectores singulares à esquerda u1 , u2 e u3 e valores singulares σ1 , σ2 e σ3 .
Exemplo 12 : Norma quadrática duma matriz 2 por 2
Como a matriz
¸
·
1, 44 0, 92
A =
0, 08 1, 44
com a seguinte decomposiçã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 circunferência unitária numa elipse com semi-eixos de comprimentos 2 e 1,
então
kAk2 = 2 = maior valor singular de A
6
Aproximaçã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 decomposição em valores singulares
A = U SV T
Tó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 é o comprimento do maior semi-eixo da elipse em que é
transformada a circunferência de raio unitário
permite-nos chegar à decomposição diática, dada por
A =
m
X
σi ui viT
i=1
Para x = αj vj , um vector na direcçã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 módulo unitário e é perpendicular a vi para i 6= j. Esta expressão evidencia
o facto mencionado na secção anterior, de que os pontos no eixo de vj sã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, então σr+1 = σr+2 = · · · = σm = 0, significando isto que as
componentes αr+1 vr+1 , αr+2 vr+2 , . . . , αm vm estão no núcleo de A sendo, por isso, eliminadas
na transformação Ax. Teremos, assim,
Ax = σ1 α1 u1 + σ2 α2 u2 + · · · + σr αr ur .
Tó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 aproximação é
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 são vectores de norma unitá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 são ortogonais. Isto significa que Ak x é a projecção ortogonal de Ax
no subespaço gerado por u1 , u2 , . . . , uk , sendo, por isso, a sua melhor aproximação neste
subespaço e , consequentemente, im(Ak ) é a melhor aproximação de dimensão k do subespaç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 é a melhor aproximação de AT z no subespaço gerado por v1 , v2 , . . . vk sendo im(ATk ) a melhor aproximação de dimensão k de im(AT )
Como im(Ak ) e im(ATk ) são as melhores aproximações de im(A) e im(AT ), respectivamente, podemos afirmar que Ak é a melhor aproximação com caracterı́stica k de A.
Tópicos de Algebra Linear
7
25
Projecções Ortogonais de Subespaços
Sejam x e y dois vectores em IRn . A projecção ortogonal de y em x, que designaremos por
y\x é um vector na direcção de x com módulo kyk2 cos φ em que φ é o â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: Projecçã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 é um vector unitário na direcçã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)
Tópicos de Algebra Linear
26
Como y − y\x é perpendicular a x, então y\x é a melhor aproximação na direcção de x.
Notemos, ainda, que a projecção y\x é uma combinação linear de x, isto é,
y\x = xθ̂
em que
θ̂ =
¡
xT x
¢−1
xT y.
Vemos, assim, que θ̂ é o estimador de mı́nimos quadrados
θ̂ = min ky − xθk2 .
θ
Se x for um vector na direcção de um dos vectores da base canónica, isto é, se x =
Kx ei ,
Kx ∈ IR, entã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 expressão é independente de Kx a projecção y\x , depende unicamente da direcção
de x, ou seja, y\z = y\x para qualquer z na direcção de x. Vemos, deste modo, que projectar
y em x é o mesmo que projectar y no subespaço gerado por x.
Vamos agora ver o que acontece quando x é um vector com direcção arbitrária. Comecemos por definir uma base ortonormal {u1 , . . . , un } em que x = Kx u1 . A seguir podemos
efectuar as seguintes operações
• Alinhar u1 com e1 .
• Projectar y em e1 no novo referencial.
• Pendurar e1 em u1 .
Tópicos de Algebra Linear
27
y
y2
1
Kx e1 y1 e1
e1
−1
y1
1
−1
Figura 11: Projecçã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: Projecção ortogonal de y em x: 1 - O plano é rodado para alinhar o eixo de x
com o de e1 . 2 - y rodado é projectado no eixo de e1 . 3 - O plano é rodado para a posição
inicial.
Estas operações traduzem-se na seguinte expressã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) é a decomposição em valores singulares de
P , concluı́mos que esta matriz tem caracterı́stica 1. Notemos que P é uma matriz simétrica
(P T = P ) e idempotente (P 2 = P ).
Tó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 projecção pode ser feita através das
seguintes operaçõ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 projecções traduzem-se na expressã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 decomposição em valores singulares de P .
Podemos alargar este conceito de projecção de um vector num plano, ao da projecção
dum subespaço noutro subespaço. Neste contexto, a projecção da imagem de Y na imagem
de X em que
Y
=
X =
£
£
y1 · · · y`
¤
x1 · · · xm
∈ IRn×` , n > `
¤
∈ IRn×m , n > m
é a imagem da matriz
Y \X = P Y
(16)
em que
P =
£
Ur
Ūr
¤
·
Ir
0r×(m−r)
0(n−r)×r
0(n−r)×(m−r)
¸·
UrT
ŪrT
¸
= Ur UrT
(17)
Tópicos de Algebra Linear
29
Se as colunas x1 , . . . , xm de X forem linearmente independentes, então r = m e
P = X(X T X)−1 X T
pois X T X é uma matriz não singular. Nestas condições, a projecção de Y em X é a combinação linear das colunas de X
Y \X = X θ̂,
em que θ̂ tem uma só soluçã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 projecção Y \X existe sempre mesmo quando as colunas de X não são linearmente
independentes. No entanto, (19) deixa de ter uma única solução pois X T X é singular.
Como obter uma solução θ nestas condições? Se
X = Ur S+ VrT
(20)
for a forma reduzida da decomposiçã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 † é a única matriz que obedece às seguintes condições (condições de Moore-Penrose):
1. XX † X = X
2. X † XX † = X †
¢T
¡
3. XX † = X † X
Tópicos de Algebra Linear
30
¡
¢T
4. X † X = XX †
X † é designada como o inverso generalizado ou pseudo-inverso de X. Se car(X) =
m, então X † = (X T X)−1 X T e X † X = Im . Se car(X) = n, então teremos X † = X T (XX T )−1
e XX † = In .
Vamos agora provar que θ̂ definido em (22) é 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 > `, então
¡
¢
θ̄(Ψ) = X † y + Im − X † X Ψ,
∀Ψ ∈ IRm
é a solução geral do problema de mı́nimos quadrados
min ky − Xθk2 .
θ ∈ IRm×`
(23)
e
θ̂ = θ̄(0m×` ) = X † y
é a única solução de norma mı́nima, isto é, é a única solução tal que
°
°
kθ̂k2 ≤ °θ̄(Ψ)°2 ,
∀Ψ ∈ IRm .
Demonstração:
Todas soluções de (23) devem ser coeficientes de todas as combinações lineares de X que
©
ª
geram y\X , isto é, o conjunto Θ = θ̄ : X θ̄ = y\X . Utilizando a forma reduzida da decomposição em valores singulares de X em (20) e as definiçõ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 solução de (23). As outras
³
´
soluções são do tipo θ̂ + Υ tal que X θ̂ + Υ = y\X . Como X θ̂ = y\X , então XΥ =
0n×` . Isto significa que Υ pode ser qualquer vector no núcleo de X, ker(X). Υ pode então
ser gerado através da projecção ortogonal de um vector qualquer Ψ ∈ IRm em ker(X).
Vimos, anteriormente, que ker(X) é o complemento ortogonal de im(X T ) em que im(X T ) é
Tópicos de Algebra Linear
31
o subespaço gerado pelas linhas de X. Se Vr for uma base ortonormal de im(X T ), então, de
(16) e de (17), a projecção de Ψ em im(X T ) é dada por
Ψ\X T = Vr VrT Ψ,
sendo
Υ = Ψ\(X T )⊥ = Ψ − Ψ\X T
a projecção ortogonal de Ψ em (X T )⊥ . Se Vr for a base calculada na decomposição em
valores singulares de X, então podemos gerar Υ atravé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 solução geral de (23) será
¡
¢
θ̄(Ψ) = θ̂ + Im − X † X Ψ,
∀Ψ ∈ IRm
em que Ψ é qualquer matriz de IRm .
Como
θ̂ = |{z}
X † y = Vr S+−1 UrT y = Vr ȳ ∈ im(X T )
| {z }
−1 T
Vr S+
Ur
ȳ
e
¡
¢
Υ = Im − X † X Ψ ∈ ker(X),
então θ̂ e Υ são perpendiculares pois ker(X) é 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 só se verifica igualdade para Ψ = 0m , ficando assim concluı́da a demonstração.
2
Tópicos de Algebra Linear
32
O estimador de mı́nimos quadrados de norma mı́nima pode ser expresso através de
θ̂ = X † Y = Vr S+−1 Ur Y =
r
X
uT v i Y
i
i=1
σi
Esta expressão mostra que, se o menor valor singular σr for muito menor que os outros,
pequenas perturbações na matriz que provoquem pequenas alterações em ur ou vr causam,
seguramente, perturbações muito significativas em θ̂. Se, no entanto, os valores singulares
não forem muito diferentes uns dos outros, as perturbações nos diferentes vectores singulares
tendem-se a compensar umas às outras, não fazendo variar significativamente θ̂. Vemos,
assim, que a sensibilidade de θ̂ depende, fundamentalmente, da diferença entre os valores
singulares de X. O número de condição de X definido por
κ(X) = kXk2 kX † k2 =
σ1
σr
é utilizado como medida de sensibilidade de θ. Por definição é superior ou igual a 1. Se
for muito grande, então X é uma matriz mal condicionada. Se se mantiver pequeno X é
bem condicionada. Uma matriz ortonormal tem número de condição igual a 1 e, por isso, é
perfeitamente condicionada.
8
Projecções Oblı́quas de Subespaços
Seja y ∈ IRn dado por
y = a1 x1 + a2 x2
onde a1 e a2 ∈ IR, x1 e x2 ∈ IRn . A projecção oblı́qua de y em x1 segundo x2 , designada por
y\xx21 , é a1 x1 . Se y não estiver no plano gerado por x1 e x2 , a projecção oblı́qua de y em x1
segundo x2 é a projecçã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
Tópicos de Algebra Linear
33
y
y\xx12 = a2 x1
x2
x1
y\xx21 = a1 x1
Figura 13: y\xx21 é a projecção oblı́qua de y em x1 segundo a direcção de x2 . y\xx12 é a projecção
oblı́qua de y em x2 segundo a direcção de x1 .
então
y\xx21 = x1 θ̂1 .
Dum modo geral, dizemos que a projecção de Y ∈ IRn×` em X1 ∈ IRn×m1 segundo X2 ∈
IRn×m2 com n > ` e n > m1 + m2 é
2
Y \X
X1 = X1 θ̂1
onde
·
¸
£
¤†
θ̂1
X1 X2 Y.
=
θ̂2
9
Projecções nos Subespaços gerados pelas linhas duma
matriz
Quando o número de colunas duma matriz é superior ao das linhas (m > n) as projecções são
no subespaço gerado pelas linhas. Como, transpondo uma matriz, trocamos as linhas pelas
colunas, tudo o que se disse sobre projecções nos subespaços gerados pelas colunas continua
válido desde que todas as matrizes sejam transpostas. Se, no fim de todas as projecções,
voltarmos a transpor as matrizes, obtemos
¡
¢T
Y /X = Y T \X T = Y X † X = θ̂X = Y Vr VrT
em que θ̂ é o estimador de mı́nimos quadrados de menor norma dado por
θ̂ = Y X † .
Se car(X) = n, então X † = X T (XX T )−1 e
Y /X = Y X T (XX T )−1 X
Tópicos de Algebra Linear
34
A projecção oblı́qua de Y em X1 segundo X2 é 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 Vectorização de Matrizes
Em controlo, especialmente nas áreas de estimação e redução de ordem do modelo, é frequente
ter que se resolver equações de Lyapunov. Estas, são equações matriciais, do tipo
ΠA1 + A2 Π + A3 ΠA4 + Q = 0n×n .
(24)
Embora sejam lineares na incógnita Π ∈ IRn×n , não podem ser resolvidas de uma forma
directa porque, nuns termos a incógnita aparece multiplicada à direita , noutros é multiplicada à esquerda, podendo ainda ser multiplicada simultaneamente à direita e á esquerda
noutros termos. Estas equações podem ser resolvidas de forma iterativa. No entanto, o
facto de serem lineares na incógnita Π, indicia que existem métodos não iterativos para a
sua resolução. Nesta secção iremos constatar que isso é verdade. Para esse efeito, iremos
transformar a equação matricial num sistema de n2 equações lineares a n2 incógnitas que
pode ser resolvido por qualquer algoritmo de resolução de sistemas de equações lineares.
Esta transformação irá utilizar o produto de Kronecker e, por isso, antes de a estudarmos
iremos ver em que é que consiste e quais são as suas propriedades.
O produto de Kronecker é uma forma ordenada e compacta de exprimir uma matriz
(ou vector) cujos elementos são os produtos de todos os elementos de outras duas matrizes
(ou vectores). Trata-se dum operação bilinear muito utilizada nos modelos de sistemas nã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 definição

· · · a1m B
· · · a2m B 

n`×mp
,
..
..  ∈ IR
.
. 
· · · anm B
e goza das seguinte propriedades:
Tó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 - Transposiçã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 próprios
½
AvA = λA vA
⇒ (A ⊗ B)(vA ⊗ vB ) = λA λB (vA ⊗ vB ),
BvB = λB vB
∀A ∈ IRn×n , B ∈ IRm×m ,
isto é, se λA for um valor próprio de A ∈ IRn×n associado ao vector próprio vA ∈ IRn e se
λB for um valor próprio de B ∈ IRm×m associado ao vector próprio vB ∈ IRm , então λA λB
é um valor próprio de A ⊗ B ∈ IRnm×nm associado ao vector próprio vA ⊗ vB ∈ IRnm .
Propriedade 7 A ⊗ B ∈ IRnm×nm é uma matriz definida positiva se A ∈ IRn×n e B ∈ R
I m×m
forem matrizes simétricas, e ambas definidas positivas ou definidas negativas.
Iremos, em seguida, demonstrar a propriedade 4 (produto misturado) deixando a demonstração das outras como exercı́cio para o leitor.
Demonstraçã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, :)
Tó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), será 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 é o elemento da linha i e coluna j de CA, então AI BCJ D(i, j) també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)
então (A ⊗ B)(C ⊗ D) = AC ⊗ BD, ficando assim demonstrada a propriedade.
2
A operação vectorizaçã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,
Tópicos de Algebra Linear
37
a sua vectorização, designada por vec(A) é o vector

a1
a2
..
.




vec(A) = 



ai
..
.





 ∈ IRnm .



am
Iremos, agora, enunciar uma propriedade que é fundamental para a determinação duma
solução não iterativa de equações de Lyapunov idênticas à (24).
Propriedade 8
vec(ABC) = (C T ⊗ A)vec(B),
∀A ∈ IRn×m , B ∈ IRm×` , C ∈ IR`×p
Demonstraçã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 três matrizes é



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
..
.





.

Tó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) é
 


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
é a coluna j de C. Teremos entã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 equação (24). Podemos rescrever esta equação na forma
In ΠA1 + A2 ΠIn + A3 ΠA4 + Q = 0n×n .
Como vec(A + B) = vec(A) + vec(B), então
vec (In ΠA1 + A2 ΠIn + A3 ΠA4 + Q) =
= vec(In ΠA1 ) + vec(A2 ΠIn ) + vec(A2 ΠA4 ) + vec(Q) = vec(0n×n ) = 0n2 .
Tó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 não singular a solução é única e 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 , também conhecida como norma de HilbertSchmidt, é definida de seguinte forma
v
uX
n
u m X
kAkF = kvec(A)k2 = t
a2ij .
j=1 i=1
Esta definição mostra que a norma de Frobenius é muito semelhante à Euclidiana pois resulta
num produto interno definido no espaço das matrizes através de
< A, B >= vec(A)T vec(B).
Veremos, em seguida, como é que podemos calcular a norma de Frobenius através dos valores
singulares.
Lema 3 Se σ1 , σ2 , . . . , σp forem os valores singulares da matriz A ∈ IRn×m com p =
min(n, m), então
v
u p
p
uX
σi2 = traço(AT A)
kAkF = t
i=1
(25)
Tópicos de Algebra Linear
40
Demonstração: Vimos, anteriormente, que A pode ser decomposto na forma
A = Up Sp VpT
em que Up ∈ IRn×p e V ∈ IRm×p são matrizes ortonormais e Sp é uma matriz diagonal cujos
elementos da diagonal principal sã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 atravé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 sã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 são os valores singulares de A, os únicos elementos não nulos de vec(Sp ) são estes valores singulares. Recorrendo,
de novo, à decomposição (26)
traço(AT A) = traço(Vp Sp UpT Up Sp VpT ) = traço(Vp Sp2 VpT )
pois Up é uma matriz ortonormal. Como a operação traço é comutativa desde que as dimensões das matrizes sejam compatı́veis, então
T
traço(A A) =
traço(Vp Sp2 VpT )
=
traço(VpT Vp Sp2 )
=
p
X
σi2
i=1
pois Vp é ortonormal e Sp2 é uma matriz diagonal cujos elementos da diagonal principal são
os quadrados dos valores singulares de A.
2