View
10
Download
0
Category
Preview:
Citation preview
Introdução aos Métodos Numéricos
Instituto de Computação UFFDepartamento 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,
limi→∞
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 42 8 2 −2
−2 3 7 13 1 2 7
)
Decomposição aditiva
Um exemplo
A=(9 −1 3 42 8 2 −2
−2 3 7 13 1 2 7
) ;D=(9 0 0 00 8 0 00 0 7 00 0 0 7
) ;M=(0 −1 3 40 0 2 −20 0 0 10 0 0 0
); N=(0 0 0 02 0 0 0
−2 3 0 03 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é ndiag←aii
para j ←1até naij←−aij /diag
bi←bi /diagaii←0
Gauss-Jacobi
Laço de repetição do Método de Gauss-Jacobi
para l←1até nxl← xauxl
para k←1até niteracoespara i ←1até n
s←0para 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é nxl← xauxl
para k←1até niteracoespara i ←1até n
s←0para 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 −11 9 1 0
−1 2 10 00 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 /81/9 9 /9 1/9 0 /9
−1 /10 2/10 10 /10 0 /100 /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 01/10 −1 /5 0 00 −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 01 /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 temos sempre 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= (14
−35
)
Gauss-Jacobi – Um exemplo
x⃗1=(0 −1 /8 0 1 /8
−1/9 0 −1/9 01 /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−11/3
)=(0,9375−0,66−1
0,33)
x⃗0=(14
−35
)
Gauss-Jacobi – Um exemplo
x⃗2=(0 −1 /8 0 1 /8
−1/9 0 −1 /9 01 /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−11 /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,92700,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 01/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 /14401715 /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 01/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,01080,025340,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
−10
1/2)
Gauss-Jacobi – Um exemplo
De fato a solução exata do sistema é
e observem a sequência de vetores
x⃗= (1
−10
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
Recommended