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\);

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: \,n (ordem), a matriz triangular superior \,U e o vetor independente \,c.
  • Saída: o vetor solução \,x que satisfaz \,U x = c.
  • O algoritmo dado faz:
    • calcula \,x_n = c_n / U_{n n};
    • para i variando de n-1 até 1 (passo -1) calcula x_i = \frac{c_i - \sum_{j=i+1}^{n} U_{i j}\,x_j}{U_{i i}}.

Passo 2

Intuição e ideia matemática por trás do algoritmo (por que funciona):
  • Como \,U é triangular superior, na última equação do sistema \,U x = c só aparece a incógnita \,x_n. Escrevendo a última linha: U_{n n}\,x_n = c_n \quad\Rightarrow\quad x_n = \frac{c_n}{U_{n n}}.
  • Depois de obter \,x_n, olhamos para a penúltima linha; essa linha envolve \,x_{n-1} e possivelmente \,x_n. Isolamos \,x_{n-1}: U_{n-1,n-1}\,x_{n-1} + U_{n-1,n}\,x_n = c_{n-1} \quad\Rightarrow\quad x_{n-1} = \frac{c_{n-1} - U_{n-1,n}\,x_n}{U_{n-1,n-1}}.
  • Repetindo esse processo para cima (retroativamente) obtemos todas as componentes de \,x.
  • Observação importante: cada divisão por \,U_{ii} exige que \,U_{ii}\neq 0. Se algum \,U_{ii}=0 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 é \,1, não \,0). 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:1end
  • Para criar um vetor coluna zerado use zeros(n,1).
  • É recomendado checar:
    • se \,U é quadrada,
    • se o tamanho de \,c é compatível com \,U,
    • se elementos diagonais \,U_{ii} não são (numericamente) zero antes de dividir.
  • Para somar produtos \sum_{j=i+1}^n U_{ij} x_j pode-se usar um laço for simples 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):
  1. Obter \,n a partir de \,U (número de linhas).
  2. Verificar se \,U é quadrada e se o comprimento de \,c é \,n.
  3. Inicializar \,x como vetor coluna de zeros de tamanho \,n.
  4. Definir uma pequena tolerância numérica \,\varepsilon (por exemplo \,10^{-12}) para testar se um \,U_{ii} é efetivamente zero.
  5. Calcular \,x_n = c_n / U_{n n} (verificando |U_{nn}|>\varepsilon).
  6. Para i = n-1 até 1 (decrescendo):
    • calcular \,\text{Soma} = \sum_{j=i+1}^{n} U_{i j}\,x_j (usando um laço).
    • checar |U_{ii}|>\varepsilon; então \,x_i = (c_i - \text{Soma})/U_{ii}.
  7. Retornar \,x.

Passo 5

Complexidade e aspectos numéricos rápidos (o que vale lembrar para a prova):
  • Complexidade: o algoritmo realiza aproximadamente \,n^2/2 multiplicações/adições — portanto é \,O(n^2).
  • Estabilidade: se \,U 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 \,\varepsilon e lançar erro se |U_{ii}| \le \varepsilon.

Passo 6

Um exemplo pequeno e concreto (passo a passo numérico) para fixar a ideia:
  • Seja U = \begin{pmatrix} 2 & 1 & -1 \\[4pt] 0 & 3 & 4 \\[4pt] 0 & 0 & 5 \end{pmatrix},\qquad c = \begin{pmatrix} 1 \\[3pt] 14 \\[3pt] 10\end{pmatrix}.(Peguei esses números como exemplo para testar o algoritmo.)
  • Calcular:
    • \,x_3 = c_3 / U_{33} = 10 / 5 = 2.
    • \,\text{Soma para } i=2: U_{2,3} x_3 = 4\cdot 2 = 8. Logo \,x_2 = (14 - 8)/3 = 6/3 = 2.
    • \,\text{Soma para } i=1: U_{1,2} x_2 + U_{1,3} x_3 = 1\cdot 2 + (-1)\cdot 2 = 0. Logo \,x_1 = (1 - 0)/2 = 0{,}5.
  • Resultado final do exemplo: \,x = \begin{pmatrix}0{,}5\\[3pt]2\\[3pt]2\end{pmatrix}.
  • 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)
[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

Exercícios relacionados