Sistemas lineares

Prévia do material em texto

Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistemas lineares
Ricardo Biloti
biloti@g.unicamp.br
Ca´lculo Nume´rico – UNICAMP
2S/2018
http://goo.gl/7DZpR
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Licenc¸a
Este trabalho e´ licenciado sob os termos da Licenc¸a Internacional
Creative Commons Atribuic¸a˜o-Na˜oComercial-CompartilhaIgual 4.0.
Para ver uma co´pia desta licenc¸a, visite
http://creativecommons.org/licenses/by-nc-sa/4.0/.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Seus direitos e deveres sa˜o:
• Voceˆ e´ livre para copiar e redistribuir este material, em qualquer meio ou formato,
para adapta´-lo, transforma´-lo ou utiliza´-lo para construir seu pro´prio material.
• Voceˆ deve dar os cre´ditos apropriados, fornecendo link para a licenc¸a e indicando se
alterac¸o˜es foram feitas. Voceˆ pode fazer isto de qualquer forma razoa´vel, pore´m sem
tentar passar a ideia ou sugerir que o autor endosse suas alterac¸o˜es ou seu uso do
material.
• Voceˆ na˜o pode utilizar este material para fins comerciais.
• Se voceˆ alterar, transformar ou construir seu pro´prio material com base neste
trabalho, voceˆ devera´ distribu´ı-lo sob a mesma licenc¸a usada no original.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistemas lineares
Considere A ∈ Rn×n e b ∈ Rn. Queremos x tal que
Ax = b
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Neste curso, tratamos apenas de sistemas lineares quadrados, ou seja, sistemas lineares nos
quais o nu´mero de equac¸o˜es e o nu´mero de inco´gnitas e´ o mesmo. Apesar disto, os me´todos
diretos que sera˜o vistos (eliminac¸a˜o de Gauss / decomposic¸a˜o LU) prestam-se tambe´m a
sistemas retangulares.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistemas lineares
Para que matrizes A e´ fa´cil resolver o sistema linear Ax = b?
I I , matriz identidade
I D, matriz diagonal
I T , matriz triangular
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Uma parte da dificuldade em resolver um sistema linear e´ determinada pela estrutura da
matriz de coeficientes. O caso mais trivial e´ o de um sistema linear com a matriz de
coeficientes sendo pro´pria matriz identidade.
Outra situac¸a˜o ainda muito simples se da´ quando a matriz de coeficientes e´ diagonal. Se
todas as entradas da diagonal forem na˜o-nulas, enta˜o xi = b/dii .
Entretanto e´ uma hipo´tese muito forte supor que a matriz A e´ diagonal.
Matrizes triangulares sa˜o um bom compromisso entre simplicidade e generalidade. Veremos
que muitas vezes e´ poss´ıvel converter um sistema linear em outro equivalente cuja matriz
seja triangular. Ale´m disso, resolver sistemas lineares triangulares e´ bem simples.
Por sistemas lineares equivalentes queremos dizer sistemas lineares que tenham exatamente
as mesmas soluc¸o˜es.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Como resolver um sistema triangular?

a11 x1 + a12 x2 + a13 x3 + a14 x4 = b1
a22 x2 + a23 x3 + a24 x4 = b2
a33 x3 + a34 x4 = b3
a44 x4 = b4
x4 = (b4)/a44
x3 = (b3 − a34 x4)/a33
x2 = (b2 − a23 x3 − a24 x4)/a22
x1 = (b1 − a12 x2 − a13 x3 − a14 x4)/a11
xk =
bk −
∑n
j=k+1 akj xj
akk
, k = n, n − 1, . . . , 1
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
A u´nica hipo´tese necessa´ria para poder garantir a existeˆncia de soluc¸a˜o de um sistema
triangular e´ que todos os elementos da diagonal, akk , sejam na˜o nulos. Isto e´ facilmente
constatado observando-se a expressa˜o geral para o elemento xk .
Entretanto, mesmo que um elemento da diagonal seja nulo, ainda pode acontecer do sistema
ter soluc¸a˜o. Imagine, por exemplo, o caso em que a u´ltima equac¸a˜o e´
0 · x4 = b4.
Nesse caso, x4 esta´ livre para assumir qualquer valor se b4 = 0, e na˜o ha´ soluc¸a˜o poss´ıvel se
b4 6= 0.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Algoritmo
Se akk 6= 0, k = 1, 2, . . . , n:
xk =
bk −
∑n
j=k+1 akj xj
akk
, k = n, n − 1, . . . , 1
I xn ← bn/ann
I Para k = (n − 1), (n − 2), . . . , 1:
I soma ← bk
I Para j = (k + 1), (k + 2), . . . , n:
I soma ← soma −akj xj
I xk ← soma /akk
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O custo de algoritmos para resoluc¸a˜o de sistemas lineares e´ tradicionalmente medido
contando-se quantas operac¸o˜es de ponto flutuante sa˜o realizadas.
I xn ← bn/ann 1
I Para k = (n − 1), (n − 2), . . . , 1: ∑n−1k=1
I soma ← bk
I Para j = (k + 1), (k + 2), . . . , n:
∑n
j=k+1
I soma ← soma −akj xj 2
I xk ← soma /akk 1
Custo total:
1 +
n−1∑
k=1
 n∑
j=k+1
2
+ 1
 = 1 + n−1∑
k=1
[2(n − k) + 1]
= 1 + (2n + 1)(n − 1)− 2
n−1∑
k=1
k
= 1 + 2n2 − n − 1− 2n(n − 1)
2
= n2
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exerc´ıcio
Para contar o nu´mero de operac¸o˜es de algoritmos e´ necessa´rio
conhecer algumas identidades.
Demonstre que:
n∑
k=1
1 = n
n∑
k=1
k =
n(n + 1)
2
n∑
k=1
k2 =
n(n + 1/2)(n + 1)
3
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Na verdade, na˜o e´ necessa´rio contar exatamente o nu´mero de operac¸o˜es que um algoritmo
realiza, mas apenas ter uma boa estimativa. Para tanto, basta determinar corretamente o
termo de maior ordem e o coeficiente desse termo.
Uma te´cnica simples que presta-se a fornecer esta estimativa e´ aproximar as somas por
integrais.
n∑
k=1
1 ≈
∫ n
0
1 dk = n
n∑
k=1
k ≈
∫ n
0
k dk =
1
2
k2
∣∣∣∣n
0
=
1
2
n2
n∑
k=1
k2 ≈
∫ n
0
k2 dk =
1
3
k3
∣∣∣∣n
0
=
1
3
n3
Observe que todas as estimativas acertaram exatamente o termo de maior ordem.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Operac¸o˜es elementares

2x1 + 3x2 + x3 + x4 = 2 (×3)
4x1 + 7x2 + 4x3 + 3x4 = 1
4x1 + 7x2 + 6x3 + 4x4 = 1
6x1 + 9x2 + 9x3 + 8x4 = 3
I Multiplicar uma equac¸a˜o por um escalar na˜o-nulo
I Intercambiar a posic¸a˜o de duas equac¸o˜es
I Somar/Subtrair uma equac¸a˜o a` outra
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Operac¸o˜es elementares sa˜o operac¸o˜es que podem ser realizadas com as equac¸o˜es de um
sistema linear sem alterar seu conjunto soluc¸a˜o. Ou seja, apesar de alterar as equac¸o˜es do
sistema linear, o sistema alterado continua tendo as mesmas soluc¸o˜es do sistema original, e
nenhuma outra.
A primeira operac¸a˜o elementar e´ multiplicar uma das equac¸o˜es do sistema linear por uma
constante na˜o nula. Claramente, a igualdade e´ preservada.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Operac¸o˜es elementares

2x1 + 3x2 + x3 + x4 = 2
4x1 + 7x2 + 4x3 + 3x4 = 1
6x1 + 9x2 + 9x3 + 8x4 = 3
4x1 + 7x2 + 6x3 + 4x4 = 1
I Multiplicar uma equac¸a˜o por um escalar na˜o-nulo
I Intercambiar a posic¸a˜o de duas equac¸o˜es
I Somar/Subtrair uma equac¸a˜o a` outra
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Trocar a ordem das equac¸o˜es de um sistema linear tambe´m na˜o altera suas soluc¸o˜es.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Operac¸o˜es elementares

2x1 + 3x2 + x3 + x4 = 2
4x1 + 7x2 + 4x3 + 3x4 = 1
6x1 + 9x2 + 9x3 + 8x4 = 3
4x1 + 7x2 + 6x3 + 4x4 = 1
I Multiplicar uma equac¸a˜o por um escalar na˜o-nulo
I Intercambiar a posic¸a˜o de duas equac¸o˜es
I Somar/Subtrair uma equac¸a˜o a` outra
http://goo.gl/7DZpR Ricardo Biloti Sistemas linearesPor fim, somar ou subtrair uma equac¸a˜o de outra tambe´m na˜o alterar as soluc¸o˜es do sistemas,
visto que ao fazer isso, na verdade, esta´ se somando/subtraindo uma constante nos dois lados
de uma equac¸a˜o.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Operac¸o˜es elementares

2x1 + 3x2 + x3 + x4 = 2
4x1 + 7x2 + 4x3 + 3x4 = 1
6x1 + 9x2 + 9x3 + 8x4 = 3
2x1 + 2x2 + 3x3 + 4x4 = 2 ← `3 − `4
I Multiplicar uma equac¸a˜o por um escalar na˜o-nulo
I Intercambiar a posic¸a˜o de duas equac¸o˜es
I Somar/Subtrair uma equac¸a˜o a` outra
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Por fim, somar ou subtrair uma equac¸a˜o de outra tambe´m na˜o alterar as soluc¸o˜es do sistemas,
visto que ao fazer isso, na verdade, esta´ se somando/subtraindo uma constante nos dois lados
de uma equac¸a˜o.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
Ax = b

2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 x =

3
6
4
3

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Nesse exemplo, vamos utilizar as operac¸o˜es elementares para transformar o sistema linear
em outro sistema linear, equivalente ao original, mais simples.
Por sistemas lineares equivalentes, queremos dizer sistemas lineares com o mesmo conjunto
soluc¸a˜o.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
− 2`1 + `2
− 2`1 + `3
− 3`1 + `4

2 3 1 1
... 3
4 7 4 3
... 6
4 7 6 4
... 4
6 9 9 8
... 3
 ∼

2 3 1 1
... 3
0 1 2 1
... 0
0 1 4 2
... −2
0 0 6 5
... −6

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Ao inve´s de manipular as equac¸o˜es do sistema, e´ mais conveniente trabalhar apenas com
os coeficientes e com o termo independente. Para isso, operamos na matriz extendida ou
aumentada do sistema, que e´ a matriz de coeficientes acrescida de uma coluna contendo o
vetor b do sistema linear.
Atrave´s de operac¸o˜es elementares, vamos transformar a matriz de coeficientes do sistema
linear em uma matriz triangular superior, pois ja´ vimos que sistemas com essa estrutura sa˜o
simples de serem resolvidos.
Por uma questa˜o de organizac¸a˜o e metodologia, vamos tentar introduzir “zeros” na ma-
triz, nas posic¸o˜es abaixo da diagonal principal, de cima para baixo e da esquerda para a direita.
Esquematicamente, cada a i-e´sima linha da matriz e´ representada por `i . Para zerar os
elementos da primeira coluna, abaixo do elemento na diagonal, utilizando a terceira operac¸a˜o
elementar descrita anteriormente. Por exemplo, para introduzir um zero na posic¸a˜o (2, 1) da
matriz, somamos a` linha 2, um mu´ltiplo apropriado da linha 1. Com efeito, `2 ← −2`1 + `2.
O mesmo e´ feito com as linhas 3 e 4, atrave´s das operac¸o˜es `3 ← −2`1 +`3 e `4 ← −3`1 +`4.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
`2
− 1`2 + `3
− 0`2 + `4

2 3 1 1
... 3
0 1 2 1
... 0
0 1 4 2
... −2
0 0 6 5
... −6
 ∼

2 3 1 1
... 3
0 1 2 1
... 0
0 0 2 1
... −2
0 0 6 5
... −6

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Para introduzir “zeros” nas posic¸o˜es (3, 2) e (4, 2) vamos utilizar mu´ltiplos da linhas 2.
Veja que se continua´ssemos utilizando mu´ltiplos da linha 1, “estragar´ıamos” os zeros ja´
introduzidos na primeira coluna.
Por uma eventualidade, alguns diriam ate´ mesmo sorte, o elemento (4, 2) ja´ e´ zero.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
`2
`3
− 3`3 + `4

2 3 1 1
... 3
0 1 2 1
... 0
0 0 2 1
... −2
0 0 6 5
... −6
 ∼

2 3 1 1
... 3
0 1 2 1
... 0
0 0 2 1
... −2
0 0 0 2
... 0

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Resta zerar o coeficiente (4, 3), o que e´ feito com a operac¸a˜o `4 ← −3`3 + `4.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistema triangular superior

2 3 1 1
... 3
0 1 2 1
... 0
0 0 2 1
... −2
0 0 0 2
... 0


2x1 + 3x2 + x3 + x4 = 3
x2 + 2x3 + x4 = 0
2x3 + x4 = −2
2x4 = 0
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O sistema linear representado por essa matriz aumentada pode ser novamente escrito na
forma usual. A resoluc¸a˜o deste sistema e´ simples, realizada atrave´s do algoritmo ja´ discutido
para sistemas lineares triangulares superiores.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
A =

2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Durante o processo de eliminac¸a˜o gaussiana para simplificar o sistema linear Ax = b,
operamos na matriz aumentada do sistema, [A|b]. Todas as operac¸o˜es realizadas alteram
tanto as entradas da matriz A quanto do vetor b. Entretanto, se voceˆ olhar com atenc¸a˜o o
exemplo apresentado, vai reparar que apenas as entradas da matriz A foram determinantes
na definic¸a˜o de cada operac¸a˜o. O vetor b, mesmo tendo sido alterado, em nenhum momento
foi decisivo para a escolha da operac¸a˜o elementar a ser aplicada na matriz aumentada.
Essa constatac¸a˜o nos motiva a postergar a manipulac¸a˜o do vetor b. A raza˜o para isso ficara´
evidente mais a frente.
Vamos realizar as mesmas operac¸o˜es utilizadas no processo de escalonamento, pore´m sem
considerar o vetor b, tomando o cuidado de guardar as operac¸o˜es realizadas na matriz A, para
que possam ser posteriormente aplicadas tambe´m ao vetor b.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
−2`1 + `2
−2`1 + `3
−3`1 + `4

2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 =

2 3 1 1
0 1 2 1
0 1 4 2
0 0 6 5

L1A =

1 0 0 0
−2 1 0 0
−2 0 1 0
−3 0 0 1


2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 =

2 3 1 1
0 1 2 1
0 1 4 2
0 0 6 5

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Ja´ vimos quais sa˜o as operac¸o˜es que devem ser feitas para introduzir zeros na primeira
coluna de A, abaixo da diagonal. A questa˜o principal aqui e´ como guardar o histo´rico dessas
operac¸o˜es, de maneira que elas possam ser reaplicadas ao vetor b.
Uma forma de salvar as operac¸o˜es elementares e´ perceber que o resultado produzido por elas
pode ser obtido atrave´s de um produto matricial.
Observe que o produto da matriz L1 pela matriz A produz exatamente o mesmo efeito de
treˆs operac¸o˜es elementares utilizadas no exemplo. Perceba tambe´m que a matriz L1 tem
uma estrutura peculiar. Ela e´ triangular inferior, com os elementos da diagonal todos iguais
a 1. Ale´m disso cada multiplicador computado durante o processo de eliminac¸a˜o, adequado
para zerar o elemento na linha i da primeira coluna, foi armazenado na matriz L1 exatamente
naquela mesma posic¸a˜o.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
`2
−1`2 + `3
−0`2 + `4

2 3 1 1
0 1 2 1
0 1 4 2
0 0 6 5
 =

2 3 1 1
0 1 2 1
0 0 2 1
0 0 6 5

L2L1A =

1 0 0 0
0 1 0 0
0 −1 1 0
0 −0 0 1


2 3 1 1
0 1 2 1
0 1 4 2
0 0 6 5
 =

2 3 1 1
0 1 2 1
0 0 2 1
0 0 6 5

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Para zerar os dois elementos abaixo da diagonal na segunda coluna, podemos tambe´m realizar
um produto matricial que tem o mesmo efeito das duas operac¸o˜es elementares necessa´rias
(nesse exemplo, por sorte, de fato,apenas uma e´ necessa´ria). Essa matriz, L2 e´ multiplicada
por L1A (que representa o estado parcial da matriz A depois do primeiro passo do processo
de eliminac¸a˜o).
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
`1
`2
`3
−3`3 + `4

2 3 1 1
0 1 2 1
0 0 2 1
0 0 6 5
 =

2 3 1 1
0 1 2 1
0 0 2 1
0 0 0 2

L3L2L1A =

1 0 0 0
0 1 0 0
0 0 1 0
0 0 −3 1


2 3 1 1
0 1 2 1
0 0 2 1
0 0 6 5
 =

2 3 1 1
0 1 2 1
0 0 2 1
0 0 0 2

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Por fim, a u´ltima operac¸a˜o elementar necessa´ria para tornar a matriz A em triangular superior
pode ser computada pelo produto L3(L2L1A).
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Escalonamento
L3L2L1A =

2 3 1 1
0 1 2 1
0 0 2 1
0 0 0 2
 = U
A = (L3L2L1)
−1U = (L−11 L
−1
2 L
−1
3 )U
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
A matriz triangular superior obtida, denotada por U, fica expressa como U = L3L2L1A.
Como as matrizes Lj sa˜o todas na˜o singulares (Por queˆ?), podemos escrever A em func¸a˜o de
L1, L2, L3 e U.
Resta saber como computar L−1j .
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Invertendo Lj
L1 =

1
−2 1
−2 1
−3 1
 L−11 =

1
2 1
2 1
3 1

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Em geral, computar a inversa de uma matriz e´ bem mais caro que resolver um sistema linear.
Mas para nossa sorte, as matrizes Lj teˆm uma estrutura especial.
Se multiplicar por Lj tem o resultado de realizar algumas operac¸o˜es elementares, multiplicar
por L−1j tem que desfazer essas operac¸o˜es elementares, visto que L
−1
j Lj = I .
Por exemplo, se `2 representa a segunda linha da matriz A e ˜`2 representa a segunda linha,
apo´s a operac¸a˜o elementar, enta˜o
˜`
2 = `2 − 2`1,
que na matriz L1 corresponde a` linha [−2 1 0 0]. A operac¸a˜o inversa e´
`2 = ˜`2 + 2`1,
que corresponderia a` linha [2 1 0 0].
Assim, L−11 e´ obtida apenas trocando-se o sinal dos elementos abaixo da diagonal de L1.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Calculando L−11 L
−1
2 L
−1
3

1
2 1
2 1
3 1


1
1
1 1
0 1


1
1
1
3 1


1
2 1
2 1
3 1


1
1
1 1
0 3 1


1
2 1
2 1 1
3 0 3 1

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Nosso u´ltimo golpe de sorte e´ perceber que o produto de todas as matrizes L−1j e´ tambe´m
uma matriz triangular inferior com diagonal unita´ria, contendo todos os multiplicadores
computados durante o processo de eliminac¸a˜o, em suas respectivas posic¸o˜es.
Essa matriz final e´ denotada por L.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Decomposic¸a˜o LU
A =

2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 =

1
2 1
2 1 1
3 0 3 1


2 3 1 1
1 2 1
2 1
2
 = LU
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
A decomposic¸a˜o LU consite enta˜o de uma fatorac¸a˜o da matriz A em um produto de duas
matrizes, uma triangular inferior com diagonal unita´ria e outra triangular superior.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Algoritmo
I U ← A, L← I
I Para j = 1, 2, . . . , n − 1
I Para i = j + 1, . . . , n
I lij ← uij/ujj , se ujj 6= 0
I uij ← 0
I Para k = j + 1, . . . , n
I ui ,k ← ui ,k − lijuj ,k
Nu´mero de operac¸o˜es:
n−1∑
j=1
n∑
i=j+1
[1 + 2(n − j)] ≈ 2
3
n3 flops
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
FLOPS (FLoating-Point operations per Second) e´ a quantidade de operac¸o˜es de ponto
flutuante que seu computador pode, em tese, realizar por segundo.
Essa medida e´ computada por GFLOPS = v × np × nc × oc, onde GFLOPS sa˜o bilho˜es de
operac¸o˜es por segundo, v e´ a velocidade da CPU em GHz, np e´ o nu´mero de CPU’s, nc e´
o nu´mero de cores (nu´cleos) por CPU e oc e´ a quantidade de operac¸o˜es de ponto fluante
capazes de serem feitas por ciclo (4 em geral).
Por exemplo, um processor Intel Core i7 3.6 GHz e 4 nu´cleos, executaria, em tese, 57 GFLOPS
ou 57 bilho˜es de operac¸o˜es de ponto flutuante por segundo.
Dessa forma, uma matriz quadrada de ordem n = 5.000, precisa ao redor de 83 bilho˜es
de operac¸o˜es e portanto teria sua decomposic¸a˜o LU computada em aproximadamente 1.4
segundos, isto se todos os nu´cleos fossem utilizados. Em um algoritmo sequeˆncial, onde
apenas um nu´cleo e´ utilizado, esse tempo subiria para algo em torno de 5.8 segundos. Os dois
sistemas lineares triangulares seriam resolvidos em aproximadamente 3.5 milisegundos. Ja´
uma matriz quadrada de ordem n = 20.000 levaria aproximadamente 6.24 minutos para ser
decomposta em LU e os sistemas lineares triangulares seriam resolvidos em 56 milisegundos.
Na pra´tica, os tempos sa˜o maiores, pois ha´ restric¸o˜es de acesso a` memo´ria, tempo gasto para
trazer os dados da memo´ria para dentro do processador, tempo de acesso a disco (caso os
dados sejam grandes demais), etc.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Resoluc¸a˜o de sistemas lineares
Como resolver Ax = b, sabendo que A = LU?
Se Ax = b, como A = LU, temos que
LUx = b
Definindo y = Ux , obtemos dois sistemas triangulares{
Ly = b
Ux = y
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Utilizando a decomposic¸a˜o LU, o problema de resolver um sistema linear quadrado, sem
qualquer outra caracter´ıstica particular, e´ convertido no problema de resolver em sequeˆncia
dois sistemas lineares triangulares.
A vantagem disto, como ja´ vimos anteriormente, e´ que a resoluc¸a˜o de sistemas lineares
triangulares e´ simples e computacionalmente barata.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistemas triangulares
Seja L ∈ Rn×n e´ triangular inferior e b ∈ Rn
Ly = b
I Para i = 1, . . . , n
I yi ← 1
lii
bi − i−1∑
j=1
lijyj

Nu´mero de operac¸o˜es:
n∑
i=1
[2 + (i − 1) + (i − 2)] ≈ n2 flops
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Inicia-se pela resoluc¸a˜o do sistema linear triangular inferior, Ly = b, a um custo computacional
da ordem de n2 operac¸o˜es.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Sistemas triangulares
Seja U ∈ Rn×n e´ triangular superior e y ∈ Rn
Ux = y
Nu´mero de operac¸o˜es:
≈ n2 flops
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Computado o vetor y , resta resolver o sistema linear triangular superior, Ux = y , novamente
a um custo computacional da ordem de n2 operac¸o˜es.
Ao final, obtem-se o vetor x , soluc¸a˜o do sistema linear original.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Resoluc¸a˜o de sistema linear
Seja A ∈ Rn×n e b ∈ Rn, queremos x tal que Ax = b.
I Compute da decomposic¸a˜o LU de A
I Resolva Ly = b
I Resolva Ux = y
Nu´mero de operac¸o˜es:
≈ 2
3
n3 flops
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O algoritmo completo para a resoluc¸a˜o de um sistema linear quadrado, atrave´s da decom-
posic¸a˜o LU tem custo computacional da ordem de 2
3
n3 operac¸o˜es, uma vez que o custo
computacional da resoluc¸a˜o dos dois sistemas triangulares e´ desprez´ıvel em comparac¸a˜o com
o custo para decompor a matriz A nos fatores L e U.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos IterativosII
Desempenho da decomposic¸a˜o LU
10-4
10-3
10-2
10-1
1
10
 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
t(n) ≈ (7.70·10-9) · n2.26
Te
m
po
 [s
]
Ordem da matriz
Ajustado
Experimental
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
No gra´fico (em escala logar´ıtmica) e´ poss´ıvel ver como o tempo computacional cresce quando
a ordem da matriz aumenta. Para construir esse gra´fico, foram computadas no MATLAB
as decomposic¸o˜es LU de 100 matrizes aleato´rias, para cada ordem. O tempo exibido e´ o
tempo me´dio do ca´lculo dessas decomposic¸o˜es. Este experimento, foi conduzido em um
computador com 32 processadores. Tanto o MATLAB como o Octave conseguem fazer uso
de mais de um processador no ca´lculo da decomposic¸a˜o LU.
A curva em vermelho representa o ajuste dos tempos medidos a uma curva do tipo
t(n) = anb, onde n e´ a ordem da matriz, e a e b sa˜o constantes a determinar. O tempo na˜o
e´ exatamente proporcional ao nu´mero de operac¸o˜es, pois ha´ outro fatores envolvidos, como
movimentac¸a˜o de dados entre a memo´ria do computador e o processador. Mesmo assim, o
ajuste foi muito bom.
Na pra´tica, o desempenho foi melhor que o previsto (b = 2.26 < 3), pois de fato ha´
algoritmos mais eficientes que a versa˜o simples que apresentamos.
No to´pico de Ajuste de Curvas por Quadrados Mı´nimos e´ discutido como as constantes a e b
sa˜o computadas.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Decomposic¸a˜o LU
Teorema
Seja A uma matriz quadrada com todos os menores principais
na˜o-singulares. Enta˜o A pode ser fatorada de maneira u´nica no
produto
A = LU,
com L triangular inferior com diagonal unita´ria e U triangular
superior.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Do ponto de vista computacional, a resoluc¸a˜o de sistema lineares atrave´s do algoritmo
proposto, por meio da decomposic¸a˜o LU, parecer ser muito bom. Resta a pergunta se isso
sempre e´ poss´ıvel. Ou seja, sera´ que toda matriz pode ser decomposta em fatores L e U,
como descrito?
De fato, nem sempre isso e´ poss´ıvel. O teorema apresentado explicita qual a condic¸a˜o
necessa´ria para garantir a existeˆncia da decomposic¸a˜o LU.
Como devemos proceder na pra´tica, quando nos depararmos com um sistema linear para
resolver? Sera´ que devemos primeiro verificar se as hipo´teses do teorema sa˜o satisfeitas,
antes de tentar computar a decomposic¸a˜o LU?
Na verdade, tentar verificar se as hipo´teses do teorema sa˜o ou na˜o satisfeitas seria muito
mais caro do que tentar computar diretamente a decomposic¸a˜o LU. Sendo assim, aplica-se
diretamente o algoritmo para o ca´lculo dos fatores L e U. Se o algoritmo na˜o encontrar
empec´ılhos a` execuc¸a˜o e´ porque a matriz de fato tem decomposic¸a˜o LU.
Pergunta: mas o que poderia dar errado na ca´lculo da decomposic¸a˜o LU?
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo perverso
A matriz A =
[
0 1
1 1
]
na˜o tem decomposic¸a˜o LU. Entretanto
A =
[
10−20 1
1 1
]
=
[
1 0
1020 1
] [
10−20 1
0 1− 1020
]
= LU
Numericamente, como u ≈ 10−16, fl(1− 1020) = −1020. Logo,
A 6=
[
10−20 1
1 0
]
=
[
1 0
1020 1
] [
10−20 1
0 −1020
]
= LˆUˆ
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Este exemplo e´ para mostrar que mesmo quando a matriz tem decomposic¸a˜o LU, a qualidade
nume´rica dessa decomposic¸a˜o pode ser desastrosa.
Perceba que por um erro muito pequeno, a troca de (1− 1020) por −1020, o produto LU ja´
ficou muito diferente de A.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo perverso
[
10−20 1
1 1
]
x =
[
1
0
]
Usando LU, x ≈
[ −1
1
]
, e usando LˆUˆ, x =
[
0
1
]
.
Estabilidade
Apesar dos fatores LU terem sido calculados de maneira esta´vel, a
soluc¸a˜o do sistema linear utilizando LU na˜o foi esta´vel.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Quando se computam os fatores L e U, dificilmente sera´ computado o produto deles e
comparado com a matriz A original. O perigoso seria enta˜o tentar utilizar esses fatores na
resoluc¸a˜o do sistema linear. Veja que o resultado obtido seria completamente errado.
O problema com esse exemplo e´ que o pivoˆ, apesar de na˜o ser nulo, era muito pequeno.
Como no algoritmo dividi-se pelo pivoˆ, pivoˆs pequenos da˜o origem a multiplicadores muito
grandes e dai surge problemas de perda de d´ıgitos significativos.
A estrate´gia para circundar este tipo de problema e´ evitar ao ma´ximo pivoˆs pequenos.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Pivoteamento

× × × × ×
xkk × × ×
× × × ×
× × × ×
× × × ×
 −→

× × × × ×
xkk × × ×
0 × × ×
0 × × ×
0 × × ×

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Pivoteamento

× × × × ×
× × × ×
× × × ×
xik × × ×
× × × ×
 −→

× × × × ×
0 × × ×
0 × × ×
xik × × ×
0 × × ×

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Pivoteamento

× × × × ×
× × × ×
× × × ×
× xij × ×
× × × ×
 −→

× × × × ×
× 0 × ×
× 0 × ×
× xij × ×
× 0 × ×

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Pivoteamento parcial

× × × × ×
× × × ×
× × × ×
xik × × ×
× × × ×
 ↘ P2 |xik| = maxj |xjk|

× × × × ×
xik × × ×
× × × ×
× × × ×
× × × ×
 ↘ L2

× × × × ×
xik × × ×
0 × × ×
0 × × ×
0 × × ×

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
A =

2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo

1
1
1
1


2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 =

6 9 9 8
4 7 4 3
4 7 6 4
2 3 1 1

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo

1
−46 1
−46 1
−26 1


6 9 9 8
4 7 4 3
4 7 6 4
2 3 1 1
 =

6 9 9 8
0 1 −2 −73
0 1 0 −43
0 0 −2 −53

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo

1
1
−1 1
0 1


6 9 9 8
0 1 −2 −73
0 1 0 −43
0 0 −2 −53
 =

6 9 9 8
0 1 −2 −73
0 0 2 1
0 0 −2 −53

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo

1
1
1
1 1


6 9 9 8
0 1 −2 −73
0 0 2 1
0 0 −2 −53
 =

6 9 9 8
0 1 −2 −73
0 0 2 1
0 0 0 −23

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo

1
1
1
1


2 3 1 1
4 7 4 3
4 7 6 4
6 9 9 8
 =

14
6
1
4
6
1 1
2
6
0 −1 1


6 9 9 8
0 1 −2 − 7
3
0 0 2 1
0 0 0 − 2
3

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Decomposic¸a˜o LU com pivoteamento
Teorema
Qualquer matriz quadrada A, pode ser fatorada como
PA = LU,
com P uma permutac¸a˜o da matriz identidade, L uma matriz
triangular inferior com diagonal unita´ria com entradas com
magnitude na˜o maior que 1, e U uma matriz triangular superior.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Diferentemente do que acontece com a decomposic¸a˜o LU sem pivoteamento, a decomposic¸a˜o
LU com pivoteamento sempre existe.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Resoluc¸a˜o de sistemas lineares
Como resolver Ax = b, sabendo que PA = LU?
Se Ax = b, enta˜o PAx = Pb, como PA = LU, temos que
LUx = Pb
Definindo y = Ux , obtemos dois sistemas triangulares{
Ly = Pb
Ux = y
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Para poder utilizar a decomposic¸a˜o LU com pivoteamento, na resoluc¸a˜o de sistemas lineares,
basta multiplicar a esquerda os dois lados do sistema por P. Assim, no lugar de PA, usamos
LU.
Feito isso, novamente temos dois sistemas triangulares para resolver.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exerc´ıcios
Resolva o sistema linear abaixo atrave´s da decomposic¸a˜o LU com
pivoteamento. 2 3 46 1 5
4 2 2
 x =
−13−10
−4
 .
Encontre a decomposic¸a˜o LU com pivoteamento para2 1 46 1 5
4 2 2
 .
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exerc´ıcio
Resolva o sistema linear abaixo, com e sem pivoteamento, usando
apenas 4 d´ıgitos significativos. Compare seu resultado com a
soluc¸a˜o exata x1 = 10 e x2 = 1.
0.0003x1 + 1.566x2 = 1.569
0.3454x1 − 2.436x2 = 1.018
Poder´ıamos ter evitado o pivoteamento, apenas multiplicando a
primeira equac¸a˜o por 105? Isso resolveria o problema?
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Sem pivoteamento: Como o pivoˆ e´ 0.0003, o multiplicador usado no primeiro passo do
escalonamento e´ m = fl(0.3454/0.0003) = 1151. Com isso, na segunda linha, o primeiro
coeficiente e´ definido como zero (por construc¸a˜o), enquato que os outro dois coeficientes sa˜o
fl[−2.436−m(1.566)] = −1804,
fl[ 1.018−m(1.569)] = −1805.
Desta forma, x2 = fl[−1805/(−1804)] = 1.001. Assim x1 = fl[(1.569 − 1.566x2)/0.0003] =
3.333. Esse resultado esta´ longe de ser acurado.
Com pivoteamento: Trocando a primeira com a segunda linha, o pivoˆ e´ 0.3454. O multi-
plicador sera´ enta˜o m = fl(0.0003/0.3454) = 8.686e− 4. O resultado da eliminac¸a˜o aplicada
na (nova) segunda linha produzira´ os coeficientes
fl[1.566−m(−2.436)] = 1.568,
fl[1.569−m( 1.018)] = 1.568.
Desta forma, x2 = fl[1.568/1.568] = 1.000. Assim x1 = fl[(1.018 + 2.436x2)/0.3454] = 10.
Agora o resultado obtido foi bem acurado.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Tudo ou nada
Ja´ vimos que o custo computacional da resoluc¸a˜o de um sistema
linear e´ O( 23n3).
E se na˜o houver recursos suficientes? Por exemplo, se na˜o tiver...
I tempo,
I espac¸o,
I dinheiro?
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Tudo ou nada
Me´todos diretos
Caso seja poss´ıvel arcar com o custo total de um me´todo direto,
como eliminac¸a˜o do Gauss ou Decomposic¸a˜o LU, ao final de um
nu´mero finito de passo, a soluc¸a˜o e´ conhecida, a menos de erros
nume´ricos.
Me´todos iterativos
Me´todos iterativos obte´m aproximac¸o˜es sucessivas da soluc¸a˜o, cuja
qualidade e´ proporcional a` disponibilidade de recursos.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo pra´tico simples
{ −7.5x1 + 7.3x2 = −4.65
−2.8x1 + 9.0x2 = 49.80
{ −7.5x1 = −4.65− 7.3x2
9.0x2 = 49.80 + 2.8x1
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Considere o sistema linear { −7.5x1 + 7.3x2 = −4.65
−2.8x1 + 9.0x2 = 49.80
Repare que isolando a inco´gnita x1 na primeira equac¸a˜o e x2 na segunda, obter´ıamos duas
equac¸o˜es expl´ıcitas para x1 e x2, se soube´ssemos o valor de x2 na primeira equac¸a˜o e o de x1
na segunda. func¸a˜o desta aparoximac¸o˜es
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo pra´tico simples
{ −7.5x1 + 7.3x2 = −4.65
−2.8x1 + 9.0x2 = 49.80
 −7.5x
(k+1)
1 = −4.65− 7.3xk2
9.0x
(k+1)
2 = 49.80 + 2.8x
k
1
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Se tivermos uma aproximac¸a˜o para (x1, x2), digamos xk = (xk1 , x
k
2 ), enta˜o podemos construir
novas aproximac¸o˜es x(k+1) = (x
(k+1)
1 , x
(k+1)
2 ), utilizando estas equac¸o˜es expl´ıcitas.
Para facilitar a interpretac¸a˜o geome´trica deste me´todo, graficar a reta associada a` primeira
equac¸a˜o em vermelho e a reta associada a` segunda equac¸a˜o de azul.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo pra´tico simples
{ −7.5x1 + 7.3x2 = −4.65
−2.8x1 + 9.0x2 = 49.80
 x
(k+1)
1 = ( 4.65 + 7.3x
k
2 )/7.5
x
(k+1)
2 = (49.80 + 2.8x
k
1 )/9.0
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Se tivermos uma aproximac¸a˜o para (x1, x2), digamos xk = (xk1 , x
k
2 ), enta˜o podemos construir
novas aproximac¸o˜es x(k+1) = (x
(k+1)
1 , x
(k+1)
2 ), utilizando estas equac¸o˜es expl´ıcitas.
Para facilitar a interpretac¸a˜o geome´trica deste me´todo, graficar a reta associada a` primeira
equac¸a˜o em vermelho e a reta associada a` segunda equac¸a˜o de azul.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
 x
(k+1)
1 = ( 4.65 + 7.3x
k
2)/7.5
x
(k+1)
2 = (49.80 + 2.8x
k
1)/9.0
Seja xk a aproximac¸a˜o atual para a soluc¸a˜o do sistema linear (marcado com o ponto preto no
gra´fico). A soluc¸a˜o do sistema linear e´ facilmente identificada como o ponto de intersecc¸a˜o
das duas retas.
Determinar x
(k+1)
1 pela primeira equac¸a˜o e´ o mesmo que perguntar a coordenada x1 do
ponto da reta vermelha cuja coordenada x2 e´ a mesma do ponto xk .
Graficamente, x
(k+1)
1 e´ a abscissa do ponto de intersecc¸a˜o da reta vermelha com uma reta
paralela ao eixo x1 passando por xk .
Racioc´ınio ana´logo vale para a determinac¸a˜o de x
(k+1)
2 . Este sera´ o ponto de intersec¸a˜o da
reta azul com uma retar paralela ao eixo x2, passando por xk .
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O gra´fico acima exibe as primeiras sete iterac¸o˜es deste algoritmo.
Note a convergeˆncia para a soluc¸a˜o do sistema linear.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo pra´tico simples
{ −7.5x1 + 7.3x2 = −4.65
−2.8x1 + 9.0x2 = 49.80
{ −2.8x1 + 9.0x2 = 49.80
−7.5x1 + 7.3x2 = −4.65
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Repare que ambos os sitemas lineares sa˜o o mesmo, exceto pela troca da ordem das equac¸o˜es.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Jacobi
http://goo.gl/7DZpRRicardo Biloti Sistemas lineares
Vamos partir agora de um ponto bem mais pro´ximo da soluc¸a˜o do sistema.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Jacobi
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Vamos partir agora de um ponto bem mais pro´ximo da soluc¸a˜o do sistema.
Repetindo o processo anterior (x
(k+1)
1 definido pela intersecc¸a˜o de reta paralela ao eixo x1,
que passa por xk , e a reta vermelha, primeira equac¸a˜o, e x
(k+1)
2 definido pela intersecc¸a˜o de
reta paralela ao eixo x2, que passa por xk , e a reta azul, segunda equac¸a˜o), acabamos por
nos afastar da soluc¸a˜o do sistema linear.
Veja que a troca da ordem das equac¸o˜es resultou em divergeˆncia.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exerc´ıcio
Esboce graficamente o comportamento do me´todo de Jacobi nas
seguintes situac¸o˜es no plano:
I O sistema linear tem soluc¸a˜o e o me´todo converge lentamente.
I O sistema linear tem soluc¸a˜o e o me´todo diverge lentamente.
I O sistema linear na˜o tem soluc¸a˜o.
I O sistema linear tem infinitas soluc¸o˜es.
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exerc´ıcio
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Partindo do ponto marcado, realize algumas iterac¸o˜es do me´todo de Jacobi.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de Jacobi
I Fa´cil de construir
I Nem sempre converge
I Convergeˆncia depende da ordem das equac¸o˜es
I Mesmo quando converge, pode ser lento
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
As principais caracter´ıstica do me´todo de Jacobi (ou Gauss–Jacobi) sa˜o:
• Facilidade de construc¸a˜o. Basta utilizar a j-e´sima equac¸a˜o para determinar x(k+1)j a
partir de xk .
• Convergeˆncia na˜o assegurada para qualquer sistema linear. Precisamos ainda tentar
descobrir crite´rios que garantam a convergeˆncia pelo menos para uma classe de
sistemas lineares.
• Dependeˆncia da ordem das equac¸o˜es no sistema linear.
• Mesmo que o me´todo convirja´, como vimos no exerc´ıcio anterior, a convergeˆncia pode
ser bem lenta.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de Gauss–Seidel
 x
(k+1)
1 = ( 4.65 + 7.3x
k
2 )/7.5
x
(k+1)
2 = (49.80 + 2.8x
(k+1)
1 )/9.0
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O me´todo de Gauss–Seidel utiliza uma abordagem muito similar a` do me´todo de Jacobi,
pore´m como o me´todo de Jacobi pode ter convergeˆncia lenta, a ide´ia e´ tentar modifica-lo
com o propo´sito de acelerar sua convergeˆncia.
A ide´ia e´ utilizar a melhor aproximac¸a˜o assim que dispon´ıvel. Logo, na segunda equac¸a˜o, por
que utilizar xk1 se x
(k+1)
1 e´ supostamente melhor e ja´ e´ conhecido neste ponto do algoritmo?
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Gauss–Seidel
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Gauss–Seidel
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Gauss–Seidel
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Interpretac¸a˜o geome´trica – Gauss–Seidel
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de Gauss–Seidel
I Tambe´m e´ fa´cil de construir
I Nem sempre converge
I Convergeˆncia depende da ordem das equac¸o˜es
I Quando converge, em geral e´ mais ra´pido que Jacobi
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Direto × Iterativo
I Me´todos diretos
I Encontram a soluc¸a˜o exata depois de um nu´mero determinado
de passos
I Destroem a estrutura da matriz
I Precisam de memo´ria para manipular a matriz
I Me´todos iterativos
I Podem convergir ou na˜o
I Fornencem aproximac¸o˜es sucessivas
I Preservam a estrutura da matriz
I Precisam de menos memo´ria
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Modelo de me´todo de iterativo
I Seja x (0) uma aproximac¸a˜o inicial
I x (k+1) = φ(x (k)), para k = 0, 1, 2, . . .
Func¸a˜o de iterac¸a˜o e condic¸a˜o de ponto fixo
Se x∗ e´ uma soluc¸a˜o do problema, φ deve ter a propriedade de que
x∗ = φ(x∗)
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Um me´todo iterativo e´ dito de passo simples se para computar o iterando x(k+1) e´ utilizada
informac¸a˜o apenas da iterac¸a˜o k. De forma geral, todo me´todo iterativo de passo simples
pode ser representado por meio de uma func¸a˜o φ, dita func¸a˜o de iterac¸a˜o, que especifica
como, a partir das informac¸o˜es do passo k, obter o novo iterando x(k+1).
Um exemplo de me´todo iterativo de passo simples e´ o me´todo de Newton. A func¸a˜o de
iterac¸a˜o do me´todo de Newton e´
φ(x) = x − f (x)
f ′(x)
.
Observe que se x∗ for a soluc¸a˜o procurada, enta˜o para que o me´todo iterativo tenha chance
de encontra´-la e´ necessa´rio que φ(x∗) = x∗. Isso significa que, se em algum momento um
dos iterandos do me´todo for de fato a soluc¸a˜o do problema, todos os iterandos seguintes
permanecera˜o sendo x∗.
Essa condic¸a˜o por si so´ na˜o e´ suficiente, mas sim necessa´ria. Tal condic¸a˜o recebe o nome de
condic¸a˜o de ponto fixo.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Func¸a˜o de iterac¸a˜o
Splitting
Escrever uma matriz como a soma de duas outras matrizes e´ dito
um splitting. Por exemplo, A = M + N.
Se x∗ e´ soluc¸a˜o de Ax = b e A = M + N, enta˜o
Ax∗ = (M + N)x∗ = b
Mx∗∗ = −Nx∗ + b
x∗ = −M−1Nx∗ + M−1b
Proposta:
φ(x) ≡ Bx + c , B = (−M−1N), c = (M−1b)
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Para construir um me´todo iterativo para aproximar a resoluc¸a˜o do sistema linear Ax = b, e´
necessa´rio enta˜o criar uma func¸a˜o de iterac¸a˜o φ. Como ja´ vimos que a φ(x∗) = x∗, uma
proposta de func¸a˜o φ que cumpre essa condic¸a˜o e´
φ(x) = Bx + c,
onde B e´ constru´ıda a partir de algum splitting de A. Variando a forma com A e´ repartida
na soma M + N, teremos diferentes func¸o˜es de iterac¸a˜o.
B e´ dita a matriz de iterac¸a˜o do me´todo.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de iterativo
φ(x) = Bx + c , x∗ = φ(x∗)
I Seja x0 uma aproximac¸a˜o inicial
I x (k+1) = φ(x (k)) = Bx (k) + c , para k = 0, 1, 2, . . .
Este me´todo e´ convergente?
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Apenas o fato de ter constru´ıdo uma func¸a˜o φ que satisfaz a condic¸a˜o de ponto fixo, na˜o
garante que um me´todo iterativo a partir dessa func¸a˜o sera´ bem sucedido.
Devemos enta˜o nos perguntar sob quais condic¸o˜es os iterandos gerados por esse me´todo
convergem para a soluc¸a˜o do problema, ou seja, para x∗, soluc¸a˜o do sistema linear.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Convergeˆncia
O me´todo e´ convergente se x (k) → x∗, ou seja, se
‖e(k)‖≡ ‖x (k) − x∗‖ → 0
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Dizer que x(k) converge para x∗ e´ dizer que o vetor diferenc¸a converge para o vetor nulo, o
que pode ser medido pela norma do vetor.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Normas vetoriais
Norma e´ uma func¸a˜o que mede o tamanho de vetores.
x = (x1, x2, . . . , xn)
T
I Norma Euclidiana:
‖x‖2 =
√
x21 + x
2
2 + · · ·+ x2n
I Norma 1:
‖x‖1 = |x1|+ |x2|+ · · ·+ |xn|
I Norma infinito:
‖x‖∞ = max{|x1|, |x2|, . . . , |xn|}
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
A norma Euclidiana e´ a medida utilizada para se definir o conceito de usual distaˆncia
ou medir comprimento de vetores. Ou seja, a distaˆncia (em linha reta) de um ponto A
a um ponto B, ou o comprimento de um vetor que parte de A e atinge B, e´ dada por ‖A−B‖2.
Muitas outras normas podem ser definidas, representando noc¸o˜es distintas de comprimento.
Em particular a norma 1 e a norma infinito sa˜o outras duas opc¸o˜es, inclusive mais baratas de
serem computadas.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo: Araraquara
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
No caso da cidade de Araraquara, com seu planejamento cartesiano, a distaˆncia percorrida de
um ponto a outro da cidade na˜o e´ medida pela distaˆncia em linha reta, ou distaˆncia Euclidiana
convencional, mas sim pelo comprimento do trajeto ao longo dos eixos coordenados. Esta
distaˆncia e´ justamente medida pela norma 1.
Este exemplo e´ apenas para deixar claro que diferentes noc¸o˜es de como medir distaˆncias
podem ser u´teis em contextos diferentes.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Normas matriciais
‖A‖1 = max{‖aj‖1}, A =

...
...
...
a1 a2 · · · an
...
...
...

‖A‖1 e´ a maior norma-1 das colunas de A
‖A‖∞ = max{‖aj‖1}, A =

· · · a1 · · ·
· · · a2 · · ·
...
· · · an · · ·

‖A‖1 e´ a maior norma-1 das linhas de A
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Assim como definimos normas para vetores, tambe´m e´ posss´ıvel definir normas para matrizes.
Dentre as mais simples, destacamos as norma 1, denotadas por ‖ · ‖1 e a norma infinito,
denotada por ‖ · ‖∞.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
A =
 1 0 −34 3 1
0 −1 5
 → 4→ 8
→ 6
↓ ↓ ↓
5 4 9
‖A‖1 = 9 ‖A‖∞ = 8
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
‖A‖1 = max{‖(1, 4, 0)‖1, ‖(0, 3,−1)‖1, ‖(−3, 1, 5)‖1} = max{5, 4, 9} = 9
‖A‖∞ = max{‖(1, 0,−3)‖1, ‖(4, 3, 1)‖1, ‖(0,−1, 5)‖1} = max{8, 4, 6} = 8
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Convergeˆncia
O me´todo e´ convergente se x (k) → x∗, ou seja, se
‖e(k)‖ ≡ ‖x (k) − x∗‖ → 0
Como o erro varia em um passo do me´todo?
e(k) = x (k) − x∗
= φ(x (k−1))− φ(x∗)
= (Bx (k−1) + c)− (Bx∗ + c)
= B(x (k−1) − x∗)
= Be(k−1)
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Ja´ definimos que para que um me´todo seja convergente, o erro deve ir zero. Veja enta˜o
como escrever o erro no passo (k) em func¸a˜o do erro no passo (k − 1).
Observe que e(k) = Be(k−1).
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Convergeˆncia
e(k) = Be(k−1)
= B
(
Be(k−2)
)
= B2
(
Be(k−3)
)
= · · ·
= Bke(0)
e(k) = Bke(0) ⇒ ‖e(k)‖ ≤ ‖B‖k ‖e(0)‖
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Se ao avanc¸ar um passo o vetor erro e´ multiplicado por B, e´ fa´cil perceber que, partindo do
erro no iterando original, e(0), o erro no passo (k) sera´ e(k) = Bke(0).
E´ necessa´rio agora saber duas propriedades de normas de matrizes:
1. ‖AB‖ ≤ ‖A‖‖B‖
2. ‖Ax‖ ≤ ‖A‖‖x‖
Com essas propriedades, mostre que ‖Bke(0)‖ ≤ ‖B‖k‖e(0)‖.
Logo, para que o erro va´ a zero, basta pedir que ‖B‖ < 1.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Modelo de me´todo iterativo
I Seja x (0) uma aproximac¸a˜o inicial qualquer
I x (k+1) = φ(x (k)), para k = 0, 1, 2, . . .
com φ(x) = Bx + c , tal que x∗ = φ(x∗)
‖B‖ < 1 ⇒ x (k) → x∗
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Assim chegamos a` forma geral de me´todo iterativo de passo simples para a resoluc¸a˜o de
sistema linear.
Uma pergunta recorrente e´ se ‖B‖ precisa ser menor que 1 em todas as normas. A resposta
e´ na˜o. Se B tiver norma menor que 1, para alguma norma espec´ıfica, isto sera´ suficiente para
garantir a convergeˆncia do me´todo iterativo, naquela norma. Pore´m, se um me´todo iterativo
para sistema linear convergir em um determinada norma, o me´todo sera´ convergente em
qualquer outra norma. Logo, basta demonstrar a convergeˆncia com alguma norma.
Por outro lado, caso B tenha alguma norma maior que 1 ainda ha´ esperanc¸a de que o me´todo
seja convergente, pois e´ poss´ıvel que em outra norma a condic¸a˜o de convergeˆncia se cumpra.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
(
0.6 −0.2
0.4 1.3
)
x =
(
2.0
−0.1
)
Se A = I + (A− I ), enta˜o B = (I − A).
B = (I − A) =
(
0.4 0.2
−0.4 −0.3
)
, ‖B‖1 = 0.8, ‖B‖∞ = 0.7
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Neste exemplo, consideramos um splitting bem simples, A = M + N, onde M = I e
N = (A− I ). Esse spliting da´ origem a um me´todo conhecido como me´todo de Richardson.
A matriz de iterac¸a˜o do me´todo de Richardson e´ B = −M−1N = (I − A), e o vetor
c = M−1b = b.
No caso do exemplo, a matriz de iterac¸a˜o tem tanto norma 1 quando norma infinito menores
que 1. Portanto, o me´todo de Richardson aplicado ao sistema linear do exemplo, sera´ con-
vergente.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Iterando...
x (0) = b, ‖Ax (0) − b‖∞ = 0.78
x (1) = Bx (0) + b =
(
2.78
−0.87
)
‖Ax (1) − b‖∞ = 0.16
x (2) = Bx (1) + b =
(
2.94
−0.95
)
‖Ax (2) − b‖∞ = 0.05
· · ·
x (4) = Bx (3) + b =
(
3.00
−1.00
)
‖Ax (4) − b‖∞ = 2 · 10−3
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Outro exemplo com o me´todo de Richardson
(
1.7 −0.6
−0.7 1.5
)
x =
(
2.0
−0.1
)
B = (I − A) =
( −0.7 0.6
0.7 −0.5
)
, ‖B‖1 = 1.4, ‖B‖∞ = 1.3
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Como a matriz de iterac¸a˜o tem norma maior que 1, nas duas normas que conhecemos, na˜o
ha´ como garantir que o me´todo de Richardson sera´ convergente.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Outros splittings
A =

× × × ×
× × × ×
× × × ×
× × × ×

A =
×× ×
× × ×
+

×
×
×
×
+

× × ×
× ×
×

A = L + D + U
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Outra maneira de separar a matriz A em somas e considerando suas porc¸o˜es diagonal e
triangulares inferior e superior.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de Jacobi
Escrevendo A = D + (L + U),
Ax∗ = b
(L + D + U)x∗ = b
Dx∗ = −(L + U)x∗ + b
x∗ = −D−1(L + U)x∗ + D−1b
Func¸a˜o de Iterac¸a˜o
φ(x) = BJx + c , BJ = −D−1(L + U), c = D−1b
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O me´todo de Jacobi e´ constru´ıdo resolvendo-se um sistema diagonal.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
(
1.7 −0.6
−0.7 1.5
)
x=
(
2.0
−0.1
)
BJ = −
(
1.7
1.5
)−1( −0.6
−0.7
)
=
(
0.00 0.35
0.47 0.00
)
‖BJ‖1 = ‖BJ‖∞ = 0.47
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Observe que a matriz de iterac¸a˜o do me´todo de Jacobi tem norma menor que 1, enquanto
que ja´ hav´ıamos visto que para este mesmo sistema linear, a matriz de iterac¸a˜o do me´todo
de Richardson tinham norma maior que 1.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Convergeˆncia
BJ = −

a−111
a−122
a−133
. . .
a−1nn


0 a12 a13 a1n
a21 0 a23 · · · a2n
a31 a32 0 a2n
...
. . .
...
an1 an2 an3 · · · 0

BJ = −

0 a12/a11 a13/a11 a1n/a11
a21/a22 0 a23/a22 · · · a2n/a22
a31/a33 a32/a33 0 a3n/a33
...
. . .
...
an1/ann an2/ann an3/ann · · · 0

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
De forma geral, observando a matriz de iterac¸a˜o do me´todo de Jacobi e´ poss´ıvel vislumbrar
um crite´rio de convergeˆncia baseado diretamente nas entradas da matriz A original.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Crite´rio das linhas
Para que ‖BJ‖∞ < 1, basta que
‖bj‖1 =
|aj1|+ · · ·+ |aj(j−1)|+ |aj(j+1)|+ · · ·+ |ajn|
|ajj | < 1,
para j = 1, 2, . . . , n, ou seja
|ajj | >
n∑
k=1
k 6=j
|ajk |
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O crite´rio das linhas garante que o me´todo de Jacobi sera´ convergente se os elementos
da diagonal da matriz dominarem os restantes dos elementos das linhas, ou seja, se em
cada linha o elemento da diagonal em mo´dulo foi maior que a soma dos elementos fora da
diagonal, todos em mo´dulo.
Matrizes com essa propriedade sa˜o ditas matrizes diagonalmente dominantes por linhas.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Exemplo
 4 2 −10 −3 1
−2 2 −6

 5 2 −16 −3 1
−1 2 7

 5 2 −12 −3 7
−1 2 0

http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
A primeira matriz satisfaz o crite´rio das linhas, visto que 4 > 2 + 1, 3 > 0 + 1, e 6 > 2 + 2.
Logo, seguramente o me´todo de Jacobi aplicado a um sistema linear com esta matriz de
coeficientes convergira´.
A segunda matriz na˜o satisfaz o crite´rio das linhas, visto que na segunda linha 3 < 6 + 1.
A terceira matriz tambe´m na˜o satisfaz o crite´rio das linhas, dado que tanto a segunda como a
terceira linhas violam a condic¸a˜o necessa´ria (3 < 2+7 e 0 < 2+1). Entretanto, permuntando
a segunda e a terceira linhas, a nova matriz sim satisfaz o crite´rio das linhas. Portanto, e´
poss´ıvel aplicar o me´todo de Jacobi, desde que esta permutac¸a˜o seja feita antes.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Jacobi na pra´tica

5x1 − 2x2 + x3 = 6
x1 − 4x2 − 2x3 = 3
2x1 + 2x2 − 7x3 = 8

5x
(k+1)
1 = 6 + 2x
(k)
2 − x (k)3
−4x (k+1)2 = 3 − x (k)1 + 2x (k)3
−7x (k+1)3 = 8 − 2x (k)1 − 2x (k)2
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Observe que na pra´tica, na˜o e´ necessa´rio formar a matriz de iterac¸a˜o do Jacobi.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Jacobi na pra´tica

5x
(k+1)
1 = 6 + 2x
(k)
2 − x (k)3
−4x (k+1)2 = 3 − x (k)1 + 2x (k)3
−7x (k+1)3 = 8 − 2x (k)1 − 2x (k)2
x0 =
 63
8
 x1 =
 0.80−3.25
1.43
 x2 =
 −0.39−1.26
−1.84

‖x1 − x0‖∞ = 6.6, ‖x2 − x1‖∞ = 3.3
‖Ax0−b‖∞ = 46.0, ‖Ax1−b‖∞ = 22.9, ‖Ax2−b‖∞ = 7.2
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Me´todo de Gauss–Seidel
Escrevendo A = (L + D) + U,
Ax∗ = b
(L + D + U)x∗ = b
(L + D)x∗ = −Ux∗ + b
x∗ = −(L + D)−1Ux∗ + (L + D)−1b
Func¸a˜o de Iterac¸a˜o
φ(x) = BGSx + c , BGS = −(L + D)−1U, c = (L + D)−1b
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
O me´todo de Jacobi e´ constru´ıdo resolvendo-se um sistema triangular inferior.
Tambe´m e´ poss´ıvel obter um crite´rio de convergeˆncia espec´ıfico para o me´todo de Gauss–
Seidel, assim como foi feito para o me´todo de Jacobi. Entretanto, a a´lgebra envolvida e´ mais
tediosa e, portanto na˜o o faremos aqui. A saber, se o me´todo de Jacobi for convergente, o
me´todo de Gauss–Seidel tambe´m o sera´. Logo o crite´rio das linhas tambe´m pode ser adotado
aqui.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Gauss–Seidel na pra´tica

5x1 − 2x2 + x3 = 6
x1 − 4x2 − 2x3 = 3
2x1 + 2x2 − 7x3 = 8

5x
(k+1)
1 = 6 + 2x
(k)
2 − x (k)3
−4x (k+1)2 = 3 − x (k+1)1 + 2x (k)3
−7x (k+1)3 = 8 − 2x (k+1)1 − 2x (k+1)2
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Assim como no caso do me´todo de Jacobi, aqui tambe´m na˜o e´ necessa´rio construir a matriz
de iterac¸a˜o.
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Gauss–Seidel na pra´tica

5x
(k+1)
1 = 6 + 2x
(k)
2 − x (k)3
−4x (k+1)2 = 3 − x (k+1)1 + 2x (k)3
−7x (k+1)3 = 8 − 2x (k+1)1 − 2x (k+1)2
x0 =
 63
8
 x1 =
 0.80−4.55
−2.21
 x2 =
 0.540.32
1.39

‖x1 − x0‖∞ = 10.2, ‖x2 − x1‖∞ = 4.9
‖Ax0−b‖∞ = 46.0, ‖Ax1−b‖∞ = 20.4, ‖Ax2−b‖∞ = 8.6
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Eliminac¸a˜o de Gauss Decomposic¸a˜o LU Pivoteamento Me´todos iterativos I Me´todos Iterativos II
Jacobi × Gauss–Seidel
Se Gauss–Seidel e´, em geral, mais ra´pido que Jacobi,
e o custo computacional e´ o mesmo,
ainda ha´ espac¸o para o me´todo de Jacobi?
http://goo.gl/7DZpR Ricardo Biloti Sistemas lineares
Sim! Pois no me´todo de Jacobi o ca´lculo de x
(k+1)
j depende apenas de x
(k) e portanto,
todos x
(k+1)
j podem ser calculados em paralelo. Esta caracter´ıtica pode ser aproveitada
quando utilizamos computadores com processadores com va´rios nu´cleos, ou mesmo va´rios
processadores, ou ainda clusters de computadores, capazes de realizar va´rias operac¸o˜es em
simultaˆneo.
Dito isso, e´ importante saber que ha´ outros me´todos iterativos para sistemas lineares mais
modernos e velozes que Jacobi e Gauss–Seidel, como o me´todo de sobrerrelaxac¸o˜es sucessivas
(SOR) ou os me´todos de Krylov, como o me´todo de gradientes conjugados ou o GMRES,
por exemplo.
	Eliminação de Gauss
	Decomposição LU
	Pivoteamento
	Métodos iterativos I
	Métodos Iterativos II