Introducao aos Metodos Numericos

Prévia do material em texto

Chapter 1
Sobre Erros
1.1 Introduc¸a˜o
Podemos distinguir va´rios tipos de erros que podem limitar a precisa˜o dos resultados de ca´lculos,
1. erros inerentes;
2. erros de arredondamento;
3. erros de aproximac¸a˜o.
Os erros inerentes esta˜o ale´m do controle do ca´lculo e surgem, em geral, na aquisic¸a˜o de dados,
que podem ser obtidos com instrumentos que possuem uma precisa˜o limitada.
Os erros de arredondamento surgem quando realizamos os ca´lculos com nu´meros cuja repre-
sentac¸a˜o e´ restrita a um nu´mero finito de d´ıgitos, como e´ o caso dos computadores digitais.
Vejamos o terceiro tipo de erro. Muitos me´todos na˜o fornecem a soluc¸a˜o exata de um problema
P , mesmo que os ca´lculos sejam realizados sem erros de arredondamento, eles fornecem, na verdade,
a soluc¸a˜o de um outro problema mais simples P˜ que aproxima o problema P . Por exemplo, seja P o
problema de somar os termos de uma se´rie infinita como abaixo,
e =
1
1!
+
1
2!
+
1
3!
+
1
4!
+ · · ·
este problema pode ser substitu´ıdo por um problema P̂ mais simples de somar somente um nu´mero
finito de termos da se´rie. Isto e´
e ≈ 1 + 1
2!
+
1
3!
+ · · ·+ 1
n!
Muitas aproximac¸o˜es de problemas sa˜o obtidas por discretizac¸a˜o do problema original: por exemplo,
integrais definidas sa˜o aproximadas por somas finitas, diferenciais por diferenc¸as, etc.. Em tais casos
os erros de aproximac¸a˜o sa˜o tambe´m chamados erros de discretizac¸a˜o. Estes tipos de erros sera˜o
discutidos individualmente, sempre que poss´ıvel, para cada me´todo estudado.
1.2 Representac¸a˜o de Nu´meros
Por razo˜es te´cnicas, a maioria dos computadores digitais representam os nu´meros internamente na
forma bina´ria, ao inve´s da decimal.
1
2
Os computadores fazem uso de um nu´mero finito e fixo de posic¸o˜es quando internamente rep-
resentam um nu´mero, o comprimento da palavra. Esse nu´mero n e´ determinado pela construc¸a˜o da
ma´quina, embora algumas ma´quinas possuam extenso˜es para mu´ltiplos de n, 2n (precisa˜o dupla), 3n
(precisa˜o tripla), para fornecer uma precisa˜o maior, se for necesssa´rio.
1.2.1 Conversa˜o de Nu´meros: Decimal ↔ Bina´rio
Se o nu´mero e´ inteiro:
Ex:
(347)10 = 3× 102 + 4× 101 + 7× 100
(10111)2 = 1× 24 + 0× 23 + 1× 22 + 1× 21 + 1× 20
Bina´rio → Decimal
N = (anan−1 . . . a2a1a0)β = anβ
n + an−1β
n−1 + . . . a2β
2 + a1β
1 + a0β
0
logo
(10111)2 = 1× 24 + 0× 23 + 1× 22 + 1× 21 + 1× 20 = 16 + 0 + 4+ 2 + 1 = (23)10
Decimal → Bina´rio
347
2
= 173× 2 + 19
173
2
= 86× 2 + 18
86
2
= 43× 2 + 07
43
2
= 21× 2 + 16
21
2
= 10× 2 + 15
10
2
= 5× 2 + 04
5
2
= 2× 2 + 13
2
2
= 11 × 2 + 02
ou
(347)10 = (101011011)2
Se o nu´mero e´ fraciona´rio
r = rI + rF = Parte Inteiro + Parte Fraciona´ria
3
Se a base e´ decimal (10)
rF = b1 × 10−1 + b2 × 10−2 + b3 × 10−3 + . . .+ bk × 10−k + . . .
ex:
rF = 0,125 = 1× 10−1 + 2× 10−2 + 5× 10−3 (representac¸a˜o finita)
rF = 0,11111 . . .= 1× 10−1 + 1× 10−2 + 1× 10−3 + . . . (sem representac¸a˜o finita)
Se a base e´ bina´ria (2)
rF = b1 × 2−1 + b2 × 2−2 + b3 × 2−3 + . . .+ bk × 2−k + . . .
Bina´rio → Decimal
Ex:
(0,001)2 = 0× 2−1 + 0× 2−2 + 1× 2−3 = 0× 1
2
+ 0× 1
4
+ 1× 1
8
= 0 + 0 + 0,125 = (0,125)10
Decimal → Bina´rio
rF → parte decimal
→ rF =
∞∑
k=1
bk2
−k
×2 → 2rF =
∞∑
k=1
bk2
−k+1 = b1︸︷︷︸
(⋆)
+
∞∑
k=1
bk+12
−k
︸ ︷︷ ︸
(⋆⋆)
onde (⋆) e´ a parte inteira bina´ria de 2rF e (⋆⋆) e´ a parte fraciona´ria bina´ria.
Novamente
→ (2rF )F =
∞∑
k=1
bk+12
−k
→ 2(2rF )F =
∞∑
k=1
bk+12
−k+1 = b2︸︷︷︸
(⋆)
+
∞∑
k=1
bk+22
−k
︸ ︷︷ ︸
(⋆⋆)
onde (⋆) e´ a parte inteira bina´ria de 2(2rF )F e (⋆⋆) e´ a parte fraciona´ria bina´ria.
Ex:
1. rF = (0,5)10
2rF = 2
{
∞∑
k=1
bk2
−k
}
=
∞∑
k=1
bk2
−k+1 = b1 +
∞∑
k=1
bk+12
−k
4
2rF = 2(0,5) = 1 = b1 +
∞∑
k=1
bk+12
−k
=⇒ b1 = 1 e bk = 0, k = 2, 3, . . .
assim
rF = (0,5)10 = (0,1)2
2. rF = (0,1)10
2rF = 0,2 −→ b1 = 0
2(2rF )F = 0,4 −→ b2 = 0
2(2(2rF)F )F = 0,8 −→ b3 = 0
2(2(2(2rF)F )F )F = 1,6 −→ b4 = 1
2(0.6) = 1,2 −→ b5 = 1
2(0.2) = 0,4 −→ b6 = 0
2(0.4) = 0,8 −→ b7 = 0
2(0.8) = 1,6 −→ b8 = 1
2(0.6) = 1,2 −→ b9 = 1
2(0.2) = 0,4 −→ b10 = 0
2(0.4) = 0,8 −→ b11 = 0
2(0.8) = 1,6 −→ b12 = 1
2(0.6) = 1,2 −→ b13 = 1
2(0.2) = 0,4 −→ b14 = 0
... =
... −→ ...
logo (0,1)10 = (0,000110011001100110011 . . .)2.
Note que (0,1)10 tem representac¸a˜o finita, pore´m, na base bina´ria na˜o (0,0001100 . . .)2.
Ex:
100∑
k=1
0,1 6= 10 num computador
na ma´quina sera´ armazenada uma aproximac¸a˜o para o nu´mero que depende do comprimento da
palavra do computador.
Vimos que uma fonte de erros esta´ no processo de conversa˜o do sistema decimal para o sistema
bina´rio e vice-versa. Outra fonte de erros esta´ no fato de que os computadores possuem um nu´mero
finito de d´ıgitos para representar os nu´meros reais.
5
1.2.2 Representac¸a˜o em Ponto Flutuante
Neste tipo de representac¸a˜o o ponto decimal (bina´rio) na˜o e´ fixo, sua posic¸a˜o com respeito ao primeiro
d´ıgito e´ indicado separadamente, atrave´s de um expoente. Isto e´,
Definic¸a˜o:
Um nu´mero real x e´ dito um nu´mero de ponto flutuante normalizado se:
(1) x = mbe
(2) m = ±0,d1d2d3 . . . dn, n ∈ IN
(3) 1 ≤ d1 ≤ b− 1, 0 ≤ di ≤ b− 1; i = 2, 3, 4, . . . , n
(4) e1 ≤ e ≤ e2, e1 ≤ 0, e2 ≥ 1, e1, e2 ∈ ZZ
onde
• b - base, b ≥ 2
• e - expoente
• m - mantissa
• n - nu´mero de digitos usados para representar a mantissa
Observac¸a˜o: No sistema me´trico o s´ımbolo separador decimal e´ a v´ırgula e na˜o o ponto como no
sistema ingleˆs. Aqui usamos a nomenclatura ponto flutuante e na˜o v´ırgula flutuante (esta u´ltima
parecendo mais correta), por causa da muito difundida terminologia inglesa.
Todos os nu´meros de ponto flutuante e o nu´mero 0 que e´ representado como
0 = 0,000 . . .00︸ ︷︷ ︸
n vezes
×be1
formam um sistema de ponto flutuante denotado por F (b, n, e1, e2).
Exemplo:
0,1236 = 0,1236× 100
= 1,236× 10−1
= 12,36× 10−2
= 0,01236× 101
= 0,001236× 102
Dado um sistema F de ponto flutuante
F = F (b, n, e1, e2)
Temos que:
6
0,1× be1 −→ menor nu´mero positivo na˜o nulo
0,[b− 1][b− 1][b− 1] . . . [b− 1]× be2 −→ maior nu´mero
Ale´m disso
♯F = 2︸︷︷︸
±
× (b− 1)bn−1︸ ︷︷ ︸
mantissas 6=
× (e2 − e1 + 1)︸ ︷︷ ︸
expoentes 6=
+ 1︸︷︷︸
0
Exemplo:
F = F (b, n, e1, e2) = F (2, 3,−1, 2)
♯F = 2︸︷︷︸× 1× 22︸ ︷︷ ︸× (2− (−1) + 1)︸ ︷︷ ︸+ 1︸︷︷︸ = 33
b = 2
n = 3 −→ treˆs digitos para a mantissa, logo todas as mantissas poss´ıveis sa˜o:
0,100
0,101
0,110
0,111
e1 = −1; e2 = 2 −→ todos os expoentes poss´ıveis sa˜o:
−1
0
1
2
Temos enta˜o os seguintes nu´meros reais positivos neste sistema
(0,100× 2−1)2 = (0,01)2 = (0× 20 + 0× 2−1 + 1× 2−2)10 = 1
4
(0,100× 20)2 = (0,1)2 = (0× 20 + 1× 2−1)10 = 1
2
(0,100× 21)2 = (1,0)2 = (1× 20)10 = 1
(0,100× 22)2 = (10,0)2 = (1× 21 + 0× 20)10 = 2
(0,101× 2−1)2 = (0,0101)2 = (0× 20 + 0× 2−1 + 1× 2−2 + 0× 2−3 + 1× 2−4)10 = 5
16
(0,101× 20)2 = (0,101)2 = (0× 20 + 1× 2−1 + 0× 2−2 + 1× 2−3)10 = 5
8
e assim sucessivamente. Resumindo
7
e\m 0,100 0,101 0,110 0,111
-1 1/4 5/16 3/8 7/16
0 1/2 5/8 3/4 7/8
1 1 5/4 3/2 7/4
2 2 5/2 3 7/2
Representando estes nu´meros na reta dos reais
- 1
2
- 7
16
- 3
8
- 5
16
- 1
4
0 1
4
5
16
3
8
7
16
1
2
5
8
3
4
7
8
1 5
4
3
2
7
4
2 5
2
3 7
2
✲
IR
Vemos claramente que os nu´meros de ponto flutuante de F na˜o esta˜o uniformemente distribu´ıdos
no intervalo [−7/2, 7/2], na verdade, existem regio˜es onde eles esta˜o uniformemente distribu´ıdos.
Podemos destacar duas regio˜es noto´rias num sistema de pontoflutuante.
Regia˜o de UNDERFLOW: entre o maior nu´mero de ponto flutuante negativo e zero e entre zero
e o menor nu´mero de ponto flutuante positivo. Para diminuir esta regia˜o devemos aumentar o valor
de n.
Regia˜o de OVERFLOW: a regia˜o aque´m e ale´m do menor e maior nu´mero de ponto flutuante,
respectivamente. Para melhorar devemos aumentar e diminuir e2 e e1, respectivamente.
Ale´m disso podemos observar tambe´m que se efetuarmos uma operac¸a˜o aritme´tica com pontos
de um sistema de ponto flutuante, seu resultado pode na˜o pertencer ao sistema. Por exemplo, no
sistema mostrado acima temos
1 +
7
8
=
15
8
/∈ F

1 + 78 =
7
4 ∈ F
1 + 78 = 2 ∈ F
0 14
1
2
5
8
3
4 (
7
8)(1)
5
4
3
2
7
4 (
15
8 )
/∈F
2 52 3
7
2
✲
IR
logo, podemos ter
x⊕ y 6= x+ y
x⊖ y 6= x− y
x⊗ y 6= x× y
x⊘ y 6= x/y
onde © denota uma operac¸a˜o aritme´tica elementar efetuada em um sistema de ponto flutuante.
8
Devido a estes erros as operac¸o˜es aritme´ticas podem fornecer como resultados nu´meros incorre-
tos, mesmo que os operandos estejam certos. Ademais, outras propriedades das operac¸o˜es aritme´ticas
deixam de serem va´lidas, e o resultado pode depender do algoritmo usado.
Exemplo:
Seja F = F (10, 8,−99, 99), e os seguintes nu´meros reais com representac¸a˜o no sistema de ponto flu-
tuante
a = 0,23371258× 10−4
b = 0,33678429× 102
c = −0,33677811× 102
temos, enta˜o,
a+ (b+ c) = 0,23371258× 10−4 + (0,33678429× 102 − 0,33677811× 102)
= 0,23371258× 10−4 + 0,00000618× 102
= 0,23371258× 10−4 + 0,61800000× 10−3
= 0,02337126× 10−3 + 0,61800000× 10−3
= 0,64137126× 10−3
(a+ b) + c = (0,23371258× 10−4 + 0,33678429× 102)− 0,33677811× 102
= (0,00000023× 102 + 0,33678429× 102)− 0,33677811× 102
= 0,33678452× 102 − 0,33677811× 102
= 0,64100000× 10−3
que sa˜o diferentes do resultado exato
a+ b+ c = 0,641371258× 10−3
Portanto as operac¸o˜es aritme´ticas em ponto flutuante na˜o sa˜o necessariamente associativas ou
distributivas.
Arredondamento
A aproximac¸a˜o de um nu´mero real por um nu´mero de ponto flutuante pode ser feito de maneiras
diferentes. As mais conhecidas sa˜o:
• Arredondamento para cima;
• Arredondamento para baixo;
• Arredondamento para o nu´mero de ma´quina mais pro´ximo;
a p/baixo a+b
2
x b p/cima ou + pro´x.
✲
IR
Exemplo: F = F (2, 3,−1, 2)
9
8
/∈ F
9
9
8
= (1.125)10 = (0.1001× 21)2
para baixo
9
8
= (0.100× 21)2 = 1
para cima
9
8
= (0.101× 21)2 = 5
4
10
1.2.3 Erros Absolutos e Relativos
Erro Absoluto:
EAx = x− x˜
ou
EAx =| x− x˜ | −→ mais usada
onde x e´ o valor exato e x˜ e´ o valor aproximado.
Erro Relativo:
ERx =
x− x˜
x
ou ERx =
x− x˜
x˜
ou
ERx =
| x− x˜ |
| x | ou ERx =
| x− x˜ |
| x˜ | −→ mais usadas
Exemplo:
x = 0,00005
x˜ = 0,00006
logo,
EAx =| x− x˜ |=| 0,00005− 0,00006 |= 0,00001 −→ parece pequeno
ERx =
| x− x˜ |
| x | =
| 0,00005− 0,00006 |
| 0,00005 | =
0,00001
0,00005
= 0,2 = 20%
Chapter 2
Resoluc¸a˜o de Sistemas Lineares
2.1 Introduc¸a˜o
Seja uma sistema linear geral de n equac¸o˜es e n inco´gnitas x1, x2, x3, . . . xn
a11x1 + a12x2 + a13x3 + a14x4 + · · ·+ a1nxn = b1
a21x1 + a22x2 + a23x3 + a24x4 + · · ·+ a2nxn = b2
a31x1 + a32x2 + a33x3 + a34x4 + · · ·+ a3nxn = b3
a41x1 + a42x2 + a43x3 + a44x4 + · · ·+ a4nxn = b4
...
...
...
...
...
...
an1x1 + an2x2 + an3x3 + an4x4 + · · ·+ annxn = bn
(2.1)
Que reescrito na forma matricial torna-se
a11 a12 a13 a14 · · · a1n
a21 a22 a23 a24 · · · a2n
a31 a32 a33 a34 · · · a3n
a41 a42 a43 a44 · · · a4n
...
...
...
...
. . .
...
an1 an2 an3 an4 · · · ann

·

x1
x2
x3
x4
...
xn

=

b1
b2
b3
b4
...
bn

(2.2)
ou na forma compacta
Ax = b
11
12
onde
A =

a11 a12 a13 a14 · · · a1n
a21 a22 a23 a24 · · · a2n
a31 a32 a33 a34 · · · a3n
a41 a42 a43 a44 · · · a4n
...
...
...
...
. . .
...
an1 an2 an3 an4 · · · ann

e´ chamada matriz de coeficientes do sistema
x =

x1
x2
x3
x4
...
xn

e´ o vetor de inco´gnitas e
b =

b1
b2
b3
b4
...
bn

e´ o vetor segundo membro.
Teoricamente se A e´ invers´ıvel (det(A) 6= 0) enta˜o x =A−1b e´ a soluc¸a˜o do sistema, entretanto,
calcular inversas de matrizes pode ser uma tarefa trabalhosa.
13
2.2 Definic¸o˜es Preliminares
A ∈ IRn×n, sa˜o chamadas matrizes quadradas
A = [aij ] =

a11 a12 a13 a14 · · · a1n
a21 a22 a23 a24 · · · a2n
a31 a32 a33 a34 · · · a3n
a41 a42 a43 a44 · · · a4n
...
...
...
...
. . .
...
an1 an2 an3 an4 · · · ann

Operac¸o˜es Ba´sicas com Matrizes
C = A+B ; cij = aij + bij
C = αA ; cij = αaij
C = AB ; cij =
∑n
k=1 aik · bkj
C = AT ; cij = aji
I =

1 0 0 · · · 0 0
0 1 0 · · · 0 0
0 0 1 · · · 0 0
...
...
...
. . .
...
...
0 0 0 · · · 1 0
0 0 0 · · · 0 1

Chama-se inversa de uma matriz A a matriz A−1 tal que AA−1 = A−1A = I.
Se A−1 existe, A e´ dita na˜o-singular, caso contra´rio A e´ dita singular.
Determinantes:
Se A = a ∈ IR1×1 −→ det(A) = a
Se A ∈ IRn×n −→
det(A) =
n∑
j=1
(−1)j+1aij det(A1j)
onde a matriz A1j e´ obtida retirando-se a primeira linha e a j-e´sima coluna de A.
Propriedades dos determinantes:
1. det(AB) = det(A) det(B);
2. det(AT ) = det(A);
3. det(cA) = cn det(A);
4. det(A) 6= 0←→ A e´ na˜o-singular;
14
Matrizes Especiais:
• Sime´trica se AT = A
• Anti-sime´trica se AT = −A
• Positiva definida se xTAx > 0, ~0 6= x ∈ IRn
• Na˜o positiva definida se xTAx ≥ 0, x ∈ IRn
• Ortogonal se ATA = I
• Nilpotente se Ak = 0 para algum k
• Idempotente se A2 = A
• Positiva se aij > 0, ∀ i, j
• Na˜o negativa se aij ≥ 0, ∀ i, j
• Diagonal dominante se | aii |>
∑n
j 6=i | aij |, ∀ i
Classificac¸a˜o quanto a forma da matriz:
• Diagonal se aij = 0 para i 6= j;
• Tridiagonal se aij = 0 para | i− j |> 1;
• Triangular superior se aij = 0 para i > j;
• Estritamente triangular superior se aij = 0 para i ≥ j;
• Triangular inferior se aij = 0 para i < j;
• Matriz esparsa se tem a maioria de seus elementos nu-
los;
• Matriz densa se a maioria de seus elementos sa˜o
diferentes de zero;
• Matriz em Banda Uma matriz e´ de banda superior s e
de banda inferior r se aij = 0 para
i > j + r e j > i + s, se s = r a
matriz e´ chamada simplesmente de
banda r.
Definic¸a˜o: Uma norma em IRn e´ uma func¸a˜o real ‖.‖ satisfazendo as seguintes propriedades.
• ∀x ∈ IRn, ‖x‖ ≥ 0 e ‖x‖ = 0⇐⇒ x = ~0
• ∀x ∈ IRn, ∀α ∈ IR, ‖αx‖ =| α | ‖x‖
• ∀x, y ∈ IRn, ‖x+ y‖ ≤ ‖x‖+ ‖y‖
15
Exemplos:
‖x‖2 =
√√√√ n∑
i=1
| xi |2 Norma Euclidiana
‖x‖1 =
n∑
i=1
| xi | Norma da Soma
‖x‖∞ = max
1≤i≤n
| xi | Norma do Ma´ximo
Analogamente podemos definir normas para matrizes como:
Definic¸a˜o: Uma norma em IRm×n e´ uma func¸a˜o real ‖.‖ satisfazendo as seguintes propriedades.
• ∀A ∈ IRm×n, ‖A‖ ≥ 0 e ‖A‖ = 0⇐⇒ A = 0ˆ
• ∀A ∈ IRm×n, ∀α ∈ IR, ‖αA‖ =| α | ‖A‖
• ∀A,B ∈ IRm×n, ‖A+B‖ ≤ ‖A‖+ ‖B‖
Exemplos:
‖A‖1 = max
1≤j≤
(
n∑
i=1
| aij |
)
Norma do Ma´ximo das Colunas
‖A‖∞ = max
1≤j≤
(
n∑
i=1
| aij |
)
Norma do Ma´ximo das Linhas
‖A‖E =
√√√√ n∑
i=1
n∑
j=1
a2ij Norma Euclidiana
Observac¸a˜o: Uma norma matricial e´ consistente com uma norma vetorial se:
‖Ax‖ ≤ ‖A‖‖x‖ ∀A ∈ IRn×n, ∀x ∈ IRn
Existem duas grandesclasses de me´todos nume´ricos para a resoluc¸a˜o de sistemas lineares. Os
Me´todos Diretos e os Me´todos Iterativos. Nos me´todos diretos a soluc¸a˜o do sistema e´ obtida apo´s um
nu´mero finito de passos. Diferentemente, os me´todos iterativos partem de uma aproximac¸a˜o inicial
para a soluc¸a˜o do sistema e geram uma sequ¨eˆncia de aproximac¸o˜es que esperamos convirja para a
soluc¸a˜o do sistema.
2.3 Me´todos Diretos
Nesta classe de me´todos a soluc¸a˜o do sistema e´ obtida apo´s um nu´mero finito de passos e sa˜o em
geral baseados em me´todos de eliminac¸a˜o onde se transforma o sistema a resolver em outro sistema de
resoluc¸a˜o mais fa´cil que o sistema original. Estes me´todos sa˜o normalmente empregados na soluc¸a˜o
de sistemas de pequeno a me´dio porte em que a matriz de coeficientes e´ densa.
16
2.3.1 Eliminac¸a˜o de Gauss / Fatorac¸a˜o LU
O objetivo do processo de Eliminac¸a˜o de Gauss e´ transformar um sistema linear Ax = b em um outro
sistema, que possui a mesma soluc¸a˜o do primeiro, Ux = c tal que a matriz U seja triangular superior.
Esta transformac¸a˜o e´ feita atrave´s de combinac¸o˜es lineares das linhas do sistema. As operac¸o˜es sobre
as linhas na˜o alteram a soluc¸a˜o do sistema original e se resumem a:
• Multiplicac¸a˜o de uma linha por um escalar;
• Soma de duas linhas;
• Troca de duas linhas.
Os sistemas lineares onde a matriz do sistema e´ triangular superior sa˜o de fa´cil soluc¸a˜o. Seja o
sistema triangular superior abaixo
a11x1 + a12x2 + a13x3 + · · · · · · + a1,n−1xn−1 + a1nxn = b1
a22x2 + a23x3 + · · · · · · + a2,n−1xn−1 + a2nxn = b2
a33x3 + · · · · · · + a3,n−1xn−1 + a3nxn = b3
...
...
...
an−1,n−1xn−1 + an−1,nxn = bn
annxn = bn
(2.3)
Vemos que a u´ltima equac¸a˜o do sistema acima so´ possui dependeˆncia da u´ltima inco´gnita xn, logo
podemos calcular esta inco´gnita,
xn =
bn
ann
da penu´ltima equac¸a˜o como ja´ conhecemos xn, podemos determinar xn−1, logo
xn−1 =
1
an−1,n−1
{bn − an−1,nxn}
Conhecendo xn−1 e xn podemos da antipenu´ltima equac¸a˜o do sistema determinar xn−2. Com xn,
xn−1 e xn−2 calculamos xn−3 e repetindo este procedimento podemos determinar todas as inco´gnitas
do sistema. Este processo e´ chamado retro-substituic¸a˜o.
Para i = n, n− 1, . . . , 1
xi = bi
Para j = i+ 1, . . . , n
xi = xi − aijxj
xi = xi/aii
Exemplo:
3x1 + 4x2 − 4x3 = 3
2x2 + x3 = 3
4x3 = 4
17
Soluc¸a˜o:
Da terceira equac¸a˜o −→ x3 = 4
4
= 1
Da segunda equac¸a˜o −→ x2 = 1
2
{3− x3} = 1
2
{3− 1} = 2
2
= 1
Da primeira equac¸a˜o −→ x1 = 1
3
{3 + 4x3 − 4x2} = 1
3
{3 + 4 · 1− 4 · 1} = 1
3
{3 + 4− 4} = 3
3
= 1
Resp: (1; 1; 1)
De maneira similar podemos resolver um sistema triangular inferior atrave´s de uma substituic¸a˜o
progressiva,
a11x1 = b1
a21x1 + a22x2 = b2
a31x1 + a32x2 + a33x3 = b2
...
...
...
an−1,1x1 + an−1,2x2 + an−1,3x3 + · · · + an−1,n−1xn−1 = bn−1
an1x1 + an2x2 + an3x3 + · · · + an,n−1xn−1 + annxn = bn
(2.4)
isto e´ da primeira equac¸a˜o do sistema calculamos o valor da inco´gnita x1, que substitu´ıdo na segunda
equac¸a˜o permite que calculemos diretamente a inco´gnita x2, com os valores de x1 e x2 podemos obter
x3 da terceira equac¸a˜o e assim em diante.
Para i = 1, 2, 3, . . . , n
xi = bi
Para j = 1, . . . , i− 1
xi = xi − aijxj
xi = xi/aii
Exemplo:
4x1 = 4
x1 + 2x2 = 3
3x1 + 4x2 − 4x3 = 3
Soluc¸a˜o:
Da primeira equac¸a˜o −→ x1 = 4
4
= 1
18
Da segunda equac¸a˜o −→ x2 = 1
2
{3− x1} = 1
2
{3− 1} = 2
2
= 1
Da terceira equac¸a˜o −→ x3 = 1−4 {3− 3x1 − 4x2} =
1
−4 {3− 3− 4} =
−4
−4 = 1
Resp: (1; 1; 1)
Ja´ vimos que muito fa´cil resolver qualquer sistema triangular superior. Veremos agora como
transformar um sistema qualquer em um sistema triangular superior usando combinac¸o˜es lineares das
linhas do sistema. Vejamos o procedimento no seguinte exemplo:
Exemplo: Seja o sistema linear
3x1 + x2 + 6x3 = 2
2x1 + x2 + 3x3 = 7
x1 + x2 + x3 = 4
Substituiremos a (2a. linha) por
{
(2a. linha)− 23 (1a. linha)
}
, isto e´
(2a. linha) 2x1 + x2 + 3x3 = 7
−23(1a. linha) −233x1 − 23x2 − 236x3 = −232
0x1 +
1
3x2 − x3 = 173
o sistema linear se transforma
3x1 + x2 + 6x3 = 2
0x1 +
1
3x2 − x3 = 173
x1 + x2 + x3 = 4
Agora substituiremos a (3a. linha) por
{
(3a. linha)− 13 (1a. linha)
}
, isto e´
(3a. linha) x1 + x2 + x3 = 4
−13(1a. linha) −133x1 − 13x2 − 136x3 = −132
0x1 +
2
3x2 − x3 =
10
3
19
e o sistema linear se torna
3x1 + x2 + 6x3 = 2
0x1 +
1
3x2 − x3 =
17
3
0x1 +
2
3x2 − x3 =
10
3
Enfim, substituiremos a (3a. linha) por {(3a. linha)− 2(2a. linha)}, isto e´
(3a. linha) 0x1 +
2
3x2 − x3 = 103
−2(2a. linha) −2 · 0x1 − 213x2 − 2x3 = −2173
0x1 + 0x2 + x3 = − 243
resultando no seguinte sistema linear
3x1 + x2 + 6x3 = 2
0x1 +
1
3x2 − x3 = 173
0x1 + 0x2 + x3 = −243
ou 
3x1 + x2 + 6x3 = 2
1
3x2 − x3 = 173
x3 = −243
que e´ triangular superior, logo de soluc¸a˜o imediata.
x3 = −8, x2 = −7, x1 = 19
20
Caso Geral
Num primeiro passo do algoritmo um mu´ltiplo adequado da primeira linha e´ subtra´ıda de todas as
outras equac¸o˜es do sistema de forma que os coeficientes de x1 se anulem, e dessa forma restando x1
somente na primeira equac¸a˜o. Isso e´ poss´ıvel se a11 6= 0, condic¸a˜o que pode ser obtida rearranjando
as equac¸o˜es do sistema ate´ que pelo menos um ai1 6= 0 (se for poss´ıvel), como veremos mais adiante.
Ao inve´s de trabalhar com as equac¸o˜es propriamente ditas, poder´ıamos efetuar as operac¸o˜es sobre a
matriz estendida com o segundo membro que corresponde a um sistema linear completo.
(A,b) =

a11 a12 a13 a14 · · · a1n b1
a21 a22 a23 a24 · · · a2n b2
a31 a32 a33 a34 · · · a3n b3
a41 a42 a43 a44 · · · a4n b4
...
...
...
...
. . .
...
...
an1 an2 an3 an4 · · · ann bn

(ii) ← (ii) − a21a11 (i)
(iii) ← (iii) − a31a11 (i)
(iv) ← (iv) − a41a11 (i)
(n) ← (n) − an1a11 (i)
Vejamos as operac¸o˜es da primeira linha: Substituiremos a (2a. linha) por
{
(2a. linha)− a21a11 (1a. linha)
}
,
isto e´
(ii) a21x1 + a22x2 + a23x3 · · · + a2nxn = b2
−a21a11 (i) −
a21
a11a11x1 −
a21
a11a12x2 −
a21
a11a13x3 · · · −
a21
a11a1nxn = −
a21
a11 b1
{
a21 − a21
a11
a11
}
︸ ︷︷ ︸
=0
x1 +
{
a22 − a21a11a12
}
x2 +
{
a23 − a21a11 a13
}
x3 · · · +
{
a2n − a21a11a1n
}
xn =
{
b2 − a21a11 b1
}
Observe que os mu´ltiplos da primeira linha sa˜o calculados da seguinte maneira, e´ a raza˜o entre o
coeficiente que se dejesa anular e o elemento a11 da diagonal da primeira linha.
21
Logo o primeiro passo do processo de eliminac¸a˜o de Gauss transforma o sistema acima (A,b)
num sistema da forma
(A′, b′) =

a′11 a
′
12 a
′
13 a
′
14 · · · a′1n b′1
0 a′22 a
′
23 a
′
24 · · · a′2n b′2
0 a′32 a
′
33 a
′
34 · · · a′3n b′3
0 a′42 a
′
43 a
′
44 · · · a′4n b′4
...
...
...
...
. . .
...
...
0 a′n2 a
′
n3 a
′
n4 · · · a′nn b′n

esta primeira etapa pode ser descrita como:
Etapa 1 Para k = 2, 3, . . . , n, subtraia da linha (k) o mu´ltiplo
lk1 =
ak1
a11
da linha (1) da matriz (A, b). O resultado sera´ a matriz desejada (A′, b′).
A transic¸a˜o (A, b)→ (A′, b′) pode ser descrita usando multiplicac¸a˜o de matrizes
(A′, b′) = G1(A, b)
onde G1 e´ uma matriz triangular inferior da seguinte forma
G1 =

1 0 0 0 · · · 0
−l21 1 0 0 · · · 0−l31 0 1 0 · · · 0
−l41 0 0 1 · · · 0
...
...
...
...
. . .
...
−ln1 0 0 0 · · · 1

onde os coeficientes l21, l31, l41, . . . , ln1 sa˜o dados respectivamente por
a21
a11
, a31a11
, a41a11
, . . . , an1a11
.
Matrizes tais como a acima (G1), as quais diferem da matriz identidade em uma linha somente
sa˜o chamadas matrizes de Frobenius. G1 e´ na˜o-singular. Observe que:
G−11 =

1 0 0 0 · · · 0
l21 1 0 0 · · · 0
l31 0 1 0 · · · 0
l41 0 0 1 · · · 0
...
...
...
...
. . .
...
ln1 0 0 0 · · · 1

22
Por esta raza˜o os sistemas Ax = b e A′x = b′ teˆm a mesma soluc¸a˜o: Ax = b implica que
G1Ax = A
′x = b′ = G1b, e A
′x = b′ implica que G−11 A
′x = Ax = b = G−11 b
′.
O elemento a11 na diagonal da primeira linha na Etapa 1 e´ chamado elemento pivoˆ ou simples-
mente pivoˆ, a linha que conte´m o pivoˆ e´ chamada linha pivotal.
Observe que o sistema resultante dessa primeira etapa na˜o possui a varia´vel x1 nas linhas
abaixo da linha pivotal, isto e´, as linhas 2, 3, 4, . . ., n, tornam-se agora um sistema de ordem n − 1,
independente da varia´vel x1. Logo, podemos repetir o procedimento anterior usando agora o elemento
a′22 (a
′
22 6= 0) como pivoˆ e a segunda linha como linha pivotal. Enfim, num segundo passo do algoritmo
um mu´ltiplo adequ¨ado da segunda linha e´ subtra´ıdo de todas as linhas abaixo da segunda linha, de
forma que todos os elementos de x2 abaixo de a22 se anulem. Isto e´,
(A′, b′) =

a′11 a
′
12 a
′
13 a
′
14 · · · a′1n b′1
0 a′22 a
′
23 a
′
24 · · · a′2n b′2
0 a′32 a
′
33 a
′
34 · · · a′3n b′3
0 a′42 a
′
43 a
′
44 · · · a′4n b′4
...
...
...
...
. . .
...
...
0 a′n2 a
′
n3 a
′
n4 · · · a′nn b′n

(iii) ← (iii) − a
′
32
a′22
(ii)
(iv) ← (iv) − a
′
42
a′22
(ii)
(n) ← (n) − a
′
n2
a′22
(ii)
Logo o segundo passo do processo de eliminac¸a˜o de Gauss transforma o sistema acima (A′, b′) em um
sistema da forma
(A′′, b′′) =

a′′11 a
′′
12 a
′′
13 a
′′
14 · · · a′′1n b′′1
0 a′′22 a
′′
23 a
′′
24 · · · a′′2n b′′2
0 0 a′′33 a
′′
34 · · · a′′3n b′′3
0 0 a′′43 a
′′
44 · · · a′′4n b′′4
...
...
...
...
. . .
...
...
0 0 a′′n3 a
′′
n4 · · · a′′nn b′′n

agora a segunda etapa pode ser descrita como:
Etapa 2 Para k = 3, . . . , n, subtraia da linha (k) o mu´ltiplo
lk2 =
a′k2
a′22
23
da linha (2) da matriz (A′, b′). O resultado sera´ a matriz desejada (A′′, b′′).
A transic¸a˜o (A′, b′)→ (A′′, b′′) tambe´m pode ser descrita usando multiplicac¸a˜o de matrizes
(A′′, b′′) = G2(A
′, b′)
onde G2 e´ uma matriz triangular inferior da seguinte forma
G2 =

1 0 0 0 · · · 0
0 1 0 0 · · · 0
0 −l32 1 0 · · · 0
0 −l42 0 1 · · · 0
...
...
...
...
. . .
...
0 −ln2 0 0 · · · 1

onde os coeficientes l32, l42, l52, . . . , ln2 sa˜o dados respectivamente por
a′32
a′22
,
a′42
a′22
,
a′52
a′22
, . . . ,
a′n2
a′22
.
Assim como a matriz G1, G2 e´ uma matriz de Frobenius e possui inversa da forma
G−12 =

1 0 0 0 · · · 0
0 1 0 0 · · · 0
0 l32 1 0 · · · 0
0 l42 0 1 · · · 0
...
...
...
...
. . .
...
0 ln2 0 0 · · · 1

Assim como na etapa anterior, podemos mostrar que A′x = b′ e A′′x = b′′ teˆm a mesma
soluc¸a˜o.
O elemento a′22 na diagonal da segunda linha na Etapa 2 agora e´ chamado pivoˆ e a segunda
linha e´ agora a linha pivotal.
Observando o sistema resultante vemos que a partir da terceira linha as equac¸o˜es na˜o possuem
nenhuma dependeˆncia das inco´gnitas x1 e x2 e portanto podemos visualizar um sistema de ordem
n− 2 com inco´gnitas x3, x4, . . . , xn e enta˜o repetir o procedimento anterior.
(A′′, b′′) =

a′′11 a
′′
12 a
′′
13 a
′′
14 · · · a′′1n b′′1
0 a′′22 a
′′
23 a
′′
24 · · · a′′2n b′′2
0 0 a′′33 a
′′
34 · · · a′′3n b′′3
0 0 a′′43 a
′′
44 · · · a′′4n b′′4
...
...
...
...
. . .
...
...
0 0 a′′n3 a
′′
n4 · · · a′′nn b′′n

(iv) ← (iv) − a
′′
43
a′′33
(iii)
(n) ← (n) − a
′′
n3
a′′33
(iii)
24
Como nas etapas anteriores a eliminac¸a˜o de Gauss transforma o sistema acima (A′′, b′′) em um sistema
da forma
(A′′′, b′′′) =

a′′′11 a
′′′
12 a
′′′
13 a
′′′
14 · · · a′′′1n b′′′1
0 a′′′22 a
′′′
23 a
′′′
24 · · · a′′′2n b′′′2
0 0 a′′′33 a
′′′
34 · · · a′′′3n b′′′3
0 0 0 a′′′44 · · · a′′′4n b′′′4
...
...
...
...
. . .
...
...
0 0 0 a′′′n4 · · · a′′′nn b′′′n

e a terceira etapa sera´ descrita como:
Etapa 3 Para k = 4, 5, . . . , n, subtraia da linha (k) o mu´ltiplo
lk3 =
a′′k3
a′′33
da linha (3) da matriz (A′′, b′′). O resultado sera´ o sistema desejado (A′′′, b′′′).
A transic¸a˜o (A′′, b′′)→ (A′′′, b′′′) sera´ descrita por
(A′′′, b′′′) = G3(A
′′, b′′)
onde G3 e´ da forma
G3 =

1 0 0 0 · · · 0
0 1 0 0 · · · 0
0 0 1 0 · · · 0
0 0 −l43 1 · · · 0
...
...
...
...
. . .
...
0 0 −ln3 0 · · · 1

onde os coeficientes l43, l53, . . . , ln3 sa˜o dados por
a′′43
a′′33
,
a′′53
a′′33
, . . . ,
a′′n3
a′′33
respectivamente.
Como G1 e G2, G3 possui sua inversa da forma
G−13 =

1 0 0 0 · · · 0
0 1 0 0 · · · 0
0 0 1 0 · · · 0
0 0 l43 1 · · · 0
...
...
...
...
. . .
...
0 0 ln3 0 · · · 1

25
Mais uma vez podemos mostrar que A′′x = b′′ e A′′′x = b′′′ teˆm a mesma soluc¸a˜o.
O pivoˆ nesta etapa e´ o elemento a′′33 na diagonal da terceira linha, e esta e´ chamada linha pivotal.
O sistema resultante a partir da quarta linha na˜o possue dependeˆncia das inco´gnitas x1, x2 e x3
sendo assim um sistema de ordem n−3 com inco´gnitas x4, x5, . . . , xn e mais uma vez podemos repetir
o procedimento no novo sistema reduzido.
Procedendo sucessivamente de maneira ana´loga, reduziremos o sistema original a um sistema
triangular superior, que pode ser facilmente resolvido.
Usando a representac¸a˜o matricial da eliminac¸a˜o de Gauss temos
Ax = b ⇐⇒ Ax = b
A′x = b′ ⇐⇒ G1Ax = G1b
A′′x = b′′ ⇐⇒ G2G1Ax = G2G1b
A′′′x = b′′′ ⇐⇒ G3G2G1Ax = G3G2G1b
...
...
...
...
...
...
A(n−1)︸ ︷︷ ︸
U
x = b(n−1)︸ ︷︷ ︸
c
⇐⇒ Gn−1 . . .G2G1A︸ ︷︷ ︸
U
x = Gn−1 . . .G2G1b︸ ︷︷ ︸
c
Ux = c ⇐⇒ Ux = Gn−1 . . .G2G1b
Premultiplicando o sistema acima pela inversa de Gn−1 que sabemos que existe
G−1n−1Ux = G
−1
n−1Gn−1︸ ︷︷ ︸
I
Gn−2 . . .G2G1b
ou
G−1n−1Ux = Gn−2 . . .G2G1b
Analogamente premultiplicamos o sistema por G−1n−2
G−1n−2G
−1
n−1Ux = G
−1
n−2Gn−2︸ ︷︷ ︸
I
Gn−3 . . .G2G1b
logo
G−1n−2G
−1
n−1Ux = Gn−3 . . .G2G1b
Da mesma forma podemos premultiplicar o sistema por G−1n−3
G−1n−3G
−1
n−2G
−1
n−1Ux = G
−1
n−3Gn−3︸ ︷︷ ︸
I
Gn−4 . . .G2G1b
logo
G−1n−3G
−1
n−2G
−1
n−1Ux = Gn−4 . . .G2G1b
26
Procedendo da mesma forma, premultiplicamos sucessivamente o sistema porG−1n−4, G
−1
n−5, G
−1
n−6, . . .G
−1
2 , G
−1
1 ,
obtendo enfim
G−11 G
−1
2 G
−1
3 . . .G
−1
n−3G
−1
n−2G
−1
n−1Ux = b
Vimos que a inversa de cada matriz de Frobenius e´ fa´cil de calcular. Temos agora que calcular o
produto dessas matrizes. Pore´m, cada matriz Gi e´ triangular inferior, logo o produto delas e´ tambe´m
triangular inferior, ale´m disso devido a estrutura de cada uma delas este produto possui a forma
G−11 G
−1
2 G
−1
3 . . .G
−1
n−3G
−1
n−2G
−1
n−1 =
=

1 0 0 0 · · · 0
l21 1 0 0 · · · 0
l31 0 1 0 · ·· 0
l41 0 0 1 · · · 0
...
...
...
...
. . .
...
ln1 0 0 0 · · · 1

︸ ︷︷ ︸
G
−1
1

1 0 0 0 · · · 0
0 1 0 0 · · · 0
0 l32 1 0 · · · 0
0 l42 0 1 · · · 0
...
...
...
...
. . .
...
0 ln2 0 0 · · · 1

︸ ︷︷ ︸
G
−1
2
· · ·

1 0 0 · · · 0 0
0 1 0 · · · 0 0
0 0 1 · · · 0 0
...
...
...
. . .
...
...
0 0 0 · · · 1 0
0 0 0 · · · ln,n−1 1

︸ ︷︷ ︸
G
−1
n−1
=
=

1 0 0 · · · 0 0
l21 1 0 · · · 0 0
l31 l32 1 · · · 0 0
l41 l42 l43 · · ·
... 0
...
...
...
. . . 1
...
ln1 ln2 ln3 · · · ln,n−1 1

︸ ︷︷ ︸
L
= L
Observando a matriz L, vemos que seus elementos sa˜o os valores dos mu´ltiplos utilizados no processo
de eliminac¸a˜o do me´todo de eliminac¸a˜o de Gauss.
Decomposic¸o˜es triangulares tem grande importaˆncia na soluc¸a˜o de sistemas de equac¸o˜es lineares.
Se esta decomposic¸a˜o e´ conhecida para uma matriz A, enta˜o o sistema
Ax = b
pode ser imediatamente resolvido para qualquer segundo membro b. Isto e´,
Ax = b =⇒ LUx = b =⇒
{
Ly = b −→ y
Ux = y −→ x
Observac¸a˜o: Nem sempre toda matriz invers´ıvel possui uma decomposic¸a˜o da forma acima, a`s vezes,
e´ necessa´ria uma conveniente troca de linhas da matriz para a obtenc¸a˜o da fatorac¸a˜o.
Resumindo temos os seguintes algoritmos:
Eliminac¸a˜o de Gauss:
27
Para k = 1, 2, . . . , n− 1
Para i = k + 1, . . . , n
lik = aik/akk
Para j = k + 1, . . . , n
aij = aij − likakj
bi = bi − likbk
Exemplo:
3x1 + x2 + 6x3 = 2
1x1 + x2 + x3 = 4
2x1 + x2 + 3x3 = 7
Soluc¸a˜o:
3 1 6 | 2
1 1 1 | 4
2 1 3 | 7
 (ii) ← (ii) −1/3(i)
(iii) ← (iii) −2/3(i)
3 1 6 | 2
0 2/3 −1 | 10/3
0 1/3 −1 | 17/3

(iii) ← (iii) −1/2(ii)
3 1 6 | 2
0 2/3 −1 | 10/3
0 0 −1/2 | 4

Resp: (19;−7;−8)
enta˜o
L =

1 0 0
1/3 1 0
2/3 1/2 1
 e U =

3 1 6
0 2/3 −1
0 0 −1/2

Se possu´ımos a fatorac¸a˜o LU da matriz A o sistema acima seria resolvido da seguinte maneira.
Fatorac¸a˜o LU com pivoˆ nulo.
−x1 + 2x2 + 3x3 + x4 = 1
2x1 − 4x2 − 5x3 − x4 = 0
−3x1 + 8x2 + 8x3 + x4 = 2
x1 + 2x2 − 6x3 + 4x4 = −1
28

−1 2 3 1 | 1
2 −4 −5 −1 | 0
−3 8 8 1 | 2
1 2 −6 4 | −1

(ii) ← (ii) − 2−1(i)
(iii) ← (iii) − −3−1(i)
(iv) ← (iv) − 1−1(i)
=⇒ L =

1 0 0 0
−2 1 0 0
3 ? 1 0
−1 ? ? 1


−1 2 3 1 | 1
0 0 1 1 | 2
0 2 −1 −2 | −1
0 4 −3 5 | 0

trocando a segunda e terceira linha contornamos o pivoˆ nulo
=⇒ L =

1 0 0 0
3 1 0 0
−2 ? 1 0
−1 ? ? 1

Observe que os elementos de L abaixo da diagonal sa˜o tambe´m permutados.
−1 2 3 1 | 1
0 2 −1 −2 | −1
0 0 1 1 | 2
0 4 −3 5 | 0

(iii) ← (iii) − 02(ii)
(iv) ← (iv) − 42(ii)
=⇒ L =

1 0 0 0
3 1 0 0
−2 0 1 0
−1 2 ? 1

29

−1 2 3 1 | 1
0 2 −1 −2 | −1
0 0 1 1 | 2
0 0 −1 9 | 2

(iv) ← (iv) − −11 (iii)
=⇒ L =

1 0 0 0
3 1 0 0
−2 0 1 0
−1 2 −1 1


−1 2 3 1 | 1
0 2 −1 −2 | −1
0 0 1 1 | 2
0 0 0 10 | 4

Resp: ( 285 ;
7
10 ;
8
5 ;
2
5)
Resumindo temos a fatorac¸a˜o PA = LU .
L =

1 0 0 0
3 1 0 0
−2 0 1 0
−1 2 −1 1

U =

−1 2 3 1
0 2 −1 −2
0 0 1 1
0 0 0 10

Calculando o produto LU
1 0 0 0
3 1 0 0
−2 0 1 0
−1 2 −1 1

·

−1 2 3 1
0 2 −1 −2
0 0 1 1
0 0 0 10

=

−1 2 3 1
−3 8 8 1
2 −4 −5 −1
1 2 −6 4

= PA
Veremos a seguir, que por razo˜es nume´ricas trocamos linhas do sistema para utilizar um pivoˆ melhor,
ate´ mesmo quando temos um pivoˆ diferente de zero.
30
2.3.2 Sobre erros de arredondamento e Sistemas Mal Condicionados (MUDAR)
Teoricamente a soluc¸a˜o de um sistema linear na˜o singular esta´ perfeitamente estabelecida. Na elim-
inac¸a˜o de Gauss pode ser necessa´rio algumas trocas de linhas, mas sempre sera´ poss´ıvel resolver
corretamente (teoricamente) o sistema. A pra´tica, pore´m e´ diferente.
Lembre-se que para um sistema linear de tamanho pequeno, digamos 100×100, a Eliminac¸a˜o de
Gauss envolve aproximadamente 300.000 operac¸o˜es aritme´ticas (n3/3). Para cada operac¸a˜o podemos
esperar um erro de arredondamento.
A questa˜o e´, como estes erros contribuem para o erro final na soluc¸a˜o?
Os exemplos abaixo podem ilustrar alguns pontos importantes sobre os erros de arredondamento.
Sejam duas matrizes,
A =
[
1 1
1 1,0001
]
e A′ =
[
0,0001 1
1 1
]
O primeiro ponto e´: Algumas matrizes sa˜o extremamente sens´ıveis a` pequenas mu-
danc¸as, e outras na˜o.
Qualitativamente A e´ quase singular enquanto A′ na˜o e´. Se trocarmos o u´ltimo elemento de A
para a22 = 1, a matriz se torna singular. Considere agora dois segundos membros pro´ximos para o
sistema Ax = b{
x1 + x2 = 2
x1 + 1,0001x2 = 2
e
{
x1 + x2 = 2
x1 + 1,0001x2 = 2,0001
A soluc¸a˜o do primeiro sistema e´ x1 = 2, x2 = 0; a soluc¸a˜o do segundo sistema e´ x1 = x2 = 1.
Uma mudanc¸a na quinta casa decimal de b foi amplificada para uma mudanc¸a na primeira casa
decimal da soluc¸a˜o. Nenhum me´todo nume´rico pode evitar tal sensibilidade a pequenas pertubac¸o˜es.
O mal-condicionamento pode se modificado de um lugar para outro, mas na˜o pode ser removido.
A soluc¸a˜o real do sistema e´ muito sens´ıvel, e a soluc¸a˜o calculada computacionalmente na˜o pode ser
menos sens´ıvel.
Exemplo gra´fico: =⇒ retas quase paralelas.
O segundo ponto e´: Mesmo uma matriz bem-condicionada pode ser afetada por um
algoritmo.
Infelizmente para a matriz A′, o processo de Eliminac¸a˜o de Gauss Cla´ssica na˜o e´ um bom al-
goritmo. Suponha que 0,0001 seja utilizado como o primeiro pivoˆ, e 10000 vezes a primeira linha seja
subtra´ıda da segunda. O elemento na posic¸a˜o (22) da matriz tornar-se-a´ −9999, que arredondado se
transforma em −10000. Os vest´ıgios do valor 1 que estava originalmente naquela posic¸a˜o desaparece-
ram.
Considere o exemplo:{
0,0001x1 + x2 = 1
x1 + x2 = 2 (ii)← (ii)− 10,0001(i) (ii)← (ii)− 10000(i)
31
−
x1 + x2 = 2
x1 + 10000x2 = 10000
− 9999x2 = −9998
Apo´s a eliminac¸a˜o a segunda equac¸a˜o poderia tornar-se
−9999x2 = −9998, ou x2 = 0,99990
Um arredondamento resultaria em −10000x2 = −10000, ou x2 = 1. Independentemente, a
alterac¸a˜o da segunda equac¸a˜o na˜o resultou em uma soluc¸a˜o ”errada” para x2. Entretanto, quando e´
feita a retro-substituic¸a˜o a primeira equac¸a˜o com o valor correto de x2 torna-se
0,0001x1 + 0,9999 = 1 ou x1 = 1
Se ao inve´s disso usarmos o valor x2 = 1 que esta´ incorreto somente na quarta casa decimal,
teremos:
0,0001x1 + 1 = 1 ou x1 = 0
O valor calculado computacionalmente e´ completamente erroˆneo. Mesmo a matriz A′ sendo
bem-condicionada o processo de Eliminac¸a˜o de Gauss Cla´ssico e´ extremamente insta´vel.
O pivoˆ de pequeno valor (= 0,0001) trouxe instabilidade, e a cura e´ a troca de linhas. Esse e´ o
terceiro ponto:
Teoricamente apenas os pivoˆs nulos forc¸am a troca de linhas na Eliminac¸a˜o de
Gauss, e um pivoˆ pequeno forc¸a uma troca pra´tica.
A menos que se tenha garantias especiais, um computador precisa comparar cada pivoˆ com todos
os poss´ıveis pivoˆ na mesma coluna. Escolhendo entre esses candidatos ocom maior valor absoluto, e
trocando as respectivas linhas tal que o maior valor seja o novo pivoˆ, teremos a chamada Eliminac¸a˜o
de Gauss com pivoteamento Parcial.
Outro exemplo de Sistema Mal-Condicionado
Seja o sistema
10x1 + 7x2 + 8x3 + 7x4 = 32
7x1 + 5x2 + 6x3 + 5x4 = 23
8x1 + 6x2 + 10x3 + 9x4 = 33
7x1 + 5x2 + 9x3 + 10x4 = 31
32
se substituirmos x = ( 9,2 ; −12,6 ; 4,5 ; −1,1 ) no sistema acima obtemos, no lado esquerdo:
b1 = 32,1
b2 = 22,9
b3 = 33,1
b4 = 30,9
o que nos leva a crer que x e´ uma boa aproximac¸a˜o da soluc¸a˜o do sistema.
Mas, se fizermos x = ( 1,82 ; −0,36 ; 1,35 ; 0,79 ) obtemos
b1 = 32,01
b2 = 22,99
b3 = 33,01
b4 = 30,99
que e´ outra aproximac¸a˜o da soluc¸a˜o, pore´m, ainda longe do valor correto que e´ x = (1; 1; 1; 1).
33
Estrate´gias de Pivoteamento
Vimos que quando encontramos um pivoˆ nulo temos que procurar um outro elemento para substitu´ı-lo.
Entretanto, como tambe´m ja´ vimos o me´todo da eliminac¸a˜o de Gauss pode ser insta´vel se utilizamos
um pivoˆ com valor muito pequeno, isto sugere que sempre seja feita um selec¸a˜o para a escolha de um
novo pivoˆ. Isto e´ feito geralmente de duas maneiras chamadas, pivoteamento parcial e pivoteamento
total.
Pivoteamento parcial
Nesta estrate´gia a pesquisa por um novo pivoˆ e´ feita na mesma coluna do pivoˆ natural (aquele que
e´ usado na eliminac¸a˜o de Gauss cla´ssica), os elementos candidatos ao cargo de pivoˆ sa˜o os situados
abaixo do pivoˆ natural. O eleito sera´ o de maior valor absoluto, isto e´,
| ar1 | = max
i
| ai1 | i = 1, 2, 3, . . . , n
enta˜o trocamos as linhas r e 1 tornando ar1 o novo pivoˆ e continuamos a eliminac¸a˜o de Gauss.
Na Etapa 2 a pesquisa pelo novo pivoˆ e´ feita agora na segunda coluna abaixo do pivoˆ a′22, isto
e´,
| ar2 | = max
i
| ai1 | i = 2, 3, . . . , n
Na pra´tica o me´todo da eliminac¸a˜o de Gauss (ou Fatorac¸a˜o LU) sempre e´ usado com alguma
selec¸a˜o de pivoˆ, principalmente com a estrate´gia de pivoteamento parcial.
Observac¸o˜es:
a) Quando calculamos a fatorac¸a˜o LU de uma matriz A usando pivoteamento parcial, devemos de
alguma forma guardar as trocas de linhas realizadas na eliminac¸a˜o para a posterior trocas das
linhas do vetor segundo membro.
Pivoteamento total
No pivoteamento parcial a pesquisa por um novo pivoˆ e´ restrita a uma coluna (aquela que conte´m o pivoˆ
natural). No pivoteamento total a pesquisa e´ feita em toda a matriz de coeficientes e novo pivoˆ sera´
aquele que tiver o maior valor absoluto. Neste caso apo´s a escolha devemos trocar convenientemente
as linhas e colunas do sistema para continuar o processo de eliminac¸a˜o.
Observac¸o˜es:
a) Como nesta estrate´gia de pivoteamento trocamos colunas do sistema deve-se atentar para a troca
na ordem das inco´gnitas visto que estas esta˜o associadas a cada coluna do sistema.
b) O pivoteamento total e´ muito pouco utilizado devido ao alto custo da pesquisa por um novo pivoˆ,
na k-e´sima etapa da fatorac¸a˜o sa˜o necesssa´rios (n− k+1)2 testes para se determinar quem sera´
o novo pivoˆ, enquanto que no pivoteamento parcial o nu´mero de testes necessa´rios e´ igual a
(n− k + 1), visto que a procura e´ restrita a uma u´nica coluna.
34
2.3.3 Custo da Eliminac¸a˜o Gaussiana
Quantas operac¸o˜es aritme´ticas sa˜o necessa´rias para se resolver um sistema de n equac¸o˜es e n inco´gnitas?
Suporemos que na˜o sejam necessa´rias trocas de linhas, isto e´, na˜o existam pivoˆs nulos nem os
erros de arrendondamento.
Vejamos em primeiro lugar somente as operac¸o˜es na matriz (ignoraremos inicialmente as operac¸o˜es
no segundo membro).
Essas operac¸o˜es sa˜o de dois tipos.
Uma operac¸a˜o e´ a divisa˜o pelo pivoˆ, para encontrar o mu´ltiplo da linha pivotal que devera´ ser
subtra´ıdo. E a seguir, efetuamos realmente essa subtrac¸a˜o.
Consideremos cada divisa˜o e cada multiplicac¸a˜o–subtrac¸a˜o uma u´nica operac¸a˜o.
No in´ıcio, quando a primeira equac¸a˜o tem n elementos na matriz, sa˜o necessa´rias n operac¸o˜es
para cada zero(0) obtido na primeira coluna de cada linha ( 1 operac¸a˜o para determinarmos o mu´ltiplo
(divisa˜o) e n − 1 para os outros elementos da linha fatorada (multiplicac¸o˜es e subtrac¸o˜es)). Existem
n−1 linhas abaixo da primeira linha, assim a primeira etapa da eliminac¸a˜o necessita de n(n−1) = n2−n
operac¸o˜es (outra abordagem e´ a seguinte: todos os n2 elementos precisam ser modificados, menos os
n elementos da primeira linha → n2 −n). Agora, observe que as etapas seguintes sa˜o mais ”ra´pidas“,
porque as equac¸o˜es se tornam progressivamente menores. Quando a eliminac¸a˜o e´ feita em k equac¸o˜es
(k < n), somente k2 − k operac¸o˜es sa˜o necessa´rias para zerar a coluna abaixo do pivoˆ (pela mesma
raza˜o usada na primeira linha).
Juntas, o nu´mero de operac¸o˜es na matriz e´ a soma de k2−k operac¸o˜es para k variando de 1 ate´
n. Isto e´,
n∑
k=1
k2 − k =
n∑
k=1
k2 −
n∑
k=1
k =
= (12 + 22 + . . .+ n2)− (1 + 2 + . . .+ n) = n(n + 1)(2n+ 1)
6
− n(n+ 1)
2
=
n3 − n
3
≈ n
3
3
Observac¸a˜o:
Se o n e´ muito grande, uma estimativa do nu´mero de operac¸o˜es e´ 13n
3.
No segundo membro na primeira etapa temos n − 1 operac¸o˜es (uma multiplicac¸a˜o–subtrac¸a˜o
para cada elemento do segundo membro). Na segunda etapa como temos um sistema (n−1)× (n−1),
sera˜o necessa´rias n − 2 operac¸o˜es, e assim por diante. Logo, somando todas as operac¸o˜es, teremos
(n− 1) + (n− 2) + . . .+ 2 + 1 = 1 + 2 + . . .+ (n− 1) = (n− 1)((n− 1) + 1)
2
=
n(n − 1)
2
=
=
n2 − n
2
≈ n
2
2
Observac¸a˜o:
Se o n e´ muito grande, uma estimativa do nu´mero de operac¸o˜es no segundo membro e´ 12n
2.
A retro-substituic¸a˜o e´ bem mais ”ra´pida“.
35
A u´ltima inco´gnita (xn) e´ determinada com somente uma operac¸a˜o (uma divisa˜o). A penu´ltima
inco´gnita requer 2 operac¸o˜es (uma subtrac¸a˜o–multiplicac¸a˜o e uma divisa˜o) e assim por diante. Logo
o nu´mero total de operac¸o˜es para a retrosubstituic¸a˜o e´
1 + 2 + . . .+ n =
n(n+ 1)
2
=
n2 + n
2
≈ n
2
2
Somando todas as operac¸o˜es efetuadas, temos:
n3 − n
3
+
n2 − n
2
+
n2 + n
2
=
n3 − n
3
+ n2
Observac¸a˜o:
Novamente, podemos dizer, se n for muito grande que o nu´mero de operac¸o˜es necessa´rios para
se resolver um sistema por Eliminac¸a˜o de Gauss e´ 13n
3.
36
Exemplos
Eliminac¸a˜o de Gauss
2x1 + 2x2 + x3 + x4 = 7
x1 − x2 + 2x3 − x4 = 1
3x1 + 2x2 − 3x3 − 2x4 = 4
4x1 + 3x2 + 2x3 + x4 = 12

2 2 1 1 | 7
1 −1 2 −1 | 1
3 2 −3 −2 | 4
4 3 2 1 | 12

(ii) ← (ii) − 12(i)
(iii) ← (iii) − 32(i)
(iv) ← (iv) − 42(i)

2 2 1 1 | 7
0 −2 32 −32 | −52
0 −1 −92 −72 | −132
0 −1 0 −1 | −2

(iii) ← (iii) − −1−2(ii)
(iv) ← (iv) − −1−2(ii)

2 2 1 1 | 7
0 −2 32 −32 | −52
0 0 −214 −114 | −214
0 0 −34 −14 | −34

(iv) ← (iv) − −3/4−21/4(iii)
37

2 2 1 1 | 7
0 −2 32 −32 | −52
0 0 −214 −114 | −214
0 0 0 17 | 0


2x1 + 2x2 + x3 + x4 = 7
− 2x2 + 32x3 − 32x4 = −52
− 214 x3 − 114 x4 = −214
1
7x4 = 0
Da quarta equac¸a˜o −→ x4 = 0
Da terceira equac¸a˜o −→ x3 = 1−214
{
−21
4
+
11
4
x4
}
=
1
−214
{
−21
4
+ 0
}
= 1
Da segunda equac¸a˜o −→ x2 = −1
2
{
−5
2
− 3
2
x3 +
3
2
x4
}
= −1
2
{
−5
2
− 3
2
· 1 + 3
2
· 0
}
=
8
4
= 2
Da primeira equac¸a˜o −→ x1 = 1
2
{7− 2x2 − x3 − x4} = 1
2
{7− 2 · 2− 1− 0} = 1
Resp: (1; 2; 1; 0)
38
Quando precisamos resolver va´riossistemas lineares que possuem a mesma matriz de coeficientes,
a fatorac¸a˜o LU e´ vantajosa em relac¸a˜o a eliminac¸a˜o de Gauss. Com a fatorac¸a˜o LU precisamos
tringularizar a matriz de coeficientes uma u´nica vez e armazenar os multiplicares usados que sera˜o os
coeficientes da matriz L.
Os pro´ximos exemplos ilustram esta caracter´ıtica.
Exemplo 1: do uso da fatorac¸a˜o LU (sem estrate´gia de pivoteamento)
Sejam os seguintes treˆs sistemas lineares:
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

5
9
1
−2


2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

12
21
8
−5


2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

10
10
10
10

Observe que os treˆs sistemas tem a mesma matriz de coeficientes. Vamos inicialmente usar a
eliminac¸a˜o de Gauss para resolveˆ-los.
39
Primeiro sistema linear
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

5
9
1
−2

Segundo sistema linear
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

12
21
8
−5

Terceiro sistema linear
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

10
10
10
10

Fatorac¸a˜o LU com e sem pivoteamento
1) Calcular a fatorac¸a˜o LU da matriz abaixo e calcular seu determinante
A =

2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4

40
usaremos as posic¸o˜es da matriz abaixo da diagonal principal que forem sendo zeradas para armazenar
os elementos da matriz L.
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4

(ii) ← (ii) − 42 (i)
(iii) ← (iii) − −22 (i)
(iv) ← (iv) − 02 (i)

2 −1 4 0
—-
2 | 1 −3 1
|
−1 | 1 2 3
|
0 | 3 −9 4

(iii) ← (iii) − 11 (ii)
(iv) ← (iv) − 31 (ii)
2 −1 4 0
—-
2 | 1 −3 1
—-
−1 1 | 5 2
|
0 3 | 0 1

(iv) ← (iv) − 05 (iii)
2 −1 4 0
—-
2 | 1 −3 1
—-
−1 1 | 5 2
—-
0 3 0 | 1

L =

1 0 0 0
2 1 0 0
−1 1 1 0
0 3 0 1
 e U =

2 −1 4 0
0 1 −3 1
0 0 5 2
0 0 0 1

logo
detA = detLU = detL · detU = 1 · detU = detR = 2× 1× ×5× 1 = 10
41
como o determinante da matriz e´ diferente de zero enta˜o o sistema linear abaixo possui uma u´nica
soluc¸a˜o.
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

5
9
1
−2


2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4


x1
x2
x3
x4

=

10
50
1
2

ache a soluc¸a˜o deste sistema usando a decomposic¸a˜o LU de A.
Ax = b =⇒ LUx = b =⇒
{
Ly = b −→ y
Ux = y −→ x
Ly = b −→

1 0 0 0
2 1 0 0
−1 1 1 0
0 3 0 1


y1
y2
y3
y4

=

5
9
1
−2

−→ y1 = 5
−→ y2 = −1
−→ y3 = 7
−→ y4 = 1
Ux = y −→

2 −1 4 0
0 1 −3 1
0 0 5 2
0 0 0 1


x1
x2
x3
x4

=

5
−1
7
1

−→ x1 = 1
−→ x2 = 1
−→ x3 = 1
−→ x4 = 1
Agora repetiremos o problema usando pivoteamento parcial.
2 −1 4 0
4 −1 5 1
−2 2 −2 3
0 3 −9 4

42
Com pivoteamento parcial precisamos trocar a primeira com a segunda linha para que novo pivoˆ seja
o 4. 
4 −1 5 1
2 −1 4 0
−2 2 −2 3
0 3 −9 4

(ii) ← (ii) − 24 (i)
(iii) ← (iii) − −24 (i)
(iv) ← (iv) − 04 (i)
4 −1 5 1
—-
1/2 | −1/2 3/2 −1/2
|
−1/2 | 3/2 1/2 7/2
|
0 | 3 −9 4

Precisamos agora de nova troca de linhas, isto e´, a segunda linha sera´ trocada com a quarta linha
4 −1 5 1
—-
0 | 3 −9 4
|
−1/2 | 3/2 1/2 7/2
|
1/2 | −1/2 3/2 −1/2

(iii) ← (iii) − 3/23 (ii)
(iv) ← (iv) − −1/23 (ii)
4 −1 5 1
—-
0 | 3 −9 4
—-
−1/2 1/2 | 5 3/2
|
1/2 −1/6 | 0 1/6

(iv) ← (iv) − 05 (iii)
Temos enfim
4 −1 5 1
—-
0 | 3 −9 4
—-
−1/2 1/2 | 5 3/2
—-
1/2 −1/6 0 | 1/6

43
e
L =

1 0 0 0
0 1 0 0
−1/2 1/2 1 0
1/2 −1/6 0 1

e U =

4 −1 5 1
0 3 −9 4
0 0 5 3/2
0 0 0 1/6

se calcularmos o produto LU obtemos
LU =

4 −1 5 1
0 3 −9 4
−2 2 −2 3
2 −1 4 0

= PA
que na˜o e´ igual a matriz A, pore´m o resultado e´ igual a A com as mesmas trocas de linhas realizadas
durante a fatorac¸a˜o.
No produto LU , P e´ a matriz de permutac¸a˜o relativa a`s trocas de linhas e P = P 2P 1. P 1
representa a troca das 1a. e 2a. linhas e P 2 representa a troca das 2a. e 4a. linhas. Na forma matricial
temos
P =

0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0

=

1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0


0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1

= P 2P 1
Para usarmos a fatorac¸a˜o acima para resolver um sistema linear temos que permutar as linhas do
segundo membro da mesma forma que foram feitas na matriz durante a fatorac¸a˜o. Logo inicialmente
trocamos a primeira e a segunda linhas e a seguir trocamos a segunda e quarta linhas, resultando no
44
seguinte segundo membro.
b′ =

9
−2
1
5

45
2.4 Me´todos Iterativos
Muitos problemas pra´ticos requerem a soluc¸a˜o de grandes sistemas lineares (Ax = b) em que a matriz
A e´ esparsa, isto e´, tem relativamente poucos elementos na˜o nulos. Sistemas desse tipo surgem, por
exemplo, em aplicac¸o˜es dos me´todos de diferenc¸as finitas ou elementos finitos para aproximar a soluc¸a˜o
de problemas de valor de contorno em equac¸o˜es diferenciais parciais. Os me´todos de eliminac¸a˜o usuais,
normalmente na˜o podem ser empregados neste caso (excec¸a˜o feita as matrizes do tipo banda, quando
a largura de banda e´ pequena), pois eles tendem a gerar matrizes intermedia´rias densas e o nu´mero de
operac¸o˜es necessa´rias para a soluc¸a˜o torna-se muito grande, mesmo para os computadores modernos,
ale´m disso tais matrizes ocupariam uma memo´ria, a`s vezes, na˜o dispon´ıvel, ale´m disso existem os
erros de arredondamento. Por estas e outras razo˜es utiliza-se os me´todos iterativos para resolver tais
sistemas.
Nesta classe de me´todos partimos de uma aproximac¸a˜o inicial x(0) para a soluc¸a˜o do sistema
linear, e a partir dela geramos por um processo recursivo (repetitivo) novasaproximac¸o˜es que definem
uma sequ¨eˆncia. O me´todo sera´ bem sucedido se a sequ¨eˆncia convergir para a soluc¸a˜o do sistema.
Cada ciclo responsa´vel pela gerac¸a˜o de uma nova aproximac¸a˜o e´ chamado iterac¸a˜o. A cada iterac¸a˜o
sa˜o usadas informac¸o˜es das iterac¸o˜es anteriores. Resumindo
x(0) −→ x(1) −→ x(2) −→ x(3) −→ . . . −→ x
lim
i→∞
x(i) = x
Obviamente e´ imposs´ıvel realizar infinitas iterac¸o˜es para obter a soluc¸a˜o do sistema. Por isso adotare-
mos um crite´rio de parada.
2.4.1 Crite´rio de Parada
Uma maneira de determinar se a sequ¨eˆncia gerada pelo me´todo iterativo esta´ convergindo e´ verificar
se a diferenc¸a entre a aproximac¸a˜o e o vetor exato da soluc¸a˜o esta´ diminuindo. Seja x(i) o vetor
aproximado obtido na iterac¸a˜o i e x¯ o vetor soluc¸a˜o, podemos verificar se
‖x(i) − x¯‖ < ǫ
isto e´, se a diferenc¸a acima citada e´ menor que um valor pequeno (ǫ), onde ‖ · ‖ denota uma norma do
IR
n. Chamamos o valor escalar ǫ de toleraˆncia de parada ou simplesmente toleraˆncia.
Entretanto, como na˜o conhecemos a soluc¸a˜o do sistema (queremos na verdade determinar este
vetor), o teste acima na˜o pode ser efetuado. Substitu´ımos o teste acima pelo seguinte teste:
‖x(i+1) − x(i)‖ < ǫ
A diferenc¸a agora e´ calculada entre duas aproximac¸o˜es sucessivas.
O crite´rio empregando a diferenc¸a relativa entre aproximac¸o˜es sucessivas tambe´m e´ usado, isto
e´,
‖x(i+1) − x(i)‖
‖x(i+1)‖ < ǫ
A sec¸a˜o a seguir se dedica a` apresentar brevemente os me´todos iterativos para resoluc¸a˜o de
sistemas lineares. Nos retringiremos aos me´todos cla´ssicos.
46
2.4.2 Me´todo de Jacobi
No me´todo de Jacobi partimos do sistema original abaixo
a11x1 + a12x2 + a13x3 + a14x4 + · · ·+ a1nxn = b1
a21x1 + a22x2 + a23x3 + a24x4 + · · ·+ a2nxn = b2
a31x1 + a32x2 + a33x3 + a34x4 + · · ·+ a3nxn = b3
a41x1 + a42x2 + a43x3 + a44x4 + · · ·+ a4nxn = b4
...
...
...
...
...
...
an1x1 + an2x2 + an3x3 + an4x4 + · · ·+ annxn = bn
e o reescrevemos da maneira descrita a seguir.
Da primeira linha explicitamos a inco´gnita x1, da segunda linha a inco´gnita x2, da terceira
linha a inco´gnita x3, e assim por diante ate´ a u´ltima equac¸a˜o do sistema, onde enta˜o, explicitamos a
inco´gnita xn. Resultando assim,
x1 =
1
a11
(b1 − a12x2 − a13x3 − a14x4 − · · · − a1nxn)
x2 =
1
a22
(b2 − a21x1 − a23x3 − a24x4 − · · · − a2nxn)
x3 =
1
a33
(b3 − a31x1 − a32x2 − a34x4 − · · · − a3nxn)
x4 =
1
a44
(b4 − a41x1 − a42x2 − a43x3 − · · · − a4nxn)
...
...
xn =
1
ann
(bn − an1x1 − an2x2 − an3x3 − · · · − an,n−1xn−1)
(2.5)
47
A func¸a˜o de iterac¸a˜o e´ enta˜o definida como
x
(i+1)
1 =
1
a11
(
b1 − a12x(i)2 − a13x(i)3 − a14x(i)4 − · · · − a1nx(i)n
)
x
(i+1)
2 =
1
a22
(
b2 − a21x(i)1 − a23x(i)3 − a24x(i)4 − · · · − a2nx(i)n
)
x
(i+1)
3 =
1
a33
(
b3 − a31x(i)1 − a32x(i)2 − a34x(i)4 − · · · − a3nx(i)n
)
x
(i+1)
4 =
1
a44
(
b4 − a41x(i)1 − a42x(i)2 − a43x(i)3 − · · · − a4nx(i)n
)
...
...
x(i+1)n =
1
ann
(
bn − an1x(i)1 − an2x(i)2 − an3x(i)3 − · · · − an,n−1x(i)n−1
)
(2.6)
Para i = 0, 1, 2, . . .
Para k = 1, 2, . . . , n
x
(i+1)
k =
bk −
k−1∑
j=1
akjx
(i)
j −
n∑
j=k+1
akjx
(i)
j
 /akk
Testa Criterio de Parada
com x(0) = (x
(0)
1 , x
(0)
2 , x
(0)
3 , . . . , x
(0)
n ) dado
Assim se tivermos uma aproximac¸a˜o inicial para a soluc¸a˜o do sistema, podemos gerar uma
sequeˆncia de aproximac¸o˜es que esperamos convirja para a soluc¸a˜o.
Um Crite´rio de Convergeˆncia (Jacobi)
Mostraremos a seguir uma condic¸a˜o suficiente para a convergeˆncia do Me´todo de Jacobi.
Por ser um crite´rio somente suficiente asseguramos a convergeˆncia se as condic¸o˜es do teorema
sa˜o satisfeitas. Entretanto, nada podemos afirmar se as condic¸o˜es na˜o sa˜o satisfeitas.
Teorema 2.4.1 (Crite´rio das Linhas ou Crite´rio da Diagonal Dominante) Seja um sistema
linear Ax = b e seja
α1 =
| a12 | + | a13 | + | a14 | + · · · | a1n |
| a11 |
α2 =
| a21 | + | a23 | + | a24 | + · · · | a2n |
| a22 |
48
α3 =
| a31 | + | a32 | + | a34 | + · · · | a3n |
| a33 |
...
αn =
| an1 | + | an2 | + | an3 | + · · · | an,n−1 |
| ann |
isto e´
αi =
 n∑
j=1
j 6=i
| aij |
 / | aii | i = 1, . . . , n
Se
α = max
1≤i≤n
αi < 1
enta˜o o me´todo de Jacobi e o me´todo de Gauss-Seidel convergem para a soluc¸a˜o do sistema linear,
independentemente da aproximac¸a˜o inicial.
Exemplo:
4x1 − x2 + x3 = 4
x1 + 6x2 + 2x3 = 9
−x1 − 2x2 + 5x3 = 2
Pelo crite´rio das linhas
α1 =
| a12 | + | a13 |
| a11 | =
1 + 1
4
=
1
2
< 1
α2 =
| a21 | + | a23 |
| a22 | =
1 + 2
6
=
1
2
< 1
α3 =
| a31 | + | a32 |
| a33 | =
1 + 2
5
=
3
5
< 1
logo temos certeza de que o me´todo de Jacobi convergira´. Reescrevendo o sistema linear
x
(k+1)
1 =
1
4
(
4 + x
(k)
2 − x(k)3
)
x
(k+1)
2 =
1
6
(
9− x(k)1 − 2x(k)3
)
x
(k+1)
3 =
1
5
(
2 + x
(k)
1 + 2x
(k)
2
)
com x(0) = ~0 e ǫ = 0.01
x
(1)
1 =
1
4
(
4 + x
(0)
2 − x(0)3
)
= 14 (4 + 0− 0) = 1
x
(1)
2 =
1
6
(
9− x(0)1 − 2x(0)3
)
= 16 (9− 0− 2 · 0) = 96
x
(1)
3 =
1
5
(
2 + x
(0)
1 + 2x
(0)
2
)
= 15 (2 + 0 + 2 · 0) = 25
49

x
(1)
1
x
(1)
2
x
(1)
3

=

1
9
6
2
5

Temos que verificar se o crite´rio de parada foi satisfeito
‖x(1) − x(0)‖ < ǫ ?????
‖

1
9
6
2
5

−

0
0
0

‖ = ‖

1
9
6
2
5

‖ = 9
6
= 1.5 > ǫ
faremos enta˜o mais uma iterac¸a˜o
x
(2)
1 =
1
4
(
4 + x
(1)
2 − x(1)3
)
= 14
(
4 + 96 − 25
)
= 5140
x
(2)
2 =
1
6
(
9− x(1)1 − 2x(1)3
)
= 16
(
9− 1− 2 · 25
)
= 3630
x
(2)
3 =
1
5
(
2 + x
(1)
1 + 2x
(1)
2
)
= 15
(
2 + 1 + 2 · 96
)
= 65

x
(2)
1
x
(2)
2
x
(2)
3

=

51
40
36
30
6
5

Pelo crite´rio de parada
‖x(2) − x(1)‖ < ǫ ?????
‖

51
40
36
30
6
5

−

1
9
6
2
5

‖ = ‖

11
40
−9
30
4
5

‖ = 4
5
= 0.8 > ǫ
mais uma iterac¸a˜o. E assim por diante.
50
Outro Exemplo:
10x1 + 2x2 + x3 = 7
x1 + 5x2 + x3 = −8
2x1 + 3x2 + 10x3 = 6
Reescrevendo o sistema linear
x
(k+1)
1 =
1
10
(
7− 2x(k)2 − x(k)3
)
x
(k+1)
2 =
1
5
(
−8 − x(k)1 − x(k)3
)
x
(k+1)
3 =
1
10
(
6− 2x(k)1 − 3x(k)2
)
com
[
x(0)
]T
= (0.7;−1.6; 0.6) e ǫ = 0.05, temos:
[
x(0)
]T
= (0.7000;−1.6000; 0.6000)[
x(1)
]T
= (0.9780;−1.9800; 0.9660) =⇒ ‖x(2) − x(1)‖ = 0.3800> ǫ[
x(2)
]T
= (0.9994;−1.9888; 0.9984) =⇒ ‖x(3) − x(2)‖ = 0.0324< ǫ
2.4.3 Me´todo de Gauss-Seidel
Novamente partindo do sistema linear reescrito na forma 2.5. Assim como no me´todo do Jacobi as
u´ltimas aproximac¸o˜es para os componentes sa˜o usadas para aclcular as novas aproximac¸o˜es. Entre-
tanto, a medida que novos valores sa˜o obtidos para os componentes estes sa˜o usados ao inve´s daqueles
da aproximac¸a˜o anterior.
x
(i+1)
1 =
1
a11
(
b1 − a12x(i)2 − a13x(i)3 − a14x(i)4 − · · · − a1nx(i)n
)
x(i+1)
2 =
1
a22
(
b2 − a21x(i+1)1 − a23x(i)3 − a24x(i)4 − · · · − a2nx(i)n
)
x
(i+1)
3 =
1
a33
(
b3 − a31x(i+1)1 − a32x(i+1)2 − a34x(i)4 − · · · − a3nx(i)n
)
x
(i+1)
4 =
1
a44
(
b4 − a41x(i+1)1 − a42x(i+1)2 − a43x(i+1)3 − · · · − a4nx(i)n
)
...
...
x(i+1)n =
1
ann
(
bn − an1x(i+1)1 − an2x(i+1)2 − an3x(i+1)3 − · · · − an,n−1x(i+1)n−1
)
(2.7)
51
Um Crite´rio de Convergeˆncia (Gauss-Seidel)
Pode-se utilizar o Crite´rio da Linhas ou Diagonal Dominante usado no me´todo de Jacobi para o
me´todo de Gauss-Seidel. Mostraremos a seguir uma outra condic¸a˜o suficiente para a convergeˆncia do
Me´todo de Gauss-Seidel.
Teorema 2.4.2 (Crite´rio de Sassenfeld) Seja um sistema linear Ax = b e seja
β1 =
| a12 | + | a13 | + | a14 | + · · ·+ | a1n |
| a11 |
β2 =
β1 | a21 | + | a23 | + | a24 | + · · ·+ | a2n |
| a22 |
β3 =
β1 | a31 | +β2 | a32 | + | a34 | + · · ·+ | a3n |
| a33 |
...
βn =
β1 | an1 | +β2 | an2 | +β3 | an3 | + · · ·+ βn−1 | an,n−1 |
| ann |
ou seja,
β1 =
| a12 | + | a13 | + | a14 | + · · ·+ | a1n |
| a11 |
e
βi =
i−1∑
j=1
βj | aij | +
n∑
j=i+1
| aij |
/ | aii | i = 2, . . . , n
Se
β = max
1≤i≤n
βi < 1
enta˜o o me´todo de Gauss-Seidel converge para a soluc¸a˜o do sistema linear, independentemente da
aproximac¸a˜o inicial.
Exemplo:
5x1 + x2 + x3 = 5
3x1 + 4x2 + x3 = 6
3x1 + 3x2 + 6x3 = 0
Pelo crite´rio das linhas
α1 =
| a12 | + | a13 |
| a11 |
=
1 + 1
5
=
2
5
< 1
α2 =
| a21 | + | a23 |
| a22 | =
3 + 1
4
= 1
52
α3 =
| a31 | + | a32 |
| a33 |
=
3 + 3
6
= 1
logo na˜o temos certeza de que o me´todo de Gauss-Seidel convergira´. Vamos testar o crite´rio de
Sassenfeld.
β1 =
| a12 | + | a13 |
| a11 |
=
1+ 1
5
=
2
5
< 1
β2 =
β1 | a21 | + | a23 |
| a22 | =
2
5 · 3 + 1
4
=
11
20
< 1
β3 =
β1 | a31 | +β2 | a32 |
| a33 | =
2
5 · 3 + 1120 · 3
6
=
57
120
< 1
que foi satisfeito.
Reescrevendo o sistema linear
x
(k+1)
1 =
1
5
(
5− x(k)2 − x(k)3
)
x
(k+1)
2 =
1
4
(
6− 3x(k+1)1 − x(k)3
)
x
(k+1)
3 =
1
6
(
0− 3x(k+1)1 − 3x(k+1)2
)
com x(0) = ~0 e ǫ = 0.05.
x
(1)
1 =
1
5
(
5− x(0)2 − x(0)3
)
= 15 (5− 0− 0) = 1
x
(1)
2 =
1
4
(
6− 3x(1)1 − x(0)3
)
= 14 (6− 3 · 1− ·0) = 34
x
(1)
3 =
1
6
(
0− 3x(1)1 − 3x(1)2
)
= 16
(
0− 3 · 1− 3 · 34
)
= −2124

x
(1)
1
x
(1)
2
x
(1)
3

=

1
3
4
−2124

=

1
0.75
−0.875

Temos que verificar se o crite´rio de parada foi satisfeito
‖x(1) − x(0)‖ < ǫ ?????
‖

1
0.75
−0.875

−

0
0
0

‖ = ‖

1
0.75
−0.875

‖ = 1 > 0.05 = ǫ
53
faremos enta˜o mais uma iterac¸a˜o
x
(2)
1 =
1
5
(
5− x(1)2 − x(1)3
)
= 15 (5− 1 + 0.875) = 1.025
x
(2)
2 =
1
4
(
6− 3x(2)1 − x(1)3
)
= 14 (6− 3 · 1.025 + 0.875) = 0.95
x
(2)
3 =
1
6
(
0− 3x(2)1 − 3x(2)2
)
= 16 (0− 3 · 1.025− 3 · 0.95) = −0.9875

x
(2)
1
x
(2)
2
x
(2)
3

=

1.025
0.95
−0.9875

Pelo crite´rio de parada
‖x(2) − x(1)‖ < ǫ ?????
‖

1.025
0.95
−0.9875

−

1
0.75
−0.875

‖ = ‖

0.0250
0.2000
−0.1125

‖ = 0.2000 > ǫ
com mais uma iterac¸a˜o, obteremos,
x
(3)
1
x
(3)
2
x
(3)
3

=

1.0075
0.9912
−0.9993

Pelo crite´rio de parada
‖x(3) − x(2)‖ < ǫ ?????
‖

1.0075
0.9912
−0.9993

−

1.025
0.95
−0.9875

‖ = ‖

0.0175
0.0412
0.0118

‖ = 0.0412 < ǫ = 0.05
54
2.4.4 Me´todo da Relaxac¸a˜o
Neste me´todo introduzimos um paraˆmetro ω de maneira que a sequ¨eˆncia de aproximac¸o˜es geradas
convirja mais rapidamente. O paraˆmetro ω deve respeitar o seguinte intervalo 0 < ω < 2. Se ω < 1
chamamos o me´todo de sob-relaxac¸a˜o e se ω > 1 o me´todo e´ chamado de sobre-relaxac¸a˜o.
Este me´todo pode ser interpretado da seguinte maneira:
Suponha que para a (i + 1) aproximac¸a˜o x(i+1) ja´ conhec¸amos os componentes x
(i+1)
k , k =
1, 2, . . . , i− 1. Os novos componentes da aproximac¸a˜o (i+ 1) pode ser interpretada como uma me´dia
ponderada com pesos (1− ω) e ω da aproximac¸a˜o anterior e daquela que seria calculada pelo me´todo
de Gauss-Seidel, respectivamente. Isto e´,
x
(i+1)
j = (1− ω) x(i)j︸︷︷︸
aprox. anterior
+ω
1
ajj
bj − j−1∑
k=1
ajkx
(i+1)
k −
n∑
k=j+1
ajkx
(i)
k

︸ ︷︷ ︸
aprox. Gauss-Seidel
j = 1, 2, . . . , n

x
(i+1)
1 = (1− ω)x(i)1 +
ω
a11
(
b1 − a12x(i)2 − a13x(i)3 − a14x(i)4 − · · · − a1nx(i)n
)
x
(i+1)
2 = (1− ω)x(i)2 +
ω
a22
(
b2 − a21x(i+1)1 − a23x(i)3 − · · · − a2nx(i)n
)
x
(i+1)
3 = (1− ω)x(i)3 +
ω
a33
(
b3 − a31x(i+1)1 − a32x(i+1)2 · · · − a3nx(i)n
)
x
(i+1)
4 = (1− ω)x(i)4 +
ω
a44
(
b4 − a41x(i+1)1 − a42x(i+1)2 − · · · − a4nx(i)n
)
...
...
x(i+1)n = (1− ω)x(i)n +
ω
ann
(
bn − an1x(i+1)1 − an2x(i+1)2 − · · · − an,n−1x(i+1)n−1
)
(2.8)
Exemplo: Seja o sistema abaixo que e´ uma aproximac¸a˜o do sistema de equac¸o˜es que modelam uma
viga bi-apoiada com um carregamento pontual na posic¸a˜o 2. (DESENHO)
5 −4 1 0
−4 6 −4 1
1 −4 6 −4
0 1 −4 5

·

u1
u2
u3
u4

=

0
1
0
0

Resolvendo por relaxac¸a˜o:
x
(i+1)
j = x
(i)
j +
ω
ajj
bj − j−1∑
k=1
ajkx
(i+1)
k − ajjx(i)j −
n∑
k=j+1
ajkx
(i)
k
 j = 1, 2, . . . , n
55
ou 
u
(i+1)
1 = u
(i)
1 +
ω
5
(
−5u(i)1 + 4u(i)2 − u(i)3
)
u
(i+1)
2 = u
(i)
2 +
ω
6
(
1 + 4u
(i+1)
1 − 6u(i)2 + 4u(i)3 − u(i)4
)
u
(i+1)
3 = u
(i)
3 +
ω
6
(
−u(i+1)1 + 4u(i+1)2 − 6u(i)3 + 4u(i)4
)
u
(i+1)
4 = u
(i)
4 +
ω
5
(
−u(i+1)2 + 4u(i+1)3 − 5u(i)4
)
com uma estimativa inicial u(0) = ~0 e toleraˆncia ǫ = 0.001. Para o me´todo de Gauss-Seidel (ω = 1)
obteremos a convergeˆncia apo´s 104 iterac¸o˜es e a aproximac¸a˜o para a soluc¸a˜o e´:[
u(104)
]T
= (1.59; 2.59; 2.39; 1.39)
sendo que a soluc¸a˜o exata e´:
[u]T = (1.6; 2.6; 2.4; 1.4).
Variando-se o valor do paraˆmetro ω temos a seguinte relac¸a˜o entre ω e o nu´mero de iterac¸o˜es:
ω 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9
no. iterac¸o˜es 104 88 74 61 49 37 23 30 43 82
56
Sistemas Lineares – Exerc´ıcios
1. Resolva os sistemas lineares abaixo por Eliminac¸a˜o de Gauss.
a)

2x1 + x2 + 3x3 = 7
4x1 + 4x2 + 3x3 = 21
6x1 + 7x2 + 4x3 = 32
b)

3x1 + x2 + 6x3 = 2
2x1 + x2 + 3x3 = 7
x1 + x2 + x3 = 4
c)

2x1 + 2x2 + x3 + x4 = 7
x1 − x2 + 2x3 − x4 = 1
3x1 + 2x2 − 3x3 − 2x4 = 4
4x1 + 3x2 + 2x3 + x4 = 12
d)

4x1 + 3x2 + 2x3 + x4 = 10
x1 + 2x2 + 3x3 + 4x4 = 5
x1 − x2 − x3 − x4 = −1
x1 + x2 + x3 + x4 = 3
e)

2x1 + 3x2 − x3 = 5
4x1 + 4x2 − 3x3 = 3
2x1 − 3x2 + 1x3 = −1
Resp: x = [1 2 3]T
Soluc¸a˜o:
a)

2x1 + x2 + 3x3 = 7
4x1 + 4x2 + 3x3 = 21
6x1 + 7x2 + 4x3 = 32
2 1 3 | 7
4 4 3 | 21
6 7 4 | 32
 (ii) ← (ii) −4/2(i)
(iii) ← (iii) −6/2(i)
2 1 3 | 70 2 −3 | 7
0 4 −5 | 11

(iii) ← (iii) −4/2(ii)
2 1 3 | 7
0 2 −3 | 7
0 0 1 | −3

Resp: (17/2;−1;−3)
57
c)

2x1 + 2x2 + x3 + x4 = 7
x1 − x2 + 2x3 − x4 = 1
3x1 + 2x2 − 3x3 − 2x4 = 4
4x1 + 3x2 + 2x3 + x4 = 12
2 2 1 1 | 7
1 −1 2 −1 | 1
3 2 −3 −2 | 4
4 3 2 1 | 12

(ii) ← (ii) −1/2(i)
(iii) ← (iii) −3/2(i)
(iv) ← (iv) −2(i)
2 2 1 1 | 7
0 −2 3/2 −3/2 | −5/2
0 −1 −9/2 −7/2 | −13/2
0 −1 0 −1 | −2
 (iii) ← (iii) −1/2(ii)
(iv) ← (iv) −1/2(ii)
2 2 1 1 | 7
0 −2 3/2 −3/2 | −5/2
0 0 −21/42 −11/4 | −21/4
0 0 0 1/7 | 0

Resp: (1; 2; 1; 0)
2. Repita o exerc´ıcio acima usando pivoteamento parcial.
Soluc¸a˜o:
b) O elemento na diagonal da matriz e´ o maior da primeira coluna, logo na˜o e´ necessa´rio uma
troca de linhas de escolha de pivoˆ’s.
3 1 6 | 2
2 1 3 | 7
1 1 1 | 4
 (ii) ← (ii) −2/3(i)
(iii) ← (iii) −1/3(i)
3 1 6 | 2
0 1/3 −1 | 17/3
0 2/3 −1 | 10/3

assim temos que trocar a segunda e terceiras linhas de
3 1 6 | 2
0 2/3 −1 | 10/3
0 1/3 −1 | 17/3

(iii) ← (iii) −1/2(ii)
3 1 6 | 2
0 2/3 −1 | 10/3
0 0 −1/2 | 4

58
com a retrosubstituic¸a˜o, obtemos
x1 = 19
x2 = −7
x3 = −8
3. Ache a fatorac¸a˜o LU da matriz abaixo e calcule seu determinante
A =

3 2 4
1 −1 2
4 3 2

a seguir use esta fatorac¸a˜o para determinar a soluc¸a˜o do sistema
Ax =

1
2
3


3 2 4
1 1 2
4 3 2
 (ii) ← (ii) −1/3(i)
(iii) ← (iii) −4/3(i)

3 2 4
0 1/3 2/3
0 1/3 −10/3

(iii) ← (iii) −(ii)

3 2 4
0 1/3 2/3
0 0 −12/3

Logo
L =

1 0 0
1/3 1 0
4/3 1 1
 e U =

3 2 4
0 1/3 2/3
0 0 −4

Para resolver o sistema:
LUx = b
Chamando Ux = y, temos
Ly = b
59
ou para b = (1, 2, 3)
1 0 0
1/3 1 0
4/3 1 1


y1
y2
y3
 =

1
2
3

que resulta em
y1 = 4
y2 = 5/3
y3 = 0
Resolvendo agora o sistema triangular superior temos
Ux = y
ou 
3 2 4
0 1/3 2/3
0 0 −4


x1
x2
x3
 =

1
5/3
0

com a retrosubstituic¸a˜o, obtemos
x1 = −3
x2 = 5
x3 = 0
4. Dada a matriz A abaixo
A =

3 1 6
2 1 3
1 1 1

Ache a fatorac¸a˜o LR de A usando pivoteamento parcial. A seguir, com a fatorac¸a˜o encontrada
resolva o sistema Ax = b onde
b =

2
7
4

Soluc¸a˜o:
O elemento na diagonal da matriz e´ o maior da primeira coluna, logo na˜o e´ necessa´rio uma troca
de linhas de escolha de pivoˆ’s.
3 1 6
2 1 3
1 1 1
 (ii) ← (ii) −2/3(i)
(iii) ← (iii) −1/3(i)
60
logo,
A′ =

3 1 6
0 1/3 −1
0 2/3 −1
 e L =

1 0 0
2/3 1 0
1/3 ? 1
 e R =

3 1 6
0 1/3 −1
0 ? ?

assim temos que trocar a segunda e terceiras linhas de
A′′ =

3 1 6
0 2/3 −1
0 1/3 −1
 e L =

1 0 0
1/3 1 0
2/3 ? 1
 e R =

3 1 6
0 2/3 −1
0 ? ?


3 1 6
0 2/3 −1
0 1/3 −1

(iii) ← (iii) −1/2(ii)
enta˜o
A′′ =

3 1 6
0 2/3 −1
0 0 −1/2
 e L =

1 0 0
1/3 1 0
2/3 1/2 1
 e R =

3 1 6
0 2/3 −1
0 0 −1/2

Para utilizar a fatorac¸a˜o acima na resoluc¸a˜o do sistema, precisamos considerar as trocas de
linhas efetuadas na matriz e realiza´-las tambe´m no segundo membro. Como trocamos a segunda
e terceira linhas da matriz, devemos trocar a segunda e terceira linhas do segundo membro. Logo
b′ =

2
4
7

LRx = b′
Chamando Rx = y, temos
Ly = b′
ou 
1 0 0
1/3 1 0
2/3 1/2 1


y1
y2
y3
 =

2
4
7

que resulta em
y1 = 2
y2 = 10/3
y3 = 4
61
Resolvendo agora o sistema triangular superior temos
Rx = y
ou 
3 1 6
0 2/3 −1
0 0 −1/2


x1
x2
x3
 =

2
10/3
4

com a retrosubstituic¸a˜o, obtemos
x1 = 19
x2 = −7
x3 = −8
5. Suponha que desejamos resolver dois sistemas lineares que sa˜o ideˆnticos exceto pelos segundos
membros. Entre a Eliminac¸a˜o de Gauss e a Fatorac¸a˜o LU qual me´todo voceˆ escolheria? Por
queˆ?
Usando o me´todo escolhido por voceˆ resolva os dois sistemas abaixo.

2x1 + x2 + x3 = 4
4x1 + 4x2 + 3x3 = 11
6x1 + 7x2 + 4x3 = 17
e 
2x1 + x2 + x3 = 1
4x1 + 4x2 + 3x3 = 1
6x1 + 7x2 + 4x3 = 1
Soluc¸a˜o:
Claramente escolheria a Fatorac¸a˜o LU , visto que podemos resolver facilmente qualquer sistema
no qual conhecemos sua fatorac¸a˜o.
Com o processo de eliminac¸a˜o de Gauss, temos

2 1 1
4 4 3
6 7 4
 (ii) ← (ii) −4/2(i)
(iii) ← (iii) −6/2(i)

2 1 1
0 2 1
0 4 1

(iii) ← (iii) −4/2(ii)
62

2 1 1
0 2 1
0 0 −1

Logo
L =

1 0 0
2 1 0
3 2 1
 e U =

2 1 1
0 2 1
0 0 −1

Para resolver os sistemas ......
LUx = b
Chamando Ux = y, temos
Ly = b
ou para b = (4, 11, 17)
1 0 0
2 1 0
3 2 1


y1
y2
y3
 =

4
11
17

que resulta em
y1 = 4
y2 = 3
y3 = −1
Resolvendo agora o sistema triangular superior temos
Ux = y
ou 
2 1 1
0 2 1
0 0 −1


x1
x2
x3
 =

4
3
−1

com a retrosubstituic¸a˜o, obtemos
x1 = 1
x2 = 1
x3 = 1
63
e para b = (1, 1, 1)
1 0 0
2 1 0
3 2 1


y1
y2
y3
 =

1
1
1

que resulta em
y1 = 1
y2 = −1
y3 = 0
Resolvendo agora o sistema triangular superior temos
Ux = y
ou 
2 1 1
0 2 1
0 0 −1


x1
x2
x3
 =

1
−1
0

com a retrosubstituic¸a˜o, obtemos
x1 = 3/4
x2 = −1/2
x3 = 0
6. Seja a estrutura de trelic¸as abaixo
Calcular os esforc¸os nas barras da estrutura sabendo que cada uma possue comprimentoL = 1 m,
F = 1000 N . Use o me´todo da Eliminac¸a˜o de Gauss para resolver o sistema linear resultante.
64
7. Uma maneira de se calcular a inversa de uma matriz A (n× n) e´ resolver os n sistemas lineares
abaixo,
Ax = ei i = 1, 2, · · · , n
onde ei sa˜o os vetores da base canoˆnica, isto e´, e1 = (1, 0, 0, · · · , 0), e2 = (0, 1, 0, · · · , 0), e3 =
(0, 0, 1, · · · , 0), · · · · · ·, en = (0, 0, · · · , 0, 1). As colunas de A−1 sa˜o os vetores soluc¸o˜es desses
sistemas. Entre a Eliminac¸a˜o de Gauss e a Fatorac¸a˜o LU qual me´todo voceˆ escolheria? Por
queˆ?
Usando o me´todo escolhido por voceˆ ache a inversa da matriz abaixo.
A =

4 −1 0
−1 4 −1
0 −1 4

Soluc¸a˜o:
Obviamente escolheria´mos a fatorac¸a˜o LR da matriz A visto que temos que resolver va´rios
sistemas lineares em a matriz dos coeficientes e´ fixa, so´ havendo modificac¸o˜es nos segundos
membros.
Fatorac¸a˜o LR de A
4 −1 0
−1 4 −1
0 −1 4
 (ii) ← (ii) −(−1)/(4)(i)
(iii) ← (iii) −(0)/(4)(i)
Obtemos
4 −1 0
0 15/4 −1
0 −1 4

Logo,
=⇒ L =

1 0 0
−1/4 1 0
0 ∗ 1
 e R =

4 −1 0
0 15/4 −1
0 0 ∗

Continuando a Fatorac¸a˜o

4 −1 0
0 15/4 −1
0 −1 4

(iii) ← (iii) −(−1)/(15/4)(ii)
65

4 −1 0
0 15/4 −1
0 0 56/15

Logo,
=⇒ L =

1 0 0
−1/4 1 0
0 −4/15 1
 e R =

4 −1 0
0 15/4 −1
0 0 56/15

Usaremos agora a fatorac¸a˜o LR para resolver os sistemas lineares.
Em todos os casos resolveremos os seguintes sistemas
Ax = b
LRx = b
L(Rx) = b
L(y) = b
resolvendo-se este sistema triangular inferior obtemos o vetor y e a seguir podemos resolver o
seguinte sistema linear triangular superior
Rx = y
Para o primeiro sistema
Ax = e1
onde
e1 = (1,