Álgebra Linear Aplicada – Exer. 28 – Qualificação
Estou estudando para a prova de qualificação de álgebra linear aplicada do programa de mestrado em matemática aplicada da UFPR e vou divulgar a resolução de algumas questões. Os exercícios são das provas de exames anteriores, disponíveis na página do programa. Fique à vontade para fazer sugestões, correções, críticas, etc.
Veja aqui todos os exercícios resolvidos de Álgebra Linear Aplicada.
Farei cópia fiel do enunciado dos exercícios, não corrigirei erros e imprecisões. Fica por conta dos comentário na resolução.
Exercício: (número 4 da prova de 06/04/2009)
Use o método de decomposição em valor singular (SVD) para:
- provar que toda matriz $A$ pode ser representada através de uma combinação linear de matrizes de posto um.
- assumindo que os valores singulares são positivos, encontrar uma fórmula para a solução por quadrados mínimos do sistema linear $Ax=b$.
Resolução:
-
Mais um exemplo de enunciado mal escrito. Para mostrar o fato do primeiro item, basta escrever a matriz $A$ como soma de matrizes cuja única entrada diferente de zero é uma entrada da matriz $A$ na sua respectiva posição (outra maneira trivial é escrever $A$ como soma de matrizes que cada uma tem uma linha de $A$, ou ainda uma coluna de $A$), e isso nada tem a ver com SVD. Não vejo como arrumar este enunciado com mudanças pequenas, acho que deveria simplesmente pedir para demonstrar a fórmula
$$A=\sum_{j=1}^r{\sigma_ju_jv_j^T}.$$Vamos começar. Como não foi especificado, vou escolher o ambiente da matriz em questão: $A\in\mathbb{R}^{m\times n}$, de posto $r$.
Por decomposição em valores singulares na forma reduzida, $A_{m\times n}=U_{m\times r}\Sigma_{r\times r}(V^T)_{r\times n}$. Podemos escrever $\Sigma_{r\times r}$ como soma de $r$ matrizes,
$$\Sigma_{r\times r}=
\begin{pmatrix}
\sigma_1 \\
& \sigma_2 \\
& & \ddots \\
& & & \sigma_r
\end{pmatrix}$$
$$=\begin{pmatrix}
\sigma_1 \\
& 0 \\
& & \ddots \\
& & & 0
\end{pmatrix}+
\begin{pmatrix}
0
& \sigma_2 \\
& & \ddots \\
& & & 0
\end{pmatrix}+\cdots+
\begin{pmatrix}
0 \\
& 0 \\
& & \ddots \\
& & & \sigma_r
\end{pmatrix}$$
$$=\Sigma_1+\Sigma_2+\cdots+\Sigma_r.$$Portando,
$$A=U(\Sigma_1+\Sigma_2+\cdots+\Sigma_r)V^T=U\Sigma_1 V^T+U\Sigma_2 V^T+\cdots+U\Sigma_r V^T.$$Pelo enunciado, aqui já é o suficiente, pois nesta soma cada matriz tem posto $1$. Mas vamos chegar àquela fórmula que propus acima.
Vou escrever as coordenadas dos vetores $v_j$ e $u_j$ assim: $v_j=(v_{j1},v_{j2},…,v_{jn})$ e $u_j=(u_{j1},u_{j2},…,u_{jn})$. Para cada matriz da soma acima,
$$U\Sigma_j V^T=U\begin{pmatrix}
0 \\
& \ddots \\
& & \sigma_j \\
& & & \ddots \\
& & & & 0
\end{pmatrix}
\begin{pmatrix}
& & v_1 & & \\
\hline
& & \vdots & & \\
\hline
& & v_j & & \\
\hline
& & \vdots & & \\
\hline
& & v_r & &
\end{pmatrix}$$
$$=\begin{pmatrix}
& | & & | & & | & & | & \\
& | & & | & & | & & | & \\
u_1 & | & \cdots & | & u_j & | & \cdots & | & u_r \\
& | & & | & & | & & | & \\
& | & & | & & | & & | &
\end{pmatrix}
\begin{pmatrix}
0 & 0 & \cdots & 0 \\
\vdots & & & \vdots \\
0 & 0 & \cdots & 0 \\
\sigma_jv_{j1} & \sigma_jv_{j2} & \cdots & \sigma_jv_{jn} \\
0 & 0 & \cdots & 0 \\
\vdots & & & \vdots \\
0 & 0 & \cdots & 0 \\
\end{pmatrix}$$
(perceba que os zeros da segunda matriz fazem o $u_j$ ser o único a contribuir neste produto)
$$=\sigma_j
\begin{pmatrix}
u_{j1} \\
u_{j2} \\
\vdots \\
u_{jn}
\end{pmatrix}
\begin{pmatrix}
v_{j1} & v_{j2} & \cdots & v_{jn}
\end{pmatrix}=\sigma_ju_jv_j^T.$$Somando todas as parcelas resulta
$$A=\sum_{j=1}^r{\sigma_ju_jv_j^T}.$$
-
A hipótese dos valores singulares serem positivos é estranha. Se isto significa que $A$ tem posto máximo, o sistema linear $Ax=b$ tem solução, como vimos no Exer. 24 – Qualificação, o que torna desnecessário falar em ”quadrados mínimos”. Caso contrário, não era necessário colocar tal hipótese.
O que vou fazer então é ignorar aquela hipótese, supor que $A$ tem posto $r$ e mostrar um processo para resolver o problema de mínimos quadrados para um sistema $Ax=b$.
Novamente por decomposição em valores singulares na forma reduzida, $A_{m\times n}=U_{m\times r}\Sigma_{r\times r}(V^T)_{r\times n}$. Como as colunas da matriz $U$ são vetores ortonormais, sabemos que $UU^T=P$ é a projeção ortogonal sobre o espaço gerado pelas colunas de $U$, que é o mesmo que a imagem de $A$, pois $AV=U\Sigma$ e as matrizes $\Sigma$ e $V$ não interferem no espaço imagem de $U$ e de $A$, respectivamente.
Resolver o problema de mínimos quadrados para $Ax=b$ é fazer a projeção ortogonal de $b$ sobre a imagem de $A$, ou seja, encontrar $x$ tal que $Ax=y$, onde $y=Pb$.
$$y=Pb,$$
$$Ax=UU^Tb,$$
$$U\Sigma V^Tx=UU^Tb,$$
$$\Sigma V^Tx=U^Tb,$$
$$V^Tx=\Sigma^{-1}U^Tb,$$
$$x=V\Sigma^{-1}U^Tb.$$Observação: Existe $\Sigma^{-1}$ somente nesta forma reduzida da SVD, em que a ordem da $\Sigma$ é o posto de $A$.