Métodos para Sistemas Lineares

Prévia do material em texto

MAT 012 versa˜o 2018.1 Prof. Rodrigo Lima
Me´todos para Sistemas Lineares
Na aula de hoje iniciaremos o estudo de me´todos para resolver sistemas de equac¸o˜es line-
ares. Tais me´todos se classificam em diretos e iterativos. Os me´todos diretos conseguem
encontrar a soluc¸a˜o exata de um sistema linear em um nu´mero finito de passos (supondo que
os ca´lculos envolvidos estejam livres de erros nume´ricos). Sa˜o exemplos de me´todos diretos:
regra de Cramer, eliminac¸a˜o gaussiana e fatorac¸a˜o LU. Ja´ os me´todos iterativos en-
contram uma aproximac¸a˜o para a soluc¸a˜o de um sistema satisfazendo um crite´rio de parada
espec´ıfico. Como exemplo, podemos citar os me´todos de Gauss-Jacobi e Gauss-Seidel. A
seguir, lembraremos alguns conceitos importantes da teoria de resoluc¸a˜o de sistemas lineares.
Introduc¸a˜o
Em nosso estudo consideraremos sistemas lineares com n equac¸o˜es e n varia´veis, isto e´,
a11x1 + a12x2 + . . .+ a1nxn = b1
a21x1 + a22x2 + . . .+ a2nxn = b2
...
...
an1x1 + an2x2 + . . .+ annxn = bn
, (1)
onde os nu´meros aij, com i = 1, . . . , n e j = 1, . . . , n sa˜o os coeficientes das equac¸o˜es lineares
e xi, com i = 1, . . . , n sa˜o as inco´gnitas (varia´veis). O conjunto de equac¸o˜es (1) e´ chamado
de sistema linear quadrado e pode ser reescrito em notac¸a˜o matricial como
Ax = b, (2)
onde A = [aij] e´ a matriz de coeficientes n× n, x e´ o vetor de varia´veis de tamanho n× 1 e
b e´ o termo independente de tamanho n× 1.
O sistema linear (2) possui soluc¸a˜o u´nica se, e somente se, qualquer uma das afirmac¸o˜es
abaixo for verificada:
(A1) a matriz de coeficientes A admite inversa, isto e´, AA−1 = A−1A = I, onde I e´ a matriz
identidade de ordem n,
(A2) o determinante de A e´ diferente de zero,
(A3) a u´nica soluc¸a˜o do sistema homogeˆneo Ax = 0 e´ x = 0 (soluc¸a˜o trivial).
E´ poss´ıvel mostrar que estas afirmac¸o˜es sa˜o equivalentes, ou seja, A1 implica em A2, A2
implica em A3 e, por fim, A3 implica em A1. Supondo A invert´ıvel, multiplicando ambos
os lados da equac¸a˜o (2) por A−1 e lembrando que A−1A = I, podemos escrever a soluc¸a˜o do
sistema como
x = A−1b. (3)
1
Isto sugere um algoritmo para a resoluc¸a˜o de sistemas lineares com matriz de coeficientes
invert´ıvel:
0: Dados: A invert´ıvel de tamanho n× n e b de tamanho n× 1.
1: Calcule a inversa de A.
2: Fac¸a x← A−1b, imprima x e pare o algoritmo.
3: Fim
Embora este algoritmo esteja correto sob o ponto de vista matema´tico, na˜o e´ conveniente
implementa´-lo em um computador devido ao ca´lculo da inversa de A requerido no passo 1.
Este ca´lculo demanda esforc¸o computacional e pode acarretar erros nume´ricos principalmente
se a matriz A for muito grande. O exemplo a seguir ilustra, de forma simplificada, o que
acontece com a soluc¸a˜o de um sistema linear quando utilizamos A−1.
Exemplo 1:
Resolva o sistema linear 1 × 1 dado por 7x = 21. (Fonte: Numerical Computing with
MATLAB - C. Moler, cap. 2 - pa´g. 1).
Resoluc¸a˜o: supondo que vamos utilizar o algoritmo descrito acima e computador com
precisa˜o finita, devemos primeiramente calcular a inversa da matriz A e, depois, efetuar o
produtoA−1b. ComoA = 7 e b = 21, temos queA−1b = (7−1)×21 = 0.142857×21 = 2.99997.
Notemos que a soluc¸a˜o obtida e´ diferente da soluc¸a˜o exata deste sistema (que e´ x = 3). Este
exemplo simples serve para nos alertar que nas aplicac¸o˜es reais onde e´ necessa´rio resolver
um sistema linear maior, devemos evitar o ca´lculo expl´ıcito de A−1 e propor outras maneiras
de resolver o sistema.
⇒ Informac¸a˜o: o livro citado neste exemplo esta´ dispon´ıvel gratuitamente no enderec¸o
https://www.mathworks.com/moler/chapters.html
Regra de Cramer
Uma alternativa para evitar o ca´lculo da inversa de A durante a resoluc¸a˜o de um sistema
linear Ax = b consiste em aplicar a Regra de Cramer. Esta regra esta´ resumida no
algoritmo abaixo:
0: Dados: A invert´ıvel de tamanho n× n e b de tamanho n× 1.
1: Fac¸a D ← det(A).
2: Para cada k = 1, 2, . . . , n:
3: construa a matriz Ak substituindo a k-e´sima coluna de A pelo vetor b,
2
4: fac¸a Dk ← det(Ak), xk ← Dk/D e volte ao passo 2.
5: Imprima x e pare o algoritmo.
6: Fim
Exemplo 2:
Resolva o sistema linear abaixo aplicando a regra de Cramer:
x1 + 4x2 − 2x3 = −3
−2x1 + 3x2 − 3x3 = 5
2x2 − 4x3 = 8
Resoluc¸a˜o: temos que A =
 1 4 −2−2 3 −3
0 2 −4
 e D = det(A) = −30.
� k = 1: A1 =
 −3 4 −25 3 −3
8 2 −4
, D1 = det(A1) = 30 e x1 = D1/D = −1.
� k = 2: A2 =
 1 −3 −2−2 5 −3
0 8 −4
, D2 = det(A2) = 60 e x2 = D2/D = −2.
� k = 3: A3 =
 1 4 −3−2 3 5
0 2 8
, D3 = det(A3) = 90 e x3 = D3/D = −3.
Portanto, a soluc¸a˜o procurada e´ x∗ =
 −1−2
−3
.
Para aplicar a regra de Cramer na resoluc¸a˜o de Ax = b na˜o precisamos utilizar A−1 em
nenhum momento. No entanto, precisamos calcular o determinante de n+1 matrizes quadra-
das para obter os valores das varia´veis xk. Considerando sistemas lineares de grande porte
(com muitas equac¸o˜es e varia´veis), a aplicac¸a˜o da regra de Cramer na˜o e´ aconselha´vel pois
o computador precisa calcular determinantes de matrizes gigantes e estes ca´lculos envolvem
muitas operac¸o˜es de soma, multiplicac¸a˜o e divisa˜o. De fato, o ca´lculo de um determinante
de ordem n envolve n! operac¸o˜es.
3
Me´todo da Eliminac¸a˜o Gaussiana
Seja Ax = b um sistema linear n × n com matriz de coeficientes invert´ıvel. O me´todo da
eliminac¸a˜o gaussiana consiste em transformar Ax = b em um novo sistema linear A˜x = b˜
com as seguintes caracter´ısticas:
� A˜x = b˜ possui a mesma soluc¸a˜o que o sistema inicial Ax = b,
� A˜ e´ triangular superior, ou seja, os elementos abaixo da diagonal principal de A˜ sa˜o
nulos.
Para resolver o sistema Ax = b atrave´s deste me´todo, devemos inicialmente construir a
matriz ampliada [A | b]. Em seguida, aplicamos nesta matriz uma sequeˆncia de operac¸o˜es
elementares ate´ obtermos a matriz [A˜ | b˜], onde A˜ e´ triangular superior. As operac¸o˜es
elementares sa˜o:
� alterac¸a˜o da ordem de linhas,
� multiplicac¸a˜o de uma linha por uma constante na˜o nula,
� substituic¸a˜o de uma linha i pela combinac¸a˜o linear dela pro´pria com outra linha k
qualquer multiplicada por um escalar na˜o nulo, isto e´, `i ← `i − α`k, com i 6= k.
Por fim, resolvemos o sistema triangular A˜x = b˜ cuja soluc¸a˜o e´ a mesma do sistema inicial.
Exemplo 3:
Resolva o sistema linear abaixo aplicando o me´todo da eliminac¸a˜o gaussiana.
−x1 + 4x2 − x3 = 2
4x1 + 2x2 + x3 = 4
3x1 − 3x2 + 4x3 = 0
Resoluc¸a˜o:
1. Montamos a matriz ampliada do sistema e zeramos os elementos da primeira coluna
abaixo de a11 = −1 (pivoˆ nesta etapa).−1 4 −1 24 2 1 4
3 −3 4 0
 ←−×4+
←−−−−
×3
+
∼
−1 4 −1 20 18 −3 12
0 9 1 6

2. Na matriz resultante, zeramos os elementos da segunda coluna abaixo de a22 (pivoˆ
nesta etapa):−1 4 −1 20 18 −3 12
0 9 1 6

←−
×(− 12)
+
∼
−1 4 −1 20 18 −3 12
0 0 5/2 0

4
3. Com a matriz ampliada resultante [A˜ | b˜], montamos o sistema final A˜x = b˜ que deve
ser resolvido de baixo para cima, pois e´ um sistema triangular superior:
−x1 + 4x2 − x3 = 2
18x2 − 3x3 = 12
5
2
x3 = 0
⇒
x3 = 0
x2 =
2
3
x1 =
2
3
Portanto, a soluc¸a˜o do sistema e´ o vetor x∗ =

2
3
2
3
0
.
Eliminac¸a˜o Gaussiana com Estrate´gia de Pivoteamento Parcial
Como vimos no exemplo anterior, os pivoˆs a11 = −1 e a22 = 18 sa˜o utilizados para zerar,
respectivamente, os elementos abaixo da primeira e segunda colunas da matriz ampliada
durante o processo de eliminac¸a˜o. Em um computador devemos evitar trabalhar com pivoˆs
muito pequenos para que o me´todo de eliminac¸a˜o gaussiana na˜o seja afetado por erros
nume´ricos. Sendo assim, para aplicar a estrate´gia de pivoteamento parcial, devemos fixar
como pivoˆ na etapa k o maiorelemento em mo´dulo que esta´ na coluna k na diagonal principal
ou abaixo dela, isto e´
pivoˆ = aik = max{|akk|, |ak+1k|, . . . , |an−1k|, |ank|}.
Apo´s selecionarmos o elemento aik devemos trocar as linhas i e k de posic¸a˜o para dar conti-
nuidade ao processo de eliminac¸a˜o.
Exemplo 4:
Resolva o sistema linear abaixo considerando quatro d´ıgitos significativos na representac¸a˜o
dos nu´meros e arredondamento ao desprezar o quinto d´ıgito. (Fonte: Me´todos Nume´ricos -
M. C. C. Cunha - Segunda Edic¸a˜o - Editora da Unicamp - pa´g. 37.){
0.004x1 + 15.73x2 = 15.77
0.423x1 − 24.72x2 = −20.49 (4)
Resoluc¸a˜o: se aplicarmos o me´todo da eliminac¸a˜o gaussiana sem a estrate´gia de pivo-
teamento parcial e eliminarmos x1 da segunda equac¸a˜o do sistema (4) obtemos:{
0.004x1 + 15.73x2 = 15.77
−1689x2 = −1688
cuja soluc¸a˜o e´ x1 = 12.50 e x2 = 0.9994. Mas a soluc¸a˜o exata deste sistema e´ x1 = 10.0
e x2 = 1.0. Por outro lado, aplicando a estrate´gia de pivoteamento parcial no sistema (4),
devemos trocar as linhas 1 e 2 de posic¸a˜o, ou seja,{
0.423x1 − 24.72x2 = −20.49
0.004x1 + 15.73x2 = 15.77
(5)
5
Assim, eliminando x1 da segunda equac¸a˜o em (5) teremos{
0.423x1 − 24.72x2 = −20.49
15.96x2 = 15.96
cuja soluc¸a˜o e´ x1 = 10.0 e x2 = 1.0. A seguir, resolveremos o mesmo sistema linear do Exem-
plo 3 pore´m, aplicaremos o me´todo da eliminac¸a˜o gaussiana com estrate´gia de pivoteamento
parcial.
Exemplo 5
Resolva o sistema linear abaixo aplicando o me´todo da eliminac¸a˜o gaussiana com estrate´gia
de pivoteamento parcial. 
−x1 + 4x2 − x3 = 2
4x1 + 2x2 + x3 = 4
3x1 − 3x2 + 4x3 = 0
Resoluc¸a˜o:
1. Na primeira coluna do sistema inicial o maior elemento em mo´dulo e´ a21 = 4. Enta˜o,
devemos trocar as linhas 1 e 2 de posic¸a˜o na matriz ampliada para iniciar o me´todo.−1 4 −1 24 2 1 4
3 −3 4 0
 ←−←− ∼
 4 2 1 4−1 4 −1 2
3 −3 4 0
 ←−×( 14 )+
←−−−−−
×(− 3
4
)
+
2. Na segunda etapa na˜o ha´ necessidade de realizar o pivoteamento parcial uma vez que
os elementos a22 = −9/2 e a32 = 9/2 sa˜o iguais em mo´dulo.4 2 1 40 9/2 −3/4 3
0 −9/2 13/4 −3

←−
×1
+
∼
4 2 1 40 9/2 −3/4 3
0 0 10/4 0

3. Assim, o sistema linear final que deve ser resolvido e´ dado por
4x1 + 2x2 + x3 = 4
9
2
x2 − 34x3 = 3
10
4
x3 = 0
⇒
x3 = 0
x2 =
2
3
x1 =
2
3
E a soluc¸a˜o e´ a mesma obtida antes, isto e´, x∗ =

2
3
2
3
0
.
6
Uso de softwares
Apresentamos a seguir duas maneiras de resolver um sistema linear Ax = b no software
Mathematica. Para ilustrar o uso dos comandos, utilizaremos o sistema linear resolvido
no Exemplo 3. A Figura 1 abaixo mostra como resolver o sistema utilizando o comando
LinearSolve[ ]. Declaramos a matriz de coeficientes A e o termo independente b e, em
seguida, fornecemos estes dados para o comando.
������� � = {{-�� �� -�}� {�� �� �}� {�� -�� �}}�
� = {�� �� �}�
�����������[�� �]
�������  �� � �� � �
Figura 1: Usando LinearSolve[ ] para resolver um sistema linear.
Outra maneira de resolver o sistema e´ utilizando o comando Solve[ ]. Neste caso escre-
vemos cada uma das equac¸o˜es dentro de chaves com dois s´ımbolos de igual (=). As equac¸o˜es
devem vir separadas por v´ırgulas e devemos tambe´m explicitar quais sa˜o as varia´veis envol-
vidas. A Figura 2 a seguir ilustra este procedimento.
�������
�����[{-�� + � �� - �� ⩵ �� � �� + � �� + �� ⩵ �� � �� - � �� + � �� ⩵ �}�{��� ��� ��}]
������� �� → �� � �� → �� � �� → �
Figura 2: O comando Solve[ ] tambe´m resolve sistemas lineares.
⇒ Importante: o software e´ sens´ıvel aos tipos de dados de entrada que sa˜o fornecidos
aos comandos. Por exemplo, se na declarac¸a˜o da matriz A fizermos a11 = −1.0 ao inve´s
de a11 = −1 e utilizarmos LinearSolve[ ] para resolver Ax = b, o Mathematica dara´
como resposta a soluc¸a˜o {0.666667, 0.666667, 0}, que e´ uma aproximac¸a˜o para {2
3
, 2
3
, 0}. Isso
acontece porque algoritmos de resoluc¸a˜o diferentes sa˜o utilizados dependendo dos tipos de
nu´meros fornecidos como dados de entrada.
7
Algoritmos e Complexidade Computacional
O algoritmo abaixo transforma a matriz ampliada [A | b] na matriz [A˜ | b˜] levando em
considerac¸a˜o a estrate´gia de pivoteamento parcial.
0: Dados: A invert´ıvel e b.
1: Para k = 1 : (n− 1) fac¸a:
2: w ← |akk|
3: Para j = k : n fac¸a
4: Se |akj| > w: w ← |akj| e r ← j.
5: Trocar as linhas k e r.
6: Para i : (k + 1) : n fac¸a
7: m← aik/akk
8: bi ← bi −mbk
9: Para j = (k + 1) : n fac¸a
10: aij ← aij −makj
11: Fim
Uma vez obtido o sistema triangular A˜x = b˜, podemos resolveˆ-lo pelo seguinte algoritmo:
0: Dados: A˜ triangular superior, invert´ıvel e b˜.
1: Fac¸a xn ← b˜n/a˜nn e soma← 0.
2: Para k = (n− 1) : 1 fac¸a
3: soma← b˜k
4: Para j = (k + 1) : n fac¸a
5: soma← soma− a˜kjxj
6: xk ← soma/a˜kk
7: Fim
E´ poss´ıvel demonstrar que o nu´mero de operac¸o˜es (adic¸o˜es, multiplicac¸o˜es e diviso˜es) reali-
zadas para resolver um sistema linear Ax = b utilizando os dois algoritmos descritos acima
(fase de eliminac¸a˜o e fase de resoluc¸a˜o do sistema triangular) e´ da ordem de n3, onde n e´ o
tamanho da matriz de coeficientes A.
8
Exerc´ıcios
1. Resolva o sistema linear abaixo aplicando eliminac¸a˜o gaussiana sem estrate´gia de pi-
voteamento parcial: 
4x1 + x2 + 2x3 = 9
2x1 + 4x2 − x3 = −5
x1 + x2 − 3x3 = 9
2. Resolva o sistema linear abaixo utilizando eliminac¸a˜o gaussiana com estrate´gia de
pivoteamento parcial: 
2x1 + 3x2 − x3 = 5
4x1 + 6x2 + 3x3 = 25
5x1 − 4x2 − 3x3 = −12
3. Sabe-se que uma alimentac¸a˜o dia´ria equilibrada em vitaminas deve conter 170 unidades
(u) de vitamina A, 180 u de vitamina B, 140 u de vitamina C, 180 u de vitamina D
e 350 u de vitamina E. Com o objetivo de descobrir como devera´ ser uma refeic¸a˜o
equilibrada, foram estudados 5 alimentos. Fixada a mesma quantidade (1g) de cada
alimento, a quantidade de vitaminas (em unidades u) presente em cada amostra esta´
indicada na tabela abaixo:
Alim./Vit. A B C D E
1 1 10 1 2 2
2 9 1 0 1 1
3 2 2 5 1 2
4 1 1 1 2 13
5 1 1 1 9 2
Quantos gramas de cada um dos alimentos devemos ingerir diariamente para que nossa
alimentac¸a˜o seja equilibrada? Formule este problema como um sistema linear Ax = b
e o resolva no software Mathematica.
4. Sejam A =
 1 2 34 5 6
7 8 9
 e b =
 13
5
.
a) Calcule o determinante de A. Esta matriz admite inversa? Justifique.
b) Mostre que o sistema linear Ax = b possui infinitas soluc¸o˜es. Descreva o conjunto
de soluc¸o˜es desse sistema.
c) Suponha que o me´todo de eliminac¸a˜o gaussiana (sem estrate´gia de pivoteamento
parcial) seja utilizado para resolver Ax = b usando aritme´tica exata. Como o
sistema admite infinitas soluc¸o˜es, na˜o podemos esperar que uma soluc¸a˜o particular
seja obtida. Descreva o que acontece.
9
d) Utilize o comando LinearSolve[ ] do Mathematica para resolver Ax = b de duas
formas: (1) A e b devem ser declarados com entradas inteiras; (2) pelo menos
uma entrada de A deve ser declarada com uma casa decimal apo´s a v´ırgula, por
exemplo, a11 = 1.0. As respostas obtidas pelo comando sa˜o iguais? Justifique o
comportamento observado.
e) Utilize o comando Solve[ ] do Mathematica para resolver Ax = b, onde A e b
devem ser declarados com entradas inteiras. A resposta obtida e´ a mesma do item
d)? Justifique.
5. Considere o sistema Ax = b, onde A e´ uma matriz n× n tridiagonal (ou seja, aij = 0,
se |i− j| > 1.) Proponha um algoritmo que resolve este tipo de sistema utilizando eli-
minac¸a˜o gaussiana sem estrate´gia de pivoteamento parcial. Quantas operac¸o˜es realiza
seu algoritmo?
6. Considerando o algoritmo da regra de Cramer, qual e´ o comportamento do sistema
linear Ax = b nas situac¸o˜es descritas abaixo? Justifique!
a) D = 0 e Dk = 0, para todo k = 1, 2, . .. , n.
b) D = 0 e Di 6= 0 para algum i ∈ {1, 2, . . . , n}.
7. Sejam x, y vetores de tamanho n × 1 e W = xyT uma matriz n × n (note que yT e´ o
transposto do vetor y). Dado o vetor b de tamanho n×1, considere a tarefa de calcular
o produto matriz-vetor c = Wb.
a) Explique como calcular c realizando o menor nu´mero poss´ıvel de operac¸o˜es (somas,
multiplicac¸o˜es e diviso˜es).
b) Mostre que a matriz W na˜o admite inversa.
c) Quantas soluc¸o˜es possui o sistema linear homogeˆneo Wz = 0, onde z e´ o vetor de
varia´veis? Justifique.
8. Uma matriz A de ordem n e´ chamada anti-sime´trica se A + AT = 0, onde AT e´ a
transposta da matriz A.
a) Fornec¸a exemplos de matrizes anti-sime´tricas na˜o nulas de ordens 2 e 3.
b) Utilizando propriedades dos determinantes e a equac¸a˜o A + AT = 0, mostre que
matrizes anti-sime´tricas de ordem n na˜o admitem inversa se n for ı´mpar.
c) Quantas soluc¸o˜es possui o sistema linear Ax = 0, onde A e´ anti-sime´trica de
ordem 40? Justifique.
9. Uma matriz quadrada A de ordem n e´ chamada totalmente unimodular se toda sub-
matriz quadrada de A possui determinante 0, +1 ou −1.
a) Fornec¸a um exemplo de uma matriz totalmente unimodular.
10
b) Fornec¸a um exemplo de uma matriz formada apenas por 0, +1 ou −1 que na˜o e´
totalmente unimodular.
c) Seja Ax = b um sistema linear onde A e´ totalmente unimodular e invert´ıvel e b
e´ um vetor com entradas inteiras, isto e´ bi ∈ Z para todo i = 1, 2, . . . , n. Mostre
que a soluc¸a˜o do sistema linear Ax = b e´ um vetor de entradas inteiras, ou seja,
x∗i ∈ Z para todo i = 1, 2, . . . , n. (Dica: utilize a regra de Cramer.)
10. Considere o problema de resolver o sistema Ax = b pelo me´todo da eliminac¸a˜o gaus-
siana com estrate´gia de pivoteamento parcial. Se M = max
i,j
{|aij|}, 1 ≤ i, j ≤ n,
verifique se a afirmac¸a˜o a seguir e´ verdadeira ou falsa e justifique: apo´s a primeira
etapa do me´todo todos os elementos da matriz transformada na˜o excedem 2M .
11