Métodos para Resolver Sistemas Lineares
Enviado por
rafaelamnascimento01Métodos para Resolver Sistemas Lineares
Enviado por
rafaelamnascimento01DCC008 - Cálculo Numérico
Resolução de Sistemas de Equações Lineares
Bernardo Martins Rocha
Departamento de Ciência da Computação
Universidade Federal de Juiz de Fora
bernardomartinsrocha@[Link]
Conteúdo
▶ Introdução
▶ Conceitos fundamentais
▶ Métodos diretos
▶ Sistemas triangulares
▶ Eliminação de Gauss
▶ Estratégias de Pivotamento
▶ Decomposição LU
▶ Decomposição Cholesky e LDLT
▶ Usos da decomposição
▶ Métodos iterativos
▶ Introdução
▶ Métodos Iterativos Estacionários
▶ Método de Jacobi
▶ Método de Gauss-Seidel
▶ Análise de Convergência
▶ Método SOR
2 / 168
Introdução
Iremos estudar agora métodos computacionais para resolver um sistema de
equações lineares da forma:
a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
.. ..
. .
am1 x1 + am2 x2 + . . . + amn xn = bm
onde
aij ∈ R, bi ∈ R, xj ∈ R, i = 1, . . . , m, j = 1, . . . , n
Chamamos aij de coeficientes, bi são constantes dadas e xj são as variáveis ou
incógnitas do problema.
3 / 168
Introdução
Em uma vasta gama de problemas de ciências e engenharias a solução de um
sistema de equações lineares é necessária. Podemos enumerar diversas áreas e
problemas típicos, tais como:
▶ Solução de equações diferenciais
▶ Solução de EDPs através do método dos elementos finitos, diferenças
finitas ou volumes finitos.
▶ Solução de EDOs
▶ Programação linear
▶ Análise de estruturas
▶ Sistemas de equações não-lineares
▶ Outros métodos numéricos
▶ Interpolação, mínimos quadrados, etc.
▶ Circuitos elétricos
4 / 168
Introdução
Calcular as tensões dos nós do circuito elétrico da figura abaixo:
5 / 168
Introdução
Calcular as tensões dos nós do circuito elétrico da figura abaixo:
Modelagem do problema:
▶ Lei de Kirchhoff: a soma das correntes que passam em cada nó do
circuito é nula.
▶ Lei de Ohm: a corrente do nó j para o nó k é dada pela equação
Vj −Vk
Ijk = Rjk
5 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 = 0
6 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 =0
0−V1
1 + V2 −V1
1 + V3 −V
2
1
+ V4 −V
2
1
=0
6 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 =0
0−V1
1 + 1 + V3 −V
V2 −V1
2
1
+ V4 −V
2
1
=0
− 2V1 + V2 − V1 + V23 − V21 + V24 − V21 =0
6 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 =0
0−V1
1 + 1 + V3 −V
V2 −V1
2
1
+ V4 −V
2
1
=0
− 2V1 + V2 − V1 + V23 − V21 + V24 − V21 =0
− 4V1 + 2V2 + V3 − 2V1 + 2V4 = 0
−6V1 + 2V2 + V3 + V4 = 0
6 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 =0
0−V1
1 + 1 + V3 −V
V2 −V1
2
1
+ V4 −V
2
1
=0
− 2V1 + V2 − V1 + V23 − V21 + V24 − V21 =0
− 4V1 + 2V2 + V3 − 2V1 + 2V4 = 0
−6V1 + 2V2 + V3 + V4 = 0
Nó 2:
3V1 − 4V2 + V3 = 0
Nó 3:
3V1 + 2V2 − 13V2 + 6V4 = −254
Nó 4:
V1 + 2V3 − 3V4 = 0
6 / 168
Introdução
Nó 1: IA1 + I21 + I31 + I41 =0
0−V1
1 + 1 + V3 −V
V2 −V1
2
1
+ V4 −V
2
1
=0
− 2V1 + V2 − V1 + V23 − V21 + V24 − V21 =0
− 4V1 + 2V2 + V3 − 2V1 + 2V4 = 0
−6V1 + 2V2 + V3 + V4 = 0
Nó 2:
3V1 − 4V2 + V3 = 0
Nó 3:
−6 2 1 1 V1
3 −4 1 0 V2 3V1 + 2V2 − 13V2 + 6V4 = −254
3 2 −13 6 V3
1 0 2 −3 V4 Nó 4:
V1 + 2V3 − 3V4 = 0
6 / 168
Introdução
−6 2 1 1 V1 0
3 −4 1 0 V2 0
=
3 2 −13 6 V3 −254
1 0 2 −3 V4 0
Usando algum método que iremos estudar, encontramos a solução deste
sistema
25.7
31.75
V∗ =
49.6
41.6
ou seja V1 = 25.7V, V2 = 31.75V, V3 = 49.6V e V4 = 41.6V.
7 / 168
Introdução
Exemplo 1, Capítulo 3, Página, 105, Livro da Ruggiero.
Determinar as forças que atuam nesta treliça.
Junção 2:
X
Fx = −αf1 + f4 + αf5 = 0
X
Fy = −αf1 − f3 − αf5 = 0
Procedendo de forma análoga para todas as junções obtem-se um sistema
linear de 17 equações e 17 variáveis (f1 , . . . , f17 ).
8 / 168
Conceitos fundamentais
Antes de estudar os métodos para solução deste tipo de problema, vamos
rever alguns conceitos fundamentais de Álgebra Linear necessários para o
desenvolvimento e análise dos métodos.
9 / 168
Conceitos fundamentais
Antes de estudar os métodos para solução deste tipo de problema, vamos
rever alguns conceitos fundamentais de Álgebra Linear necessários para o
desenvolvimento e análise dos métodos.
Matrizes
Uma matriz é um conjunto de elementos (números reais ou complexos)
dispostos de forma retangular. O tamanho ou dimensão é definido pelo seu
número de linhas e colunas. Uma matriz com m linhas e n colunas é dita ser
m × n (m por n) e se m = n, então dizemos que a matriz é quadrada.
a11 a12 . . . a1n
a21 a22 . . . a2n Um elemento aij da matriz é
A= .
.. referenciado por 2 índices: o primeiro
.. ..
. . indica a linha e o segundo a coluna.
am1 am2 . . . amn
9 / 168
Conceitos fundamentais
▶ Matriz coluna e matriz linha
Matriz coluna: n × 1
Matriz linha: 1 × n a11
a21
a11 a12 . . . a1n
..
.
an1
▶ Matriz nula:
aij = 0, ∀i, j
▶ Matriz diagonal:
dij = 0, ∀i ̸= j
▶ Matriz identidade:
eij = 1, ∀i = j
eij = 0, ∀i ̸= j
10 / 168
Conceitos fundamentais
▶ Matriz triangular inferior: acima da diagonal principal é nula
b11 0 0
bij = 0, ∀ i < j, Exemplo: B = b21 b22 0
b31 b32 b33
11 / 168
Conceitos fundamentais
▶ Matriz triangular inferior: acima da diagonal principal é nula
b11 0 0
bij = 0, ∀ i < j, Exemplo: B = b21 b22 0
b31 b32 b33
▶ Matriz triangular superior: abaixo da diagonal principal é nula
c11 c12 c13
cij = 0, ∀ i > j, Exemplo: C = 0 c22 c23
0 0 c33
11 / 168
Conceitos fundamentais
▶ Matriz triangular inferior: acima da diagonal principal é nula
b11 0 0
bij = 0, ∀ i < j, Exemplo: B = b21 b22 0
b31 b32 b33
▶ Matriz triangular superior: abaixo da diagonal principal é nula
c11 c12 c13
cij = 0, ∀ i > j, Exemplo: C = 0 c22 c23
0 0 c33
▶ Matriz simétrica:
mij = mji , ∀ i, j
11 / 168
Conceitos fundamentais
Transposição
A transposta de uma matriz A, denotada por AT , é uma matriz obtida
trocando-se as suas linhas pelas colunas.
Exemplo:
1 2 3
4 5 6 1 5 7 10
A=
7 8 9 ,
AT = 2 5 8 11
3 6 9 12
10 11 12
12 / 168
Conceitos fundamentais
Transposição
A transposta de uma matriz A, denotada por AT , é uma matriz obtida
trocando-se as suas linhas pelas colunas.
Exemplo:
1 2 3
4 5 6 1 5 7 10
A=
7 8 9 ,
AT = 2 5 8 11
3 6 9 12
10 11 12
Adição e Subtração
Sejam A e B matrizes m × n. Então a matriz C é m × n e seus elementos são
dados por
cij = aij + bij , ∀ i, j
12 / 168
Conceitos fundamentais
Multiplicação por escalar
Seja A uma matriz m × n e seja k ∈ R um escalar qualquer. Então B = kA é
tal que
bij = k aij , ∀ i, j
13 / 168
Conceitos fundamentais
Multiplicação por escalar
Seja A uma matriz m × n e seja k ∈ R um escalar qualquer. Então B = kA é
tal que
bij = k aij , ∀ i, j
Multiplicação matriz-vetor
Seja A uma matriz m × n e x um vetor n × 1, então a multiplicação de A por x
é
n
X
v = Ax ⇒ vi = aij xj , i = 1, 2, . . . , m
j=1
13 / 168
Conceitos fundamentais
Multiplicação por escalar
Seja A uma matriz m × n e seja k ∈ R um escalar qualquer. Então B = kA é
tal que
bij = k aij , ∀ i, j
Multiplicação matriz-vetor
Seja A uma matriz m × n e x um vetor n × 1, então a multiplicação de A por x
é
n
X
v = Ax ⇒ vi = aij xj , i = 1, 2, . . . , m
j=1
Exemplo
1 2
5
1
3 4 = 11
2
5 6 17
13 / 168
Conceitos fundamentais
Multiplicação matriz-matriz
Seja A uma matriz m × p e B uma matriz p × n. O resultado da multiplicação
AB é uma matriz C de tamanho m × n.
p
X
cij = aik bkj , i = 1, . . . , m, j = 1, . . . , n
k=1
Exemplo:
−3 2
3 1 0
A= , B= 4 9
−1 6 4
8 −1
−5 15
C = AB =
59 48
14 / 168
Conceitos fundamentais
Produto Interno e Produto Externo
O produto interno ou escalar entre dois vetores x e y, ambos de tamanho n
resulta em um valor escalar k dado por
n
X
k = xT y = x1 y1 + x2 y2 + . . . + xn yn = xi yi
i=1
15 / 168
Conceitos fundamentais
Produto Interno e Produto Externo
O produto interno ou escalar entre dois vetores x e y, ambos de tamanho n
resulta em um valor escalar k dado por
n
X
k = xT y = x1 y1 + x2 y2 + . . . + xn yn = xi yi
i=1
O produto externo entre x(m × 1) e y(n × 1) resulta em uma matriz M de
tamanho m × n dada por
mij = xi yj , i = 1, . . . , m, j = 1, . . . , n
15 / 168
Conceitos fundamentais
Produto Interno e Produto Externo
O produto interno ou escalar entre dois vetores x e y, ambos de tamanho n
resulta em um valor escalar k dado por
n
X
k = xT y = x1 y1 + x2 y2 + . . . + xn yn = xi yi
i=1
O produto externo entre x(m × 1) e y(n × 1) resulta em uma matriz M de
tamanho m × n dada por
mij = xi yj , i = 1, . . . , m, j = 1, . . . , n
Exemplo:
5 1 5 15 20
x = −1 , y = 3 , xT y = 10, xyT = M = −1 −3 −4
2 4 2 6 8
15 / 168
Conceitos fundamentais
Determinante
Seja A uma matriz quadrada de ordem n. Então A possui um número
associado chamado de determinante, o qual pode ser calculado pela seguinte
fórmula:
det(A) = a11 det(M11 ) − a12 det(M12 ) + . . . + (−1)n+1 a1n det(M1n )
onde Mij é a matriz resultante da remoção da linha i e da coluna j da matriz A.
16 / 168
Conceitos fundamentais
Determinante
Seja A uma matriz quadrada de ordem n. Então A possui um número
associado chamado de determinante, o qual pode ser calculado pela seguinte
fórmula:
det(A) = a11 det(M11 ) − a12 det(M12 ) + . . . + (−1)n+1 a1n det(M1n )
onde Mij é a matriz resultante da remoção da linha i e da coluna j da matriz A.
Em particular
a11 a12
A = [a11 ] ⇒ det(A) = a11 , A= ⇒ det(A) = a11 a22 − a12 a21
a21 a22
det(A) = a11 (a22 a33 − a32 a23 )
a11 a12 a13
A = a21 a22 a23 − a12 (a21 a33 − a31 a23 )
a31 a32 a33 + a13 (a21 a32 − a31 a22 )
16 / 168
Conceitos fundamentais
Definição (Matriz singular)
Uma matriz com det(A) = 0 é dita singular. Por outro lado quando
det(A) ̸= 0 dizemos que a matriz é não-singular.
17 / 168
Conceitos fundamentais
Definição (Matriz singular)
Uma matriz com det(A) = 0 é dita singular. Por outro lado quando
det(A) ̸= 0 dizemos que a matriz é não-singular.
Definição (Vetores Linearmente Independentes)
Um conjunto de vetores x1 , x2 , . . . , xk é dito ser linearmente independente
(LI) se
c1 x1 + c2 x2 + . . . + ck xk = 0
somente se c1 = c2 = . . . = ck = 0. Caso contrário, isto é, quando
c1 , c2 , . . . , ck não são todos nulos, dizemos que o conjunto de vetores é
linearmente dependente (LD).
17 / 168
Conceitos fundamentais
Definição (Posto)
O posto (ou rank) de uma matriz A de tamanho m × n é definido como o
número máximo de vetores linhas (ou de vetores colunas) linearmente
independentes de A. Escrevemos posto(A) = r e temos que r ≤ min (m, n).
18 / 168
Conceitos fundamentais
Definição (Posto)
O posto (ou rank) de uma matriz A de tamanho m × n é definido como o
número máximo de vetores linhas (ou de vetores colunas) linearmente
independentes de A. Escrevemos posto(A) = r e temos que r ≤ min (m, n).
Definição (Inversa)
A inversa de uma matriz A quadrada n × n é representada por A−1 e definida
de tal forma que
AA−1 = A−1 A = I
onde I é a matriz identidade de ordem n.
3
− 21
2 1 −1 2
A= , A =
4 3 −2 1
18 / 168
Sistemas Lineares
Um sistema de equações lineares consiste em um conjunto de m equações
polinomiais com n variáveis xi de grau um, isto é
a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
.. ..
. .
am1 x1 + am2 x2 + . . . + amn xn = bm
o qual pode ser escrito da seguinte forma matricial Ax = b onde
a11 a12 . . . a1n x1 b1
a21 a22 . . . a2n x2 b2
A= . .. , x = .. , b = ..
.. ..
. . . .
am1 am2 . . . amn xn bm
onde A é a matriz dos coeficientes, b é o vetor dos termos independentes e x é
o vetor solução procurado.
19 / 168
Classificação de Sistemas
Vamos considerar apenas sistemas cujas matrizes dos coeficientes são
quadradas, isto é, onde A ∈ Rn×n .
Iremos tratar do caso onde A não é uma matriz quadrada e m > n mais
adiante, quando estudarmos mínimos quadrados.
Para o sistema Ax = b, temos as seguintes possibilidades quanto ao número
de soluções:
(a) uma única solução
(b) infinitas soluções
(c) sem solução
Vamos analisar cada caso em mais detalhes através de alguns exemplos de
sistemas de equações lineares 2 × 2.
20 / 168
Classificação de Sistemas
Caso (a) Única solução
x1 + x2 = 3 1 1 x1 3 1
= ⇒ x=
x1 − x2 = −1 1 −1 x2 −1 2
21 / 168
Classificação de Sistemas
Caso (a) Única solução
x1 + x2 = 3 1 1 x1 3 1
= ⇒ x=
x1 − x2 = −1 1 −1 x2 −1 2
44 3 2 1 0 1 2 3 4
21 / 168
Classificação de Sistemas
Caso (b) Infinitas Soluções
x1 + x2 = 1 1 1 x1 1
=
2x1 + 2x2 = 2 2 2 x2 2
22 / 168
Classificação de Sistemas
Caso (b) Infinitas Soluções
x1 + x2 = 1 1 1 x1 1 1−θ
= ⇒ x=
2x1 + 2x2 = 2 2 2 x2 2 θ
22 / 168
Classificação de Sistemas
Caso (b) Infinitas Soluções
x1 + x2 = 1 1 1 x1 1 1−θ
= ⇒ x=
2x1 + 2x2 = 2 2 2 x2 2 θ
5
x+y=1
4 2x + 2y = 2
34 3 2 1 0 1 2 3 4
22 / 168
Classificação de Sistemas
Caso (c) Sem Solução
x1 + x2 = 1
⇒ ̸ ∃x tal que Ax = b
x1 + x2 = 4
23 / 168
Classificação de Sistemas
Caso (c) Sem Solução
x1 + x2 = 1
⇒ ̸ ∃x tal que Ax = b
x1 + x2 = 4
8
x+y=1
x+y=4
6
44 3 2 1 0 1 2 3 4
23 / 168
Existência e unicidade da solução
A equação Ax = b possui uma única solução se e somente se a matriz A for
não-singular. O Teorema a seguir, caracteriza a não-singularidade da matriz A.
Teorema
Seja A uma matriz quadrada n × n. As seguintes afirmações são equivalentes:
a) A−1 existe
b) Não existe y não-zero tal que Ay = 0. Ou seja, a única solução do
sistema homogêneo é y = 0.
c) posto(A) = n
d) det(A) ̸= 0
e) Dado qualquer vetor b, existe exatamente um vetor x tal que Ax = b (ou
x = A−1 b).
Prova
Livro texto de Álgebra Linear.
24 / 168
Existência e unicidade da solução
De fato, para os exemplos anteriores, temos
Caso (a)
1 1
det = −1 − 1 = −2 ̸= 0 ⇒ OK, solução única
1 −1
Caso (b)
1 1
det =2−2=0
2 2
Caso (c)
1 1
det =1−1=0
1 1
25 / 168
Métodos para solução de sistemas lineares
Iremos estudar agora diversos métodos numéricos para a solução de sistemas
de equações lineares. Vamos considerar que A é quadrada e não-singular.
26 / 168
Métodos para solução de sistemas lineares
Iremos estudar agora diversos métodos numéricos para a solução de sistemas
de equações lineares. Vamos considerar que A é quadrada e não-singular.
Os métodos de solução de sistemas lineares geralmente envolvem a conversão
de um sistema quadrado em um sistema triangular que possui a mesma
solução que o original.
Inicialmente, vamos estudar como resolver sistemas lineares triangulares
inferiores e superiores.
26 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
l11 x1 = b1
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
l21 x1 + l22 x2 = b2
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
b2 − l21 x1
l21 x1 + l22 x2 = b2 ⇒ x2 =
l22
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
b2 − l21 x1
l21 x1 + l22 x2 = b2 ⇒ x2 =
l22
..
.
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
b2 − l21 x1
l21 x1 + l22 x2 = b2 ⇒ x2 =
l22
..
.
ln1 x1 + ln2 x2 + . . . + lnn xn = bn
27 / 168
Sistema triangular inferior
Considere um sistema triangular inferior de ordem n dado por
l11 0 0 . . . 0 x1 b1
l21 l22 0 . . . 0 x2 b2
.. = ..
.. . .
. . . .
ln1 ln2 ln3 . . . lnn xn bn
A solução deste sistema é feita através de um procedimento chamado de
substituição (ou substituições sucessivas):
b1
l11 x1 = b1 ⇒ x1 =
l11
b2 − l21 x1
l21 x1 + l22 x2 = b2 ⇒ x2 =
l22
..
.
bn − ln1 x1 − ln2 x2 − . . . − lnn−1 xn−1
ln1 x1 + ln2 x2 + . . . + lnn xn = bn ⇒ xn =
lnn
27 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
28 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
Exemplo
2 0 0 0 x1 4
3 5 0 0 x2 1
=
1 −6 8 0 x3 48
−1 4 −3 9 x4 0
28 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
Exemplo
2 0 0 0 x1 4
3 5 0 0 x2 1
=
1 −6 8 0 x3 48
−1 4 −3 9 x4 0
Solução
2x1 = 4 ⇒ x1 = 2
28 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
Exemplo
2 0 0 0 x1 4
3 5 0 0 x2 1
=
1 −6 8 0 x3 48
−1 4 −3 9 x4 0
Solução
2x1 = 4 ⇒ x1 = 2
1−6
3x1 + 5x2 = 1 ⇒ x2 = 5 = −1
28 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
Exemplo
2 0 0 0 x1 4
3 5 0 0 x2 1
=
1 −6 8 0 x3 48
−1 4 −3 9 x4 0
Solução
2x1 = 4 ⇒ x1 = 2
1−6
3x1 + 5x2 = 1 ⇒ x2 = 5 = −1
48−2−6
x1 − 6x2 + 8x3 = 48 ⇒ x3 = 8 =5
28 / 168
Sistema triangular inferior
De forma geral para Lx = b temos
,
Xi−1
xi = bi − lij xj lii i = 1, . . . , n
j=1
Exemplo
2 0 0 0 x1 4
3 5 0 0 x2 1
=
1 −6 8 0 x3 48
−1 4 −3 9 x4 0
Solução
2x1 = 4 ⇒ x1 = 2
1−6
3x1 + 5x2 = 1 ⇒ x2 = 5 = −1
48−2−6
x1 − 6x2 + 8x3 = 48 ⇒ x3 = 8 =5
2+4+15 21 28 / 168
Sistema triangular inferior
entrada: L ∈ Rn×n , b ∈ Rn
saída: x ∈ Rn
x(1) = b(1) / L(1,1);
para i=2, ..., n faça
s = b(i);
para j=1, ..., i-1 faça
s = s - L(i,j) * x(j);
fim-para
x(i) = s/L(i,i);
fim-para
29 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
unn xn = bn
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
un−1n−1 xn−1 + un−1n xn = bn−1
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
bn−1 − un−1n xn
un−1n−1 xn−1 + un−1n xn = bn−1 ⇒ xn−1 =
un−1n−1
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
bn−1 − un−1n xn
un−1n−1 xn−1 + un−1n xn = bn−1 ⇒ xn−1 =
un−1n−1
..
.
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
bn−1 − un−1n xn
un−1n−1 xn−1 + un−1n xn = bn−1 ⇒ xn−1 =
un−1n−1
..
.
u11 x1 + u12 x2 + . . . + u1n xn = b1
30 / 168
Sistema triangular superior
O algoritmo análogo para o caso de um sistema triangular superior Ux = b é
chamado de retro-substituição (ou substituições retroativas).
u11 u12 u13 . . . u1n x1 b1
0 u22 u23 . . . u2n x2 b2
.. = ..
.. ..
. . . .
0 0 0 . . . unn xn bn
e assim temos
bn
unn xn = bn ⇒ xn =
unn
bn−1 − un−1n xn
un−1n−1 xn−1 + un−1n xn = bn−1 ⇒ xn−1 =
un−1n−1
..
.
b1 − u12 x2 − u13 x3 − . . . − u1n xn
u11 x1 + u12 x2 + . . . + u1n xn = b1 ⇒ x1 =
u11
30 / 168
Sistema triangular superior
De forma geral para Ux = b temos
,
Xn
xi = bi − uij xj uii i = n, . . . , 1
j=i+1
31 / 168
Sistema triangular superior
De forma geral para Ux = b temos
,
Xn
xi = bi − uij xj uii i = n, . . . , 1
j=i+1
Exemplo
2 4 −2 x1 2
0 1 1 x2 = 4
0 0 4 x3 8
31 / 168
Sistema triangular superior
De forma geral para Ux = b temos
,
Xn
xi = bi − uij xj uii i = n, . . . , 1
j=i+1
Exemplo
2 4 −2 x1 2
0 1 1 x2 = 4
0 0 4 x3 8
Solução
4x3 = 8 ⇒ x3 = 2
31 / 168
Sistema triangular superior
De forma geral para Ux = b temos
,
Xn
xi = bi − uij xj uii i = n, . . . , 1
j=i+1
Exemplo
2 4 −2 x1 2
0 1 1 x2 = 4
0 0 4 x3 8
Solução
4x3 = 8 ⇒ x3 = 2
x2 + x3 = 4 ⇒ x2 = 2
31 / 168
Sistema triangular superior
De forma geral para Ux = b temos
,
Xn
xi = bi − uij xj uii i = n, . . . , 1
j=i+1
Exemplo
2 4 −2 x1 2
0 1 1 x2 = 4
0 0 4 x3 8
Solução
4x3 = 8 ⇒ x3 = 2
x2 + x3 = 4 ⇒ x2 = 2
2−8+4
2x1 + 4x2 − 2x3 = 2 ⇒ x1 = 2 = − 22 = −1
31 / 168
Sistema triangular superior
entrada: U ∈ Rn×n , b ∈ Rn
saída: x ∈ Rn
x(n) = b(n)/U(n,n);
para i=n-1, ..., 1 faça
s = b(i);
para j=i+1, ..., n faça
s = s - U(i,j) * x(j);
fim-para
x(i) = s/U(i,i);
fim-para
32 / 168
Complexidade Computacional
Muitas vezes precisamos medir o custo de execução de um algoritmo. Para
isso usualmente definimos uma função de complexidade que pode ser uma
medida do tempo para o algoritmo resolver um problema cuja instância de
entrada tem tamanho n (ou medir por exemplo o quanto de memória seria
necessário para execução).
A complexidade de um algoritmo para solução de um sistema linear de ordem
n é medida através do número de operações aritméticas como adição,
multiplicação e divisão.
Lembrando que
n
X n(n + 1)
i=
2
i=1
33 / 168
Complexidade Computacional
Substituição:
Divisão: n
n n−1
X X n(n − 1)
Adição: (i − 1) = i=
2
i=2 i=1
n n−1
X X n(n − 1)
Multiplicação: (i − 1) = i=
2
i=2 i=1
No total o algoritmo de substituição para sistemas triangulares inferiores
realiza
n(n − 1) n(n − 1)
n+ + = n + n2 − n = n2
2 2
operações de ponto flutuante.
34 / 168
Complexidade Computacional
Retro-substituição:
Divisão: n
n−1
X n(n − 1) n(n − 1)
Adição: (n − i) = n(n − 1) − =
2 2
i=1
n−1
X n(n − 1) n(n − 1)
Multiplicação: (n − i) = n(n − 1) − =
2 2
i=1
No total o algoritmo de retro-substituição para sistemas triangulares
superiores realiza
n(n − 1) n(n − 1)
n+ + = n + n2 − n = n2
2 2
operações de ponto flutuante.
35 / 168
Métodos para solução de sistemas lineares
Existem dois tipos de métodos para a solução de sistemas de equações
lineares:
36 / 168
Métodos para solução de sistemas lineares
Existem dois tipos de métodos para a solução de sistemas de equações
lineares:
▶ Métodos diretos
▶ Os métodos diretos são aqueles que conduzem à solução exata após um
número finito de passos a menos de erros de arredondamento introduzidos
pela máquina.
36 / 168
Métodos para solução de sistemas lineares
Existem dois tipos de métodos para a solução de sistemas de equações
lineares:
▶ Métodos diretos
▶ Os métodos diretos são aqueles que conduzem à solução exata após um
número finito de passos a menos de erros de arredondamento introduzidos
pela máquina.
▶ Métodos iterativos
▶ São aqueles que se baseiam na construção de sequências de
aproximações. Em um método iterativo, a cada passo, os valores
calculados anteriormente são usados para melhorar a aproximação. É
claro que o método só será útil se a sequência de aproximações
construídas convergir para uma solução aproximada do sistema.
36 / 168
Eliminação de Gauss
O primeiro método direto que iremos estudar é o método da eliminação de
Gauss. A idéia fundamental do método é transformar a matriz A em uma
matriz triangular superior introduzindo zeros abaixo da diagonal principal,
primeiro na coluna 1, depois na coluna 2 e assim por diante.
37 / 168
Eliminação de Gauss
O primeiro método direto que iremos estudar é o método da eliminação de
Gauss. A idéia fundamental do método é transformar a matriz A em uma
matriz triangular superior introduzindo zeros abaixo da diagonal principal,
primeiro na coluna 1, depois na coluna 2 e assim por diante.
x x x x x x x x x x x x x x x x
x x x x 0 x x x 0 x x x 0 x x x
→ → →
x x x x 0 x x x 0 0 x x 0 0 x x
x x x x 0 x x x 0 0 x x 0 0 0 x
37 / 168
Eliminação de Gauss
O primeiro método direto que iremos estudar é o método da eliminação de
Gauss. A idéia fundamental do método é transformar a matriz A em uma
matriz triangular superior introduzindo zeros abaixo da diagonal principal,
primeiro na coluna 1, depois na coluna 2 e assim por diante.
x x x x x x x x x x x x x x x x
x x x x 0 x x x 0 x x x 0 x x x
→ → →
x x x x 0 x x x 0 0 x x 0 0 x x
x x x x 0 x x x 0 0 x x 0 0 0 x
Por fim, usa-se a retro-substituição para obter a solução do sistema
triangular superior obtido ao final dessa etapa de eliminação.
37 / 168
Eliminação de Gauss
Na eliminação de Gauss, as operações efetuadas para se obter a matriz
triangular superior são tais que a matriz triangular obtida possui a mesma
solução que o sistema original.
38 / 168
Eliminação de Gauss
Na eliminação de Gauss, as operações efetuadas para se obter a matriz
triangular superior são tais que a matriz triangular obtida possui a mesma
solução que o sistema original.
Definição (Sistema equivalente)
Dois sistemas de equações lineares são equivalentes quando possuem o
mesmo vetor solução.
38 / 168
Eliminação de Gauss
Na eliminação de Gauss, as operações efetuadas para se obter a matriz
triangular superior são tais que a matriz triangular obtida possui a mesma
solução que o sistema original.
Definição (Sistema equivalente)
Dois sistemas de equações lineares são equivalentes quando possuem o
mesmo vetor solução.
Um sistema pode ser transformado em um outro sistema equivalente
utilizando as seguintes operações elementares:
▶ trocar a ordem de duas equações
▶ multiplicar uma equação por uma constante não-nula
▶ somar um múltiplo de uma equação à outra
38 / 168
Eliminação de Gauss
Exemplo
3x1 + 5x2 = 9
6x1 + 7x2 = 4
Podemos subtrair da linha 2 um
múltiplo da linha 1, isto é
L2′ = L2 − 2L1
Efetuando esta operação obtemos o
sistema equivalente
3x1 + 5x2 = 9
−3x2 = −14
39 / 168
Eliminação de Gauss
Exemplo 7
6
3x1 + 5x2 = 9 5
6x1 + 7x2 = 4 4
Podemos subtrair da linha 2 um 2
1
múltiplo da linha 1, isto é
0
17
L2′ = L2 − 2L1
6 5 4 3 2 1 0 1
Efetuando esta operação obtemos o
sistema equivalente
3x1 + 5x2 = 9
−3x2 = −14
39 / 168
Eliminação de Gauss
Exemplo 7
6
3x1 + 5x2 = 9 5
6x1 + 7x2 = 4 4
Podemos subtrair da linha 2 um 2
1
múltiplo da linha 1, isto é
0
17
L2′ = L2 − 2L1
6 5 4 3 2 1 0 1
6
5
Efetuando esta operação obtemos o
4
sistema equivalente
3
3x1 + 5x2 = 9
2
−3x2 = −14
17 6 5 4 3 2 1 0 1
39 / 168
Eliminação de Gauss
Vamos primeiro estudar um exemplo simples para posteriormente generalizar
a idéia.
Exemplo
Seja o sistema
x1 + x3 = 0
x1 + x2 = 1
2x1 + 3x2 + x3 = 1
Solução
40 / 168
Eliminação de Gauss
Vamos primeiro estudar um exemplo simples para posteriormente generalizar
a idéia.
Exemplo
Seja o sistema
x1 + x3 = 0 1 0 1 x1 0
1 1 0 x2 = 1
x1 + x2 = 1
2 3 1 x3 1
2x1 + 3x2 + x3 = 1
Solução
40 / 168
Eliminação de Gauss
Vamos primeiro estudar um exemplo simples para posteriormente generalizar
a idéia.
Exemplo
Seja o sistema
x1 + x3 = 0 1 0 1 x1 0
1 1 0 x2 = 1
x1 + x2 = 1
2 3 1 x3 1
2x1 + 3x2 + x3 = 1
Solução
Como podemos eliminar os coeficientes abaixo da diagonal principal na
primeira coluna?
40 / 168
Eliminação de Gauss
Vamos primeiro estudar um exemplo simples para posteriormente generalizar
a idéia.
Exemplo
Seja o sistema
x1 + x3 = 0 1 0 1 x1 0
1 1 0 x2 = 1
x1 + x2 = 1
2 3 1 x3 1
2x1 + 3x2 + x3 = 1
Solução
Como podemos eliminar os coeficientes abaixo da diagonal principal na
primeira coluna?
1 0 1 0
L2′ = L2 − L1 0 1 −1 1
L3′ = L3 − 2L1 0 3 −1 1 40 / 168
Eliminação de Gauss
Exemplo - (cont.)
Precisamos agora de eliminar os coeficientes abaixo da diagonal na segunda
coluna (a32 ). Como?
41 / 168
Eliminação de Gauss
Exemplo - (cont.)
Precisamos agora de eliminar os coeficientes abaixo da diagonal na segunda
coluna (a32 ). Como?
1 0 1 0
L3′′ = L3′ − 3L2′ 0 1 −1 1
0 0 2 −2
41 / 168
Eliminação de Gauss
Exemplo - (cont.)
Precisamos agora de eliminar os coeficientes abaixo da diagonal na segunda
coluna (a32 ). Como?
1 0 1 0
L3′′ = L3′ − 3L2′ 0 1 −1 1
0 0 2 −2
Agora podemos usar a retro-substituição para encontrar facilmente a solução
deste sistema:
41 / 168
Eliminação de Gauss
Exemplo - (cont.)
Precisamos agora de eliminar os coeficientes abaixo da diagonal na segunda
coluna (a32 ). Como?
1 0 1 0
L3′′ = L3′ − 3L2′ 0 1 −1 1
0 0 2 −2
Agora podemos usar a retro-substituição para encontrar facilmente a solução
deste sistema:
2x3 = −2 ⇒ x3 = −1
x2 − x3 = 1 ⇒ x2 = 1 + x3 = 1 − 1 = 0
x1 + x3 = 0 ⇒ x1 = −x3 = 1
41 / 168
Eliminação de Gauss
Exemplo - (cont.)
Precisamos agora de eliminar os coeficientes abaixo da diagonal na segunda
coluna (a32 ). Como?
1 0 1 0
L3′′ = L3′ − 3L2′ 0 1 −1 1
0 0 2 −2
Agora podemos usar a retro-substituição para encontrar facilmente a solução
deste sistema:
2x3 = −2 ⇒ x3 = −1
x2 − x3 = 1 ⇒ x2 = 1 + x3 = 1 − 1 = 0
x1 + x3 = 0 ⇒ x1 = −x3 = 1
Encontramos assim a solução: xT = 1 0 −1
41 / 168
Conteúdo
▶ Aula passada
▶ Conceitos fundamentais
▶ Sistemas triangulares
▶ Eliminação de Gauss
▶ Aula de hoje
▶ Eliminação de Gauss
▶ Estratégias de Pivotamento
▶ Decomposição LU
42 / 168
Revisitando a Eliminação de Gauss
Resolver o seguinte sistema
2 1 1 x1 5
4 −6 0 x2 = −2
−2 7 2 x3 9
43 / 168
Revisitando a Eliminação de Gauss
Resolver o seguinte sistema
2 1 1 x1 5
4 −6 0 x2 = −2
−2 7 2 x3 9
Passo 1
m21 = a21
a11 = 4/2 = 2 ⇒ L2′ = L2 − 2L1
43 / 168
Revisitando a Eliminação de Gauss
Resolver o seguinte sistema
2 1 1 x1 5
4 −6 0 x2 = −2
−2 7 2 x3 9
Passo 1
m21 = a21
a11 = 4/2 = 2 ⇒ L2′ = L2 − 2L1
m31 = a31
a11 = −2/2 = −1 ⇒ L3′ = L3 + L1
43 / 168
Revisitando a Eliminação de Gauss
Resolver o seguinte sistema
2 1 1 x1 5
4 −6 0 x2 = −2
−2 7 2 x3 9
Passo 1
m21 = a21
a11 = 4/2 = 2 ⇒ L2′ = L2 − 2L1
m31 = a31
a11 = −2/2 = −1 ⇒ L3′ = L3 + L1
2 1 1 5
0 −8 −2 −12
0 8 3 14
43 / 168
Revisitando a Eliminação de Gauss
Passo 2
2 1 1 5
0 −8 −2 −12
0 8 3 14
m32 = a32
a22 = 8/ − 8 = −1 ⇒ L3′′ = L3′ + L2′
44 / 168
Revisitando a Eliminação de Gauss
Passo 2
2 1 1 5
0 −8 −2 −12
0 8 3 14
m32 = a32
a22 = 8/ − 8 = −1 ⇒ L3′′ = L3′ + L2′
2 1 1 5
0 −8 −2 −12
0 0 1 2
Próxima etapa: resolver o sistema triangular superior obtido usando o
algoritmo de retro-substituição.
44 / 168
Eliminação de Gauss
De forma geral
a11 a12 a13 ... a1n b1
a21 a22 a23 ... a2n b2
.. .. .. .. .. ..
. . . . . .
an1 an2 an3 ... ann bn
45 / 168
Eliminação de Gauss
De forma geral
a11 a12 a13 ... a1n b1
a21 a22 a23 ... a2n b2
.. .. .. .. .. ..
. . . . . .
an1 an2 an3 ... ann bn
Passo 1 (k=1): eliminamos os elementos abaixo da diagonal principal na
primeira coluna. Suponha que a11 ̸= 0.
45 / 168
Eliminação de Gauss
De forma geral
a11 a12 a13 ... a1n b1
a21 a22 a23 ... a2n b2
.. .. .. .. .. ..
. . . . . .
an1 an2 an3 ... ann bn
Passo 1 (k=1): eliminamos os elementos abaixo da diagonal principal na
primeira coluna. Suponha que a11 ̸= 0. Então:
m21 = a21 /a11
m31 = a31 /a11
..
.
mn1 = an1 /a11
ou seja
mi1 = ai1 /a11 , i=2:n
45 / 168
Eliminação de Gauss
De forma geral
a11 a12 a13 ... a1n b1
a21 a22 a23 ... a2n b2
.. .. .. .. .. ..
. . . . . .
an1 an2 an3 ... ann bn
Passo 1 (k=1): eliminamos os elementos abaixo da diagonal principal na
primeira coluna. Suponha que a11 ̸= 0. Então:
m21 = a21 /a11
m31 = a31 /a11
..
.
mn1 = an1 /a11
ou seja
mi1 = ai1 /a11 , i=2:n
Notação: i = 2 : n ⇔ i = 2, 3, . . . , n 45 / 168
Eliminação de Gauss
Agora, multiplicamos a 1a equação por mi1 e subtraimos da i-ésima equação,
isto é
(1) (0) (0)
Para i = 2 : n aij = aij − mi1 a1j
(1) (0) (0)
bi = bi − mi1 b1 , j=1:n
46 / 168
Eliminação de Gauss
Agora, multiplicamos a 1a equação por mi1 e subtraimos da i-ésima equação,
isto é
(1) (0) (0)
Para i = 2 : n aij = aij − mi1 a1j
(1) (0) (0)
bi = bi − mi1 b1 , j=1:n
Observe que não alteramos a primeira linha, pois i = 2 : n, logo esta
permanece inalterada:
(1) (0) (1) (0)
a1j = a1j = a1j , b1 = b1 = b1
46 / 168
Eliminação de Gauss
Agora, multiplicamos a 1a equação por mi1 e subtraimos da i-ésima equação,
isto é
(1) (0) (0)
Para i = 2 : n aij = aij − mi1 a1j
(1) (0) (0)
bi = bi − mi1 b1 , j=1:n
Observe que não alteramos a primeira linha, pois i = 2 : n, logo esta
permanece inalterada:
(1) (0) (1) (0)
a1j = a1j = a1j , b1 = b1 = b1
Após essa etapa zeramos todos os elementos abaixo da diagonal principal na
1a coluna.
a11 a12 a13 ... a1n b1
0 a122 a123 ... a12n b12
0 a132 a133 ... a13n b13
.. .. .. .. .. ..
. . . . . .
0 a1n2 a1n3 ... a1nn b1n
46 / 168
Eliminação de Gauss
Passo 2 (k=2): consiste em introduzir zeros abaixo da diagonal principal na
2a coluna. Suponha a22 ̸= 0. Definimos
mi2 = ai2 /a22 , i=3:n
47 / 168
Eliminação de Gauss
Passo 2 (k=2): consiste em introduzir zeros abaixo da diagonal principal na
2a coluna. Suponha a22 ̸= 0. Definimos
mi2 = ai2 /a22 , i=3:n
e assim
(2) (1) (1)
para i = 3 : n aij = aij − mi2 a2j
(2) (1) (1)
bi = bi − mi2 b2 , j=2:n
47 / 168
Eliminação de Gauss
Passo 2 (k=2): consiste em introduzir zeros abaixo da diagonal principal na
2a coluna. Suponha a22 ̸= 0. Definimos
mi2 = ai2 /a22 , i=3:n
e assim
(2) (1) (1)
para i = 3 : n aij = aij − mi2 a2j
(2) (1) (1)
bi = bi − mi2 b2 , j=2:n
o que resulta em
a11 a12 a13 . . . a1n b1
0 a122 a123 . . . a12n b12
0 0 a233 . . . a23n b23
.. .. .. .. .. ..
. . . . . .
0 0 a2n3 . . . a2nn b2n
47 / 168
Eliminação de Gauss
Passo 3, Passo 4, ...
Passo k: Considerando akk ̸= 0, temos
mik = aik /akk , i=k+1:n
48 / 168
Eliminação de Gauss
Passo 3, Passo 4, ...
Passo k: Considerando akk ̸= 0, temos
mik = aik /akk , i=k+1:n
e assim fazemos
(k) (k−1) (k−1)
para i = k + 1 : n aij = aij − mik akj
(k) (k−1) (k−1)
bi = bi − mik bk , j=k:n
Observe novamente que não alteramos as linhas de 1 a k.
48 / 168
Eliminação de Gauss
(1) (2) (k−1)
No processo de eliminação os elementos a11 , a22 , a33 , . . ., akk que
aparecem na diagonal da matriz A são chamados de pivôs.
Se os pivôs não se anulam, isto é, se akk ̸= 0, k = 1 : n, durante o processo,
então a eliminação procede com sucesso e por fim chegamos ao seguinte
sistema triangular superior
a11 a12 a13 . . . a1n−1 a1n b1
0 a1 a1 . . . a1 a12n b12
22 23 2n−1
0 2 2
0 a33 . . . a3n−1 a3n 2 b23
.. .. .. .. .. ..
. . . . . .
0 0 0 ... 0 an−1
nn bn−1
n
Em seguida resolvemos esse sistema usando retro substituição.
49 / 168
Eliminação de Gauss
entrada: matriz A ∈ Rn×n , vetor b ∈ Rn
saída: vetor solução x ∈ Rn
para k = 1 : n − 1 faça
para i = k + 1 : n faça
m = A(i,k) / A(k,k);
para j = k + 1 : n faça
A(i,j) = A(i,j) - m * A(k,j);
fim-para
b(i) = b(i) - m * b(k);
fim-para
fim-para
x = retroSubstituicao(A,b);
retorna x;
50 / 168
Eliminação de Gauss
Novamente vamos contabilizar o número de operações aritméticas de ponto
flutuante que são realizadas pelo algoritmo.
Para contar o número de operações realizadas na eliminação de Gauss, vamos
dividir o processo nas seguintes etapas:
(1) A → U: o processo de transformar a matriz A em uma matriz triangular
superior U
(2) b → g: modificações no vetor b
(3) Resolver Ux = g usando retro-substituição
▶ Já vimos que o número de operações deste algoritmo é n2
51 / 168
Eliminação de Gauss
Novamente vamos contabilizar o número de operações aritméticas de ponto
flutuante que são realizadas pelo algoritmo.
Para contar o número de operações realizadas na eliminação de Gauss, vamos
dividir o processo nas seguintes etapas:
(1) A → U: o processo de transformar a matriz A em uma matriz triangular
superior U
(2) b → g: modificações no vetor b
(3) Resolver Ux = g usando retro-substituição
▶ Já vimos que o número de operações deste algoritmo é n2
No que segue iremos usar
n
n X n(n + 1)(2n + 1)
X n(n + 1) i2 =
i= 6
2 i=1
i=1
51 / 168
Eliminação de Gauss
(1) A → U
▶ Divisões
n−1 n
! n−1
X X X
1 = (n − k)
k=1 i=k+1 k=1
n−1
X
= n(n − 1) − k
k=1
n(n − 1)
= n(n − 1) −
2
n(n − 1)
=
2
52 / 168
Eliminação de Gauss
(1) A → U
▶ Adições
!
n−1 X
X n n
X n−1
X n
X
1 = (n − k)
k=1 i=k+1 j=k+1 k=1 i=k+1
n−1
X
= (n − k)(n − k)
k=1
n−1
X
= (n2 − 2kn + k2 )
k=1
(n−1)(n−1+1)(2n−2+1)
= n2 (n − 1) − 2n n(n−1)
2 + 6
n(n − 1)(2n − 1)
=
6
▶ Multiplicações
n(n − 1)(2n − 1)
6 53 / 168
Eliminação de Gauss
(2) b → g
▶ Adições
n−1 n
! n−1
X X X
1 = (n − k)
k=1 i=k+1 k=1
n−1
X
= n(n − 1) − k
k=1
n(n − 1)
= n(n − 1) −
2
n(n − 1)
=
2
▶ Multiplicações
n(n − 1)
2
54 / 168
Eliminação de Gauss
(Total)
Em cada etapa temos
2 3 n2 n
(1) 3n − 2 − 6
(2) n2 − n
2
Assim nas etapas (1) e (2) temos um total de 23 n3 + n2 − 76 n.
Considerando que na etapa de retro-substituição (3) temos n2 operações, no
total o algoritmo de eliminação de Gauss realiza um total de
2n3 n2 7n 2 2n3 3n2 7n
+ − + n = + −
|3 {z2 6} 3 2 6
|{z}
retro-substituição
eliminação
55 / 168
Eliminação de Gauss
Para um valor de n muito grande, o algoritmo realiza aproximadamente 23 n3
operações de ponto flutuante.
Exemplo
Se um sistema linear tem tamanho n = 100, então:
▶ resolver o sistema triangular: 1002 = 10 000 operações
▶ eliminação de gauss: 681 550 operações
Ou seja, nesse exemplo, a eliminação de Gauss é 68× mais lenta que a
solução de um sistema triangular !!!
56 / 168
Eliminação de Gauss
Mas, e se na etapa k da eliminação de Gauss, o pivô for zero?
Isso significa que akk = 0, e assim, teríamos
aik
mik = ⇒ divisão por zero!
akk
Nesse caso, se um pivô for zero, o processo de eliminação tem que parar, ou
temporariamente ou permanentemente.
O sistema pode ou não ser singular.
Se o sistema for singular, i.e, det(A) = 0, e portanto como vimos o sistema
não possui uma única solução.
Veremos agora um caso que a matriz não é singular e podemos resolver esse
problema.
57 / 168
Estratégia de Pivotamento
Vamos ilustrar a idéia do Pivotamento através de um exemplo. Considere a
seguinte matriz.
1 1 1
A = 2 2 5
4 6 8
Vamos proceder com a eliminação de Gauss.
58 / 168
Estratégia de Pivotamento
Vamos ilustrar a idéia do Pivotamento através de um exemplo. Considere a
seguinte matriz.
1 1 1
A = 2 2 5
4 6 8
Vamos proceder com a eliminação de Gauss.
m21 = 2, a12j = a02j − 2 a01j
m31 = 4, a13j = a03j − 4 a01j , j=1:3
58 / 168
Estratégia de Pivotamento
Vamos ilustrar a idéia do Pivotamento através de um exemplo. Considere a
seguinte matriz.
1 1 1
A = 2 2 5
4 6 8
Vamos proceder com a eliminação de Gauss.
m21 = 2, a12j = a02j − 2 a01j
m31 = 4, a13j = a03j − 4 a01j , j=1:3
Então obtemos
1 1 1
0 0 3
0 2 4
58 / 168
Estratégia de Pivotamento
No próximo passo, o pivô é a22 e usamos ele para calcular m32 . Entretanto
a32 2
m32 = =
a22 0
Divisão por zero! E agora, o que podemos fazer?
59 / 168
Estratégia de Pivotamento
No próximo passo, o pivô é a22 e usamos ele para calcular m32 . Entretanto
a32 2
m32 = =
a22 0
Divisão por zero! E agora, o que podemos fazer?
Podemos realizar uma operação elementar de troca de linhas. Como vimos
este tipo de operação quando realizado em um sistema, não altera a solução.
Sendo assim, vamos trocar as linhas 2 e 3.
59 / 168
Estratégia de Pivotamento
No próximo passo, o pivô é a22 e usamos ele para calcular m32 . Entretanto
a32 2
m32 = =
a22 0
Divisão por zero! E agora, o que podemos fazer?
Podemos realizar uma operação elementar de troca de linhas. Como vimos
este tipo de operação quando realizado em um sistema, não altera a solução.
Sendo assim, vamos trocar as linhas 2 e 3.
1 1 1 1 1 1
0 0 3 ⇒ 0 2 4
0 2 4 0 0 3
E assim chegamos a um sistema triangular superior, cuja solução pode ser
obtida usando a retro-substituição.
59 / 168
Estratégia de Pivotamento
A estratégia de Pivotamento é importante pois:
▶ evita a propagação de erros numéricos
▶ nos fornece meios de evitar problemas durante a eliminação de Gauss
quando o pivô akk no passo k é igual a zero e precisamos calcular o
multiplicador
aik
mik =
akk
Assim, através da troca de linhas, podemos encontrar uma linha de tal forma
que o novo pivô é não-zero, permitindo que a eliminação de Gauss continue
até obter uma matriz triangular superior.
Temos duas possibilidades:
▶ Pivotamento parcial
▶ Pivotamento total
60 / 168
Pivotamento Parcial
No Pivotamento parcial, em cada passo k, o pivô é escolhido como o maior
elemento em módulo abaixo de akk (inclusive), isto é
Encontrar r tal que: |ark | = max |aik |, k ≤ i ≤ n
61 / 168
Pivotamento Parcial
No Pivotamento parcial, em cada passo k, o pivô é escolhido como o maior
elemento em módulo abaixo de akk (inclusive), isto é
Encontrar r tal que: |ark | = max |aik |, k ≤ i ≤ n
Feita a escolha do pivô, trocamos as linhas r e k e o algoritmo procede.
Isso evita a propagação de erros numéricos, pois:
▶ O Pivotamento parcial garante que
|mik | ≤ 1
▶ Se akk for muito pequeno, consequentemente mik será muito grande.
Dessa forma, após a multiplicação por mik podemos ampliar erros de
arredondamento envolvidos no processo.
▶ Também evitamos o erro que pode ser causado quando somamos um
número pequeno com um número grande.
61 / 168
Pivotamento Parcial
Exemplo
Aplique a eliminação de Gauss com Pivotamento parcial no seguinte sistema:
2 4 −2 2
4 9 −3 8
−2 −3 7 10
A cada passo k:
▶ encontrar o pivô do passo k
▶ se necessário, trocar as linhas
▶ calcular multiplicador mik
▶ para i = k + 1 : n, calcular
(k) (k−1) (k−1)
aij = aij − mik akj
(k) (k−1) (k−1)
bi = bi − mik bk , j=k:n
62 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 1
Escolha do pivô: max {2, 4, 2} = 4. Trocar as linhas 1 e 2.
2 4 −2 2 4 9 −3 8
4 9 −3 8 ⇒ 2 4 −2 2
−2 −3 7 10 −2 −3 7 10
63 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 1
Escolha do pivô: max {2, 4, 2} = 4. Trocar as linhas 1 e 2.
2 4 −2 2 4 9 −3 8
4 9 −3 8 ⇒ 2 4 −2 2
−2 −3 7 10 −2 −3 7 10
m21 = 2/4 = 1/2 ⇒ a12j = a02j − 12 a01j
m31 = −2/4 = −1/2 ⇒ a13j = a03j + 21 a01j , j=1:3
63 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 1
Escolha do pivô: max {2, 4, 2} = 4. Trocar as linhas 1 e 2.
2 4 −2 2 4 9 −3 8
4 9 −3 8 ⇒ 2 4 −2 2
−2 −3 7 10 −2 −3 7 10
m21 = 2/4 = 1/2 ⇒ a12j = a02j − 12 a01j
m31 = −2/4 = −1/2 ⇒ a13j = a03j + 21 a01j , j=1:3
4 9 −3 8
0 −1 − 12 −2
2
0 32 11
2 14
63 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 2
Escolha do pivô: max { 21 , 32 } = 23 .
4 9 −3 8 4 9 −3 8
0 −1 − 21 −2 ⇒ 0 3 11
14
2 2 2
0 23 11
2 14 0 − 21 − 12 −2
64 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 2
Escolha do pivô: max { 21 , 32 } = 23 .
4 9 −3 8 4 9 −3 8
0 −1 − 21 −2 ⇒ 0 3 11
14
2 2 2
0 23 11
2 14 0 − 21 − 12 −2
m32 = − 12 32 = − 13 ⇒ a23j = a13j + 31 a12j , j=2:3
64 / 168
Pivotamento Parcial
Exemplo - (cont.)
Passo 2
Escolha do pivô: max { 21 , 32 } = 23 .
4 9 −3 8 4 9 −3 8
0 −1 − 21 −2 ⇒ 0 3 11
14
2 2 2
0 23 11
2 14 0 − 21 − 12 −2
m32 = − 12 32 = − 13 ⇒ a23j = a13j + 31 a12j , j=2:3
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
64 / 168
Pivotamento Parcial
Exemplo - (cont.)
Retro-substituição
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
65 / 168
Pivotamento Parcial
Exemplo - (cont.)
Retro-substituição
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
4 8
3 x3 = 3 ⇒ x3 = 2
65 / 168
Pivotamento Parcial
Exemplo - (cont.)
Retro-substituição
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
4 8
3 x3 = 3 ⇒ x3 = 2
3
2 x2 + 2 11
2 = 14 ⇒ x2 = 2
65 / 168
Pivotamento Parcial
Exemplo - (cont.)
Retro-substituição
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
4 8
3 x3 = 3 ⇒ x3 = 2
3
2 x2 + 2 11
2 = 14 ⇒ x2 = 2
4x1 + 9(2) − 3(2) = 8 ⇒ x1 = −1
65 / 168
Pivotamento Parcial
Exemplo - (cont.)
Retro-substituição
4 9 −3 8
0 3 11 14
2 2
0 0 43 8
3
4 8
3 x3 = 3 ⇒ x3 = 2
3
2 x2 + 2 11
2 = 14 ⇒ x2 = 2
4x1 + 9(2) − 3(2) = 8 ⇒ x1 = −1
Portanto a solução é xT = [−1, 2, 2].
65 / 168
Pivotamento Parcial
Exemplo (efeitos numéricos)
Considere o seguinte sistema:
0.0001 1 x1 1
=
1 1 x2 2
Usando um sistema de ponto flutuante F(10, 3, −10, 10) (sistema decimal
com 3 dígitos na mantissa), com arredondamento, encontre a solução do
sistema usando eliminação de Gauss sem Pivotamento.
Solução
Temos que
1 ′
m21 = = 10000 ⇒ L2 = L2 − 10000L1
0.0001
66 / 168
Pivotamento Parcial
Solução (efeitos numéricos) - Cont.
0.0001 1 1
0 −10000∗ −10000∗∗
Note que (∗) foi obtido como
1 − 10000 × 1 = 0.00001 × 105 − 0.10000 × 105
= 0.09999 × 105
= (arredondando) = 0.100 × 105
e de forma análoga para (∗∗), temos
2 − 10000 × 1 = 0.00001 × 105 − 0.10000 × 105
= 0.09998 × 105
= (arredondando) = 0.100 × 105
67 / 168
Pivotamento Parcial
Solução (efeitos numéricos) - Cont.
Por fim, aplicando a retrosubstituição obtemos uma solução errada, devido
aos erros de aritmética em ponto flutuante cometidos em (∗) e (∗∗) durante a
soma/subtração de números muito pequenos com números muito grandes.
→ xT = 0 1
Solução obtida
68 / 168
Pivotamento Parcial
Solução (efeitos numéricos) - Cont.
Por fim, aplicando a retrosubstituição obtemos uma solução errada, devido
aos erros de aritmética em ponto flutuante cometidos em (∗) e (∗∗) durante a
soma/subtração de números muito pequenos com números muito grandes.
→ xT = 0 1
Solução obtida
A solução exata é dada por
xT =
Solução exata → 1.00010001 0.99989999
68 / 168
Pivotamento Parcial
Se durante o processo de eliminação com Pivotamento parcial no passo k não
houver nenhuma entrada não-zero abaixo de akk na coluna k, como no
exemplo abaixo (depois do passo 1):
x x x x x
0 0 x x x
0 0 x x x
0 0 x x x
0 0 x x x
então:
▶ podemos seguir para o próximo passo e completar a eliminação
▶ entretanto a matriz triangular superior U resultante do processo possui
um zero na diagonal principal, o que implica que
det U = 0 ⇒ U é singular ⇒ A é singular
69 / 168
Pivotamento Parcial
para k = 1 : n − 1 faça
w = |A(k,k)|;
para j = k : n faça
se |A(j,k)| > w então
w = |A(j,k)|;
r = j;
fim-se
fim-para
trocaLinhas(k,r);
para i = k + 1 : n faça
m = A(i,k) / A(k,k);
para j = k + 1 : n faça
A(i,j) = A(i,j) - m*A(k,j) ;
fim-para
b(i) = b(i) - m*b(k) ;
fim-para
fim-para 70 / 168
Pivotamento Total
Na estratégia de Pivotamento total, o elemento escolhido como pivô é o maior
elemento em módulo que ainda atua no processo de eliminação, isto é:
Encontrar r e s tais que: |ars | = max |aij |, k ≤ i, j ≤ n
Feita a escolha do pivô é preciso trocar as linhas k e r e as colunas k e s.
71 / 168
Pivotamento Total
Na estratégia de Pivotamento total, o elemento escolhido como pivô é o maior
elemento em módulo que ainda atua no processo de eliminação, isto é:
Encontrar r e s tais que: |ars | = max |aij |, k ≤ i, j ≤ n
Feita a escolha do pivô é preciso trocar as linhas k e r e as colunas k e s.
Observe que a troca de colunas afeta a ordem das incógnitas do vetor x.
71 / 168
Pivotamento Total
Na estratégia de Pivotamento total, o elemento escolhido como pivô é o maior
elemento em módulo que ainda atua no processo de eliminação, isto é:
Encontrar r e s tais que: |ars | = max |aij |, k ≤ i, j ≤ n
Feita a escolha do pivô é preciso trocar as linhas k e r e as colunas k e s.
Observe que a troca de colunas afeta a ordem das incógnitas do vetor x.
Em geral o Pivotamento parcial é satisfatório, e o Pivotamento total não é
muito usado devido ao alto esforço computacional requerido na busca pelo
maior elemento em módulo no resto da matriz.
71 / 168
Estratégias de Pivotamento
Pivoteamento Parcial Pivoteamento Total
maior elemento
em valor absoluto maior elemento
em valor absoluto
72 / 168
Eliminação de Gauss e Método de Gauss-Jordan
▶ Objetivo:
▶ Eliminação de Gauss: Reduz a matriz a uma forma triangular superior
(forma escalonada) para resolver o sistema por substituição regressiva.
▶ Gauss-Jordan: Reduz a matriz à forma escalonada reduzida, onde os
pivôs são 1 e são os únicos elementos não nulos em suas colunas,
permitindo uma solução direta.
▶ Operações:
▶ Ambos utilizam operações elementares de linha (troca de linhas,
multiplicação por escalar, e soma de múltiplos de linhas).
▶ No Gauss-Jordan, as operações continuam até que os elementos acima e
abaixo dos pivôs sejam zerados.
▶ Forma Final da Matriz:
▶ Eliminação de Gauss: Forma triangular superior.
▶ Gauss-Jordan: Forma escalonada reduzida (matriz identidade na parte
dos coeficientes).
73 / 168
Eliminação de Gauss e Método de Gauss-Jordan
▶ Esforço Computacional:
▶ Eliminação de Gauss: Menor esforço, pois para na forma triangular
superior.
▶ Gauss-Jordan: Maior esforço devido à necessidade de zerar elementos
acima e abaixo dos pivôs.
▶ Aplicações:
▶ Eliminação de Gauss: Resolver sistemas de equações lineares de forma
eficiente.
▶ Gauss-Jordan: Encontrar a inversa de matrizes ou resolver diretamente
múltiplos sistemas.
74 / 168
Diferença nas Formas Finais
Eliminação de Gauss Gauss-Jordan (Escalonada
(Triangular): Reduzida):
a11 a12 a13 b1 1 0 0 x1
0 a22 a23 b2 0 1 0 x2
0 0 a33 b3 0 0 1 x3
Requer retro-substituição. Solução direta disponível.
75 / 168
Decomposição LU
Uma matriz quadrada pode ser escrita como o produto de duas matrizes L e
U, onde
▶ L é uma matriz triangular inferior unitária (com elementos da diagonal
principal igual a 1)
▶ U é uma matriz triangular superior
76 / 168
Decomposição LU
Uma matriz quadrada pode ser escrita como o produto de duas matrizes L e
U, onde
▶ L é uma matriz triangular inferior unitária (com elementos da diagonal
principal igual a 1)
▶ U é uma matriz triangular superior
Ou seja, a matriz pode ser escrita como
A = LU
76 / 168
Decomposição LU
Uma matriz quadrada pode ser escrita como o produto de duas matrizes L e
U, onde
▶ L é uma matriz triangular inferior unitária (com elementos da diagonal
principal igual a 1)
▶ U é uma matriz triangular superior
Ou seja, a matriz pode ser escrita como
A = LU
Dessa forma para resolver o sistema linear Ax = b usamos A em sua forma
decomposta, isto é
Ax = b ⇒ LUx = b
Então definimos
Ux = y
76 / 168
Decomposição LU
Assim para resolver
Ux = b
L |{z}
y
fazemos
Ly = b ⇒ Ux = y
isto é, temos os seguintes passos:
1. Como L é triangular inferior podemos resolver Ly = b facilmente
usando o algoritmo de substituição. Assim encontramos o vetor y.
2. Em seguida substituimos y no sistema Ux = y. Como U é uma matriz
triangular superior, podemos resolver este sistema usando o algoritmo da
retro-substituição para encontrar a solução x.
Vamos ver agora em que condições podemos decompor uma matriz A na
forma LU.
77 / 168
Decomposição LU
Teorema (LU)
Sejam A = (aij ) uma matriz quadrada de ordem n e Ak o menor principal,
constituído das k primeiras linhas e k primeiras colunas de A.
Assumimos que det(Ak ) ̸= 0 para k = 1, 2, . . . , n − 1.
Então existe:
▶ uma única matriz triangular inferior L = (lij ) com lii = 1, i = 1 : n
▶ uma única matriz triangular superior U = (uij )
tal que A = LU.
Além disso, det(A) = u11 u22 . . . unn .
Prova (Neide, Página 123)
Usa indução matemática.
78 / 168
Decomposição LU
Prova
(i) Para n = 1 temos
a11 = 1 a11 = 1 u11 ⇒ u11 = a11 , l11 = 1
e ainda det(A) = u11 .
79 / 168
Decomposição LU
Prova
(i) Para n = 1 temos
a11 = 1 a11 = 1 u11 ⇒ u11 = a11 , l11 = 1
e ainda det(A) = u11 .
(ii) Assumimos que o teorema é verdadeiro para n = k − 1, ou seja, que toda
matriz de ordem (k − 1) é decomponível no produto LU.
79 / 168
Decomposição LU
Prova
(i) Para n = 1 temos
a11 = 1 a11 = 1 u11 ⇒ u11 = a11 , l11 = 1
e ainda det(A) = u11 .
(ii) Assumimos que o teorema é verdadeiro para n = k − 1, ou seja, que toda
matriz de ordem (k − 1) é decomponível no produto LU.
(iii) Vamos mostrar que podemos decompor A para n = k. Seja A de ordem k,
escrita da forma
Ak−1 r
A= (1)
s akk
Por hipótese de indução temos que
79 / 168
Decomposição LU
Prova (cont.)
Usando (2) temos
Lk−1 0 Uk−1 p
A = LU ⇒ L= , U=
m 1 0 ukk
onde m, p e ukk são desconhecidos.
80 / 168
Decomposição LU
Prova (cont.)
Usando (2) temos
Lk−1 0 Uk−1 p
A = LU ⇒ L= , U=
m 1 0 ukk
onde m, p e ukk são desconhecidos. Efetuando o produto temos
Lk−1 Uk−1 Lk−1 p
LU = (3)
mUk−1 mp + ukk
80 / 168
Decomposição LU
Prova (cont.)
Usando (2) temos
Lk−1 0 Uk−1 p
A = LU ⇒ L= , U=
m 1 0 ukk
onde m, p e ukk são desconhecidos. Efetuando o produto temos
Lk−1 Uk−1 Lk−1 p
LU = (3)
mUk−1 mp + ukk
Comparando (1) e (3)
Ak−1 r L U Lk−1 p
A= = k−1 k−1
s akk mUk−1 mp + ukk
80 / 168
Decomposição LU
Prova (cont.)
Assim
Ak−1 = Lk−1 Uk−1
r = Lk−1 p
s = mUk−1
mp + ukk = akk
Observe que
▶ pela hip. de indução Lk−1 e Uk−1 são unicamente determinadas
▶ e ainda, Lk−1 e Uk−1 não são singulares, caso contrário Ak−1 também
seria, contrariando a hipótese
81 / 168
Decomposição LU
Prova (cont.)
Portanto
r = Lk−1 p ⇒ p = L−1
k−1 r
s = mUk−1 ⇒ m = sU−1
k−1
mp + ukk = akk ⇒ ukk = akk − mp
Ou seja, m, p e ukk são determinados unicamente nesta ordem e, portanto, L
e U são determinados unicamente.
Finalmente
det(A) = det(L)det(U) = 1 det(U) = u11 u22 . . . unn
82 / 168
Decomposição LU
Podemos obter as matrizes L e U aplicando a definição de produto e
igualdade de matrizes, ou seja, impondo que A seja igual a LU, onde L é
triangular inferior unitária e U triangular superior. Então
1 0 0 . . . 0 u11 u12 u13 . . . u1n
l21 1 0 . . . 0 0 u22 u23 . . . u2n
LU = l31 l32 1 . . . 0 0 0 u33 . . . u3n
.. .. . . .. .. .. .. ..
. . . 1 0 . . . . .
ln1 ln2 ln3 . . . 1 0 0 0 0 unn
Vamos obter os elementos de L e U da seguinte forma:
▶ 1a linha de U
▶ 1a coluna de L
▶ 2a linha de U
▶ 2a coluna de L
▶ ...
83 / 168
Decomposição LU
1a linha de U
a11 = 1 u11 ⇒ u11 = a11
a12 = 1 u12 ⇒ u12 = a12
...
a1n = 1 u1n ⇒ u1n = a1n
84 / 168
Decomposição LU
1a linha de U
a11 = 1 u11 ⇒ u11 = a11
a12 = 1 u12 ⇒ u12 = a12
...
a1n = 1 u1n ⇒ u1n = a1n
1a coluna de L
a21
a21 = l21 u11 ⇒ l21 = u11
a31
a31 = l31 u11 ⇒ l31 = u11
...
an1
an1 = ln1 u11 ⇒ ln1 = u11
84 / 168
Decomposição LU
2a linha de U
a22 = l21 u12 + 1 u22 ⇒ u22 = a22 − l21 u12
a23 = l21 u13 + 1 u23 ⇒ u23 = a23 − l21 u13
...
a2n = l21 u1n + 1 u2n ⇒ u2n = a2n − l21 u1n
85 / 168
Decomposição LU
2a linha de U
a22 = l21 u12 + 1 u22 ⇒ u22 = a22 − l21 u12
a23 = l21 u13 + 1 u23 ⇒ u23 = a23 − l21 u13
...
a2n = l21 u1n + 1 u2n ⇒ u2n = a2n − l21 u1n
2a coluna de L
a32 − l31 u12
a32 = l31 u12 + l32 u22 ⇒ l32 =
u22
a42 − l41 u1
a42 = l41 u12 + l42 u22 ⇒ l42 =
u22
...
an2 − ln1 u12
an2 = ln1 u12 + ln2 u22 ⇒ ln2 =
u22
85 / 168
Decomposição LU
De forma geral temos
i−1
X
uij = aij − lik ukj , i≤j
k=1
j−1
!,
X
lij = aij − lik ukj ujj , i>j
k=1
86 / 168
Decomposição LU
para i = 1 : n faça
para j = i : n faça
Pi−1
uij = aij − k=1 lik ukj ;
fim-para
para j = i + 1 : n faça ,
Pj−1
lij = aij − k=1 lik ukj ujj ;
fim-para
fim-para
87 / 168
Decomposição LU
para i = 1 : n faça
para j = i : n faça
Pi−1
uij = aij − k=1 lik ukj ;
fim-para
para j = i + 1 : n faça ,
Pj−1
lij = aij − k=1 lik ukj ujj ;
fim-para
fim-para
Observação: na prática as matrizes L e U nunca são criadas e alocadas
explicitamente. O que fazemos é sobrescrever as entradas da matriz original
A com as entradas de L e U.
87 / 168
Decomposição LU
O método da eliminação de Gauss pode ser interpretado como um método
para obtenção das matrizes L e U. No processo da EG no passo 1, eliminamos
as entradas abaixo de a11 na coluna 1 da matriz fazendo
ai1
Para i = 2 : n mi1 =
a11
aij = a0ij − mi1 a01j
1
b1i = b0i − mi1 b01 , j=1:n
essa operação é equivalente a multiplicar (A|b)0 por uma matriz M1 , para
obter (A|b)1 , onde
1 0 0 ... 0
−m21 1 0 . . . 0
−m31 0 1 . . . 0
M1 =
.. .. .. . .
. . . . 0
−mn1 0 . . . 0 1
88 / 168
Decomposição LU
Assim
1 0 0 . . . 0 a11 a12 . . . a1n b1
−m21 1 0 . . . 0 a21 a22 . . . a2n b2
M1 (A|b)0 = −m31 0 1 . . . 0 a31 a32 . . . a3n b3
.. .. .. . . . .. .. .. ..
. . . . 0 .. . . . .
−mn1 0 . . . 0 1 an1 an2 . . . ann bn
89 / 168
Decomposição LU
Assim
1 0 0 ... 0 a11 a12 . . . a1n b1
−m21 1 0 ... 0 . . . a2n
a21 a22 b2
M1 (A|b)0 = −m31 0 1 ... 0 a31 a32 . . . a3n b3
.. .. .. .. .. .. .. .. ..
. . . . 0 . . . . .
−mn1 0 ... 0 1 an1 an2 . . . ann bn
a11 a12 . . . a1n b1
0 a1 . . . a12n b12
22
1 . . . a13n b13
= 0 a32 = (A|b)1
.. .. .. .. ..
. . . . .
0 a1n2 . . . a1nn b1n
89 / 168
Decomposição LU
No passo seguinte temos
(A|b)2 = M2 (A|b)1
1 0 0 . . . 0 a11 a12 . . . a1n b1
0
1 0 . . . 0 0
a122 . . . a12n b12
M2 (A|b)1 = 0 −m32 1 . . . 0 0
a132 . . . a13n b13
.. .. .. . . . .. .. .. ..
. . . . 0 .. . . . .
0 −mn2 . . . 0 1 0 1
an2 . . . ann b1n
1
90 / 168
Decomposição LU
No passo seguinte temos
(A|b)2 = M2 (A|b)1
1 0 0 ... 0 a11 a12 . . . a1n b1
0 1 0 ... 0 1 . . . a12n b12
0 a22
0 −m32 1 ... 0 1 . . . a13n b13
1
M2 (A|b) = 0 a32
.. .. .. .. . .. .. .. ..
. . . . 0 .. . . . .
0 −mn2 ... 0 1 0 an21 1
. . . ann b1n
a11 a12 . . . a1n b1
0 a1 . . . a12n b12
22
= 0
0 . . . a23n b23
= (A|b)2
.. .. .. .. ..
. . . . .
0 0 . . . ann b2n
2
90 / 168
Decomposição LU
Procedemos dessa forma, até que por fim temos
(A|b)(n−1) = Mn−1 (A|b)(n−2)
91 / 168
Decomposição LU
Procedemos dessa forma, até que por fim temos
(A|b)(n−1) = Mn−1 (A|b)(n−2)
= . . . = Mn−1 Mn−2 . . . M2 M1 (A|b)(0)
| {z }
M
91 / 168
Decomposição LU
Procedemos dessa forma, até que por fim temos
(A|b)(n−1) = Mn−1 (A|b)(n−2)
= . . . = Mn−1 Mn−2 . . . M2 M1 (A|b)(0)
| {z }
M
Deste modo temos
A(n−1) = MA = U
onde U é a matriz triangular superior da decomposição LU. Como M é um
produto de matrizes não-singulares, M é inversível, isto é,
M = Mn−1 Mn−2 . . . M2 M1
M −1
= M−1 −1 −1 −1
1 M2 . . . Mn−2 Mn−1
Portanto
−1
MA = U ⇒ A=M
|{z} U
L
91 / 168
Decomposição LU
−1
MA = U ⇒ A=M
|{z} U
L
onde
1 0 0 ... 0
m21 1
0 ... 0
M−1 = L = m31 m32 1 ... 0
.. .. .. ..
. . . .0
mn1 mn2 mn3 ... 1
é a matriz triangular inferior da decomposição LU.
92 / 168
Decomposição LU
Exemplo 1
Decomponha a matriz A dada abaixo nos fatores L e U, usando a eliminação
de Gauss.
2 1 1 0
4 3 3 1
A= 8 7 9 5
6 7 9 8
93 / 168
Decomposição LU
Exemplo 1
Decomponha a matriz A dada abaixo nos fatores L e U, usando a eliminação
de Gauss.
2 1 1 0
4 3 3 1
A= 8 7 9 5
6 7 9 8
Solução do Exemplo 1
2 1 1 0 1 0 0 0 2 1 1 0
4 3 3 1 2 1 0 0
0 1 1 1
A=
8 =
7 9 5 4 3 1 0 0
0 2 2
6 7 9 8 3 4 1 1 0 0 0 2
| {z }| {z } 93 / 168
Decomposição LU
Exemplo 2
Resolva o seguinte sistema linear:
1 2 −1 x1 2
2 3 −2 x2 = 3
1 −2 1 x3 0
94 / 168
Decomposição LU
Exemplo 2
Resolva o seguinte sistema linear:
1 2 −1 x1 2
2 3 −2 x2 = 3
1 −2 1 x3 0
Solução do Exemplo 2
1 0 0 1 2 −1
A = LU = 2 1 0 0 −1 0
1 4 1 0 0 2
94 / 168
Decomposição LU
Exemplo 2
Resolva o seguinte sistema linear:
1 2 −1 x1 2
2 3 −2 x2 = 3
1 −2 1 x3 0
Solução do Exemplo 2
1 0 0 1 2 −1 1
∗
A = LU = 2 1 0 0 −1 0 , x = 1
1 4 1 0 0 2 1
94 / 168
Decomposição LU
Veremos como utilizar a decomposição A = LU para calcular o determinante
da matriz.
det(A) = det(L)det(U)
O determinante de uma matriz triangular é dado pelo produto dos elementos
da diagonal principal, isto é
det(L) = 1
det(U) = u11 u22 u33 . . . unn
Portanto
det(A) = det(L) det(U)
= 1 det(U)
= u11 u22 u33 . . . unn
95 / 168
Decomposição LU
Exemplo 2
Para o exemplo anterior, temos
1 0 0 1 2 −1
A = 2 1 0 0 −1 0
1 4 1 0 0 2
96 / 168
Decomposição LU
Exemplo 2
Para o exemplo anterior, temos
1 0 0 1 2 −1
A = 2 1 0 0 −1 0
1 4 1 0 0 2
Portanto o determinante é
det(A) = 1 (−1) 2 = −2
96 / 168
Decomposição LU com Pivotamento Parcial
Vamos estudar agora o uso de Pivotamento parcial para a decomposição LU.
Para definir o que significa, de forma matricial, a troca de duas linhas de uma
matriz, iremos apresentar o conceito de matrizes de permutação.
Uma matriz de permutação é uma matriz obtida a partir da matriz identidade
através de uma reordenação de suas linhas, isto é
0 0 1
P = 0 1 0
1 0 0
Portanto se P é uma matriz de permutação e A uma matriz qualquer, então
▶ PA é uma versão da matriz A com as linhas permutadas
▶ AP é uma versão da matriz A com as colunas permutadas
97 / 168
Decomposição LU com Pivotamento Parcial
Na prática (implementação) uma matriz de permutação P de dimensão n × n
nunca é armazenada explicitamente. É muito mais eficiente representar P por
um vetor p de valores inteiros de tamanho n.
Uma forma de implementar isso é fazer com que p[k] seja o índice da
coluna que tem apenas um "1"na k-ésima linah de P. Para o exemplo anterior
p = [3 2 1]
98 / 168
Decomposição LU com Pivotamento Parcial
Na prática (implementação) uma matriz de permutação P de dimensão n × n
nunca é armazenada explicitamente. É muito mais eficiente representar P por
um vetor p de valores inteiros de tamanho n.
Uma forma de implementar isso é fazer com que p[k] seja o índice da
coluna que tem apenas um "1"na k-ésima linah de P. Para o exemplo anterior
p = [3 2 1]
Para aplicar a estratégia de Pivotamento parcial nos exercícios, basta trocar
efetivamente as linhas da matriz. Vejamos um exemplo.
98 / 168
Decomposição LU com Pivotamento Parcial
Para resolver Ax = b, segue-se o procedimento:
▶ Calcular P, L e U tal que PA = LU
▶ Atualizar vetor b = Pb
▶ Resolver Ly = b
▶ Resolver Ux = y
Dicas para calcular L e U via eliminação de Gauss com Pivotamento:
▶ se trocar linhas, atualizar o vetor p;
▶ guardar os multiplicadores da eliminação de Gauss na posição que foi
zerada, ao invés de colocar os zeros.
99 / 168
Decomposição LU com Pivotamento Parcial
Exemplo 3
Resolver o sistema linear abaixo usando a decomposição LU com
Pivotamento parcial.
3 −4 1 x1 9
1 2 2 x2 = 3
4 0 −3 x3 −2
100 / 168
Decomposição LU com Pivotamento Parcial
Exemplo 3
Resolver o sistema linear abaixo usando a decomposição LU com
Pivotamento parcial.
3 −4 1 x1 9
1 2 2 x2 = 3
4 0 −3 x3 −2
Solução do Exemplo 3
1 0 0 4 0 −3
L = 34 U = 0 −4 13
1 0 , 4
, p= 3 1 2
1
4 − 12 1 0 0 35
8
xT = 1 −1 2
100 / 168
Decomposição LU com Pivotamento Parcial
Solução do Exemplo 3 - Passo a passo
Etapa 1
3 −4 1
1 2 2 , p= 1 2 3
4 0 −3
Troca as linhas 1 e 3 e atualiza vetor p
4 0 −3
1 2 2 , p= 3 2 1
3 −4 1
Elimina e guarda os multiplicadores nas suas posições (em azul):
4 0 −3
1/4 2 11/4 , p = 3 2 1
3/4 −4 13/4 101 / 168
Decomposição LU com Pivotamento Parcial
Solução do Exemplo 3 - Passo a passo
Etapa 2
4 0 −3
1/4 2 11/4 , p= 3 2 1
3/4 −4 13/4
Troca as linhas 2 e 3 e atualiza vetor p
4 0 −3
3/4 −4 13/4 , p= 3 1 2
1/4 2 11/4
Elimina e guarda os multiplicadores nas suas posições (em azul):
4 0 −3
3/4 −4 13/4 , p = 3 1 2
1/4 −1/2 35/8 102 / 168
Decomposição LU com Pivotamento Parcial
Solução do Exemplo 3 - Passo a passo
Resultado
4 0 −3
3/4 −4 13/4 , p= 3 1 2
1/4 −1/2 35/8
Decomposição PA = LU:
0 0 1 3 −4 1
P = 1 0 0 , A = 1 2 2
0 1 0 4 0 −3
1 0 0 4 0 −3
L = 3/4 1 0 , U = 0 −4 13/4
1/4 −1/2 1 0 0 35/8
103 / 168
Decomposição LU com Pivotamento Parcial
Solução do Exemplo 3
Para resolver PAx = Pb ⇒ LUx = Pb, define-se Ux = y e então:
1. Resolva Ly = Pb
2. Resolva Ux = y
Procedendo desta forma, chega-se em
1 0 0 4 0 −3
L = 43 1 0 , U = 0 −4 13
, p= 3 1 2
4
1 1 35
4 −2 1 0 0 8
xT = 1 −1 2
104 / 168
Conteúdo
▶ Aula passada
▶ Eliminação de Gauss
▶ Estratégias de Pivotamento
▶ Decomposição LU
▶ Aula de hoje
▶ Decomposição de Cholesky
▶ Decomposição LDLT
▶ Cálculo da Matriz Inversa
▶ Sistema com Matriz Singular
105 / 168
Revisitando algumas definições
Definição (Matriz Simétrica)
Uma matriz real A ∈ Rn×n é simétrica se possui as mesmas entradas acima e
abaixo da diagonal principal, isto é, se
aij = aji , ∀ i, j
Portanto A = AT .
106 / 168
Revisitando algumas definições
Definição (Matriz Simétrica)
Uma matriz real A ∈ Rn×n é simétrica se possui as mesmas entradas acima e
abaixo da diagonal principal, isto é, se
aij = aji , ∀ i, j
Portanto A = AT .
Tais matrizes satisfazem a seguinte relação
xT Ay = yT Ax, ∀ x, y ∈ Rn
Definição (Matriz Positiva Definida)
Se a matriz A é simétrica, então é dita ser positiva definida se
xT Ax > 0, ∀x ̸= 0
106 / 168
Revisitando algumas definições
Matriz Positiva Definida: de imediato verifica-se que se A é não singular,
caso contrário haveria um x diferente de zero tal que Ax = 0.
107 / 168
Revisitando algumas definições
Matriz Positiva Definida: de imediato verifica-se que se A é não singular,
caso contrário haveria um x diferente de zero tal que Ax = 0.
Além disso, escolhendo vetores escritos na forma
xT = x1 x2 . . . xk 0 0 . . . 0
podemos verificar que todas as matrizes menores principais (Ak ) são positivas
definidas, portanto não singular (det(Ak ) ̸= 0) e consequentemente podemos
decompor A na forma A = LU.
107 / 168
Revisitando algumas definições
Matriz Positiva Definida: de imediato verifica-se que se A é não singular,
caso contrário haveria um x diferente de zero tal que Ax = 0.
Além disso, escolhendo vetores escritos na forma
xT = x1 x2 . . . xk 0 0 . . . 0
podemos verificar que todas as matrizes menores principais (Ak ) são positivas
definidas, portanto não singular (det(Ak ) ̸= 0) e consequentemente podemos
decompor A na forma A = LU.
Na prática muitas matrizes que surgem em aplicações de engenharias e
ciências são simétricas e positiva definidas, devido a leis físicas que estão por
trás da origem dessas matrizes.
107 / 168
Testes para matrizes positivas definidas
1. Critério de Sylvester: uma matriz A ∈ Rn×n é positiva definida, se e
somente se
det(Ak ) > 0, k = 1, 2, . . . , n
onde Ak é a matriz menor principal de ordem k (a matriz k × k formada
pelas k primeiras linhas e pelas k primeiras colunas).
108 / 168
Testes para matrizes positivas definidas
1. Critério de Sylvester: uma matriz A ∈ Rn×n é positiva definida, se e
somente se
det(Ak ) > 0, k = 1, 2, . . . , n
onde Ak é a matriz menor principal de ordem k (a matriz k × k formada
pelas k primeiras linhas e pelas k primeiras colunas).
2. Se realizarmos a eliminação de Gauss sem troca de linha ou coluna na
matriz A, podemos dizer que A é positiva definida, se e somente se,
todos os pivôs forem positivos.
108 / 168
Testes para matrizes positivas definidas
1. Critério de Sylvester: uma matriz A ∈ Rn×n é positiva definida, se e
somente se
det(Ak ) > 0, k = 1, 2, . . . , n
onde Ak é a matriz menor principal de ordem k (a matriz k × k formada
pelas k primeiras linhas e pelas k primeiras colunas).
2. Se realizarmos a eliminação de Gauss sem troca de linha ou coluna na
matriz A, podemos dizer que A é positiva definida, se e somente se,
todos os pivôs forem positivos.
Exemplo
Verifique se as seguintes matrizes são positivas definidas:
4 1 2 4 4 2 2 −1 0
A = 1 3 0 , B = 4 3 0 , K = −1 2 −1
2 0 5 2 0 5 0 −1 2
108 / 168
Decomposição de Cholesky
Quando a matriz do sistema linear é simétrica, podemos simplificar os
cálculos da decomposição LU levando em conta a simetria da matriz. Essa é a
idéia do método de Cholesky.
Se A é simétrica positiva definida, pelo critério de Sylvester temos que
det(Ak ) > 0
portanto, todos os menores principais são não singulares e consequentemente
(Teorema LU), a matriz pode ser escrita como A = LU.
Se A é simétrica, então A = AT . Logo
LU = A = AT = (LU)T = UT LT
109 / 168
Decomposição de Cholesky
Assim
LU = UT LT
L−1 LU = L−1 UT LT
U = L−1 UT LT
U(LT )−1 = L−1 UT LT (LT )−1
U(LT )−1 = L−1 UT
110 / 168
Decomposição de Cholesky
Assim
LU = UT LT
L−1 LU = L−1 UT LT
U = L−1 UT LT
U(LT )−1 = L−1 UT LT (LT )−1
U(LT )−1 = L−1 UT
Temos que
U(LT )−1 = L −1 T
| {zU }
| {z }
triangular superior triangular inferior
110 / 168
Decomposição de Cholesky
Assim
LU = UT LT
L−1 LU = L−1 UT LT
U = L−1 UT LT
U(LT )−1 = L−1 UT LT (LT )−1
U(LT )−1 = L−1 UT
Temos que
U(LT )−1 = L −1 T
| {zU }
| {z }
triangular superior triangular inferior
Portanto, essa igualdade só pode ser uma matriz diagonal!
110 / 168
Decomposição de Cholesky
Assim
LU = UT LT
L−1 LU = L−1 UT LT
U = L−1 UT LT
U(LT )−1 = L−1 UT LT (LT )−1
U(LT )−1 = L−1 UT
Temos que
U(LT )−1 = L −1 T
| {zU }
| {z }
triangular superior triangular inferior
Portanto, essa igualdade só pode ser uma matriz diagonal!
Seja
D = U(LT )−1 (ou D = L−1 UT )
110 / 168
Decomposição de Cholesky
Seja
D = U(LT )−1 (ou D = L−1 UT )
então
DLT = U (ou UT = LD)
Sendo assim temos que
A = LDLT = UT DU (4)
111 / 168
Decomposição de Cholesky
Seja
D = U(LT )−1 (ou D = L−1 UT )
então
DLT = U (ou UT = LD)
Sendo assim temos que
A = LDLT = UT DU (4)
E assim o determinante pode ser calculado como
det(A) = det(L)det(D)det(LT ) = 1 · (d11 d22 . . . dnn ) · 1
= d11 d22 . . . dnn
111 / 168
Decomposição de Cholesky
Assim de (4), como todos dii > 0, podemos escrever
A = LDLT = L(D)1/2 (D)1/2 LT = GGT
onde
G = L(D)1/2
GT = (D)1/2 LT
112 / 168
Decomposição de Cholesky
Assim de (4), como todos dii > 0, podemos escrever
A = LDLT = L(D)1/2 (D)1/2 LT = GGT
onde
G = L(D)1/2
GT = (D)1/2 LT
A decomposição de Cholesky é um caso especial da fatoração LU aplicada
para matrizes simétricas e positiva definida (SPD) e sua decomposição pode
ser obtida a partir de
A = GGT
onde G é uma matriz triangular inferior tal que
a11 a12 ... a1n g11 0 ... 0 g11 g21 ... gn1
a21 a22 ... a2n g21 g22 ... 0 0 g22 ... g2n
A= . .. = ..
.. .. .. .. . .. .. ..
.. . . . . . . 0 .. . . .
an1 an2 ... ann gn1 gn2 ... gnn 0 0 ... gnn
112 / 168
Decomposição de Cholesky
Pelo produto e igualdade de matrizes podemos obter os elementos de G.
Elementos da diagonal principal:
a11 = g211
a22 = g221 + g222
..
.
ann = g2n1 + g2n2 + . . . + g2nn
de forma geral
v
u
u i−1
X
gii = taii − g2ik , i=1:n (5)
k=1
113 / 168
Decomposição de Cholesky
Para os elementos fora da diagonal principal, temos
a21 = g21 g11
a31 = g31 g11
..
.
an1 = gn1 g11
a32 = g31 g21 + g32 g22
a42 = g41 g21 + g42 g22
..
.
an2 = gn1 g21 + gn2 g22
de forma geral
j−1
X
aij − gik gjk
k=1
gij = , i = j + 1 : n, j=1:n (6)
114 / 168
Decomposição de Cholesky
Observando as equações (5) e (6), vemos que podemos calcular os elementos
de G da seguinte forma:
▶ a cada passo j:
▶ calcula-se termo da diagonal principal gjj
▶ calcula-se termos da coluna j abaixo da diagonal principal isto é gij com
i=j+1:n
115 / 168
Decomposição de Cholesky
Observando as equações (5) e (6), vemos que podemos calcular os elementos
de G da seguinte forma:
▶ a cada passo j:
▶ calcula-se termo da diagonal principal gjj
▶ calcula-se termos da coluna j abaixo da diagonal principal isto é gij com
i=j+1:n
para j = v
1 : n faça
u j−1
X
u
gjj = ajj −
t g2jk ;
k=1
para i = j + 1 : n faça
j−1
!,
X
gij = aij − gik gjk gjj ;
k=1
fim-para
fim-para
115 / 168
Decomposição de Cholesky
Observações:
▶ Se A é SPD, então a aplicação do método de Cholesky requer menos
operações de ponto flutuante do que a decomposição LU.
▶ Como A é positiva definida, isto garante que só teremos raízes quadradas
de números positivos, isto é, os termos ajj − j−1 2
P
k=1 gjk são sempre
maiores do que zero.
▶ Exemplo do caso 2 × 2
▶ Caso o algoritmo falhe, podemos concluir que A não é simétrica e
positiva definida.
▶ Determinante
det(A) = det(G)det(GT ) = det(G)2 = (g11 g22 . . . gnn )2
116 / 168
Decomposição de Cholesky
Podemos usar a decomposição de Cholesky para encontrar a solução de
Ax = b da seguinte forma:
1. Determinar a decomposição
A = GGT
então
GT x = b
G |{z}
y
2. Resolver Gy = b, usando substituição
3. Resolver GT x = y, retro-substituição
117 / 168
Decomposição de Cholesky
Exemplo
Considere a matriz
4 −2 2
A = −2 10 −7
2 −7 30
a) Verificar se A satisfaz as condições da decomposição de Cholesky
b) Decompor A em GGT
c) Calcular o determinante
8
d) Resolver o sistema Ax = b com b = 11
−31
118 / 168
Decomposição de Cholesky
Solução do Exemplo
a) A é simétrica e positiva definida
det(A1 ) = 4, det(A2 ) = 36, det(A3 ) = 900
b) A decomposição é
2 0 0 2 −1 1
A = −1 3 0 0 3 −2
1 −2 5 0 0 5
| {z }| {z }
G GT
c) det(A) = (2 · 3 · 5)2 = 302 = 900
3
d) x = 1
−1
119 / 168
Decomposição de Cholesky
Podemos usar as fórmulas (5) e (6) para calcular os elementos da matriz G da
decomposição, mas também podemos proceder de outra forma.
Idéia:
▶ Decompor A = LU via eliminação de Gauss
▶ Como U = DLT , calcular D
▶ E assim calcular G = LD1/2
Exemplo
A partir da decomposição LU da matriz A do exemplo anterior, obtenha G.
4 −2 2 1 0 0 4 −2 2
A = −2 10 −7 = − 12 1 0 0 9 −6
1
2 −7 30 − 2 1 0 0 25
| 2 {z 3 }| {z }
L U
120 / 168
Decomposição de Cholesky
Exercício
Mostrar que, se o sistema linear Ax = b, onde A é não singular, é
transformado no sistema linear equivalente
AT Ax = AT b
então esse último sistema linear pode sempre ser resolvido pelo método de
Cholesky (isto é B = AT A satisfaz as condições para a aplicação do método).
Aplicar a técnica anterior para encontrar a solução do seguinte sistema linear:
1 0 1 x1 4
1 1 0 x2 = 2
1 −1 0 x3 2
121 / 168
Decomposição de Cholesky
Exercício
Dicas:
▶ Mostre que B satisfaz as condições da decomposição de Cholesky
▶ Irá precisar de usar
q
||x|| = x12 + x22 + . . . + xn2
||x||2 = x12 + x22 + . . . + xn2 = xT x
122 / 168
Decomposição LDLT
Como vimos anteriormente também podemos decompor A na forma
A = LDLT , onde L é uma matriz triangular inferior unitária e D é uma matriz
diagonal.
De forma análoga ao que fizemos para a decomposição de Cholesky, podemos
determinar os elementos da decomposição da seguinte forma:
123 / 168
Decomposição LDLT
Como vimos anteriormente também podemos decompor A na forma
A = LDLT , onde L é uma matriz triangular inferior unitária e D é uma matriz
diagonal.
De forma análoga ao que fizemos para a decomposição de Cholesky, podemos
determinar os elementos da decomposição da seguinte forma:
j−1
X
2
djj = ajj − ljk dkk , j=1:n
k=1
123 / 168
Decomposição LDLT
Como vimos anteriormente também podemos decompor A na forma
A = LDLT , onde L é uma matriz triangular inferior unitária e D é uma matriz
diagonal.
De forma análoga ao que fizemos para a decomposição de Cholesky, podemos
determinar os elementos da decomposição da seguinte forma:
j−1
X
2
djj = ajj − ljk dkk , j=1:n
k=1
Xj−1
aij − lik dkk ljk
k=1
lij = j = 1 : n − 1, i=j+1:n
djj
123 / 168
Decomposição LDLT
A solução do sistema linear Ax = b é dada por
Ax = b ⇒ LT x = b
LD |{z}
y
124 / 168
Decomposição LDLT
A solução do sistema linear Ax = b é dada por
Ax = b ⇒ LT x = b
LD |{z}
y
⇒ L Dy = b
|{z}
w
124 / 168
Decomposição LDLT
A solução do sistema linear Ax = b é dada por
Ax = b ⇒ LT x = b
LD |{z}
y
⇒ L Dy = b
|{z}
w
e assim temos os seguintes passos para a solução do sistema:
1. Lw = b
2. Dy = w
3. LT x = y
124 / 168
Decomposição LDLT
A solução do sistema linear Ax = b é dada por
Ax = b ⇒ LT x = b
LD |{z}
y
⇒ L Dy = b
|{z}
w
e assim temos os seguintes passos para a solução do sistema:
1. Lw = b
2. Dy = w
3. LT x = y
Cálculo do determinante
det(A) = det(L)det(D)det(LT )
= 1 · det(D) · 1 = d11 d22 . . . dnn
124 / 168
Decomposição LDLT
para j = v
1 : n faça
u j−1
X
u
2
djj = tajj − ljk dkk ;
k=1
para i = j + 1 : n faça
j−1
!,
X
lij = aij − lik dkk ljk djj ;
k=1
fim-para
fim-para
125 / 168
Decomposição LDLT
det = 1 ;
para j = 1 : n faça
soma = 0 ;
para k = 1 : j − 1 faça
soma = soma + A(j,k)*A(j,k)*A(k,k) ;
fim-para
A(j,j) = A(j,j) - soma ;
r = 1 / A(j,j) ;
det = det * A(j,j) ;
para i = j + 1 : n faça
soma = 0 ;
para k = 1 : j − 1 faça
soma = soma + A(i,k)*A(k,k)*A(j,k) ;
fim-para
A(i,j) = (A(i,j) - soma) * r ;
fim-para
fim-para
126 / 168
Cálculo da Matriz Inversa
Iremos descrever como calcular a matriz inversa através da decomposição LU.
Sejam A uma matriz de dimensão n, não singular (det(A ̸= 0) e A−1 a matriz
inversa de A. Vamos escrever a matriz inversa como:
A−1 = v1 v2 . . . vn
127 / 168
Cálculo da Matriz Inversa
Iremos descrever como calcular a matriz inversa através da decomposição LU.
Sejam A uma matriz de dimensão n, não singular (det(A ̸= 0) e A−1 a matriz
inversa de A. Vamos escrever a matriz inversa como:
A−1 = v1 v2 . . . vn
Seja ainda
ej a coluna j da matriz
identidade. Por exemplo,
e2 = 0 1 0 . . . 0 , en = 0 0 0 . . . 1 . Resolvendo o seguinte
sistema linear
Av1 = e1
encontramos a primeira coluna v1 da matriz inversa de A.
127 / 168
Cálculo da Matriz Inversa
Iremos descrever como calcular a matriz inversa através da decomposição LU.
Sejam A uma matriz de dimensão n, não singular (det(A ̸= 0) e A−1 a matriz
inversa de A. Vamos escrever a matriz inversa como:
A−1 = v1 v2 . . . vn
Seja ainda
ej a coluna j da matriz
identidade. Por exemplo,
e2 = 0 1 0 . . . 0 , en = 0 0 0 . . . 1 . Resolvendo o seguinte
sistema linear
Av1 = e1
encontramos a primeira coluna v1 da matriz inversa de A. Repetindo o
procedimento para cada coluna temos
Avj = ej , j=1:n (7)
127 / 168
Cálculo da Matriz Inversa
Agora basta usar algum dos métodos que vimos para resolver os sistemas
lineares da equação (7).
1. Decomposição LU
LUvj = ej , j=1:n
Basta fatorar a matriz na forma LU uma única vez, e com os fatores
resolver os seguintes sistemas
Lyj = ej
Uvj = yj
2. Se a matriz for SPD, podemos usar decomposição de Cholesky
GGT vj = ej ⇒ (1) Gyj = ej , (2) GT vj = yj
128 / 168
Cálculo da Matriz Inversa
3. Eliminação de Gauss.
Montar
A I
e efetuar a eliminação de Gauss de uma vez só. Assim obtemos
U T
onde T é uma matriz triangular inferior. Em seguida dado que temos U
triangular superior, basta resolver a seguinte sequência de sistemas
Uvj = tj
onde tj é a coluna j da matriz T.
129 / 168
Cálculo da Matriz Inversa
Exemplo
Calcular a inversa da seguinte matriz
4 1 −6
A = 3 2 −6
3 1 −5
Assim temos
4 1 −6 1 0 0
3 2 −6 0 1 0
3 1 −5 0 0 1
Efetuando a eliminação de Gauss obtemos
4 1 −6 1 0 0
0 5/4 −3/2 −3/4 1 0
0 0 −1/5 −3/5 −1/5 1 130 / 168
Cálculo da Matriz Inversa
Exemplo
Agora basta resolver
4 1 −6 1
0 5/4 −3/2 v1 = −3/4
0 0 −1/5 −3/5
4 1 −6 0
0 5/4 −3/2 v2 = 1
0 0 −1/5 −1/5
4 1 −6 0
0 5/4 −3/2 v3 = 0
0 0 −1/5 1
131 / 168
Conteúdo
▶ Aula passada
▶ Decomposição de Cholesky
▶ Decomposição LDLT
▶ Cálculo da Matriz Inversa
▶ Aula de hoje
▶ Métodos Iterativos
▶ Método de Jacobi
▶ Método de Gauss-Seidel
▶ Método SOR
132 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
133 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
▶ Como construir a sequência {x(0) , x(1) , x(2) , . . .}?
133 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
▶ Como construir a sequência {x(0) , x(1) , x(2) , . . .}?
▶ x(k) → x∗ ?
133 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
▶ Como construir a sequência {x(0) , x(1) , x(2) , . . .}?
▶ x(k) → x∗ ?
▶ Quais são as condições para convergência?
133 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
▶ Como construir a sequência {x(0) , x(1) , x(2) , . . .}?
▶ x(k) → x∗ ?
▶ Quais são as condições para convergência?
▶ Como saber se x(k) está próximo de x∗ ?
133 / 168
Métodos Iterativos
O sistema de equações lineares Ax = b pode ser resolvido por um processo
que gera a partir de um vetor inicial x(0) uma sequência de vetores x(1) , x(2) ,
x(3) , . . . que deve convergir para a solução.
Existem muitos métodos iterativos para a solução de sistemas lineares,
entretanto só iremos estudar os chamados métodos iterativos estacionários.
Algumas perguntas importantes são:
▶ Como construir a sequência {x(0) , x(1) , x(2) , . . .}?
▶ x(k) → x∗ ?
▶ Quais são as condições para convergência?
▶ Como saber se x(k) está próximo de x∗ ?
▶ Critério de parada?
133 / 168
Métodos Iterativos
Um método iterativo escrito na forma
x(k+1) = Bx(k) + c (8)
é dito estacionário quando a matriz B for fixa durante o processo iterativo.
134 / 168
Métodos Iterativos
Um método iterativo escrito na forma
x(k+1) = Bx(k) + c (8)
é dito estacionário quando a matriz B for fixa durante o processo iterativo.
Veremos como construir a matriz B para cada um dos métodos que iremos
estudar: Jacobi, Gauss-Seidel e Sobre-relaxação (SOR).
134 / 168
Métodos Iterativos
Um método iterativo escrito na forma
x(k+1) = Bx(k) + c (8)
é dito estacionário quando a matriz B for fixa durante o processo iterativo.
Veremos como construir a matriz B para cada um dos métodos que iremos
estudar: Jacobi, Gauss-Seidel e Sobre-relaxação (SOR).
Antes, é preciso rever alguns conceitos como norma de vetores e matrizes, os
quais serão importantes no desenvolvimento do critério de parada e na análise
de convergência dos métodos.
134 / 168
Normas de Vetores e Matrizes
Para discutir o erro envolvido nas aproximações é preciso associar a cada
vetor e matriz um valor escalar não negativo que de alguma forma mede sua
magnitude. As normas para vetores mais comuns são:
▶ Norma euclideana (ou norma L2 )
||x||2 = (x12 + x22 + . . . + xn2 )1/2
▶ Norma infinito (ou norma do máximo)
||x||∞ = max |xi |
1≤i≤n
135 / 168
Normas de Vetores e Matrizes
Para discutir o erro envolvido nas aproximações é preciso associar a cada
vetor e matriz um valor escalar não negativo que de alguma forma mede sua
magnitude. As normas para vetores mais comuns são:
▶ Norma euclideana (ou norma L2 )
||x||2 = (x12 + x22 + . . . + xn2 )1/2
▶ Norma infinito (ou norma do máximo)
||x||∞ = max |xi |
1≤i≤n
Normas vetoriais devem satisfazer às seguintes propriedades:
1. ||x|| > 0 se x ̸= 0, ||x|| = 0 se x = 0
135 / 168
Normas de Vetores e Matrizes
Para discutir o erro envolvido nas aproximações é preciso associar a cada
vetor e matriz um valor escalar não negativo que de alguma forma mede sua
magnitude. As normas para vetores mais comuns são:
▶ Norma euclideana (ou norma L2 )
||x||2 = (x12 + x22 + . . . + xn2 )1/2
▶ Norma infinito (ou norma do máximo)
||x||∞ = max |xi |
1≤i≤n
Normas vetoriais devem satisfazer às seguintes propriedades:
1. ||x|| > 0 se x ̸= 0, ||x|| = 0 se x = 0
2. ||αx|| = α||x||, onde α é um escalar
135 / 168
Normas de Vetores e Matrizes
Para discutir o erro envolvido nas aproximações é preciso associar a cada
vetor e matriz um valor escalar não negativo que de alguma forma mede sua
magnitude. As normas para vetores mais comuns são:
▶ Norma euclideana (ou norma L2 )
||x||2 = (x12 + x22 + . . . + xn2 )1/2
▶ Norma infinito (ou norma do máximo)
||x||∞ = max |xi |
1≤i≤n
Normas vetoriais devem satisfazer às seguintes propriedades:
1. ||x|| > 0 se x ̸= 0, ||x|| = 0 se x = 0
2. ||αx|| = α||x||, onde α é um escalar
3. ||x + y|| ≤ ||x|| + ||y||
135 / 168
Normas de Vetores e Matrizes
Normas de matrizes tem que satisfazer a propridades similares:
1. ||A|| > 0 se A ̸= 0, ||A|| = 0 se A = 0
2. ||αA|| = α||A||, onde α é um escalar
3. ||A + B|| ≤ ||A|| + ||B||
4. ||AB|| ≤ ||A|| ||B||
5. ||Ax|| ≤ ||A|| ||x||
136 / 168
Normas de Vetores e Matrizes
Normas de matrizes tem que satisfazer a propridades similares:
1. ||A|| > 0 se A ̸= 0, ||A|| = 0 se A = 0
2. ||αA|| = α||A||, onde α é um escalar
3. ||A + B|| ≤ ||A|| + ||B||
4. ||AB|| ≤ ||A|| ||B||
5. ||Ax|| ≤ ||A|| ||x||
Iremos fazer uso em diversos momentos da seguinte norma matricial
n
X
||A||∞ = max |aij |
1≤i≤n
j=1
136 / 168
Normas de Vetores e Matrizes
Normas de matrizes tem que satisfazer a propridades similares:
1. ||A|| > 0 se A ̸= 0, ||A|| = 0 se A = 0
2. ||αA|| = α||A||, onde α é um escalar
3. ||A + B|| ≤ ||A|| + ||B||
4. ||AB|| ≤ ||A|| ||B||
5. ||Ax|| ≤ ||A|| ||x||
Iremos fazer uso em diversos momentos da seguinte norma matricial
n
X
||A||∞ = max |aij |
1≤i≤n
j=1
Exemplo
4 6
A= ⇒ ||A||∞ = max{10, 7} = 10
−3 4
136 / 168
Critério de Parada
A distância entre dois vetores x e y pode ser calculada como
||x − y||2 ou ||x − y||∞
137 / 168
Critério de Parada
A distância entre dois vetores x e y pode ser calculada como
||x − y||2 ou ||x − y||∞
Iremos usar a norma infinito nos algoritmos que iremos descrever. Seja x(k+1)
e x(k) duas aproximações para o vetor solução x∗ de um sistema de equações
lineares.
Critério de parada
(k+1) (k)
||x(k+1) − x(k) ||∞ max |xi − xi |
(k+1)
= (k+1)
<ε
||x ||∞ max |xi |
onde ε é a precisão desejada (Ex: 10−3 ).
137 / 168
Critério de Parada
A distância entre dois vetores x e y pode ser calculada como
||x − y||2 ou ||x − y||∞
Iremos usar a norma infinito nos algoritmos que iremos descrever. Seja x(k+1)
e x(k) duas aproximações para o vetor solução x∗ de um sistema de equações
lineares.
Critério de parada
(k+1) (k)
||x(k+1) − x(k) ||∞ max |xi − xi |
(k+1)
= (k+1)
<ε
||x ||∞ max |xi |
onde ε é a precisão desejada (Ex: 10−3 ).
Na prática também adotamos um número máximo de iterações para evitar que
o programa execute indefinidamente, caso o método não convirja para um
determinado problema.
k < kmax
137 / 168
Método de Jacobi
Vamos ilustrar a idéia do método de Jacobi através de um exemplo. Seja o
seguinte sistema:
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
138 / 168
Método de Jacobi
Vamos ilustrar a idéia do método de Jacobi através de um exemplo. Seja o
seguinte sistema:
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
o qual pode ser escrito como
x1 = (b1 − a12 x2 − a13 x3 )/a11
x2 = (b2 − a21 x1 − a23 x3 )/a22
x3 = (b3 − a31 x1 − a32 x2 )/a33
138 / 168
Método de Jacobi
Vamos ilustrar a idéia do método de Jacobi através de um exemplo. Seja o
seguinte sistema:
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
o qual pode ser escrito como
x1 = (b1 − a12 x2 − a13 x3 )/a11
x2 = (b2 − a21 x1 − a23 x3 )/a22
x3 = (b3 − a31 x1 − a32 x2 )/a33
A partir de uma aproximação inicial
(0)
x
1
x(0) = x2(0)
(0)
x3
138 / 168
Método de Jacobi
Calculamos uma nova aproximação x(1) através de
(1) (0) (0)
x1 = b1 − a12 x2 − a13 x3 /a11
(1) (0) (0)
x2 = b2 − a21 x1 − a23 x3 /a22
(1) (0) (0)
x3 = b3 − a31 x1 − a32 x2 /a33
Após obter x(1) , calculamos x(2) substituindo x(1) no lugar de x(0) na
expressão anterior e assim procedemos até que o critério de parada seja
satisfeito.
139 / 168
Método de Jacobi
Calculamos uma nova aproximação x(1) através de
(1) (0) (0)
x1 = b1 − a12 x2 − a13 x3 /a11
(1) (0) (0)
x2 = b2 − a21 x1 − a23 x3 /a22
(1) (0) (0)
x3 = b3 − a31 x1 − a32 x2 /a33
Após obter x(1) , calculamos x(2) substituindo x(1) no lugar de x(0) na
expressão anterior e assim procedemos até que o critério de parada seja
satisfeito.
Para um sistema de n equações e n incógnitas, a cada passo k, temos:
para i = 1 : nfaça ,
i−1 n
(k+1) (k) (k)
X X
xi = bi − aij xj − aij xj aii ;
j=1 j=i+1
fim-para
139 / 168
Método de Jacobi
entrada: A, b, x(0) , max, ε
saída: x
para k = 1 : max faça
para i = 1 : nfaça ,
i−1 n
(k+1) (k) (k)
X X
xi = bi − aij xj − aij xj aii ;
j=1 j=i+1
fim-para
(k+1) (k)
se max |xi − xi | < ε então
retorna x(k+1) ;
fim-se
fim-para
140 / 168
Método de Jacobi
Exemplo
Resolver o seguinte sistema:
4x1 + 0.24x2 − 0.08x3 = 8
0.09x1 + 3x2 − 0.15x3 = 9
0.04x1 − 0.08x2 + 4x3 = 20
usando o método de Jacobi com vetor inicial x(0) = 0.
141 / 168
Método de Jacobi
Exemplo
Resolver o seguinte sistema:
4x1 + 0.24x2 − 0.08x3 = 8
0.09x1 + 3x2 − 0.15x3 = 9
0.04x1 − 0.08x2 + 4x3 = 20
usando o método de Jacobi com vetor inicial x(0) = 0.
Solução do Exemplo
k 0 1 2 3
x1 0 2 1.92 1.91
x2 0 3 3.19 3.1944
x3 0 5 5.04 5.0446
141 / 168
Método de Jacobi
Solução do Exemplo
Fórmula de iteração
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k) (k)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
142 / 168
Método de Jacobi
Solução do Exemplo
Fórmula de iteração
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k) (k)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1) (0) (0)
x1 = 2 − 0.06x2 + 0.02x3 = 2
142 / 168
Método de Jacobi
Solução do Exemplo
Fórmula de iteração
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k) (k)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1) (0) (0)
x1 = 2 − 0.06x2 + 0.02x3 = 2
(1) (0) (0)
x2 = 3 − 0.03x1 + 0.05x3 = 3
142 / 168
Método de Jacobi
Solução do Exemplo
Fórmula de iteração
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k) (k)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1) (0) (0)
x1 = 2 − 0.06x2 + 0.02x3 = 2
(1) (0) (0)
x2 = 3 − 0.03x1 + 0.05x3 = 3
(1) (0) (0)
x3 = 5 − 0.01x1 + 0.02x2 = 5
142 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
(2)
x3 = 5 − 0.01(2) + 0.02(3) = 5 + 0.04 = 5.04
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
(2)
x3 = 5 − 0.01(2) + 0.02(3) = 5 + 0.04 = 5.04
Passo 3 → (x(2) )T = 1.92 3.19 5.04
(3)
x1 = 2 − 0.06(3.19) + 0.02(5.04) = 1.91
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
(2)
x3 = 5 − 0.01(2) + 0.02(3) = 5 + 0.04 = 5.04
Passo 3 → (x(2) )T = 1.92 3.19 5.04
(3)
x1 = 2 − 0.06(3.19) + 0.02(5.04) = 1.91
(3)
x2 = 3 − 0.03(1.92) + 0.05(5.04) = 3.1944
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
(2)
x3 = 5 − 0.01(2) + 0.02(3) = 5 + 0.04 = 5.04
Passo 3 → (x(2) )T = 1.92 3.19 5.04
(3)
x1 = 2 − 0.06(3.19) + 0.02(5.04) = 1.91
(3)
x2 = 3 − 0.03(1.92) + 0.05(5.04) = 3.1944
(3)
x3 = 5 − 0.01(1.92) + 0.02(3.19) = 5.0446
143 / 168
Método de Jacobi
Solução do Exemplo
Passo 2 → (x(1) )T = 2 3 5
(2)
x1 = 2 − 0.06(3) + 0.02(5) = 2 − 0.08 = 1.92
(2)
x2 = 3 − 0.03(2) + 0.05(5) = 3 + 0.19 = 3.19
(2)
x3 = 5 − 0.01(2) + 0.02(3) = 5 + 0.04 = 5.04
Passo 3 → (x(2) )T = 1.92 3.19 5.04
(3)
x1 = 2 − 0.06(3.19) + 0.02(5.04) = 1.91
(3)
x2 = 3 − 0.03(1.92) + 0.05(5.04) = 3.1944
(3)
x3 = 5 − 0.01(1.92) + 0.02(3.19) = 5.0446
Erro: ||x(3) − x(2) ||∞ = max{0.01, 0.0044, 0.0046} = 0.01
143 / 168
Método de Gauss-Seidel
Observe no exemplo anterior, que o método de Jacobi, não usa os valores
atualizados de x(k) até completar por inteiro a iteração do passo k.
144 / 168
Método de Gauss-Seidel
Observe no exemplo anterior, que o método de Jacobi, não usa os valores
atualizados de x(k) até completar por inteiro a iteração do passo k.
O método de Gauss-Seidel pode ser visto como uma modificação do método
de Jacobi. Nele usaremos a mesma forma de iterar que o método de Jacobi,
entretanto vamos aproveitar os cálculos já atualizados, de outras
componentes, para atualizar a componente que está sendo calculada.
(k+1) (k+1)
Dessa forma o valor de x1 será usado para calcular x2 , os valores de
(k+1) (k+1) (k+1)
x1 e x2 serão usados para calcular x3 , e assim por diante.
144 / 168
Método de Gauss-Seidel
Para um sistema 3 × 3 temos o seguinte esquema:
(k+1) (k) (k)
x1 = b1 − a12 x2 − a13 x3 /a11
145 / 168
Método de Gauss-Seidel
Para um sistema 3 × 3 temos o seguinte esquema:
(k+1) (k) (k)
x1 = b1 − a12 x2 − a13 x3 /a11
(k+1) (k+1) (k)
x2 = b2 − a21 x1 − a23 x3 /a22
145 / 168
Método de Gauss-Seidel
Para um sistema 3 × 3 temos o seguinte esquema:
(k+1) (k) (k)
x1 = b1 − a12 x2 − a13 x3 /a11
(k+1) (k+1) (k)
x2 = b2 − a21 x1 − a23 x3 /a22
(k+1) (k+1) (k+1)
x3 = b3 − a31 x1 − a32 x2 /a33
145 / 168
Método de Gauss-Seidel
Para um sistema 3 × 3 temos o seguinte esquema:
(k+1) (k) (k)
x1 = b1 − a12 x2 − a13 x3 /a11
(k+1) (k+1) (k)
x2 = b2 − a21 x1 − a23 x3 /a22
(k+1) (k+1) (k+1)
x3 = b3 − a31 x1 − a32 x2 /a33
No caso geral temos
para i = 1 : nfaça ,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii ;
j=1 j=i+1
fim-para
145 / 168
Método de Gauss-Seidel
Para um sistema 3 × 3 temos o seguinte esquema:
(k+1) (k) (k)
x1 = b1 − a12 x2 − a13 x3 /a11
(k+1) (k+1) (k)
x2 = b2 − a21 x1 − a23 x3 /a22
(k+1) (k+1) (k+1)
x3 = b3 − a31 x1 − a32 x2 /a33
No caso geral temos
para i = 1 : nfaça ,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii ;
j=1 j=i+1
fim-para
Obs: Note que no método de GS apenas 1 aproximação para xi precisa ser
armazenada. No método de Jacobi é preciso manter 2 vetores em memória,
um para x(k+1) e outro para x(k) .
145 / 168
Método de Gauss-Seidel
Exemplo
Resolva o sistema de equações do exemplo anterior usando o método de
Gauss-Seidel.
146 / 168
Método de Gauss-Seidel
Exemplo
Resolva o sistema de equações do exemplo anterior usando o método de
Gauss-Seidel.
Solução do Exemplo
Fórmula de iteração (*)
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k+1) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k+1) (k+1)
x3 = 5 − 0.01x1 + 0.02x2
146 / 168
Método de Gauss-Seidel
Exemplo
Resolva o sistema de equações do exemplo anterior usando o método de
Gauss-Seidel.
Solução do Exemplo
Fórmula de iteração (*)
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k+1) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k+1) (k+1)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1)
x1 = 2 − 0.06(0) + 0.02(0) = 2
146 / 168
Método de Gauss-Seidel
Exemplo
Resolva o sistema de equações do exemplo anterior usando o método de
Gauss-Seidel.
Solução do Exemplo
Fórmula de iteração (*)
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k+1) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k+1) (k+1)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1)
x1 = 2 − 0.06(0) + 0.02(0) = 2
(1)
x2 = 3 − 0.03(2) + 0.05(0) = 3 − 0.06 = 2.94
146 / 168
Método de Gauss-Seidel
Exemplo
Resolva o sistema de equações do exemplo anterior usando o método de
Gauss-Seidel.
Solução do Exemplo
Fórmula de iteração (*)
(k+1) (k) (k)
x1 = 2 − 0.06x2 + 0.02x3
(k+1) (k+1) (k)
x2 = 3 − 0.03x1 + 0.05x3
(k+1) (k+1) (k+1)
x3 = 5 − 0.01x1 + 0.02x2
Passo 1 → x(0) = 0
(1)
x1 = 2 − 0.06(0) + 0.02(0) = 2
(1)
x2 = 3 − 0.03(2) + 0.05(0) = 3 − 0.06 = 2.94
(1) 146 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
147 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
(2)
x2 = 3 − 0.03(1.924376) + 0.05(5.0388) = 3.194209
147 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
(2)
x2 = 3 − 0.03(1.924376) + 0.05(5.0388) = 3.194209
(2)
x3 = 5 − 0.01(1.924376) + 0.02(3.194209) = 5.044640
147 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
(2)
x2 = 3 − 0.03(1.924376) + 0.05(5.0388) = 3.194209
(2)
x3 = 5 − 0.01(1.924376) + 0.02(3.194209) = 5.044640
Passo 3 → (x(2) )T = 1.924376 3.194209 5.044640
(2)
x1 = 2 − 0.06(1.924376) + 0.02(5.04464) = 1.909240
147 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
(2)
x2 = 3 − 0.03(1.924376) + 0.05(5.0388) = 3.194209
(2)
x3 = 5 − 0.01(1.924376) + 0.02(3.194209) = 5.044640
Passo 3 → (x(2) )T = 1.924376 3.194209 5.044640
(2)
x1 = 2 − 0.06(1.924376) + 0.02(5.04464) = 1.909240
(2)
x2 = 3 − 0.03(1.909240) + 0.05(5.04464) = 3.194955
147 / 168
Método de Gauss-Seidel
Solução do Exemplo
Passo 2 → (x(1) )T = 2 2.94 5.0388
(2)
x1 = 2 − 0.06(2.94) + 0.02(5.0388) = 1.924376
(2)
x2 = 3 − 0.03(1.924376) + 0.05(5.0388) = 3.194209
(2)
x3 = 5 − 0.01(1.924376) + 0.02(3.194209) = 5.044640
Passo 3 → (x(2) )T = 1.924376 3.194209 5.044640
(2)
x1 = 2 − 0.06(1.924376) + 0.02(5.04464) = 1.909240
(2)
x2 = 3 − 0.03(1.909240) + 0.05(5.04464) = 3.194955
(2)
x3 = 5 − 0.01(1.909240) + 0.02(3.194955) = 5.044807
147 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para estudar a convergência dos métodos, vamos primeiros escrevê-los na
seguinte forma:
x(k+1) = Bx(k) + c
Para isso, vamos dividir a matriz A como
A= L
|{z} + |{z}
D + U
|{z}
triangular inferior diagonal triangular superior
148 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para estudar a convergência dos métodos, vamos primeiros escrevê-los na
seguinte forma:
x(k+1) = Bx(k) + c
Para isso, vamos dividir a matriz A como
A= L
|{z} + |{z}
D + U
|{z}
triangular inferior diagonal triangular superior
isto é, para uma matriz 3 × 3 temos
a11 a12 a13 0 0 0 a11 0 0 0 a12 a13
a21 a22 a23 = a21 0 0 + 0 a22 0 + 0 0 a23
a31 a32 a33 a31 a32 0 0 0 a33 0 0 0
148 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
⇒ Dx = b − (L + U)x
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
⇒ Dx = b − (L + U)x
e assim
Dx(k+1) = b − (L + U)x(k)
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
⇒ Dx = b − (L + U)x
e assim
Dx(k+1) = b − (L + U)x(k)
x(k+1) = −D−1 (L + U)x(k) + D−1 b
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
⇒ Dx = b − (L + U)x
e assim
Dx(k+1) = b − (L + U)x(k)
x(k+1) = −D−1 (L + U)x(k) + D−1 b
x(k+1) = BJ x(k) + c
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Sendo assim o método de Jacobi pode ser escrito como:
Ax = b ⇒ (L + D + U)x = b
⇒ Dx = b − (L + U)x
e assim
Dx(k+1) = b − (L + U)x(k)
x(k+1) = −D−1 (L + U)x(k) + D−1 b
x(k+1) = BJ x(k) + c
onde para o método de Jacobi
BJ = −D−1 (L + U)
c = D−1 b
149 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Gauss-Seidel temos
(L + D)x(k+1) = −Ux(k) + b
150 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Gauss-Seidel temos
(L + D)x(k+1) = −Ux(k) + b
x(k+1) = −(L + D)−1 Ux(k) + (L + D)−1 b
150 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Gauss-Seidel temos
(L + D)x(k+1) = −Ux(k) + b
x(k+1) = −(L + D)−1 Ux(k) + (L + D)−1 b
x(k+1) = BGS x(k) + c
150 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Gauss-Seidel temos
(L + D)x(k+1) = −Ux(k) + b
x(k+1) = −(L + D)−1 Ux(k) + (L + D)−1 b
x(k+1) = BGS x(k) + c
onde para o método de Gauss-Seidel
BGS = −(L + D)−1 U
c = (L + D)−1 b
150 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Gauss-Seidel temos
(L + D)x(k+1) = −Ux(k) + b
x(k+1) = −(L + D)−1 Ux(k) + (L + D)−1 b
x(k+1) = BGS x(k) + c
onde para o método de Gauss-Seidel
BGS = −(L + D)−1 U
c = (L + D)−1 b
Ou seja, ambos os métodos podem ser escritos como
x(k+1) = Bx(k) + c (9)
onde B é chamada de matriz de iteração
BJ = −D−1 (L + U)
BGS = −(L + D)−1 U
150 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Se o método de Jacobi ou Gauss-Seidel converge ou não, depende dos
autovalores da matriz de iteração B.
151 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Se o método de Jacobi ou Gauss-Seidel converge ou não, depende dos
autovalores da matriz de iteração B.
Dizemos que λi , i = 1 : n é um autovalor da matriz B se
Bu = λi u
para algum vetor u ̸= 0. O seguinte teorema caracteriza a condição para
convergência desses métodos.
Teorema
A condição necessária e suficiente para que o método iterativo descrito por
x(k+1) = Bx(k) + c convirja usando um vetor inicial x(0) qualquer é
ρ(B) = max |λi (B)| < 1
1≤i≤n
151 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Na prática encontrar os autovalores de B é tão custoso quanto resolver um
sistema de equações lineares e portanto o Teorema 1 é difícil de usar. Vamos
estudar outra forma de analisar a convergência para esses métodos.
152 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Na prática encontrar os autovalores de B é tão custoso quanto resolver um
sistema de equações lineares e portanto o Teorema 1 é difícil de usar. Vamos
estudar outra forma de analisar a convergência para esses métodos.
Seja x∗ a solução exata. Então x∗ = Bx∗ + c. Subtraindo de (9) temos
x(k+1) − x∗ = Bx(k) − Bx∗ + c − c
= B(x(k) − x∗ )
152 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Na prática encontrar os autovalores de B é tão custoso quanto resolver um
sistema de equações lineares e portanto o Teorema 1 é difícil de usar. Vamos
estudar outra forma de analisar a convergência para esses métodos.
Seja x∗ a solução exata. Então x∗ = Bx∗ + c. Subtraindo de (9) temos
x(k+1) − x∗ = Bx(k) − Bx∗ + c − c
= B(x(k) − x∗ )
de forma análoga
x(k) − x∗ = B(x(k−1) − x∗ )
152 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Na prática encontrar os autovalores de B é tão custoso quanto resolver um
sistema de equações lineares e portanto o Teorema 1 é difícil de usar. Vamos
estudar outra forma de analisar a convergência para esses métodos.
Seja x∗ a solução exata. Então x∗ = Bx∗ + c. Subtraindo de (9) temos
x(k+1) − x∗ = Bx(k) − Bx∗ + c − c
= B(x(k) − x∗ )
de forma análoga
x(k) − x∗ = B(x(k−1) − x∗ )
e assim
x(k+1) − x∗ = B2 (x(k−1) − x∗ ) = . . . = Bk+1 (x(0) − x∗ )
152 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
x(k+1) − x∗ = Bk+1 (x(0) − x∗ ) (10)
Aplicando a norma infinito em (10), obtemos
||x(k+1) − x∗ ||∞ = ||Bk+1 (x(0) − x∗ )||∞
(11)
153 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
x(k+1) − x∗ = Bk+1 (x(0) − x∗ ) (10)
Aplicando a norma infinito em (10), obtemos
||x(k+1) − x∗ ||∞ = ||Bk+1 (x(0) − x∗ )||∞
≤ ||Bk+1 ||∞ ||(x(0) − x∗ )||∞
(11)
153 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
x(k+1) − x∗ = Bk+1 (x(0) − x∗ ) (10)
Aplicando a norma infinito em (10), obtemos
||x(k+1) − x∗ ||∞ = ||Bk+1 (x(0) − x∗ )||∞
≤ ||Bk+1 ||∞ ||(x(0) − x∗ )||∞
≤ ||B||k+1
∞ ||(x
(0)
− x∗ )||∞ (11)
153 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
x(k+1) − x∗ = Bk+1 (x(0) − x∗ ) (10)
Aplicando a norma infinito em (10), obtemos
||x(k+1) − x∗ ||∞ = ||Bk+1 (x(0) − x∗ )||∞
≤ ||Bk+1 ||∞ ||(x(0) − x∗ )||∞
≤ ||B||k+1
∞ ||(x
(0)
− x∗ )||∞ (11)
Assim de (11) fica claro que só haverá convergência se
||B||∞ < 1 (12)
153 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
x(k+1) − x∗ = Bk+1 (x(0) − x∗ ) (10)
Aplicando a norma infinito em (10), obtemos
||x(k+1) − x∗ ||∞ = ||Bk+1 (x(0) − x∗ )||∞
≤ ||Bk+1 ||∞ ||(x(0) − x∗ )||∞
≤ ||B||k+1
∞ ||(x
(0)
− x∗ )||∞ (11)
Assim de (11) fica claro que só haverá convergência se
||B||∞ < 1 (12)
Vamos analisar agora critérios específicos para atender ao critério geral dado
por (12) para o método de Jacobi e Gauss-Seidel.
153 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Jacobi, a matriz de iteração BJ = −D−1 (L + U) é da forma
1
a11 a11
1
a22
−1
a22
D= ⇒ D =
.. . .
. .
ann 1
ann
154 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Jacobi, a matriz de iteração BJ = −D−1 (L + U) é da forma
1
a11 a11
1
a22
−1
a22
D= ⇒ D =
.. . .
. .
ann 1
ann
portanto
a12 a12 a1n
0 a11 a11 ... a11
a21 a23 a2n
a 0 a22 ... a22
BJ = − .22 .. ..
.. . .
an1 an2 ann−1
ann ann ... ann 0
154 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para o método de Jacobi, a matriz de iteração BJ = −D−1 (L + U) é da forma
1
a11 a11
1
a22
−1
a22
D= ⇒ D =
.. . .
. .
ann 1
ann
portanto
a12 a12 a1n
0 a11 a11 ... a11
a21 a23 a2n
a 0 a22 ... a22
BJ = − .22 .. ..
.. . .
an1 an2 ann−1
ann ann ... ann 0
ou seja, seus elementos são
a
bij = − aijii
154 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
n
X
||BJ ||∞ = max |bij |
1≤i≤n
j=1
155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
n n
X X aij
||BJ ||∞ = max |bij | = max
1≤i≤n 1≤i≤n aii
j=1 j=1,i̸=j
155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
n n
X X aij
||BJ ||∞ = max |bij | = max <1
1≤i≤n 1≤i≤n aii
j=1 j=1,i̸=j
155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
n n
X X aij
||BJ ||∞ = max |bij | = max <1
1≤i≤n 1≤i≤n aii
j=1 j=1,i̸=j
Teorema (Critério das Linhas)
n
X aij
Seja Ax = b e seja αk = , para k = 1 : n. Se α = max{αk } < 1,
aii
j=1,i̸=j
então o método de Jacobi converge independentemente da aproximação
inicial x(0) .
155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para termos convergência, então precisamos que ||BJ ||∞ < 1
n n
X X aij
||BJ ||∞ = max |bij | = max <1
1≤i≤n 1≤i≤n aii
j=1 j=1,i̸=j
Teorema (Critério das Linhas)
n
X aij
Seja Ax = b e seja αk = , para k = 1 : n. Se α = max{αk } < 1,
aii
j=1,i̸=j
então o método de Jacobi converge independentemente da aproximação
inicial x(0) .
Exemplo
Verificar se as seguintes matrizes satisfazem o critério das linhas.
4 0.24 −0.08 1 3 1
0.09 3 −0.15 , 5 2 2
0.04 −0.08 4 0 6 8 155 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Definição
Uma matriz A é estritamente diagonal dominante se
n
X
|aij | < |aii |, i=1:n
j=1, j̸=i
156 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Definição
Uma matriz A é estritamente diagonal dominante se
n
X
|aij | < |aii |, i=1:n
j=1, j̸=i
Fica claro então que para matrizes estritamente diagonal dominante o critério
das linhas é sempre satisfeito. Portanto, uma outra forma de verificar se o
método de Jacobi converge para uma certa matriz é verificar se esta é
estritamente diagonal dominante.
156 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Definição
Uma matriz A é estritamente diagonal dominante se
n
X
|aij | < |aii |, i=1:n
j=1, j̸=i
Fica claro então que para matrizes estritamente diagonal dominante o critério
das linhas é sempre satisfeito. Portanto, uma outra forma de verificar se o
método de Jacobi converge para uma certa matriz é verificar se esta é
estritamente diagonal dominante.
Exemplo
10 2 1
1 5 1
2 3 10
156 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Definição
Uma matriz A é estritamente diagonal dominante se
n
X
|aij | < |aii |, i=1:n
j=1, j̸=i
Fica claro então que para matrizes estritamente diagonal dominante o critério
das linhas é sempre satisfeito. Portanto, uma outra forma de verificar se o
método de Jacobi converge para uma certa matriz é verificar se esta é
estritamente diagonal dominante.
Exemplo
|a12 | + |a13 | = |2| + |1| < |10| = |a11 |
10 2 1 |a21 | + |a23 | = |1| + |1| < |5| = |a22 |
1 5 1
|a31 | + |a32 | = |2| + |3| < |10| = |a33 |
2 3 10
156 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Para ter convergência é preciso satisfazer pelo menos um dos critérios:
▶ critério das linhas, isto é
n
|aij |
X
max |aii | <1
1≤i≤n
j=1, j̸=i
▶ critério de Sassenfeld
max βi < 1 (13)
1≤i≤n
onde βi são calculados como
,
i−1
X n
X
βi = |aij |βj + |aij | |aii |
j=1 j=i+1
157 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
É possível mostrar que para BGS dado por
BGS = −(L + D)−1 U
temos que
||BGS ||∞ ≤ max βi
1≤i≤n
Sendo assim, para mostrar que o método converge, basta mostrar que o
critério de Sassenfeld (13) é satisfeito.
158 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
É possível mostrar que para BGS dado por
BGS = −(L + D)−1 U
temos que
||BGS ||∞ ≤ max βi
1≤i≤n
Sendo assim, para mostrar que o método converge, basta mostrar que o
critério de Sassenfeld (13) é satisfeito.
* Para ver que o critério das linhas também é válido para o método de
Gauss-Seidel, basta verificar que
n
|aij |
X
max |aii | <1 ⇒ βi < 1, i=1:n
1≤i≤n
j=1, j̸=i
158 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Pn |aij |
Prova: Considere que: max j=1, j̸=i |aii | < 1 (CL → OK)
159 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Pn |aij |
Prova: Considere que: max j=1, j̸=i |aii | < 1 (CL → OK)
n n
X |a1j | X |aij |
β1 = ≤ max <1
|a11 | 1≤i≤n |aii |
j=2 j=1, j̸=i
159 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Pn |aij |
Prova: Considere que: max j=1, j̸=i |aii | < 1 (CL → OK)
n n
X |a1j | X |aij |
β1 = ≤ max <1
|a11 | 1≤i≤n |aii |
j=2 j=1, j̸=i
Suponha agora que βj < 1 para i = 1, 2, . . . , i − 1. Então
i−1 n n
X |aij | X |aij | X |aij |
βi = βj + ≤
|aii | |aii | |aii |
j=1 j=i+1 j=1, j̸=i
n
X |aij |
≤ max <1
1≤i≤n |aii |
j=1, j̸=i
159 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Pn |aij |
Prova: Considere que: max j=1, j̸=i |aii | < 1 (CL → OK)
n n
X |a1j | X |aij |
β1 = ≤ max <1
|a11 | 1≤i≤n |aii |
j=2 j=1, j̸=i
Suponha agora que βj < 1 para i = 1, 2, . . . , i − 1. Então
i−1 n n
X |aij | X |aij | X |aij |
βi = βj + ≤
|aii | |aii | |aii |
j=1 j=i+1 j=1, j̸=i
n
X |aij |
≤ max <1
1≤i≤n |aii |
j=1, j̸=i
Fica claro que o critério de Sassenfeld pode ser menor que o das linhas.
Logo, o critério de Sassenfeld pode ser satisfeito e o critério das linhas não, e
portanto o processo iterativo converge.
159 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Algumas observações:
▶ Quanto menor o valor de ||B||∞ , mais rápida será a convergência do
método.
▶ Permutação de linhas ou colunas pode reduzir ||B||∞
▶ A convergência dos métodos de Jacobi e Gauss-Seidel não depende do
vetor inicial x(0) .
160 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Jacobi.
10 2 1 x1 7
1 5 1 x2 = −8
2 3 10 x3 6
161 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Jacobi.
10 2 1 x1 7
1 5 1 x2 = −8
2 3 10 x3 6
Solução do Exemplo
Critério das linhas:
α1 = (|a12 | + |a13 |)/|10| = 0.2 + 0.1 = 0.3 < 1
α2 = (|a21 | + |a23 |)/|5| = 0.2 + 0.2 = 0.4 < 1
α3 = (|a31 | + |a32 |)/|10| = 0.2 + 0.3 = 0.5 < 1
Logo α = α3 = 0.5 < 1 e portanto o método de Jacobi converge para essa
matriz. 161 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
Ou então basta verificar que a matriz A é estritamente diagonal dominante.
Fórmula de iteração:
(k+1) (k) (k)
x1 = 0.7 − 0.2x2 − 0.1x3
(k+1) (k) (k)
x2 = −1.6 − 0.2x1 − 0.2x3
(k+1) (k) (k)
x3 = 0.6 − 0.2x1 − 0.3x2
Assim temos as seguintes iterações para o vetor inicial x(0) = 0
k 1 2 3 4 5
x1 0.7 0.96 0.978 0.9994 0.9979
x2 -1.6 -1.86 -1.98 -1.9888 -1.9996
x3 0.6 0.94 0.966 0.966 0.9968
162 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Gauss-Seidel.
5 1 1 x1 5
3 4 1 x2 = 6
3 3 6 x3 0
163 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Gauss-Seidel.
5 1 1 x1 5
3 4 1 x2 = 6
3 3 6 x3 0
Solução do Exemplo
1) A matriz não é estritamente diagonal dominante. Nada podemos afirmar
sobre a convergência.
163 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Gauss-Seidel.
5 1 1 x1 5
3 4 1 x2 = 6
3 3 6 x3 0
Solução do Exemplo
1) A matriz não é estritamente diagonal dominante. Nada podemos afirmar
sobre a convergência.
2) Critério das linhas:
α1 = (|a12 | + |a13 |)/|5| = 0.2 + 0.2 = 0.4 < 1
α2 = (|a21 | + |a23 |)/|4| = 0.75 + 0.25 = 1
α3 = (|a31 | + |a32 |)/|6| = 0.5 + 0.5 = 1
163 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Exemplo
Resolva o sistema utilizando o método de Gauss-Seidel.
5 1 1 x1 5
3 4 1 x2 = 6
3 3 6 x3 0
Solução do Exemplo
1) A matriz não é estritamente diagonal dominante. Nada podemos afirmar
sobre a convergência.
2) Critério das linhas:
α1 = (|a12 | + |a13 |)/|5| = 0.2 + 0.2 = 0.4 < 1
α2 = (|a21 | + |a23 |)/|4| = 0.75 + 0.25 = 1
α3 = (|a31 | + |a32 |)/|6| = 0.5 + 0.5 = 1
163 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
3) Critério de Sassenfeld:
β1 = |0.2| + |0.2| = 0.4
β2 = |0.75|(0.4) + |0.25| = 0.3 + 0.25 = 0.55
β3 = |0.5|(0.4) + |0.5|(0.55) = 0.2 + 0.275 = 0.475
164 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
3) Critério de Sassenfeld:
β1 = |0.2| + |0.2| = 0.4
β2 = |0.75|(0.4) + |0.25| = 0.3 + 0.25 = 0.55
β3 = |0.5|(0.4) + |0.5|(0.55) = 0.2 + 0.275 = 0.475
Assim
max βi = max{0.4, 0.55, 0.475} = 0.55 < 1
1≤i≤n
164 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
3) Critério de Sassenfeld:
β1 = |0.2| + |0.2| = 0.4
β2 = |0.75|(0.4) + |0.25| = 0.3 + 0.25 = 0.55
β3 = |0.5|(0.4) + |0.5|(0.55) = 0.2 + 0.275 = 0.475
Assim
max βi = max{0.4, 0.55, 0.475} = 0.55 < 1
1≤i≤n
Portanto, como o critério de Sassenfeld é satisfeito, podemos garantir que o
processo de Gauss-Seidel converge para essa matriz.
164 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
Fórmula de iteração:
(k+1) (k) (k)
x1 = 1 − 0.2x2 − 0.2x3
(k+1) (k+1) (k)
x2 = 1.5 − 0.75x1 − 0.25x3
(k+1) (k+1) (k+1)
x3 = 0 − 0.5x1 − 0.5x2
165 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
Fórmula de iteração:
(k+1) (k) (k)
x1 = 1 − 0.2x2 − 0.2x3
(k+1) (k+1) (k)
x2 = 1.5 − 0.75x1 − 0.25x3
(k+1) (k+1) (k+1)
x3 = 0 − 0.5x1 − 0.5x2
Usando x(0) = 0 como aproximação inicial, temos
(1)
x1 = 1 − 0.2(0) − 0.2(0) = 1
(1)
x2 = 1.5 − 0.75(1) − 0.25(0) = 0.75
(1)
x3 = 0 − 0.5(1) − 0.5(0.75)
165 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
Iterando para k = 1, 2, . . . temos
k 1 2 3 4
x1 1.0 1.025 1.0075 1.0016
x2 0.75 0.95 0.9913 0.9987
x3 -0.875 -0.9875 -0.9994 -1.0002
166 / 168
Convergência dos métodos de Jacobi e Gauss-Seidel
Solução do Exemplo
Iterando para k = 1, 2, . . . temos
k 1 2 3 4
x1 1.0 1.025 1.0075 1.0016
x2 0.75 0.95 0.9913 0.9987
x3 -0.875 -0.9875 -0.9994 -1.0002
Podemos verificar o erro
||x(4) − x(3) ||∞ max{|1.0016−1.0075|,|0.9987−0.9913|,|−1.0002+0.9994|}
= max{|1.0016|,|0.9987|,|−1.0002|}
||x(4) ||∞
0.0074
= = 0.0074 < 10−2
1.0016
166 / 168
Método SOR
É possível acelerar a convergência dos métodos iterativos visto até então
através do método da sobre-relaxação sucessiva, ou do inglês SOR (sucessive
over relaxation).
Nesse método definimos a aproximação na iteração (k + 1) como uma média
entre o valor de x(k) obtido na iteração (k) e o valor de x(k+1) , que seria obtido
pelo método de Gauss-Seidel.
167 / 168
Método SOR
É possível acelerar a convergência dos métodos iterativos visto até então
através do método da sobre-relaxação sucessiva, ou do inglês SOR (sucessive
over relaxation).
Nesse método definimos a aproximação na iteração (k + 1) como uma média
entre o valor de x(k) obtido na iteração (k) e o valor de x(k+1) , que seria obtido
pelo método de Gauss-Seidel.
As iterações associadas ao parâmetro ω do método SOR são definidas por:
xSOR (k+1) = (1 − ω)xSOR (k) + ωxGS (k+1) (14)
onde xSOR (k) é a aproximação do passo anterior obtida pelo método SOR e
xGS (k+1) é a aproximação atual obtida pelo método de Gauss-Seidel.
167 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
▶ Quando ω = 1 temos o método de Gauss-Seidel.
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
▶ Quando ω = 1 temos o método de Gauss-Seidel.
▶ O método só converge se 0 < ω < 2.
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
▶ Quando ω = 1 temos o método de Gauss-Seidel.
▶ O método só converge se 0 < ω < 2.
▶ 1 < ω < 2: sobre-relaxação.
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
▶ Quando ω = 1 temos o método de Gauss-Seidel.
▶ O método só converge se 0 < ω < 2.
▶ 1 < ω < 2: sobre-relaxação.
▶ 0 < ω < 1: sub-relaxação.
168 / 168
Método SOR
Lembrando que para o método de Gauss-Seidel temos
,
i−1 n
(k+1) (k+1) (k)
X X
xi = bi − aij xj − aij xj aii
j=1 j=i+1
chegamos ao seguinte esquema para o método SOR:
i−1 n
(k+1) (k) (k+1) (k)
X X
xi = (1 − ω)xi + aωii bi − aij xj − aij xj
j=1 j=i+1
▶ Quando ω = 1 temos o método de Gauss-Seidel.
▶ O método só converge se 0 < ω < 2.
▶ 1 < ω < 2: sobre-relaxação.
▶ 0 < ω < 1: sub-relaxação.
▶ Em alguns casos particulares é possível encontrar um valor ótimo para ω,
de forma que o método apresenta uma boa convergência com relação a
outras escolhas de ω
168 / 168
Você também pode gostar
- Exercícios Resolvidos: Sistemas LinearesAinda não há avaliaçõesExercícios Resolvidos: Sistemas Lineares22 páginas
- Matrizes e Sistemas Lineares: Guia CompletoAinda não há avaliaçõesMatrizes e Sistemas Lineares: Guia Completo8 páginas
- Matrizes e Sistemas Lineares: FundamentosAinda não há avaliaçõesMatrizes e Sistemas Lineares: Fundamentos7 páginas
- Fundamentos de Sistemas de EquaçõesAinda não há avaliaçõesFundamentos de Sistemas de Equações33 páginas
- Sistemas de Equações Lineares: Métodos e SoluçõesAinda não há avaliaçõesSistemas de Equações Lineares: Métodos e Soluções21 páginas
- Matrizes e Sistemas Lineares: Guia CompletoAinda não há avaliaçõesMatrizes e Sistemas Lineares: Guia Completo17 páginas
- Álgebra Linear: Sistemas e MatrizesAinda não há avaliaçõesÁlgebra Linear: Sistemas e Matrizes48 páginas
- Conceitos de Matrizes e Sistemas LinearesAinda não há avaliaçõesConceitos de Matrizes e Sistemas Lineares103 páginas
- Algebra Linear para Computacao PDFAinda não há avaliaçõesAlgebra Linear para Computacao PDF288 páginas
- Resumo de Álgebra Linear: Matrizes e OperaçõesAinda não há avaliaçõesResumo de Álgebra Linear: Matrizes e Operações29 páginas
- Propriedades de Matrizes e EquivalênciaAinda não há avaliaçõesPropriedades de Matrizes e Equivalência17 páginas
- Notas de Álgebra Linear: Sistemas e MatrizesAinda não há avaliaçõesNotas de Álgebra Linear: Sistemas e Matrizes159 páginas
- Resumo de Álgebra Linear: Matrizes e ExemplosAinda não há avaliaçõesResumo de Álgebra Linear: Matrizes e Exemplos31 páginas
- Resumo sobre Matrizes e Sistemas LinearesAinda não há avaliaçõesResumo sobre Matrizes e Sistemas Lineares8 páginas
- Revisão de Sistemas Lineares e MatrizesAinda não há avaliaçõesRevisão de Sistemas Lineares e Matrizes23 páginas
- Conceitos de Matrizes e Sistemas LinearesAinda não há avaliaçõesConceitos de Matrizes e Sistemas Lineares22 páginas
- Álgebra Linear I: Matrizes e SistemasAinda não há avaliaçõesÁlgebra Linear I: Matrizes e Sistemas72 páginas
- Solução Numérica de Equações LinearesAinda não há avaliaçõesSolução Numérica de Equações Lineares23 páginas
- Aula 06 - Sistemas Lineares - Eliminação GaussianaAinda não há avaliaçõesAula 06 - Sistemas Lineares - Eliminação Gaussiana34 páginas
- Matrizes e Determinantes: Notas de AulaAinda não há avaliaçõesMatrizes e Determinantes: Notas de Aula24 páginas
- Fundamentos de Sistemas Lineares e MatrizesAinda não há avaliaçõesFundamentos de Sistemas Lineares e Matrizes32 páginas
- Matrizes e Determinantes: Conceitos e CálculosAinda não há avaliaçõesMatrizes e Determinantes: Conceitos e Cálculos23 páginas
- Matrizes e Sistemas Lineares: Guia CompletoAinda não há avaliaçõesMatrizes e Sistemas Lineares: Guia Completo31 páginas
- Introdução às Matrizes e Sistemas LinearesAinda não há avaliaçõesIntrodução às Matrizes e Sistemas Lineares34 páginas
- Sistemas Lineares: Métodos e ClassificaçõesAinda não há avaliaçõesSistemas Lineares: Métodos e Classificações43 páginas
- Apostila de Álgebra Linear MAT 27Ainda não há avaliaçõesApostila de Álgebra Linear MAT 27144 páginas
- Matemática Geral: Matrizes e OperaçõesAinda não há avaliaçõesMatemática Geral: Matrizes e Operações68 páginas
- Fundamentos de Matrizes em ComputaçãoAinda não há avaliaçõesFundamentos de Matrizes em Computação27 páginas
- Geometria Analítica e Álgebra LinearAinda não há avaliaçõesGeometria Analítica e Álgebra Linear61 páginas
- Álgebra Linear III: Matrizes e SistemasAinda não há avaliaçõesÁlgebra Linear III: Matrizes e Sistemas192 páginas
- Conduta+Militar+ +matriz +determinante +sistemas+ +teoriaAinda não há avaliaçõesConduta+Militar+ +matriz +determinante +sistemas+ +teoria10 páginas
- Fundamentos de Álgebra Linear e VetorialAinda não há avaliaçõesFundamentos de Álgebra Linear e Vetorial19 páginas
- Geometria Analítica e Álgebra LinearAinda não há avaliaçõesGeometria Analítica e Álgebra Linear88 páginas
- Geometria Analítica e Álgebra LinearAinda não há avaliaçõesGeometria Analítica e Álgebra Linear81 páginas
- Álgebra Linear III: Matrizes e SistemasAinda não há avaliaçõesÁlgebra Linear III: Matrizes e Sistemas194 páginas
- 4 - Aplicacoes de Matrizes e DeterminantesAinda não há avaliações4 - Aplicacoes de Matrizes e Determinantes8 páginas
- Sistemas de Equações Lineares e SoluçõesAinda não há avaliaçõesSistemas de Equações Lineares e Soluções64 páginas
- Algebra Linear III: Matrizes e SistemasAinda não há avaliaçõesAlgebra Linear III: Matrizes e Sistemas181 páginas
- Matrizes e Sistemas Lineares: FundamentosAinda não há avaliaçõesMatrizes e Sistemas Lineares: Fundamentos28 páginas
- Introdução às Matrizes MatemáticasAinda não há avaliaçõesIntrodução às Matrizes Matemáticas14 páginas
- Poema e Arcadismo no Brasil: AnáliseAinda não há avaliaçõesPoema e Arcadismo no Brasil: Análise14 páginas
- 21 Qualidades Essenciais de um LíderAinda não há avaliações21 Qualidades Essenciais de um Líder6 páginas
- Produtos Notáveis e Fatoração MatemáticaAinda não há avaliaçõesProdutos Notáveis e Fatoração Matemática88 páginas
- PIAGET, Jean. Sabedoria e Ilusões Da FilosofiaAinda não há avaliaçõesPIAGET, Jean. Sabedoria e Ilusões Da Filosofia118 páginas
- Manual para Reuniões do Ministério Infantil100% (3)Manual para Reuniões do Ministério Infantil45 páginas
- Manual de Referências Bibliográficas ABNTAinda não há avaliaçõesManual de Referências Bibliográficas ABNT22 páginas
- Resultados do Mini-Mult em Jovem AdultoAinda não há avaliaçõesResultados do Mini-Mult em Jovem Adulto2 páginas
- As Regras de Ouro Da Conduta Profissional PDFAinda não há avaliaçõesAs Regras de Ouro Da Conduta Profissional PDF151 páginas
- Gabarito Avaliação OS&M: Questões e RespostasAinda não há avaliaçõesGabarito Avaliação OS&M: Questões e Respostas9 páginas
- Resistência de Paralelepípedos em LaboratórioAinda não há avaliaçõesResistência de Paralelepípedos em Laboratório11 páginas
- Diretrizes para Avaliação na Educação InfantilAinda não há avaliaçõesDiretrizes para Avaliação na Educação Infantil16 páginas
- Exercícios sobre Coesão e CoerênciaAinda não há avaliaçõesExercícios sobre Coesão e Coerência7 páginas
- Função Social do Contrato em MoçambiqueAinda não há avaliaçõesFunção Social do Contrato em Moçambique6 páginas
- Questões de Engenharia Mecânica e FluidomecânicaAinda não há avaliaçõesQuestões de Engenharia Mecânica e Fluidomecânica2 páginas
- Termômetros e Calorimetria: ExercíciosAinda não há avaliaçõesTermômetros e Calorimetria: Exercícios10 páginas
- DBL8451 - Camadas de Zinco e de Liga de Zinco Eletrodepoditadas para Peças de Materiais Ferrosos PDFAinda não há avaliaçõesDBL8451 - Camadas de Zinco e de Liga de Zinco Eletrodepoditadas para Peças de Materiais Ferrosos PDF18 páginas
- Convocação para Curso de Formação PM/2013Ainda não há avaliaçõesConvocação para Curso de Formação PM/201365 páginas
- Efeito Peltier: Funcionamento e AplicaçõesAinda não há avaliaçõesEfeito Peltier: Funcionamento e Aplicações2 páginas
- Valores Extremos e Teoremas de FunçõesAinda não há avaliaçõesValores Extremos e Teoremas de Funções8 páginas