Sistemas de Equações Lineares - Métodos Diretos

Prévia do material em texto

MODELAGEM MATEMÁTICA
Aula 04: SISTEMAS DE EQUAÇÕES LINEARES – MÉTODOS
DIRETOS
Apresentação
Na aula passada, começamos a tratar da resolução de problemas clássicos em Engenharia. De início, você aprendeu as
principais técnicas de identi�cação de raízes ou zeros de funções de uma variável. Deste modo, além de conhecer os
critérios de existência e unicidade de soluções, você estudou os principais métodos de resolução (intervalos, aproximação
e secantes), terminando com a aplicação os métodos estudados, por meio da implementação computacional de
programas em Python.
Agora, nós começaremos o estudo de sistemas de equações lineares algébricas (SELA). Tais sistemas são muito úteis em
tarefas diversas, como a análise de circuitos elétricos (Engenharia Elétrica), do comportamento variante no tempo de
sistemas de comunicações sem �o (Engenharia de Telecomunicações), de sistemas mecânicos (Engenharia Mecânica) e
da distribuição de forças em estruturas (Engenharia Civil), dentre outros.
Assim, o objetivo da aula de hoje é começar a apresentar os principais métodos de solução de sistemas de equações
lineares algébricas em uma de suas duas vertentes – os denominados métodos diretos. Em primeiro lugar, você
aprenderá o método de eliminação de Gauss. Adicionalmente, você estudará o método de decomposição LU. Por �m, você
aplicará estes novos conhecimentos, implementando-os com suporte da linguagem de programação Python.
Objetivos
Identi�car os principais conceitos associados a sistemas de equações lineares;
Descrever os principais métodos diretos de resolução de sistemas de equações lineares: eliminação de Gauss e
decomposição LU;
Aplicar os métodos estudados com suporte da linguagem de programação Python.
Resolução de sistemas de equações lineares
Conforme descrito em Moura (2017), um sistema de equações lineares algébricas (SELA) pode ser de�nido como um conjunto
de n equações com n variáveis independentes entre si. A seguir, vemos a forma genérica de um SELA:
 
Neste modelo genérico que você acabou de ver, nós temos que os termos aij (i, j = 1, 2, 3, ..., n) são os coe�cientes do sistema
de equações. Já os termos xi (i = 1, 2, 3, ..., n) representam as n incógnitas ou variáveis do SELA. Por �m, temos que bi (i = 1, 2,
3, ..., n) indicam os resultados das equações ou os termos independentes (termos que recebem este nome por não
dependerem das variáveis xi).
  +     +     +  . . .   +   =  a11 x1 a12x2 a13x3 a1n xn b1
  +     +     +  . . .   +   =  a21 x1 a22x2 a23x3 a2n xn b2
  +     +     +  . . .   +   =  a31 x1 a32x2 a33x3 a3n xn b3
  +     +     +  . . .   +   =  an1 x1 an2 x2 an3 x3 annxn bn
É importante você saber que esta não é a única forma de se representar um SELA. Além da forma algébrica apresentada há
pouco, você pode representar as equações estudadas sob a forma matricial, pois 
, formula, sabendo-se que:
 
Nesta forma matricial, nós temos que a matriz A corresponde a uma matriz quadrada (isto é, com o mesmo número de linhas e
de colunas) de ordem n contendo os coe�cientes do SELA. Já o vetor-coluna x corresponde às incógnitas ou variáveis que nós
estudamos na forma algébrica. Por �m, temos o vetor-coluna b que contém os termos independentes do sistema.
A_ {nxn} \ times x_ {nx1}  =  b_ {nx1}
[A]  =   ,   [X]  =   ,    [b]  =  
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
a11 
a21 
a31 
.
.
.
an1 
a12 
a21 
a31 
.
.
.
an2 
a13 
a21 
a31 
.
.
.
an3 
. . .
. . .
. . .
.
a1n 
a2n 
a3n 
.
.
.
ann 
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
x1
x2
x3
.
.
.
xn
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
b1
b2
b3
.
.
.
bn
∣
∣
∣
∣
∣
∣
∣
∣
∣
∣
       Ok, mas como nós podemos identi�car a resposta do SELA?
Existem dois tipos principais de métodos, os diretos e os iterativos. Os métodos diretos, foco da aula de hoje, caracterizam-se
pela obtenção dos resultados para as variáveis xi (i = 1, 2, 3, ..., n) de modo exato e direto, sem que você precise fazer
execuções repetidas ou iteradas de expressões algébricas para obtenção de aproximações adequadas para os valores-
resposta desejados. Deste modo, veremos a seguir os principais métodos diretos, cada um com sua estratégia e, naturalmente,
com as vantagens e desvantagens associadas.
Métodos diretos de resolução de SELA
O primeiro dos métodos a serem estudados nesta aula é a substituição retroativa. Este método é aplicado para todo SELA em
que Ax = b, mas em uma condição especí�ca: aij = 0, para todo j < i – em outras palavras, quando a matriz A é do tipo triangular
superior.
A situação descrita no parágrafo anterior pode ser expressa sob a forma algébrica na forma apresentada a seguir:
 
 
Apesar de ser empregada em situação bastante restrita, o método da Substituição Retroativa apresenta uma grande vantagem:
sua solução é trivial e direta. Veja só: com base na última equação , temos que o valor de é dado por 
⎡
⎣
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢
a11x1 + a12x2
a22x2
+
+
a13x3
a22x2
a33x3
+
+
+
. . .
. . .
. . .
+
+
+
a1n xn
a2n xn
a3n xn
.
.
.
annxn
=
=
=
.
.
.
=
b1
b2
b3
.
.
.
bn
⎤
⎦
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥
.   =  ann xn bn xn
bn
ann
Feito este cálculo, podemos subistituir o valor obtido na equação imediatamente anterior (a saber,
), de modo que o valor de Xn-1 seja determinado facilmente a partir da
substituição de Xn pelo valor indicado no parágrafo anterior - ou seja, . Assim, trata-se de determinar
Xn-1 a partir da substituição da variável subsequente (Xn).
Creio que você já tenha percebido que as variáveis serão calculadas na sequência inversa
daquela indicada no vetor X das variáveis - ou seja, de modo retroativo, com base na substituição das variáveis sucessoras nas
expressões algébricas que as de�nem no SELA. daí, conhecermos o método pelo termo Substituição Retroativa. Conforme
exposto em Moura (2017), veja a seguir o algoritmo que representa este método:
, .   + , .   =    an−1  n−1 xn−1 an−1  n xn bn−1
  =  xn−1
−bn−1  an−1, n.xn
an−1, n−1
  ,  . . . . ,  xn−2,  xn−3,  x2,  x3,  x1 
/* Dados de Entrada: número de variáveis – n; matriz de coe�cientes – A;
vetor de termos independentes – b*/
/* Resultado: vetor solução – x */
Início
xn ← 
Para i de n-1 até 1 passo -1 faça
SOMA ← 0
Para j de i+1 até n faça
SOMA ← SOMA + aijxj
Fim-Para
xi ← (bi – SOMA)/aii
Fim-Para
Fim-Substituição Retroativa
bn
ann
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Já o segundo método que estudaremos é denominado Eliminação de Gauss. Este método consiste em operar transformações
elementares sobre as equações de um sistema Ax = b até que, depois de n - 1 passos, se obtenha um sistema triangular
superior, Ux = c, equivalente ao sistema dado, o qual pode ser resolvido por substituições retroativas – ou seja, da forma que
você acabou de aprender.
O método de Eliminação de Gauss apresenta duas fases. Conforme descrito em Moura (2017), temos:
1
Fase de eliminação
Consiste em transformar o sistema dado em um sistema
triangular superior.
 
 
 
 
2
Fase de substituição
Na qual se resolve o sistema triangular superior através de
substituições retroativas, de acordo com a técnica
apresentada no método da Substituição Retroativa.
Vamos ver um exemplo disto? Vamos considerar as matrizes A e b apresentadas a seguir:
 
 
Em primeiro lugar, precisamos anular o termoA(2,1). Isto se dá da seguinte forma:
 
 
Desta forma, temos que a 2a linha é recalculada a partir de sua soma com a 1a linha multiplicada por m = -2. Logo:
 
 
A  =  ;  b =  
⎡
⎣
⎢
2
4
5
3
3
2
1
2
3
⎤
⎦
⎥
⎡
⎣
⎢
2
1
3
⎤
⎦
⎥
m = = = −2
−A(2,1)
A(1,1)
−4
2
A (2, 1)  =  A (2, 1)  +  m * A (1, 1)  → A (2, 1)  =  4  +   (−2) * 2 → A (2, 1)  =  0
Depois, fazemos o mesmo para que A(3,1) e A(3,2) também sejam iguais a zero. Isto feito, vemos que as novas matrizes A e b
assumem os valores expostos a seguir:
 
 
Como mencionamos anteriormente, agora temos um sistema sob uma forma de apresentação que pode ser resolvida com o
métido de Substituição Retroativa, visto que a matrizA é triangular superior. Conforme descrito em Moura (2017), o algoritimo
que representa a operação descrita anteriormente é dado por:
A  =  ;  b =  
⎡
⎣
⎢
2
0
0
3
−3
0
1
0
0, 5
⎤
⎦
⎥
⎡
⎣
⎢
2
−3
3, 5
⎤
⎦
⎥
/* Dados de Entrada: número de variáveis – n; vetor de coe�cientes – A;
vetor de termos independentes – b*/
/* Resultado: vetor de coe�cientes – A; vetor de termos independentes – b*/
Inicio
Para k de 1 até n-1 faça
Para i de k+1 até n faça
m ← - 
Para j de 1 até n faça
aij ← aij + m akj
Fim-Para
bi ← bi + m bk
Fim-Para
Fim-Para
Fim-Eliminação
− aik
akk
Agora, é só aplicar o método da Substituição Retroativa. Fácil, não é?
No entanto, o Método de Eliminação de Gauss também apresenta suas desvantagens. Por exemplo, ele não pode ser aplicado
quando houver um termo na diagonal principal (ou seja, na forma akk) que seja nulo, além do risco de propagação de erros de
arredondamento, o que pode comprometer a validade da solução obtida. Neste último caso, para resolver (ou, ao menos,
minimizar) tais problemas, adota-se a troca de linhas das equações do SELA.
Outra forma de resolver este problema é por meio da utilização de outra estratégia, a denominada decomposição LU. Conforme
descrito em UFRGS (2019), nós podemos fatorar a matriz A como o produto de duas matrizes, uma triangular inferior
(denominada matriz L) e outra triangular superior (denominada matriz U). Deste modo, temos:
 
 
 
Assim, a resolução do sistema de equações lineares se dá em duas etapas: a primeira é a resolução de um sistema triangular
inferior (L.y = b), para em seguida resolver um sistema triangular superior (U.x = y), de modo que a solução x é a resposta para o
sistema original.
A. x  =  b
(L. U). x  =  b
L. (U . x)  =  b
Excelente, mas como obter as matrizes L e U? Simples. A matriz U é obtida ao �nal do escalonamento que vimos no método da
Eliminação de Gauss. Já os elementos da matriz L são tais que:
1
Os elementos da diagonal principal são todos iguais a 1;
2
Os elementos acima da diagonal principal são todos iguais a 0
(a�nal, é uma matriz triangular inferior);
3
Os elementos abaixo da diagonal principal são os múltiplos do
primeiro elemento da linha de A a ser zerado dividido pelo pivô
acima na mesma coluna.
Vamos ver com calma esta última regra.
Por exemplo, para obter o exemplo de L21, nós fazemos A21 dividio pelo pivô acima na mesma coluna - ou seja, A11. Para o
elemento L31, nós fazemos parecido, pois tomamos A31 para que seja dividido pelo pivô acima na mesma coluna - novamente
A11. Este processo deve ser repetido para as próximas colunas, escalonando a matriz A para se coletar os elementos abaixo da
diagonal principal da matriz L.
Por exemplo, vamos aplicar a decomposição LU na matriz A utilizada no exemplo anterior:
 
 
Do próprio exercício que �zemos, já obtemos a matriz U:
 
A  = 
⎡
⎣
⎢
2
4
5
3
3
2
1
2
3
⎤
⎦
⎥
U   = 
⎡
⎣
⎢
2
0
0
3
−3
0
1
0
0, 5
⎤
⎦
⎥
Já a matriz L vem dos multiplicadores: A21 é igual a 4/2 = 2, A31 é dada por 5/2 = 2,5. Assim, chegamos a uma matriz
intermediária, já que não calculamos ainda o A32. Veja só:
 
 
Agora, podemos calcular o A32, que é dado por (-5,5)/(-3) = 11/6 = 1,83. Assim, chegamos à matriz L, dada por:
 
 
A partir daí, calculamos L.y = b e, em seguida, A.x = y. A resposta do SELA é o vetor x a ser obtido.
A  = 
⎡
⎣
⎢
2
0
0
3
−3
−5, 5
1
0
0, 5
⎤
⎦
⎥
L  = 
⎡
⎣
⎢
1
2
2, 5
0
1
1, 83
0
0
1
⎤
⎦
⎥
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Aplicação da linguagem Python
Vamos ver os códigos em Python destes três métodos? Com isto, creio que você estará em condições de aplicar os
conhecimentos aprendidos em implementações computacionais que o ajudem a solucionar problemas em Engenharia.
O código a seguir implementa a solução da Substituição Retroativa. Em outras situações, basta substituir as matrizes A e b,
bem como a quantidade de elementos de x, de modo conveniente a sua necessidade:
Executando este código em um ambiente Python de sua escolha , obtemos o vetor resposta x dado por [1,25 -0,5 1].
https://stecine.azureedge.net/webaula/estacio/go0323/aula4.html
import numpy as np;
A = ([[2,3,1],[0,2,2],[0,0,3]]);
b = ([2,1,3]);
x = np.zeros(3)
x[2] = b[2]/A[2][2]
n = 3
for i in np.arange(n-2,-1,-1):
SOMA = 0
for j in np.arange(i+1,n):
SOMA = SOMA + A[i][j]*x[j]
x[i] = (b[i] - SOMA)/A[i][i]
print(x)
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Já o algoritmo da fatoração LU disponível em UFRGS (2019) nos mostra um código em Python muito interessante. Veja a
seguir:
def fatoraLU(A):
U = np.copy(A)
n = np.shape(U)[0]
L = np.eye(n)
for j in np.arange(n-1):
for i in np.arange(j+1,n):
L[i,j] = U[i,j]/U[j,j]
for k in np.arange(j+1,n):
U[i,k] = U[i,k] - L[i,j]*U[j,k]
U[i,j] = 0
return L, U
Atividade
1. Assinale a ÚNICA alternativa que apresenta a matriz L resultante da decomposição LU da matriz A  = 
⎡
⎣
⎢
1
4
7
2
5
8
3
6
9
⎤
⎦
⎥
a) .L  = 
⎡
⎣
⎢
1
4
7
0
5
8
0
0
9
⎤
⎦
⎥
b) L  = 
⎡
⎣
⎢
1
4
7
0
1
8
0
0
1
⎤
⎦
⎥
c) L  = 
⎡
⎣
⎢
1
4
7
0
1
2
0
0
1
⎤
⎦
⎥
d) L  = 
⎡
⎣
⎢
1
4
7
0
5
2
0
0
9
⎤
⎦
⎥
e) nenhuma das alternativas anteriores.
2. Assinale a ÚNICA alternativa que apresenta a matriz U resultante da decomposição LU da matriz A  = 
⎡
⎣
⎢
1
4
7
2
5
8
3
6
9
⎤
⎦
⎥
a)L  = 
⎡
⎣
⎢
1
0
0
2
5
0
3
6
9
⎤
⎦
⎥
b)L  = 
⎡
⎣
⎢
1
0
0
2
1
0
3
6
1
⎤
⎦
⎥
c)L  = 
⎡
⎣
⎢
1
0
0
2
−3
0
3
−6
0
⎤
⎦
⎥
d)L  = 
⎡
⎣
⎢
1
4
7
0
5
2
0
0
9
⎤
⎦
⎥
e) nenhuma das alternativas anteriores.
3. Assinale a ÚNICA alternativa que apresenta uma limitação do método de Eliminação de Gauss:
a) Impossibilidade de utilização quando um elemento da diagonal principal é maior do que 0.
b) Impossibilidade de utilização quando um elemento da diagonal principal é igual a 0.
c) Impossibilidade de utilização quando um elemento da diagonal principal é menor do que 0.
d) Impossibilidade de utilização quando há elementos múltiplos entre si na diagonal secundária.>
e) mensagem de erro
4. Determine a solução do sistema A.x = b, dado que: A  =  ;  b =
⎡
⎣
⎢
2
0
0
3
−3
0
1
0
0, 5
⎤
⎦
⎥
⎡
⎣
⎢
2
−3
3, 5
⎤
⎦
⎥
a) x (1)  =   − 4;  x (2)  =  1;  x (3)  =  7
b) x (1)  =  4;  x (2)  =  1;  x (3)  =  7
c) x (1)  =   − 4;  x (2)  =  1;  x (3)  =   − 7
d) x (1)  =   − 4;  x (2)  =   − 1;  x (3)  =  7
e) nenhuma das alternativas anteriores.
5. Determine a solução do sistema A.x = b, dado que: A  =  ;  b =
⎡
⎣
⎢
2
0
0
3
3
0
1
0
3, 5
⎤
⎦
⎥
⎡
⎣
⎢
2
−3
3, 5
⎤
⎦
⎥
a) x (1)  =   − 1;  x (2)  =  1;  x (3)  =  7
b) x (1)  =  1;  x (2)  =  1;  x (3)  =  1
c) x (1)  =   − 1;  x (2)  =   − 1;  x (3)  =  1
d) x (1)  =   − 1;  x (2)  =   − 1;  x (3)  =   − 1
e) nenhuma das alternativas anteriores.
Notas
escolha
Por exemplo, utilize o compilador online disponível em: https://www.onlinegdb.com/online_python_compiler, acesso em 16 OUT
19.
Referências
MOURA, D. F. C, Cálculo Numérico. Rio de Janeiro: SESES, 2017. 144 p.
UFRGS (colaborativo). Cálculo Numérico: Um Livro Colaborativo Versão Python. Porto Alegre: UFRGS, 2019.
Próxima aula
Aprofundar os conceitos de sistemas de equações lineares;
O método de Gauss-Jacobi;
O método de Gauss-Seidel;
A li t h i t i l t d t d li d ã P th
javascript:void(0);
Aplicar estes novos conhecimentos, implementando-os com suporte da linguagem de programação Python.
Explore mais
Há materiais adicionais que podem complementar e ampliar seu conhecimento acerca dos métodos de determinação de
uma raiz de funções de uma só variável, motivando-o ainda mais para os novos desa�os que virão. Assim, segue uma lista
de sites na Internet para que você os consulte depois:
Sigmoidal. Resolvendo um Sistema de Equações Lineares com Python, acesso em 16 de outubro de 2019.
Khan Academy Brasil. Resolução de sistemas lineares por substituição, acesso em 16 de outubro de 2019.
UNIVESP.Métodos Numéricos– Aula 11 – Sistemas lineares, acesso em 16 de outubro de 2019.
javascript:void(0);
javascript:void(0);
javascript:void(0);