Sejam
, uma matriz triangular superior,
e o seguinte problema: encontrar
tal que
. 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
que já é triangular superior e um vetor
. A missão é achar o vetor
que satisfaça
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
é 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
), depois a
, e assim por diante.
A equação genérica na linha é:
A equação genérica na linha
Mas como
Passo 3
Isolando
, temos a fórmula de retro-substituição:
Repare que, no passo em que calculamos
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
Passo 5
Complexidade:
- Para cada
, o laço em roda de até , fazendo uma multiplicação e uma soma a cada passo. O número de iterações é . - Somando para
dá
- Além disso, pra cadatem uma divisão no final, ou seja, mais divisões.
No total, a ordem de grandeza é
Resposta
Algoritmo de retro-substituição mostrado acima e complexidade computacional de ordem
.