Introdução aos Métodos Numéricosotton/graduacao/introducaonumericos/...Gauss-Jacobi Observe que -(M + N) é a matriz original A sem a diagonal e com sinal trocado D-1 é obtida

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


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




● Também teria um critério claro de quando convergiria

Métodos iterativos




● 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


Um exemplo

então

A=(9 −1 3 42 8 2 −2

−2 3 7 13 1 2 7

)


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


● 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


● 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


● Zere a diagonal da matriz resultante

Gauss-Jacobi


● 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)


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)


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)


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)


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)


Mas qual será o vetor inicial?

Métodos Iterativos


● Em problemas reais temos sempre uma dica se examinamos o problema como ele merece

Métodos Iterativos


● 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

)


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

)


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

)


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


Qual o significado da primeira componente ter se repetido?


Qual o significado da primeira componente ter se repetido?

Nenhum! Observe que as demais componentes mudaram consideravelmente

Estamos em busca de um vetor!


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...


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)


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


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)


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


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


De fato a solução exata do sistema é

x⃗= (1

−10

1/2)


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

Documents

Introdução aos Métodos Numéricosotton/graduacao/introducaonumericos/...Gauss-Jacobi Observe que -(M + N) é a matriz original A sem a diagonal e com sinal trocado D-1 é obtida