Aula_6-Métodos numéricos(Newton)

8/15/2019 Aula_6-Métodos numéricos(Newton)

http://slidepdf.com/reader/full/aula6-metodos-numericosnewton 1/17

2- Resolução de SistemasNão-lineares.

2.1- Método de Newton.

2.2- Método da Iteração.

3.3- Método do Gradiente.

MÉTODOS NUMÉRICOS PARA EQUAÇÕES DIFERENCIAIS PARCIAIS



2- Sistemas Não Lineares de Equações

Considere um sistema não linear de n equações com n incógnitas.

Note que como caso particular podemos ter um sistemalinear de equações algébricas:

( , , , )

( , , , ) ou com e ( )

( , , , )

n

n

n nn n

f x x x f x

f x x x f x

f x f x x x

=

= = = = =

f(x) 0 f x

1 1 2 1 1

2 1 2 2 2

1 2

0

01

0

L

L

M MLLLLLLLL

L

11 1 12 2 1 1

2

1 1 2

2 1 2 1 1 22 2 2 2

1 1 2 21 2

( , , , )

( , , , ) ou

( ,

0

0

, , ) 0

n n

n n

n n nn n

n

n

n nn

a x a x a x b

a x a

f x x x

f x x x x a x b

a x a x f x b x x a x

+ + − =

+ + − =− =

==

+= + − =

Ax b 0

L

L

LLLLLLLLLLLLLLLL

L

LLL

L

L

L



2.1- Método de Newton

Considere um sistema não linear de n equações com n incógnitas.

Resolveremos este problema com aproximações sucessivas.Seja a aproximação k com sendo uma das

raízes de com erro . Logo .

Supondo que é continuamente diferenciável num domínioconvexo que contem e podemos expandir a função emsérie de potencia entorno do ponto e desprezamos as

potencias maiores que 1 (termos não lineares).

( , , , )

( , , , ) ou com e ( )

( , , , )

n

n

n nn n

f x x x f x

f x x x f x

f x f x x x

=

=

= = = =

f(x) 0 f x

1 1 2 1 1

2 1 2 2 2

1 2

0

01

0

L

L

M MLLLLLLLL

L

( , , , )k k k k

n x x x=x 1 2 L

x ( , , , )k k k k

n x x x∆ = ∆ ∆ ∆x 1 2 L k k

= + ∆x x x

( )k k + ∆ =f(x x ) 0 2

f(x)k

xxk

x




Linearização do sistema (2).

Devemos entender como sendo a matriz Jacobiana das

funções com respeito as variáveis .

1 1 11 1 2 1 2

1 2

2 2 22 1 2 1 2

1 2

1 2 1

1

1

2

( , , , )

( , , , )

( ,

( ) 0

( ) 0

( ) , , )

k k k k k k

n n

n

k k k k k k

n n

n

k k k k n nn nn

f f f f x x x x x x x x x

f f f f x x x x x x

x x x

f f

f x x x x

f

x

f

f

∂ ∂ ∂

≈ + ∆ + ∆ + + ∆∂ ∂ ∂

∂ ∂ ∂≈ + ∆ + ∆ + + ∆

∂ ∂ ∂

∂ ∂

≈ + ∆ +

=

∂

=

k k k

k k k

k

x x x

x x x

x

x

x

x

L L

L L

L

LLLLLLLLLLLLLLLLLLLLLLLLLLLL

2

20

k k nn

n

f

x x x x

=

∂

∆ + + ∆∂ ∂ k k

x xL

n x x x ,,, 21 L

) (3) ou'k k k k k ≈= + ∆ + ∆ =f(x ) f f(x f(x x ) (x ) x 0

n f f f ,,, 21 L

'f (x)




O sistema (3) é um sistema linear da forma:

'

n

n

n n n

n

f f f

x x x

f f f

x x x

f f f

x x x

∂ ∂ ∂ ∂ ∂ ∂

∂ ∂ ∂

∂ ∂ ∂= =

∂ ∂ ∂ ∂ ∂ ∂

f (x) W (x)

1 1 1

1 2

2 2 2

1 2

1 2

L

L

L L L L

L

( )

( ) ou

( )

k k k

k k k

k k k

k k

n

k k k k k

n

k k n n nn n

n

f f f f x

x x x

f f f f x x x x

f f f f x x x x

∂ ∂ ∂ ∆

∂ ∂ ∂

∂ ∂ ∂ ∆ + = + ∆ =∂ ∂ ∂

∂ ∂ ∂

∆ ∂ ∂ ∂

x x x

x x x

x x x

x

xf(x ) W (x ) x 0

x

1 1 1

1 11 2

2 2 22 2

1 2

1 2

0

L

L

L L L LM M

L





2.1.1- Existência de Raiz do Sistema e Convergência doMétodo de Newton

Teorema 1: Seja um sistema não linear de equações comcoeficientes reais, onde as funções são definidas e

continuas junto com suas derivadas parciais de primeira e

segunda ordem num domínio . Ou seja, .

Suponha e o fecho de sua vizinhança

serem pontos de , onde é am

-norma e as seguintescondições serem válidas:

1) A matriz Jacobiana em tem inversa e

x0

são os cofatores

do elemento, com max ,

det( )

n

ij ijm m i W ij j

A W W −

=

≤ = ∑W(x ) W(x )W(x )

0 1 00 0

11

com e

n n

f x

f x

f x

= = =

f(x) 0 f x

1 1

2 2

M M

Ω

f(x)

( )C ∈ Ωf(x)2

Ω

m

V = − ≤ ∆ ⊂ Ω(x ) x x x0 0

m

W(x) x0

)−W(x

0 1




2)

3)

4) as constantes e satisfazem a desigualdade

Então o Método de Newton

converge para esta escolha de aproximação inicial e*

*

lim é a solução do sistema tal que

.

p

p

m B

→∞= =

− ≤ ≤ ∆

x x f(x) 0

x x x0

02

0x

, B0 0

( ) com ( , , , ) e ,

ni

k j k

f C i j n V

x x=

∂≤ = ∈

∂ ∂

∑ x

x (x )

20

1

1 L

.nA B C = ≤0 0 02 1

,m

B− ∆≤ ≤

xW(x ) f(x )0 1 0

02

C

, , , , ... p p p p p+ −= − =x x W(x ) f(x )

1 1 0 1 2

Note que, sempre que sejam verificadastodas as hipóteses do teorema o métodode Newton converge para uma soluçãoque é raiz do sistema na vizinhança de .x0

*x




Note que, se e o sistema tem em umasolução segue que e as condições do

teorema são válidas para qualquer ponto suficientemente

perto de .Por outro lado, para que a condição 2) seja válida é importante

observar que fornece uma estimativa da diferença entre as

aproximações primeira e inicial. Desta forma podemos verificarrapidamente se esta desigualdade é verificada assim que a

primeira aproximação seja calculada:

Também, podem ser obtidos resultados de convergênciaanálogos aos anteriores para o caso em que a normaconsiderada é

=f(x) 0*

x

B0

( )C ∈ Ωf(x) 2Ω

* * e= ≠f(x ) 0 W(x ) 0

*

x

x0

) .m m

B− ∆

= − ≤ ≤ x

W(x ) f(x ) x x0 1 0 1 0

0

22

ou .l k




Definição de Taxa de Convergência para os Métodositerativos:

Dizemos que um método iterativo converge para a solução

com taxa de convergência de ordem se a seguintedesigualdade se verifica

onde não depende de .

*x

Q

específica

k

específica

k

c

**1xxxx −≤−

+

Q

k k >∀

k xc

−

−

−

−

=

−

+

específica

k

específica

k

específica

k

específica

k

*1

*

*

*1

ln

ln

xx

xx

xx

xx

ρ Taxa deConvergênciaComputacional



2.1.2- Unicidade da Solução do Método de Newton e Taxade Convergência e Estabilidade.

Teorema 2: Se as condições 1) a 4) do Teorema 1 sãoverificadas, então existirá no domínio uma

única solução do sistema .

Teorema 3: Se as condições 1) a 4) do Teorema 1 sãoverificadas, então a seguinte desigualdade se verifica para as

aproximações sucessivas

onde é a solução do sistema eFalta algum resultado que garanta a estabilidade daconvergência do Método de Newton quando varia a escolha daaproximação inicial!

=f(x) 0

*x *

=f(x ) 0

px

m B− ≤ ≤ ∆x x x

0

02

* ( ) ( ) p

p p

m B µ

−−

− ≤

x x1

2 1

0 0

1

2

.nA B C = ≤0 0 0

2 1



2.1.2- Unicidade da Solução do Método de Newton e Taxade Convergência e Estabilidade.

Teorema 4: Se as condições 1) a 4) do Teorema 1 sãoverificadas e onde , então o Método

de Newton converge para sua única solução do sistema

no domínio para qualquer escolha daaproximação inicial que pertença ao domínio

Note que se então para a aproximação inicialsempre há uma vizinhança e qualquer ponto desta vizinhançapode ser escolhido como aproximação inicial para que o Método

de Newton seja convergente para a solução procurada .

=f(x) 0*

x

x0

m B− ≤ ≤ ∆x x x0

02

nA B C = <0 0 02 1 B C µ

≤ ∆ x0

0

2

% .m

B µ

−− ≤x x

0 0 00

0

1

2

e B µ < ∆ <x0 02 1 x0

*x

%

%

*

0 0 0 0

0

*

0 0 *00

0

Suponha 2 2 com 1 fixe max( ,1/ ) logo pelo

teorema 1 e 4 o Método de Newton para qualquer aproximação inicial

1que verifique a condição será convergente para .2m

B qB q q

B

µ µ

µ

µ

< = ∆ > =

−− ≤

x

x

x x x



2.1.3- Exemplo 2 pag. 462 do Demidovich

Use o Método de Newton para encontrar a solução aproximadapositiva do sistema de equações:

começando com a aproximação inicial

Solução: Nosso sistema é( , , )

( , , )

( , , )

f x y z x y z

f x y z x y z

f x y z x y z

= + + − =

= + − =

= − + =

2 2 2

12 2

2

2 23

1 0

2 4 0

3 4 0

x y z

x y z

x y z

+ + =

+ − =

− + =

2 2 2

2 2

2 2

1

2 4 0

3 4 0

. . x y z= = =0 0 0 0 5

M é t o d o d e N e w t o n

k k k k

f f f

x y z

f f f

x y z

f f f

x y z

+ −= −

∂ ∂ ∂

∂ ∂ ∂ ∂ ∂ ∂

= ∂ ∂ ∂

∂ ∂ ∂

∂ ∂ ∂

x x W ( x ) f ( x )

W ( x )

1 1

1 1 1

2 2 2

3 3 3

Para executar cadaaproximação devemoscalcular em cada passo

, ek k k −f ( x ) W ( x ) W ( x ) 1



2.1.3- Exemplo 2 pag. 462 do Demidovich

Solução: Nosso sistema é ( , , )( , , )

( , , )

f x y z x y z f x y z x y z

f x y z x y z

= + + − == + − =

= − + =

2 2 2

1

2 22

2 23

1 02 4 0

3 4 0

. . x y z= = =0 0 0 0 5

0 0 0 2 2 2

1

0 0 0 2 2

2

0 0 2 2

3

0

0

( , , ) (0.5) (0.5) (0.25

( ) 1.2

0.5) 1 0.25

( , , ) 2(0.5) (0.5) 4(0.5) 1.25

( , , ) 3

5

1 (0.5) 4(. 0.500 ) (0.5) 1.00

f x y z

f x y z

f x y z

−

= −

= + + − = −

= = + − = −

= − + = − −

f x

1 0 1

0

1 00 0

0

1 1 1

0.875

0.500

0.375

2 2 2

4 2 4 logo e det( ) 40

6 4 2

e

2 1 4

3 4 1

15 5 51

14 2 6

40 11 7

1

x y z

x y

x z

−−

= − =

= − −

− − −

= − − −

= − = −

− −

−

W ( x )

W (x x) x W (x ) f(x

W (x) W (

)

x )



2.1.3- Exemplo 2 pag. 462 do DemidovichPara a iteração 2 devemos calcular

1 1 1 2 2 2

1

1 1 1 2 2

2

1 1 1 2 2

3

1

( , , ) (0.875) (0.500) (0.375) 1 0.15625

( , , ) 2(0.875) (0.500) 4(0.375) 0.281

0.15625

( ) 0.28125

0.4

25

( , , ) 3(0.875) 4(0.500) (037

.375) 05

00

.4375

f x y z

f x y z

f x y z

=

= + + − =

= = + − =

= − + =

f x

2

1

1 11 1 1

1

1.750 1 0.750

3.500 1 4

5.250 4 0.75015.25 3.75 4.75

123.625 2.6250 9.62

2 2 2

4 2 4 logo e det( ) 64.75

6 4 2

e564.75

19.25 12.25 1.75

x y z

x y

x z

− −

= − = −

= − −

− − −

= − − −

− −

−

=

−

W(x) WW(x )

W( x x W(xx )

(

)

x )

f(1

0.78981

0.49662

0.36993

=

x )

e assim sucessivamente,. . 0.007279

note que a medida que . . 0.014511

aumenta o número de

. . 0.021767iterações k

= = =

→

x f(x ) f(x )

f(x ) 0

3 3 2

078521 000001

049662 000004

036992 000005



2.1.3- Exemplo 2 pag. 462 do DemidovichVisualização gráfica do problema



Frase do Dia

“True Laws of Nature cannot be linear.”

Albert Einstein

Documents

Aula_6-Métodos numéricos(Newton)