Resolução de Sistemas Lineares com Eliminação Gaussiana

Prévia do material em texto

GEX114 - Ca´lculo Nume´rico
Profa.Dra. Amanda Castro Oliveira
Departamento de Cieˆncias Exatas - DEX/UFLA
amanda@dex.ufla.br
Cap.3 Resoluc¸o˜es de Sistemas Lineares
Seja o Sistema Linear Ax = b , onde A = (aij) i , j = 1, 2, ..., n
A = matriz nxn, matriz dos coeficientes,
x = (xj)
t , j = 1, ..., n
vetor da inco´gnitas,
b = (bi )
t , i = 1, ..., n
vetor dos coeficientes independentes,
det(A) 6= 0
Garantia de soluc¸a˜o u´nica.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Este me´todo consiste em transformar convenientemente o sistema
linear original para obter um sistema linear equivalente com a matriz
dos coeficientes triangular superior.
Teorema 3.1
Seja Ax = b um sistema linear. Aplicando sobre as equac¸o˜es deste sistema
uma sequeˆncia de operac¸o˜es elementares escolhidas entre:
(i) trocar duas equac¸o˜es;
(ii) multiplicar uma equac¸a˜o por uma constante na˜o nula;
(iii) adicionar um mu´ltiplo de uma equac¸a˜o a uma outra equac¸a˜o;
obtemos um novo sistema A˜x = b˜ e os sistemas sa˜o
equivalentes.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Use a eliminac¸a˜o gaussiana e a aritme´tica de ponto flutuante com 3
d´ıgitos para encontrar a soluc¸a˜o do seguinte sistema linear:{
0.0002x1 + 2x2 =
2x1 + 2x2 =
5
6
Primeiramente vamos colocar o sistema na notac¸a˜o de ponto
flutuante. {
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.5 ∗ 101
0.6 ∗ 101
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Use a eliminac¸a˜o gaussiana e a aritme´tica de ponto flutuante com 3
d´ıgitos para encontrar a soluc¸a˜o do seguinte sistema linear:{
0.0002x1 + 2x2 =
2x1 + 2x2 =
5
6
Primeiramente vamos colocar o sistema na notac¸a˜o de ponto
flutuante.
{
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.5 ∗ 101
0.6 ∗ 101
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Use a eliminac¸a˜o gaussiana e a aritme´tica de ponto flutuante com 3
d´ıgitos para encontrar a soluc¸a˜o do seguinte sistema linear:{
0.0002x1 + 2x2 =
2x1 + 2x2 =
5
6
Primeiramente vamos colocar o sistema na notac¸a˜o de ponto
flutuante. {
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.5 ∗ 101
0.6 ∗ 101
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
1a etapa: pivoˆ a11 = 0.2 ∗ 10−3
m21 =
0.2∗101
0.2∗10−3 = 0.1 ∗ 105
L
(1)
1 ← L(0)1
L
(1)
2 ← L(0)2 −m21L(0)1
a
(1)
22 = a
(0)
22 − a(0)12 m21 = 0.2 ∗ 101 − (0.1 ∗ 105)(0.2 ∗ 101) =
0.2 ∗ 101 − 0.2 ∗ 105 = −0.2 ∗ 105
b
(1)
2 = b
(0)
2 − b(0)1 m21 = 0.6 ∗ 101 − (0.1 ∗ 105)(0.5 ∗ 101) =
0.6 ∗ 101 − 0.5 ∗ 105 = −0.5 ∗ 105 =
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
1a etapa: pivoˆ a11 = 0.2 ∗ 10−3
m21 =
0.2∗101
0.2∗10−3 = 0.1 ∗ 105
L
(1)
1 ← L(0)1
L
(1)
2 ← L(0)2 −m21L(0)1
a
(1)
22 = a
(0)
22 − a(0)12 m21 = 0.2 ∗ 101 − (0.1 ∗ 105)(0.2 ∗ 101) =
0.2 ∗ 101 − 0.2 ∗ 105 = −0.2 ∗ 105
b
(1)
2 = b
(0)
2 − b(0)1 m21 = 0.6 ∗ 101 − (0.1 ∗ 105)(0.5 ∗ 101) =
0.6 ∗ 101 − 0.5 ∗ 105 = −0.5 ∗ 105 =
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
1a etapa: pivoˆ a11 = 0.2 ∗ 10−3
m21 =
0.2∗101
0.2∗10−3 = 0.1 ∗ 105
L
(1)
1 ← L(0)1
L
(1)
2 ← L(0)2 −m21L(0)1
a
(1)
22 = a
(0)
22 − a(0)12 m21 = 0.2 ∗ 101 − (0.1 ∗ 105)(0.2 ∗ 101) =
0.2 ∗ 101 − 0.2 ∗ 105 = −0.2 ∗ 105
b
(1)
2 = b
(0)
2 − b(0)1 m21 = 0.6 ∗ 101 − (0.1 ∗ 105)(0.5 ∗ 101) =
0.6 ∗ 101 − 0.5 ∗ 105 = −0.5 ∗ 105 =
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim a matriz triangular superior torna-se:
A(1) =
[
0.2 ∗ 10−3 0.2 ∗ 101 0.5 ∗ 101
0 − 0.2 ∗ 105 − 0.5 ∗ 105
]
Que podemos prontamente resolver:
−0.2 ∗ 105x2 = 0.5 ∗ 105 ⇒ x2 = 0.25 ∗ 101
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 = 0.5 ∗ 101 =
0.2 ∗ 10−3x1 + (0.2 ∗ 101)(0.25 ∗ 101) = 0.5 ∗ 101
⇒ 0.2 ∗ 10−3x1 = 0.5 ∗ 101 − 0.5 ∗ 101
x1 = 0
O vetor soluc¸a˜o e´ dado por: x =
[
0
0.25 ∗ 101
]
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim a matriz triangular superior torna-se:
A(1) =
[
0.2 ∗ 10−3 0.2 ∗ 101 0.5 ∗ 101
0 − 0.2 ∗ 105 − 0.5 ∗ 105
]
Que podemos prontamente resolver:
−0.2 ∗ 105x2 = 0.5 ∗ 105 ⇒ x2 = 0.25 ∗ 101
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 = 0.5 ∗ 101 =
0.2 ∗ 10−3x1 + (0.2 ∗ 101)(0.25 ∗ 101) = 0.5 ∗ 101
⇒ 0.2 ∗ 10−3x1 = 0.5 ∗ 101 − 0.5 ∗ 101
x1 = 0
O vetor soluc¸a˜o e´ dado por: x =
[
0
0.25 ∗ 101
]
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Assim a matriz triangular superior torna-se:
A(1) =
[
0.2 ∗ 10−3 0.2 ∗ 101 0.5 ∗ 101
0 − 0.2 ∗ 105 − 0.5 ∗ 105
]
Que podemos prontamente resolver:
−0.2 ∗ 105x2 = 0.5 ∗ 105 ⇒ x2 = 0.25 ∗ 101
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 = 0.5 ∗ 101 =
0.2 ∗ 10−3x1 + (0.2 ∗ 101)(0.25 ∗ 101) = 0.5 ∗ 101
⇒ 0.2 ∗ 10−3x1 = 0.5 ∗ 101 − 0.5 ∗ 101
x1 = 0
O vetor soluc¸a˜o e´ dado por: x =
[
0
0.25 ∗ 101
]
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Podemos verificar a soluc¸a˜o substituindo o vetor soluc¸a˜o no sistema
original:{
(0.2 ∗ 10−3)(0) + (0.2 ∗ 101)(0.25 ∗ 101) =
(0.2 ∗ 101)(0) + (0.2 ∗ 101)(0.25 ∗ 101) =
0.5 ∗ 101
0.5 ∗ 101!!
O que fizemos de errado??
3.3.1 Me´todos de Eliminac¸a˜o de Gauss
Podemos verificar a soluc¸a˜o substituindo o vetor soluc¸a˜o no sistema
original:{
(0.2 ∗ 10−3)(0) + (0.2 ∗ 101)(0.25 ∗ 101) =
(0.2 ∗ 101)(0) + (0.2 ∗ 101)(0.25 ∗ 101) =
0.5 ∗ 101
0.5 ∗ 101!!
O que fizemos de errado??
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Estrate´gias de
Pivoteamento
No algoritmo de eliminac¸a˜o de gauss precisamos calcular os
multiplicadores
mik =
a
(k−1)
ik
a
(k−1)
kk
, i = k + 1, · · · , n
em cada etapa do processo.
O que acontece se o pivoˆ for nulo?
E se ele estiver pro´ximo de zero?
E´ imposs´ıvel trabalhar com um pivoˆ nulo!
Se isto acontecer e´ preciso trocar linhas para evitar tal inconveniente.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Estrate´gias de
Pivoteamento
No algoritmo de eliminac¸a˜o de gauss precisamos calcular os
multiplicadores
mik =
a
(k−1)
ik
a
(k−1)
kk
, i = k + 1, · · · , n
em cada etapa do processo.
O que acontece se o pivoˆ for nulo?
E se ele estiver pro´ximo de zero?
E´ imposs´ıvel trabalhar com um pivoˆ nulo!
Se isto acontecer e´ preciso trocar linhas para evitar tal inconveniente.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Estrate´gias de
Pivoteamento
Se o pivoˆ ≈ 0 pode levar a resultados totalmente inesperados como
no exemplo anterior.
Em qualquer ma´quina os ca´lculos sa˜o efetuados com aritme´tica de
precisa˜o finita e pivoˆs ≈ 0 da˜o origem a multiplicadores bem maiores
que a unidade que, por sua vez, geram uma ampliac¸a˜o dos erros de
arredondamento.
Sendo assim e´ necessa´rio adotar uma estrate´gia que contorne esses
inconvenientes.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Essa estrate´gia consiste em:
(i) no in´ıcio da etapa k da fase de eliminac¸a˜o, escolher para
pivoˆ o elemento de maior mo´dulo entre os coeficientes
a
(k−1)
ik i = k , k + 1, · · · , n dispon´ıveis;
(ii) trocar as linhas k e i se for necessa´rio.
Ex.n = 4 e k = 2
A(1) =

3 2 1 −1 5
0 1 0 3 6
0 −3 −5 7 7
0 2 4 0 15

3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Essa estrate´gia consiste em:
(i) no in´ıcio da etapa k da fase de eliminac¸a˜o, escolher para
pivoˆ o elemento de maior mo´dulo entre os coeficientes
a
(k−1)
ik i = k , k + 1, · · · , n dispon´ıveis;
(ii) trocar as linhas k e i se for necessa´rio.
Ex.n = 4 e k = 2
A(1) =

3 2 1 −1 5
0 1 0 3 6
0 −3 −5 7 7
0 2 4 0 15

3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
2a etapa: pivoˆ sem pivoteamento seria a
(1)
22 = 1, mas se usamos
estrate´gia de pivoteamento parcial precisamos escolher para pivoˆ o
maior elemento da 2a coluna dispon´ıvel para o escalonamento.
max{|a(1)i2 |, i = 2, 3, 4} = |a(1)32 | = 3
Trocar as linhas 2 e 3A(1) =

3 2 1 −1 5
0 −3 −5 7 7
0 1 0 3 6
0 2 4 0 15

E os multiplicadores m32 =
1
−3 e m42 =
2
−3
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Com esta escolha do maior elemento em mo´dulo para ser o pivoˆ
fazemos com que os multiplicadores, em mo´dulo, estejam entre zero e
um, o que evita a ampliac¸a˜o dos erros de arredondamento.
Ha´ ainda outras te´cnicas de pivoteamento como por exemplo, o
pivoteamento completo que consiste em escolher para pivoˆ de cada
etapa o elemento de maior mo´dulo dispon´ıvel.
Esta u´ltima te´cnica na˜o e´ muito empregada uma vez que envolve uma
extensa comparac¸a˜o entre os elementos no in´ıcio de cada etapa o que
aumenta o custo computacional do processo.
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Vamos agora resolver novamente o sistema do primeiro exemplo
considerando a estrate´gia de pivoteamento parcial:{
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.5 ∗ 101
0.6 ∗ 101
1a etapa: escolher para pivoˆ o maior elemento da primeira coluna.
Neste caso trocar a 1a com a 2a linha.
A(0) =
{
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.6 ∗ 101
0.5 ∗ 101
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Vamos agora resolver novamente o sistema do primeiro exemplo
considerando a estrate´gia de pivoteamento parcial:{
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.5 ∗ 101
0.6 ∗ 101
1a etapa: escolher para pivoˆ o maior elemento da primeira coluna.
Neste caso trocar a 1a com a 2a linha.
A(0) =
{
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
0.2 ∗ 10−3x1 + 0.2 ∗ 101x2 =
0.6 ∗ 101
0.5 ∗ 101
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Assim o pivoˆ e´ 0.2∗101 e o multiplicador m21 = 0.2∗10−30.2∗101 = 0.1∗10−3.
Resolvendo o sistema de forma ana´loga ao que fizemos anteriormente
encontramos:
A(1) =
{
0.2 ∗ 101x1 + 0.2 ∗ 101x2 =
+ 0.2 ∗ 101x2 =
0.6 ∗ 101
0.5 ∗ 101
Cujo vetor soluc¸a˜o e´ dado por:x =
[
0.5
0.25 ∗ 101
]
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Podemos verificar a soluc¸a˜o substituindo o vetor soluc¸a˜o no sistema
original:{
(0.2 ∗ 101)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
(0.2 ∗ 10−3)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
0.6 ∗ 101
0.5 ∗ 101
Ufa!! Ate´ que enfim!!
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Podemos verificar a soluc¸a˜o substituindo o vetor soluc¸a˜o no sistema
original:{
(0.2 ∗ 101)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
(0.2 ∗ 10−3)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
0.6 ∗ 101
0.5 ∗ 101
Ufa!! Ate´ que enfim!!
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Podemos verificar a soluc¸a˜o substituindo o vetor soluc¸a˜o no sistema
original:{
(0.2 ∗ 101)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
(0.2 ∗ 10−3)(0.5) + (0.2 ∗ 101)(0.25 ∗ 101) =
0.6 ∗ 101
0.5 ∗ 101
Ufa!! Ate´ que enfim!!
3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Resolva o sistema linear utilizando aritme´tica de arredondamento de 3
d´ıgitos e estrate´gia de pivoteamento parcial:
2.11x1 −4.21x2 +0.921x3 =
4.01x1 +10.2x2 −1.12x3 =
1.09x1 +0.987x2 +0.832x3 =
2.01
−3.09
4.21
Cujo vetor soluc¸a˜o e´ dado por:x =
 −0.4310.430
5.12

3.3.1 Me´todos de Eliminac¸a˜o de Gauss - Pivoteamento
Parcial
Resolva o sistema linear utilizando aritme´tica de arredondamento de 3
d´ıgitos e estrate´gia de pivoteamento parcial:
2.11x1 −4.21x2 +0.921x3 =
4.01x1 +10.2x2 −1.12x3 =
1.09x1 +0.987x2 +0.832x3 =
2.01
−3.09
4.21
Cujo vetor soluc¸a˜o e´ dado por:x =
 −0.4310.430
5.12

Pro´xima aula
Fatorac¸a˜o LU
Por hoje e´ so´ pessoal!!
Este material e´ inteiramente baseado na bibliografia do curso,
principalmente no livro texto :RUGIERO, M. A.G; LOPES,V Ca´lculo
Nume´rico: Aspectos teo´ricos e computacionais, Editora McGraw-Hill.1997.
Sites consultados acessados em 24/03/2011: CASTILHO, J. E., Apostila
de Ca´lculo Nume´rico, http://www.castilho.prof.ufu.br, UFU, 2002
http://www.alunos.eel.usp.br/numerico/notas.html
Colli, E., Asano, H. C,Ca´lculo Nume´rico — Fundamentos e
Aplicac¸o˜es-Departamento de Matema´tica Aplicada – IME-USP, 2009
Este material na˜o substitui a bibliografia.