06 Condensação Pivotal e Refinamento da Solução

Prévia do material em texto

Condensação Pivotal e Refinamento da Solução
No primeiro exemplo resolvemos o sistema linear utilizando frações em todas as operações. No
entanto, quando realizadas no computador, o resultado de cada operação deve ser
truncado/arredondado de acordo com as regras da álgebra de ponto flutuante. Para sistemas mal-
condicionados a propagação de erros de arredondamento pode levar a resultados que não são nem
mesmo próximos da solução exata.
Temos, portanto, que conseguir controlar, ou melhor, minimizar os erros de arredondamento cometidos
durante o processo como também garantir que a solução aproximada esteja próxima da solução exata. 
 
Condensação pivotal
A condensação pivotal consiste em colocar na posição do pivô o maior valor absoluto dos elementos
da coluna que será escalonada, antes de calcular o multiplicador.
Caso este valor já esteja na posição correta, nada será feito, entretanto se ele estiver em qualquer outra
linha, abaixo da diagonal principal, a mesma será permutada para a posição da linha pivô.Com isso
garantimos que os multiplicadores mkj terão sempre valores entre -1 e 1. Isto minimiza a propagação
dos erros de arredondamento.
Exemplo: resolvendo o sistema com condensação pivotal:
 = 
como |-3| é o maior elemento de primeira coluna em módulo, a linha 1 será permutada com a 3, antes
de calcular os multiplicadores e efetivamente escalonar a matris A:
 == == 
 
p1=3
OBSERVAÇÃO: deixaremos anotado que houve uma permutação entre as linhas 1 e
3 por p1=3, colocado exatamente abaixo da coluna que será escalonada. Esta
informação será usada futuramente quando no refinamento da solução.
 
Novamente, para escalonar a segunda coluna teremos que fazer nova permutação com a
linhas 2 e 3
 == 
p1=2 p2=3
OBSERVAÇÃO: toda a linha é permutada, inclusive os multiplicadores.
o sistema escalonado é dado or
 == 
Resolvendo as equações temos:
a) usando frações obtemos a solução exata: X= (1, -1, 3) 
b) com 3 algarismos significativos, obtemos a solução aproximada: Xa=
(0.997 , -1.01, 3.0)
Dependendo do número de algarismos significativos que trabalharmos, teremos boas
aproximações dessa solução exata para a solução aproximada.
Reforçando pontos importantes:
Ao permutarmos as linhas permutamos também os multiplicadores, pois se
precisarmos aplicar um refinamento à solução aproximada, não
precisaremos mais re-escalonar a matriz A, apenas o vetor dos termos
independentes. Isto será feito logo a seguir.
Arquivamento: os valores dos mkj são arquivados nas próprias posições dos
elementos da matriz A que estão sendo zerados, o que implica numa grande
economia de espaço. Porém para que o processo possa ser repetido é
preciso guardar mais um vetor com todas as permutações que foram
efetuadas durante o processo.
Nem sempre a condensação pivotal traz os melhores resultados, ou mesmo
em casos onde a matriz A é quase singular (determinante próximo de zero) as
soluções aproximadas podem nào ser boas, com ou sem condensação
pivotal; entretanto, ela traz resultados satisfatórios para a maioria dos
sistemas e, portanto, deve ser usada sistematicamente.
Refinamento da solução
Seja o sistema linear de ordem n
Ax = b
X = (x1, x2, ..., xn): o vetor da solução exata;
Na primeira resolução obtemos a solução aproximada X(k), onde k = 0.
Xa(0) = (xa1(0) , xa2 (0),..., xan(0)): o vetor da solução aproximada obtida através do Método de
Eliminação de Gauss, calculada com condensação pivotal e aritmética de ponto flutuante.
Vamos chamar de C(0) o vetor da diferença entre a solução exata e a aproximada após a primeira
aproximação.
 
X - Xa(0) = C(0) X = C(0) + Xa(0)
substituindo no sistema linear
A X = b
substituindo X A [C(0) + Xa(0) ] = b 
passando para o segundo membro os termos conhecidos A C(0) = b - A Xa(0 )
nomeando o termo
b - A Xa(0) = r(0) de resíduo e substituindo na equação
 A C(0) = r(0) 
Caso o resíduo não seja um vetor nulo, resolvendo esse novo sistema, encontraremos o
vetor correção C(0).
Observe que a solução do sistema
A C(0) = r(0)
pode aproveitar o escalonemento da matriz A, feito anteriormente. Logo, para concluir,
basta escalonar o vetor r(0).
 
Cálculo do Resíduo - USE PRECISÃO DUPLA
Pelo fato de
b - A Xa(0)
ser a subtração de vetores de mesma ordem de grandeza, esse cálculo deve ser efetuado
com precisão dupla, para que venha a ser significativo. Geralmente, quando efetuado
com precisão simples o resultado é o vetor nulo.
Isto quer dizer que, se estamos trabalhando com N algarismos significativos, devemos
efetuar este cálculo
b - A Xa(0)
e somente este cálculo deve ser feito com 2N algarismos significativos.
Escalonamento do Resíduo - USE PRECISÃO SIMPLES
Como os multiplicadores e as permutações efetuadas durante o processo de escalonamento da matriz
A foram armazenados, para resolver o sistema
A C(0) = r(0)
basta triangularizar o resíduo, pois já conhecemos a matriz A triangularizada.
A triangularização do resíduo, será feita em duas etapas:
1. efetuar primeiro todas as permutações que foram feitas e estão indicadas pelos pi's;
2. aplicar os multiplicadores.
Resolvendo para o sistema acima:
Exemplo resolvido com condensação pivotal e 3 algarismos significativos
Sistema original:
Permutando a linha 1 com a 3: P1=3
Escalonando a matriz (zerando a primeira coluna abaixo da diagonal principal):
Permutando a linha 2 com a 3: P2 = 3
Escalonando a matriz (zerando a segunda coluna abaixo da diagonal principal):
Resolvendo o sistema escalonado a solução aproximada é dada por
Cálculo do resíduo: AQUI DEVE SER USADA A PRECISÃO DUPLA 
 
Este valor do resíduo, calculado em precisão dupla, deve ser agora passado para precisão simples
para iniciar as contas com os multiplicadores. Neste caso não haverá nenhuma alteração nos números
do vetor r, mas isso é um caso particular.
Permutações
 : 
P1=3 => 
p2 = 3 =>
 
 
Multiplicadores - EM PRECISÃO SIMPLES
 
 
Cálculo da correção c- EM PRECISÃO SIMPLES
 
 
Solução refinada:
 
Este é o fim da primeira etapa do refinamento!.
Decidindo o próximo passo
A cada etapa do refinamento, encontramos uma nova aproximação.
partindo do sistema sistema original: A X = b a seqüência de operações para o (k-1)-ésimo
refinamento, onde k = 1, 2,...
solução aproximada: X(k-1)
diferença entre a solução exata e aproximada: X = C(k-1) + Xa(k-1)
substituição no sistema original: A [ C(k-1) + Xa(k-1)] = b
cálculo do resíduo: r(k-1) = b - Xa(k-1)
cálculo da correção, resolução do sistema: A C(k-1) = r(k-1)
solução corrigida: X(k) = X(k-1) + C(k-1)
Precisamos agora decidir se continuamos ou não refinando a solução.
Esta análise será feita através da variação relativa.
Seja
 
Se
Vk < d, onde d é a precisão pré-fixada então paramos o refinamento e a solução
aproximada é dada por X(k).
Caso contrário, continuar a fazer o refinamento até que a precisão d seja atingida ou um número
máximo de iterações de etapas do refinamento atingido.