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
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
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 parcials \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:
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 parcials \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
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.