Exercício 2.

Desenvolva na liguagem Scilab, o Algoritmo de substituições sucessivas apresentado pelo Algoritmo 1 .
Algoritmo 1: Substituições Sucessivas
    Entradas: \(n, L, c\) /* ordem, matriz triang. inf. e vetor indep. */
    Saída: \(x\)
    \(x_{1} \leftarrow c_{1} / L_{11}\)
    for \((i \leftarrow 2\) to \(n)\) do
        Soma \(\leftarrow 0\);
        for \((j \leftarrow 1\) to \(i-1)\) do
            Soma \(\leftarrow\) Soma \(+L_{i j} * x_{j} ;\)
        end
        \(x_{i} \leftarrow\left(c_{i}\right.\) - Soma \() / L_{i i}\);
    end
    Retorne \(x\);

Passo 1

O que o enunciado pede e quais são as informações dadas:
  • Deve-se implementar em Scilab o Algoritmo 1 — “Substituições Sucessivas”.
  • Entradas do algoritmo: n (ordem), L (matriz triangular inferior) e c (vetor independente).
  • Saída do algoritmo: x (vetor solução).
  • O algoritmo básico fornecido faz a resolução por “substituição direta” (forward substitution) da equação linear
Lx = c.
  • O enunciado pede que o algoritmo seja desenvolvido (ou seja: implementado) em Scilab. Não há pedido de interface gráfica, apenas função/programa que recebe os dados e retorna x.

Passo 2

Entendendo a matemática por trás (passo didático): por que o algoritmo funciona
  • Temos uma matriz triangular inferior L de ordem n e o sistema
Lx = c,
onde L = \left(L_{ij}\right), x=\left(x_i\right) e c=\left(c_i\right).
  • Como L é triangular inferior, a primeira equação envolve apenas x_1:
L_{11} x_1 = c_1 \quad\Rightarrow\quad x_1 = \frac{c_1}{L_{11}}.
  • A segunda equação envolve x_1 e x_2:
L_{21} x_1 + L_{22} x_2 = c_2 \quad\Rightarrow\quad x_2 = \frac{c_2 - L_{21} x_1}{L_{22}}.
  • Em geral, para i=1,\dots,n,
x_i = \frac{c_i - \displaystyle\sum_{j=1}^{i-1} L_{ij} x_j}{L_{ii}}.
  • Esta fórmula é exatamente a substituição sucessiva: resolvemos x_1 primeiro, depois x_2 usando x_1, e assim por diante até x_n.
  • Observações importantes:
    • É necessário que todos os L_{ii} sejam diferentes de zero; caso contrário, o sistema é singular ou precisa de pivoteamento (fora do escopo aqui).
    • Indices na fórmula e no algoritmo começam em 1, o que casa bem com a indexação do Scilab (1-based).

Passo 3

Tradução do algoritmo para passos executáveis (pseudocódigo adaptado e detalhes a cuidar)
  • Precisamos de:
    • Verificar que L é quadrada e que as dimensões de L e c batem com n.
    • Verificar que L é realmente triangular inferior (opcional como checagem) e que a diagonal principal não tem zeros.
    • Alocar o vetor solução x com zeros antes do loop para eficiência.
    • Implementar um laço externo para i=1 até n e, dentro, somar \sum_{j=1}^{i-1} L_{ij} x_j e calcular x_i.
  • Em Scilab:
    • Indexação: usar L(i,j) e x(i), c(i).
    • Alocação: x = zeros(n,1);.
    • Checagens: usar funções como size(L) e length(c). Para testar triangular inferior pode-se comparar com tril(L).

Passo 4

Tratamento de casos e robustez numérica (dicas importantes para a prova)
  • Checagem de dimensões: se L não for n\times n ou se c não for n\times 1 (ou 1\times n), devolver erro.
  • Checagem de diagonal nula: testar se existe algum L_{ii} = 0. Em cálculo numérico real, usar tolerância se desejar:
\text{tolerância} = \text{eps} \times \max_i |L_{ii}|â
mas para implementar rápido na prova pode-se checar igualdade a zero e devolver mensagem “Matriz singular”.
  • Se L não for estritamente triangular inferior (ou houver elementos acima da diagonal), o algoritmo ainda funcionará matematicamente contanto que as equações obedeçam ao formato triangular; porém é bom alertar o usuário.
  • Complexidade do algoritmo: a operação interna de somas faz, ao todo, cerca de \dfrac{n(n-1)}{2} multiplicações e somas, ou seja complexidade \mathcal{O}(n^2).

Passo 5

Passo-a-passo detalhado da implementação em Scilab (explicando cada linha importante)
  • Função: criar uma função chamada, por exemplo, substsuc que receba L e c (e opcionalmente n). Em Scilab a definição começa com:
    • function x = substsuc(L, c)
  • Obter tamanho de L:
    • [m, p] = size(L); — verificar que m=p e então n=m.
  • Verificar tamanho do vetor c:
    • if size(c,"*") <> n then error… — mas mais simples: if length(c) <> n then error…
  • Checar triangularidade (opcional):
    • if ~isequal(L, tril(L)) then warning(“Matriz não é triangular inferior”); end
  • Checar zeros na diagonal:
    • d = diag(L); if any(d == 0) then error(“Diagonal contém zero — matriz singular”); end
  • Inicializar solução:
    • x = zeros(n,1);
  • Loop principal (implementação direta do algoritmo):
    • for i = 1:n
      soma = 0;
      for j = 1:i-1
      soma = soma + L(i,j) * x(j);
      end
      x(i) = (c(i) - soma) / L(i,i);
      end
  • Retornar x (Scilab retorna automaticamente o valor da variável de saída declarada na linha function).

Passo 6

Exemplo numérico pequeno (para fixar a ideia)
  • Considere
L = \begin{pmatrix} 2 & 0 & 0 \\\\ 3 & 1 & 0 \\\\ -1 & 4 & 5 \end{pmatrix},\qquad c = \begin{pmatrix} 4 \\\\ 7 \\\\ 1 \end{pmatrix}.
  • Aplicando as fórmulas:
    • x_1 = 4/2 = 2.
    • x_2 = (7 - 3\cdot 2)/1 = (7-6)=1.
    • x_3 = (1 - (-1)\cdot 2 - 4\cdot 1)/5 = (1 +2 -4)/5 = (-1)/5 = -0,2.
  • Resultado esperado x = (2,\;1,\;-0{,}2)^T. Esse cálculo é exatamente o que o código em Scilab irá executar passo a passo.

Passo 7

Observações de implementação e variações possíveis (úteis na prova)
  • Versão vetorizada parcial: em Scilab pode-se usar operações de produto de subvetores, por exemplo:
    • soma = L(i,1:i-1) * x(1:i-1);
      que substitui o loop interno. Isso é mais curto e eficiente, mas exige cuidado com as dimensões quando i=1 (a expressão 1:i-1 fica vazia).
  • Tratamento de entradas inválidas: preferível usar error(…) para encerrar e retornar mensagem clara.
  • Para números muito próximos de zero na diagonal, é melhor testar com tolerância e avisar sobre condicionamento ruim.
  • Se for necessário lidar com matrizes que não sejam exatamente triangulares devido a erros numéricos, pode-se usar tril(L) para extrair a parte triangular inferior.

Passo 8

Resumo (para memorização rápida antes da prova)
  • O algoritmo resolve Lx=c com:
x_i = \frac{c_i - \sum_{j=1}^{i-1} L_{ij} x_j}{L_{ii}},\qquad i=1,\dots,n.
  • Implementação em Scilab: checar dimensões, diagonal não nula, alocar x, e fazer os loops conforme descrito.
  • Complexidade \mathcal{O}(n^2). Sempre verificar diagonal para evitar divisão por zero.

Resposta

function x = substsuc(L, c)
    // Substituições sucessivas (forward substitution) para resolver L*x = c
    // Entradas:
    //   L : matriz (n x n) triangular inferior
    //   c : vetor (n x 1) termo independente
    // Saída:
    //   x : vetor solução (n x 1)

    // Verificações básicas de dimensão
    [m, p] = size(L);
    if m ~= p then
        error("Matriz L deve ser quadrada.");
    end
    n = m;
    if length\text{(c)} ~= n then
        error("Vetor c deve ter comprimento igual a n.");
    end

    // Verificar (opcional) se L é triangular inferior
    if ~isequal(L, tril(L)) then
        warning("Atenção: L não é estritamente triangular inferior. Usando tril(L) para segurança.");
        L = tril(L); // força usar apenas a parte triangular inferior
    end

    // Checar zeros na diagonal
    d = diag(L);
    if any(d == 0) then
        error("Diagonal de L contém zero(s): divisão por zero. Matriz singular ou necessário pivoteamento.");
    end

    // Inicializa solução
    x = zeros(n, 1);

    // Loop de substituições sucessivas
    for i = 1:n
        // calcular soma = sum_{j=1}^{i-1} L(i,j)*x(j)
        if i == 1 then
            soma = 0;
        else
            // versão vetorizada para eficiência
            soma = L(i, 1:i-1) * x(1:i-1);
        end
        x(i) = (c(i) - soma) / L(i, i);
    end
endfunction

Exercícios relacionados