Sistemas Lineares - Aula 09

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 I: Introdução, Eliminação de 
Gauss e Decomposição LU 
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. 
Objetivos 
 
Definição dos conceitos de equação linear e sistema 
linear; 
Apresentação de métodos numéricos exatos e 
iterativos para resolução de sistemas lineares; 
Exemplos de aplicações dos sistemas lineares na 
engenharia. 
Motivação 
Aplicações: 
Determinação do potencial elétrico em redes elétricas; 
Cálculos de estruturas em construção civil; 
Cálculo da razão de escoamento num sistema hidráulico com 
derivações; 
Previsão da concentração de reagentes sujeitos à reações químicas 
simultâneas. 
a11 x1 + a12 x2 + ... + a1nxn = b1 
a21 x1 + a22 x2 + ... + a2nxn = b2 
... 
an1 x1 + an2 x2 + ... + annxn = bn 
 
Em diversas situações práticas, necessitamos resolver 
sistemas de equações lineares, da forma: 
Exemplo 
Considere o circuito a seguir com resistências e baterias 
tal como indicado. 
Escolhemos arbitrariamente os sentidos das correntes 
em cada malha: 
Motivação 
Aplicando no exemplo anterior, obtemos para as correntes 
i1, i2, i3, o seguinte sistema linear: 
 
 
 
Deseja-se determinar o valor de i = (i1, i2, i3)
T que 
satisfaça o sistema acima. 
A Lei de Kirchhoff estabelece que a soma 
algébrica das diferenças de potencial em 
qualquer circuito fechado é zero. 








04)(2)(26
0)(4)(222
010)(2)(42
23133
123222
31211
iiiii
iiiiii
iiiii
Motivação 
Em forma matricial: 
 
 
 
 
Neste caso, existe solução, mas nem sempre é o caso. 
 


































4
0
10
 
1022
2104
248
3
2
1
i
i
i

8i1  4i2  2i3 10
4i1 10i2  2i3  0
2i1  2i2 10i3  4





Linearidade 
• O conceito de linearidade é baseado nos dois princípios 
abaixo: 
 
– Homogeneidade: a*f(x1) = f(a*x1) 
 
 
– Superposição: f(x1) + f(x2) = f(x1 + x2) 
 
 
• Desta forma, se uma função ou sistema f(x) satisfaz os 
dois princípios acima, ele é dito linear. 
Linearidade 
Uma equação é linear se cada termo contém não mais 
do que uma variável e cada variável aparece na primeira 
potência. 
Sistemas lineares 
Um conjunto de n equações lineares com n variáveis 
(incógnitas) é denominado de: 
Sistemas de n equações lineares; ou 
Sistema linear de ordem n 
Uma solução para um sistema linear consiste em 
determinar valores para as n variáveis que satisfaçam 
todas as equações simultaneamente. 
Sistemas lineares 
De modo geral, um sistema de n equações lineares 
pode ser escrito como: 
Sistemas lineares 
Ou na forma matricial: 
 
 
 
 
Ou simplesmente: 
Matriz dos 
coeficientes 
Vetor de termos 
independentes 
Vetor 
solução 
Classificação de um Sistema Linear 
Sistema possível ou consistente: pelo menos uma 
solução 
Determinado: apenas uma solução 
Indeterminado: mais de uma solução 
Sistema impossível ou inconsistente: nenhuma solução 
 
 
Exemplos 
possível e determinado possível e indeterminado 
impossível 
Sistemas possíveis e indeterminados 
Qual a característica de um sistema indeterminado ? 
 
 
 
 
A linha 2 é igual à linha 1 multiplicada por um escalar. 
Caso geral: 
Uma linha é combinação linear de outras linhas. 
A matriz A é singular: det(A)=0. 
 
x + y = 6 
2x + 2y = 12 
 
Sistemas impossíveis 
Qual a característica de um sistema impossível? 
 
 
 
A linha 2 (coeficientes) é igual à linha 1 multiplicada por 
um escalar, enquanto o coeficiente b2 é igual a b1 
multiplicado por um outro escalar. 
Caso geral: 
Uma linha (coeficientes) é combinação linear de outras 
linhas, mas a combinação diverge para o vetor b. 
A matriz A é singular: det(A)=0. 
 
x + y = 6 
x + y = 4 
 
Sistemas possíveis e determinados 
Características: 
A matriz A é não-singular: inversível e det(A)  0. 
 
Na forma matricial: 
 A x = b 
 x = A-1 b 
 
O nosso objetivo nesta disciplina é desenvolver métodos 
numéricos para resolver sistemas lineares de ordem n 
que tenham solução única. 
Exercício 
Classificar os seguintes sistemas lineares: 
Operações elementares 
Ao multiplicarmos o sistema Ax=b por uma matriz W 
inversível, a solução x não é modificada. 
WAx = Wb  W-1WAx = W-1Wb  Ax = b 
 
As operações elementares vamos realizar sobre a matriz 
A que correspondem a três tipos diferentes de matrizes 
W inversíveis. 
 
 
 
Multiplicação de uma linha por um escalar 
Exemplo: 
 
 











































































10
33
6
145
31218
213
100
030
001
)3(
10
11
6
145
146
213
3
2
1
22
3
2
1
x
x
x
WbWAx
MW
x
x
x
bAx

Notação: M(i  i) 
Solução: [1 1 1]T 
Solução: [1 1 1]T 
Permutação de linhas 
Exemplo: 
 
 
Notação: P(i  j) 
Solução: [1 1 1]T 
Solução: [1 1 1]T 










































































11
10
6
146
145
213
010
100
001
)(
10
11
6
145
146
213
3
2
1
32
3
2
1
x
x
x
WbWAx
PW
x
x
x
bAx

Operação T(i i +j) 
Exemplo: 
 
 
Notação: T(i  i +j) 
Solução: [1 1 1]T 
Solução: [1 1 1]T 










































































10
1
6
146
320
213
100
012
001
)2(
10
11
6
145
146
213
3
2
1
122
3
2
1
x
x
x
WbWAx
TW
x
x
x
bAx

Matriz aumentada 
A matriz aumentada de um sistema linear é a matriz de 
dimensão n por n+1 que obtemos adicionando-se o 
membro da direita b à matriz A, ou seja: 
Sistemas equivalentes 
Podemos multiplicar uma linha de um sistema por um 
escalar e somar com outra linha. O sistema resultante 
continua válido. 
Exemplo: 
 x + y = 3 
x - y = 5 
× 2 
2x + 2y = 6 
x - y = 5 
- x + 3y = 1 
x - y = 5 
A B C 
A, B e C são equivalentes! x = 4, y = -1 
Definição: 
Dois sistemas lineares são equivalentes quando 
admitem a mesma solução. 
Sistemas equivalentes 
Qual a vantagem ? 
Obviamente, de A para B para C, não ganhamos nada. 
Mas se fizermos: 
 x + y = 3 
x - y = 5 
A 
- x + y = 3 
 -2y = 2 
D 
sabemos resolver facilmente! 
Sistemas Triangulares 
Um sistema linear de ordem n é triangularinferior se 
tiver a seguinte forma: 
Sistemas Triangulares 
A solução de um sistema triangular inferior é obtida por 
substituição direta (descida triangular): 
Sistemas Triangulares 
Um sistema linear de ordem n é triangular superior se 
tiver a seguinte forma: 
Sistemas Triangulares 
A solução de um sistema triangular superior é obtida por 
retro-substituição (subida triangular): 
Mas como obter um sistema triangular? 
zerar estes elementos 
Resolução Numérica de Sistemas Lineares 
Os métodos numéricos para a resolução de sistemas 
lineares são divididos em dois grupos: 
– Métodos Exatos: são aqueles que forneceriam a solução 
exata com um número finito de operações, não fossem os 
erros de arredondamento; 
– Métodos Iterativos: são aqueles que permitem obter a 
solução de um sistema com uma dada precisão através de 
um processo infinito convergente. 
Resolução Numérica de Sistemas Lineares 
Uma maneira de obter a solução de um sistema linear 
através de métodos numéricos é transformá-lo em 
outro equivalente cuja solução seja facilmente obtida, 
por exemplo, em um sistema triangular. 
No geral, é o que acontece nos métodos exatos. 
Métodos Exatos 
Eliminação de Gauss 
Método da Eliminação de Gauss 
O método de Gauss consiste em transformar o sistema 
dado num sistema triangular superior equivalente através 
da aplicação repetida da operação: 
T(i i +j) 
Descrição do algoritmo 
Começamos com a matriz aumentada: 
 
 
 
 
 
Primeiro passo: eliminar a incógnita x1 da 2ª, 3ª, ..., nª 
equações (zerar os elementos da primeira coluna abaixo 
da diagonal) 
Descrição do algoritmo 
2a linha = 2a linha - 1a linha multiplicada por a21
(1)/ a11 
(1) 
3a linha = 3a linha - 1a linha multiplicada por a31
(1)/ a11 
(1) 
na linha = na linha - 1a linha multiplicada por an1
(1)/ a11 
(1) 
Descrição do algoritmo 
Ficamos com a matriz: 
Observações (1/3) 
Para efetuar as operações de eliminação da primeira 
coluna, necessitamos que a11  0. 
O elemento a11 é denominado pivô. 
 
Descrição do algoritmo 
Segundo passo: eliminar a incógnita x2 da 3ª, 4ª, ..., nª 
equações (zerar os elementos da segunda coluna abaixo 
da diagonal). 
Descrição do algoritmo 
3a linha = 3a linha - 2a linha multiplicada por a32
(2)/ a22 
(2) 
na linha = na linha - 2a linha multiplicada por an2
(2)/ a22 
(2) 
Descrição do algoritmo 
Obtemos então a matriz: 
Observações (2/3) 
Para efetuar as operações de eliminação da primeira 
coluna, necessitamos que a11  0. 
Para efetuar as operações de eliminação da segunda 
coluna, necessitamos a22
(2)  0 (pivô). O que isso 
significa ? 
Quando da eliminação de a21, não pode aparecer zero 
em a22
(2). 
E assim sucessivamente, sendo o pivô sempre não nulo. 
Descrição do algoritmo 
(n – 1)º passo: eliminar a incógnita xn-1 da nª equação 
(zerar os elementos da (n-1)ª coluna abaixo da diagonal) 
 Para tal substituímos a nª equação pela diferença entre a 
nª equação e a (n-1)ª multiplicada por: 
 
Descrição do algoritmo 
Finalmente, obtemos a matriz: 
Descrição do algoritmo 
De forma geral, o kº passo do algoritmo da eliminação de 
Gauss é obtido por: 
Observações (3/3) 
No 2º passo, repetimos o processo, como se não 
existisse a 1ª linha e a 1ª coluna da 2ª matriz, isto é, 
todas as operações são realizadas em função da 2ª 
linha da matriz obtida no 1º passo. 
De um modo geral, no kº passo, repetimos o processo 
como se não existissem as (k-1) primeiras linhas e 
colunas da kª matriz, ou seja, todas as operações são 
realizadas em função da linha k da matriz obtida no 
passo (k-1). 
Exemplo 
Resolver o sistema abaixo usando eliminação de Gauss 
 
 
 
 
Matriz aumentada: 
 
Exemplo 
Eliminando a21: 
2a linha = 2a linha - 1a linha x a21/a11 
 = 2a linha - 1a linha x 1/3 
 = 2a linha - (2 2/3 -1/3 | 7/3) 
 
Eliminando a31: 
3a linha = 3a linha - 1a linha x a31/a11 
 = 3a linha - 1a linha x 1/2 
 = 3a linha - (3 1 -1/2 | 7/2) 
Exemplo 
Eliminando a32: 
3a linha = 3a linha - 2a linha x a32/a22 
 = 3a linha - 2a linha x 1/(10/3) 
 = 3a linha - 2a linha x 3/10 
 = 3a linha - (0 1 2/5 | 7/5) 
 
Exemplo 
81/10 x3 = 81/10 x3 = 1 
10/3 x2 + 4/3 = 14/3 x2 = 1 
6 x1 + 2 - 1 = 7 x1 = 1 
E quando aparece um pivô nulo? 
Exemplo: 
E quando aparece um pivô nulo? 
))1/1((
))1/1((
))1/2((
1443
1332
1221






T
T
T
)( 324  P
))1/2(( 3445  T
2x4 = - 4 x4 = -2 
x3 - 2 = 0 x3 = 2 
2x2 + 2 - 4 = -4 x2 = -1 
x1 – 1 + 4 – 2 = 2 x1 = 1 
E quando aparece um pivô nulo? 
Métodos Exatos 
Decomposição LU 
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. 
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: 
 
 
 
 
– Resolva-o usando a decomposição LU; 
– Calcule o determinante de A, usando a decomposição. 
Estudo Extra-Classe 
Livro Neide Franco: 
• Leitura: Seções 4.1 a 4.5 
• Exercícios: 4.1, 4.2, 4.5 e4.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.