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\);
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:
(ordem), (matriz triangular inferior) e (vetor independente). - Saída do algoritmo:
(vetor solução). - O algoritmo básico fornecido faz a resolução por “substituição direta” (forward substitution) da equação linear
- 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
.
Passo 2
Entendendo a matemática por trás (passo didático): por que o algoritmo funciona
- Temos uma matriz triangular inferior
de ordem e o sistema
onde
,
e
.
- Como
é triangular inferior, a primeira equação envolve apenas :
- A segunda equação envolve
e :
- Em geral, para
,
- Esta fórmula é exatamente a substituição sucessiva: resolvemos
primeiro, depois usando , e assim por diante até . - Observações importantes:
- É necessário que todos os
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).
- É necessário que todos os
Passo 3
Tradução do algoritmo para passos executáveis (pseudocódigo adaptado e detalhes a cuidar)
- Precisamos de:
- Verificar que
é quadrada e que as dimensões de e batem com . - Verificar que
é realmente triangular inferior (opcional como checagem) e que a diagonal principal não tem zeros. - Alocar o vetor solução
com zeros antes do loop para eficiência. - Implementar um laço externo para
até e, dentro, somar e calcular .
- Verificar que
- Em Scilab:
- Indexação: usar
e , . - Alocação:
. - Checagens: usar funções como size(L) e length(c). Para testar triangular inferior pode-se comparar com tril(L).
- Indexação: usar
Passo 4
Tratamento de casos e robustez numérica (dicas importantes para a prova)
- Checagem de dimensões: se
não for ou se não for (ou ), devolver erro. - Checagem de diagonal nula: testar se existe algum
. Em cálculo numérico real, usar tolerância se desejar:
mas para implementar rápido na prova pode-se checar igualdade a zero e devolver mensagem “Matriz singular”.
- Se
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
multiplicações e somas, ou seja complexidade .
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
e (e opcionalmente ). Em Scilab a definição começa com: - function x = substsuc(L, c)
- Obter tamanho de
: - [m, p] = size(L); — verificar que
e então .
- [m, p] = size(L); — verificar que
- Verificar tamanho do vetor
: - 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
- for i = 1:n
- 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
- Aplicando as fórmulas:
-
. -
. -
.
-
- Resultado esperado
. 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 (a expressão fica vazia).
- soma = L(i,1:i-1) * x(1:i-1);
- 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
com:
- Implementação em Scilab: checar dimensões, diagonal não nula, alocar
, e fazer os loops conforme descrito. - Complexidade
. 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