Faça um algoritmo computacional para resolver sistemas lineares triangulares. No caso de sistemas triangulares superiores, use as substituições retroativas e, no caso de triangulares inferiores, as substituições sucessivas. A implementação deve ser feita em C (ou C++), usando matrizes e vetores no estilo de C (ou da biblioteca std, boost, etc.) e no MATLAB. O programa deve receber como entrada a matriz dos coeficientes (suposta triangular) e a matriz dos termos independentes e ter como saída a matriz com o valor das incógnitas.
Passo 1
O enunciado pede que eu faça algoritmos que resolvam sistemas lineares cuja matriz dos coeficientes é triangular. Entradas e saídas esperadas:
Entrada: a matriz dos coeficientes (supondo que seja triangular) e o vetor (ou matriz coluna) dos termos independentes. Vou tratar o caso geral de matrizes quadradas de ordem n.
Saída: o vetor solução com os valores das incógnitas.
Perguntas que o exercício faz (explicitadas):
Como resolver um sistema triangular superior (usar substituições retroativas)?
Como resolver um sistema triangular inferior (usar substituições sucessivas)?
Implementar as duas rotinas em C (ou C++), usando matrizes e vetores no estilo de C (ou std::vector) e em MATLAB.
Informações relevantes fornecidas ou assumidas:
A matriz dos coeficientes é triangular (ou superior, ou inferior). Vou considerar que o usuário especifica qual tipo ou que o algoritmo detecta automaticamente.
Deve-se cuidar de elementos diagonais iguais a zero (caso torne o sistema singular) — o enunciado supõe triangular, mas não garante não singularidade; portanto, o algoritmo deve checar a_{ii}\neq0.
Passo 2
Definições, notação e forma do sistema que vamos resolver (para eu e você falarmos a mesma língua):
Seja a matriz dos coeficientes A\in\mathbb{R}^{n\times n}\).
- Seja o vetor dos termos independentes \(b\in\mathbb{R}^{n}\).
- A incógnita é o vetor \(x\in\mathbb{R}^{n}\) que satisfaz \(Ax=b\).
- Entradas do algoritmo: \(A\) (armazenada em memória no estilo C) e \(b\). Saída: \(x\).
Formas específicas:
- Sistema triangular superior: \(A=(a_{ij})\) com \(a_{ij}=0\) para todo \(i>j\). As equações ficam:
\[\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1\\\ \quad\vdots\\\ a_{n-1,n-1}x_{n-1} + a_{n-1,n}x_n = b_{n-1}\\\ a_{nn}x_n = b_n \end{cases}
Sistema triangular inferior: A=(a_{ij})\] com \(a_{ij}=0 para todo i<j. As equações ficam:
Procedimento prático: calcular x_n pela última equação; depois x_{n-1} usando x_n; seguir até x_1.
Checagem importante: em cada passo é necessário garantir que a_{ii}\neq0. Se a_{ii}=0 e o resto da equação não satisfizer b_i, o sistema é singular ou indeterminado; o algoritmo deve sinalizar erro.
Passo 4
Derivação do método para sistema triangular inferior (substituição sucessiva) — ideia e fórmula:
Observação prática: na primeira equação do sistema inferior só aparece x_1, portanto podemos obter x_1 direto; em seguida usar x_1 para obter x_2, etc.
Para um índice genérico i(1\le i\le n), a i-ésima equação do sistema inferior é
\sum_{j=1}^{i} a_{ij} x_j = b_i.
Isolando x_i (supondo a_{ii}\neq0) obtemos a fórmula central da forward-substituição:
Procedimento prático: calcular x_1 pela primeira equação; depois x_2 usando x_1; seguir até x_n.
Mesmo cuidado: checar a_{ii}\neq0 antes de dividir.
Passo 5
Complexidade, estabilidade e verificações práticas (coisas que costumam aparecer na prova ou na hora de implementar):
Complexidade: ambos os métodos fazem cerca de \frac{n(n-1)}{2} multiplicações e somas, ou seja, custo assintótico \mathcal{O}(n^2). A operação dominante é o somatório na fórmula de atualização.
Estabilidade numérica básica: não estamos fazendo pivoteamento, então se algum a_{ii} for muito pequeno pode haver problemas de erro numérico; normalmente, para matrizes triangulares já obtidas (por ex. após eliminação), a rotina direta é usada — mas temos que checar divisões por zero.
Verificação de triangularidade (opcional): o algoritmo pode verificar que os elementos por fora da parte triangular são (aproximadamente) zero. Vou incluir uma nota de verificação opcional no código para debug.
Formato de memória: em C costuma-se usar arrays 1D em row-major com índice A[i*n+j] para acessar a_{ij}. Em MATLAB usa-se indexação 1-based.
Passo 6
Exemplo numérico curto (para fixar o conceito) — triangular superior:
Considere a matriz e vetor (vou mostrar os números só para entender o algoritmo):
Resultado: x=(5,\,-2,\,3)^T.
Esse cálculo manual segue exatamente a fórmula da retro-substituição apresentada.
Passo 7
Pseudocódigo (para traduzir facilmente para C/C++/MATLAB)
Retro-substituição (matriz triangular superior A, vetor b, devolve x):
function x = back_substitution(A, b, n)
for i = n downto 1
sum = 0
for j = i+1 to n
sum = sum + A[i][j] * x[j]
if A[i][i] == 0 then error "diagonal zero"
x[i] = (b[i] - sum) / A[i][i]
return x
Forward-substituição (matriz triangular inferior A, vetor b, devolve x):
function x = forward_substitution(A, b, n)
for i = 1 to n
sum = 0
for j = 1 to i-1
sum = sum + A[i][j] * x[j]
if A[i][i] == 0 then error "diagonal zero"
x[i] = (b[i] - sum) / A[i][i]
return x
Passo 8
Implementações finais: código em C (estilo C com matriz armazenada em 1D row-major), em C++ (com std::vector) e em MATLAB. Os códigos abaixo são práticos e verificam diagonal nula; leem/escrevem vetores no formato usual. Eles implementam exatamente as fórmulas que derivamos e são prontos para usar numa prova ou num trabalho prático.
Resposta
C (estilo C, matriz em array 1D row-major):
#include<stdio.h>#include<stdlib.h>voidback_substitution(int n, constdouble *A, constdouble *b, double *x) {
for (int i = n-1; i >= 0; --i) {
double sum = 0.0;
for (int j = i+1; j < n; ++j) sum += A[i*n + j] * x[j];
double aii = A[i*n + i];
if (aii == 0.0) {
fprintf(stderr, "Erro: elemento diagonal A[%d,%d] == 0 (sistema singular ou indeterminado)\n", i, i);
exit(EXIT_FAILURE);
}
x[i] = (b[i] - sum) / aii;
}
}
voidforward_substitution(int n, constdouble *A, constdouble *b, double *x) {
for (int i = 0; i < n; ++i) {
double sum = 0.0;
for (int j = 0; j < i; ++j) sum += A[i*n + j] * x[j];
double aii = A[i*n + i];
if (aii == 0.0) {
fprintf(stderr, "Erro: elemento diagonal A[%d,%d] == 0 (sistema singular ou indeterminado)\n", i, i);
exit(EXIT_FAILURE);
}
x[i] = (b[i] - sum) / aii;
}
}
/* Exemplo de uso:
Primeiro forneça n, depois n*n elementos de A (linha por linha), depois n elementos de b.
Por exemplo para a matriz 3x3 e vetor b:
./prog
3
2 3 -1 0 1 4 0 0 5
1 10 15
*/intmain(void) {
int n;
if (scanf("%d", &n) != 1) return0;
double *A = (double*)malloc(n * n * sizeof(double));
double *b = (double*)malloc(n * sizeof(double));
double *x = (double*)malloc(n * sizeof(double));
if (!A || !b || !x) { fprintf(stderr,"Memória insuficiente\n"); return1; }
for (int i = 0; i < n*n; ++i) scanf("%lf", &A[i]);
for (int i = 0; i < n; ++i) scanf("%lf", &b[i]);
/* Exemplo: se a matriz for triangular superior, usar back_substitution.
Se for triangular inferior, usar forward_substitution.
Aqui escolhemos automaticamente: se existirem zeros acima da diagonal, é inferior; caso contrário, superior.
Essa detecção é simplista; se não tiver certeza, o usuário deve indicar.*/int is_upper = 1;
for (int i = 1; i < n && is_upper; ++i)
for (int j = 0; j < i && is_upper; ++j)
if (A[i*n + j] != 0.0) is_upper = 0;
if (is_upper) back_substitution(n, A, b, x);
else forward_substitution(n, A, b, x);
for (int i = 0; i < n; ++i) printf("%.12g\n", x[i]);
free(A); free(b); free(x);
return0;
}
C++ (com std::vector, matriz representada como vector<vector<double>>):
#include<iostream>#include<vector>#include<stdexcept>using std::vector;
vector<double> back_substitution(const vector<vector<double>>& A, const vector<double>& b){
int n = (int)A.size();
vector<double> x(n, 0.0);
for (int i = n-1; i >= 0; --i) {
double sum = 0.0;
for (int j = i+1; j < n; ++j) sum += A[i][j] * x[j];
double aii = A[i][i];
if (aii == 0.0) throw std::runtime_error("Diagonal zero (sistema singular)");
x[i] = (b[i] - sum) / aii;
}
return x;
}
vector<double> forward_substitution(const vector<vector<double>>& A, const vector<double>& b){
int n = (int)A.size();
vector<double> x(n, 0.0);
for (int i = 0; i < n; ++i) {
double sum = 0.0;
for (int j = 0; j < i; ++j) sum += A[i][j] * x[j];
double aii = A[i][i];
if (aii == 0.0) throw std::runtime_error("Diagonal zero (sistema singular)");
x[i] = (b[i] - sum) / aii;
}
return x;
}
intmain(){
int n;
if (!(std::cin >> n)) return0;
vector<vector<double>> A(n, vector<double>(n));
vector<double> b(n);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) std::cin >> A[i][j];
for (int i = 0; i < n; ++i) std::cin >> b[i];
bool is_upper = true;
for (int i = 1; i < n && is_upper; ++i)
for (int j = 0; j < i && is_upper; ++j)
if (A[i][j] != 0.0) is_upper = false;
try {
vector<double> x = is_upper ? back_substitution(A, b) : forward_substitution(A, b);
for (double xi : x) std::cout << xi << std::endl;
} catch (const std::exception& e) {
std::cerr << "Erro: " << e.what() << std::endl;
return1;
}
return0;
}
MATLAB (funções separadas para upper e lower, 1-indexed):
functionx = back_substitution(U, b)% U should be upper triangular n-by-n, b is n-by-1
n = length(b);
x = zeros(n,1);
fori = n:-1:1
aii = U(i,i);
if aii == 0
error('Diagonal zero at %d', i);
endifi < n
s = U(i,i+1:n) * x(i+1:n);
else
s = 0;
end
x(i) = (b(i) - s) / aii;
endendfunctionx = forward_substitution(L, b)% L should be lower triangular n-by-n, b is n-by-1
n = length(b);
x = zeros(n,1);
fori = 1:n
aii = L(i,i);
if aii == 0
error('Diagonal zero at %d', i);
endifi > 1
s = L(i,1:i-1) * x(1:i-1);
else
s = 0;
end
x(i) = (b(i) - s) / aii;
endend