379728-2_MNC-Sistemas_Equacoes_Lineares

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

Sistemas de Equações Lineares
Unidade - 2
Prof.: Silvio Alves
CEFET – MG
Centro Federal de Educação Tecnológica de Minas Gerais
1
Métodos Numéricos e Computacionais
2.1 Conceitos fundamentais;
2.2 Sistemas triangulares;
2.3 Eliminação de Gauss;
2.4 Decomposição LU;
2.5 Decomposição de Cholesky e ;
2.6 Métodos iterativos Estacionários;
2.7 Análise de erro na solução de sistemas.
Sumário
2
Métodos Numéricos e Computacionais
		Um sistema de equações algébricas lineares consiste em um conjunto de m equações e n variáveis de grau 1,
2.1 Conceitos fundamentais
n variáveis
3
Métodos Numéricos e Computacionais
3
4
Métodos Numéricos e Computacionais
Que pode ser representado na forma matricial por
5
Métodos Numéricos e Computacionais
Ou seja
Onde A é uma matriz denominada matriz dos coeficientes, x é o vetor de soluções e b é o vetor de termos independentes.
O número de soluções de um sistema de equações depende do determinante da matriz A.
6
Métodos Numéricos e Computacionais
 Determinado: 
 Uma única solução. Neste caso
 
Exemplo:
Classificação de sistemas
7
Métodos Numéricos e Computacionais
 Várias soluções ou infinitas soluções. Neste caso temos
Exemplo:
8
Métodos Numéricos e Computacionais
 Indeterminado: não possui solução. Neste caso
Exemplo:
9
Métodos Numéricos e Computacionais
 Os sistemas triangulares são utilizados pois suas soluções são fáceis de serem encontradas utilizando substituições sucessivas;
 Podemos ter sistemas triangulares inferiores e superiores;
2.2 Sistemas triangulares
10
Métodos Numéricos e Computacionais
2.2.1 Sistema Triangular inferior
11
Métodos Numéricos e Computacionais
Solução sistema triangular inferior 
12
Métodos Numéricos e Computacionais
2.2.2 Sistema Triangular Superior
13
Métodos Numéricos e Computacionais
Solução sistema triangular superior 
14
Métodos Numéricos e Computacionais
Calcular a solução do sistema triangular inferior usando substituições sucessivas:
Exemplo:
15
Métodos Numéricos e Computacionais
 Métodos diretos: solução exata é obtida, teoricamente, com um número finito de operações aritméticas;
 Métodos indiretos: solução exata é obtida, com um número infinito de operações ;
 O método de eliminação de Gauss é um método direto;
2.3 Eliminação de Gauss
16
Métodos Numéricos e Computacionais
 Definição: Dois sistemas de equações lineares são equivalentes quando possuem a mesma solução.
 Exemplo:
2.3.1 Sistemas Equivalentes
17
Métodos Numéricos e Computacionais
		Utilizando operações L-elementares podemos encontrar sistemas equivalentes. Este sistema equivalente deve ser triangular.
Operações:
 Trocar a ordem de duas equações;
 Multiplicar uma equação por uma constante não nula;
 Somar uma equação à outra.
2.3.2 Operações L-elementares
18
Métodos Numéricos e Computacionais
 A eliminação de Gauss consiste em resolver sistemas utilizando operações L-elementares para encontrar sistemas equivalentes cuja matriz A seja triangular..
19
Métodos Numéricos e Computacionais
		Resolver o sistema de equações pelo método de eliminação de Gauss.
 
Exemplos:
20
Métodos Numéricos e Computacionais
 
21
Métodos Numéricos e Computacionais
 O método de eliminação de Gauss irá falhar quando um pivô for nulo. 
 Este problema pode ser resolvido utilizando a pivotação parcial que consiste em escolher como pivô o maior elemento (em módulo) da coluna, cujos elementos serão eliminados. 
 A pivotação parcial garante que o pivô seja não nulo, exceto quando a matriz for singular.
 OBS: Uma matriz é singular se seu determinante é nulo.
2.3.3 Pivotação parcial
22
Métodos Numéricos e Computacionais
 Escolher a linha pivotal;
 Encontrar os multiplicadores ;
 A linha pivotal deverá ser multiplicada pelo fator 
e somado à outra linha, a que será substituída;
Passos 
23
Métodos Numéricos e Computacionais
 Resolver o sistema pelo método de Gauss com pivotação parcial.
Exemplo
24
Métodos Numéricos e Computacionais
Resolver o sistema pelo método de Gauss com pivotação parcial.
1.
Exercícios
25
Métodos Numéricos e Computacionais
2. 
26
Métodos Numéricos e Computacionais
3. 
27
Métodos Numéricos e Computacionais
 Considere a matriz
2.4 Decomposição LU
 Matriz A pode ser escrita como produto de duas outras
28
Métodos Numéricos e Computacionais
 Assim a matriz A foi fatorada de modo que A=LU, onde L é uma matriz triangular inferior unitária, ou seja
29
Métodos Numéricos e Computacionais
e U é uma matriz triangular superior. 
Assim, para resolver Ax=b, usamos a decomposição
30
Métodos Numéricos e Computacionais
 A matriz triangular U é a mesma matriz triangular encontrada no método de Gauss sem pivotação parcial;
 A solução do sistema triangular Ly=b é obtida pelas substituições sucessivas;
 O vetor y é usado como termo independente no sistema triangular superior Ux=y, cuja solução x é calculada pelas substituições retroativas.
31
Métodos Numéricos e Computacionais
 A matriz triangular L possui 
onde representa os multiplicadores utilizados no processo de Gauss sem pivotação parcial. 
 Exemplo de matriz L, caso 3x3 
32
Métodos Numéricos e Computacionais
 Não podemos permutar as linhas da matriz A para fazer a decomposição e achar a matriz U pois, neste caso, a decomposição fica errada.
Exemplo: Considere a matriz
Observações
33
Métodos Numéricos e Computacionais
Usando Gauss sem pivotação parcial, ou seja, sem permutar linhas, encontramos
Métodos Numéricos e Computacionais
34
Neste caso temos
Usando Gauss com pivotação parcial, ou seja, permutando as linhas 1 e 2 da matriz A, temos
Métodos Numéricos e Computacionais
35
Neste caso encontramos
Neste caso podemos observar que
Métodos Numéricos e Computacionais
36
 Assim, se desejamos permutar as linhas da matriz A deveremos utilizar o método LU com pivotação parcial. Este tema será tratado na próxima seção.
 Resolver o sistema pelo método da decomposição LU.
Exemplo
37
Métodos Numéricos e Computacionais
Resolva utilizando decomposição LU:
 
Exercícios
38
Métodos Numéricos e Computacionais
2. 
39
Métodos Numéricos e Computacionais
3. 
40
Métodos Numéricos e Computacionais
4. Desafio 
41
Métodos Numéricos e Computacionais
 Afim de evitar pivô nulo e que os multiplicadores m tenham valores muito grandes usamos a decomposição LU com pivotação parcial dada por
Decomposição LU com pivotação parcial
42
Métodos Numéricos e Computacionais
 Onde P é uma matriz de permutações, que será constituída das linhas de uma matriz identidade I, colocadas na mesma ordem das linhas pivotais que geram a matriz triangular superior U;
 Se utilizarmos operações L-elementares para encontrar U então temos que construir P a partir da matriz original, verificando quais linhas utilizadas como pivotais;
 L : mesma matriz método Gauss sem pivotação;
 U : mesma matriz método Gauss sem pivotação. 
43
Métodos Numéricos e Computacionais
Resolver o sistema usando decomposição LU com pivotação parcial.
1.
Exemplo
44
Métodos Numéricos e Computacionais
2. 
45
Métodos Numéricos e Computacionais
		Quando a matriz dos coeficientes A for simétrica e definida positiva então A pode ser decomposta tal que
2.5 Decomposição de Cholesky 
onde 
 é uma matriz triangular inferior e
 será matriz triangular superior.
46
Métodos Numéricos e Computacionais
Fazemos
Solução do sistema
47
Métodos Numéricos e Computacionais
 Uma matriz A é simétrica se: 
Definições
 Uma matriz A é definida positiva se para todo vetor v tivermos 
48
Métodos Numéricos e Computacionais
 Em uma matriz definida positiva os autovalores são todos positivos, ou seja:
Métodos Numéricos e Computacionais
49
		Considere o exemplo de ordem 3.
50
Métodos Numéricos e Computacionais
Para qualquer elemento da diagonal principal de L temos:
Cálculo dos coeficientes da diagonal principal
51
Métodos Numéricos e Computacionais
 Para qualquer elemento abaixo da diagonal principal de L temos:
Cálculo dos coeficientes abaixo da diagonal principal
52
Métodos Numéricos e Computacionais
 Resolver o sistema usando a decomposição de Cholesky. Verificar unicidade e exatidão.
Exemplo
53
Métodos Numéricos e Computacionais
Resolver o sistema usando a decomposição de Cholesky. Verificar unicidade e exatidão.
1.
Exercícios
54
Métodos Numéricos e Computacionais
		Quando a matriz dos coeficientes A for simétrica ela pode ser decomposta tal que
Fatoração 
onde 
 é uma matriz triangular inferior unitária 
 é uma matriz diagonal.
55
Métodos Numéricos e Computacionais
Onde 
56
Métodos Numéricos e Computacionais
Fazemos
Solução do sistema
57
Métodos Numéricos e Computacionais
Resolver o sistema pelo método de fatoração 
Exemplo
58
Métodos Numéricos e Computacionais
Resolver os sistemas utilizando fatoração
1. 
Exercício
59
Métodos Numéricos e Computacionais
2. 
60
Métodos Numéricos e Computacionais
 Um sistema de equações lineares Ax=b pode ser resolvido por um processo que consiste em gerar, a partir de um vetor inicial , uma sequência de vetores
que deve convergir para a solução x do sistema. Tal processo é chamado iterativo. 
Métodos iterativos estacionários
61
Métodos Numéricos e Computacionais
 Seja uma matriz M chamada de matriz de iteração e c um vetor constante. Um método iterativo escrito na forma
é dito estacionário quando a matriz M for fixa, ou seja, quando ela não for alterada durante o processo.
62
Métodos Numéricos e Computacionais
 A cada passo a solução é obtida com exatidão crescente, isto é,
 
Dado um o processo é interrompido quando
Critério de parada
63
Métodos Numéricos e Computacionais
ou quando
onde é a tolerância e é o número máximo de iterações.
 Nos algoritmos adotaremos norma infinita
64
Métodos Numéricos e Computacionais
Teorema de convergência: É condição suficiente para convergência do método de Jacobi que a matriz dos coeficientes A seja diagonal estritamente dominante, ou seja,
Método de Jacobi
65
Métodos Numéricos e Computacionais
 Considere o sistema
66
Métodos Numéricos e Computacionais
 Na forma iterativa temos
67
Métodos Numéricos e Computacionais
 Encontre o sistema iterativo pelo método iterativo de Jacobi
Exemplo
68
Métodos Numéricos e Computacionais
Como pequenas variações nos elementos da matriz dos coeficientes A e ou no vetor b influenciam na solução x do sistema linear Ax=b.
Análise de erros na solução de sistemas
69
Métodos Numéricos e Computacionais
 Um sistema linear com matriz A tal que
ou seja, a matriz a é quase singular.
 Exemplo
Malcondicionamento
70
Métodos Numéricos e Computacionais