Sistema de equações lineares
Caracterização
 Um sistema de m equações a n variáveis é é
chamado sistema de equações lineares. Ele
tem a forma genérica seguinte:
a11 x1  a12 x2  ....  a1n xn  b1
a21 x1  a22 x2  ....  a2 n xn  b2
............................................
am1 x1  am 2 x2  ....  amn xn  bm
Solução
 Um conjunto de n valores (x1, ..., xn)
verificando as equações do sistema é uma
solução do sistema.
 Um sistema cujo os valores dos coeficientes
bn são iguais a 0 é um sistema homogêneo:
a11 x1  a12 x2  ....  a1n xn  0
a21 x1  a22 x2  ....  a2 n xn  0
............................................
am1 x1  am 2 x2  ....  amn xn  0
Caracterização matricial
 O sistema pode ser escrita sobre a forma de
um produto de matrizes:
onde as matrizes são definidas por:
Combinação linear
 A combinação linear de equações é a soma
dessas equações multiplicado por
coeficientes reais:

a1eq1+a2eq2+...+aneqn onde ai0, i{1,...,n} é
uma combinação linear de eq1, eq2, ..., eqn.
 Em relação com as variáveis envolvidas nas
equações, uma equação linear, combinação
linear entre as outras equações não introduz
novas relações entre as variáveis.
Sistemas equivalentes
 Num sistema de equações lineares independentes,
se uma equação é trocada por uma combinação
linear dela mesma e outras equações do sistema, o
novo sistema é equivalente o primeiro. Os dois
sistemas têm a mesma solução.
a1.eq1  a 2 .eq2  ...  a n eqn ,a1  0
eq1
eq
eq
 2
 2


...
...
eqn
eqn
Sistemas equivalentes
 Num sistema, se uma equação é combinação
linear das outras, ele é equivalente ao sistema
sem essa equação:
a 2 .eq2  ...  a n eqn
eq2
eq
eq
 2
 3


...
...
eqn
eqn
Equações e variáveis
 Um sistema de m equações a n variaveis:


Tem uma solução unica se ele pode ser reduzido
a um sistema de n equações independentes a n
variáveis.
Tem uma infinidade de soluções, se ele é
equivalente a um sistema de m’ equações
independentes com m’<n
Determinante
 Um determinante é um número associado a um
matriz quadrada (mesmo número de linha e coluna).
 A definição do determinação envolve a noção de
permutação. O determinante de uma matriz A (aij é
o coeficiente da i-ésima linha e j-ésima coluna) é,
onde an são elementos distintos de (1,...,n) e k é o
número de permutações para passar de (1,...,n) para
(a1,..., an):
k
n!
A   (1) a1a1 a2a2 ...anan
Calculo do determinante,
caso 2x2 e 3x3
 O calculo do determinante 2x2:
a11
a12
a21 a22
 a11a22  a21a12
 O calculo do determinante 3x3 é feito da forma
seguinte:
 Det A=
= a11a22a33  a21a32a13  a31a12a23
a31a22 a13  a11a32 a23  a21a12 a33
Determinante, caso nxn
 O desenvolvimento de Laplace permite o calculo do
determinante da forma seguinte:
a11
a12
... a1n
a21
a22
... a2 n
...
...
...
an1
an 2 ... ann
...
j n
j n
j 1
j 1
  aij D ij  a ji D ji , D ij  (1)i  j akp ,k i , p  j
Onde Dij é o determinante da submatriz obtido de A retidandose a i-ésima linha e j-ésima coluna e multiplicado por (-1)i+j.
O número i pode ser qualquer número de {1,...,n}. Esse
princípio funciona para qualquer linha ou coluna.
Determinante, caso nxn
 O calculo do determinante pode ser implementado
com um procedimento recursivo. O calculo de um
determinante nxn é determinado a partir de
determinantes (n-1)x(n-1).
 O preço do cálculo de um determinante é elevado.
Considerando a formula da definição, são
necessárias n!(n-1)+(n!-1) ou seja n!n-1 operações
para um determinante de dimensão n: (n!-1) somas
de n!(n-1) produtos, sem considerar os elementos
anexos necessários (posição de memoria, sinal, etc).
Determinante, um algoritmo
 O calculo é feito usando os coeficientes da primeira
linha.
Determinante(m) // m: matriz
se dim(m)=2 resultado=m[0][0].m[1][1]-m[1][0].m[0][1]
se dim(m)=1 resultado=m[0][0]
Se dim(m)>2 resultado=0
i de 1 a dim(m) construír a submatriz de m sem a primeira
linha e a i-ésima coluna (subm)
resultado=resultado+(-1)i.m[0][i].Determinante(subm)
Determinante e sistema
 Se um sistema de n equações lineares a n
variáveis tem um determinante diferente de
0: det A0, as equações do sistema são
independentes.
 Nesse caso, o sistema tem uma solução
única. Em caracterização matricial, essa
solução escreve-se:
1

x

A
    b 
onde A-1 é a matriz inversa da matriz A.
Determinante e matriz inversa
 Se o determinante de uma matriz é não nulo,
a matriz inversa pode ser calculada.
 a11 ... a1n 
 D11 ... D n1 
1 



A   ... ... ...  , A1   ... ... ... 
A
a


...
a
D
...
D
nn 
nn 
 n1
 1n
Onde Dij é o determinante da matriz formada a
partir da matriz A retirando a i-ésima linha e
j-ésima coluna.
Formula de Cramer
 Pela formula de Cramer, se o determinante do sistema é não
nulo, o valor solução da variável xi é dado pela formula
seguinte:
a11 ... a1i 1
b1
a1i 1
... a1n
1 a21 ... a2i 1 b2 a2i 1 ... a2 n
xi 
det A ... ... ... ... ... ... ...
an1 ... ani 1 bn ani 1 ... ann
 O numerator da fração é o determinante da matriz formada
da matriz A do sistema onde a coluna dos coeficientes de xi
são subsituídos pelos termos constantes bi.
Exemplo
2 x1  3 x2  x3  0

 x1  x2  4 x3  3
 x  8x  x  1
2
3
 1
0
x1 
2
3
1
det  1 1 4  2  8  12  3  64  1  64
1 8 1
3 1 4
1 8 1
64
2
x2 

46
64
0 1
1 3 4
1 1 1
64
2
x3 
1
3
3
10
64
0
1 1 3
1 8 1
64


62
64
Custo da formula de Cramer
 Para resolver um sistema de n equações a n
variáveis, pela formula de Cramer precisam
ser calculados n+1 determinante de ordem n
(n linhas, n colunas).
 O custo da resolução desse sistema é de:
(n!n-1)(n+1) operações.
Para 10 variaveis: 399167989
Eliminação Gaussiana
 A eliminação Gaussiana usa a propriedade de
equivalência de sistema para eliminar
progressivamente as variáveis ate chegar a
uma equação de uma variável.
a11 x1  a12 x2  ....  a1n xn  b1

a22 x2  ....  a2 n xn  b2


............................................

ann xn  bn
Sistema triangular
 No novo sistema, podemos determinar:
n
bn
bn1  an1n xn
1
xn 
, xn1 
,......, xi  (bi   aij x j )
ann
an1n1
aii
j i 1
 O sistema é chamado sistema triangular e a
matriz associada é uma matriz triangular. Se
fala também de triangular superior ou
inferior para caracterizar a posição dos
coeficientes não nulos.
Eliminação Gaussiana e
determinante
 O determinante de um sistema triangular é o
produto dos termos da diagonal.
a11
a12
... a1n
0
a22 ... a2 n
...
0
...
...
0
...
0
ann
 a11a22 ...ann
 Em um determinante, adicionar os termos (ou os
termos multiplicado por um fator) de qualquer linha
(resp. coluna) a qualquer outra linha (resp. coluna)
não muda o valor do determinante.
Método
 Escolhe uma das equações (i-ésima) com o
coeficiente (ai1) de x1 não nulo. Esse coeficiente é
chamado de pivot (ou pivot de Gauss).
 Adicionar a cada uma das equações restantes (j,
ji), a primeira equação multiplicada por: -aj1/ai1
 Aplicar de novo o algoritmo com o sub-sistema de
n-1 variáveis ate chegar a uma equação de uma
variável.
Exemplo
2 x1  3x2  x3  0
 x1  x2  4 x3  3
x1  8 x2  x3  1
2 x1  3 x2  x3  0
5
7
x2  x3  3
2
2
19
1
 x2  x3  1
2
2
2 x1  3 x2  x3  0
5
7
x2  x3  3
2
2
128
62
x3 
10
5
46

x

 1 64

10

 x2  
64

62

 x3  64

Matriz
 O processo pode ser aplicado com matrizes. Nesse
caso, se considera a matriz aumentada com as
constantes da matriz do sistema:
 a11

a21


[A ] 
 ...

 an1
a12
... a1n
a22
... a2 n
...
...
...
an 2 ... ann
b1 

b2 
... 

bn 
 E as combinações lineares entre as equações são
feitas entre as linhas de coeficientes.
Exemplo com matriz
 2 3 1 0 


 1 1 4 3 
 1 8 1 1 




2
3
1 0 


5
7
0
3


2
2


19
1
 0 

1 

2
2


2

0


 0

1
7
2
128
0
10
3
5
2

0 

3 


62

5 
Exercício
  x1  3 x2  5 x3  2 x4  10
 x  9 x  8 x  4 x  15
 1
2
3
4

Solução: x1=-1,
x

x

2
x2=0, x3=1 e
2
4

x4=2
 2 x1  x2  x3  x4  3
Custo da eliminação Gaussiana
 Para eliminar o primeiro termo das n-1
equações de um sistema a n equação,
precisamos de n-1 divisões, (n-1)(n+1)
multiplicações e (n-1)(n+1) adições: 2n2+n-3.
Para eliminar osi ntermos ate a ultima equação
precisamos de  2i 2  i  3 operações, da ordem
i2
de 2n3/2.
 A resolução do sistema triangular necessita:
n divisões, n(n-1)/2 multiplicações e n(n-1)/2
adições.
Velocidade da resolução
 Uma das razões de escolher uma algoritmo
no lugar de um outro é em geral baseado
sobre a relação entre velocidade e precisão.
 No caso da resolução de sistemas lineares, a
formula de Cramer precisa de muito mais
operações que a eliminação Gaussiana.
Estratégia de pivoteamento
 Resolução do sistema seguinte usando
sucessivamente 0.004 e 0.423 como pivot e
calculando usando somente 4 algarismos
significativos:
0.004 x1  15.73x2  15.77
0.423x1  24.72 x2  20.49
 A solução do sistema e (10,1). Com 0.004
como pivot achamos (12.5,0.9994) e com
0.423 achamos (10,1).
Estratégia de pivoteamento
 No caso geral, para diminuir os erros de
arredondamento, é preferível usar como pivot
o maior coeficiente em valor absoluto da
variável a eliminar nas equações do sistema.
pivot ( xi )  max( aij )
j 1..n
Eliminação Gaussiana,
algoritmo
 n: numero de variáveis, m: matriz aumentada
 Eliminacao_gauss(n, m)

para i de 1 a n
para j de i a n, procure o coeficiente maior em valor
absolute: linha max
 troca a linha max com a linha i de m
 para j de i+1 a n, para k de i a n+1, subtrai
m[j][i]/m[i][i] de m[j][k]

Soluções particulares
 Certas situações precisam de determinar as
soluções de sistemas onde somente os termos
constantes (bi) mudam:
 a11 x1  a12 x2  ....  a1n xn  b1

............................................
 a x  a x  ....  a x  b
nn n
n
 n1 1 n 2 2

solução de:

e solução de: a11 x1  a12 x2  ....  a1n xn  b '1
............................................
a x  a x  ....  a x  b '
nn n
n
 n1 1 n 2 2
Soluções particulares
 Nesses casos, é mais eficiente de triangular o
sistema uma vez e resolve-lo com os diversos
valores dos termos constantes (bi). Nesse
caso uma segunda matriz é necessária para
calcular os termos constantes do sistema
triangular em fonções dos coeficientes de
origem.
Soluções particulares
 Nesse caso, a matriz coluna dos termos constantes é
considerada como o produto da matriz identidade como essa
matriz coluna. As transformações operadas pela
triangularização serão aplicadas à matriz identidade e não à
matriz coluna dos termos constantes.
 a11 ... a1n   x1   1 0 0   b1 

  
 
 ... ... ...   ...    0 1 0   ... 
a
 x  0 0 1b 
...
a
nn   n 
 n1

 n 
Matriz Inversa
 Se o processo de transformação do sistema
continua ate obter um sistema cuja matriz é a
matriz identidade, a matriz de transformação
dos termos constantes é a matriz inversa da
matriz do sistema inicial:
 1 0 0   x1 
 b1 

 

1 
 0 1 0   ...   A  ... 
0 0 1 x 
b 

 n 
 n
Exemplo
2

1

A
0

 1
1 0
0 1
1 1
0 0
0

1
1

3
 3 3 3 2 


5 6 2 4 
1

A 
 4 5 4 3 


 1 1 1 1 
Erros de aproximação
 Os erros de arredondamento têm um papel
importante na solução de sistemas de
equações lineares, principalmente por conto
do grande número de calculo a ser efetuados.
 A um efeito de “condensação pivotal” no
caso da eliminação gaussiana. Cada calculo
depende dos resultados anteriores.
Avaliação dos erros
 Uma forma de avaliar o erro é trocar as
variáveis nas equações pelos valores
determinados e comparar os resultados com
os termos constantes:
3 x1  4 x2  7
Sistema: 
5 x1  2 x2  3
 x1  0.999
soluções: 
 x1  1.002
Trocando nas equações: 3(0.999)  4(1.002)  7.005

5(0.999)  2(1.002)  2.991
Avaliação dos erros
 Um pequeno erro sobre os resultados conduz
a considerar que os valores das variáveis
determinados são boas aproximações dos
resultados exatos.
 Existem casos nos quais não podemos
afirmar isso.
Sistema mal condicionado
 Considerando o sistema seguinte:
 x1  x2  2

1.0001x1  x2  2.007
 Uma solução como x1=100, x2=-98 é uma
solução aceitável do ponto de vista do
critério precedente, porém ela é longe da
solução exata (70,-68).
Sistema mal condicionado
 Um sistema de equações que pode ser satisfeito por
soluções erradas é um sistema mal condicionado.
Do ponto de vista gráfico, no
caso da dimensão 2, o sistema
é mal condicionado quando as
duas retas representando as
equações são próximas:
Sistema mal condicionado
 Um sistema é mal condicionado quando seu
determinante é próximo de zero.
 O que significa, um determinante próximo de
zero ? Como multiplicando qualquer equação
por um fator não muda a solução do sistema,
enquanto multiplica o determinante por esse
fator, falar de um valor pequeno do
determinante não significa nada.
Sistema mal condicionado
 Para determinar se um sistema é mal
condicionado, existem duas possibilidades:


O determinante normalizado é próximo de 0: cada
linha é dividida por um fator de proporcionalidade,
1
raiz quadrada da soma dos
n
2


2
quadrados dos coeficientes da linha. k 
a
  ij 
i
 j 1

Se uma pequena mudança de um termo constante do
sistema provoca uma uma mudança importante no
resultado, o sistema é mal condicionado.
Método iterativo de
Gauss-Seidel
 O sistema é transformado de tal forma que cada equação
pode dar o valor de uma variável (no caso que um dos aii é
nulo, o sistema pode ser reordenado para ter a condição: aii,
i={1,...,n}):
1

x1 
(b1  a12 x2  ....  a1n xn )

a11
 a11 x1  a12 x2  ....  a1n xn  b1


 ............................................   ............................................
a x  a x  ....  a x  b

1
nn n
n
 n1 1 n 2 2
 xn 
(bn  an1 x1  ....  ann 1 xn1 )
ann

Método iterativo de
Gauss-Seidel
 Em seguida, a cada passo e a partir de valor
iniciais de (x2, ..., xn), novos valores de (x1,
..., xn) são calculados.
 Quando converge, esse processo pode exigir
muitas iterações para chegar a um resultado
razoável. Ele é aconselhado somente quando
o sistema é mal condicionado ou quando
muitos coeficientes do sistema são nulos
(convergência rápida)
Método iterativo de
Gauss-Seidel
 O algoritmo pode ser parado quando:


É atingido um número de iteração dado.
A diferencia entre dois valores sucessivas dos xi
é menor que um valor limito: e. Critério
particularmente delicado a manipular
(convergência muito lenta).
Método iterativo de
Gauss-Seidel
 Se o método não converge, ele pode ser
aplicado mudando a ordem das equações (ou
seja mudando as equações determinando
cada xn).
Existe um teorema que garante a
convergência: Se o termo da diagonal
aii   aij , i  1,..., n principal é maior em valor absoluta que a
j 1
soma dos valores absolutos dos outros
j i
n
termos da linha do coeficiente e que a
aii   a ji , i  1,..., n soma dos valores absolutos dos outros
j 1
termos da coluna do coeficiente, a
j i
convergência é garantida.
n