Métodos para equações não-lineares

Metodo de Newton Metodos Quase-Newton Sistemas nao-lineares

Metodos para equacoesnao-lineares

Ricardo [email protected]

Calculo Numerico – UNICAMP

1S/2017

http://goo.gl/rYq41

http://goo.gl/rYq41 Ricardo Biloti Metodos para equacoes nao-lineares


Licenca

Este trabalho e licenciado sob os termos da Licenca InternacionalCreative Commons Atribuicao-NaoComercial-CompartilhaIgual 4.0.

Para ver uma copia desta licenca, visitehttp://creativecommons.org/licenses/by-nc-sa/4.0/.


Seus direitos e deveres sao:

• Voce e livre para copiar e redistribuir este material, em qualquer meio ou formato,para adapta-lo, transforma-lo ou utiliza-lo para construir seu proprio material.

• Voce deve dar os creditos apropriados, fornecendo link para a licenca e indicando sealteracoes foram feitas. Voce pode fazer isto de qualquer forma razoavel, porem semtentar passar a ideia ou sugerir que o autor endosse suas alteracoes ou seu uso domaterial.

• Voce nao pode utilizar este material para fins comerciais.

• Se voce alterar, transformar ou construir seu proprio material com base nestetrabalho, voce devera distribuı-lo sob a mesma licenca usada no original.


Exemplo

d

θ

y ′′(t) = −gy(0) = 0, y ′(0) = v0 sin θ

y(t) = (v0 sin θ)t − g

2t2


Suponha que um canhao dispara projeteis a uma velocidade v0. O objetivo e calibrar oangulo de tiro para que o projetil acerte um alvo a distancia d conhecida.

Apos o disparo, a unica forca agindo sobre o projetil e a forca da gravidade.


Exemplo

y(t) = (v0 sin θ)t − g

2t2

Impacto:

y(T ) = 0⇒ T =2v0 sin θ

g

Distancia percorrida:

(v0 cos θ)T = d

f (θ) ≡ 2v20 sin θ cos θ

g− d = 0


O momento do impacto pode ser encontrado resolvendo-se y(T ) = 0. Feito isso, sabendo-se que a distancia horizontal percorrida e (v0 cos θ)T , para calibrar o angulo de tiro bastaresolver a equacao nao-linear em θ, f (θ) = 0.


Exemplo

f (θ) ≡ 2v20 sin θ cos θ

g− d = 0

I Pode nao ter solucao (d > v20 /g)

I Pode nao haver unicidade

I Nem todas as solucoes fazem sentido

I f pode ser simplificada?

I f pode ser diferenciada?


Antes de tentar resolver uma equacao como esta, devemos pensar sobre algumas questoes:

• A equacao tem solucao? O que poderia acontecer com um metodo numerico paraaproximar a solucao de equacoes quando aplicado a uma equacao que nao tenhasolucao?

• Havendo solucao, sera que ela e unica? Como um metodo numerico se comportaria sea equacao que ele tenta resolver tivesse mais de uma solucao? Ele deveria encontrartodas? Ele encontraria alguma? Ele ficaria indeciso sobre qual solucao aproximar?

• Sera que todas as solucoes da equacao fazem sentido fısico? O metodo numerico temobrigacao de encontrar a solucao que eu quero? E possıvel guiar o metodo parabuscar uma solucao especıfica?

• Sera que nao tem como simplificar a equacao, antes de aplicar um metodo numerico?Isto pode fazer a diferenca entre o metodo ser bem sucedido ou nao, ou mesmo navelocidade com que a uma aproximacao e obtida.

• Por fim, como muito metodos (como veremos) utilizam informacao de derivada, epreciso saber se f pode ou nao ser diferenciada. Isso influencia a escolha do metodonumerico.


Existencia

Teorema de Bolzano

Seja f e contınua em [a, b]. Se f (a) · f (b) < 0, entao existex ∈ (a, b) tal que f (x) = 0.

ax b


Uma funcao contınua que troca de sinal nos extremos de um intervalo, tem que teratravessado o eixo das ordenadas. Essa e a essencia do Teorema de Bolzano. Esse e oprincipal resultado utilizado para garantir a existencia de um ponto onde a funcao se anula.Esse teorema e consequencia direta do Teorema do Valor Intermediario.

Mesmo que a funcao nao troque de sinal nos extremos de um intervalo, ainda pode haverpontos onde a funcao se anula. Observe o grafico e imagine que o intervalo de interesse,ao inves de ser [a, b] fosse [0, b]. A funcao e positiva tanto em 0 como em b, mas mesmoassim, se anula em dois pontos no interior deste intervalo.

A dificuldade em aplicar esse resultado e conseguir exibir um intervalo [a, b] onde f (a) e f (b)tem sinais opostos. Isso e feito principalmente por tentativa e erro.


Exemplo

f (x) = x3 − 6x + 3

f (−3) = −6, f (3) = 12


Como todo polinomio e contınuo e exibimos dois pontos, −3 e 3, onde o valor de f troca desinal, pelo Teorema de Bolzano, e possıvel garantir que ha pelo menos um zero de f nesseintervalo.


Unicidade

Teorema

Seja f e diferenciavel em [a, b]. Se f (a) · f (b) < 0 e f ′(x) naotroca de sinal em (a, b), entao existe um unico x ∈ (a, b) tal quef (x) = 0.

ax b


Enquanto que a existencia de zeros para funcoes contınuas e garantida examinando-se apenasos extremos de intervalos, a unicidade nao pode ser assegurada sem que todo o intervaloseja analisado.

Note que garantir que nao exista apenas um zero em um intervalo e o mesmo que pedir quea funcao corte o eixo das ordenadas uma unica vez. Uma maneira de garantir isso e pedirque a funcao seja estritamente crescente (se f (a) < 0 < f (b)) ou estritamente decrescente(se f (a) > 0 > f (b)). Dessa forma, apos cruzar o eixo uma vez nao haveria como cruza-lonovamente. Essa e a essencia do teorema apresentado.

Atencao: para dizer que uma funcao e estritamente crescente no intervalo (a, b) e precisoverificar se f ′(x) > 0 para todo x ∈ (a, b), e nao apenas nos pontos a e b. O mesmo valepara funcoes estritamente decrescentes.


Exemplo

f (x) = x3 − 6x + 3, f ′(x) = 3x2 − 6

f (−3) = −6, f (3) = 12

f ′(−3) > 0, f ′(0) < 0

Porem

f ′(x) > 0, se x >√

2, e f (1.5) < 0, f (3) > 0


No exemplo anterior, havıamos concluıdo que f tinha zeros no intervalo [−3, 3]. Entretantof ′ troca de sinal nesse intervalo. Logo, nao e possıvel assegura a unicidade da solucao daequacao f (x) = 0.

Porem e facil verificar que f ′(x) > 0 se x >√

2, isto e f e estritamente crescente depois de√2. Como f (1.5) < 0 < f (3), podemos assegurar que no intervalo (1.5, 3) ha apenas um

zero de f .


Exercıcio

Para a funcao abaixo, tente localizar seus zeros. Dentro de cadaintervalo que voce encontrou, e possıvel garantir que a funcao temapenas um zero?

f (x) = x2 −√

5x +1

4


A funcao f nao esta definda para x < 0. Observe que f (1) < 0 < f (2). Alem disso,

f ′(x) = 2x −5

2√

5xe nao e difıcil perceber que f ′(x) > 0 se x > 1. Logo, existe um unico

zero de f no intervalo (1, 2).


Metodo da bisseccao

a

b


No metodo da bisseccao, parte-se de um intervalo inicial [a, b] onde f (a) · f (b) < 0.Calcula-se entao o valor da funcao no ponto medio e com base nisso reduz-se o intervalo demaneira a ficar com o subintervalo da direita ou da esquerda onde ainda e possıvel observara alternancia de sinal da funcao.

Dessa forma, sucessivamente o intervalo de confinamento do zero da funcao e contraıdo.


Metodo da bisseccao

a

b



Metodo da bisseccao

a a

b



Metodo da bisseccao

a a

b



Metodo da bisseccao

a a

bb



Metodo da bisseccao

a a

bb



Metodo da bisseccao

a a a

bb



Metodo da bisseccao

a a a

bb



Metodo da bisseccao

a a a

bb



Caracterısticas

I [a, b]?

I Convergencia assegurada (dado [a, b])

I Convergencia lenta


A grande dificuldade para a aplicacao do metodo da bisseccao e a sua inicializacao, querequer a determinacao de um intervalo inicial [a, b] onde haja a alternancia de sinal novalores da funcao.

Uma vez iniciado, o metodo a bisseccao tem convergencia assegurada, porem a obtencaode uma aproximacao com a precisao desejada pode implicar numa grande quantidade deiteracoes. O grande problema disso e que, em algumas situacoes de interesse real, a avaliacaoda funcao f pode ser muito cara.


Aproximacao linear

xkxk+1 x

y

r(x) = f (xk) + f ′(xk)(x − xk)

r(xk+1) = 0 ⇒ xk+1 = xk −f (xk)

f ′(xK )


O metodo de Newton parte do fato de que encontrar o zero de uma reta e simples e umafuncao diferenciavel pode ser aproximada pela reta tangente, pelo menos proximo do pontode tangencia. Desta forma, se xk e uma aproximacao para o zero de f , no metodo de Newton,a funcao e aproximada pela reta tangente no ponto xk e depois e computado o zero da retatangente. Esse ponto e entao definido como a nova aproximacao para o zero da funcao,denotada por xk+1.


Metodo de Newton

I Seja x0 uma aproximacao razoavel de x∗

I Para k = 0, 1, 2, . . .

I Se f ′(xk) 6= 0, xk+1 = xk −f (xk)

f ′(xk)


Em linhas gerais, o algoritmo para o metodo de Newton e bem simples.

Parte-se de uma aproximacao inicial para o zero da funcao, denominada x0.

Depois, sucessivamente computam-se as aproximacoes seguintes pela formula de iteracao,desde que em nenhum dos iterandos a derivada seja nula.


Exemplo: aproximando√

3

xk+1 = xk −f (xk)

f ′(xk)

f (x) = x2 − 3, f ′(x) = 2x

xk+1 = xk −x2k − 3

2xk=

1

2

(xk +

3

xk

)

x0 = 2, f (x0) = 1

x1 = x0 −x2

0 − 3

2x0= 1.7500, f (x1) = 0.0625

x2 = x1 −x2

1 − 3

2x1= 1.7321, f (x2) = 0.0002


O problema de computar√

3 pode ser formulado como encontrar o zero da funcaof (x) = x2 − 3. Desta forma a iteracao de Newton e dada por xk+1 = (xk + 3/xk )/2.

Como aproximacao inicial, escolhemos x0 = 2. Apos duas iteracoes de Newton ja temos umaaproximacao para a qual f (x) ≈ 2 · 10−4 e |x2 −

√3| ≈ 5 · 10−5.

Observe o quao rapido conseguimos progredir de uma aproximacao inicial grosseira para umaaproximacao aceitavel. De fato, uma grande vantagem do metodo de Newton e sua velocidadede convergencia.


Taylor ⇒ Newton

Se f ∈ C 2 entao

f (x∗) = f (x) + f ′(x)(x∗ − x) +O(|x∗ − x |2)

Se x for uma aproximacao razoavel para x∗, entao |x∗ − x | epequeno. Logo

0 = f (x∗) ≈ f (x) + f ′(x)(x∗ − x)

ou, se f ′(x) 6= 0,

x∗ ≈ x − f (x)

f ′(x)


Outra maneira de chegarmos ao metodo de Newton e atraves da expansao de Taylor deprimeira ordem. Ao utilizar tal caminho e possıvel estimar tambem a taxa de convergenciado metodo.

Teorema de Taylor: Seja f : [a, b] → R uma funcao com n derivadas contınuas em [a, b] ef (n+1) contınua em (a, b). Entao existe c ∈ (a, b) tal que

f (b) = f (a) + f ′(a)(b − a) +f ′′(a)

2(b − a)2 + · · ·+

f (n)(a)

n!(b − a)n︸︷︷︸

Tn(b)

+f (n+1)(c)

(n + 1)!(b− a)n+1.

Isto significa que|f (b)− Tn(b)| ≤ K(b − a)n+1.


Historia

1600 Francois Viete propos tecnica de perturbacao para solucaode equacoes polinomiais escalares.

1664 Newton conhece o trabalho de Viete.

1669 Newton aperfeicoa Viete, linearizando os sucessivospolinomios.

1687 O metodo e aplicado a primeira equacao nao polinomial.

1690 Joseph Raphson transforma o metodo em iterativo.

1740 Thomas Simpson introduz derivadas e extende o metodopara sistemas de equacoes.



Algoritmo

I Seja x0 uma aproximacao razoavel de x∗ E se nao for?

I Para k = 0, 1, 2, . . . Ate quando?

I Se f ′(xk) 6= 0, xk+1 = xk −f (xk)

f ′(xk)E se f ′(xk) = 0?


O nucleo do algoritmo para o metodo de Newton e bem simples. Ele consiste apenas decomputar sucessivamente uma aproximacao linear para a funcao e resolver o problema deencontrar o zero dessa aproximacao, tomando-o como nova estimativa para o zero da funcao.

Entretando, ao sair do campo teorico para o computacional, devemos nos atentar a algumasquestoes perguntas importantes. Vimos que a convergencia do Metodo de Newton easseguranda apenas quando partimos de um ponto inicial proximo. E se este nao for o caso?Nao temos como ter certeza, pois em geral nao conhecemos uma vizinhaca onde a solucaodeve estar.

Quando dissemos que as aproximacoes sao computadas sucessivamente, precisamos especi-ficar ate quando ou por quanto tempo, visto que na pratica nao e possıvel interar ao infinito.

Por fim, como a formula de interacao do Metodo de Newton realiza uma divisao, podeacontecer do denominador ser zero. O que fazer entao nessa situacao?


E se x0 nao for razoavel?

I Aplicar um metodo menos restritivo para comecar

I Globalizar o metodo de Newton

I Busca linear

I Regiao de confianca


Como o metodo de Newton precisa de uma boa estimativa inicial, uma estrategia pode serutilizar um metodo menos exigente, que funcione mesmo que essa aproximacao inicial naoseja tao boa. Depois desse metodo melhora-la um pouco, entao emprega-se o Metodo deNewton. O metodo da Bisseccao poderia ser utilizado com essa finalidade.

Outra estrategia e Globalizar o metodo de Newton, ou seja, modifica-lo para que o metodoconvirja independentemente de ponto de partida. As duas principais formas de globalizar ometodo de Newton sao atraves da insercao de uma busca linear na direcao apontada pelometodo de Newton ou atraves da definicao de uma Regiao de confianca, dentro da quala aproximacao linear e valida. Ambas as estrategias sao melhor discutidas no contexto demetodos de otimizacao e fogem ao escopo desta notas.


Criterios de parada

Gostarıamos de parar as iteracoes quando

|ek | ≤ ε|e0|

Porem, nao temos como medir ek diretamente!

ek = xk − x∗


Um algoritmo computacional nao pode deixar de explicitar o criterio de parada de execucao.O desejavel seria pedir que o erro ficasse abaixo de um certo nıvel aceitavel. Porem o problemae como medir o erro absoluto, sem o conhecimento do zero de f , x∗?


Criterios de parada

|f (xk)| ≤ ε

ε

−ε

|f ′(x∗)| � 1

ε

−ε

|f ′(x∗)| ≈ 1

ε

−ε

|f ′(x∗)| � 1


Um dos criterios que sim podemos aplicar e sobre o valor da f (xk ). O ideal seria relacionarum decrescimo no valor de f (xk ) com um decrescimo em ek . Quando a solucao existe,esta relacao de fato pode ser estabelecida. Porem, a constante de proporcionalidade estarelacioanda ao valor de f ′(x∗).

Pelos tres graficos e possıvel observar que se |f ′(x∗)| � 1, a funcao corta o eixo x muito“rasante”, o que significa que mesmo para pontos ainda relativamente distantes de x∗, jaterıamos a condicao |f (xk )| ≤ ε satisfeita.

Por outro lado, se |f ′(x∗)| � 1, a funcao cortaria o eixo x muito abruptamente. Destaforma, apenas quando xk estivesse realmente muito proximo de x∗ e que o criterio de paradaseria satisfeito.

Podemos ver isso expandido f em torno de x∗, em primeira ordem:

f (xk ) ≈ f (x∗) + f ′(x∗)(xk − x∗) = f ′(x∗)(xk − x∗),

pois f (x∗) = 0. Logo

|ek | = |xk − x∗| ≈∣∣∣∣ f (xk )

f ′(x∗)

∣∣∣∣ / ε

|f ′(x∗)|,

se |f (xk )| ≤ ε.


Criterios de parada

I |f (xk)| ≤ ε|f (x0)|

I |f (xk)| ≤ ε1|f (x0)|+ ε2

I |sk | ≤ ε|s0|, para sk = xk+1 − xk


Na pratica, os criterios mais usados, alem de um limite maximo para o numero de iteracoes,sao:

1. Uma reducao relativa no valor de funcao: O problema deste criterio e que se f (x0) formuito grande, o metodo pode parar ainda com f (xk ) muito grande. Por outro lado, sef (x0) ja for muito pequeno, entao o metodo vai se esforcar em demasia para reduzirdemais o valor de f (xk ).

2. Uma combinacao entre uma tolerancia relativa e uma absoluta para o valor de funcao:A escolha apropriada de ε1 e ε2 evita as mazelas do criterio anterior.

3. Uma reducao relativa no comprimento dos passos dados pelo metodo: Isso evitaprosseguir quando o metodo parece estagnar.


Derivada nula

I Trocar de ponto

I Fazer uma iteracao de outro metodo

I Utilizar a derivada do passo anterior


A iteracao de Newton para ser computada precisa de uma divisao pela derivada de f em xk .Se essa derivada for nula, a unica possibilidade e evitar isso, quer seja pela escolha de outroponto, quer seja pela troca do metodo de iteracao.

Claro que a change de voce acertar um ponto, no curso das iteracoes de Newton, que tenha aderivada exatamente nula, e muitıssima pequena. Sera que podemos nos tranquilizar entao?


Derivada quase nula

x0

x1 x2


Na pratica, a derivada ser quase nula ja e um problema. Como a reta tangente, num pontoonde a derivada e muito pequena, e praticamente paralela ao eixo horizontal, sua intersecaocom o eixo (proximo iterando do Metodo de Newton) acontecera muito distante. Com istoo iterando pode se afastar da regiao onde procuravamos por um zero da funcao, levando aconvergencia para outro zero ou mesmo a divergencia.


Taxas de convergencia

Convergencia linear

|ek+1| ≤ C |ek |, 0 < C < 1, ∀k > K

Convergencia superlinear

limk→∞

ek+1

ek= 0

Convergencia quadratica

limk→∞

|ek+1||e2k |

= C , C > 0


A taxa de convergencia linear e observada quando o erro em cada passo e aproximadamenteum fracao do erro no passo anterior.

A convergencia superlinear acontece quando essa fracao, ao inves de ser aproximadamentefixa, vai progressivamente reduzindo, ao longo das iteracoes.

Ja a taxa de convergencia quadratica e observada quando o erro em cada passo e, a grossomodo, o quadrado do erro no passo anterior. Na pratica, e como se a cada passo o numerode dıgitos corretos na aproximacao dobrasse.


Resultado

Convergencia do metodo de Newton

Hipoteses:

I f tem segunda derivada contınua

I f (x∗) = 0 e f ′(x∗) 6= 0

Entao existe uma vizinhanca V de x∗ tal que para qualquerx0 ∈ V , a sequencia gerada pelo metodo de Newton convergequadraticamente para x∗.

Proximo da solucao: ek+1 ≈ C e2k


Convergencia do metodo de NewtonSeja f ∈ C2, uma funcao com segunda derivada contınua. Suponha que x∗ e tal quef (x∗) = 0, f ′(x∗) 6= 0.

Entao existe uma vizinhanca V de x∗ tal que para qualquer x0 ∈ V , a sequencia gerada pelometodo de Newton converge quadraticamente para x∗.


Exercıcio

Estime π aplicando o metodo de Newton para f (x) = 1 + cos(x)

I Partindo de x0 = 3, quantas iteracoes sao necessarias paraobter uma aproximacao x para π, tal que |x − π| ≤ 10−2?

I Qual a taxa de convergencia observada?

I Explique o comportamento do metodo e proponha outrafuncao que se anule em π e seja mais adequada para ometodo de Newton.



Propriedades

I Necessidade de uma aproximacao inicial

I Convergencia local

I Taxa de convergencia quadratica, se proximo da solucao

I Necessidade da derivada a cada passo



Exemplo

f (z) = z3 − 1 = 0, z ∈ C

Quantas solucoes existem?


As tres solucoes de z3 = 1, sao 1 e − 12± i√

3.


Fractal


Nesta figura, cada uma das tres raızes esta associada a um cor (laranja, azul escuro e azulclaro). Cada ponto do plano foi pintado com uma dessas tres cores para indicar para qualzero a sequencia gerada pelo metodo de Newton converge quando iniciado naquele ponto.A intencidade da cor indica a quantidade de iteracoes necessarias para declara convergencia.Se a sequencia gerada nao convergir o ponto e pintado de preto.

Repare que proximo a cada um dos zeros, nao ha duvida e o metodo converge como esperado.Porem se o ponto inicial nao esta assim tao proximo de um dos zeros, e impossıvel saber paraonde o metodo convergira.


Metodos Quase-Newton

Metodos Quase-Newton sao aqueles que utilizam uma

aproximacao da derivada.


Como a operacao mais cara do metodo de Newton e a avaliacao da derivada, uma classe demetodos, conhecidos como metodos quase-Newton, barateam as iteracoes, evitando computara derivada da funcao, que e trocada por uma aproximacao. Os metodos diferem entre si, pelaforma como a derivada e aproximada.


Metodo das cordas

x0x1x2 x

y

xk+1 = xk −f (xk)

f ′(x0)


No metodo das cordas, a derivada e computada apenas no iterando inicial e depois mantidafixa no decorrer das iteracoes.


Metodo da secante

x0x1x2 x

y

xk+1 = xk −f (xk)

gk

gk =f (xk)− f (xk−1)

xk − xk−1


No metodo da secante, a inclinacao da reta secante ao grafico da funcao nas ultimas duasiteracoes e utilizada como aproximacao para o valor da derivada.

Esse metodo tem convergencia superlinear e precisa de dois pontos para ser inicializado.Observe que o ponto x2 obtido pelo metodo da secante foi melhor que o ponto x2 do metododas cordas.


Metodo de Newton

x1x2 x

y

xk+1 = xk −f (xk)

f ′(xk)


Para efeito de comparacao, veja qual seria o ponto x2 obtido pelo metodo de Newton.



3 (Newton)

xk+1 = xk −f (xk)

f ′(xk)

f (x) = x2 − 3, f ′(x) = 2x

x0 = 2, f (x0) = 1

x1 = x0 −x2

0 − 3

2x0= 1.7500, f (x1) = 0.0625

x2 = x1 −x2

1 − 3

2x1= 1.7321, f (x2) = 0.0002




3 (Secante)

xk+1 = xk −f (xk)

gk, gk =

f (xk)− f (xk−1)

xk − xk−1

f (x) = x2 − 3, f ′(x) = 2x

x0 = 2, f (x0) = 1

x1 = 1.7500, f (x1) = 0.0625

x2 = x1 −x2

1 − 3

g1= 1.7333, f (x2) = 0.0044



Exercıcio: Resolver f (x) = 0

f (x) = 3x2 − ex

I Identifique intervalos que contenham uma unica raız.

I Quantas raızes a equacao admite?

I Aplique o metodo de Newton para encontrar todas as raızes(utilize ε = 10−5).



Sistemas nao-lineares

Queremos agora resolver o sistema nao-linearf1(x1, x2, . . . , xn) = 0f2(x1, x2, . . . , xn) = 0

...fn(x1, x2, . . . , xn) = 0


A extensao do problema de encontrar uma solucao de uma unica equacao real e procuraruma solucao para um sistema de equacoes nao-lineares. As variaveis agora sao x1, x2, . . . , xn.Para nao confundir (ou ja confundindo), o subındice j em xj indica a j-esima variavel e naomais a aproximacao computada na j-esima iteracao. Para discriminar iteracoes, utilizaremos

ındices acima, por exemplo x(2)3 representa a aproximacao para a variavel x3 computada na

segunda iteracao.

Cada funcao fj que compoe o sistema e uma funcao escalar, ou seja, fj : Rn → R, que a cada(x1, x2, . . . , xn) 7→ f (x1, x2, . . . , xn) ∈ R.

Atencao: Na discussao que se segue, vamos nos restringir a sistema com igual numero deequacoes e variaveis.


Exemplo

{(x − x0)2 + (y − y0)2 − 1 = 0

ax + by + c = 0

x0

y0



Caracterısticas

I Pode ter ou nao solucao

I Pode ter uma, algumas ou infinitas solucoes

I Nao e tao simples localizar solucoes



Sistemas nao-lineares

Em notacao vetorial,

x ∈ Rn, x = (x1, x2, . . . , xn)T , e

F : Rn → Rn, F (x) = (f1(x), f2(x), . . . , fn(x))T .

Queremos encontrar x∗ ∈ Rn tal que

F (x∗) = 0

Hipotese: F e diferenciavel


A maneira de simplificar a notacao e poder perceber as semelhancas e diferencas entre oproblema unidimensional e multidimensional, e reescrever um sistema nao-linear usandonotacao vetorial.

1-D n-Dx ∈ R x ∈ Rn

f : R→ R F : Rn → Rn

Queremos x∗ tal que:f (x∗) = 0 F (x∗) = 0


Exemplo

{x2

1 − e−x1x2 = 0

x1x2 + sin x1 = 0

Neste caso,

F (x) =

(x2

1 − e−x1x2

x1x2 + sin x1

)


Neste caso, f1(x) = x21 − e−x1x2 e f2(x) = x1x2 + sin x1 sao as componentes de F (x).


Taylor ⇒ Newton

F (x + s) = F (x) + J(x)s +O(‖s‖2)

J(x) e a matriz Jacobiana de F

J(x) =

∇T f1(x)∇T f2(x)

...∇T fn(x)


Em 1-D:f (x + s) = f (x) + f ′(x)s +O(s2), f ′(x)s ≈ f (x + s)− f (x)

Em n-D:F (x + s) = F (x) + J(x)s +O(‖s‖2), Js ≈ F (x + s)− F (x)


Exemplo

F (x) =

(x2

1 − e−x1x2

x1x2 + sin x1

)

J(x) =

(2x1 + x2e

−x1x2 x1e−x1x2

x2 + cos x1 x1

)


Observe as linhas da matriz Jacobiana sao os gradientes das componentes de F .


Metodo de Newton para sistemas

F (x + s) = F (x) + J(x)s +O(‖s‖2)

F (x + s) ≈ F (x) + J(x)s

Impondo que F (x + s) = 0, temos que

J(x)s = −F (x)

Nova aproximacao

x + s = x − J(x)−1F (x)


O metodo de Newton para sistemas e construıdo de maneira analoga ao metodo de Newtonpara uma equacao escalar, ou seja, considerando-se a aproximacao de Taylor de primeiraordem apenas.

Em cada iteracao, um sistema linear deve ser resolvido para descobrir s, denominado passo.Esse passo e entao somado a aproximacao atual para obter a nova aproximacao.


Algoritmo

I Seja x (0) uma aproximacao razoavel de x∗

I Para k = 0, 1, 2, . . .

I Se J(x (k)) for nao-singular, resolver J(x (k))s(k) = −F (x (k))

I x (k+1) = x (k) + s(k)


Repare a semelhanca entre esse algoritmo e o algoritmo para o metodo de Newton no casode uma unica equacao escalar.


Exemplo: ponto inicial

F (x) =

(x2

1 − e−x1x2

x1x2 + sin x1

)J(x) =

(2x1 + x2e

−x1x2 x1e−x1x2

x2 + cos x1 x1

)

Se x (0) = (2, 1)T , entao

F (x (0)) =

(3.8647

2.9093

)J(x (0)) =

(4.1353 0.2707

0.5839 2.0000

)

‖F (x (0))‖∞ = 3.8647


Abritrariamente foi escolhido como ponto inicial x(0) = (2, 1)T . Nesse ponto, avaliar afuncao F e da matriz Jacobiana J. Observe que a ‖F (x(0))‖ da uma medida de quao pertox(0) esta de satisfazer F (x) = 0.

Aqui usamos a norma infinito apenas por ser mais simples. Outras normas poderiam serusadas tambem.


Exemplo: primeira iteracao

(4.1353 0.2707

0.5839 2.0000

)s(0) = −

(3.8647

2.9093

)

s(0) = (−0.8557,−1.2049)T , x (1) = x (0)+s(0) = (1.1443,−0.2049)T

F (x (1)) =

(0.0453

−0.6760

)‖F (x (1))‖∞ = 0.6760


Para progredir de x(0) a x(1) e necessario resolver o sistema linear que determina o passos(0). Feito isso, obtemos a nova aproximacao.

Repare que nesse novo ponto, o valor de ‖F (x(1))‖ < ‖F (x(0))‖, indicando que houve melhoraem satisfazer o sistema nao-linear.


Exemplo: segunda iteracao

(2.0297 1.4466

0.2088 1.1443

)s(1) = −

(0.0453

−0.6760

)

s(1) = (0.4584,−0.6744)T , x (2) = x (1)+s(1) = (1.6026,−0.8793)T

F (x (2)) =

(−1.5239

−0.4097

)‖F (x (2))‖∞ = 1.5239


Estranhamente, nesta segunda iteracao parece que tivemos uma piora na aproximacao vistoque ‖F (x(2))‖ > ‖F (x(1))‖.


Exemplo: terceira iteracao

(−0.3930 6.5589

−0.9111 1.6027

)s(2) = −

(−1.5239

−0.4097

)

s(2) = (0.0457, 0.2296)T , x (3) = x (2)+s(2) = (1.5569,−0.6497)T

F (x (3)) =

(−0.3256

−0.0115

)‖F (x (3))‖∞ = 0.3256


Nesse exemplo, temos que

k ‖F (x(k))‖0 3.8647

1 0.6760

2 1.5239 ← aumentou!

3 0.3256

Esse comportamento significa o que? Da para confiar que a sequencia esta convergindo?Pense em um exemplo em uma dimensao, isto e, um exemplo com uma unica equacao nao-linear, onde esse mesmo comportamento e observado.


Exemplo: trajetoria

x0


Observe que neste exemplo, mesmo com o valor de funcao tendo aumentado, em todos ositerandos se aproximaram gradativamente da solucao do sistema. De fato, a partir da terceiraiteracao e possıvel perceber que os iterandos devem estar dentro da regiao de convergenciaquadratica do metodo de Newton.

k ‖F (x(k))‖∞ ‖x(k) − x∗‖∞0 3.8647 1.6057

1 0.6760 0.5021

2 1.5239 0.27343 0.3256 0.0894 ← conv. quadratica

4 0.0210 0.0061

5 0.0001 0.0000


Criterios de parada

I ‖s(k)‖ ≤ ε‖s(0)‖

I ‖F (x (k))‖ ≤ ε‖F (x (0))‖

I ‖F (x (k))‖ ≤ ε1‖F (x (0))‖+ ε2


Os criterios de parada sao totalmente analogos aos criterios utilizados no caso de uma unicaequacao nao-linear.


Algoritmo

I Seja x (0) uma aproximacao razoavel de x∗

I Enquanto ‖F (x (k))‖ > ε‖F (x (0))‖ e k < K

I Se J(x (k)) for nao-singular, resolver J(x (k))s(k) = −F (x (k))

I x (k+1) = x (k) + s(k)

I k ← k + 1



Subproblema – Sistema Linear

J(x (k))s(k) = −F (x (k))

I Metodos diretos

I Metodos iterativos

I Solucao exata

I Solucao aproximada (Newton Inexato)


No caso do metodo de Newton para sistemas nao-lineares surge a questao de como re-solver o sistema linear gerado em cada iteracao. Esse problema e denominado de subproblema.

Para o subproblema, tanto metodos diretos quanto iterativos podem ser utilizados, e nocaso de metodos iterativos, pode-se emprega-los ate atingir convergencia na solucao ou paraem uma solucao aproximada. Neste caso deve-se apenas tomar o cuidado de exigir que aqualidade dessas solucoes aproximadas aumentem a medida que progredimos nas iteracoes dometodo de Newton.


Exercıcio

{x2

1 + x22 − 2 = 0

x1x2 − 1 = 0

I Analisando graficamente, discuta a existencia e unicidade desolucoes.

I Obtenha a matriz jacobiana, J.

I Exiba o sistema linear a ser resolvido em cada iteracao dometodo.


Documents

Métodos para equações não-lineares