Sistemas de Equações Lineares

Prévia do material em texto

Sistemas de Equac¸o˜es Lineares
Sistemas de Equac¸o˜es Lineares
Me´todo de Eliminac¸a˜o de Gauss
Eduardo Camponogara
Departamento de Automac¸a˜o e Sistemas
Universidade Federal de Santa Catarina
DAS-5103: Ca´lculo Nume´rico para Controle e Automac¸a˜o
1 / 34
Sistemas de Equac¸o˜es Lineares
Suma´rio
Fundamentos
Exemplo 1
Exemplo 2
Exemplo 3
2 / 34
Sistemas de Equac¸o˜es Lineares
Fundamentos
Suma´rio
Fundamentos
Exemplo 1
Exemplo 2
Exemplo 3
3 / 34
Sistemas de Equac¸o˜es Lineares
Fundamentos
Me´todo de Eliminac¸a˜o de Gauss
I Me´todo direto mais conhecido e mais usado para resoluc¸a˜o de
um sistema denso, de pequeno e me´dio porte
I Um sistema e´ considerado de pequeno porte se conte´m ate´ 30
varia´veis
I E´ considerado de me´dio porte se conte´m ate´ 50 varia´veis
I E´ dito ser de grande porte se conte´m mais de 50 varia´veis.
4 / 34
Sistemas de Equac¸o˜es Lineares
Fundamentos
Me´todo de Eliminac¸a˜o de Gauss
Me´todo
O me´todo consiste na aplicac¸a˜o sucessiva de propriedades ba´sicas
de a´lgebra linear.
1) Combinac¸o˜es lineares: adic¸a˜o de uma linha com um mu´ltiplo
de outra linha, para substituir uma das linhas consideradas.
2) Troca de linhas
3) Multiplicac¸a˜o de uma linha por uma constante
5 / 34
Sistemas de Equac¸o˜es Lineares
Fundamentos
Me´todo de Eliminac¸a˜o de Gauss
Observac¸a˜o
I Se a matriz B e´ obtida a partir de uma matriz A por meio de
combinac¸o˜es lineares de linhas, dizemos que A e B sa˜o
equivalentes.
I Se A e´ quadrada enta˜o det(A) = det(B).
6 / 34
Sistemas de Equac¸o˜es Lineares
Fundamentos
Me´todo de Eliminac¸a˜o de Gauss: Algoritmo Ba´sico
Algoritmo ba´sico de Gauss apresenta os seguintes passos:
1) Triangularizac¸a˜o: consiste em transformar a matriz A numa
matriz triangular superior, mediante perturbac¸o˜es e
combinac¸o˜es lineares de linhas.
2) Retrossubstituic¸a˜o: consiste no ca´lculo dos componentes do
vetor x , a partir da soluc¸a˜o imediata do u´ltimo componente
de x , e enta˜o substitu´ımos regressivamente nas equac¸o˜es
anteriores.
7 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Suma´rio
Fundamentos
Exemplo 1
Exemplo 2
Exemplo 3
8 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Problema
Tomemos como exemplo o sistema de equac¸o˜es lineares dado
abaixo 

3x1 + 2x2 + x4 = 3
9x1 + 8x2 − 3x3 + 4x4 = 6
−6x1 + 4x2 − 8x3 = −16
3x1 − 8x2 + 3x3 + 4x4 = 18
(1)
o qual pode ser escrito na forma matricial como segue
A =


3 2 0 1
9 8 −3 4
−6 4 −8 0
3 −8 3 4

 e y =


3
6
−16
18

 .
9 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Triangularizac¸a˜o
A primeira fase consiste da triangularizac¸a˜o de A, cujos passos sa˜o
ilustrados abaixo.
0) Obtendo a matriz aumentada


3 2 0 1 3
9 8 −3 4 6
−6 4 −8 0 −16
3 −8 3 4 18


10 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Triangularizac¸a˜o
1) Primeiro passo: zerando os elementos abaixo do elemento a11.


3 2 0 1 3
9 8 −3 4 6
−6 4 −8 0 −16
3 −8 3 4 18


E2 − 9/3E1 →
E3 + 6/3E1 →
E4 − 3/3E1 →


3 2 0 1 3
0 2 −3 1 −3
0 8 −8 2 −10
0 −10 3 3 15


11 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Triangularizac¸a˜o
2) Segundo passo: zerando os elementos abaixo de a22


3 2 0 1 3
0 2 −3 1 −3
0 8 −8 2 −10
0 −10 3 3 15


E3 − 8/2E2 →
E4 + 10/2E2 →


3 2 0 1 3
0 2 −3 1 −3
0 0 4 −2 2
0 0 −12 8 0


12 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Triangularizac¸a˜o
3) Terceiro passo: zerando os elementos abaixo de a33


3 2 0 1 3
0 2 −3 1 −3
0 0 4 −2 2
0 0 −12 8 0


E4 + 12/4E3 →


3 2 0 1 3
0 2 −3 1 −3
0 0 4 −2 2
0 0 0 2 6


13 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Soluc¸a˜o
Obtemos, portanto um sistema equivalente a (1) na forma
triangular:


3x1 + 2x2 + 0x3 + x4 = 3
+ 2x2 − 3x3 + x4 = −3
+ 4x3 − 2x4 = 2
2x4 = 6
14 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Soluc¸a˜o
Por meio de retrossubstituic¸a˜o, podemos encontrar uma soluc¸a˜o
para o sistema original (1). Considerando a u´ltima equac¸a˜o temos
que
2x4 = 6⇒ x4 = 3
Substituindo na terceira equac¸a˜o, obtemos:
+4x3 − 2(3) = 2⇒ x3 = 2
Substituindo na segunda equac¸a˜o, obtemos:
+2x2 − 3× 2 + 3 = −3⇒ x2 = 0
15 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 1
Soluc¸a˜o
Substituindo na primeira equac¸a˜o, obtemos:
3x1 + 2(0) + 0(2) + 3 = 3⇒ x1 = 0
Portanto, uma soluc¸a˜o para (1) e´:
x =


x1
x2
x3
x4

 =


0
0
2
3


16 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 1
Me´todo de Eliminac¸a˜o de Gauss
Teorema
O me´todo de Gauss produz, em precisa˜o infinita, uma soluc¸a˜o
exata do sistema Ax = b desde que:
1) A seja na˜o singular, det(A) 6= 0
2) As linhas sejam trocadas sempre que necessa´rio, caso aii = 0
17 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Suma´rio
Fundamentos
Exemplo 1
Exemplo 2
Exemplo 3
18 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Problema
Aqui vamos considerar o sistema de equac¸o˜es lineares abaixo:


−1x1 + 2x2 + 3x3 + x4 = 1
2x1 − 4x2 − 5x3 − 1x4 = 0
−3x1 + 8x2 + 8x3 + 1x4 = 2
1x1 + 2x2 − 6x3 + 4x4 = −1
(2)
19 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Triangularizac¸a˜o
Iniciamos a soluc¸a˜o pelo me´todo de Gauss com a triangularizac¸a˜o
do sistema (2).
0) Obtendo a matriz aumentada:


−1 2 3 1 1
2 −4 −5 −1 0
−3 8 8 1 2
1 2 −6 4 −1


20 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Triangularizac¸a˜o
1) Primeiro passo: zerando os elementos abaixo de a11


−1 2 3 1 1
2 −4 −5 −1 0
−3 8 8 1 2
1 2 −6 4 −1


E2 + 2E1 →
E3 − 3E1 →
E4 + E1 →


−1 2 3 1 1
0 0 1 1 2
0 2 −1 −2 −1
0 4 −3 5 0


21 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Triangularizac¸a˜o
2) Segundo passo: trocando as linhas 2 e 3


−1 2 3 1 1
0 0 1 1 2
0 2 −1 −2 −1
0 4 −3 5 0


E3 →
E2 →


−1 2 3 1 1
0 2 −1 −2 −1
0 0 1 1 2
0 4 −3 5 0


22 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Triangularizac¸a˜o
3) Terceiro passo: zerando os elementos abaixo de a22


−1 2 3 1 1
0 2 −1 −2 −1
0 0 1 1 2
0 4 −3 5 0


E4 − 2E2 →


−1 2 3 1 1
0 2 −1 −2 −1
0 0 1 1 2
0 0 −1 9 2


23 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Triangularizac¸a˜o
4) Quarto passo: zerando os elementos abaixo de a33


−1 2 3 1 1
0 2 −1 −2 −1
0 0 1 1 2
0 0 −1 9 2


E4 + E3 →


−1 2 3 1 1
0 2 −1 −2 −1
0 0 1 1 2
0 0 0 10 4


24 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 2
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 2
Retrossubstituic¸a˜o
Portanto, atrave´s de retrossubstituic¸a˜o podemos verificar que a
soluc¸a˜o de (2) e´:
x4 = 2/5, x3 = 8/5, x2 = 7/10, x1 = 28/5.
25 / 34
Sistemasde Equac¸o˜es Lineares
Exemplo 3
Suma´rio
Fundamentos
Exemplo 1
Exemplo 2
Exemplo 3
26 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
Problema
Como terceiro exemplo, tomemos o sistema de equac¸o˜es


3x1 + 2x2 − 1x3 + 2x4 = 1
3x1 + 4x2 + 1x3 + 1x4 = 3
−6x1 − 2x2 + 4x3 − 3x4 = 5
−3x1 − 6x2 − 3x3 − 4x4 = 2
(3)
Os passos da aplicac¸a˜o do me´todo de Gauss na resoluc¸a˜o do
sistema (3) sa˜o descritos no que segue.
27 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
Triangularizac¸a˜o
0) Obtendo a matriz aumentada:


3 2 −1 2 1
3 4 1 1 3
−6 −2 4 −3 5
−3 −6 −3 −1 2


28 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
Triangularizac¸a˜o
1) Primeiro passo: zerando os elementos abaixo de a11


3 2 −1 2 1
3 4 1 1 3
−6 −2 4 −3 5
−3 −6 −3 −1 2


E2 − E1 →
E3 + 2E1 →
E4 + E1 →


3 2 −1 2 1
0 2 2 −1 2
0 2 2 1 7
0 −4 −4 1 3


29 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
Triangularizac¸a˜o
2) Sistema resultante:


3 2 −1 2 1
0 2 2 −1 2
0 2 2 1 7
0 −4 −4 1 3


E3 − E2 →
E4 + 2E2 →


3 2 −1 2 1
0 2 2 −1 2
0 0 0 2 5
0 0 0 −1 7


30 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
A partir das equac¸o˜es obtidas no terceiro passo, verificamos que o
sistema na˜o tem soluc¸a˜o, pois:
{
2x4 = 5
−x4 = 7
31 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss: Exemplo 3
Se o lado direto da terceira equac¸a˜o fosse −14, enta˜o as duas
u´ltimas equac¸o˜es do sistema reduzido seriam:
{
2x4 = −14
−x4 = 7
Usando este valor x4 = −7 na terceira equac¸a˜o com qualquer valor
de x3, podemos encontrar uma soluc¸a˜o para o sistema. Ou seja, o
sistema teria um nu´mero infinito de soluc¸o˜es.
32 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Me´todo de Eliminac¸a˜o de Gauss
Teorema
Seja A ∈ Rn×n uma matriz e b ∈ Rn×1 um vetor, enta˜o Ax = b
pode ser resolvida pelo algoritmo de Gauss com:
{
n2 + 13(n − 1)(n + 1)n ∈ O(n
3) multiplicac¸o˜es ou diviso˜es
n(n − 1) + 16(n − 1)(2n − 1)n ∈ O(n
3) adic¸o˜es ou subtrac¸o˜es
33 / 34
Sistemas de Equac¸o˜es Lineares
Exemplo 3
Comenta´rios Finais
I Fim!
I Obrigado pela presenc¸a
34 / 34