Desenvolva um algoritmo que utilize as matrizes L e U (obtidas pelo algoritmo desenvolvido em sala de aula) para resolver os sistemas \mathrm{LY}=\mathrm{B} e \mathrm{UX}=\mathrm{Y}
OBS : lembrem-se que neste caso não é necessário fazer escalonamento, pois as matrizes dos coeficientes são triangulares.

Passo 1

O enunciado pede para construir um algoritmo que, dadas as matrizes L e U (triangulares) obtidas pelo método de fatoração LU, resolva os dois sistemas triangulares
L Y = B
e
U X = Y.
Informações relevantes fornecidas:
\text{dados: } L,\; U,\; B,
onde L é triangular inferior e U é triangular superior. Foi observado que não é necessário escalonamento porque as matrizes são triangulares. A tarefa é produzir um procedimento passo a passo (algoritmo) que calcule Y e depois X.

Passo 2

Entendendo o primeiro sistema L Y = B (substituição direta ou forward substitution).
  • O que significa que L é triangular inferior? Significa que todos os elementos acima da diagonal de L são zero: para i<j temos L_{ij}=0. Assim a equação matricial pode ser escrita componente a componente como
\sum_{j=1}^{i} L_{ij}\,Y_j = B_i,\qquad i=1,2,\dots,n.
  • Como isolar Y_i? Observe que, ao resolver as equações na ordem i=1,2,\dots,n, a soma acima envolve apenas Y_1,\dots,Y_i; então quando chegarmos a i já conhecemos Y_1,\dots,Y_{i-1} e podemos isolar Y_i:
L_{ii}\,Y_i = B_i - \sum_{j=1}^{i-1} L_{ij}\,Y_j.
  • Se L tem diagonal unária (caso comum em fatoração LU where L_{ii}=1), a fórmula simplifica para
Y_i = B_i - \sum_{j=1}^{i-1} L_{ij}\,Y_j.
  • Se L_{ii}\neq 1, então
Y_i = \frac{1}{L_{ii}}\left(B_i - \sum_{j=1}^{i-1} L_{ij}\,Y_j\right).
  • Sempre verifique que L_{ii}\neq 0. Se for zero, não é possível dividir e o algoritmo falha (isso indica que a fatoração LU sem pivoteamento não foi adequada).

Passo 3

Algoritmo detalhado (forward substitution) com explicação de cada passo e notação:
  • Inicialize um vetor Y com n componentes.
  • Para i variando de 1 até n:
    • Calcule a soma parcial s \leftarrow \sum_{j=1}^{i-1} L_{ij}\,Y_j.Explicação: aqui multiplicamos os elementos já conhecidos de Y pelas entradas correspondentes de L na linha i.
    • Subtraia da entrada de B: r \leftarrow B_i - s.
    • Divida pelo pivô diagonal: Y_i \leftarrow \frac{r}{L_{ii}}.Observação: se L_{ii}=1, essa divisão é desnecessária e podemos usar Y_i \leftarrow r.
  • Depois do loop, Y é solução do sistema L Y = B.
Complexidade: esse processo faz aproximadamente \tfrac{n(n-1)}{2} multiplicações/somas, ou seja, O(n^2).

Passo 4

Exemplo didático (pequeno) para fixar a ideia — suponha que os dados na imagem ou no enunciado não existam, então eu uso um exemplo explícito:
Considere
L=\begin{pmatrix} 1 & 0 & 0\\[4pt] 2 & 1 & 0\\[4pt] -1 & 3 & 1 \end{pmatrix},\qquad B=\begin{pmatrix}4\\[4pt]1\\[4pt]7\end{pmatrix}.
(Isto é um exemplo numérico para ilustrar; se você tiver L e B diferentes, aplique os mesmos passos.)
Resolvendo L Y = B por forward substitution:
  • i=1: Y_1 = B_1 = 4(porque a soma é vazia e L_{11}=1).
  • i=2: s = L_{21}Y_1 = 2\cdot 4 = 8,
Y_2 = B_2 - s = 1 - 8 = -7.
  • i=3: s = L_{31}Y_1 + L_{32}Y_2 = (-1)\cdot 4 + 3\cdot(-7) = -4 -21 = -25,
Y_3 = B_3 - s = 7 - (-25) = 32.
Resultado: Y = (4,\,-7,\,32)^T.]

Passo 5

Entendendo o segundo sistema U X = Y (substituição retrógrada ou backward substitution).
  • U é triangular superior: para i>j temos U_{ij}=0. Componente a componente:
\sum_{j=i}^{n} U_{ij}\,X_j = Y_i,\qquad i=1,2,\dots,n.
  • Para isolar X_i resolvemos as equações de i=n até 1. Para um índice genérico i a soma se escreve como
U_{ii}\,X_i + \sum_{j=i+1}^{n} U_{ij}\,X_j = Y_i.
Como já conhecemos X_{i+1},\dots,X_n (porque resolvemos os índices maiores antes), podemos isolar
X_i = \frac{1}{U_{ii}}\left(Y_i - \sum_{j=i+1}^{n} U_{ij}\,X_j\right).
  • Novamente, verifique U_{ii}\neq 0. Se U_{ii}=0, não é possível dividir.

Passo 6

Algoritmo detalhado (backward substitution) com explicação:
  • Inicialize um vetor X com n componentes.
  • Para i variando de n até 1 (decrescendo):
    • Calcule a soma parcial s \leftarrow \sum_{j=i+1}^{n} U_{ij}\,X_j.Explicação: multiplicamos os X_j já conhecidos pelos coeficientes correspondentes da linha i de U.
    • Subtraia de Y_i: r \leftarrow Y_i - s.
    • Divida pelo pivô diagonal: X_i \leftarrow \frac{r}{U_{ii}}.
  • Ao final, X é a solução de U X = Y.
Complexidade: também aproximadamente \tfrac{n(n-1)}{2} operações, ou seja, O(n^2).

Passo 7

Exemplo de backward usando o Y do passo anterior e um U de exemplo (seguindo o exemplo anterior):
Suponha
U=\begin{pmatrix} 2 & -1 & 0\\[4pt] 0 & 3 & 1\\[4pt] 0 & 0 & 4 \end{pmatrix},\qquad Y=\begin{pmatrix}4\\[4pt]-7\\[4pt]32\end{pmatrix}.
Resolva U X = Y:
  • i=3: X_3 = \frac{Y_3}{U_{33}} = \frac{32}{4} = 8.
  • i=2: s = U_{23}X_3 = 1\cdot 8 = 8,
X_2 = \frac{Y_2 - s}{U_{22}} = \frac{-7 - 8}{3} = \frac{-15}{3} = -5.
  • i=1: s = U_{12}X_2 + U_{13}X_3 = (-1)\cdot(-5) + 0\cdot 8 = 5,
X_1 = \frac{Y_1 - s}{U_{11}} = \frac{4 - 5}{2} = \frac{-1}{2} = -\tfrac{1}{2}.
Resultado: X = (-\tfrac{1}{2},\,-5,\,8)^T.]

Passo 8

Pseudocódigo do algoritmo completo (combina forward e backward). Aqui está legível e pronto para implementação; todas as variáveis estão em notação matemática para você poder transcrever diretamente:
Defina n como a ordem de L e U. Suponha vetores/matrizes indexados a partir de 1.
Forward substitution (computar Y):
\text{para } i=1 \text{ até } n \text{ faça}éç
\quad s \leftarrow 0
\quad \text{para } j=1 \text{ até } i-1 \text{ faça } s \leftarrow s + L_{ij}\,Y_jéç
\quad r \leftarrow B_i - s
\quad \text{se } L_{ii}=0 \text{ então erro: pivô zero}ãô
\quad Y_i \leftarrow \dfrac{r}{L_{ii}}
\text{fim para}
Backward substitution (computar X):
\text{para } i=n \text{ até } 1 \text{ faça}éç
\quad s \leftarrow 0
\quad \text{para } j=i+1 \text{ até } n \text{ faça } s \leftarrow s + U_{ij}\,X_jéç
\quad r \leftarrow Y_i - s
\quad \text{se } U_{ii}=0 \text{ então erro: pivô zero}ãô
\quad X_i \leftarrow \dfrac{r}{U_{ii}}
\text{fim para}
Observações finais:
  • Complexidade total: O(n^2) para resolver ambos os sistemas.
  • Cheque pivôs diagonais L_{ii} e U_{ii} antes de dividir; idealmente na fatoração LU sem pivoteamento você tem pivôs não nulos, mas é bom validar.
  • Se tiver múltiplos vetores B (colonas de uma matriz B com várias colunas), aplique a forward substitution para cada coluna de B para obter as correspondentes colunas de Y, e depois a backward substitution em cada coluna de Y para obter X — a estrutura do algoritmo permanece a mesma.
Força aí — na prova faça com calma: primeiro forward (de cima para baixo), depois backward (de baixo para cima). Se errar um índice, você perde tudo; controle os laços e os pivôs.

Resposta

Forward substitution:
\text{para } i=1\text{ até }n:\quad Y_i \leftarrow \dfrac{1}{L_{ii}}\Bigl(B_i - \sum_{j=1}^{i-1} L_{ij}\,Y_j\Bigr)é
Backward substitution:
\text{para } i=n\text{ até }1:\quad X_i \leftarrow \dfrac{1}{U_{ii}}\Bigl(Y_i - \sum_{j=i+1}^{n} U_{ij}\,X_j\Bigr)é

Exercícios relacionados