Descreva os principais passos da decomposição LU.

Passo 1

Você pediu: “Descreva os principais passos da decomposição LU.”\n
Informações/dados que o enunciado dá (ou que vou assumir para responder): \n
  • Temos uma matriz quadrada \;A\; de dimensão n\times n.\n
  • O objetivo é obter matrizes triangulares \;L\; (inferior) e \;U\; (superior) tais que \;A = LU\; (ou, quando houver permutações, \;PA = LU\;).\n
  • Você quer os passos principais — isto é, o procedimento prático, as fórmulas usadas, como resolver sistemas com a decomposição e cuidados (pivotamento, existência).

Passo 2

O que é a decomposição LU (explicação simples e intuitiva).\n
  • A decomposição LU é escrever \;A\; como o produto de uma matriz triangular inferior \;L\; e uma triangular superior \;U\;: \;A = LU.\n
  • Convenção comum (Doolittle): \;L\; tem diagonal formada por 1s, isto é \;l_{ii}=1\; e \;L\; guarda os multiplicadores usados na eliminação; \;U\; é a forma resultante da eliminação (como a matriz escalonada superior).\n
  • Por que isso é útil? Porque, uma vez que temos \;A=LU\;, resolver \;A x = b\; reduz-se a resolver duas substituições triangulares: \;L y = b\; (forward) e \;U x = y\; (back).

Passo 3

Relação com eliminação de Gauss — ideia central (sem fórmulas pesadas ainda).\n
  • Fazer eliminação de Gauss para zerar elementos abaixo da diagonal da matriz \;A\; equivale a multiplicar \;A\; por matrizes elementares; se registrarmos os multiplicadores usados em cada etapa, esses multiplicadores formam \;L\; e o resultado da eliminação é \;U\;.\n
  • Em termos práticos: a entrada l_{ik} (para i>k) é o multiplicador que usamos na etapa k para anular a_{ik} (o elemento na linha i, coluna k): \;l_{ik}=\text{multiplicador usado para zerar }a_{ik}.

Passo 4

Algoritmo Doolittle (fórmulas explicadas passo a passo).\n
  • Objetivo: calcular \;L\; e \;U\; linha a linha/coluna a coluna. Use índices k de 1 a n.\n
  • Inicialize \;l_{ii}=1\; para todo i.\n
  • Para k=1,2,\dots,n faça:\n
    1. Calcule as entradas da linha k de \;U\; para j=k,k+1,\dots,n:\n u_{kj} \;=\; a_{kj} \;-\; \sum_{s=1}^{k-1} l_{ks}\,u_{sj}.\n
    2. Calcule as entradas da coluna k de \;L\; para i=k+1,k+2,\dots,n:\n l_{ik} \;=\; \frac{1}{u_{kk}} \left( a_{ik} \;-\; \sum_{s=1}^{k-1} l_{is}\,u_{sk} \right).\n
  • Interpretação das fórmulas: quando calculamos u_{kj} subtraímos as contribuições já computadas (produto L U parcial) para obter o novo coeficiente. Para l_{ik} usamos o pivô u_{kk} para normalizar o multiplicador.\n
  • Condição importante: precisamos de u_{kk}\neq 0 em cada etapa; caso contrário, deve-se pivotar (trocar linhas).

Passo 5

Pivotamento e permutações (quando e por que trocar linhas).\n
  • Problema: se em alguma etapa u_{kk}=0 (ou é muito pequeno numericamente), divisão por u_{kk} é impossível (ou instável).\n
  • Solução prática: fazer pivotamento por linhas (partial pivoting). Troca-se a linha k pela linha p\ge k que maximiza |a_{p k}| (ou o valor absoluto do elemento atual na coluna) antes de continuar. Registramos essa troca numa matriz de permutação \;P\;.\n
  • Resultado final com pivotamento: \;P A = L U.\n
  • No cálculo, ao permutar linhas, os multiplicadores no \;L\; correspondem às operações já feitas nas linhas permutadas — ou seja, calcula-se a decomposição sobre a matriz permutada.

Passo 6

Variações: Crout, Doolittle e Cholesky (quando usar cada uma).\n
  • Doolittle: \;l_{ii}=1\;. Fórmulas dadas no Passo 4.\n
  • Crout: \;u_{ii}=1\; — neste caso as fórmulas são ligeiramente diferentes (preenche-se coluna de L primeiro).\n
  • Cholesky: quando \;A\; é simétrica definida positiva, existe decomposição especial \;A = LL^{T}\; com L tendo diagonal positiva. Cholesky é mais eficiente (cerca de metade das operações) e numericamente estável para esse caso.

Passo 7

Como usar a decomposição para resolver \;A x = b\; (passo-a-passo das substituições).\n
  • Suponha que já temos \;A = LU\; (ou \;PA = LU\; e permutamos b adequadamente).\n- 1ª etapa (forward substitution): resolva \;L y = b\; para y usando\n y_1 = b_1,\qquad y_i = b_i - \sum_{s=1}^{i-1} l_{is}\,y_s\quad (i=2,\dots,n).\n
  • 2ª etapa (back substitution): resolva \;U x = y\; para x usando\n x_n = \frac{y_n}{u_{nn}},\qquad x_i = \frac{1}{u_{ii}}\Big( y_i - \sum_{s=i+1}^{n} u_{is}\,x_s\Big)\quad (i=n-1,\dots,1).\n
  • Vantagem: se precisar resolver \;A x = b\; para vários vetores \;b\;, computa-se \;L e \;U\; uma única vez e reaplica-se as substituições (muito eficiente).

Passo 8

Exemplo numérico completo (3×3) — eu mostro cada conta para você “mastigar”.\n
Considere a matriz (exemplo escolhido)
A = \begin{pmatrix} 2 & 3 & 1 \\[4pt] 4 & 7 & 7 \\[4pt] -2 & 4 & 5 \end{pmatrix}.\n
Vamos decompor A usando Doolittle (ou seja, l_{11}=l_{22}=l_{33}=1).\n
  • Etapa k=1:\n u_{11} = a_{11} = 2,\quad u_{12}=a_{12}=3,\quad u_{13}=a_{13}=1.\n\n l_{21} = a_{21}/u_{11} = 4/2 = 2,\quad l_{31} = a_{31}/u_{11} = (-2)/2 = -1.\n\n- Etapa k=2:\n u_{22} = a_{22} - l_{21} u_{12} = 7 - 2\cdot 3 = 1.\n\n u_{23} = a_{23} - l_{21} u_{13} = 7 - 2\cdot 1 = 5.\n\n l_{32} = \dfrac{a_{32} - l_{31} u_{12}}{u_{22}} = \dfrac{4 - (-1)\cdot 3}{1} = 7.\n\n- Etapa k=3:\n u_{33} = a_{33} - l_{31} u_{13} - l_{32} u_{23} = 5 - (-1)\cdot 1 - 7\cdot 5 = 5 + 1 - 35 = -29.\n\nAssim obtém-se\n L = \begin{pmatrix}1 & 0 & 0 \\[4pt] 2 & 1 & 0 \\[4pt] -1 & 7 & 1\end{pmatrix}, \qquad U = \begin{pmatrix}2 & 3 & 1 \\[4pt] 0 & 1 & 5 \\[4pt] 0 & 0 & -29\end{pmatrix}.\n
Verificação rápida: multiplicando L U recobra-se A (experimente na prova ou no rascunho — é um cálculo direto).\n
Exemplo de uso: suponha que o vetor solução real seja \;x = (1,2,3)^{T} e calculemos \;b = A x\; (para testar a solução inversa):\n b = \begin{pmatrix}11\\[4pt]39\\[4pt]21\end{pmatrix}.\n
Agora, com L e U encontrados, resolvemos L y = b:\n y_1 = 11,\quad y_2 = 39 - 2\cdot 11 = 17,\quad y_3 = 21 - (-1)\cdot 11 - 7\cdot 17 = -87.\n
E depois U x = y:\n x_3 = \frac{-87}{-29} = 3,\quad x_2 = 17 - 5\cdot 3 = 2,\quad x_1 = \frac{11 - 3\cdot 2 - 1\cdot 3}{2} = 1.\n
Recuperamos \;x=(1,2,3)^{T} — perfeito. Esse exemplo mostra como os multiplicadores entram em L e como a solução é obtida rapidamente.]

Passo 9

Condições de existência e problemas numéricos (o que olhar na prova).\n
  • Nem toda matriz tem decomposição LU sem permutações; requisito suficiente simples: se todos os principais menores leading (determinantes dos sub-blocos k\times k no canto superior esquerdo) são não nulos, a decomposição sem permutações existe.\n- Na prática numérica usamos pivotamento parcial; com pivotamento parcial a decomposição existe para muitas matrizes usadas em aplicações e é numericamente estável para a maioria dos casos.\n- Atenção ao condicionamento: se \;A\; é mal condicionada (número de condição grande), os erros de arredondamento podem afetar muito a solução; pivotamento ajuda, mas não resolve condicionamento ruim.

Passo 10

Complexidade e usos práticos (dicas rápidas para prova e exame).\n
  • Custo computacional: decompor uma matriz \;n\times n\; custa \mathcal{O}(n^{3}) operações (aprox. \tfrac{2}{3}n^{3} multiplicações somas para LU sem pivotamento). Resolver A x = b após ter LU custa \mathcal{O}(n^{2}) por RHS (forward + back substitution).\n- Uso prático: quando tiver vários vetores b com mesma A, faz sentido decompor \;A\; uma vez e reutilizar \;L,U\;.\n- Em problemas simétricos definidas positivas, prefira Cholesky (metade do trabalho, mais estável).

Passo 11

Checklist rápido para fazer na prova (passos práticos que você pode decorar)\n
  1. Se necessário, aplique pivotamento parcial para garantir pivôs não-nulos. 2) Para k=1 até n: calcule u_{kj} para j\ge k e depois l_{ik} para i>k usando as fórmulas do Passo 4. 3) Guarde L e U (muitas vezes armazenados na própria matriz A para economizar memória). 4) Para resolver A x=b: primeiro L y=b (forward), depois U x = y (back). 5) Verifique resultados com multiplicação L U ou aplicando A x e comparando com b.

Resposta

  1. Verifique pivôs e, se preciso, aplique pivotamento (obter P tal que PA seja adequada).\n
  2. Use eliminação de Gauss registrando multiplicadores; com Doolittle fixe l_{ii}=1.\n
  3. Para cada k: calcule \;u_{kj}=a_{kj}-\sum_{s=1}^{k-1} l_{ks}u_{sj}\;(j\ge k)\n
  4. Em seguida calcule \;l_{ik}=\dfrac{1}{u_{kk}}\big(a_{ik}-\sum_{s=1}^{k-1} l_{is}u_{sk}\big)\;(i>k)\n
  5. Ao fim obtém-se PA=LU (ou A=LU sem permutações); para resolver Ax=b faça Ly=b (forward) e depois Ux=y (back substitution).\n
  6. Atenção prática: faça pivotamento parcial para estabilidade; se A é simétrica definida positiva, prefira Cholesky ( A=LL^{T}).

Exercícios relacionados