Pivoteamento

Teoria Completa

Introdução

Fala galera! No último tópico estudamos o Método da Eliminação de Gauss e, de certo modo, vamos continuar estudando ele nesse tópico.

Lembra de quando a gente estava aplicando lá o algoritmo e aparecia um 0 no lugar onde devia ter o pivô? Isso é um belo de um problema porque a gente ia acabar fazendo uma divisão por zero! Bom, quando isso acontecia bastava a gente trocar as linhas pra evitar o problema né? Mas e se isso acontecer com seu computador? Ele tem um algoritmo pré-definido a seguir, que vamos aprender agorinha mesmo.

Outro problema é quando temos um número muito próximo de zero, o que acarreta uma maior propagação de erros. Por exemplo:

0.0030 53.14 8.573 - 8.390 53.17 44.52

A solução desse sistema é dada por x 1 , x 2 = 10,1 . Vamos ver o que acontece quando o resolvemos normalmente utilizando aritmética de ponto flutuante de 4 dígitos. O multiplicador será dado por:

8.573 0.003 = 2857 . 6 ¯

Arredondando para o sistema de 4 dígitos ficamos com 2858 . Assim, fazendo os cálculos, temos:

0.0030 53.13 0 - 151900 53.16 - 152000

Resolvendo o sistema:

- 151900 x 2 = - 152000

x 2 ≈ 1.001

Que é de fato um valor bem próximo de 1 . No entanto, ao substituirmos na primeira equação,

x 1 = 53.17 - 53.14 ∙ 1.001 0.003 = - 7.713

O que deu bem distante do nosso valor correto 10 ! Isso porque o valor muito pequeno 0.003 no denominador multiplicou aquele errinho de 0.001 e fez ele ficar muito grande.

Então precisamos de uma forma de contornar esse problema no nosso algoritmo, e é aí que entram as estratégias de pivoteamento.

Pivoteamento Parcial

O que fazemos aqui é o seguinte: a cada etapa em que vamos definir o pivô nós olhamos todos os números abaixo dele e escolhemos como pivô o que tiver maior módulo, fazendo a troca das linhas! Isso faz com que os multiplicadores estejam entre 0 e 1 evitando que os erros por arredondamento aumentem absurdamente. Vamos ver um exemplo:

3 3 4 2 3 1 - 9 3 6 2 12 2 2 - 5 2 5 16 12 16 - 3

O primeiro pivô seria o 3 . Mas como estamos aplicando o pivoteamento parcial precisamos comparar os elementos abaixo dele. E como podemos ver, o de maior módulo é o 6 . Logo, fazemos a troca das linhas:

Prosseguindo com a Eliminação de Gauss, chegaríamos ao momento de escolher o próximo pivô:

6 2 12 2 0 0 - 15 2 0 2 - 2 1 0 - 5.67 - 2 4.33 16 4 8 - 8.33

Dessa vez pra piorar ainda temos o pivô igual à zero! Escolhendo o de maior módulo abaixo dele ficamos com:

Deu pra pegar o espírito né? Lembrando que levamos em conta o módulo como podemos ver no exemplo acima.

Algoritmo do Pivoteamento Parcial

O Pivoteamento Parcial faz uma pequena alteração na Fase 1 do Método de Gauss, na parte da eliminação. A retrosubstituição não é alterada então não iremos repetir seu algoritmo aqui. Segue o algoritmo da fase da eliminação com pivoteamento parcial:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Matriz quadrada A n × n (em geral uma matriz é representada como uma lista de listas em programação).

b. Vetor solução b 1 × n (normalmente representado por uma lista).

Passo 2. Percorremos as linhas de A com uma variável i (de 1 a n ).

Passo 3. l = i + 1

Passo 4. p o s M a i o r = i

Passo 5. m a i o r = a i i

Passo 6. Se a l i > m a i o r , então m a i o r = a l i e p o s M a i o r = l .

Passo 7. l = l + 1

Passo 8. Enquanto l ≤ n , volte para o Passo 6. Caso contrário, continue.

Passo 9. Troque as linhas i e p o s M a i o r de A e b .

Passo 10. Escolher pivô da i -ésima linha e armazenar na variável p .

Passo 11. Para cada ‘ i ’, percorremos as linhas de i + 1 até n com uma variável k .

Passo 12. Definimos o multiplicador m i k = a k i p .

Passo 13. Para cada ' k ' , b k = b k - m i k ∙ b i

Passo 14. Para cada ‘ k ’, percorremos as colunas de i até n com uma variável j .

Passo 15. a k j = a k j - m i k ∙ a i j

O Algoritmo é exatamente o mesmo, sendo acrescentados apenas os passos 3 a 9 para fazer o pivoteamento quando necessário.

Pivoteamento Completo

O propósito do Pivoteamento Completo é exatamente o mesmo do parcial. A diferença aqui é que além de trocar as linhas ele também pode trocar as colunas! Na comparação de módulo ele leva em conta todos os valores das colunas e linhas seguintes ao pivô. Vamos ver no exemplo que fica mais claro:

3 3 4 2 3 1 - 9 3 6 2 12 2 2 - 5 2 5 16 1 2 1 6 - 3

Fazendo o Pivoteamento Completo, temos:

Conseguiu perceber o que aconteceu? Nós trocamos as linhas dos números circulados de lugar e depois trocamos as colunas de lugar também! O cuidado que temos que ter é que ao fazer isso também estamos trocando a ordem das nossas variáveis!!!! E isso é extremamente importante, não se esqueça disso! Tipo pensa em forma de equação:

3 x 1 + 3 x 2 + 4 x 3 + 2 x 4 = 16 6 x 1 + 2 x 2 + 12 x 3 + 2 x 4 = 16

Trocando as linhas:

6 x 1 + 2 x 2 + 12 x 3 + 2 x 4 = 16 3 x 1 + 3 x 2 + 4 x 3 + 2 x 4 = 16

Agora trocando as colunas:

12 x 3 + 2 x 2 + 6 x 1 + 2 x 4 = 16 4 x 3 + 3 x 2 + 3 x 1 + 2 x 4 = 16

Ficou claro? Como trocamos as colunas 1 e 3 de lugar, as variáveis x 1 e x 3 também trocaram de lugar na nossa matriz! Nesse tipo de questão eu normalmente escrevo em cima das colunas qual variável que ela representa pra eu não me perder, então já fica a dica ;)

Continuando a Eliminação de Gauss com a matriz pivoteada chegamos em:

12 2 6 2 0 2.5 7.5 4.5 0 2.33 1 1.33 0 - 5.33 1 4.67 16 24 10.67 - 5.67

Aplicando o pivoteamento completo novamente:

Trocamos as colunas novamente! Volto a repetir, tomem cuidado com essa mudança na ordem das variáveis, galera. Deu pra pegar o espírito da coisa né? Vamos ver o algoritmo pra fechar.

Algoritmo do Pivoteamento Completo

Mesmo esquema do pivoteamento parcial. Basta adicionar alguns passos no algoritmo da Fase 1 da Eliminação de Gauss.

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Matriz quadrada A n × n (em geral uma matriz é representada como uma lista de listas em programação).

b. Vetor solução b 1 × n (normalmente representado por uma lista).

Passo 2. Percorremos as linhas de A com uma variável i (de 1 a n ).

Passo 3. l = i + 1

Passo 4. m = i

Passo 5. l i n M a i o r = i

Passo 6. c o l M a i o r = i

Passo 7. m a i o r = a i i

Passo 8. Se a l m > m a i o r , então m a i o r = a l m , l i n M a i o r = l e c o l M a i o r = m .

Passo 9. l = l + 1

Passo 10. Enquanto l ≤ n , volte para o Passo 8. Caso contrário, continue.

Passo 11. l = i e m = m + 1

Passo 12. Enquanto m ≤ n , volte para o Passo 8. Caso contrário, continue.

Passo 13. Troque as linhas i e l i n M a i o r de A e b .

Passo 14. Troque as colunas i e c o l M a i o r de A . Não se esqueça de armazenar essas alterações de alguma forma.

Passo 15. Escolher pivô da i -ésima linha e armazenar na variável p .

Passo 16. Para cada ‘ i ’, percorremos as linhas de i + 1 até n com uma variável k .

Passo 17. Definimos o multiplicador m i k = a k i p .

Passo 18. Para cada ' k ' , b k = b k - m i k ∙ b i

Passo 19. Para cada ‘ k ’, percorremos as colunas de i até n com uma variável j .

Passo 20. a k j = a k j - m i k ∙ a i j

A única coisa que você precisa se lembrar como eu pontuei no Passo 14 é de armazenar em algum lugar essas mudanças de colunas para consertar o resultado da Fase 2, a retrosubstituição.

Obs.: Deu pra perceber que pivoteamento dá um trabalho absurdo né? Não só para você, mas para a máquina também! O pivoteamento parcial é bem justificável já que elimina o problema com os zeros. O pivoteamento completo, no entanto, só é recomendado para sistemas em que a precisão é muito essencial de modo a justificar o tempo extra gasto.

Expandir

Exercício Resolvido #1

UFRGS-REAMAT-Cálculo Numérico-Livro Scilab.

Resolva o seguinte sistema de equações lineares

x + y + z = 0

x + 10 z = - 48

10 y + z = 2 5

Usando eliminação gaussiana com pivotamento parcial (não use o computador para resolver essa questão).

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Com esse sistema linear, conseguimos construir essas matrizes:

1 1 1 1 0 10 0 10 1 x y z = 0 - 48 25

Começamos passando para a forma de matriz aumentada:

1 1 1 1 0 10 0 1 0 1 0 - 48 25

Passo 2

Fase 1 – Eliminação:

Aplicando o pivoteamento parcial:

Como o maior elemento da primeira coluna é o 1 , não precisamos mudar nossa matriz pelo pivoteamento. Mas podemos trocar a segunda e a terceira linhas:

L 2 ↔ L 3

1 1 1 0 1 0 1 1 0 10 0 25 - 48

Agora, vamos zerar o primeiro elemento da terceira linha só:

L 3 ← L 3 - L 1 :

1 1 1 0 10 1 0 - 1 9 0 25 - 48

Novamente, não será necessário aplicar o pivoteamento parcial, pois o maior elemento da segunda coluna já é o próximo pivô:

1 1 1 0   10 1 0 - 1 9 0 25 - 48

L 3 ← L 3 + 1 10 L 2 :

1 1 1 0 10 1 0 0 9,1 0 25 - 45,5

Passo 3

Fase 2Retrosubstituição:

Passando para a forma de sistema:

x + y + z = 0 10 y + z = 25 9,1 z = - 45,5       I I I I I I

De I I I :

z = - 5