Aula 9 - SL_Fatoração LU - REMOTA

Prévia do material em texto

04/05/20
1
Sistemas de Equações Lineares - Aulas remotas
04.05.2020
Prof. João Paulo
ATENÇÃO
O CONTEÚDO AUDIOVISUAL A SEGUIR É PARA USO 
EXCLUSIVAMENTE ACADÊMICO E ESTÁ PROTEGIDO PELAS 
LEIS DE PROPRIEDADE INTELECTUAL, SENDO VEDADA SUA 
CESSÃO OU OUTRA FORMA DE UTILIZAÇÃO NÃO 
AUTORIZADA, DO TODO OU DE QUALQUER PARTE
1
2
04/05/20
2
AGENDA
Sistemas de Equações Lineares
• Métodos Diretos:
i. Fatoração LU pelo Método de Crout
ii. Fatoração LU por Eliminação de Gauss
• Métodos Iterativos:
i. Método de Jacobi
ii. Método de Gauss-Seidel
iii. Critérios de Convergência
AGENDA
Sistemas de Equações Lineares
• Métodos Diretos:
i. Fatoração LU pelo Método de Crout
ii. Fatoração LU por Eliminação de Gauss
• Métodos Iterativos:
i. Método de Jacobi
ii. Método de Gauss-Seidel
iii. Critérios de Convergência
3
4
04/05/20
3
Introdução
• O que é um sistema de equações lineares?
• Para que serve?
Do básico com 2 variáveis
• Sistemas de duas variáveis e duas equações
• Exemplo:
2x + y = 5
x – y = 1
• A resolução desse sistema nos dará os valores de x e y 
que satisfazem às duas equações ao mesmo tempo.
• Nesse caso, podemos resolver por substituição/adição 
e chegamos à solução x=2, y=1.
5
6
04/05/20
4
E como resolver sistemas com mais de 
duas variáveis ?
• Será que podemos fazer por substituição?
• Como fazer um computador resolver um sistema de 
equações lineares?
Dois tipos de métodos:
• Métodos diretos:
– “São métodos que ao cabo de um número finito de 
operações apresentam, teoricamente, a solução exata do 
sistema em estudo.”
• Métodos Iterativos:
– “Os métodos iterativos conduzem a uma solução 
aproximada, mas com erro controlado, têm vantagens 
computacionais e implicam menos recursos de memória 
do que os métodos diretos”
7
8
04/05/20
5
Formas de representação
• Equações:
• Matriz: �� = �
– A: matriz n x n (cada elemento representado por aij)
– b: vetor de tamanho n (cada elemento bi)
– x: vetor de tamanho n (cada elemento xj)
– i,j: 1, 2, ..., n
• Somatório: 
– ∑ ����� = ��
�
��� , � = 1,2, . . , �.
E hoje?
Apresentaremos dois métodos diretos para resolução de 
sistemas de equações lineares:
• Já vistos em Álgebra Linear: 
– Cramer
– Eliminação de Gauss
– Eliminação de Gauss-Jordan
• Novos: 
– Fatoração LU pelo método de Crout
– Fatoração LU por Eliminação de Gauss
9
10
04/05/20
6
FATORAÇÃO LU OU
MÉTODO DE DECOMPOSIÇÃO LU
Método de Decomposição LU
• Seja o sistema Ax = b
• No Método de Decomposição LU a matriz A é decomposta 
em duas matrizes L e U, onde A=L.U.
– L: matriz triangular inferior (Lower)
– U: matriz triangular superior (Upper)
• Logo, LUx = b.
• Ou Ly = b e Ux = y. 
• *De acordo com o método, podemos ter pequenas 
diferenças na formação dessas matrizes.
11
12
04/05/20
7
Exemplo
Exemplo
• Logo, x1= -21/5 e x2=-29/10
13
14
04/05/20
8
Pergunta:
Como calcular as matrizes L e U?
- Depende do método de fatoração utilizado.
FATORAÇÃO LU
MÉTODO DE CROUT
15
16
04/05/20
9
Método de Crout
• Seja o sistema Ax = b
• No Método de Decomposição LU pelo Método de 
Crout, a matriz A é decomposta em duas matrizes L e U.
– L: matriz triangular inferior (Lower)
– U: matriz triangular superior com os elementos da 
diagonal principal iguais a 1. (Upper)
• Logo, LUx = b.
• E podemos fazer Ly = b e Ux = y.
Método de Crout
• “A decomposição A = LU existirá e será única se as 
condições do Teorema a seguir forem satisfeitas.”
17
18
04/05/20
10
Teorema
• Uma matriz de números reais, A, de ordem n x n tem uma decomposição LU se 
det (A(1:k; 1:k)) ≠ 0 para k=1,2,3,..., n. Se a decomposição LU existe e A é não 
singular (admite inversa), então a decomposição LU é única e det(A) = l11 x l22 x l33 
x...x lnn.
Obtendo L e U
• Como calculamos o produto de duas matrizes?
• Exemplo 3x3
19
20
04/05/20
11
Obtendo L e U
Obtendo L e U
• Passo 1: Se j=1, min{i, j}=1
– Os elementos da 1ª coluna de L são iguais aos da 
1ª coluna de A.
• Passo 2: Se i=1, min{i, j}=1
– Os elementos da primeira linha de U são a razão 
dos elementos da primeira linha de A por l11.
21
22
04/05/20
12
Obtendo L e U
• Passo 3: Se j=2, i≥j=2 , min{i, j}=2
– Definimos a segunda coluna de L
– ai2:conhecido, pois é elemento de A
– li1:conhecido, pois é elemento da primeira coluna de L
– u12:conhecido, pois é elemento da primeira linha de U (passo 2)
Obtendo L e U
• Passo 4: se i=2, j>i=2 ; min{i, j}=2
– Definimos a segunda linha de U
– a2j: conhecido, pois vem da matriz A
– l21: conhecido do passo anterior
– u1j: conhecido do passo 2
– l22: conhecido do passo anterior
23
24
04/05/20
13
Obtendo L e U
• Generalizando:
• Na seguinte ordem: li1, u1j ,li2 ,u2j,...
Fatoração LU por Crout
• Exemplo 1: Resolva o Sistema de Equações Lineares abaixo pela 
Fatoração LU utilizando o Método de Crout.
25
26
04/05/20
14
Exemplo 1
• Inicialmente faremos a decomposição da matriz dos coeficientes
do Sistema (Matriz A), nas matrizes L e U, onde A=L.U: 
Exemplo 1
• Roteiro:
1. Encontrar as matrizes L e U, onde para cada coluna de L 
calculada, deve-se encontrar uma linha de U;
2. Encontrar os Y’s fazendo Ly=b.
3. Encontrar os X’s (raízes) fazendo Ux=y.
27
28
04/05/20
15
Exemplo 1
• 1ª coluna de L
• 1ª linha de U
Exemplo 1
• 2ª coluna de L
• 2ª linha de U
29
30
04/05/20
16
Exemplo 1
• 3ª coluna de L
Exemplo 1
Logo, o conjunto solução é S={1, 1, 1}
31
32
04/05/20
17
Conclusão sobre o Método de Crout:
• “Este método é particularmente muito importante 
quando o usuário tem muitos sistemas de 
equações lineares com os mesmos coeficientes 
das variáveis (Matriz A), mudando apenas os 
valores do vetor independente (Matriz b). Isto se 
deve ao fato de que não é necessário repetir a 
decomposição LU já realizada.”
FATORAÇÃO LU
POR ELIMINAÇÃO DE GAUSS
33
34
04/05/20
18
Fatoração LU por Eliminação de Gauss
• Seja o sistema Ax = b
• No Método de Decomposição LU por Eliminação de Gauss, a matriz A é 
decomposta em duas matrizes L e U.
– L: matriz triangular inferior (Lower) utilizando os coeficientes de eliminação de 
Gauss (Mij) , com os elementos da diagonal principal iguais a 1. 
– U: matriz triangular superior (Upper) elaborada a partir de A, procurando zerar 
os elementos abaixo da diagonal principal através de operações com o 
elemento pivô (o que fica em cima do elemento a ser zerado) e encontrando 
os coeficientes de eliminação (Mij).
– Nesse método primeiramente encontramos a Matriz U e depois apenas 
montamos a Matriz L.
• Logo, LUx = b.
• E podemos fazer Ly = b e Ux = y.
Fatoração LU por Eliminação de Gauss
• Onde na verdade os elementos dentro do triângulo são os 
coeficientes de eliminação de Gauss, tal que lij=mij.
• “A decomposição A = LU existirá e será única se as condições do 
Teorema já apresentadas no Método de Crout forem satisfeitas.”
35
36
04/05/20
19
Fatoração LU por Eliminação de Gauss
• Exemplo 1: Resolva o Sistema de Equações Lineares abaixo pela 
Fatoração LU utilizando o Método de Eliminação de Gauss.
Exemplo 1
• Inicialmente faremos a decomposição da matriz dos coeficientes
do Sistema (Matriz A), nas matrizes L e U, onde A=L.U: 
37
38
04/05/20
20
Exemplo 1
• Roteiro:
1. Encontrar a matriz U através da Tabela de Eliminação de 
Gauss;
2. Montar a matriz L a partir dos coeficientes usados para achar a 
matriz U;
3. Encontrar os Y’s fazendo Ly=b.
4. Encontrar os X’s (raízes) fazendo Ux=y.
Exemplo 1
• Tabela de Eliminação de Gauss
1a Linha (Matriz A) 5 2 1
m21 (queremos zerar a21)
2a Linha
m31 (queremos zerar a31)
3a Linha (versão 1)
m32 (queremos zerar a32)
3a Linha (versão 2)
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
39
40
04/05/20
21
Exemplo 1
• Tabela de Eliminação de Gauss
1a Linha (Matriz A) 5 2 1
m21 = 3/5
2a Linha
=3-(3/5)x5 = 0 =6-(3/5)x2 = 24/5 =-2-(3/5)x1 = -13/5
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
Exemplo 1
• Tabela de Eliminaçãode Gauss
1a Linha (Matriz A) 5 2 1
m21 = 3/5
2a Linha
=3-(3/5)x5 = 0 =6-(3/5)x2 = 24/5 =-2-(3/5)x1 = -13/5
m31 = 2/5
3a Linha (versão 1)
=2-(2/5)x5 = 0 =-4-(2/5)x2 = -24/5 =10-(2/5)x1 = 48/5
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
U’p =
41
42
04/05/20
22
Exemplo 1
• Tabela de Eliminação de Gauss
1a Linha (Matriz A) 5 2 1
m21 = 3/5
2a Linha
=3-(3/5)x5 = 0 =6-(3/5)x2 = 24/5 =-2-(3/5)x1 = -13/5
m31 = 2/5
3a Linha (versão 1)
=2-(2/5)x5 = 0 =-4-(2/5)x2 = -24/5 =10-(2/5)x1 = 48/5
m32 = (-24/5)/(24/5) = -1
3a Linha (versão 2)
= 0-(-1)x0 = 0 = (-24/5)-(-1)x(24/5) 
= (-24/5)+(24/5) = 0 
= (48/5)-(-1)x(-13/5) = 
(48/5)-(13/5) = 7 
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
U’p =
Exemplo 1
• Tabela de Eliminação de Gauss
1a Linha (Matriz A) 5 2 1
m21 = 3/5
2a Linha
=3-(3/5)x5 = 0 =6-(3/5)x2 = 24/5 =-2-(3/5)x1 = -13/5
m31 = 2/5
3a Linha (versão 1)
=2-(2/5)x5 = 0 =-4-(2/5)x2 = -24/5 =10-(2/5)x1 = 48/5
m32 = (-24/5)/(24/5) = -1
3a Linha (versão 2)
= 0-(-1)x0 = 0 = (-24/5)-(-1)x(24/5) 
= (-24/5)+(24/5) = 0 
= (48/5)-(-1)x(-13/5) = 
(48/5)-(13/5) = 7 
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
U =
E a matriz L?
JPNdO1
43
44
Slide 44
JPNdO1 Joao Paulo Nogueira de Oliveira; 03/05/20
04/05/20
23
Exemplo 1
• Tabela de Eliminação de Gauss
1a Linha (Matriz A) 5 2 1
m21 = 3/5
2a Linha
=3-(3/5)x5 = 0 =6-(3/5)x2 = 24/5 =-2-(3/5)x1 = -13/5
m31 = 2/5
3a Linha (versão 1)
=2-(2/5)x5 = 0 =-4-(2/5)x2 = -24/5 =10-(2/5)x1 = 48/5
m32 = (-24/5)/(24/5) = -1
3a Linha (versão 2)
= 0-(-1)x0 = 0 = (-24/5)-(-1)x(24/5) 
= (-24/5)+(24/5) = 0 
= (48/5)-(-1)x(-13/5) = 
(48/5)-(13/5) = 7 
Elemento a ser zerado/ pivô (Linha atual – coef.de eliminação x pivô)
L=
Exemplo 1
y1=8
(3/5).y1+ y2 = 7 -> (3/5).8 + y2 = 7
-> y2 = 7 – (24/5) -> y2 = 11/5
(2/5).y1- y2 + y3 = 8 -> (2/5).8- (11/5) + y3 = 8
-> (16/5) - (11/5) + y3 = 8 -> y3 = 8 -1 -> y3 = 7
45
46
04/05/20
24
Exemplo 1
7x3 = 7
(24/5).x2- (13/5).x3 = 11/5
-> (24/5).x2- (13/5).1 = 11/5
-> (24/5).x2 = 24/5 -> x2 = 1
5x1+ 2x2 + x3 = 8 -> 5x1+ 2.1 + 1 = 8
-> 5x1+ 3 = 8 -> 5x1 = 5 -> x1 = 1
-> x3=1
Logo, o conjunto solução é S={1, 1, 1}
Exercícios
• Resolva os seguintes Sistemas de Equações Lineares por Fatoração
LU, utilizando o Método de Crout e o Método de Eliminação de 
Gauss:
A) B)
C) D) 
47
48
04/05/20
25
Dúvidas e Sugestões 
?
Referências
49
50
04/05/20
26
51