ECT1303-2015.1-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 Pivotação 
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. 
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: 
 
 
 
 
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 é triangular inferiorse 
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): 
Quadro 
Resolução Retroativa 
 Ex: Resolva o seguinte sistema utilizando resolução 
retroativa 
 
 
 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 
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? 
Exercício 








23
03
0
21
321
321
xx
xxx
xxx
• Resolva o sistema: 
Introdução 
Até aqui, utilizamos a aritmética exata para a 
resolução de sistemas lineares. 
Está na hora de verificar se a aritmética flutuante 
utilizada pelos computadores tem influência sobre 
os resultados. 
De fato, veremos que certas matrizes são muito 
sensíveis aos efeitos da aritmética flutuante. 
Exemplo 1 
Considere o sistema: 
 cuja solução exata é x = [4 3]T 
Se trocamos o termo 1,1 da matriz por 1,05, a nova 
solução exata é x = [8 1]T. 
Uma pequena modificação no termo de uma matriz 
pode levar a uma grande modificação da solução 
exata. 
Na prática, a aritmética flutuante provoca pequenas 
modificações nos termos de uma matriz, o que se 
reflete nos métodos exatos de resolução. 


















4,10
10
21,1
21
2
1
x
x
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 
• Ex: Resolva o seguinte sistema, retendo durante os 
calculos 2 casas decimais, e em seguida calcule o resíduo 
da solução obtida: 
Solução 
𝐴𝑏 = 
3 2 1
1 11 5
 
𝑚 =
1
3
= 0,33, 𝐿2 −𝑚𝐿1 = 
 −0,99 − 0,66 − 0,33 
 + 1 11 5 
 0 10,34 4,67 
– Por resolução retroativa 
𝑥2 =
4,67
10,34
= 0,45 𝑥1 =
1 − 0,9
3
= 0,03 
– Resíduo 
𝑟 =
1
5
−
3 2 
1 11
0,03
0,45
= 
1
5
- 
0,99
4,98
=
0,01
0,02
 
 
 
Mal Condicionamento 
• Sistemas nos quais pequenas modificação levam 
a uma grande modificação da solução exata 
são chamados de mal condicionados 
• Nestes casos um resíduo pequeno não é 
garantia de uma boa solução (próxima da 
solução real do sistema) 
Mal Condicionamento 
• Uma maneira de verificar o mal condicionamento de um 
sistema é através do determinante normalizado de sua 
matriz dos coeficientes A, det(Norm A) 
 
 
 
 
• -1 < det(Norm A) < 1 
• Se | det(Norm A)| for muito menor que 1, a matriz será 
mal condicionada• Ex: O sistema 
 
 
𝑥1 + 1,001𝑥2 = 2,001
0,999𝑥1 + 𝑥2 = 1,999
 
 
possui a solução 𝑥 = 1 1 𝑇. Calcule o resíduo para a 
solução 𝑥 = 2 0 𝑇 e verifique que o resíduo é 
pequeno, o que significa que o sistema é mal 
condicionado. Confirme o mal condicionamento do 
sistema através do determinante normalizado da matriz 
dos coeficientes do sistema. 
 
Mal Condicionamento 
• Solução 
– Resíduo 
2,001
1,999
−
1 1,001
0,999 1
2
0
=
0,001
0,001
 
 
– Determinante normalizado 
𝛼1 = 12 + 1,0012 = 1,415 𝛼2 = 0,9992 + 12 = 1,414 
 
𝑑𝑒 𝑡 𝑁𝑜𝑟𝑚 𝐴 =
𝑑𝑒 𝑡 𝐴
𝛼1𝛼2
 = 
0,000001
1,415 ∙ 1,414
= 5 ∙ 10−7 
 
Mal Condicionamento 
Graficamente? 
• Exercício: Verifique se os seguintes sistemas são ou 
não mal condicionados. Em seguida calcule o resíduo 
da solução indicada: 
• 
𝑥1 + 𝑥2 = 2,01
2𝑥1 − 𝑥2 = −1,8
 
Solução real: 𝑥 = 0,1; 2 𝑇. Calcule o resíduo de x =
[0,4; 1,85] 
 
• 
𝑥1 + 2𝑥2 = 3
1,0001𝑥1 + 2𝑥2 = 3,0001
 
Solução real: 𝑥 = 1; 1 𝑇. Calcule o resíduo de 𝑥 =
0,7; 1,15 𝑇 
Mal Condicionamento 
Exemplo 2 – parte I 
Considere o sistema: 
 
 
 cuja solução exata é x = [10 1]T 
Suponha que iremos realizar a eliminação de Gauss 
utilizando aritmética de 4 dígitos de precisão. 
Note que o primeiro pivô é pequeno a11=0,003, e seu 
multiplicador associado, m21=5,291/0,003 = 
1763,666..., é arredondado para 1764. 





78,46130,6291,5
17,5914,59003,0
21
21
xx
xx
Exemplo 2 – parte II 
A eliminação de Gauss fornece: 
 
 
Os módulos de m21a13 e a23 introduziu erros de 
arredondamento. 
A substituição regressiva resulta em: 
 





104400104300
17,5914,59003,0
2
21
x
xx
1010
1001,1
1
2


x
x
Como podemos limitar estes erros? 
Métodos Exatos 
Pivotação 
Pivotação Parcial 
Uma primeira possibilidade consiste em aumentar a 
precisão da mantissa p, porém isso nem sempre é 
possível. 
Analisando os cálculos precedentes, pode-se 
suspeitar que a origem dos problemas é a divisão 
por um pivô quase nulo. 
Sabemos que tal operação é perigosa 
numericamente. 
Uma estratégia consiste então em permutar as linhas 
mesmo se o pivô não é exatamente nulo. 
Pivotação Parcial 
 
A pivotação parcial consiste na troca de linhas de 
um sistema: selecionar um elemento na mesma 
coluna que esteja abaixo da diagonal principal e 
que tenha o maior módulo para ser o pivô. 
Exemplo 2 – parte IV 
Retomando a eliminação de Gauss do exemplo 
(ainda com p=4) com pivotamento parcial, teremos 
agora: 
 
 
O multiplicador será, m21 = 0,000567, e o resultado 
após a substituição: 
 x = [10 1]T 
... igual a solução exata 





17,5914,59003,0
78,46130,6291,5
21
21
xx
xx
Método da Pivotação Parcial 
• Ex: Resolver o sistema com precisão de 3 casas decimais 
 
𝑥1 + 𝑥2 + 2𝑥3 = 8 
−𝑥1 − 2𝑥2 + 3𝑥3 = 1
3𝑥1 − 7𝑥2 + 4𝑥3 = 10
 
Método da Pivotação Parcial 
• Solução 
– Matriz aumentada 
𝐴𝑏 =
1,00 1,00 2,00 8,00
−1,00 −2,00 3,00 1,00
3,00 −7,00 4,00 10,00
 
– Trocando as linhas L1 e L3 
𝐴𝑏 =
3,00 −7,00 4,00 10,00
−1,00 −2,00 3,00 1,00
1,00 1,00 2,00 8,00
 
– Eliminando coeficientes abaixo 
𝐴𝑏 =
3,00 −7,00 4,00 10,00
0 −4,31 4,32 4,30
0 3,31 0,68 4,70
 
– O elemento de maior modulo é -4,31, de forma que este será o pivô e 
não é necessário trocar linhas 
Método da Pivotação Parcial 
– Eliminando coeficientes abaixo 
𝐴𝑏 =
3,00 −7,00 4,00 10,00
0 −4,31 4,32 4,30
0 0 4,01 8,01
 
 
– Utilizando resolução retroativa 
𝑥 =
3,02
1,01
2
 
 
– Resíduo 
𝑟 =
8
1
10
−
1 1 2
−1 −2 +3
3 −7 4
3,02
1,01
2
=
−0.03
0.04
0.01
 
 
Exemplo 3 – parte I 
A estratégia de pivotação parcial geralmente 
melhora a precisão dos resultados, porém nem 
sempre esta operação é suficiente. 
Considere o sistema 
 
 que é o mesmo do exemplo anterior multiplicando 
a primeira equação por 104 . 
Por Gauss chegamos a x= [-10, 1,001]t . 
 





78,46130,6291,5
59170059140030
21
21
xx
xx
Exemplo 3 – parte II 
Mais uma vez, o erro é considerável com relação à 
solução exata. 
Isto ocorre porque a matriz A é constituída de termos 
de ordem de grandeza completamente diferentes. 
Dimensionamento 
Uma solução parcial para o problema do exemplo 
anterior é efetuar o dimensionamento (mudança de 
escala) dos coeficientes da matriz. 
 
 
 
Atenção! O termo da direita b não é levado em 
consideração para se determinar o maior termo de 
cada linha. 
O dimensionamento consiste em dividir cada 
linha da matriz A pelo seu maior termo 
(em valor absoluto). 
Exemplo 3 – parte III 
O sistema 
 se torna então 
 
 
 Agora, a troca de linhas é necessária, pois o pivô 0,5x 
10-4 é muito pequeno. 
Podemos mostrar que a resolução em aritmética 
flutuante com p=4 fornece a solução 
 x = [10 1]T, 
 que é o resultado exato. 





78,46130,6291,5
59170059140030
21
21
xx
xx





6313,78631,0
0005,100005,0
21
21
xx
xx
Pivotação Completa 
• A pivotação completa, no k-ésimo passo, busca todos os 
elementos aij para i=k, k+1, ..., n, e j= k, k+1, ..., n, para achar o 
elemento com o maior módulo. Ambas as trocas de linhas e 
colunas são executadas para trazer esse elemento à posição 
pivô. 
 
 
 
 
• O número de operações acrescentadas é maior se comparado 
a pivotação parcial com dimensionamento. Porém, a precisão 
é maior e não realiza a operação de divisão na etapa de 
pivotação. 
Na Pivotação completa ocorre tanto permutação 
de linhas quanto colunas, de forma que o maior 
elemento possível seja o pivô. 
Pivotação Completa 
• Ex: Ex: Resolver o sistema com precisão de 2 casas 
decimais 
 
• Trocando as linhas L1 e L3 
𝐴𝑏 =
3,00 −7,00 4,00 10,00
1,42 0 2,56 9,4
−1,87 0 1,84 −1,9
 
 
• Eliminando coeficientes abaixo do pivô 
𝐴𝑏 =
3,00 −7,00 4,00 10,00
1,42 0 2,56 9,4
−2,89 0 0 −8,67
 
 
• Por resolução retroativa 
 
𝑥1 =
−8,67
−2,89
= 3,00 𝑥3 =
9,4 − 1,42 ∗ 3 
2,56
= 2,00 
𝑥2 =
10 − 3 ∗ 3 − 4 ∗ 2
−7
= 1,00 
• O resíduo será 0 0 0 𝑇 
 
 
 
Exercício 
• Para o sistema 
 
• Cuja solução real é [0,007 1,94], encontre utilizando 
Gauss e uma precisão de três dígitos: 
– A solução sem pivotação; 
– A solução com pivotação parcial; 
– A solução com pivotação parcial e dimensionamento; 
– A solução com pivotação total. 
 
𝑥1 + 𝑥2 = 2,01
2𝑥1 − 𝑥2 = −1,8