ECT1303-2013.2-Aula9 10-Solucao_Sistemas_LinearesI

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;iterativos para resolução de sistemas lineares;
Exemplos de aplicações dos sistemas lineares na 
engenharia.
Motivação
a11 x1 + a12 x2 + ... + a1nxn = b1
a21 x1 + a22 x2 + ... + a2nxn = b2
...
Em diversas situações práticas, necessitamos resolver 
sistemas de equações lineares, da forma:
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.
...
an1 x1 + an2 x2 + ... + annxn = bn
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 
A Lei de Kirchhoff estabelece que a soma 
algébrica das diferenças de potencial em 
qualquer circuito fechado é zero.
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.
2i1 + 4(i1 − i2 )+ 2(i1 − i3)−10 = 0
2i2 + 2i2 + 2(i2 − i3)+ 4(i2 − i1) = 0
6i3 + 2(i3 − i1)+ 2(i3 − i2 )− 4 = 0






Motivação
Em forma matricial:
8i1 − 4i2 − 2i3 =10
−4i1 +10i2 − 2i3 = 0
−2i1 − 2i2 +10i3 = 4
 
 
 
 
 
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
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 nSistema 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çãoDeterminado: 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 ?
x + y = 6
2x + 2y = 12
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.
Sistemas impossíveis
Qual a característica de um sistema impossível?
x + y = 6
x + y = 4
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.
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
11
6
145
146
213
2
1
x
x
x
bAx
Notação: M(li ← λli)
Solução: [1 1 1]T










=




















∴=










=←=

10
33
6
145
31218
213
100
030
001
)3(
10145
3
2
1
22
3
x
x
x
WbWAx
MW
x
ll
Solução: [1 1 1]T
Permutação de linhas
Exemplo: Notação: P(li ↔ lj)
Solução: [1 1 1]T










=




















∴=
10
11
6
145
146
213
2
1
x
x
x
bAx
Solução: [1 1 1]T










=




















∴=










=↔=

11
10
6
146
145
213
010
100
001
)(
10145
3
2
1
32
3
x
x
x
WbWAx
PW
x
ll
Operação T(lllli←←←← lllli +λλλλllllj)
Exemplo: Notação: T(li ← li +λlj)
Solução: [1 1 1]T










=




















∴=
10
11
6
145
146
213
2
1
x
x
x
bAx
Solução: [1 1 1]T










−=




















−∴=










−=−←=

10
1
6
146
320
213
100
012
001
)2(
10145
3
2
1
122
3
x
x
x
WbWAx
TW
x
lll
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
× 2 
2x + 2y = 6
-
x + 3y = 1x + y = 3
x - y = 5
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 = 3x + y = 3
x - y = 5
A
-
x + y = 3
-2y = 2
D
sabemos resolver facilmente!
Sistemas Triangulares
Um sistema linear de ordem n é triangular inferior se 
tiver a seguinte forma:
SistemasTriangulares
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):
Resolução Retroativa
� Ex: Resolva o seguinte sistema utilizando resolução 
retroativa
Quadro
� Solução:
Resolução Retroativa
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 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.por exemplo, em um sistema triangular.
No geral, é o que acontece nos métodos exatos.
Métodos Exatos
Eliminação de GaussEliminaçã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(li← li +λlj)
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 a é denominado pivô.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 a (2) ≠ 0 (pivô). O que isso 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: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 a :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 a /a
32
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
lll
lll
lll
−←
−←
−←
T
T
T
)( ↔P )( 324 ll ↔P
))1/2(( 3445 lll −←T
2x4 = - 4 x4 = -2
x3 - 2 = 0 x3 = 2
E quando aparece um pivô nulo?
x3 - 2 = 0 x3 = 2
2x2 + 2 - 4 = -4 x2 = -1
x1 – 1 + 4 – 2 = 2 x1 = 1
Exercício





−=+
=++
=++
23
03
0
321
321
xx
xxx
xxx
• Resolva o sistema:

 −=+ 23 21 xx
Resíduo
• Durante a solução, geralmente cometemos erros de 
arredondamento, o que causa um erro na solução obtida
• Como saber o quanto a resposta calculada foi afetada 
pelos erros de arredondamento?
– Basta verificar se a solução dada satisfaz o sistema
– Para tal, podemos calcular o resíduo, o qual irá indicar a 
qualidade da resposta obtida
• Se a solução encontrada para o sistema foi x, o resíduo r é 
dado por:
• Atenção: a matriz A e o vetor b devem ser o vetor e a 
matriz original fornecidos no problema
Axbr −=
Resíduo
Quadro
Solução
Métodos Exatos
Decomposição LUDecomposiçã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
11 22 nn
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;– 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:
bLUx =
• 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 utilizaro método de • 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• 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.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 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.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.