04MN_SL2

Prévia do material em texto

Prof. Erivelton Geraldo Nepomuceno
2016
SISTEMAS DE EQUAÇÕES LINEARES
(Continuação)
 
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
UNIVERSIDADE DE JOÃO DEL-REI 
PRÓ-REITORIA DE PESQUISA
CENTRO FEDERAL DE EDUCAÇÃO 
TECNOLÓGICA DE MINAS GERAIS 
DIRETORIA DE PESQUISA E PÓS-GRADUAÇÃO
étodos
uméricos
Eliminação de Gauss
 Operações l-elementares:
Um SL poder ser transformado em um outro equivalente (que
possui a mesma solução) utilizando as 3 operações l-elementares
(operações de linha):
▪ Trocar a ordem de duas equações:
O método de Eliminação de Gauss consiste em transformar o sistema
dado num sistema triangular equivalente através de uma seqüência de
operações elementares sobre as linhas do sistema original.
2
Eliminação de Gauss
▪ Somar uma equação à outra:
Então é possível transformar um SL em um outro de solução mais fácil.
▪ Multiplicar uma equação por constante não nula:
3
Eliminação de Gauss
 Sistema triangular equivalente:
O método de eliminação de Gauss consiste em transformar um SL
em um sistema triangular superior equivalente por meio das
operações l-elementares.
4
Eliminação de Gauss
▪ A transformação pode ser representada por: Ax = b  Ux = d.
▪ A Solução do sistema triangular superior Ux = d é obtida
pelas substituições retroativas.
▪ A exatidão pode ser verificada pelo cálculo do vetor resíduo.
r = b - Ax.
▪ Exemplo: Resolver o sistema pelo método de eliminação de
Gauss e verificar a exatidão da solução:
5
Eliminação de Gauss
▪ Eliminar elementos da primeira coluna:
Elemento pivô
Linha pivotável
▪ Eliminar elementos da segunda coluna:
Elemento pivô
Linha pivotável
6
Eliminação de Gauss
▪ Sumário das operações:
▪ Sistema triangular superior obtido:
7
Eliminação de Gauss
▪ Solução do sistema: substituições retroativas:
▪ Cálculo do resíduo:
8
Eliminação de Gauss
▪ Exemplo:
9
Eliminação de Gauss
10
Eliminação de Gauss
 Cálculo do determinante:
▪ O determinante da matriz dos coeficientes pode ser obtido
como um subproduto do método de Gauss.
▪ Deve-se conhecer as relações entre os determinantes das
várias matrizes dos sistemas equivalentes intermediários
obtidos pelas operações l-elementares durante o processo de
eliminação de Gauss.
▪ a) Se duas linhas quaisquer de uma matriz A forem trocadas,
então, o determinante da nova matriz B é:
11
Eliminação de Gauss
▪ b) Se todos os elementos de uma linha de A forem
multiplicados por uma constante k, então, o determinante da
matriz resultante B será:
▪ c) Se um múltiplo escalar de uma linha de A for somado à outra
linha, então, o determinante da nova matriz B é:
12
Eliminação de Gauss
▪ d) Se A for uma matriz triangular ou diagonal de ordem n,
então, o seu determinante será igual ao produto dos elementos
da diagonal principal:
13
Eliminação de Gauss
▪ e) Se uma matriz A for multiplicada por uma matriz B, então, o
determinante da matriz resultante C é:
14
Eliminação de Gauss
▪ Exemplo: calcular o determinante da matriz:
Sequência de matrizes obtidas pelas operações l-elementares:
Matrizes obtidas somente por combinações lineares das linhas,
logo as três matrizes possuem o mesmo determinante que é igual
ao produto dos elementos da diagonal (produto dos pivôs):
15
Eliminação de Gauss
▪ O método de Gauss falha quando o pivô é nulo (ou  0 ).
▪ O método de Gauss intensifica a propagação dos erros de
truncamento do computador (Multiplicadores grandes),
principalmente em sistemas grandes.
▪ Estes problemas podem ser evitados utilizando pivotação
parcial, que consiste em escolher como pivô o maior elemento
em módulo da coluna, cujos elementos serão eliminados.
▪ A estratégia de pivotamento parcial é baseada na operação
elementar: Troca de duas equações.
▪ Todos os multiplicadores satisfazem -1  mij  1.
 Pivotação Parcial:
16
Eliminação de Gauss
▪ Exemplo: Seja o sistema e sua solução:
Solução pelo método de Eliminação de Gauss, com 3 dígitos
significativos em todas as operações:
Solução utilizando Pivotação Parcial :
17
Eliminação de Gauss
▪ Exemplo: Resolver o sistema pelo método de Gauss com
pivotação parcial.
18
Eliminação de Gauss
19
Decomposição LU
Uma matriz quadrada qualquer pode ser escrita como o produto de
duas matrizes:
▪ A matriz A é fatorada tal que A = LU.
▪ L: matriz triangular inferior unitária.
▪ U: matriz triangular superior.
▪ Para resolver o sistema Ax = b, tem-se:
20
Decomposição LU
 Calculo dos fatores:
▪ A matriz triangular superior U é a mesma do método de Gauss;
▪ Para a matriz triangular inferior unitária L
▪ lii=1;
▪ lij i>j = 0
▪ lij = - mij, i < j, sendo mij os multiplicadores utilizados no
processo de eliminação de Gauss.
▪ Exemplo:
21
Decomposição LU
Eliminação de Gauss:
Matrizes L e U:
22
Decomposição LU
Igualdade A = LU:
Solução do sistema Ly = b:
23
Decomposição LU
Solução do sistema Ux = y:
A vantagem deste método é a eficiência computacional, pois
pode-se escolher qualquer novo o vetor b que não é necessário
voltar a fazer a eliminação de Gauss.
24
Decomposição LU
 Pivotação Parcial:
▪ Utilizada, assim como na eliminação de Gauss, para evitar pivô
nulo e multiplicadores com valores grandes.
▪ Neste caso a Decomposição é da forma: PA = LU.
▪ P: matriz de permutações (construída das linhas de uma matriz
identidade I, colocadas na mesma ordem das linhas
pivotacionais que geram a matriz U).
▪ L: matriz triangular inferior unitária formada pelos
multiplicadores, com sinais contrários.
▪ U: matriz triangular superior.
▪ Para resolver o sistema Ax = b tem-se:
25
Decomposição LU
▪ Exemplo:
Eliminação de Gauss:
26
Decomposição LU
Solução do sistema Ly = Pb:
27
Decomposição LU
Solução do sistema Ux = y:
28
Decomposição LU
 Cálculo do determinante:
Pelas propriedades dos determinantes:
(Propriedade e)
(Propriedade d)
(Propriedade a)
p: numero de trocas de linhas necessárias para transformar a matriz
de permutações em identidade. Logo:
29
Decomposição LU
▪ Exemplo: Calcular o determinante de:
Matrizes U e P:
Valor de p:
determinante:
30
Decomposição LU
▪ Exemplo: Calcular o determinante de:
Eliminação de Gauss:
31
Decomposição LU
Solução do sistema Ly = Pb
Matrizes L, U e P:
Solução do sistema Ux = y
32
Decomposição LU
Unicidade da solução:
Exatidão:
33
Decomposição LU
 Sistema com matriz singular:
Para um SL Ax=b, onde det(A) = 0, o sistema pode ter infinitas
soluções ou não ter soluções.
▪ Sistema com infinitas soluções. Resolver o sistema Ax = b:
34
Decomposição LU
Solução do sistema Ly = Pb
Solução do sistema Ux = y
35
Decomposição LU
36
Decomposição LU
▪ Sistema sem solução. Resolver o sistema Ax = c:
Solução do sistema Ly = Pc
37
Decomposição LU
Solução do sistema Ux = y
38
Decomposição de Cholesky
SE a matriz dos coeficientes, A, é simétrica e definida
Positiva:
A decomposição LU pode ser simplificada para:
e
L: matriz triangular inferior. LT : matriz triangular superior.
Teorema (Cholesky)
Se A for uma matriz simétrica e definida positiva, então existe uma 
única matriz triangular L com elementos da diagonal positivos tal 
que A = LLT .
No caso em que a 
matriz do sistema 
linear é simétrica
pode-se simplificar 
os cálculos da 
decomposição LU 
significativamente, 
levando em conta a 
simetria.
39
Decomposição de Cholesky
 Cálculo do fator:
▪ Obtenção do fator L da Decomposição LLT = A:
▪ O elemento l44 da diagonal é obtido por:
▪ Generalizando para qualquer elemento da diagonal:
40
Decomposição de Cholesky
▪ O elemento l43 é obtido por:
▪ Elemento genérico abaixo da diagonal:
e
41
Solução estável, não requer pivotação !!!
Decomposição de Cholesky
 Solução de Ax = b por Cholesky :
e
▪ Sistema triangular inferior Ly = b:
▪ Sistema triangular superior LTx = y :
42
Decomposição de Cholesky
 Cálculo do determinante:
Por meio das propriedades d) e e) dos determinantes tem-se:
▪ Exemplo: Resolver o sistema:
Coluna 1:
43
Decomposiçãode Cholesky
Coluna 2:
Coluna 3:
44
Decomposição de Cholesky
Resumindo:
Verificação LLT=A:
45
Decomposição de Cholesky
Sistema Ly=b:
Sistema LTx=y:
46
Decomposição de Cholesky
Exatidão:
Solução exata
Unicidade:
Solução única
47
Decomposição de Cholesky
▪ Exemplo: Resolver o sistema:
Coluna 1:
Coluna 2:
48
Decomposição de Cholesky
Coluna 3:
Coluna 4:
Resumo:
49
Decomposição de Cholesky
Sistema Ly=b:
Sistema LTx=y:
50
Decomposição de Cholesky
Exatidão:
Unicidade:
Solução única
Solução exata
Matriz L:
51
Decomposição de Espectral
▪ Uma matriz A de ordem n possui auto-valores i, i = 1, 2, ... , n.
▪ Cada auto-valor tem um auto-vetor correspondente.
▪ Generalizando a relação
▪ matriz diagonal contendo os auto-
valores i.
▪ V : matriz cujas colunas são os auto-vetores vi.
▪ Pós-multiplicando por V-1
▪ Matriz A decomposta em termos de seus auto-valores e auto-
vetores.
52
Decomposição de Espectral
 Cálculo dos Auto-vetores:
▪ Da relação fundamental
▪ Como a matriz é singular:
▪ E o sistema é homogêneo.
▪ Ele apresenta infinitas soluções vi.
▪ Atribuir um valor arbitrário a um elemento de v, p.ex., vi1 = 1.
▪ Obter os demais elementos do auto-vetor vi pela solução do
sistema resultante de ordem n -1.
53
Decomposição de Espectral
▪ Exemplo: Fazer a decomposição espectral da matriz:
Polinômio Característico:
Os três zeros do polinômio característico são os três
auto-valores de A:
e
54
Decomposição de Espectral
Matriz  contendo os auto-valores:
Sistema homogêneo:
Auto-vetor v correspondente a 1 = 4
Eq. 1 e 2 são redundantes. Elimina-se a 2ª e faz-se v11 = 1
55
Decomposição de Espectral
Sistema homogêneo:
Auto-vetor w correspondente a 2 = 1
Eq. 1 e 3 são redundantes. Elimina-se a 3ª e faz-se w 11 = 1
56
Decomposição de Espectral
Sistema homogêneo:
Auto-vetor z correspondente a 3 = -3
Eq. 2 e 3 são redundantes. Elimina-se a 3ª e faz-se z11 = 1
57
Decomposição de Espectral
Matriz V contendo os auto-vetores de A:
Inversa de V:
Decomposição espectral 
58
Decomposição de Espectral
 Solução de sistema:
▪ Solução de Ax = b obtida por x = A-1b.
▪ Vetor solução x depende de i
-1
▪ No caso de quase singularidade da matriz A (pelo menos um
auto-valor com valor próximo de zero).
▪ Solução x tem elementos muito grandes.
59
Decomposição de Espectral
▪ Exemplo: Calcular a solução do sistema:
Sabendo que:
Solução exata:
Grande custo computacional. 
Normalmente, não é utilizada 
para a solução de SL.
60
1. Aderito Luis Martins Araujo , Analise Numérica Engenharias 
Mecânica e de Materiais.
2. Frederico Ferreira Campos Filho, Algoritmos Numéricos. 
Referencias Bibliográficas
61