Sejam U in R^n times n, uma matriz triangular superior, b in R^n e o seguinte problema: encontrar x in R^n tal que U x=b. Apresente um algoritmo de retro-substituição para resolver este sistema e analise sua complexidade computacional.

Passo 1

Beleza, o enunciado diz assim: temos uma matriz UinR^ntimes n que já é triangular superior e um vetor binR^n. A missão é achar o vetor xinR^n que satisfaça
U,x = b
Isso faz parte de Álgebra Linear, mais precisamente de métodos diretos para resolver sistemas lineares. Para resolver isso vamos precisar de um algoritmo chamado retro-substituição e, depois de montá-lo, analisar quantas operações ele usa (a complexidade computacional).

Passo 2

Teoria básica: quando U é triangular superior, só tem elementos não nulos na diagonal e acima dela. Essa estrutura permite resolver o sistema de cima para baixo, ou seja, primeiro a última equação (linha n), depois a n-1, e assim por diante.
A equação genérica na linha i é:
sumj=1^n Uij,xj = bi
Mas como Uij=0 para j, isso vira
Uii,xi + sumj=i+1^n Uij,xj = bi,

Passo 3

Isolando xi, temos a fórmula de retro-substituição:
xi = 1Uiil(bi - sumj=i+1^n Uij,xjr),, i=n,n-1,dots,1
Repare que, no passo em que calculamos xi, todas as xj para j>i já estão disponíveis.

Passo 4

Vamos traduzir isso num algoritminho em pseudocódigo (índices 1-based):
Para i de n até 1 (decrescente):
    soma ← 0
    Para j de i+1 até n:
        soma ← soma + U[i,j] * x[j]
    Fim para
    x[i] ← (b[i] - soma) / U[i,i]
Fim para
Em Latex, a linha central equivale a
soma ;>=ts;sumj=i+1^n Uij,xj, xi;>=ts;bi-somaUii,

Passo 5

Complexidade:
  • Para cada i, o laço em j roda de i+1 até n, fazendo uma multiplicação e uma soma a cada passo. O número de iterações é (n-i).
  • Somando para i=n,n-1,dots,1 sumi=1^n (n-i) ;=;sumk=0^n-1 k ;=;n(n-1)2operações de soma+mu<çõ
    - Além disso, pra cada i tem uma divisão no final, ou seja, mais n divisões.
    No total, a ordem de grandeza é
    n(n-1)2 + n = O(n^2),

Resposta

Algoritmo de retro-substituição mostrado acima e complexidade computacional de ordem O(n^2),.

Exercícios relacionados