Capítulo 03 - Sistemas Lineares

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

A resolução de sistemas lineares é um problema que surge nas mais 
 diversas áreas!!!
 Análise de Circuitos elétricos
 Análise de Vibrações de um Sistema Mecânico
Distribuição da força-peso na estrutura de um edifício
Capítulo 03:
Estudaremos alguns métodos para calcular a solução de sistemas de equações lineares.
Apenas nos preocuparemos com sistemas quadrados
Sistemas em que o número de equações é igual ao número de incógnitas.
Veremos os seguintes métodos:
Método de Triangularização de Gauss;
Método Iterativo de Gauss-Siedel.
Noções básicas de álgebra matricial,
Adição e multiplicação de matrizes, etc.
	serão supostas conhecidas!
Introdução
Um sistema linear de ordem n
A resolução de um sistema linear consiste em calcular os valores de xi, caso eles existam, que satisfaçam todas as equações simultaneamente!
Vamos ver alguns exemplos de métodos já conhecidos.
Como resolver sistemas deste tipo?
Métodos para resolução de sistemas lineares
Exemplo 1: Sistema linear de segunda ordem
Substituindo em (1):
Substituindo em (2):
Solução:
Resolver o sistema do Exemplo 1 significa determinar a intersecção de duas retas.
Temos três casos possíveis representados nas figuras abaixo:
x1
x2
x1
x2
x1
x2
Retas Concorrentes
O sistema possui uma 
única solução!
(b) Retas Paralelas
O sistema possui não 
possui solução!
Sistema Inconsistente.
(c) Retas Coincidentes
O sistema possui infinitas 
soluções!
Sistema Indeterminado.
Reta 1
Reta 2
Ainda o Exemplo 1
Exemplo 2: Sistema linear de segunda ordem
Regra de Cramer
Matriz dos coeficientes
Numerador : Matriz dos coeficientes 
com a ia. coluna sendo substituída pelo 
vetor dos termos independentes!
matricialmente  AX = B 
Regra de Cramer
2
1
2
1
3
-1
3
-1
3
2
1
-1
3
1
3
1
Cuidado com o sinal !!!!
+
-
Determinante
Exemplo 3: Resolver graficamente os sistemas lineares de segunda ordem
A utilização do método de Cramer para sistemas lineares pode ser inviável, pois o número de operações aritméticas que devem ser efetuadas aumenta consideravelmente com pequeno aumento na ordem do sistema.
Ordem
No. Operações
Tempo estimado
2
11
0,01
3
59
0,08
4
319
0,44
5
1349
2
6
13691
19
7
109591
152
8
986399
1370
9
9234089
12825
10
101575099
141076
Na tabela ao lado estes números de operações são calculados para alguns valores de n.
1 operação aritmética 
a cada 5s!
horas
Por um computador, o tempo estimado para resolver um sistema de ordem 20 é de 1,5 107 anos.
1 operação aritmética 
a cada 3,6 10-6s!
Na verdade, o tempo gasto pelo computador é bem maior, pois apenas foram consideradas as operações aritméticas.
Outro detalhe que deve ser observado é que, na solução de problemas reais, sistemas de ordem 20 e maiores ocorrem com freqüência.
Precisamos de processos mais eficientes para resolver estes sistemas lineares!!
Método de eliminação de Gauss
O método de eliminação de Gauss consiste em transformar um sistema linear AX = B em um sistema triangular inferior equivalente.
Matriz Triangular Inferior
Gauss
Para transformar um sistema linear AX = B em um sistema triangular equivalente utilizaremos a seguinte propriedade da Álgebra Linear:
A solução de um sistema linear não se altera se subtrairmos de uma equação outra equação do sistema multiplicada por uma constante.
Para maior facilidade, vamos descrever este método para um sistema de ordem 3. 
O mesmo processo pode ser aplicado para sistemas de qualquer ordem!
Exemplo 4: Sistema linear de ordem 3
Gauss
Etapa 1: Reescrevendo o sistema na representação matricial:
O elemento a11 deve ser  0 (SEMPRE).
Se necessário, a ordem das equações pode ser alterada!!!!
Cuidado com o sinal !!!!
Etapa 2: Trabalharemos com a Matriz Aumentada:
Matriz dos coeficientes + termos independentes.
Etapa 3: Começaremos a triangularizar a matriz.
Temos que conseguir:
a21 = 0
Gauss
a31 = 0
a32 = 0
Regra para a 
multiplicação 
de elementos:
+
-
Pivô
0
1
2
5
Gauss
Em primeiro lugar vamos conseguir que a21 seja = a 0!
Agora vamos conseguir que a31 seja = a 0!
Gauss
Pivô
0
1
-22
5
Gauss
Agora vamos conseguir que a32 seja = a 0!
0
-24
0
Pivô
O elemento Pivô deve ser  0 (SEMPRE).
Se necessário, a ordem das equações pode ser alterada!!!!
Caso não seja possível, o sistema é indeterminado ou inconsistente!
Gauss
A Matriz está triangularizada!!!!
Etapa 3: Calcular os valores das variáveis!
Gauss
O número de horas necessário por cada artigo de cada tipo para ser manufaturado é dado na tabela abaixo:
Exemplo 5: Uma empresa fabrica 3 tipos diferentes de artigos metálicos, cada um dos quais deve ser usinado, polido e montado em seu processo de manufatura. 
A empresa dispõe, numa base semanal e face ao número de operários contratados, de 480 horas de usinadores, 400 horas de polidores e 400 horas de montadores.
Quantas unidades de cada tipo do artigo metálico devem ser fabricadas de modo que não haja horas ociosas para a mão de obra contratada?
Gauss
Nossas incógnitas são os números de unidades de cada tipo a manufaturar por semana:
Número de unidades do produto 1 / semana
Número de unidades do produto 2 / semana
Número de unidades do produto 3 / semana
Resultam as 3 equações lineares nos 3 parâmetros acima, quando se leva em conta as horas disponíveis por semana.
Usinagem
Polimento
Montagem
U
P
M
Prod1
3
1
2
Prod2
2
4
1
Prod3
2
2
6
Regra para a 
multiplicação 
de elementos:
+
-
Pivô
0
10
4
720
Gauss
Em primeiro lugar vamos conseguir que a21 seja = a 0!
Agora vamos conseguir que a31 seja = a 0!
Gauss
Pivô
0
-1
14
240
Gauss
Agora vamos conseguir que a32 seja = a 0!
0
144
3120
Pivô
Gauss
A Matriz está triangularizada!!!!
Etapa 3: Calcular os valores das variáveis!
Gauss
Gauss
Resultado: Dentro da precisão dos cálculos, devem ser fabricados, semanalmente:
Produto 1
Produto 2
Produto 3
103 unidades
63 unidades
22 unidades
Análise do número de operações do Método de Gauss
Ordem
No. Operações
Tempo estimado
2
9
0h 0’ 45’’
3
28
0h 2’ 20’’
4
62
0h 5’ 15’’
5
115
0h 9’ 35’’
6
191
0h 15’ 55’’
7
294
0h 24’ 30’’
8
428
0h 35’ 40’’
9
597
0h 49’ 45’’
10
805
1h 7’ 5’’
1 operação aritmética 
a cada 5s!
Por um computador, o tempo estimado para resolver um sistema de ordem 20 é de 0,021276 s.
Gauss
Exemplo 6: Resolva o seguinte circuito elétrico:
Gauss
2
E
30V
7
4
I1
I2
4
I1
I2
2
7
4
4
I1
I2
2
7
4
Gauss
0
50
210
Gauss
Exemplo 7: Para quais valores de m o sistema é indeterminado?
0
m-1
2
m-1
0
-1-m
1+m
-1-m
0
0
m2+2m+1
0
=0
Sistema Indeterminado
Gauss
Portanto, para m = -1 o sistema é indeterminado!
Método Iterativo de Gauss-Seidel
introdução
Estudaremos um novo método para calcular a solução de sistemas de equações lineares.
Novamente, apenas nos preocuparemos com sistemas quadrados
Sistemas em que o número de equações é igual ao número de incógnitas.
O novo método é um processo iterativo que consiste em calcular uma seqüência de aproximações da solução do sistema, a partir de uma aproximação inicial.	
Aproximação Inicial
Seqüência de aproximações
Solução 
Método de Gauss - Seidel
Um sistema linear de ordem 3
a11  0
Vamos admitir que na diagonal principal estão os maiores coeficientes em valor absoluto de cada equação.
Demonstraremos o método
para um sistema de ordem 3, mas ele pode ser utilizado para sistemas de qualquer ordem!
Método de Gauss - Seidel
Vamos isolar os termos xi para cada equação:
Primeira equação: isolaremos x1
Isolando a11 x1
Dividindo por a11 
Reescrevendo a equação
Método de Gauss - Seidel
Segunda equação: isolaremos x2
Isolando a22 x2
Dividindo por a22 
Reescrevendo a equação
Método de Gauss - Seidel
Terceira equação: isolaremos x3
Isolando a33 x3
Dividindo por a33 
Reescrevendo a equação
Método de Gauss - Seidel
Vamos colocar um índice para indicar a iteração:
K  significa a iteração anterior
K = 0 (Chute)
K + 1  significa a iteração utilizando o resultado da iteração K
Método de Gauss - Seidel
escolhida uma aproximação inicial
calcular a seqüência de aproximações
utilizando as equações
O método consiste em : 
Módulo 4 p. 48
Exemplo 1: Resolva o sistema abaixo pelo método de Gauss-Seidel considerando x0 = (0, 0, 0) e 4 iterações.
Método de Gauss - Seidel
Etapa 1: Os maiores coeficientes em valor absoluto de cada equação estão na diagonal principal?
maior coeficiente de x1 (considerando as 3 equações)  4 
maior coeficiente de x2 (considerando as 2 equações restantes)  5
Equação (1)
Equação (2)
A ordem das equações no sistema está OK!
Etapa 2: Isolando os xi e adicionando os índices que indicarão as iterações.
Método de Gauss - Seidel
Etapa 3: Vamos fazer a seguinte tabela:
Método de Gauss - Seidel
k
x1
x2
x3
0
1
2
3
4
0
0
0
(5 – 0 – 0) / 4
(2*1,25 – 0) / 5
(-6,5 - 3*1,25 – 0,50) / 6
1,25
0,50
-1,79
(5 – 0,5 + 1,79) / 4
(2*1,57 +1,79) / 5
(-6,5 - 3*1,57 – 0,99) / 6
1,57
0,99
-2,03
(5 – 0,99 + 2,03) / 4
(2*1,51 + 2,03) / 5
(-6,5 - 3*1,51 – 1,01) / 6
1,51
1,01
-2,01
(5 – 1,01 + 2,01) / 4
(2*1,51 + 2,01) / 5
(-6,5 - 3*1,50 – 1,00) / 6
1,50
1,00
-2,00
Método de Gauss - Seidel
Resposta:
Esta é a solução do sistema, mas, convém lembrar, que um processo iterativo nem sempre fornece a solução exata do sistema!!!
Critério de Parada
Método de Gauss - Seidel
Dizemos que o método converge se, para a seqüência de aproximações gerada, dado  > 0, existir , tal que 
para todo k > e 
i = 1, 2, ..., n, 
 
Como na prática não conhecemos , torna-se necessário um critério de parada para o processo. 
Adotaremos um critério que compara duas soluções consecutivas usando a variação relativa: 
 
onde: 
 
Considera-se, como referência, o valor 
máximo entre todas as variações relativas 
de uma mesma iteração (k).
Método de Gauss - Seidel
Método de Gauss - Seidel
Consideraremos que o processo convergiu quando 
	Vark  , para algum k e adotaremos como solução do sistema a k-ésima aproximação obtida.
Como o processo pode não convergir, devemos estipular um número máximo de iterações (ITMAX) a serem feitas. 
Lembre-se de considerar, como referência, o valor 
máximo entre todas as variações relativas 
de uma mesma iteração (k).
Exemplo 2: Resolva o sistema abaixo pelo método de Gauss-Seidel considerando x0 = (0, 0, 0) e  = 0,001 ou ITMAX = 3.
Método de Gauss - Seidel
Etapa 1: Os maiores coeficientes em valor absoluto de cada equação estão na diagonal principal?
maior coeficiente de x1 (considerando as 3 equações)  10,2 
maior coeficiente de x2 (considerando as 2 equações restantes)  9,8
Equação (3)
Equação (2)
Temos que alterar a ordem das equações (1) e (3)
Alterando a ordem das equações (1) e (3):
Método de Gauss - Seidel
Os maiores coeficientes em valor absoluto estão na diagonal principal!
Etapa 2: Isolando os xi e adicionando os índices que indicarão as iterações.
Método de Gauss - Seidel
Adicionando os índices que indicarão as iterações:
(
-7,8 – 4,2*0,34 – 5,7*0,6) / 11,9
Etapa 3: Vamos fazer a seguinte tabela:
Método de Gauss - Seidel
k
x1
x2
x3
v1
v2
v3
0
1
2
3
0
0
0
(3,5 – 0 – 0) / 10,2
(5,2 + 2,1*0,34 +3,1*0) / 9,8
0,34
0,60
-0,49
(3,5 – 3,9*0,6 + 4,9*0,49) / 10,2
(5,2 + 2,1*0,35 +3,1*0,49) / 9,8
(-7,8 – 4,2*0,35 + 5,7*0,45) / 11,9
 0,35
0,45
-0,56
(3,5 – 3,9*0,45 +4,9*0,56) / 10,2
(5,2 + 2,1*0,35 - 3,1*0,56) / 9,8
(-7,8 – 4,2*0,44 + 5,7*0,45) / 11,9
0,44
 0,45
-0,60
1
1
1
0,03
0,33
0,13
0,20
0,00
0,07
Método de Gauss - Seidel
Resposta: 
Esta é a solução do sistema, mas, convém lembrar, que um processo iterativo nem sempre fornece a solução exata do sistema!!!
Critérios de Convergência
Quando utilizamos o método iterativo de Gauss-Seidel para resolver um sistema linear AX = B , devemos nos preocupar com a convergência da seqüência de aproximações da solução.
Existem condições sobre os elementos da matriz A dos coeficientes do sistema que, se satisfeitas, são suficientes para garantir a convergência do método de Gauss-Seidel.
Analisaremos os seguintes critérios de convergência:
Critério da Soma por Linhas
Critério de Sassenfeld
Critérios de Convergência 
Critério da Soma por Linhas
O método de Gauss-Seidel gera uma seqüência convergente se: 
 			 onde
 
akk  0
O Sistema do Exemplo 1:
O processo converge!!
Critérios de Convergência 
O Sistema do Exemplo 2:
O processo converge!!
Critérios de Convergência 
Critérios de Convergência 
Critério de Sassenfeld
O método de Gauss-Seidel gera uma seqüência convergente se calculados os coeficientes: 
 			 e
 				 , obtenho:
a11  0 e
aii  0
Em outras palavras:
Critérios de Convergência 
 . 			 
 	
			
			
O Sistema do Exemplo 1:
O processo converge!!
Critérios de Convergência 
O Sistema do Exemplo 2:
O processo converge!!
Critérios de Convergência 
Exemplo 3: Verifique se o processo de Gauss-Seidel converge para o sistema abaixo .
O processo converge!
Critérios de Convergência 
Soma por Linhas:
Sassenfeld:
O process não converge!
Sistemas Lineares Determinados
Comentários
Como os critérios de Sassenfeld e das linhas são apenas condições suficientes para a convergência, o método de Gauss-Seidel pode ser utilizado para resolver sistemas lineares que não satisfaçam a nenhum destes critérios. 
Entretanto, nestes casos deve ser feita uma análise cuidadosa da seqüência de aproximações obtida, já que o método de Gauss-Seidel não detecta se o sistema é determinado ou não.
Critérios de Convergência 
Sistemas que convergem por Gauss-Seidel
Sistemas que satisfazem o critério de Sassenfeld
Sistemas que satisfazem o critério de linhas
Exemplo 4: Considere o sistema abaixo que depende de uma parâmetro  a determinar. 
Critérios de Convergência 
Para que valores de  se pode garantir a convergência, por método iterativo, para a solução do sistema? 
Resolva aplicando o critério de Sassenfeld, sem alterar a ordem das equações do sistema.
Sassenfeld:
Temos que resolver as duas inequações para encontrar o intervalo de valores de  para os quais o sistema converge.
Critérios de Convergência 
Primeira Inequação:
Critérios de Convergência 
Segunda Inequação:
Critérios de Convergência 
Solução:
Gauss x Gauss - Seidel
Vamos utilizar um exemplo para comparar o método de triangularização de Gauss e o método iterativo de Gauss-Seidel.
Exemplo 5: Um criador tem 80 cavalos de raça. A recomendação do veterinário de suplemento vitamínico diário para cada cavalo é dado na tabela abaixo: 
Essas vitaminas estão disponíveis em 6 tipos de farelos vitaminados a serem acrescidos à ração diária dos 80 cavalos. Cada grama de farelo de cada tipo contém
o número de unidades das vitaminas indicado no quadro a seguir:
130
250
20
150
50
100
No. de unidades de vitamina
F
E
D
C
B
A
Tipo de Vitamina
Doses diárias para um cavalo
Tipo de Vitamina
A
B
C
D
E
F
Farelo1
4
2
0
4
1
0
Farelo2
0
5
3
0
0
2
Farelo3
1
0
6
1
0
0
Farelo4
1
0
0
6
2
0
Farelo5
0
0
0
0
4
3
Farelo6
0
1
2
0
0
6
Número de unidades de vitamina por grama de farelo
Quantas gramas de cada tipo de farelo o criador deve acrescentar à ração diária dos 80 cavalos para que sejam atendidas exatamente as suas necessidades vitamínicas?
Gauss x Gauss-Seidel 
Vamos chamar de xi , i = 1, 2, ... , 6, o número de gramas do Farelo i a ser acrescido à ração diária dos 80 cavalos.
Tipo de Vitamina
A
B
C
D
E
F
Farelo1 –xi
4
2
0
4
1
0
Farelo2 –x2
0
5
3
0
0
2
Farelo3 –x3
1
0
6
1
0
0
Farelo4 –x4
1
0
0
6
2
0
Farelo5 –x5
0
0
0
0
4
3
Farelo6 –x6
0
1
2
0
0
6
No. de unidades de vitamina para 80 cavalos
100
*80
50
*80
150
*80
20
*80
250
*80
130
*80
Número de unidades de vitamina por grama de farelo
Gauss x Gauss-Seidel 
O problema se equaciona nas 6 expressões lineares nos parâmetros xi :
A
B
C
D
E
F
4
2
0
4
1
0
0
5
3
0
0
2
1
0
6
1
0
0
1
0
0
6
2
0
0
0
0
0
4
3
0
1
2
0
0
6
80*100
80*50
80*150
80*20
80*250
80*130
Gauss x Gauss-Seidel 
Na forma reduzida :
Etapa 1: Os maiores coeficientes em valor absoluto de cada equação estão na diagonal principal?
> coeficiente de x1  4  (1)
A ordem do sistema está ok!
(1)
(2)
(3)
(4)
(5)
(6)
> coeficiente de x2  5  (2)
> coeficiente de x3  6  (3)
> coeficiente de x4  6  (4)
> coeficiente de x5  4  (5)
> coeficiente de x6  6  (6)
Gauss x Gauss-Seidel 
Etapa 2: Verificando a convergência do sistema pelo critério de linhas :
O processo converge!!
Gauss x Gauss-Seidel 
Etapa 3: Isolando os xi e adicionando os índices que indicarão as iterações.
Gauss x Gauss-Seidel 
Etapa 4: Vamos aplicar o método de Gauss-Seidel considerando  = 0,001 ou ITMAX = 5.
k
x1
x2
x3
x4
x5
x6
v1
v2
v3
v4
v5
v6
0
1
2
3
4
5
0
0
0
0
0
0
2000
0
2000
-1400
5200
-866,7
1
1
1
1
1
1
1850
233,3
2172,2
-1329
5201,9
-945,4
0,081
1
0,079
0,054
0,000
0,083
1789,1
273,4
2178,4
-1289
5197,3
-956,5
0,034
0,147
0,003
0,031
0,000
0,012
1777,7
280,2
2178,7
-1282
5196,4
-958,3
0,006
0,024
0,000
0,006
0,000
0,002
1775,7
281,4
2178,7
-1280
5196,2
-958,6
0,001
0,004
0,000
0,001
0,000
0,000
Resposta: 
Gauss x Gauss-Seidel 
Etapa 5: Vamos aplicar o método de triangularização de Gauss.
Gauss x Gauss-Seidel 
O método de triangularização de Gauss é mais exato 
... 
mas é mais trabalhoso quando se trata de sistemas grandes!