Exercício 3.
Desenvolva na liguagem Scilab, o Algoritmo de substituições retroativas apresentado pelo Algoritmo 2.
Algoritmo 2: Substituições Retroativas
Entradas: \(n, U, c\) /* ordem, matriz triang. sup. e vetor indep. */
Saída: \(x\)
\(x_{n} \leftarrow c_{n} / U_{n n}\)
for ( \(i \leftarrow n-1\), Passo -1 to 1 ) do
Soma \(\leftarrow 0\);
for \((j \leftarrow i+1\) to \(n)\) do
Soma \(\leftarrow\) Soma \(+U_{i j} * x_{j} ;\)
end
\(x_{i} \leftarrow\left(c_{i}\right.\) - Soma \() / U_{i i} ;\)
end
Retorne \(x\);
Algoritmo 2: Substituições Retroativas
Entradas: \(n, U, c\) /* ordem, matriz triang. sup. e vetor indep. */
Saída: \(x\)
\(x_{n} \leftarrow c_{n} / U_{n n}\)
for ( \(i \leftarrow n-1\), Passo -1 to 1 ) do
Soma \(\leftarrow 0\);
for \((j \leftarrow i+1\) to \(n)\) do
Soma \(\leftarrow\) Soma \(+U_{i j} * x_{j} ;\)
end
\(x_{i} \leftarrow\left(c_{i}\right.\) - Soma \() / U_{i i} ;\)
end
Retorne \(x\);Passo 1
O que o exercício pede e quais são os dados:
- O enunciado pede implementar em Scilab o algoritmo de substituições retroativas (back substitution) descrito.
- Entradas:
(ordem), a matriz triangular superior e o vetor independente . - Saída: o vetor solução
que satisfaz . - O algoritmo dado faz:
- calcula
; - para
variando de até (passo ) calcula
- calcula
Passo 2
Intuição e ideia matemática por trás do algoritmo (por que funciona):
- Como
é triangular superior, na última equação do sistema só aparece a incógnita . Escrevendo a última linha: - Depois de obter
, olhamos para a penúltima linha; essa linha envolve e possivelmente . Isolamos : - Repetindo esse processo para cima (retroativamente) obtemos todas as componentes de
. - Observação importante: cada divisão por
exige que . Se algum o algoritmo falha (ou exige pivoteamento/reatribuição do sistema). Na prática usa-se uma tolerância para testar se o valor é numericamente zero.
Passo 3
Detalhes práticos para implementar em Scilab (coisas que você precisa saber sobre a linguagem):
- Scilab usa indexação baseada em 1 (ou seja, o primeiro elemento é
, não ). Isso combina bem com a descrição matemática que usamos. - Estrutura de função em Scilab típica:
function nome = func(arg1, arg2)
// código
endfunction - Laços em Scilab: para contagem decrescente pode-se usar a sintaxe
for i = n-1:-1:1…end - Para criar um vetor coluna zerado use
zeros(n,1). - É recomendado checar:
- se
é quadrada, - se o tamanho de
é compatível com , - se elementos diagonais
não são (numericamente) zero antes de dividir.
- se
- Para somar produtos
pode-se usar um laço forsimples ou uma forma vetorizada; usarei o laço explícito para ficar mais didático e parecido com o pseudocódigo.
Passo 4
Escrevendo o algoritmo em linguagem natural, passo a passo (pré-código):
- Obter
a partir de (número de linhas). - Verificar se
é quadrada e se o comprimento de é . - Inicializar
como vetor coluna de zeros de tamanho . - Definir uma pequena tolerância numérica
(por exemplo ) para testar se um é efetivamente zero. - Calcular
(verificando ). - Para
até (decrescendo): - calcular
(usando um laço). - checar
; então .
- calcular
- Retornar
.
Passo 5
Complexidade e aspectos numéricos rápidos (o que vale lembrar para a prova):
- Complexidade: o algoritmo realiza aproximadamente
multiplicações/adições — portanto é . - Estabilidade: se
provém de uma decomposição LU sem pivoteamento, pode haver zeros ou valores muito pequenos na diagonal; por isso, normalmente na fatoração LU se faz pivoteamento parcial para evitar divisões por números muito pequenos. - Para a implementação prática, testar diagonal com uma tolerância
e lançar erro se .
Passo 6
Um exemplo pequeno e concreto (passo a passo numérico) para fixar a ideia:
- Seja
(Peguei esses números como exemplo para testar o algoritmo.) - Calcular:
-
. -
. Logo . -
. Logo .
-
- Resultado final do exemplo:
. - Esse cálculo é exatamente o que o algoritmo implementado retornará para esses dados de entrada.]
Passo 7
Comentários finais antes do código:
- Vou colocar no código checagens básicas (dimensões, zeros na diagonal com tolerância) e manter a tradução fiel do pseudocódigo original (uso explícito de somas em laços).
- No campo de resposta segue a implementação em Scilab pronta para usar como função.
Resposta
function x = back_substitution(U, c)
// Substituições retroativas: resolve U*x = c para U triangular superior
// Entradas: U (matriz n x n triangular superior), c (vetor n x 1)
// Saída: x (vetor solução n x 1)
// Substituições retroativas: resolve U*x = c para U triangular superior
// Entradas: U (matriz n x n triangular superior), c (vetor n x 1)
// Saída: x (vetor solução n x 1)
[n, m] = size(U);
if n ~= m then
error('Matriz U deve ser quadrada');
end
if size(c, 1) ~= n then
error('Vetor c tem dimensão incompatível com U');
end
x = zeros(n, 1);
eps_tol = 1e-12; // tolerância para teste de zero na diagonal
// calcular x_n
if abs(U(n, n)) <= eps_tol then
error('Elemento diagonal U(%d,%d) é zero ou próximo de zero', n, n);
end
x(n) = c(n) / U(n, n);
// laço retroativo
for i = n-1:-1:1
s = 0;
for j = i+1:n
s = s + U(i, j) * x(j);
end
if abs(U(i, i)) <= eps_tol then
error('Elemento diagonal U(%d,%d) é zero ou próximo de zero', i, i);
end
x(i) = (c(i) - s) / U(i, i);
end
endfunction