Introduza a estratégia de pivotamento parcial no algoritmo da questão anterior e analise os efeitos sobre a complexidade computacional.
Passo 1
Beleza, o exercício está pedindo para a gente “meter” a estratégia de pivotamento parcial no algoritmo de eliminação de Gauss (que foi a questão anterior) e ver como isso mexe com a complexidade computacional. O conteúdo é “eliminação de sistemas lineares” e o que vamos usar é:
- Como a eliminação de Gauss funciona (trocar linhas, zerar elementos).
- O que é pivotamento parcial (escolher o maior elemento na coluna).
- Contagem de operações para analisar complexidade (notação
).
Passo 2
O que é pivotamento parcial? Em vez de mandar ver direto na coluna e dividir pelo pivô (que às vezes é pequeno e deixa o algoritmo num perrengue numérico), a gente faz:
- Para cada etapa
:
a) Busca, nas linhas, o índice cujo é o maior.
b) Troca a linhacom a linha .
c) A partir daí, faz a eliminação normal:- Para cada linha
, calcula o multiplicador
- Atualiza cada colunade .
- Para cada linha
Em pseudocódigo rápido (de leve):
Para k = 1 até n-1:
p ← arg max_{i=k..n} |a[i][k]| // encontro do pivô
trocar_linhas(a, k, p)
Para j = k+1 até n:
m ← a[j][k] / a[k][k]
Para l = k até n:
a[j][l] ← a[j][l] - m * a[k][l]
Passo 3
Agora, conta as operações extras do pivotamento parcial:
- Em cada
, você varre as linhas para achar o maior valor em módulo. Isso é cerca de comparações. - Soma isso para
até :
- A troca de linhas (copiar uma linha inteira de tamanho) também é , mas isso somado em todos os passos continua .
A parte de eliminação de Gauss “pura” já era
. Então, juntando:
- Eliminação:
- Pivotamento parcial (busca + troca):
No total dá
Ou seja, o pivotamento parcial só acrescenta um custo de ordem menor e não muda a ordem geral da complexidade.
Resposta
A inclusão do pivotamento parcial adiciona um sobrecusto de
para buscar e trocar pivôs, mas a eliminação em si continua dominada por
. Então a complexidade final do algoritmo permanece
, só com uma constante um pouco maior (e com muito mais estabilidade numérica).