Resolução de Sistemas Não-Lineares- Parte 1

Sistemas não-lineares

Normalmente, em problemas aplicados temos que resolver sistemas de equações

não-lineares de ordem n

nn

• Dada• Queremos achar solução para .

• Ou procuramos a solução do sistema não-linear

Tnnn fffFRRDF ,...,,,: 21

Sistemas não-lineares

1 1 2 3

1 1 2 3

1 2 3

, , ,..., 0

, , ,..., 0

, , ,..., 0

n

n

n n

f x x x x

f x x x x

f x x x x

( ) 0F x

EXEMPLO DE SISTEMAS

NÃO-LINEARES nxn

Exemplo1: Intersecção de círculo com hipérbole.

Temos 4 soluções: Os pontos de

intersecção da figura acima.

2 21 1 2 1 2

22 2

1 1 2 1

, 2 0

, 1 09

f x x x x

xf x x x

1x

2x

EXEMPLO DE SISTEMAS

NÃO-LINEARES nxn

Exemplo2: Intersecção de duas parábolas.

Não temos soluções pois as parábolas

não se intersectam.

21 1 2 1 2

21 1 2 2 1

, 0.2 0

, 1 0

f x x x x

f x x x x

1x

2x

2.0

1

SISTEMAS NÃO-LINEARES nxn

HIPÓTESES

Seja onde

é um aberto de . Em , suponha que

tenha derivadas contínuas e que exista pelo

menos um tal que .

Tnnn fffFRRDF ,...,,,: 21 D

nn x

x

x

x

xf

xf

xf

xF....

com

)(

........

)(

)(

)( 2

1

2

1

Dx 0xF

n D

SISTEMAS NÃO-LINEARES nxn

HIPÓTESESSeja o vetor gradiente de dado

por

e a matriz Jacobiana de :

1 2, ,...,i nf x x xT

n

iiii x

xf

x

xf

x

xfxf

)(,,.........

)(,

)()(

21

)(xF)(xJ

1 1 1

1 21

2 2 2

21 2

1 2

( ) ( ) ( )

( )( ) ( ) ( )

( )( )

................

( ) ( ) ( ) ( )

Tn

T

n

T

n n n n

n

f x f x f x

x x xf xf x f x f x

f xx x xJ x

f x f x f x f x

x x x

SISTEMAS NÃO-LINEARES nxnEXEMPLOS

• Exemplo 3: Para o sistema não linear

• A matriz jacobiana correspondente será:

3 21 1 2

2 31 2 2

3 1 0

3 0

x x x

x x x

2 21 2 1 2

2 21 2 1 2

3 3 6( )

6 3 3

x x x xJ x

x x x x

SISTEMAS NÃO-LINEARES nxnEXMPLOS

• Exemplo 4: (Tridiagonal de Broyden)

• E a matriz jacobiana correspondente é:

21 1 1 2

21 1

21

( ) 2 3 2 1

( ) ( ) 2 3 2 1 2 2

( ) 2 3

i i i i i

n n n n

f x x x x

F x f x x x x x i n

f x x x x

1

2

4 3 2 0 0 0

1 4 3 2 0 0( )

0 0 0 1 4 3n

x

xJ x

x

SISTEMAS NÃO-LINEARES nxnCritério de parada

• Temos métodos iterativos que com se

converge teremos a solução

• Como critério de parada verificamos se

onde é norma de vetor.

• Em testes computacionais usa-se a norma infinito, .

• Outro critério é

(0)x( ) *lim k

xx x ( )kx

( )( )kF x .

1Para , máxn

ii n

v v v

( 1) ( )k kx x

SISTEMAS NÃO-LINEARES nxn

MÉTODO DE NEWTON

O Método de Newton é método básico. Consiste na linearização local do sistema não-linear Seja a aproximação . Para qualquer

existe , tal que:

Aproximando, temos um modelo local linear

Dx k )(

nixxcfxfxf kTii

kii ,..,2,1para)(

DxDci

nixxxfxfxf kTki

kii ,..,2,1para)()(

kkkk xxxJxFxLxF )()()(

SISTEMAS NÃO-LINEARES nxnMÉTODO DE NEWTON

O modelo local linear do sistema não-linear é

Seja , então

Passo 1: Dado , calcule e .

Passo 2: Resolve-se o sistema linear .

Neste ponto técnicas de fatoração, pivoteamento e métodos

iterativos podem ser utilizadas para determinar .

O Método de Newton com resolução do sistema linear de

modo iterativo é chamado de Método de Newton Inexato.

)()()()( 0)( kkkkkkk xFxxxJxxxJxFxL

kkkkk sxxsxx 1

)()( kkk xFsxJ

kx )(kxJ

ks

kk sxx

)(kxF

SISTEMAS NÃO-LINEARES nxn

Comentário 1: Estudaremos os métodos para sistemas não-lineares são iterativos. Dado inicial, gera-se uma seqüência , de modo que

Comentário 2: Critérios de parada

a) norma dos vetores de .

b) norma infinito.

c) tolerância ou número máximo de iterações. Por exemplo.

kxF

)0(x )(kx

xxLim k

k

)(

F

ki

ki

kk xxxx 11 max

2010

kxF

SISTEMAS NÃO-LINEARES nxn

MÉTODO DE NEWTON INEXATOAlgoritmo. Dados , , , faça:

Passo1: Calcule e .

Passo 2: Se , faça e pare. Senão,

Passo 3: Obtenha , solução de

Passo 4: Faça

Passo 5: Se faça e pare. Senão

Passo 6: Faça e volte ao passo 1.

kk xFsxJ )(

kxx 1)( kxF

0x

)(kxJ

ks

01 02

)(kxF

kkk sxx 1

2

1 kk xx 1 kxx

1kk

MÉTODO DE NEWTON – Exemplo

Exemplo 5: Resolva o sistema

Sabemos que as soluções são

Tomamos , e calculando o

Jacobiano, obtemos .

09

3)(

22

21

21

xx

xxxF

.3

0e

0

3

xx

421 10

5

10x

21 22

11)(

xxxJ

MÉTODO DE NEWTON – Exemplo

Iteração 1:

continue!

métodos diretos ou iterativos

e

continue!!!!!!

17

3

5

1)( 0 FxF

41017kxF

0k

102

11

5

1)( 0 JxJ

17

3

102

110

2

01

s

s

01

02

13 / 8

11/ 8

s

s

8/29

8/5

8/11

8/13

5

1001 sxx

401 10625.18/13xx

MÉTODO DE NEWTON – Exemplo

Passo 1:

Comentário: Note que no processo de resolução de sistemas não-lineares, devemos resolver um sistemalinear a cada iteração.

Métodos diretos: Eliminação de Gauss com pivoteamento parcial ou total, fatoração LU ou Cholesky.....

Métodos iterativos: Método de Gauss-Jacobi o Gauss-Seidel

0k

MÉTODO DE NEWTON – Exemplo

CONTINUANDO. Iteração 2:

continue

e

continue!!!!!!

32/145

0

8/29

8/5)( 1 FxF

4105313.432/145kxF

1k

4/294/5

11

8/29

8/5)( 1 JxJ

32/145

0

4/294/5

111

2

11

s

s

533.0

533.01

2

11

s

s

0917.3

092.0

533.0

533.0

625.3

625.0112 sxx

412 10533.0xx

MÉTODO DE NEWTON – Exemplo

1-Continuar o processo até que um dos dois critérios de

parada seja atingido, ou seja

ou

2-Convergência do Método de Newton Inexato é

Quadrática em condições adequadas.

3-Diferentes abordagens do Método de Newton Inexato

geram algoritmos alternativos.

kxF

kk xx 1

MÉTODO DE NEWTON MODIFICADO

O Método de Newton Modificado consiste em

tomar a cada iteração, sempre, , em vez

de . O método iterativo é dado pela

seqüência .

Neste procedimento temos que resolver no

passo o sistema linear:

0xJ

kxJ kkk sxx 1

k kxFsxJ )0(

MÉTODO DE NEWTON MODIFICADO

O Método de Newton Modificado tem a vantagem de calcular uma única vez a matriz Jacobiana .

No caso de resolver por fatoração LU, os fatores L e U também serão calculados uma única vez.

0xJ

MÉTODO DE NEWTON MODIFICADO– EXEMPLO

Exemplo 6: Resolva o sistema .

Sabemos que as soluções são

Tomamos , e calculando o

Jacobiano, obtemos . Fixado!!!!

09

3)(

22

21

21

xx

xxxF

.3

0e

0

3

xx

421 10

5

10x

21 22

11)(

xxxJ

MÉTODO DE NEWTON MODIFICADO

Iteração 1:

continue!

métodos diretos ou iterativos

e

continue!!!!!!

17

3

5

1)( 0 FxF

41017kxF

0k

102

11

5

1)( 0 JxJ

17

3

102

110

2

01

s

s

01

02

13 / 8

11/ 8

s

s

8/29

8/5

8/11

8/13

5

1001 sxx

401 10625.18/13xx

MÉTODO DE NEWTON MODIFICADO

Iteração 2:

continue

Diferença e

continue!!!!!!

32/145

0

8/29

8/5)( 1 FxF

4105313.432/145kxF

1k

102

11)( 0xJ

32/145

0

102

111

2

11

s

s

5664.0

5664.01

2

11

s

s

0586.3

0586.0

5664.0

5664.0

625.3

625.0112 sxx

412 105664.0xx

MÉTODO DE NEWTON

CONVERGÊNCIA

O Método de Newton Modificado, Inexato, perde a propriedade de convergência quadrática, apesar que neste exemplo, aparentemente, o nível de convergência foi semelhante.Verifica-se que o Método de Newton Modificado converge linearmente.

MÉTODOS DE QUASE-NEWTON

Os Métodos de Quase-Newton, Inexatos,

consistem em gerar seqüências , com

Boas propriedades de convergência, sem ter

que avaliar (calcular) a matriz Jacobiana a cada

iteração.

( ){ }kx

MÉTODOS DE QUASE-NEWTON

No Método de Newton Inexato a seqüência é

gerada por

onde é a solução do sistema linear

A idéia é impor condições sobre gerando

a) algum princípio de variação mínima.

b) preservar alguma estrutura (simetria, esparsidade,..) da matriz Jacobiana.

)()()()( 0)( kkkkkkk xFxxxBxxxJxFxL

ks

kk sxx

)(kx

)(kxB )(kxJ