Como computar a decomposição LU com pivoteamento parcial
Vamos lá?
Na aula passada vimos em um exemplo como a ordem das equações pode influenciar bastante o resultado numérico da resolução de um sistema linear, quando trabalhamos em aritmética com precisão finita. Nesta aula vamos incorporar à decomposição LU a estratégia de pivoteamento parcial, para mitigar potenciais problemas numéricos.
1
2
3
No que consiste o pivoteamento parcial?
A. Na escolha do maior elemento da coluna como pivô.
B. Na ordenação das linhas da matriz.
C. Em uma estratégia para evitar pivôs pequenos.
Como é construída a matriz de permutação?
A. Realizando na matriz identidade as trocas de linhas que queremos na matriz
B. Realizando na matriz as trocas de linhas que queremos.
Podemos afirmar que...
A. toda matriz tem decomposição LU.
B. toda matriz tem decomposição LU com pivoteamento parcial.
C. se a matriz tem decomposição LU sem pivoteamento, então não será necessário permutar linhas para computar a decomposição com pivoteamento.
Para reduzir erros numéricos quando resolvemos um sistema linear em aritmética de precisa finita, devemos evitar trabalhar com pivôs pequenos durante o processo de escalonamento. Isso vale tanto para a eliminação de Gauss, quanto para a decomposição LU. Um exemplo de como a magnitude relativa do pivô tem influência na solução numérica do sistema linear foi visto na aula passada.
A forma tradicional de se fazer isso é através da estratégia de pivoteamento parcial. Relembre que o algoritmo para decomposição LU sem pivoteamento é:
Para
Se então não tem decomposição LU. FIM.
Para
Para
Neste algoritmo, quando iniciamos o passo ou seja, quando formos eliminar os elementos abaixo da diagonal da coluna o pivô é (nesse ponto, é a matriz temporária, obtida no processo de escalonamento das colunas anteriores). A estratégia de pivoteamento parcial consiste em trocar a linha do pivô por alguma das linhas abaixo dela, digamos a linha determinada de forma que Feita a troca das linhas (caso tenha sido preciso), o algoritmo segue como antes. Para registrar essa troca de linhas, precisamos de uma nova matriz, denominada matriz de permutação Essa matriz nada mais é que a matriz identidade, sobre a qual se realizam as mesmas operações de troca de linhas que tenham sido realizadas em
O algoritmo para a decomposição LU com pivoteamento parcial fica assim
,
Para
Determine a linha do pivô, tal que se cumpra.
Se então
(troca das linhas e de )
(troca das linhas e de )
(troca dos multiplicadores computados anteriormente)
Se não há o que escalonar na coluna Volte para o passo 2.
Para
Para
Vamos detalhar alguns passos do algoritmo acima. No passo 2.1 determinamos a linha abaixo da linha , que contem o maior elemento em módulo abaixo da diagonal. Se então será necessário fazer o pivoteamento. Isto é feito nos passos de 2.2.1 a 2.2.3. Por simplicidade, estamos usando aqui a notação própria do Octave, a saber representa a linha da matriz e representa a linha de apenas entre as colunas e Os passos 2.2.1 e 2.2.2 são apenas as trocas de linhas de e como já havíamos comentado. Mas o passo 2.2.3 merece atenção. Nesse passo, estamos trocando as linhas de e da matriz mas apenas da primeira coluna a até a coluna pois apenas essas foram computadas nesse momento da execução do algoritmo. Essa troca é necessária pois cada elemento da matriz armazena um multiplicador que estava relacionado a duas linhas no processo de escalonamento (a linha pivô e a linha onde a operação de eliminação foi aplicada). Caso as linhas troquem de ordem por conta do pivoteamento, os multiplicadores também precisam ser trocados, pois do contrário essas associação entre multiplicadores e linhas ficariam incorretas.
No passo 2.3, após o pivoteamento, verificamos se o pivô é nulo. Se este for o caso, isto significa que todos os elementos abaixo da diagonal também são nulos (por quê?). Logo, não há nada mais a ser eliminado e podemos passar para o processo de eliminação dos elementos na próxima coluna.
Perceba que agora não há mais a possibilidade do algoritmo interromper sua execução antes do fim e, como consequência, toda matriz tem decomposição LU com pivoteamento parcial. Isso é diferente do que acontecia com decomposição LU sem pivoteamento, que pode existir ou não.
Ao final da execução do algoritmo acima, temos três matrizes e , que satisfazem Para resolver um sistema linear premultiplicamos ambos os lados dessa equação por assim o produto pode ser substituído por Chamando temos Ou seja, o sistema original é reescrito como dois sistemas lineares, um triangular inferior e outro triangular superior.
Antes de concluir, um último comentário sobre a implementação computacional deste algoritmo. Caso a matriz original não seja mais necessária após sua decomposição nos fatores e podemos utilizar o espaço de memória que abrigava para armazenar os fatores e Como essas duas matrizes são triangulares, uma inferior e outra superior, a porção triangular inferior de abrigará enquanto que a porção triangular superior abrigará Claro que falta espaço para armazenar os elementos da diagonal de e Porém, a diagonal de é constante e igual a não precisando ser armazenada. Com essa estratégia, não é necessário espaço adicional para os fatores e e o algoritmo acima fica até um pouco mais compacto (ainda mais usando operações vetoriais do Octave!).
Para
Determine a linha do pivô, tal que se cumpra.
Se então
(troca das linhas e de e ao mesmo tempo)
(troca das linhas e de )
Se não há o que escalonar na coluna Volte para o passo 2.
(multiplicadores)
Para
Na próxima aula, veremos um exemplo prático, computado passo a passo, onde a decomposição LU com pivoteamento parcial é computada e e empregada na resolução do sistema linear.
Referência
Lloyd N. Trefethen e David Bau, III. Numerical Linear Algebra. SIAM, 1997.
1. Se e são os fatores da decomposição LU com pivoteamento de uma matriz resolva o sistema linear , para
A solução do primeiro sistema, , é . E a solução de é
2. Aplique o algoritmo da decomposição LU com pivoteamento parcial à matriz Usando os fatores da decomposição, resolva o sistema linear , para Quando encontrar a solução, verifique se ela está correta, substituindo-a no sistema linear.
Os fatores da decomposição LU de são: A solução do sistema é
3. Reescreva o passo 2.4.3 do segundo algoritmo apresentado usando a notação compacta do Octave. Você deve escrever esse passo sem usar um loop.