ECT1303-2015.1-Aula11-Solucao_Sistemas_LinearesII

Prévia do material em texto

UFRN 
Universidade Federal do Rio Grande do Norte 
Escola de Ciências e Tecnologia 
Solução de Sistemas de 
Equações Lineares 
Parte II: LU e Jordan 
ECT1303 – Computação Numérica 
• Manter o telefone celular sempre 
desligado/silencioso quando estiver em 
sala de aula; 
• Nunca atender o celular na sala de aula. 
Métodos Exatos 
Decomposição LU 
Alan Turing 
Definições Importantes 
Seja A um matriz n x n na forma: 
Definições Importantes 
Os menores principais de A de ordens 1, 2, ..., n 
são definidos pelas submatrizes de A: 
Decomposição LU 
Teorema LU 
 
Seja A uma matriz quadrada de ordem n, e 
Ak o menor principal constituído das k primeiras 
linhas e k primeiras colunas de A. 
Assumimos que det(Ak) ≠ 0, para k = 1, 2, ..., n – 1. 
 Então existe uma única matriz triangular 
inferior L = (lij), com l11 = l22 = ... = lnn = 1, e uma 
única matriz triangular superior U = (uij) tal que LU 
= A. Além disso, det(A) = u11u22...unn. 
Esquema Prático para Decomposição LU 
• Na prática, pode-se encontrar L e U simplesmente 
aplicando a definição de produto e de igualdade de 
matrizes, isto é, impondo que LU = A. 
Esquema Prático para Decomposição LU 
• Para obtermos os elementos das matrizes L e U devemos 
calcular os elementos das linhas de U e das colunas de L 
na seguinte ordem: 
– 1ª linha de U; 
– 1ª coluna de L; 
– 2ª linha de U; 
– 2ª coluna de L ... até o fim, ou seja: 
Aplicação a Solução de Sistemas Lineares 
• Seja o sistema Ax = b de ordem n determinado, em que A 
satisfaz as condições de decomposição LU. 
 Então o sistema Ax = b pode ser escrito como: 
• Fazendo Ux = y, a equação acima reduz-se a Ly = b. 
Resolvendo o sistema triangular inferior Ly = b, obtemos 
o vetor y. 
• Substituindo o vetor y no sistema Ux = y obtemos um 
sistema triangular superior cuja solução é o vetor x, que 
procuramos. 
bLUx
Aplicação a Solução de Sistemas Lineares 
• Vantagem da fatoração LU: economiza cálculos caso 
tenhamos que resolver vários sistemas onde A seja 
constante e apenas b mude 
– Ex: Cálculo da matriz inversa AA-1 = I (Como?) 
• Para achar a fatoração LU, podemos utilizar o método 
de Gauss: 
– A matriz triangular superior U será a mesma dada pelo método 
de Gauss (sem considerar o vetor b) 
– A matriz triangular inferior unitária será dada pelos coeficientes 
m, de forma que o elemento Lij da matriz L será dado por 
 jjijij aaL /
Exemplo 
• Seja 
 
 
 
– Verificar se A satisfaz as condições de decomposição LU; 
– Decompor A em LU; 
– Calcular o determinante de A através da decomposição LU; 
– Resolver o sistema Ax = b, em que b = (0, -7, -5), usando a 
decomposição LU. 
Exemplo 
• Solução 
– Para que A satisfaça as condições de decomposição LU devemos 
ter: det(A1) ≠ 0 e det(A2) ≠ 0. De fato det(A1) = 5 e det(A2) = -1. 
– Utilizando as fórmulas, obtemos: 
• Para a 1ª linha de U 
 
 
• Para a 1ª coluna de L 
 
 
• Para a 2ª linha de U 
Exemplo 
• Para a 2ª coluna de L 
 
 
 
 
• Finalmente, para a 3ª linha de U, obtemos 
 
 
 
• Então: 
Exemplo 
– Determinante 
 
 
– Para a resolução do sistema linear, basta resolver dois sistemas 
triangulares: Ly = b e Ux = y. 
• Ly = b 
Exemplo 
• Obtemos 
 
 
 
 
 
 
• Ux = y 
Exemplo 
• Obtemos 
 
 
 
 
 
 
 
• Logo, a solução do sistema Ax =b é x = (0, 1 e -2)t. 
Exercícios 
• Considere o sistema: 
 
1 −3 2
−2 8 −1
4 −6 5
𝑥1
𝑥2
𝑥3
=
11
−15
29
 
 
– Resolva-o usando a decomposição LU; 
– Calcule o determinante de A, usando a decomposição. 
1 −3 2 11
−2 8 −1 −15
4 −6 5 29
 
𝑚21 =
−2
1
= −2 𝐿2 = 𝐿2 −𝑚11𝐿1 = 0 2 3 7 
𝑚31 =
4
1
= 4 𝐿3 = 𝐿3 −𝑚11𝐿1 = 0 6 − 3 − 15 
𝑚32 =
6
2
= 3 𝐿3 = 𝐿3 −𝑚32𝐿2 = 0 0 − 12 − 36 
𝐴 = 𝐿𝑈 =
1 0 0
−2 1 0
4 3 1
1 −3 2
0 2 3
0 0 −12
 
 
 
Solução 
𝐿𝑦 = 𝑏 ⇒
1 0 0
−2 1 0
4 3 1
𝑦1
𝑦2
𝑦3
=
11
−15
29
 
 
𝑦1 = 11 𝑦2 = 7 𝑦3 = −36 
 
𝑈𝑥 = 𝑦 ⇒
1 −3 2
0 2 3
0 0 −12
𝑥1
𝑥2
𝑥3
=
11
7
−36
 
 
𝑥3 = 3 𝑥2 = −1 𝑥1 = 2 
 
Solução 
Exercício 
• Considerando o sistema massa-mola abaixo chegamos ao 
seguinte sistema linear (onde 𝑘𝑖 e 𝑥𝑖 representam 
constates elásticas e deslocamentos e 𝑤𝑖 massa): 
 
 
 
• Dados 
 
– Encontre as matrizes L e U do sistema 
– Resolva o sistema resultante para: 
 
 
 
 
 
Estudo Extra-Classe 
Livro Neide Franco: 
• Leitura: Seções 4.1 a 4.5 
• Exercícios: 4.1, 4.2, 4.5 e 4.9 a 4.11 
• Exercícios complementares: 4.30, 4.40 e 4.41 
• Problemas aplicados a Projetos do Capítulo 4: todos os 
exercícios que envolvam os métodos diretos vistos. 
 
Livro Chapra: 
• Leitura: Capítulo 9 e 10, seções 9.1, 9.2, 10.1 e 10.2 
• Exercícios: 9.1 a 9.14 e 10.2 a 10.6 que envolvam os 
métodos diretos vistos. 
Método de Jordan 
– Semelhante ao métodos de Gauss, consiste em 
transformar o sistema dado não apenas em um sistema 
triangular, mas sim em um sistema diagonal equivalente 
– Sistema diagonal 
 
𝑎11 0 ⋯ 0
0 𝑎22 ⋯ 0
⋮ ⋮ ⋱ ⋮
0 0 ⋯ 𝑎𝑛𝑛
 
 
– Elimina a necessidade de resolução retroativa 
• No método de Jordan, o pivô é utilizado para zerar 
todos os elementos de sua coluna (acima e abaixo de 
pivô) 
• Ex: Resolva o sistema abaixo utilizando o método de 
Jordan 
 
2𝑥1 + 3𝑥2 − 𝑥3 = 5
4𝑥1 + 4𝑥2 − 3𝑥3 = 3
2𝑥1 − 3𝑥2 + 𝑥3 = −1
 
 
Quadro 
Método de Jordan 
– Matriz aumentada Ab 
𝐴𝑏 =
2 3 −1 5
4 4 −3 3
2 −3 1 −1
 
 
– Zerando os dois elementos abaixo teremos 
𝐴𝑏 =
2 3 −1 5
0 −2 −1 −7
0 −6 2 −6
 
 
– Zerando os dois elementos abaixo e acima teremos 
𝐴𝑏 =
2 0 −2,5 −5,5
0 −2 −1 −7
0 0 5 15
 
 
Solução 
– Zerando os dois elementos abaixo e acima teremos 
𝐴𝑏 =
2 0 0 2
0 −2 0 −4
0 0 5 15
 
 
– A partir da matriz diagonal, podemos calcular a solução 
 
𝑥1 =
2
2
= 1 
 
𝑥2 =
−4
−2
= 2 
 
𝑥3 =
15
5
= 3 
Solução 
• Se somarmos a uma linha de A um múltiplo de outra linha, o 
determinante da nova matriz é igual ao de A 
• O método de Jordan pode ser utilizado para se calcular o 
determinante de uma matriz (e Gauss?) 
• Uma vez que a matriz 𝐴 seja convertida em uma matriz 
diagonal pelo método 
𝐴 =
𝑎11 0 ⋯ 0
0 𝑎22 ⋯ 0
⋮ ⋮ ⋱ ⋮
0 0 ⋯ 𝑎𝑛𝑛
 
o determinante desta será dado por 
det 𝐴 = 𝑎𝑛𝑛 
– Ex: Utilizando Jordan, calcule o determinante da matriz 
1 2
5 −1
 
 
Método de Jordan