Prévia do material em texto

Introdução aos Métodos 
Numéricos
Instituto de Computação UFF
Departamento de Ciência da Computação
Otton Teixeira da Silveira Filho
 
Conteúdo específico
● Sistemas de Equações Lineares. Métodos Iterativos
 
Conteúdo temático
● Conceitos básicos
● Métodos Estacionários
● Decomposição aditiva de uma matriz
● Método de Gauss-Jacobi
 
Métodos iterativos
Dado o sistema
pretendemos elaborar um método de resolução que tenha a 
forma
 
x⃗ i+1=Φ ( x⃗i ) ; dado x⃗0
A x⃗=b⃗ ; det (A)≠0
 
Métodos iterativos
Suporemos também o teorema do ponto fixo neste caso, ou 
seja, 
 
lim
i→∞
x⃗i= x⃗⇒ x⃗=Φ( x⃗)
 
Métodos iterativos
Mas porque usar métodos iterativos?
 
Métodos iterativos
Mas porque usar métodos iterativos?
Assim como os métodos iterativos que já vimos:
● Um método deste tipo não teria a instabilidade numérica dos 
métodos diretos
 
Métodos iterativos
Mas porque usar métodos iterativos?
Assim como os métodos iterativos que já vimos:
● Um método deste tipo não teria a instabilidade numérica dos 
métodos diretos
● Também teria um critério claro de quando convergiria
 
Métodos iterativos
Mas porque usar métodos iterativos?
Assim como os métodos iterativos que já vimos:
● Um método deste tipo não teria a instabilidade numérica dos 
métodos diretos
● Também teria um critério claro de quando convergiria
● Não exigiria um procedimento posterior de verificação
 
Métodos iterativos
Trabalharemos aqui com os Métodos Iterativos Estacionários 
que têm a seguinte forma
onde B e c não dependem de i
x⃗ i+1=B x⃗ i+ c⃗
 
Métodos iterativos
Trabalharemos aqui com os Métodos Iterativos Estacionários 
que têm a seguinte forma
onde B e c não dependem de i
Observe que o algoritmo é uma multiplicação de matriz por 
vetor seguida de uma soma vetorial
x⃗ i+1=B x⃗ i+ c⃗
 
Métodos iterativos
Estes métodos que veremos são de implementação simples e 
são úteis em muitas situações
 
Decomposição aditiva
Decomposição aditiva de uma matriz
Seja A uma matriz quadrada. Escreveremos esta matriz como 
onde D é a diagonal de A, M a matriz triangular estritamente 
superior de A e N a matriz triangular estritamente inferior 
de A
A=D+M+N
 
Decomposição aditiva
Um exemplo
então
A=(
9 −1 3 4
2 8 2 −2
−2 3 7 1
3 1 2 7
)
 
Decomposição aditiva
Um exemplo
A=(
9 −1 3 4
2 8 2 −2
−2 3 7 1
3 1 2 7
) ;D=(
9 0 0 0
0 8 0 0
0 0 7 0
0 0 0 7
) ;M=(
0 −1 3 4
0 0 2 −2
0 0 0 1
0 0 0 0
); N=(
0 0 0 0
2 0 0 0
−2 3 0 0
3 1 2 0
)
 
Métodos iterativos
Métodos Iterativos Estacionários
Uma maneira de construir um método iterativo é partir das 
equações que pretendemos resolver e obter uma função de 
iteração de forma similar ao que fizemos no Método da Iteração 
Linear
 
Gauss-Jacobi
Partiremos do sistema original usando a decomposição aditiva 
que apresentamos, ou seja,
e reescrevendo como
A x⃗=b⃗⇒ ( D+M+N ) x⃗=b⃗
 
Gauss-Jacobi
Partiremos do sistema original usando a decomposição aditiva 
que apresentamos, ou seja,
e reescrevendo como
A x⃗=b⃗⇒ ( D+M+N ) x⃗=b⃗
D x⃗=−( M+N ) x⃗+b⃗
 
Gauss-Jacobi
Suporemos que a matriz associada ao sistema está arrumada 
de tal forma que a matriz D tenha inversa. Então podemos 
escrever
e isto será a base do método iterativo dado por 
x⃗=−D−1 ( M+N ) x⃗+D−1 b⃗
 
Gauss-Jacobi
 dado . 
A matriz
 é chamada de Matriz de Gauss-Jacobi
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
x⃗0
−D−1 ( M+N )
 
Gauss-Jacobi
 
Como já adiantamos, o algoritmo consiste em uma 
multiplicação de matriz por vetor seguido de uma soma vetorial
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
 
Gauss-Jacobi
 
Como já adiantamos, o algoritmo consiste em uma 
multiplicação de matriz por vetor seguido de uma soma vetorial
● Custo computacional por iteração: O(n2).
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
 
Gauss-Jacobi
Observe que
● -(M + N) é a matriz original A sem a diagonal e com sinal 
trocado 
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
 
Gauss-Jacobi
Observe que
● -(M + N) é a matriz original A sem a diagonal e com sinal 
trocado 
● D-1 é obtida calculando os recíprocos dos valores da diagonal
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
 
Gauss-Jacobi
Observe que
● -(M + N) é a matriz original A sem a diagonal e com sinal 
trocado
● D-1 é obtida calculando os recíprocos dos valores da diagonal
● Multiplicar por D-1 é equivalente a dividir cada linha de M + N e 
do vetor b pelo valor correspondente da diagonal de D
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
 
Gauss-Jacobi
Temos um algoritmo para montar a fórmula de Gauss-Jacobi!
 
 
Gauss-Jacobi
● Divida todo o sistema pelos valores correspondentes da 
diagonal da matriz A
 
 
Gauss-Jacobi
● Divida todo o sistema pelos valores correspondentes da 
diagonal da matriz A
● Zere a diagonal da matriz resultante
 
Gauss-Jacobi
● Divida todo o sistema pelos valores correspondentes da 
diagonal da matriz A
● Zere a diagonal da matriz resultante
● Troque o sinal dos valores da matriz
 
 
Gauss-Jacobi
Já que estamos falando de algoritmo vamos ver como seria o 
algoritmo em pseudocódigo
 
 
Gauss-Jacobi
“Arrumação“ da matriz
 para i←1até n
diag←aii
para j ←1até n
aij←−aij /diag
bi←bi /diag
aii←0
 
Gauss-Jacobi
Laço de repetição do Método de Gauss-Jacobi
 
para l←1até n
xl← xauxl
para k←1até niteracoes
para i ←1até n
s←0
para j ←1até n
s← s+aij x j
xauxi← s+bi
 
Gauss-Jacobi
Laço de repetição do Método de Gauss-Jacobi
 
 
 Vetor auxiliar para preservar os 
 valores do vetor na iteração
para l←1até n
xl← xauxl
para k←1até niteracoes
para i ←1até n
s←0
para j ←1até n
s← s+aij x j
xauxi← s+bi
 
Métodos Iterativos
Como verificaremos a evolução da sequência
 ?( x⃗0, x⃗1, x⃗2,⋯, x⃗ i , x⃗i+1 ,⋯)
 
Métodos Iterativos
Como verificaremos a evolução da sequência
 ?
Usaremos a norma da diferença dos vetores dividido pela 
norma de um dos vetores
( x⃗0, x⃗1, x⃗2,⋯, x⃗ i , x⃗i+1 ,⋯)
 
Métodos Iterativos
Algo assim
 ‖x⃗ i+1− x⃗i‖
‖x⃗ i‖
;i>0
 
Métodos Iterativos
Algo assim
 
Em nossos cálculos usaremos a norma do máximo
‖x⃗ i+1− x⃗i‖
‖x⃗ i‖
;i>0
 
Métodos Iterativos
No momento não nos preocuparemos com a questão da 
condição de convergência
 Vamos para um exercício...
 
Gauss-Jacobi – Um 
exemplo
 Partiremos para a construção do método
(
8 1 0 −1
1 9 1 0
−1 2 10 0
0 1 1 12
) x⃗=(
13 /2
−8
−3
5
)
 
Gauss-Jacobi – Um 
exemplo
Dividamos todo o sistema pelos valores da diagonal
 
(
8/8 1 /8 0 /8 −1 /8
1/9 9 /9 1/9 0 /9
−1 /10 2/10 10 /10 0 /10
0 /12 1/12 1/12 12/12
) ; (
(13/2)/8
−8/9
−3/10
5 /12
)
 
Gauss-Jacobi – Um 
exemplo
Zere a diagonal da matriz
 
(
0 1 /8 0 −1/8
1/9 0 1/9 0
−1 /10 1 /5 0 0
0 1 /12 1 /12 0
) ; (
13 /16
−8 /9
−3 /10
5/12
)
 
Gauss-Jacobi – Um 
exemplo
Troque o sinal dos valores da matriz
 
(
0 −1/8 0 1/8
−1 /9 0 −1/9 0
1/10 −1 /5 0 0
0 −1 /12 −1 /12 0
) ; (
13 /16
−8 /9
−3 /10
5 /12
)
 
Gauss-Jacobi – Um 
exemplo
Método de Gauss-Jacobi
 
x⃗ i+1=−D
−1 ( M+N ) x⃗ i+D
−1 b⃗
x⃗ i+1=(
0 −1 /8 0 1 /8
−1/9 0 −1 /9 0
1 /10 −1/5 0 0
0 −1/12 −1/12 0
) x⃗ i+ (
13 /16
−8 /9
−3 /10
5 /12
)
 
Gauss-Jacobi – Um 
exemplo
Mas qual será o vetor inicial?
 
Métodos Iterativos
Mas qual será o vetor inicial?
● Em problemas reais temos sempre uma dica se examinamos o 
problema como ele merece
 
Métodos Iterativos
Mas qual será o vetor inicial?
● Em problemas reais temossempre uma dica se examinamos o 
problema como ele merece
● Aqui escolheremos um vetor qualquer antecipando que, se o 
método converge, convergirá para qualquer vetor inicial
 
Métodos Iterativos
Usaremos
 
x⃗0= (
1
4
−3
5
)
 
Gauss-Jacobi – Um 
exemplo
 
x⃗1=(
0 −1 /8 0 1 /8
−1/9 0 −1/9 0
1 /10 −1 /5 0 0
0 −1/12 −1/12 0
) x⃗0+(
13 /16
−8 /9
−3 /10
5/12
)
x⃗1=(
[0×1−1/8×4+0×(−3)+1 /8×5]+13 /16
[−1/9×1+0×4−1 /9×(−3)+0×5]−8 /9
[1 /10×1−1 /5×4+0×(−3)+0×5]−3/10
[0×1−1 /12×4−1/12×(−3)+0×5]+5 /12
)=(
15 /16
−2/3
−1
1/3
)=(
0,9375
−0,66
−1
0,33
)
x⃗0=(
1
4
−3
5
)
 
Gauss-Jacobi – Um 
exemplo
 
x⃗2=(
0 −1 /8 0 1 /8
−1/9 0 −1 /9 0
1 /10 −1/5 0 0
0 −1/12 −1/12 0
) x⃗1+ (
13 /16
−8 /9
−3 /10
5 /12
)
x⃗2=(
[0×15 /16−1/8×(−2 /3)+0×(−1)+1/8×1/3]+13 /16
[−1/9×15 /16+0×(−2/3)−1/9×(−1)+0×1/3]−8 /9
[1/10×15 /16−1/5×(−2/3)+0×(−1)+0×1/3]−3 /10
[0×15 /16−1 /12×(−2 /3)−1/12×(−1)+0×1 /3 ]+5 /12
)=(
15 /16
−127 /144
−7 /96
5 /9
)=(
0,9375
−0,8819 44
−0,07291 66
0,55
)
x⃗1=(
15 /16
−2/3
−1
1 /3
)
 
Gauss-Jacobi – Um 
exemplo
Avaliemos a evolução dos vetores obtidos
 
x⃗2− x⃗1=(
0,9375
−0,8819 44
−0,07291 66
0,55
)− (
0,9375
−0,66
−1
0, 33
)≈ (
0
−0,2152
0,9270
0,2222
)⇒‖x⃗2− x⃗1‖max≈0,9270
‖x⃗1‖max=1⇒
‖x⃗2− x⃗1‖max
‖x⃗1‖max
≈0,9270
 
Gauss-Jacobi – Um 
exemplo
Qual o significado da primeira componente ter se repetido?
 
Gauss-Jacobi – Um 
exemplo
Qual o significado da primeira componente ter se repetido?
Nenhum! Observe que as demais componentes mudaram 
consideravelmente
Estamos em busca de um vetor!
 
Gauss-Jacobi – Um 
exemplo
Você já deve ter reparado que estamos apresentando cálculos 
desnecessários. Os valores da diagonal da matriz de Gauss-
Jacobi sempre serão nulos para qualquer sistema de equações 
lineares.
 Simplifiquemos um pouco... 
 
Gauss-Jacobi – Um 
exemplo
 
x⃗3=(
0 −1/8 0 1/8
−1 /9 0 −1/9 0
1/10 −1/5 0 0
0 −1/12 −1/12 0
) x⃗2+ (
13 /16
−8 /9
−3 /10
5 /12
)
x⃗3=(
[−1/8×(−127 /144)+0×(−7 /96)+1/8×5/9 ]+13 /16
[−1/9×15 /16−1/9×(−7 /96)+0×5 /9]−8 /9
[1/10×15 /16−1 /5×(−127 /144)+0×5/9]−3 /10
[0×15 /16−1 /12×(−127 /144 )−1/12×(−7 /96)]+5 /12
)=(
127/128
−851 /864
−43 /1440
1715 /3456
)=(
0,992188
−0,984953 44
−0,02986 22
0,496238
)
x⃗2=(
15 /16
−127 /144
−7 /96
5 /9
)
 
Gauss-Jacobi – Um 
exemplo
Avaliemos a evolução dos vetores
 
x⃗3− x⃗2=(
0,992188
−0,984953 44
−0,02986 22
0,496238
)− (
0,9375
−0,8819 44
−0,0729166
0,55
)≈ (
0,0546
−0,1030
0,0430
−0,0593
)⇒‖x⃗3− x⃗2‖max≈0,1030
‖x⃗2‖max=0,9375⇒
‖x⃗3− x⃗2‖max
‖x⃗2‖max
≈0,1098
 
Gauss-Jacobi – Um 
exemplo
 
x⃗4= (
0 −1/8 0 1/8
−1 /9 0 −1/9 0
1/10 −1/5 0 0
0 −1/12 −1/12 0
) x⃗3+ (
13 /16
−8/9
−3/10
5 /12
)
x⃗ 4=(
[−1 /8×(−0,984953)+0×(−0,029862)+1 /8×0,496238 ]+13 /16
[−1 /9×0,992188−1/9×(−0,029862)+0×0,496238 ]−8 /9
[1 /10×0,992188−1/5×(−0,984953)+0×0,496238 ]−3 /10
[0×0,992188−1 /12×(−0,984953)−1 /12×(−0,029862)]+5 /12
)=(
0,997648
−0,995814
−0,004514
0,501234
)
x⃗3=(
0,992188
−0,984953
−0,029862
0,496238
)
 
Gauss-Jacobi – Um 
exemplo
Avaliemos a evolução dos vetores
 
x⃗4− x⃗3=(
0,997648
−0,995814
−0,004514
0,501234
)−(
0,992188
−0,984953
−0,029862
0,496238
)≈ (
0,0054
−0,0108
0,02534
0,0049
)⇒‖x⃗4− x⃗3‖max≈0,02534
‖x⃗3‖max≈0,9921⇒
‖x⃗4− x⃗3‖max
‖x⃗3‖max
≈0,0255
 
Gauss-Jacobi – Um 
exemplo
Observe que os valores da avaliação se aproximam de zero a 
medida que fazemos mais e mais iterações. 
‖x⃗2− x⃗1‖max
‖x⃗1‖max
≈0,9270 ;
‖x⃗3− x⃗2‖max
‖x⃗2‖max
≈0,1098 ;
‖x⃗4− x⃗3‖max
‖x⃗3‖max
≈0,0255
 
Gauss-Jacobi – Um 
exemplo
De fato a solução exata do sistema é
 
x⃗= (
1
−1
0
1/2
)
 
Gauss-Jacobi – Um 
exemplo
De fato a solução exata do sistema é
e observem a sequência de vetores 
x⃗= (
1
−1
0
1/2
)
x⃗1=(
0,9375
−0,66
−1
0, 33
) x⃗2=(
0,9375
−0,8819 44
−0,07291 66
0,55
) x⃗3=(
0,9921 88
−0,984953 44
−0,02986 22
0,496238
) x⃗4=(
0,997648
−0,995814
−0,004514
0,501234
)
 
Gauss-Jacobi
Repare que a cada iteração, cada componente do vetor 
pode ser calculado independentemente. 
 Assim, este algoritmo é facilmente paralelizável, ou seja, é fácil 
implementá-lo num computador paralelo. 
 
x i+1
	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