aulaPedro EliminacaodeGauss

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Clique para editar o estilo do título mestre
Clique para editar o estilo do subtítulo mestre
*
*
*
Resolução de sistemas lineares
Métodos Numéricos para Engenharia I
Pedro Augusto Munari Junior [munari@icmc.usp.br]
*
*
Aula de hoje...
Introdução
Número de soluções
Métodos para resolução
Eliminação de Gauss
Fatoração LU
Exemplos e algoritmos
*
*
Introdução
Sistemas lineares são de grande importância para a descrição e resolução de problemas que surgem nas mais diversas áreas da ciência e engenharia.
Geometria
Redes elétricas, hidráulicas, de tráfego, ...
Distribuição de calor
Química
Economia
Programação linear
Estatística
Jogos
...
(http://aix1.uottawa.ca/~jkhoury/system.html)
*
*
Introdução
Interpretação geométrica para sistemas de duas variáveis
*
*
Introdução
*
*
Introdução
Por que utilizar um método?
*
*
Introdução
Notação
*
*
Número de soluções
Dado um sistema linear, apenas uma das situações abaixo pode ocorrer:
O sistema tem solução única
O sistema tem infinitas soluções
O sistema não admite solução
*
*
Número de soluções
Solução única
*
*
Número de soluções
Infinitas soluções
*
*
Número de soluções
Não admite solução
*
*
Número de soluções
Graficamente...
Solução única:
Retas concorrentes. A solução é o ponto onde as retas se cruzam.
Infinitas soluções:
Retas coincidentes. Todos os pontos sobre a reta são soluções do sistema.
O sistema não admite solução:
Retas paralelas. As retas não se cruzam e, portanto, não existe nenhum ponto que esteja sobre as duas ao mesmo tempo.
*
*
Número de soluções
No caso geral...
Precisamos analisar o Posto e a Imagem da matriz A, de acordo com suas dimensões m e n.
*
*
Número de soluções
Solução única
*
*
Número de soluções
As colunas de A são Linearmente Independentes e formam uma base do R2. 
b pode ser escrito como combinação linear das colunas de A.
Sistema compatível determinado
*
*
Número de soluções
Infinitas soluções
*
*
Número de soluções
As colunas de A são Linearmente Dependentes e não formam uma base do R2. 
Basta uma coluna de A para escrever b.
Sistema compatível indeterminado
*
*
Número de soluções
Não admite solução
*
*
Número de soluções
As colunas de A são Linearmente Dependentes e não formam uma base do R2. 
b não pode ser escrito como combinação das colunas de A.
Sistema incompatível
*
*
Número de soluções
Essas situações se estendem para o caso geral, sempre que m = n.
Quando m ≠ n, temos:
posto(A) ≤ min{m, n}
se m < n o sistema nunca pode ter solução única, pois posto(A) < n
se m > n o sistema pode não ter solução
*
*
Número de soluções
Quadro-resumo...
*
*
Métodos de resolução
*
*
Métodos de resolução
Veremos aqui métodos para a resolução sistemas com n linhas e n variáveis (a matriz A deve ter posto completo).
Os métodos de resolução podem ser divididos em dois grupos:
Métodos Diretos
Métodos Iterativos
Veremos dois métodos diretos: Eliminação de Gauss e Fatoração LU
*
*
Métodos de resolução
Mas... só uma pergunta antes de começar...
Se a matriz A é quadrada, por que não fazer x = A-1 b ?
*
*
Eliminação de Gauss
*
*
Eliminação de Gauss
Qual sistema é mais fácil de ser resolvido?
(2)
(1)
*
*
Eliminação de Gauss
Algoritmo...
*
*
Eliminação de Gauss
Consiste em transformar o sistema a ser resolvido em um sistema triangular equivalente, por meio de operações elementares. A solução é então obtida, resolvendo-se um sistema triangular.
*
*
Eliminação de Gauss
zerar estes elementos
*
*
Eliminação de Gauss
Operações elementares:
Trocar duas equações;
Multiplicar uma equação por uma constante não-nula;
Adicionar um múltiplo de uma equação a uma outra equação.
Garantem que o sistema obtido é equivalente ao original
*
*
Eliminação de Gauss
*
*
Eliminação de Gauss
*
*
Eliminação de Gauss
Zerar esses elementos
utilizando operações
elementares
*
*
Eliminação de Gauss
pivô
Zerar esses elementos
utilizando operações
elementares
*
*
Eliminação de Gauss
*
*
Eliminação de Gauss
Zerar esses elementos
utilizando operações
elementares
pivô
*
*
Eliminação de Gauss
*
*
Eliminação de Gauss
Multiplicador
...
Iteração 1
*
*
Eliminação de Gauss
Obs.: devemos ter , para todo k = 1, ..., n
*
*
Eliminação de Gauss
Exemplo
*
*
Eliminação de Gauss
Algoritmo...
*
*
Eliminação de Gauss
Estratégias de pivoteamento
O que acontece se o pivô for nulo?
Pivô próximo de zero pode levar a resultados totalmente imprecisos.
Para contornar esses dois problemas deve-se adotar uma estratégia para a escolha de um “bom” pivô.
*
*
Eliminação de Gauss
Pivoteamento parcial
Escolher para pivô o elemento de maior módulo na coluna, dentre os que ainda irão atuar no processo de eliminação.
Pivoteamento completo
Escolher para pivô o elemento de maior módulo dentre todos os elementos que ainda irão atuar no processo de eliminação
*
*
Eliminação de Gauss
*
*
Fatoração LU
*
*
Fatoração LU
Decompor a matriz A em um produto de dois fatores:
L: matriz triangular inferior
U: matriz triangular superior
Ax = b LU x = b
A = LU
*
*
Fatoração LU
U é a matriz triangular resultante na eliminação de Gauss.
Quem é L então?
Por que utilizar a fatoração LU se vamos obter a mesma matriz da eliminação de Gauss?
*
*
Fatoração LU
U é a matriz triangular resultante na eliminação de Gauss.
Quem é L então?
Por que utilizar a fatoração LU se vamos obter a mesma matriz da eliminação de Gauss?
Continua na próxima aula...
*
*
Bibliografia
Ruggiero, MAG; Lopes, VLR. Cálculo numérico. 2ª edição. 1998.