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:
\begin{cases} a_{11}x_1 = b_1\\\ a_{21}x_1 + a_{22}x_2 = b_2\\\ \quad\vdots\\\ a_{n1}x_1 + \dots + a_{nn}x_n = b_n \end{cases}

Passo 3

Derivação do método para sistema triangular superior (substituição retroativa) — ideia e fórmula:
  • Observação prática: na última equação só aparece x_n, então posso calcular x_n diretamente e voltar para cima.
  • Para um índice genérico i (1\le i\le n), a i-ésima equação do sistema superior é
\sum_{j=i}^{n} a_{ij} x_j = b_i.
  • Isolando x_i (supondo a_{ii}\neq0) obtemos a fórmula central da retro-substituição:
x_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j=i+1}^{n} a_{ij} x_j\right).
  • 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:
x_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j\right).
  • 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):
A=\begin{pmatrix}2 & 3 & -1\\\\ 0 & 1 & 4\\\\ 0 & 0 & 5\end{pmatrix},\quad b=\begin{pmatrix}1\\\\ 10\\\\ 15\end{pmatrix}.
  • Última equação: 5x_3 = 15 então x_3 = 3.
  • Segunda equação: 1\cdot x_2 + 4\cdot x_3 = 10 \Rightarrow x_2 = 10 - 4\cdot 3 = -2.
  • Primeira equação: 2x_1 + 3x_2 - 1x_3 = 1 \Rightarrow 2x_1 = 1 - 3(-2) + 1\cdot 3 = 1 + 6 + 3 = 10 então x_1 = 5.
  • 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>

void back_substitution(int n, const double *A, const double *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;
    }
}

void forward_substitution(int n, const double *A, const double *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
*/
int main(void) {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    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"); return 1; }

    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);
    return 0;
}
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;
}

int main() {
    int n;
    if (!(std::cin >> n)) return 0;
    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;
        return 1;
    }
    return 0;
}
MATLAB (funções separadas para upper e lower, 1-indexed):
function x = back_substitution(U, b)
% U should be upper triangular n-by-n, b is n-by-1
n = length(b);
x = zeros(n,1);
for i = n:-1:1
    aii = U(i,i);
    if aii == 0
        error('Diagonal zero at %d', i);
    end
    if i < n
        s = U(i,i+1:n) * x(i+1:n);
    else
        s = 0;
    end
    x(i) = (b(i) - s) / aii;
end
end

function x = forward_substitution(L, b)
% L should be lower triangular n-by-n, b is n-by-1
n = length(b);
x = zeros(n,1);
for i = 1:n
    aii = L(i,i);
    if aii == 0
        error('Diagonal zero at %d', i);
    end
    if i > 1
        s = L(i,1:i-1) * x(1:i-1);
    else
        s = 0;
    end
    x(i) = (b(i) - s) / aii;
end
end

Exercícios relacionados