Aula 10 Sistemas lineares

Prévia do material em texto

Universidade Federal do Ceará
Campus de Russas
RUS0024
Programação computacional e
introdução ao cálculo numérico
Aula 10 – Sistemas lineares
Markos Freitas
markos@lia.ufc.br
 
Introdução
● Leis de Kirchhoff
● Circuitos elétricos
– Em um nó, a soma das correntes que entram é igual 
a soma das correntes que saem
● Um nó não acumula carga
– A soma algébrica da diferença de potencial elétrico 
em um percurso fechado é nula
 
Introdução
● Leis de Kirchhoff
● Circuitos elétricos
– Bateria e resistores
 
Introdução
● Leis de Kirchhoff
● Circuitos elétricos
– Qual o fluxo de corrente?
● B: i1 = i2 + i3
● C: i3 = i4 + i5
● Circuito 1: 2i1 + 5i2 + 3i1 = V
● Circuito 2: 3i3 + 2i4 + 4i3 – 5i2 = 0
● Circuito 3: 2i5 + 1i5 – 2i4 = 0
 
Introdução
● Sistema linear
● 5 equações e 5 incógnitas
– 1i1 – 1i2 – 1i3 = 0
– 1i3 – 1i4 – 1i5 = 0
– 5i1 + 5i2 = V
– – 5i2 + 7i3 + 2i4 = 0
– – 2i4 + 3i5 = 0
 
Sistema linear
● Conjunto de equações
● Todas as equações são lineares
– Do tipo
● a0x0 + a1x1 + … anxn = c
– Não existe multiplicação entre incógnitas
● x0x1, x22, xixj3xk
● Sistema anterior
– Incógnitas → is → corrente elétrica
● i1, i2, i3, i4 e i5
 
Sistema linear
● Sistema linear em notação matricial
● 5 equações e 5 incógnitas
– 1i1 – 1i2 – 1i3 + 0i4 + 0i5= 0
– 0i1 + 0i2 + 1i3 – 1i4 – 1i5 = 0
– 5i1 + 5i2 + 0i3 + 0i4 + 0i5 = V
– 0i1 – 5i2 + 7i3 + 2i4 + 0i5 = 0
– 0i1 + 0i2 + 0i3 – 2i4 + 3i5 = 0
● Solução
– Deve satisfazer a todas as equações
 
Sistema linear
● Sistema linear em notação matricial
● 5 linhas e 5 colunas
(
1 – 1 – 1 0 0
0 0 1 – 1 – 1
5 5 0 0 0
0 – 5 7 2 0
0 0 0 – 2 3
) [
i1
i2
i3
i4
i5
]=[ 00V00 ]
 
Sistema linear
● Exemplos
{2 x1+x2=3x1−3 x2=−2→ x∗={x1=1x2=1
{2 x1+x2=34 x1+2 x2=6→ x∗={x1=αx2=3−2α
{2 x1+x2=34 x1+2 x2=2
 
Sistema linear
● Exemplos
1 ponto
{2 x+ y=3x−3 y=−2
x−3 y=−2x−3 y>−2
x−3 y<−2
x−3 y>−2
x−3 y<−2
2 x+ y<3
2 x+ y>3
(1,1)
2 x+ y=3
2 x+ y<3
2 x+ y>3
 
Sistema linear
● Exemplos
infinitos
pontos
{2 x+ y=34 x+2 y=6 2 x+ y=3
2 x+ y>3
2 x+ y<3
4 x+2 y=6
4 x+2 y<6
4 x+2 y>6
 
Sistema linear
● Exemplos
nenhum
ponto
{2 x+ y=34 x+2 y=2 2 x+ y=3
2 x+ y>3
2 x+ y<3
4 x+2 y=2
4 x+2 y<2
4 x+2 y>2
4 x+2 y>2
2 x+ y<3
 
Sistema linear
● Exemplos
1 ponto
{2 x+ y=3x−3 y=−2ax+by=c
 
Sistema linear
● Exemplos
nenhum
ponto
{2 x+ y=3x−3 y=−2ax+by=c
 
Sistema linear
● Exemplos
infinitos
pontos
{a1 x+b1 y+c1 z=d1a2 x+b2 y+c2 z=d2
 
Sistema linear
● Exemplos
1 ponto
{a1 x+b1 y+c1 z=d1a2 x+b2 y+c2 z=d2a3 x+b3 y+c3 z=d3
 
Sistema linear
● De maneira geral
● m equações e n incógnitas
{ a1,1 x1+a1,2 x2+…+a1,n xn=b1→Eq1a2,1 x1+a2,2 x2+…+a2,n xn=b2→Eq2⋮am ,1 x1+am ,2 x2+…+am, n xn=bm→Eqm
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
am ,1 am ,2 ⋯ am ,n
)
m×n
[x1x2⋮xn]n×1=[
b1
b2
⋮
bm
]
m×1
Am×n xn×1=bm×1
 
Sistema linear
● De maneira geral
● m equações e n incógnitas
– Uma única soluções
● Sistema compatível determinado
– Nenhuma solução
● Sistema incompatível
– Infinitas soluções
● Sistema compatível indeterminado
 
Álgebra linear
● Matriz A
● Pode ser vista como uma função ou uma transformação
– Associa um vetor b de Rm a cada vetor x de Rn
● Onde b = Ax
● A: Rn → Rm | x → b = Ax
● Resolver o sistema Ax = b consiste em
● Dado b em Rm, obter, x de Rn tal que Ax = b, caso exista
– x* = A-1b → descobrir matriz inversa é complicado
● Três perguntas
● Existe x* tal que Ax* = b?
● Se existir, x* é único?
● Como obter x*?
 
Álgebra linear
● Matriz A
● Dado b
● Existe um único x* tal que A x* = b
A=(2 11 −3)
v=(11)→u=Av=(2 11 −3)(11)=( 3−2)
w=( 2−1)→t=Aw=(2 11 −3)( 2−1)=(35)
b=( 3−2)
x∗=(11)
 
Álgebra linear
● Graficamente
 
Álgebra linear
● Caso geral
● Número de equações diferente do número de 
incógnitas
● Caso específico
● Número de equações igual ao número de incógnitas
– Matriz A seja quadrada
● Colunas linearmente independentes
– Existe solução → sistema compatível determinado
– Nenhuma solução → sistema incompatível
● Colunas linearmente dependentes
– Infinitas soluções → sistema compatível indeterminado
– Nenhuma solução → sistema incompatível
 
Álgebra linear
● Dependência linear
● Um vetor escrito como combinação linear de 
outros vetores
● Matriz linearmente independente
● Suas colunas formam vetores
● Nenhuma coluna pode ser escrita como 
combinação linear das outras colunas
– Mesmo vale para linhas
v⃗=c1 u⃗1+c2 u⃗2+…+cn u⃗n
 
Métodos de sistemas lineares
● Métodos numéricos para resolver sistemas 
lineares
● Métodos diretos
– Fornecem uma solução aproximada após um número 
finito de iterações
● Pode-se calcular o número de iterações previamente
● Exemplos: Regra de Cramer, Eliminação de Gauss, 
Decomposição LU, Fatoração de Cholesky
● Métodos iterativos
– Geram uma sequência de aproximações a partir de uma 
aproximação inicial
● Geralmente, a sequência converge para uma solução
– Exemplos: Método de Gauss-Jacobi, Método de Gauss-Seidel
 
Regra de Cramer
● Calcula determinante
de A → |A|
● Para cada i
● Encontra matriz A(i)
– Troca coluna i
pelo vetor b
● Calcula
determinante
de A(i) → |A(i)|
● xi = |A(i)| / |A|
A x=b
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)[ x1x2⋮xn]=[
b1
b2
⋮
bn
]
xi=
|A(i)|
|A|
A(i)=(
a1,1 ⋯ a1, i−1 b1 a1, i+1 ⋯ a1,n
a2,1 ⋯ a2, i−1 b2 a2, i+1 ⋯ a2,n
⋮ ⋯ ⋮ ⋮ ⋮ ⋱ ⋮
an ,1 ⋯ an , i−1 bn an ,i+1 ⋯ an ,n
)
 
Regra de Cramer
● Número de determinantes
● N + 1 cálculos de determinante
● Cálculo de determinante
● N = 1 → direto
● N = 2 → fácil
● N = 3 → médio
● N ≥ 4 → chato de fazer
 
Regra de Cramer
● Determinante
● Escolha uma linha i
– Somatório nos elementos da linha i
● A-i,-j é A excluindo-se a linha i e a coluna j
– Exige o determinante de n matrizes de tamanho
n-1 x n-1
● Pode-se escolher uma coluna j
– Somatório nos elementos da coluna j
|A|=∑
j=1
n
(−1)i+ j ai , j|A−i ,− j|
 
Regra de Cramer
● Determinante de matriz n-1 x n-1
● n-1 determinantes de matriz n-2 x n-2
● Determinante de matriz n-2 x n-2
● n-2 determinantes de matriz n-3 x n-3
● …
● Determinante de matriz 4 x 4
● 4 determinantes de matriz 3 x 3
● Totalizando
● O(n!) operações
– Número muito grande
– Impraticável
 
Eliminação de Gauss
● Transformação
● Matriz cheia em uma triangular superior
– Matriz A em uma matriz Ã
– De forma que
● x* é solução dos dois sistemas lineares
– Sistemas equivalentes
● Mesma solução
A x=b→~A x=~b
 
Eliminação de Gauss
● Resolução de sistema triangular superior
(
a1,1 a1,2 a1,3 ⋯ a1,n−1 a1,n
0 a2,2 a2,3 ⋯ a2,n−1 a2,n
0 0 a3,3 ⋯ a3,n−1 a3,n
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
0 0 0 ⋯ an−1,n−1 an−1,n
0 0 0 ⋯ 0 an ,n
) [ x1x2⋮xn ]=[b1b2⋮bn ]
{
a1,1 x1+a1,2 x2+a1,3 x3+…+a1,n−1 xn−1+a1,n xn=b1
a2,2 x2+a2,3 x3+…+a2,n−1 xn−1+a2,n xn=b2
a3,3 x3+…+a3,n−1 xn−1+a3,n xn=b3
⋮
an−1,n−1 xn−1+an ,n xn=bn−1
an ,n xn=bn
 
Eliminação de Gauss
● Resolução de sistema triangular superior
● Encontro xn → da equação n
– Diretamente → xn = bn / an,n
● Encontro xn-1 → da equação n-1
– Usando xn → xn-1 = (bn-1 – an-1,n xn)/an-1,n-1
● …
● Encontro x2 → da equação 2
– x2 = (b2 – a2,n xn – a2,n-1 xn-1 – … – a2,3 x3)/a2,2
● Encontro x1 → da equação 1
– x1 = (b1 – a1,n xn – a1,n-1 xn-1 – … – a1,2 x2)/a1,1
 
Eliminação de Gauss
● Algoritmo de substituição retroativa
xn = bn / an,n
para k = n-1, …, 1 faça
s = 0
para j = k+1,…, n faça
s = s + ak,j xj
xk = (bk – s)/ak,k
 
Eliminação de Gauss
● Operações elementares
● Garantem a equivalência entre sistemas
– Trocar duas equações
● Eqi ↔ Eqj
● Li ↔ Lj
– Multiplicar uma equação por uma constante
● Constante diferente de 0
– Eqi ← c Eqi, c ≠ 0
– Li ← c Li, c ≠ 0
– Adicionar um múltiplo de uma equação a outra equação
● Múltiplo diferente de 0
– Eqi ← Eqi + c Eqj, c ≠ 0
– Li ← Li + c Lj, c ≠ 0
 
Eliminação de Gauss
● Procedimento
● Converter matriz qualquer em triangular 
superior
– Eliminação → transformação em zeros
– Eliminação coluna a coluna
● Assumimos |A| ≠ 0
● Matriz aumentada A|b
– Matriz A concatenada do vetor b
● Vetor b colocado como última coluna na matriz A|b
 
Eliminação de Gauss
● Matriz aumentada A|b
A x=b
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)[ x1x2⋮xn]=[
b1
b2
⋮
bn
]
A∣b=(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
|b1b2⋮bn)
 
Eliminação de Gauss
● Inicialização
● A(0)|b(0) ← A|b
● Sequência de transformações
● A(1)|b(1) de A(0)|b(0)
– 1a coluna, abaixo da diagonal principal, é composta de zeros
● A(2)|b(2) de A(1)|b(1)
– 2a coluna, abaixo da diagonal principal, é composta de zeros
● A(3)|b(3) de A(2)|b(2)
– 3a coluna, abaixo da diagonal principal, é composta de zeros
● …
● A(n-1)|b(n-1) de A(n-2)|b(n-2)
– n-1-ésima coluna, abaixo da diagonal principal, é composta de zeros
– A(n-1) é triangular superior
● Resolução por substituição retroativa
● A(n-1)x = b(n-1)
 
Eliminação de Gauss
● Inicialização
● A(0)|b(0) ← A|b
(
a1,1
(0) a1,2
(0) a1,3
(0) ⋯ a1,n−1
(0) a1,n
(0)
a2,1
(0) a2,2
(0) a2,3
(0) ⋯ a2,n−1
(0) a2,n
(0)
a3,1
(0) a3,2
(0) a3,3
(0) ⋯ a3,n−1
(0) a3,n
(0)
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
an−1,1
(0) an−1,2
(0) an−1,3
(0) ⋯ an−1,n−1
(0) an−1,n
(0)
an ,1
(0) an ,2
(0) an ,3
(0) ⋯ an ,n−1
(0) an ,n
(0)
|
b1
(0)
b2
(0)
b3
(0)
⋮
bn−1
(0)
bn
(0)
)
 
Eliminação de Gauss
● Transformação
● A(1)|b(1) de A(0)|b(0)
(
a1,1
(1) a1,2
(1) a1,3
(1) ⋯ a1,n−1
(1) a1,n
(1)
0 a2,2
(1) a2,3
(1) ⋯ a2,n−1
(1) a2,n
(1)
0 a3,2
(1) a3,3
(1) ⋯ a3,n−1
(1) a3,n
(1)
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
0 an−1,2
(1) an−1,3
(1) ⋯ an−1,n−1
(1) an−1,n
(1)
0 an ,2
(1) an ,3
(1) ⋯ an ,n−1
(1) an ,n
(1)
|
b1
(1)
b2
(1)
b3
(1)
⋮
bn−1
(1)
bn
(1)
)
 
Eliminação de Gauss
● Transformação
● A(1)|b(1) de A(0)|b(0)
● Terceira operação elementar
– Adicionar um múltiplo de uma equação a outra equação
● Múltiplo da equação 1
● Linha 2
– L2 ← L2 + c2,1 L1, c2,1 ≠ 0
● L2(1) ← L2(0) + c2,1 L1(0), c2,1 ≠ 0
– Restrição → a2,1(1) = 0
● a2,1(1) = a2,1(0) + c2,1 a1,1(0) = 0
● c2,1 = - a2,1(0) / a1,1(0) = - m2,1
– m2,1 = a2,1(0) / a1,1(0) → multiplicador da linha 2
 
Eliminação de Gauss
● Transformação
● A(1)|b(1) de A(0)|b(0)
● Terceira operação elementar
– Adicionar um múltiplo de uma equação a outra equação
● Múltiplo da equação 1
● Linha 3
– L3 ← L3 + c3,1 L1, c3,1 ≠ 0
● L3(1) ← L3(0) + c3,1 L1(0), c3,1 ≠ 0
– Restrição → a3,1(1) = 0
● a3,1(1) = a3,1(0) + c3,1 a1,1(0) = 0
● c3,1 = - a3,1(0) / a1,1(0) = - m3,1
– m3,1 = a3,1(0) / a1,1(0) → multiplicador da linha 3
 
Eliminação de Gauss
● Transformação
● A(1)|b(1) de A(0)|b(0)
● Terceira operação elementar
– Adicionar um múltiplo de uma equação a outra 
equação
● Múltiplo da equação 1
● Linha n
– mn,1 = an,1(0) / a1,1(0) → multiplicador da linha n
– cn,1 = - mn,1 = - an,1(0) / a1,1(0)
 
Eliminação de Gauss
● Transformação
● A(1)|b(1) de A(0)|b(0)
● Linha i > 1
– mi,1 = ai,1(0) / a1,1(0)
– ai,j(1) = ai,j(0) - mi,1 a1,j(0)
– bi(1) = bi(0) - mi,1 b1(0)
● Linha 1
– Não modificada
● Pivô
– a1,1(0)
 
Eliminação de Gauss
● Transformação
● A(2)|b(2) de A(1)|b(1)
(
a1,1
(2) a1,2
(2) a1,3
(2) ⋯ a1,n−1
(2) a1,n
(2)
0 a2,2
(2) a2,3
(2) ⋯ a2,n−1
(2) a2,n
(2)
0 0 a3,3
(2) ⋯ a3,n−1
(2) a3,n
(2)
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
0 0 an−1,3
(2) ⋯ an−1,n−1
(2) an−1,n
(2)
0 0 an ,3
(2) ⋯ an ,n−1
(2) an ,n
(2)
|
b1
(2)
b2
(2)
b3
(2)
⋮
bn−1
(2)
bn
(2)
)
 
Eliminação de Gauss
● Transformação
● A(2)|b(2) de A(1)|b(1)
● Linha i > 2
– mi,2 = ai,2(1) / a2,2(1)
– ai,j(2) = ai,j(1) - mi,2 a2,j(1)
– bi(2) = bi(1) - mi,2 b2(1)
● Linha i ≤ 2
– Não modificada
● Pivô
– a2,2(1)
 
Eliminação de Gauss
● Transformação
● A(k)|b(k) de A(k-1)|b(k-1)
● Linha i > k
– mi,k = ai,k(k-1) / ak,k(k-1)
– ai,j(k) = ai,j(k-1) - mi,k ak,j(k-1)
– bi(k) = bi(k-1) - mi,k bk(k-1)
● Linha i ≤ k
– Não modificada
● Pivô
– ak,k(k-1)
(
a1,1
(k ) a1,2
(k ) ⋯ a1,n−1
(k ) ⋯ a1,n
(k )
0 a2,2
(k ) ⋯ a2,n−1
(k ) ⋯ a2,n
(k)
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
0 0 ⋯ ak ,n−1
(k) ⋯ ak ,n
(k )
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
0 0 ⋯ an ,n−1
(k) ⋯ an ,n
(k )
|
b1
(k )
b2
(k )
⋮
bk
(k )
⋮
bn
(k )
)
 
Eliminação de Gauss
● Transformação
● A(n-1)|b(n-1) de A(n-2)|b(n-2)
● Sistema linear A(n-1)|b(n-1)
– Triangular superior
(
a1,1
(n−1) a1,2
(n−1) a1,3
(n−1) ⋯ a1,n−1
(n−1) a1,n
(n−1)
0 a2,2
(n−1) a2,3
(n−1) ⋯ a2,n−1
(n−1) a2,n
(n−1)
0 0 a3,3
(n−1) ⋯ a3,n−1
(n−1) a3,n
(n−1)
⋮ ⋮ ⋮ ⋱ ⋮ ⋮
0 0 0 ⋯ an−1,n−1
(n−1) an−1,n
(n−1)
0 0 0 ⋯ 0 an ,n
(n−1)
|
b1
(n−1)
b2
(n−1)
b3
(n−1)
⋮
bn−1
(n−1)
bn
(n−1)
)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Primeira linha → i = 1
● Não modificada
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Segunda linha → i = 2
● Multiplicador → m2,1 = a2,1(0) / a1,1(0) = 1 / 3
– Operação elementar → L2(1) ← L2(0) - m2,1 L1(0)
● Coluna 1 → j = 1 → a2,1(1) = a2,1(0) - m2,1 a1,1(0) = 1 – 1/3 * 3 = 0
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Segunda linha → i = 2
● Multiplicador → m2,1 = a2,1(0) / a1,1(0) = 1 / 3
– Operação elementar → L2(1) ← L2(0) - m2,1 L1(0)
● Coluna 2 → j = 2 → a2,2(1) = a2,2(0) - m2,1 a1,2(0) = 1 – 1/3 * 2 = 
1/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Segunda linha → i = 2
● Multiplicador → m2,1 = a2,1(0) / a1,1(0) = 1 / 3
– Operação elementar → L2(1) ← L2(0) - m2,1 L1(0)
● Coluna 3 → j = 3 → a2,3(1) = a2,3(0) - m2,1 a1,3(0) = 2 – 1/3 * 4 = 
2/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Segunda linha → i = 2
● Multiplicador → m2,1 = a2,1(0) / a1,1(0) = 1 / 3
– Operação elementar → L2(1) ← L2(0) - m2,1 L1(0)
● Vetor b → b2(1) = b2(0) - m2,1 b1(0) = 2 – 1/3 * 1 = 5/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Terceira linha → i = 3
● Multiplicador → m3,1 = a3,1(0) / a1,1(0) = 4 / 3
– Operação elementar → L3(1) ← L3(0) - m3,1 L1(0)
● Coluna 1 → j = 1 → a3,1(1) = a3,1(0) - m3,1 a1,1(0) = 4 – 4/3 * 3 = 0
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0)= 3
– Terceira linha → i = 3
● Multiplicador → m3,1 = a3,1(0) / a1,1(0) = 4 / 3
– Operação elementar → L3(1) ← L3(0) - m3,1 L1(0)
● Coluna 2 → j = 2 → a3,2(1) = a3,2(0) - m3,1 a1,2(0) = 3 – 4/3 * 2 = 
1/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Terceira linha → i = 3
● Multiplicador → m3,1 = a3,1(0) / a1,1(0) = 4 / 3
– Operação elementar → L3(1) ← L3(0) - m3,1 L1(0)
● Coluna 3 → j = 3 → a3,3(1) = a3,3(0) - m3,1 a1,3(0) = -2 – 4/3 * 4 = 
-22/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Entrada
● Primeiro passo → k = 1
– Pivô → a1,1(0) = 3
– Terceira linha → i = 3
● Multiplicador → m3,1 = a3,1(0) / a1,1(0) = 4 / 3
– Operação elementar → L3(1) ← L3(0) - m3,1 L1(0)
● Vetor b → b3(1) = b3(0) - m3,1 b1(0) = 3 – 4/3 * 1 = 5/3
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3 A(0)∣b(0)=(
3 2 4
1 1 2
4 3 −2|
1
2
3)
 
Eliminação de Gauss
● Exemplo
● Fim do primeiro passo
● Segundo passo → k = 2
– Pivô → a2,2(1) = 1/3
– Primeira linha → i = 1
● Não modificada
– Segunda linha → i = 2
● Não modificada
A(1)∣b(1)=(3 2 40 1 /3 2/30 1 /3 −22/3|
1
5 /3
5 /3){
3 x1+2 x2+4 x3=1
1/3 x2+2 /3 x3=5 /3
1 /3 x2−22/3 x3=5 /3
 
Eliminação de Gauss
● Exemplo
● Fim do primeiro passo
● Segundo passo → k = 2
– Pivô → a2,2(1) = 1/3
– Primeira linha → i = 3
● Multiplicador → m3,2 = a3,2(1) / a2,2(1) = 1/3 / 1/3 = 1
– Operação elementar → L3(2) ← L3(1) - m3,2 L2(1)
● Coluna 1 → j = 1 → a3,1(2) = a3,1(1) - m3,2 a2,1(1) = 0 – 1 * 0 = 0
A(1)∣b(1)=(3 2 40 1 /3 2/30 1 /3 −22/3|
1
5 /3
5 /3){
3 x1+2 x2+4 x3=1
1/3 x2+2 /3 x3=5 /3
1 /3 x2−22/3 x3=5 /3
 
Eliminação de Gauss
● Exemplo
● Fim do primeiro passo
● Segundo passo → k = 2
– Pivô → a2,2(1) = 1/3
– Primeira linha → i = 3
● Multiplicador → m3,2 = a3,2(1) / a2,2(1) = 1/3 / 1/3 = 1
– Operação elementar → L3(2) ← L3(1) - m3,2 L2(1)
● Coluna 2 → j = 2 → a3,2(2) = a3,2(1) - m3,2 a2,2(1) = 1/3 – 1 * 1/3 = 
0
A(1)∣b(1)=(3 2 40 1 /3 2/30 1 /3 −22/3|
1
5 /3
5 /3){
3 x1+2 x2+4 x3=1
1/3 x2+2 /3 x3=5 /3
1 /3 x2−22/3 x3=5 /3
 
Eliminação de Gauss
● Exemplo
● Fim do primeiro passo
● Segundo passo → k = 2
– Pivô → a2,2(1) = 1/3
– Primeira linha → i = 3
● Multiplicador → m3,2 = a3,2(1) / a2,2(1) = 1/3 / 1/3 = 1
– Operação elementar → L3(2) ← L3(1) - m3,2 L2(1)
● Coluna 3 → j = 3 → a3,3(2) = a3,3(1) - m3,2 a2,3(1) = -22/3 – 1 * 2/3 
= -24/3 = -8
A(1)∣b(1)=(3 2 40 1 /3 2/30 1 /3 −22/3|
1
5 /3
5 /3){
3 x1+2 x2+4 x3=1
1/3 x2+2 /3 x3=5 /3
1 /3 x2−22/3 x3=5 /3
 
Eliminação de Gauss
● Exemplo
● Fim do primeiro passo
● Segundo passo → k = 2
– Pivô → a2,2(1) = 1/3
– Primeira linha → i = 3
● Multiplicador → m3,2 = a3,2(1) / a2,2(1) = 1/3 / 1/3 = 1
– Operação elementar → L3(2) ← L3(1) - m3,2 L2(1)
● Vetor b → b3(2) = b3(1) - m3,2 b2(1) = 5/3 – 1 * 5/3 = 0
A(1)∣b(1)=(3 2 40 1 /3 2/30 1 /3 −22/3|
1
5 /3
5 /3){
3 x1+2 x2+4 x3=1
1/3 x2+2 /3 x3=5 /3
1 /3 x2−22/3 x3=5 /3
 
Eliminação de Gauss
● Exemplo
● Fim do segundo passo
● Resolução por substituição retroativa
– x3 = ( 0 ) / ( -8 ) = 0
– x2 = ( 5/3 – 2/3 * 0 ) / ( 1/3 ) = 5
– x1 = ( 1 – 2 * 5 – 4 * 0 ) / ( 3 ) = -3
A(2)∣b(2)=(3 2 40 1/3 2 /30 0 −8|
1
5 /3
0 ){
3 x1+2 x2+4 x3=1
1 /3 x2+2/3 x3=5 /3
−8 x3=0
 
Eliminação de Gauss
● Algoritmo
● Passo k
– Linha i ≤ k, coluna j < k
● Não modificada
● Desnecessário considerá-las
– Linha i > k, coluna = k
● Valor 0
● Desnecessário fazer cálculos
● Reaproveitamento de espaço
– Alteração da mesma matriz A
– Alteração do mesmo vetor b
 
Eliminação de Gauss
● Algoritmo de eliminação de Gauss com 
substituição retroativa
para k = 1, …, n-1 faça
 para i = k+1, …, n faça
 m = ai,k / ak,k
 ai,k = 0
 para j = k+1, …, n faça
 ai,j = ai,j – m * ak,j
 bi = bi – m * bk
xn = bn / an,n
para k = n-1, …, 1 faça
 s = 0
 para j = k+1, …, n faça
 s = s + ak,j xj
 xk = (bk – s)/ak,k
 
Eliminação de Gauss com 
pivoteamento
● Passo k
● Multiplicador → divisão por ak,k
– Se ak,k for 0 → divisão por 0 → número inválido
● NaN
– Se ak,k for próximo de 0 → divisão por número muito 
pequeno → número muito grande
– Imprecisão nos resultados
● Erro muito grande
● Pivoteamento
● Parcial → troca de linhas
● Total → troca de linhas e colunas
 
Eliminação de Gauss com 
pivoteamento
● Pivoteamento parcial
● Troca de linhas
– Procurar elemento na coluna mais longe de 0
● Início do passo k
– Escolhe a linha i ≥ k com maior ai,k
● Em valor absoluto
– Troca linha i com linha k
● Na matriz A e no vetor b
 
Eliminação de Gauss com 
pivoteamento
● Pivoteamento total
● Troca de linhas e colunas
– Procurar elemento mais longe de 0
● Início do passo k
– Escolhe a linha i ≥ k e a coluna j ≥ k com maior ai,j
● Em valor absoluto
– Troca linha i com linha k
● Na matriz A e no vetor b
– Troca coluna j com coluna k
● Na matriz A
– Consequências para o vetor x
● Troca das linhas j com k no vetor x
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Sem pivoteamento
{0,0002 x1+2 x2=52 x1+2 x2=6
A(0)∣b(0)=(0,2×10−3 0,2×1010,2×101 0,2×101|0,5×10
1
0,6×101)
m2,1=
0,2×101
0,2×10−3
=0,1×105
a2,2=0,2×10
1−(0,1×105)×(0,2×101)=−0,2×105
b2=0,6×10
1−(0,1×105)×(0,5×101)=−0,5×105
A(1)∣b(1)=(0,2×10−3 0,2×1010 −0,2×105| 0,5×10
1
−0,5×105)
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Sem pivoteamento
● Substituição retroativa
{0,0002 x1+2 x2=52 x1+2 x2=6
A(1)∣b(1)=(0,2×10−3 0,2×1010 −0,2×105| 0,5×10
1
−0,5×105)
x2=
−0,5×105
−0,2×105
=0,25×101=2,5
x1=
0,5×101−(0,2×101)×(0,25×101)
0,2×10−3
=0,5×10
1−0,5×101
0,2×10−3
=0
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Sem pivoteamento
● Ax = b
{0,0002 x1+2 x2=52 x1+2 x2=6
(0,0002 22 2)[ 02,5]=[55]≠[56 ]
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Com pivoteamento parcial
{0,0002 x1+2 x2=52 x1+2 x2=6
A(0)∣b(0)=( 0,2×101 0,2×1010,2×10−3 0,2×101|0,5×10
1
0,6×101)
m2,1=
0,2×10−3
0,2×101
=0,1×10−3
a2,2=0,2×10
1−(0,1×10−3)×(0,2×101)=0,2×101
b2=0,6×10
1−(0,1×10−3)×(0,5×101)=0,5×101
A(1)∣b(1)=(0,2×101 0,2×1010 0,2×101|0,6×10
1
0,5×101)
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Com pivoteamento parcial
● Substituição retroativa
{0,0002 x1+2 x2=52 x1+2 x2=6
A(1)∣b(1)=(0,2×101 0,2×1010 0,2×101|0,6×10
1
0,5×101)
x2=
0,5×101
0,2×101
=0,25×101=2,5
x1=
0,6×101−(0,2×101)×(0,25×101)
0,2×101
=0,6×10
1−0,5×101
0,2×101
=0,5
 
Eliminação de Gauss com 
pivoteamento
● Exemplo → aritmética de 3 dígitos
● Com pivoteamento parcial
● Ax = b
{0,0002 x1+2 x2=52 x1+2 x2=6
(0,0002 22 2)[0,52,5]=[5,00016 ]≃[56 ]
 
Decomposição LU
● Decomposição ou fatoração
● Transformar a matriz A em uma multiplicação de 
matrizes
● Decomposição LU
– A = L U
● L é triangular inferior com diagonal unitária
● U é triangular superior
– Resolução de dois sistemas lineares
● A x = b → LUx = b
– Faço Ux = y
– Ly = b → Encontra-se y por substituição direta
– Ux = y → Encontra-se y por substituição retroativa
● Pode-se trocar b por qualquer outro vetor
– A fatoração de A não muda
 
Decomposição LU
● A = LU
● Substituição direta
● Ly = b
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an,1 an ,2 ⋯ an ,n
)=( 1 0 ⋯ 0l2,1 1 ⋯ 0⋮ ⋮ ⋱ ⋮ln ,1 ln ,2 ⋯ 1)(
u1,1 u1,2 ⋯ u1,n
0 u2,2 ⋯ u2,n
⋮ ⋮ ⋱ ⋮
0 0 ⋯ un ,n
)
(
1 0 ⋯ 0
l2,1 1 ⋯ 0
⋮ ⋮ ⋱ ⋮
ln ,1 ln ,2 ⋯ 1
)[ y1y2⋮yn ]=[
b1
b2
⋮
bn
]
 
Decomposição LU
● A = LU
● Substituição retroativa
● Ux = y
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)=( 1 0 ⋯ 0l2,1 1 ⋯ 0⋮ ⋮ ⋱ ⋮ln ,1 ln ,2 ⋯ 1)(
u1,1 u1,2 ⋯ u1,n
0 u2,2 ⋯ u2,n
⋮ ⋮ ⋱ ⋮
0 0 ⋯ un ,n
)
(
u1,1 u1,2 ⋯ u1,n
0 u2,2 ⋯ u2,n
⋮ ⋮ ⋱ ⋮
0 0 ⋯ un ,n
) [ x1x2⋮xn ]=[
y1
y2
⋮
yn
]
 
Decomposição LU
● A = LU
● Como descobrir L e U?
– Processo de eliminação de Gauss
● Multiplicadores fazem parte de L
● Matriz A(n-1) é a matriz U
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)=( 1 0 ⋯ 0l2,1 1 ⋯ 0⋮ ⋮ ⋱ ⋮ln ,1 ln ,2 ⋯ 1)(
u1,1 u1,2 ⋯ u1,n
0 u2,2 ⋯ u2,n
⋮ ⋮ ⋱ ⋮
0 0 ⋯ un ,n
)
 
Decomposição LU
A=(a1,1 a1,2 a1,3a2,1 a2,2 a2,3a3,1 a3,2 a3,3)=(
1 0 0
l2,1 1 0
l3,1 l3,2 1)(
u1,1 u1,2 u1,3
0 u2,2 u2,3
0 0 u3,3)=LU
A(0)=(a1,1
(0) a1,2
(0) a1,3
(0)
a2,1
(0) a2,2
(0) a2,3
(0)
a3,1
(0) a3,2
(0) a3,3
(0))=(a1,1 a1,2 a1,3a2,1 a2,2 a2,3a3,1 a3,2 a3,3)
l2,1=m2,1=
a2,1
(0)
a1,1
(0) l3,1=m3,1=
a3,1
(0)
a1,1
(0) → A
(1)=(a1,1
(1) a1,2
(1) a1,3
(1)
0 a2,2
(1) a2,3
(1)
0 a3,2
(1) a3,3
(1))
l3,2=m3,2=
a3,2
(1)
a2,2
(1) → U=A
(2)=(a1,1
(2) a1,2
(2) a1,3
(2)
0 a2,2
(2) a2,3
(2)
0 0 a3,3
(2))
 
Decomposição LU
● Exemplo
{3 x1+2 x2+4 x3=1x1+x2+2 x3=24 x1+3 x2−2 x3=3
A(0)=(3 2 41 1 24 3 −2)→m2,1=13 ,m3,1=43
A(1)=(3 2 40 1/3 2 /30 1/3 −22/3)→m3,1=1 /31 /3=1
A(2)=(3 2 40 1 /3 2/30 0 −8 )
L=( 1 0 01 /3 1 04 /3 1 1) U=(
3 2 4
0 1/3 2 /3
0 0 −8 )
 
Decomposição LU
● Exemplo
LU=( 1 0 01 /3 1 04 /3 1 1)(
3 2 4
0 1/3 2 /3
0 0 −8 )=
( 1∗3+0∗0+0∗0 1∗2+0∗1 /3+0∗0 1∗4+0∗2 /3+0∗−81/3∗3+1∗0+0∗0 1/3∗2+1∗1/3+0∗0 1/3∗4+1∗2 /3+0∗−84 /3∗3+1∗0+1∗0 4 /3∗2+1∗1/3+1∗0 4 /3∗4+1∗2/3+1∗−8)=
( 3+0+0 2+0+0 4+0+01+0+0 2/3+1/3+0 4 /3+2 /3+012/3+0+0 8 /3+1/3+0 16 /3+2 /3−8)=
(3 2 41 1 24 3 −2)
 
Decomposição LU
● Exemplo
Ly=b
( 1 0 01/3 1 04 /3 1 1)[ y1y2y3]=[
1
2
3]
y1=1
1
3
y1+ y2=2→ y2=2−1 /3=5 /3
4
3
y1+1 y2+ y3=3→ y3=3−4 /3−5 /3=0
Ux= y
(3 2 40 1 /3 2/30 0 −8 )[ x1x2x3]=[
1
5/3
0 ]
x3=0
x2=5
x1=−3
 
Decomposição LU
● Observações
● Decomposição
– Descobrimos multiplicadores de L
– Descobrimos U
– Não mexemos em b
● Substituição direta → Ly = b
– Mesmo que fazer eliminação de Gauss em b
● Substituição retroativa
– Mesmo da eliminação de Gauss
 
Decomposição LU
● Observações
● É possível fazer pivoteamento
– Parcial
● Mais fácil
● Deve-se fazer a troca de linhas também no vetor b
– Total
● Mais difícil
● Deve-se fazer a troca de linhas também no vetor b
– De acordo com a troca de linhas da matriz A
● Deve-se fazer a troca de linhas também no vetor x
– De acordo com a troca de colunas da matriz A
 
Decomposição LU
● Observações
● Economia de espaço
– Utiliza-se a matriz A para guardar L e de U
● L
– Diagonal principal → sempre 1
– Acima da diagonal principal → sempre 0
● U
– Abaixo da diagonal principal → sempre 0
● A
– Diagonal principal → armazena a diagonal principal de U
– Acima da diagonal principal → armazena elementos de U
– Abaixo da diagonal principal → armazena elementos de L
 
Decomposição LU
● Algoritmo → Decomposição LU
para k = 1, …, n-1 faça
 para i = k+1, …, n faça
 m = ai,k / ak,k
 ai,k = m
 para j = k+1, …, n faça
 ai,j = ai,j – m * ak,j
 
Decomposição LU
● Algoritmo → Resolução
para i = 1, …, n faça
 s = 0
 para j = 1, …, i-1 faça
 s = s + ai,j yj
 yi = bi – s
para i = n, …, 1 faça
 s = 0
 para j = i+1, …, n faça
 s = s + ai,j xj
 xi = (bi – s)/ai,i
 
Fatoração de Cholesky
● Caso específico da decomposição LU
● Para matrizes simétricas, definidas positivas
– Matriz A é definida positiva se xT A x > 0, para qualquer 
vetor x
● xT é a transposta de x
● A = LU = LDU = L(DD)LT = (LD)(LD)T = GGT
– D é matriz diagonal contendo os elementos da 
diagonal principal de U
– U = LT, pois a matriz é simétrica
– Em D, di,i = √di,i
– G = LD
● Triangular inferior com diagonal estritamente positiva
 
Fatoração de Cholesky
● Exemplo
(
16 −4 12 −4
−4 2 −1 1
12 −1 14 −2
−4 1 −2 83
)=(
1 0 0 0
−1/4 1 0 0
3 /4 2 1 0
−1/4 0 1 1
)(
16 −4 12 −4
0 1 2 0
0 0 1 1
0 0 0 81
)=
(
1 0 0 0
−1/4 1 0 0
3 /4 2 1 0
−1/4 0 1 1
)(
16 0 0 0
0 1 0 0
0 0 1 0
0 0 0 81
)(
1 −1 /4 3 /4 −1/4
0 1 2 0
0 0 1 1
0 0 0 1
)=
(
1 0 0 0
−1/4 1 0 0
3 /4 2 1 0
−1/4 0 1 1
)(
4 0 0 0
0 1 0 0
0 0 1 0
0 0 0 9
)(
4 0 0 0
0 1 0 0
0 0 1 0
0 0 0 9
)(
1 −1 /4 3 /4 −1/4
0 1 2 0
0 0 1 1
0 0 0 1
)
 
Fatoração de Cholesky
● Exemplo
(
16 −4 12 −4
−4 2 −1 1
12 −1 14 −2
−4 1 −2 83
)=
(
4 0 0 0
−1 1 0 0
3 2 1 0
−1 0 1 9
)(
4 −1 3 −1
0 1 2 0
0 0 1 1
0 0 0 9
)
 
Fatoração de Cholesky
● A = GGT → coluna k = 1
(
a1,1 a2,1 ⋯ an ,1
a2,1 a2,2 ⋯ an ,2
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)=(
g1,1 0 ⋯ 0
g2,1 g2,2 ⋯ 0
⋮ ⋮ ⋱ ⋮
gn ,1 gn ,2 ⋯ gn ,n
)(
g1,1 g2,1 ⋯ gn ,1
0 g2,2 ⋯ gn ,2
⋮ ⋮ ⋱ ⋮
0 0 ⋯ gn ,n
)
a1,1=g1,1
2 →g1,1=√a1,1
a2,1=g2,1 g1,1→g2,1=
a2,1
g1,1
a3,1=g3,1 g1,1→g3,1=
a3,1
g1,1
⋮
an ,1=gn ,1g1,1→gn ,1=
an ,1
g1,1
}gi ,1= ai ,1g1,1
 
Fatoração de Cholesky
● A = GGT → coluna k = 2
(
a1,1 a2,1 ⋯ an ,1
a2,1 a2,2 ⋯ an ,2
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)=(
g1,1 0 ⋯ 0
g2,1 g2,2 ⋯ 0
⋮ ⋮ ⋱ ⋮
gn ,1 gn ,2 ⋯ gn ,n
)(
g1,1 g2,1 ⋯ gn ,1
0 g2,2 ⋯ gn ,2
⋮ ⋮ ⋱ ⋮
0 0 ⋯ gn ,n
)
a2,1=g1,1 g2,1
a2,2=g2,1
2 +g2,2
2 →g2,2=√a2,2−g2,12
a3,2=g3,1 g2,1+g3,2 g2,2→g3,2=
a3,2−g3,1 g2,1
g2,2
⋮
an ,2=gn ,1g2,1+gn ,2 g2,2→gn ,2=
an ,2−gn ,1g2,1
g2,2
}gi ,2=ai ,2−gi ,1g2,1g2,2
Já calculado
 
Fatoração de Cholesky
● A = GGT → coluna k qualquer
(
a1,1 a2,1 ⋯ an ,1
a2,1 a2,2 ⋯ an ,2
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)=(
g1,1 0 ⋯ 0
g2,1 g2,2 ⋯ 0
⋮ ⋮ ⋱ ⋮
gn ,1 gn ,2 ⋯ gn ,n
)(
g1,1 g2,1 ⋯ gn ,1
0 g2,2 ⋯ gn ,2
⋮ ⋮ ⋱ ⋮
0 0 ⋯ gn ,n
)
ak ,k=gk ,1
2 +gk ,2
2 +…+gk ,k
2 →gk , k=√a2,2−∑i=1
k−1
gk ,i
2
a j , k=g j ,1gk ,1+g j ,2gk ,2+…+g j , k gk , k→g j , k=
a j , k−∑
i=1
k−1
g j , igk ,i
gk , k
, k< j≤n
 
Fatoração de Cholesky
● Resolução do sistema
● Parecido com a da decomposição LU
– A = GGT
● Gy = b
● GTx = y
– Diferença
● Em LU
– L tem diagonal unitária
● Em Cholesky
– L tem diagonal com valores positivos
 
Fatoração de Cholesky
● Algoritmo
para k = 1, …, n faça
 s = 0
 para j = 1, …, k-1 faça
 s = s + gk,j2
 r = ak,k – soma
 gk,k = r1/2
 para i = k+1, …, n faça
 s = 0
 para j = 1, …, k-1 faça
 s = s + gi,j gk,j
 gi,k = (ai,k – s) / gk,k
 
Fatoração de Cholesky
● Observações
● Eliminação de Gauss ou decomposição LU 
com pivoteamento
– Divisão por zero → ak,k = 0 (ou próximo de 0)
● Matriz não tem inversa
● Impossível encontrar solução para o sistema Ax = b
– Sistema indeterminado
● Fatoração de Cholesky
– Raiz de um número não positivo → r ≤ 0
● Matriz A não é definida positiva
 
Matriz inversa
● AB = BA = I
● B é a inversa de A
● B = A-1
● A também é inversa de B
● Como descobrir A-1?
(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)(
b1,1 b1,2 ⋯ b1,n
b2,1 b2,2 ⋯ b2,n
⋮ ⋮ ⋱ ⋮
bn ,1 bn ,2 ⋯ bn ,n
)=(1 0 ⋯ 00 1 ⋯ 0⋮ ⋮ ⋱ ⋮0 0 ⋯ 1)
 
Matriz inversa
● Coluna a coluna de A-1
● Vários vetores de termos independentes
– Decomposição LU ou fatoração de Cholesky(
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)[b1,1b2,1⋮bn ,1]=[
1
0
⋮
0 ] (
a1,1 a1,2 ⋯ a1,n
a2,1 a2,2 ⋯ a2,n
⋮ ⋮ ⋱ ⋮
an ,1 an ,2 ⋯ an ,n
)[b1,2b2,2⋮bn ,2]=[
0
1
⋮
0 ]
(
a1,1 ⋯ a1,k ⋯ a1,n
⋮ ⋱ ⋮ ⋱ ⋮
a2,1 ⋯ ak ,k ⋯ ak ,n
⋮ ⋱ ⋮ ⋱ ⋮
an ,1 ⋯ ak ,2 ⋯ an ,n
)[ b1, k⋮b2, k⋮
bn ,k
]=[0⋮1⋮0 ]
 
Métodos iterativos
● Generalização do método do ponto fixo
● Método do ponto fixo → uma equação
– f(x) = 0 → x = φ(x)
● Gauss-Jacobi e Gauss-Seidel → várias equações
– Ax = b → Ax – b = 0 → x = φ(x) = C x + g
● C é matriz e g é vetor
● Função de iteração matricial
– Dado x(0)
● x(1) = φ(x(0)) = C x(0) + g
● x(2) = φ(x(1)) = C x(1) + g
● …
● x(k+1) = φ(x(k)) = C x(k) + g
 
Métodos iterativos
● Testes de parada
● Uma equação → um valor
– Intervalo → |x(k) – x(k-1)| ≤ ε
– Valor → |f(x(k))| ≤ ε
● Um sistema de equações → vários valores
– Intervalo → valor a valor
● Calculamos a distância em cada elemento → di(k) = |xi(k) – xi(k-1)|
● Calculamos a distância máxima → d(k) = max1≤i≤n di(k)
– Ou relativamente → dr(k) = d(k) / max1≤i≤n |xi(k)|
● Comparamos com a tolerância → d(k) ≤ ε
– Valor
● Calculamos b* = Ax(k)
● Calculamos a diferença → r = b* – b
● Calculamos o valor máxima → d(k) = max1≤i≤n |ri|
● Comparamos com a tolerância → d(k) ≤ ε
 
Gauss-Jacobi
● Sistema original
● Suponha ai,i ≠ 0
● Se não for
– Troca de linhas
● Isolamento de xi
– Pela diagonal
{a1,1 x1+a1,2 x2+…+a1,n xn=b1a2,1 x1+a2,2 x2+…+a2,n xn=b2⋮an ,1 x1+an ,2 x2+…+an ,n xn=bn
 
Gauss-Jacobi
● Sistema modificado
{
x1=
b1−(a1,2 x2+…+a1,n xn)
a1,1
x2=
b2−(a2,1 x1+a2,3 x3+…+a2,n xn)
a2,2
⋮
xi=
bi−(ai ,1 x1+…+ai , i−1 xi−1+ai , i+1 xi+1+…+ai , n xn)
ai , i
⋮
xn=
bn−(an ,1 x1+…+an ,n−1 xn−1)
an ,n
 
Gauss-Jacobi
● Sistema modificado
x=Cx+g
(
x1
x2
⋮
xi
⋮
xn
)=[
0
−a1,2
a1,1
⋯
−a1,i
a1,1
⋯
−a1,n
a1,1
−a2,1
a2,2
0 ⋯
−a2,i
a2,2
⋯
−a2,n
a2,2
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
ai ,1
ai , i
−ai ,2
ai , i
⋯ 0 ⋯
−ai , n
ai , i
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
an ,1
an ,n
−an ,2
an ,n
⋯
an , i
an ,n
⋯ 0
]( x1x2⋮xi⋮xn)+(
b1
a1,1
b2
a2,2
⋮
bi
ai , i
⋮
bn
an
, n
)
 
Gauss-Jacobi
● Sistema modificado iterativo
x(k+1)=Cx(k)+g
(
x1
(k+1)
x2
(k+1)
⋮
xi
(k+1)
⋮
xn
(k+1)
)=[
0
−a1,2
a1,1
⋯
−a1, i
a1,1
⋯
−a1,n
a1,1
−a2,1
a2,2
0 ⋯
−a2, i
a2,2
⋯
−a2,n
a2,2
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
ai ,1
ai , i
−ai ,2
ai , i
⋯ 0 ⋯
−ai , n
ai , i
⋮ ⋮ ⋱ ⋮ ⋱ ⋮
an ,1
an ,n
−an ,2
an ,n
⋯
an ,i
an ,n
⋯ 0
](x1(k )x2(k )⋮x i(k )⋮xn(k ))+(
b1
a1,1
b2
a2,2
⋮
bi
ai , i
⋮
bn
an
, n
)
 
Gauss-Jacobi
● Exemplo
{ 10 x1+2 x2+x3=7x1+5 x2+x3=−82 x1+3 x2+10 x3=6 C=[ 0
−2
10
−1
10
−1
5
0 −1
5
−2
10
−3
10
0 ] g=(
7
10
−8
5
6
10
)x(0)=(000) ,ε=0,05
x(1)=[ 0 −0,2 −0,1−0,2 0 −0,2−0,2 −0,3 0 ](
0
0
0)+(
0,7
−1,6
0,6 )=(
0
0
0)+(
0,7
−1,6
0,6 )=(
0,7
−1,6
0,6 )
( |0,7−0||−1,6−0||0,6−0| )=(
0,7
1,6
0,6) → { d
(1)=1,6>0,05
dr
(1)=1,6
1,6
=1>0,05
 
Gauss-Jacobi
● Exemplo
x(1)=( 0,7−1,60,6 )
x(2)=[ 0 −0,2 −0,1−0,2 0 −0,2−0,2 −0,3 0 ](
0,7
−1,6
0,6 )+(
0,7
−1,6
0,6 )=(
0,26
−0,26
0,34 )+(
0,7
−1,6
0,6 )=(
0,96
−1,86
0,94 )
( |0,96−0,7||−1,86−−1,6||0,94−0,6| )=(
0,26
0,26
0,34) → { d
(2)=0,34>0,05
dr
(2)=0,34
1,86
=0,1828>0,05
 
Gauss-Jacobi
● Exemplo
x(2)=( 0,96−1,860,94 )
x(3)=[ 0 −0,2 −0,1−0,2 0 −0,2−0,2 −0,3 0 ](
0,96
−1,86
0,94 )+(
0,7
−1,6
0,6 )=(
0,278
−0,38
0,366 )+(
0,7
−1,6
0,6 )=(
0,978
−1,98
0,966 )
( |0,978−0,96||−1,98−−1,86||0,966−0,94| )=(
0,018
0,12
0,026) → { d
(3)=0,12>0,05
dr
(3)=0,12
1,98
=0,0606>0,05
 
Gauss-Jacobi
● Exemplo
x(3)=(0,978−1,980,966 )
x(4)=[ 0 −0,2 −0,1−0,2 0 −0,2−0,2 −0,3 0 ](
0,978
−1,98
0,966 )+(
0,7
−1,6
0,6 )=(
0,2994
−0,3888
0,3984 )+(
0,7
−1,6
0,6 )=(
0,9994
−1,9888
0,9984 )
( |0,9994−0,978||−1,9888−−1,98||0,9984−0,966| )=(
0,0214
0,0088
0,0324) → { d
(4)=0,0324<0,05
dr
(4)=0,0324
1,9888
=0,0163<0,05
 
Gauss-Jacobi
● Convergência
● Conforme k cresce, x(k) tende à solução?
– O método converge?
● A convergência depende de x(0)?
– O método só converge para determinados chutes 
iniciais?
x(3)=(0,978−1,980,966 ) x(4)=(
0,9994
−1,9888
0,9984 )x(2)=(
0,96
−1,86
0,94 )x(1)=(
0,7
−1,6
0,6 )x(0)=(
0
0
0)
 
Gauss-Jacobi
● Convergência
● Critério das linhas
– Sejam e . Se α < 1, então 
o método de Gauss-Jacobi gera uma sequência {x(k)} 
convergente para a solução do sistema dado, 
independentemente da escolha da aproximação 
inicial x(0).
– Em outras palavras
● Pegue a matriz com os elementos em módulo
● Se o elemento da diagonal principal for maior que a soma 
dos outros elementos da linha, o método converge
αk=
∑
j=1, j≠k
n
|ak , j|
|ak ,k|
α=max1≤k≤nak
 
Gauss-Jacobi
● Convergência
● Observação
– Se um sistema linear não satisfizer ao critério das 
linhas
● Pode convergir
● Pode não convergir → Podemos tentar uma troca de linhas
{ x1+ x2=3x1−3 x2=−3 x∗=(1,51,5)
{ x1+3 x2+x3=−25 x1+2 x2+2 x3=36 x2+8 x3=−6 → {
5 x1+2 x2+2 x3=3
x1+3 x2+x3=−2
6 x2+8 x3=−6
 
Gauss-Seidel
● Gauss-Jacobi
● Próxima aproximação depende da atual
{
x1
(k+1)=
b1−(a1,2 x2
(k )+…+a1,n xn
(k ))
a1,1
x2
(k+1)=
b2−(a2,1 x1
(k )+a2,3 x3
(k)+…+a2,n xn
(k ))
a2,2
⋮
xi
(k+1)=
bi−(ai ,1 x1
(k )+…+ai , i−1 xi−1
(k ) +ai , i+1 xi+1
(k) +…+ai ,n xn
(k ))
ai , i
⋮
xn
(k+1)=
bn−(an ,1 x1
(k )+…+an ,n−1 xn−1
(k ) )
an ,n
 
Gauss-Seidel
● Próxima aproximação depende dela mesma
● Em xi(k+1), já descobrimos x1(k+1), …, xi-1(k+1)
{
x1
(k+1)=
b1−(a1,2 x2
(k )+…+a1,n xn
(k ))
a1,1
x2
(k+1)=
b2−(a2,1 x1
(k+1)+a2,3 x3
(k )+…+a2,n xn
(k))
a2,2
⋮
xi
(k+1)=
bi−(ai ,1 x1
(k+1)+…+ai , i−1 xi−1
(k+1)+ai , i+1 x i+1
(k ) +…+ai ,n xn
(k ))
ai , i
⋮
xn
(k+1)=
bn−(an ,1 x1
(k+1)+…+an ,n−1 xn−1
(k+1))
an , n
 
Gauss-Seidel
● Exemplo
{ 10 x1+2 x2+x3=7x1+5 x2+x3=−82 x1+3 x2+10 x3=6 x(0)=(
0
0
0) ,ε=0,05
x1
(1)=
7−(2∗0+1∗0)
10
=0,7
x2
(1)=
−8−(1∗0,7+1∗0)
5
=−1,74
x3
(1)=
6−(2∗0,7+3∗−1,74)
10
=0,982
( |0,7−0||−1,74−0||0,982−0|)=(
0,7
1,74
0,982) → { d
(1)=1,74>0,05
dr
(1)=1,74
1,74
=1>0,05
x(4)=( 0,9994−1,98880,9984 )
 
Gauss-Seidel
● Exemplo
{ 10 x1+2 x2+x3=7x1+5 x2+x3=−82 x1+3 x2+10 x3=6 x(1)=(
0,7
−1,74
0,982 ),ε=0,05
x1
(2)=
7−(2∗−1,74+1∗0,982)
10
=0,9498
x2
(2)=
−8−(1∗0,9498+1∗0,982)
5
=−1,9864
x3
(2)=
6−(2∗0,9498+3∗−1,9864)
10
=1,006
( |0,9498−0,7||−1,9864−−1,74||1,006−0,982| )=(
0,2498
0,2464
0,024 ) → { d
(1)=0,2498>0,05
d r
(1)=0,2498
1,9864
=0,1258>0,05
x(4)=( 0,9994−1,98880,9984 )
 
Gauss-Seidel
● Exemplo
{ 10 x1+2 x2+x3=7x1+5 x2+x3=−82 x1+3 x2+10 x3=6 x(2)=(
0,9498
−1,9864
1,006 ),ε=0,05
x1
(3)=
7−(2∗−1,9864+1∗1,006)
10
=0,9967
x2
(3)=
−8−(1∗0,9967+1∗1,006)
5
=−2,0005
x3
(3)=
6−(2∗0,9967+3∗−2,0005)
10
=1,0008
( |0,9967−0,9498||−2,0005−−1,9864||1,0008−1,006| )=(
0,0469
0,0141
0,0052) → { d
(1)=0,0469<0,05
dr
(1)=0,0469
2,0005
=0,0234<0,05
x(4)=( 0,9994−1,98880,9984 )
 
Métodos iterativos
● Interpretação geométrica
● Gauss-Jacobi
● Gauss-Seidel
{ x1+ x2=3x1−3 x2=−3 → {x1=3−x2x2=3+x13
{x1
(k+1)=3−x2
(k )
x2
(k+1)=
3+x1
(k)
3
{ x1
(k+1)=3−x2
(k )
x2
(k+1)=
3+x1
(k+1)
3
 
Métodos iterativos
● Interpretação geométrica
● Gauss-Jacobix(0)=(00) x(1)=(31) x(2)=(22) x(3)=( 15 /3) x(4)=(4 /34 /3)
 
Métodos iterativos
● Interpretação geométrica
● Gauss-Seidel
x(0)=(00) x(0,5)=(30) x(1)=(32) x(1,5)=(12) x(2)=( 14 /3) x(2,5)=(5 /34 /3) x(3)=( 5 /314 /9)
 
Métodos iterativos
● Interpretação geométrica
● Gauss-Seidel
x(0)=(00) x(0,5)=(−30 ) x(1)=(−36 ) x(1,5)=(156 ) x(2)=( 15−12)
{ x1+ x2=3x1−3 x2=−3→{x1−3 x2=−3x1+x2=3 →{x1
(k+1)=−3+3 x2
(k )
x2
(k+1)=3−x1
(k+1)
 
Gauss-Seidel
● Convergência
● Critério de Sassenfeld
– Mais geral que o critério das linhas
● Critério das linhas implica o critério de Sassenfeld
– Sejam
– Se β < 1, Gauss-Seidel converge para qualquer x(0)
β1=
|a1,2|+|a1,3|+…+|a1,n|
|a1,1|
=
∑
j=2
n
|a1, j|
|a1,1|
βi=
|ai ,1|β1+…+|ai , i−1|βi−1+|ai , i+1|…+|ai ,n|
|ai , i|
=
∑
j=1
i−1
|ai , j|β j+∑
j=i+1
n
|ai , j|
|ai , i|
β=max1≤i≤nβi
 
Comparação entre os métodos
● Convergência
● Métodos diretos
– Convergem se a solução existir
● Métodos indiretos
– Podem divergir, dependem de outras condições
● Critérios das linhas e de Sassenfeld
 
Comparação entre os métodos
● Esparsidade
● Matrizes esparsas
– Têm muitos zeros
● Métodos diretos
– Eliminação de Gauss
● Tendem a introduzir valores diferentes de zero na matriz
● Métodos indiretos
– Muitas multiplicações por zero
● Facilitam os cálculos
 
Comparação entre os métodos
● Erros de arredondamento
● Métodos diretos
– Podem apresentar erros grandes
● Resolvidos com pivoteamento
● Métodos indiretos
– Se a convergência for garantida
● Erros pequenos
 
Exercícios
● (5.5) Resolva o sistema linear abaixo usando o 
método da Eliminação de Gauss
2x1 + 2x2 + x3 + x4 = 7
x1 - x2 + 2x3 - x4 = 1
3x1 + 2x2 - 3x3 - 2x4 = 4
4x1 + 3x2 + 2x3 + x4 = 12
● (5.7) O cálculo do determinante de matrizes 
quadradas pode ser feito usando o método da 
Eliminação de Gauss
● (a) Deduza o método
● (b) Aplique-o no cálculo do determinante da matriz do 
sistema do Exercício 5.5
 
Exercícios
● (5.10) Calcule a fatoração LU da matriz abaixo, se 
possível
1 1 1
2 1 -1
3 2 0
● (5.11)
● (d) Encontre a inversa da matriz abaixo, usando 4 
casas decimais
4 -1 0 -1 0 0
-1 4 -1 0 -1 0
0 -1 4 0 0 -1
-1 0 0 4 -1 0
0 -1 0 -1 4 -1
0 0 -1 0 -1 4
 
Exercícios
● (5.23)
● (a) Usando o critério de Sassenfeld, verifique 
para quais valores positivos de k se tem 
garantia que o método de Gauss-Seidel vai 
gerar uma sequência convergente para a 
solução do sistema
k x1 + 3x2 + x3 = 1
k x1 + 6x2 + x3 = 2
x1 + 6x2 +7x3 = 3
● (b) Escolha o menor valor inteiro e positivo para 
k e faça duas iterações do método de Gauss-
Seidel para o sistema obtido
 
Exercícios
● (5.25)
● (a) Aplique analítica e graficamente os métodos 
de Gauss-Jacobi e de Gauss-Seidel no sistema
2 x1 + 5x2 = -3
3 x1 + x2 = 2
● (b) Repita o item (a) para o sistema obtido 
permutando as equações
● (c) Analise os resultados
 
Exercícios
● (5.33) Resolva os sistemas lineares abaixo 
usando a fatoração de Cholesky
● (a)
16x1 + 4x2 + 8x3 + 4x4 = 32
4x1 + 10x2 + 8x3 + 4x4 = 26
8x1 + 8x2 + 12x3 + 10x4 = 38
4x1 + 4x2 + 10x3 + 12x4 = 30
● (b)
20x1 + 7x2 + 9x3 = 16
7x1 + 30x2 + 8x3 = 38
9x1 + 8x2 + 30x3 = 38
 
● (5.5) x* = (1 2 1 0)T
● (5.7)
● (a) Propriedades
● Troca de linhas → determinante troca de sinal
● Multiplicação de linha por constante → determinante fica multiplicado pela 
constante
● Adição de múltiplo de outra linha a linha → determinante não se altera
– Método
● Transforme em matriz triangular U
● Calcule o determinante de U multiplicando os elementos da diagonal 
principal
● Divida o determinante calculado pelos multiplicadores de linhas (2a 
propriedade)
● Se o número de trocas de linhas for ímpar, então troque o sinal do 
determinante calculado
● (b) 3
Respostas
 
● (5.10) A matriz não possui inversa
1 0 0 1 1 1
2 1 0 0 -1 -3
3 -1 1 0 0 0
● (5.11)
0,2948 0,0932 0,0282 0,0861 0,0497 0,0195
0,0932 0,3230 0,0932 0,0497 0,1056 0,0497
0,0282 0,0932 0,2948 0,0195 0,0497 0,0861
0,0861 0,0497 0,0195 0,2948 0,0932 0,0282
0,0497 0,1056 0,0497 0,0932 0,3230 0,0932
0,0195 0,0497 0,0861 0,0282 0,0932 0,2948
Respostas
 
● (5.23)
● (a) |k| > 4
● (b) k = 5
x(0) = (0 0 0)T, x(2) = (0,04857 0,25 0,20734)T
● (5.25)
● (a) As sequências geradas por Gauss-Jacobi e por Gauss-
Seidel não convergem
● (b) Permutando as equações, as sequências convergem 
para x* = (1 -1)T
● (5.33)
● (a) x* = (1 1 1 1)T
● (b) x* = (0 1 1)T
Respostas
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86
	Slide 87
	Slide 88
	Slide 89
	Slide 90
	Slide 91
	Slide 92
	Slide 93
	Slide 94
	Slide 95
	Slide 96
	Slide 97
	Slide 98
	Slide 99
	Slide 100
	Slide 101
	Slide 102
	Slide 103
	Slide 104
	Slide 105
	Slide 106
	Slide 107
	Slide 108
	Slide 109
	Slide 110
	Slide 111
	Slide 112
	Slide 113
	Slide 114
	Slide 115
	Slide 116
	Slide 117
	Slide 118
	Slide 119
	Slide 120
	Slide 121
	Slide 122
	Slide 123
	Slide 124
	Slide 125
	Slide 126
	Slide 127
	Slide 128
	Slide 129
	Slide 130