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 O(cdot)).

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:
  1. Para cada etapa k = 1,2,dots,n-1:
    a) Busca, nas linhas i = k,dots,n, o índice p cujo |ai,k| é o maior.
    b) Troca a linha k com a linha p.
    c) A partir daí, faz a eliminação normal:
    • Para cada linha j = k+1,dots,n, calcula o multiplicador m = aj,kak,k
      - Atualiza cada coluna l = k,k+1,dots,n de aj,l = aj,l - m,ak,l.
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 k, você varre as linhas i=kn para achar o maior valor em módulo. Isso é cerca de (n-k+1) comparações.
  • Soma isso para k=1 até n-1: sumk=1^n-1 (n-k+1) ;approx; n(n+1)2 = O(n^2)
    - A troca de linhas (copiar uma linha inteira de tamanho n) também é O(n), mas isso somado em todos os passos continua O(n^2).
A parte de eliminação de Gauss “pura” já era Ol(tfrac23n^3r). Então, juntando:
  • Eliminação: O(n^3)
  • Pivotamento parcial (busca + troca): O(n^2)
No total dá
O(n^3) + O(n^2) = O(n^3),
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 O(n^2) para buscar e trocar pivôs, mas a eliminação em si continua dominada por O(n^3). Então a complexidade final do algoritmo permanece O(n^3), só com uma constante um pouco maior (e com muito mais estabilidade numérica).

Exercícios relacionados