Álgebra Linear Computacional

Aula 19: Sistemas Lineares (Decomposicões LU e Cholesky)

Heitor S. Ramos
ramosh@dcc.ufmg.br

Créditos

Important

Esses slides são fortemente baseados no livro do prof. Frederico Ferreira Campos, Filho

Decomposição \(LU\)

  • Uma matriz quadrada pode ser escrita como o produto de duas matrizes: \[ A = \begin{bmatrix} 4&3\\ 8&5 \end{bmatrix} = \begin{bmatrix} 1&0\\ 2&1 \end{bmatrix} \begin{bmatrix} 4&3 \\ 0 & -1 \end{bmatrix} \]

  • A matriz \(A\) foi fatorada de modo que \(A = LU\)

  • \(L\) é uma matriz triangular inferior unitária (\(l_{ii}=1, \forall i\))

  • \(U\) é uma matriz triangular superior

  • Para resolver o sistema \(Ax=b\) \[ Ax= b\\ LUx = b\\ Ux = y, \text{ então } Ly=b \]

Cálculo dos fatores

  • A matriz pode ser fatorada usando-se o método da eliminação de Gauss
  • A matriz triangular superior \(U\) é a mesma do método de Gauss
  • A matriz triangular inferior unitária \(L\), além de \(l_{ii}=1, l_{ij} = 0, i<j\), possui \(l_{ij} = m_{ij}, i>j\), sendo \(m_{ij}\) os multiplicadores usados no processo de eliminação de Gauss

Exemplo de decomposição \(LU\)

  • Resolva o sistema a seguir usando a decomposição \(LU\)

\[ \begin{bmatrix} 1 &-3 & 2\\ -2 & 8 & -1 \\ 4 & -6 & 5 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 11\\ -15\\ 29 \end{bmatrix} \]

  • \(m_{21} = (-2)/1 = -2\)
  • \(m_{31} = 4/1 = 4\)

Eliminando os elementos da primeira coluna \[ U = \begin{bmatrix} 1 &-3 & 2\\ 0 & 2 & 3 \\ 0 & 6 & -3 \end{bmatrix} \]

Eliminando os elementos da segunda coluna

  • \(m_{32} = 6/2 = 3\)

\[ U = \begin{bmatrix} 1 &-3 & 2\\ 0 & 2 & 3 \\ 0 & 0 & -12 \end{bmatrix} \]

Sendo assim,

\[ L = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0 \\ 4 & 3 & 1 \end{bmatrix} \]

Então, temos que

\[ A = \begin{bmatrix} 1 &-3 & 2\\ -2 & 8 & -1 \\ 4 & -6 & 5 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0 \\ 4 & 3 & 1 \end{bmatrix} \begin{bmatrix} 1 &-3 & 2\\ 0 & 2 & 3 \\ 0 & 0 & -12 \end{bmatrix} \]

Resolvendo o sistema, temos

\(Ly = b\)

\[ \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0 \\ 4 & 3 & 1 \end{bmatrix} \begin{bmatrix} y_1\\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 11\\ -15\\ 29 \end{bmatrix} \]

  • solução intermediária (em y): \(y = \begin{bmatrix}11 & 7 & -36 \end{bmatrix}^\top\)

  • Usando substituições retroativas:

\[ \begin{bmatrix} 1 &-3 & 2\\ 0 & 2 & 3 \\ 0 & 0 & -12 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 11 \\ 7 \\ -36 \end{bmatrix} \]

  • Vetor solução (em x): \(x = \begin{bmatrix}2 & -1 & 3\end{bmatrix}^\top\)

Observações sobre a decomposição \(LU\)

  • Diferença para eliminação de Gauss: ausência da coluna relativa a \(b\) nas operações l-elementares
  • Efetuar as substituições sucessivas para resolver \(Ly=b\) na decomposição é o mesmo que fazer as operações l-elementares em \(b\) na decomposição de Gauss
  • A solução de \(Ly=b\) funciona como uma memória de cálculo para ser efetuada sobre o vetor \(b\)
  • Resolver vários sistemas lineares com a mesma matriz dos coeficientes com a fatoração da matriz feita uma única vez

Pivotação parcial

  • Evitar pivô nulo
  • Evitar multiplicadores com valores muito grandes
  • Decomposição da forma \[ PA = LU \]
  • \(P\) é a matriz de permutações
  • \(L\) é a matriz triangular inferior unitária formada pelos multiplicadores \(m_{ij}\)
  • \(U\) é a matriz triangular superior
  • Resolver o sistema \(Ax = b\) \[ Ax = b \\ PAx = Pb \\ LUx = Pb\\ Ux = y, \text{ então } Ly = Pb \]

Exemplo de decomposição \(LU\)

Resolver o sistema abaixo pela decomposição \(LU\) usando pivotação parcial

\[ \begin{bmatrix} 1 &-3 & 2\\ -2 & 8 & -1 \\ 4 & -6 & 5 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 11\\ -15\\ 29 \end{bmatrix} \]

  • \(m_{11} = 1/4 = 0,25\)
  • \(m_{21} = -2/4 = -0,5\)

Eliminando a primeira coluna:

\[ U = \begin{bmatrix} 0 &-1,5 & 0,75\\ 0 & 5 & 1,5 \\ 4 & -6 & 5 \end{bmatrix} \]

  • \(m_{12} = -1,5/5 = -0,3\)

Eliminando a segunda coluna: \[ U = \begin{bmatrix} 0 & 0 & 1,2\\ 0 & 5 & 1,5 \\ 4 & -6 & 5 \end{bmatrix} \]

Reescrevendo \[ U = \begin{bmatrix} 4 & -6 & 5 \\ 0 & 5 & 1,5 \\ 0 & 0 & 1,2 \end{bmatrix} \]

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ -0,5 & 1 & 0 \\ 0,25 & -0,3 & 1 \end{bmatrix} \]

\[ P= \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \]

  • Solução de \(Ly = Pb\)

  • Vetor \(Pb\) é formado pelos elementos de \(b\) dispostos na ordem das linhas contidas \(U\)

  • Solução de \(Ly=Pb\) via substituições sucessivas

\[ \begin{bmatrix} 1 & 0 & 0 \\ -0,5 & 1 & 0 \\ 0,25 & -0,3 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 11\\ -15\\ 29 \end{bmatrix} \]

\[ \begin{bmatrix} 1 & 0 & 0 \\ -0,5 & 1 & 0 \\ 0,25 & -0,3 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 29\\ -15\\ 11 \end{bmatrix} \]

  • Vetor intermediário (em \(y\)): \(y = \begin{bmatrix}29 & -0,5 & 3,6\end{bmatrix}^\top\)

  • Solução de \(Ux=y\) pelas substituições retroativas

\[ \begin{bmatrix} 4 & -6 & 5 \\ 0 & 5 & 1,5 \\ 0 & 0 & 1,2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 29\\ -0,5 \\ 3,6 \end{bmatrix} \]

  • Solução (em \(x\)): \(x = \begin{bmatrix}2 &-1 &3\end{bmatrix}^\top\)

  • Vetor resíduo

\[ r = b - Ax\]

\[ r = \begin{bmatrix} 11 \\ -15 \\ 29 \end{bmatrix} - \begin{bmatrix} 1 &-3 & 2\\ -2 & 8 & -1 \\ 4 & -6 & 5 \end{bmatrix} \begin{bmatrix} 2 \\ -1 \\ 3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

Solução exata!

Cálculo do determinante

  • Pelas propriedades dos determinantes

\[ PA = LU \\ \text{det}(PA) = \text{det}(LU) \\ \text{det}(A) = \frac{\text{det}(L)\text{det}(U)}{\text{det}(P)}\\ \text{det}(L) = \prod_{i=1}^n l_{ii} = 1\\ \text{det}(U) = \prod_{i=1}^n u_{ii} \\ \text{det}(P) = (-1)^t\\ \] onde \(t\) é o número de trocas de linhas necessárias para transformar a matriz de permutação \(P\) em uma matriz identidade

Assim,

\[ \text{det}(A) = (-1)^t\prod_{i=1}^n u_{ii}\\ \]

Exemplo de cálculo de determinante

Calcular o determinante de

\[ A = \begin{bmatrix} 1 &-3 & 2\\ -2 & 8 & -1 \\ 4 & -6 & 5 \end{bmatrix} \]

Matrizes \(U\) e \(P\)

\[ U = \begin{bmatrix} 4 & -6 & 5 \\ 0 & 5 & 1,5 \\ 0 & 0 & 1,2 \end{bmatrix} P= \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} \]

Valor de \(t\)

t Linhas Pivotais Comentário
0 3 2 1 trocar 3 com 1
1 1 2 3 ordem crescente

Cálculo do determinante

\[ \text{det}(A) = (-1)^t\prod_{i=1}^3 u_{ii} = (-1)^1\cdot 4 \cdot 5 \cdot 1,2 = -24 \]

Exemplo

Resolver o sistema a seguir pela decomposição \(LU\) usando pivotação parcial e verificar a exatidão e unicidade da solução

\[ \begin{bmatrix} 4 & -1 & 0 & -1 \\ 1 & -2 & 1 & 0 \\ 0 & 4 & -4 & 1 \\ 5 & 0 & 5 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \\ -3 \\ 4 \end{bmatrix} \]

Resposta:

Vetor de permutação: \(p = \begin{bmatrix}4 & 3 & 1 & 2\end{bmatrix}\) \[ L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0,8 & -0,25 & 1 & 0 \\ 0,2 & -0,5 & 0,4 & 1 \end{bmatrix} \] \[ U = \begin{bmatrix} 5 & 0 & 5 & -1 \\ 0 & 4 & -4 & 1 \\ 0 & 0 & -5 & 0,05 \\ 0 & 0 & 0 & 0,68 \end{bmatrix} \] \[ P = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \]

Solução: \[x = \begin{bmatrix}-0,6617 & 0,9412& 0,5441 & -4,5882 \end{bmatrix}^\top \]

Verificar exatidão da solução \(r = b - Ax\)

\[ r = \begin{bmatrix} 1 \\ -2 \\ -3 \\ 4 \end{bmatrix} - \begin{bmatrix} 4 & -1 & 0 & -1 \\ 1 & -2 & 1 & 0 \\ 0 & 4 & -4 & 1 \\ 5 & 0 & 5 & -1 \end{bmatrix} \begin{bmatrix} -0,6617 \\ 0,9412 \\ 0,5441 \\ -4,5882 \end{bmatrix} = \begin{bmatrix} -0,0002 \\ 0,0000 \\ -0,0002 \\ -0,0002 \end{bmatrix} \]

Solução quase exata

  • Verificar unicidade da solução

Valor de \(t\)

t Linhas Pivotais Comentário
0 4 3 1 2 trocar 4 com 1
1 1 3 4 2 trocar 3 com 2
2 1 2 4 3 trocar 4 com 3
3 1 2 3 4 ordem crescente
  • Determinante: \[ \text{det}(A) = (-1)^t\prod_{i=1}^4 u_{ii} \\ \text{det}(A) = (-1)^4\cdot 5 \cdot 4 \cdot -5 \cdot 0,68 = 68 \]

Solução única

Sistema com matriz singular

  • Infinitas soluções ou
  • Não tem solução

Exemplo

Resolver os sistemas \(Ax = b\) e \(Ax =c\) usando decomposição \(LU\) com pivotação parcial, sendo

\[ A = \begin{bmatrix} 1 & -3 & 2 \\ -2 & 8 & -1 \\ -1 & 5 & 1 \end{bmatrix}, b = \begin{bmatrix} 22 \\ -12 \\ 10 \end{bmatrix}, c = \begin{bmatrix} 20 \\ -10 \\ 80 \end{bmatrix} \]

Decomposição de Cholesky

  • Matriz de coeficientes \(A\) simétrica e definida positiva \[ v^\top A v >0, \forall v\neq 0 \]

  • \(A\) pode ser decomposta tal que \[ A = LL^\top \]

  • \(L\) é triangular inferior

  • \(L^\top\) é triangular superior

Decomposição de Cholesky

Teorema (Cholesky)

Se \(A\) for uma matriz simétrica e definida positiva, então existe uma única matriz triangular \(L\) com elementos da diagonal positivos tal que \(A= LL^\top\)

  • Produto \(LL^\top = A\) de uma matriz de ordem 4

\[ \begin{bmatrix} l_{11} & 0 & 0 & 0 \\ l_{21} & l_{22} & 0 & 0 \\ l_{31} & l_{32} & l_{33} & 0 \\ l_{41} & l_{42} & l_{43} & l_{44} \\ \end{bmatrix} \begin{bmatrix} l_{11} & l_{21} & l_{31} & l_{41} \\ 0 & l_{22} & l_{32} & l_{42} \\ 0 & 0 & l_{33} & l_{43} \\ 0 & 0 & 0 & l_{44} \\ \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \\ \end{bmatrix} \]

Cálculo dos fatores

\[ \begin{bmatrix} l_{11} & 0 & 0 & 0 \\ l_{21} & l_{22} & 0 & 0 \\ l_{31} & l_{32} & l_{33} & 0 \\ l_{41} & l_{42} & l_{43} & l_{44} \\ \end{bmatrix} \begin{bmatrix} l_{11} & l_{21} & l_{31} & l_{41} \\ 0 & l_{22} & l_{32} & l_{42} \\ 0 & 0 & l_{33} & l_{43} \\ 0 & 0 & 0 & l_{44} \\ \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \\ \end{bmatrix} \]

  • Calculo de \(l_{44}\) \[ l^2_{41} + l^2_{42} + l^2_{43} + l^2_{44} = a_{44} \\ l_{44} = \sqrt{a_{44} - (l^2_{41} + l^2_{42} + l^2_{43})}\\ l_{44} = \sqrt{a_{44} - \sum_{k=1}^3 l^2_{4k}} \]

  • Elemento de qualquer diagonal

\[ l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l^2_{jk}}, \] onde \(j = 1, 2, \ldots, n\)

  • Elemento \(l_{43}\) abaixo da diagonal

\[ l_{41}l_{31} + l_{42}l_{32} + l_{43}l_{33} = a_{43} \\ l_{43} = \frac{a_{43} - (l_{41}l_{31} + l_{42}l_{32})}{l_{33}}\\ l_{43} = \frac{a_{43} - \sum_{k=1}^2 l_{4k}l_{3k}}{l_{33}} \]

  • Elemento genérico abaixo da diagonal principal

\[ l_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk}}{l_{jj}}, \] onde \(j=1,2,\ldots,n-1\) e \(i=j+1,j+2,\ldots,n\)

Solução do sistema \(Ax = b\) pela decomposição de Cholesky

Seja \[ Ax = b\\ LL^\top x = b\\ L^\top x =y, \text{ então } Ly=b \]

Sistema triangular inferior \(Ly=b\) resolvido pelas substituições sucessivas

\[ y_i = \frac{\left( b_i - \sum_{j=1}^{i-1} l_{ij}y_j\right)}{l_{ii}}, \] onde \(i=1,2,\ldots,n\)

Sistema triangular superior \(L^\top x=y\) resolvido pelas substituições retroativas

\[ x_i = \frac{\left( y_i - \sum_{j=i+1}^{n} l_{ji}x_j\right)}{l_{ii}}, \] onde \(i=1,2,\ldots,n\)

Cálculo do determinante

Pela propriedade dos determinantes

\[ \text{det}(A) = \text{det}(L)\text{det}(L^\top) \]

\[ \text{det}(A) = \left(\prod_{i=1}^n l_{ii} \right)^2 \]

Exemplo da decomposição de Cholesky

Resolver o sistema a seguir usando a decomposição de Cholesky e verificar a exatidão e unicidade da solução

\[ \begin{bmatrix} 4 & -2 & 2 \\ -2 & 10 & -7 \\ 2 & -7 & 30 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \begin{bmatrix} 8 \\ 11 \\ -31 \end{bmatrix} \]

  • Coluna 1:

\[ l_{11} = \sqrt{a_{11}} = \sqrt{4} = 2\\ l_{21} = \frac{a_{21}}{l_{11}} = \frac{-2}{2} = -1\\ l_{31} = \frac{a_{31}}{l_{11}} = \frac{2}{2} = 1 \]

  • Coluna 2:

\[ l_{22} = \sqrt{a_{22}-l^2_{21}} = \sqrt{10 - (-1)^2} = 3\\ l_{32} = \frac{a_{32} - l_{31}l_{21}}{l_{22}}= \frac{-7-(-1)(-1)}{3} = -2\\ \]

  • Coluna 3: \[ l_{33} = \sqrt{a_{33} - (l^2_{31}+l^2_{32})} = \sqrt{30 - ((-1)^2 + (-2)^2)} = 5 \]

\[ \begin{bmatrix} 4 & -2 & 2 \\ -2 & 10 & -7 \\ 2 & -7 & 30 \end{bmatrix} = \begin{bmatrix} 2 & 0 & 0 \\ -1 & 3 & 0 \\ 1 & -2 & 5 \end{bmatrix} \begin{bmatrix} 2 & -1 & 1 \\ 0 & 3 & -2 \\ 0 & 0 & 5 \end{bmatrix} \]

Solução dos sistemas triangulares

Sistema \(Ly=b\)

\[ \begin{bmatrix} 2 & 0 & 0 \\ -1 & 3 & 0 \\ 1 & -2 & 5 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 8 \\ 11 \\ -31 \end{bmatrix} \]

  • Solução intermediária: \(y = \begin{bmatrix}4 & 5 & -5\end{bmatrix}^\top\)

Sistema \(L^\top x = y\)

\[ \begin{bmatrix} 2 & -1 & 1 \\ 0 & 3 & -2 \\ 0 & 0 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 4 \\ 5 \\ -5 \end{bmatrix} \]

  • Solução: \(x = \begin{bmatrix}3 & 1 & -1\end{bmatrix}^\top\)

  • Verificação da exatidão e unicidade da solução

Vetor resíduo \(r = b - Ax\)

\[ r = \begin{bmatrix} 8 \\ 11 \\ -31 \end{bmatrix} - \begin{bmatrix} 4 & -2 & 2 \\ -2 & 10 & -7 \\ 2 & -7 & 30 \end{bmatrix} \begin{bmatrix}3 \\ 1 \\ -1\end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} \]

Solução exata!

  • Cálculo do determinante

\[ \text{det}(A) = \left(\prod_{i=1}^n l_{ii} \right)^2 = \left( 2\cdot 3 \cdot 5)\right)^2 = 900 \]

Solução única!

https://heitorramos.github.io/alc.html