EQUAÇÕES LINEARES E DECOMPOSIÇÃO DOS
VALORES SINGULARES (SVD)
1 – Equações Lineares
Em notação matricial um sistema de equações lineares pode ser representado como
 a11 a12  a1n   x1   b1 
a
   
 21 a 22  a 2 n . x 2   b2 
 


      

   
a n1 a n 2  a nn   x n  bn 
ou
A.X = b
(1)
Para a solução, vários casos são considerados:
Caso (a):
b 0 e
 0
Nesse caso A-1 existe e
A-1 . A . X = A-1 .b
==> X = A-1 .b
e há uma única solução para (1)
Caso (b):
b=0 e  0
A-1 existe e
A.X = 0
e há apenas a solução trivial X = 0.
==>
A-1.A.X = A-1 . 0
==>
X=0
Caso (c):
b  0 e  =0
A-1 não existe.
==>
ou há infinitas soluções ou não há solução
Ex:
3.x  2.y  2 3 2 x  2
.

 não há solução (inconsistente)

3.x  2.y  6 3 2  y 6
3.x  2.y  2 3 2  x  2
.

 infinitas soluções (eqs. linearmente dependentes)

6.x  4.y  4 6 4  y 4
3
x =  y  1   para infinitos valores de 
2
Caso (d):
b=0 e  =0
Há infinitas soluções
a.x  b.y  0

a
 A 0x   y
 .x   .b.y  0
b
==> Um sistema homogêneo (A.X = 0) tem solução não-trivial se e somente se  = 0.
(veja caso b)
2 – Autovalores e Autovetores de uma Matriz Quadrada A
Procurar uma solução não-trivial para
A.X = .X
Os valores de  ==> autovalores.
As soluções de X ==> autovetores
(2)
A eq. (2) pode ser escrita na forma
(.I  A).X  0
(3)
 para que solução seja não-trivial
det(.I  A)  0
Esse resultado produz a equação característica
c( )  n  c n 1 .n 1  c n 2 n 2    c1  c 0  0
o que produz n soluções para . Os valores i podem ser não necessariamente distintos,
reais ou complexos, em que i = 1, 2, ...,n.
Correspondendo a cada i, há uma solução não-nula x = ei , e ei é chamado o autovetor de
A correspondendo ao autovalor i.
Em geral i  i-1
Se x = ei satisfaz (3), então qualquer i.ei de ei satisfaz (3).
3 – Propriedades Úteis de Autovalores
Propriedade 1: A soma dos autovalores de A é
n

i 1
n
i
 traço de A   a ii
i 1
Propriedade 2: O produto dos autovalores da A é
n

i
 det A
i 1
Propriedade 3: Os autovalores de A-1 (se existir) são
i
Propriedade 4: Os autovalores da transposta de A, AT são
i
Propriedade 5: Se k é um escalar, os autovalores de k.A são
k.1 , k.2 , . . . , k.n
Propriedade 6: Se k é um escalar e I uma matriz identidade nxn , então os autovalores de A
+ k.I são respectivamente
i  k
Propriedade 7: Se k é um inteiro positivo, então s autovalores de Ak são
i k
Decomposição dos Valores Singulares (SVD)
Três importantes aplicações da SVD:
1) resolver sistemas de equações lineares não-homogêneos;
2) resolver sistemas de equações lineares homogêneos com deficiências de posto;
3) garantir que os elementos de uma matriz estimada numericamente satisfaçam certas
restrições (ex: ortogonalidade).
Definição: Qualquer matriz Am x n pode ser escrita como o produto de 3 matrizes:
A = U.D.VT
,
(1)
em que as colunas da matriz Um x n são vetores unitários mutuamente ortogonais, assim
como também o são as colunas da matriz Vn x n. A matriz Dn x n é diagonal, seus elementos
diagonais, i , chamados valores singulares, são tais que  1   2   n  0 .
Propriedades da SVD
Propriedade 1: os valores singulares oferecem importantes informações sobre a
singularidade de uma matriz quadrada. Uma matriz quadrada, A, é não-singular, se e
somente se todos os seus valores singulares são diferentes de zero. Mais importante, os
valores singulares i também dizem o quanto uma matriz A está próxima de ser singular: a
razão
C
1
n
(2)
chamada número de condicionamento, mede o grau de singularidade de A. Quando C é
muito grande (1/C comparável à precisão da máquina), a matriz A é mal-condicionada, e
pode ser considerada singular.
Propriedade 2: Se A é uma matriz retangular, o número de i não nulos se iguala ao posto
de A. Portanto, dada uma tolerância fixa  (  10-6), o número de valores singulares > 
fornecem o posto efetivo da matriz A.
Propriedade 3: Se A é uma matriz quadrada, não-singular, sua inversa pode ser escrita
como
A-1 = V.D-1.UT
(3)
Seja A singular ou não, a pseudo-inversa1 de A, A+, pode ser escrita como
A+ = V.Do-1.UT
(4)
com Do-1 igual a D-1 para todos os valores singulares não-nulos, e zero em outro caso. Se A
é não-singular, então Do-1 = D-1 e A+ = A-1.
Propriedade 4: As colunas de U correspondentes aos valores singulares não-nulos varrem a
imagem de A, as colunas de V correspondentes aos valores singulares nulos são o espaço
nulo2 de A.
Propriedade 5: Os quadrados dos valores singulares não-nulos são os autovalores nãonulos de ambas as matrizes (AT.A)n x n e (A.AT)m x m. As colunas de U são autovetores de
A.AT, as colunas de V autovetores de AT.A. Além disso, A.u k   k .v k e A T .v k   k .u k ,
onde u k e v k são as colunas de U e V correspondentes a k.
Propriedade 6: Uma possível medida de distância entre matrizes se utiliza da “Norma de
Frobenius”. Essa norma de uma matriz A é simplesmente a soma dos quadrados dos
elementos ai,j de A, ou
A
F
  a i, j
2
i, j
substituindo (5) em (1)
A
F
  i
2
i
A pseudo-inversa de uma matriz A ∈ ℜm×n é uma matriz A+ ∈ ℜn×m tal que A=A.A+.A , A+=A+.A.A+ ,
A+ = (AT.A)+.AT = AT.(A.AT)+ e A+=A-1 se A for quadrada e não-singular.
2
O espaço nulo de A consiste de todas as soluções para Ax = 0.
1
(5)
Mínimos Quadrados
Considere um sistema com m equações lineares
 
A.x  b
,
(6)

em que x é o vetor de incógnitas n-dimensional. A matriz Am x n contém os coeficientes das


equações, e b é o vetor m-dimensional dos dados. Se os componentes de b não forem
todos nulos, a solução pode ser encontrada multiplicando-se ambos os lados da eq. (6) por
AT, produzindo


A T .A.x  A T b
(7)


x  (A T .A) 1 .A T .b
(8)
Segue que a solução é dada por
Esta
é
a
conhecida
solução
no
sentido
dos
mínimos
quadrados



2
T



( A.x  b  A.x  b . A.x  b  mínimo ). No caso de mais equações do que incógnitas



(A T .A) 1 coincide com a pseudo-inversa (A T .A)  , desde que a propriedade 1 seja
satisfeita (número de condicionamento de AT.A não muito grande).
Sistemas Homogêneos
Resolver o sistema homogêneo de m equações lineares em n incógnitas
A.x = 0
com m  n – 1 e
posto (A) = n – 1
(det(A) tem de ser nulo)
A solução, em função de um fator de escala, pode ser achada através da SVD.
A solução é simplesmente proporcional ao autovetor correspondente ao único autovalor
nulo de ATA.
Isto pode ser provado abaixo:
A norma da solução de um sistema homogêneo é arbitrária (infinitas soluções). Fazendo-se
a solução com norma unitária, no sentido dos mínimos quadrados, deve-se minimizar

A.x
2

 

 (A.x) T .A.x  x T .A T .A.x ,
submetida à restrição
 
x T .x  1
Usando multiplicador de Lagrange (método de otimização) , isto é equivalente a
minimizar o Lagrangeano
(x)  x T .A T .A.x  .(x T .x  1)
Igualando a derivada de  a zero, (
d
)
dx T
A T .A.x  ..x  0
o que mostra que  é autovalor de AT.A, e a solução é x  e  . Trocando x com e  e
A T .A.e  com .e  , tem-se
0
(e  )  e  ..e   .(e  .e   1)   , ou seja, o mínimo é atingido em = 0, o menor
autovalor de AT.A.
T
T
Entretanto pode-se obter a mesma solução das propriedades 4 e 5 como: a coluna de V
correspondente ao único valor singular nulo de A.