47
Equa¸ oes n˜ ao lineares etodos Num´ ericos e Estat´ ısticos Parte I-M´ etodos Num´ ericos Equa¸c˜ oes n˜ ao lineares Lu´ ısa Morgado Lic. Eng. Biom´ edica e Bioengenharia-2009/2010 Lu´ ısa Morgado Equa¸ oes n˜ ao lineares

Equações não Lineares

  • Upload
    lamnga

  • View
    226

  • Download
    2

Embed Size (px)

Citation preview

Page 1: Equações não Lineares

Equacoes nao lineares

Metodos Numericos e EstatısticosParte I-Metodos Numericos

Equacoes nao lineares

Luısa Morgado

Lic. Eng. Biomedica e Bioengenharia-2009/2010

Luısa Morgado Equacoes nao lineares

Page 2: Equações não Lineares

Equacoes nao lineares

Para determinarmos um valor aproximado das raızes de uma equacao nao linear,convem notar inicialmente que varias situacoes diferentes podem ocorrer no querespeita a existencia e unicidade de solucao:

Nao existe solucaosin x − 2 = 0;

Existe solucao e e unicax + 1− ex = 0;

Existe uma solucao multipla(x − 3)2 = 0;

Existem varias solucoes, algumas delas multiplas

(x − 1)(x − π)3 = 0;

Existe uma infinidade de solucoes

cos x = 0.8.

A maior parte dos metodos numericos para resolucao de equacoes nao lineares exige o

fornecimento de uma regiao que contenha as raızes procuradas. Como tal, na

utilizacao de tais metodos, e necessario um estudo preliminar mınimo da funcao

envolvida na equacao.

Luısa Morgado Equacoes nao lineares

Page 3: Equações não Lineares

Equacoes nao lineares

Metodo Grafico

Um dos metodos mais elementares para localizar um zero de umafuncao e o metodo grafico.Imaginemos que pretendemos localizar os zeros da funcao

f (x) = ex − 3x .

Notemos, em primeiro lugar que determinar os zeros de f eequivalente a determinar as raızes da equacao

f (x) = 0⇔ ex = 3x .

Assim sendo, ao utilizarmos o metodo grafico, em vez de fazermoso tracado do grafico de f e localizar os pontos onde este intersectao eixo dos xx , e mais simples se fizermos o tracado das funcoes ex

e 3x e localizar os pontos onde estes se intersectam.

Luısa Morgado Equacoes nao lineares

Page 4: Equações não Lineares

Equacoes nao lineares

-0.5 0.5 1 1.5 2x

2

4

6

y

3x

ex

Por analise dos graficos, podemos palpitar queexistem duas raızes, x∗1 e x∗2 da equacao e que

x∗1 ∈ [0, 1] e x∗2 ∈ [1, 2].

Convem sempre verificar analiticamente a existencia e a unicidade de tais raızes nosrespectivos intervalos.Recordemos que

Se f e uma funcao contınua num intervalo [a, b] e se f (a) · f (b) < 0, entao f tempelo menos um zero em [a, b].Se alem disso, ∀x ∈]a, b[, f ′(x) 6= 0 entao, nesse intervalo, esse zero e unico .

Verifiquemos entao que sendo f (x) = ex − 3x , existe um unico x∗1 ∈ [0, 1] tal quef (x∗1 ) = 0.

f (0) = 1 > 0, f (1) = e − 3 < 0, logo f (0) · f (1) < 0;

f ′(x) = ex − 3 so se anula em ln 3 ' 1.1, logo ∀x ∈]0, 1[, f ′(x) 6= 0.

Luısa Morgado Equacoes nao lineares

Page 5: Equações não Lineares

Equacoes nao lineares

Metodos Numericos para equacoes nao lineares

Os metodos que iremos estudar sao iterativos, i.e., fornecem-nosuma sucessao de valores x1, x2, . . ., os quais, em caso deconvergencia da sucessao, se irao aproximar da solucao x∗ de umaequacao f (x) = 0.Esta sucessao e definida por recorrencia, necessitando de uma oumais aproximacoes iniciais, conforme o metodo.

A utilizacao de um metodo iterativo coloca-nos, a partida tresproblemas:

1 construcao do metodo;

2 estudo da convergencia da sucessao de aproximacoesx1, x2, . . . fornecida pelo metodo;

3 analise da velocidade de convergencia.

Luısa Morgado Equacoes nao lineares

Page 6: Equações não Lineares

Equacoes nao lineares

Criterios de paragem

Como e impossıvel efectuar um numero infinito de iteracoes , seranecessario parar apos a obtencao de uma aproximacao xN . Istocoloca-nos outro problema: o da escolha de um criterio deparagem, dependente da precisao pretendida.Suponhamos que pretendemos determinar uma aproximacao xn daraız x∗ da equacao f (x) = 0, localizada num intervalo I = [a, b],tal que |xn − x∗| < ε.Existem varios criterios de paragem, p.e.:

(i) Criterio do erro absoluto: |xn − xn−1| < ε;

(ii) Criterio do erro relativo: |xn−xn−1||xn| < ε;

(iii) Numero maximo de iteracoes: n = nmax . Estecriterio costuma usar-se como factor de seguranca,para o caso do metodo divergir, e como tal e usualusa-lo juntamente com outro criterio;

Luısa Morgado Equacoes nao lineares

Page 7: Equações não Lineares

Equacoes nao lineares

(iv) no caso de f ∈ C 1 (I ), sabemos, pelo teorema dovalor medio de Lagrange que

f (xn)−f (x∗) = f ′ (ξ) (xn − x∗) , para algum ξ ∈ I .

Sendo f ′ (ξ) 6= 0, podemos dizer

|xn − x∗| =|f (xn)− f (x∗)||f ′ (ξ)|

.

Como f (x∗) = 0 e ξ e desconhecido:

|xn − x∗| ≤ |f (xn)|minx∈I |f ′ (ξ)|

,

e desta forma obtem-se o criterio de paragem

|f (xn)|minx∈I |f ′ (ξ)|

< ε.

Note-se que se f ′ tomar valores muito pequenos,mesmo nao sendo nulos, este deixa de ser um criteriorazoavel;

Luısa Morgado Equacoes nao lineares

Page 8: Equações não Lineares

Equacoes nao lineares

(v) Criterio do valor da funcao: |f (xn)| < ε.Este criterio pode nao ser uma boa escolha sempreque o grafico de f esteja muito proximo do eixo dosxx , pois assim pode ser verificado o criterio deparagem e no entanto xn estar ”longe” de x∗.

Luısa Morgado Equacoes nao lineares

Page 9: Equações não Lineares

Equacoes nao lineares

Ordem de convergencia

Chamamos ordem de convergencia de uma sucessao conver-gente (xn)n∈N, a maior potencia p ≥ 1 tal que

|xn+1 − x∗| ≤ k |xn − x∗|p ,

para algum 0 < k < 1. A k da-se o nome de factor de con-vergencia.Se p = 1, dizemos que a convergencia e linear; se p > 1, aconvergencia diz-se supra-linear.

Assim, quanto maior for a ordem de convergencia de um metodo,mais rapido ele e no fornecimento de uma boa aproximacao dasolucao; Se dois metodos tiverem a mesma ordem de convergencia,e mais rapido aquele que apresentar um factor de convergenciamenor.

Luısa Morgado Equacoes nao lineares

Page 10: Equações não Lineares

Equacoes nao lineares

No caso de convergencia linear, sao validas as seguintes ma-joracoes:

|xn − x∗| ≤ 1

1− k|xn − xn+1|

|xn+1 − x∗| ≤ k

1− k|xn − xn+1|

No caso de convergencia supra-linear:

|xn − x∗| ≈ |xn − xn+1|

Luısa Morgado Equacoes nao lineares

Page 11: Equações não Lineares

Equacoes nao lineares

Metodo da Bisseccao

O teorema de Bolzano sugere-nos um processo muito simples paraobter uma aproximacao do zero de uma funcao f :Supondo que

1. f e contınua em [a, b],2. f (a) · f (b) < 0,3. ∀ ∈]a, b[, f ′(x) 6= 0,

i.e existe um unico zero da funcao f no interior do intervalo [a, b],o processo consiste em dividir o intervalo dado ao meio,obtendo-se assim os dois subintervalos[

a,a + b

2

]e

[a + b

2, b

]e depois testar a condicao 2. nestes dois intervalos para determinarqual deles contem a raız.O processo e repetido para o novo subintervalo contendo a raız ateque se obtenha a precisao pretendida.

Luısa Morgado Equacoes nao lineares

Page 12: Equações não Lineares

Equacoes nao lineares

Condicao suficiente de convergencia:f contınua em [a, b]f (a)f (b) < 0

Inicializacao:a0 = a, b0 = bx0 = a ou x0 = b

Ciclo:Para m ≥ 0 fazer

xm+1 = am+bm2

Se |xm+1 − xm| ≤ ε ou f (xm+1) ≤ εentao fazer x∗ ≈ xm+1 e parar

caso contrarioSe f (xm+1) f (am) < 0 entao fazer

am+1 = am e bm+1 = xm+1

senaoam+1 = xm+1 e bm+1 = bm

Metodo da bisseccao

Luısa Morgado Equacoes nao lineares

Page 13: Equações não Lineares

Equacoes nao lineares

Se x∗ e o zero de f localizado no intervalo [an, bn], entao

|xn+1 − x∗| ≤ |xn+1 − xn| .

Por outro lado, prova-se facilmente que

|bn − an| =1

2n(b − a)

e que

|xn+1 − x∗| ≤bn − an

2ou |xn − x∗| ≤

b − a

2n, n ≥ 0.

No caso do metodo da bisseccao nao existe nenhuma constante k, 0 < k < 1 quesatisfaca

|xn+1 − x∗| ≤ k |xn − x∗| ou |xn − x∗| ≤ kn |x0 − x∗| , n ≥ 0.

No entanto, se considerarmos que um metodo tem convergencia linear quando

|xn − x∗| ≤ kn(b − a), n ≥ 0, podemos afirmar que o metodo da bisseccao converge

linearmente, com factor de convergencia k = 12

.

Luısa Morgado Equacoes nao lineares

Page 14: Equações não Lineares

Equacoes nao lineares

Exemplo

O numero de indivıduos de uma populacao pode ser dado, numcurto perıodo de tempo, pela funcao

N(t) = N0eλt +ν

λ

(eλt − 1

),

onde ν representa a taxa anual de imigracao, λ a taxa anual denatalidade e N0 o numero de indivıduos no instante inicial.Sabe-se que uma dada populacao possui inicialmente um milhaode indivıduos, que 281× 103 imigraram para a comunidade duranteo primeiro ano e que no fim desse ano existem 1.780× 106 deindivıduos. Pretende-se determinar a taxa de natalidade dessapopulacao nesse ano.

Luısa Morgado Equacoes nao lineares

Page 15: Equações não Lineares

Equacoes nao lineares

Para determinarmos a taxa de natalidade, temos que resolver aequacao nao linear

1.780× 106 = 106eλ +281× 103

λ

(eλ − 1

).

Vamos faze-lo determinando o zero da funcao

f (λ) = 106eλ +281× 103

λ

(eλ − 1

)− 1.780× 106

no intervalo [0.1, 1], pelo metodo da bisseccao com x0 = 0.1.

Luısa Morgado Equacoes nao lineares

Page 16: Equações não Lineares

Equacoes nao lineares

Com o criterio de paragem |f (xn)| < 10−4:

x1 = 0.55 f (x1) = 327878.650632 x17 = 0.365216827393 f (x17) = 0.8283339x2 = 0.325 f (x2) = −63930.5493404 x18 = 0.365213394165 f (x18) = −4.735935x3 = 0.4375 f (x3) = 121336.159014 x19 = 0.365215110779 f (x19) = −1.9538028x4 = 0.38125 f (x4) = 26188.1277134 x20 = 0.365215969086 f (x20) = −0.5627351x5 = 0.353125 f (x5) = −19482.6488803 x21 = 0.365216398239 f (x21) = 0.1327992x6 = 0.3671875 f (x6) = 3197.7633636 x22 = 0.365216183662 f (x22) = −0.2149679x7 = 0.36015625 f (x7) = −8180.9199049 x23 = 0.365216290951 f (x23) = −0.0410844x8 = 0.363671875 f (x8) = −2501.2307709 x24 = 0.365216344595 f (x24) = 0.0458574x9 = 0.3654296875 f (x9) = 345.8490071 x25 = 0.365216317773 f (x25) = 0.0023865x10 = 0.36455078125 f (x10) = −1078.2946831 x26 = 0.365216304362 f (x26) = −0.0193489x11 = 0.364990234375 f (x11) = −366.3738534 x27 = 0.365216311067 f (x27) = −0.0084811x12 = 0.365209960938 f (x12) = −10.3001852 x28 = 0.36521631442 f (x28) = −0.0030473

x13 = 0.365319824219 f (x13) = 167.7649694 x29 = 0.365216316096 f (x29) = −3.304× 10−4

x14 = 0.365264892578 f (x14) = 78.7300319 x30 = 0.365216316935 f (x30) = 0.0010281

x15 = 0.365237426758 f (x15) = 34.2143333 x31 = 0.365216316516 f (x31) = 3.488× 10−4

x16 = 0.365223693848 f (x16) = 11.9569266 x32 = 0.365216316306 f (x32) = 9.2× 10−6

Sao necessarias 32 iteracoes.

Luısa Morgado Equacoes nao lineares

Page 17: Equações não Lineares

Equacoes nao lineares

Com o criterio de paragem |xn − xn+1| < 10−4:

Seriam necessarias 18 iteracoes para a aproximacao pedida, com a seguinte majoracaopara o erro:

|x∗ − x18| ≤1− 0.1

218= 3.4× 10−6.

Luısa Morgado Equacoes nao lineares

Page 18: Equações não Lineares

Equacoes nao lineares

No scilab:

Exemplo

Exercıcio 18 dos problemas propostos:

x=[2:0.1:8]’;

function y=fun(t),y=7*exp(-2*t)+2*exp(-0.1*t)-1, endfunction;clf();

plot(x,fun(x))

a=6;b=7;it=0;h=10;

while h>10^(-8),

c=(a+b)/2;

if fun(c)*fun(a)>0 then a=c;else b=c;end;

printf(’it=%d\n’,it);

printf(’xi=%0.8f\n’,c);

printf(’f(xi)=%0.8f\n’,fun(c));

it=it+1;

h=abs(b-a);

end;

printf(’h=%0.8f\n’,h);printf(’valor aprox:%0.8f’,c)

Luısa Morgado Equacoes nao lineares

Page 19: Equações não Lineares

Equacoes nao lineares

Metodo do ponto fixo

Muitas vezes, o problema da determinacao do zero de uma funcao f pode reduzir-se aprocura de um valor z que satisfaca a equacao g(x) = x . Diz-se entao que z e umponto fixo de g .O metodo do ponto fixo e um metodo iterativo para aproximar o zero de uma funcaof , localizado no intervalo [a, b], baseado na relacao de recorrencia

xn+1 = g(xn), n ≥ 0, x0 ∈ [a, b].

Existem varias maneiras de reescrever f (x) = 0 na forma g(x) = x .

Exemplo

Para aproximarmos a raız de ex − 1x

= 0 no intervalo [0.4, 0.6], pelo metodo do pontofixo, temos que inicialmente escolher a funcao de iteracao g.Ora ex − 1

x= 0 pode ser reescrita, p.e.,

x = e−x ;

x = − ln x.

O proximo teorema diz-nos quais as condicoes que teremos que impor a g por forma a

obter um metodo convergente.

Luısa Morgado Equacoes nao lineares

Page 20: Equações não Lineares

Equacoes nao lineares

Teorema do ponto fixo

Seja g uma funcao definida no intervalo fechado [a, b] satis-fazendo

1 a ≤ g(x) ≤ b, para todo o x ∈ [a, b];

2 existe uma constante L, 0 < L < 1 tal que|g(x)− g(y)| ≤ L|x − y | para quaiquer x , y ∈ [a, b].

Nestas condicoes g possui em [a, b] um unico ponto fixo z , limiteda sucessao definida por recorrencia{

x0

xn = g (xn−1) , n ∈ N

qualquer que seja x0 ∈ [a, b].

Luısa Morgado Equacoes nao lineares

Page 21: Equações não Lineares

Equacoes nao lineares

Dem.: Comecemos por mostrar que a sucessao (xn)n∈N e convergente:Ora

|xn+1 − xn| = |g(xn)− g(xn−1)| ≤ L |xn − xn−1| ≤ L2 |xn−1 − xn−2| ≤ . . . ≤ Ln |x1 − x0| .

Sendo n > k

xn − xk = xn − xn−1 + xn−1 − xn−2 + . . .+ xk+1 − xk

pela desigualdade triangular

|xn − xk | ≤ |xn − xn−1|+ |xn−1 − xn−2|+ . . .+ |xk+1 − xk |

≤(

Ln−1 + Ln−2 + . . .+ Lk)

︸ ︷︷ ︸progressao geometrica de razao L

|x1 − x0|

= Lk 1− Ln−k

1− L|x1 − x0| <

Lk

1− L|x1 − x0| .

Desta forma, dado δ > 0, existe p ∈ N, tal que n, k ≥ p ⇒ |xn − xk | < δ, desde que

n > k. Podemos entao afirmar que (xn)n∈N e uma sucessao de Cauchy em R logo

convergente para um limite z que pertence a [a, b], pela condicao 1.

Luısa Morgado Equacoes nao lineares

Page 22: Equações não Lineares

Equacoes nao lineares

Mostremos agora que z e um ponto fixo de g :

|g(z)− z| = |g(z)− xn+1 + xn+1 − z| ≤ |g(z)− xn+1|+ |xn+1 − z|= |g(z)− g(xn)|+ |xn+1 − z| .

Como g e contınua (pela condicao 2.) e como limn

xn = z, fazendo n→∞ na

desigualdade acima obtem-se g(z)− z = 0⇔ g(z) = z.Resta-nos mostrar que o ponto fixo e unico. Para tal suponhamos que existem doispontos fixos de g , z1 e z2.

|z1 − z2| = |g (z1)− g (z2)| ≤ L |z1 − z2| < |z1 − z2| ,

o que e absurdo. Logo teremos que ter z1 = z2.

Nota: Dividindo ambos os membros da inequacao da condicao 2. do teorema por

|x − y | e supondo que existe o limite limy→x

g(x)−g(y)x−y

, podemos concluir que

|g ′(x)| ≤ L < 1 em [a, b].

Luısa Morgado Equacoes nao lineares

Page 23: Equações não Lineares

Equacoes nao lineares

Condicao suficiente de convergencia:f contınua em [a, b]f (a)f (b) < 0Escolher uma funcao g tal que f (x) = 0⇔ g(x) = x , com

g ∈ C 1 (]a, b[)g ([a, b]) ⊂ [a, b]maxx∈]a,b[ |g ′(x)| < 1

Inicializacao:x0 ∈ [a, b]

Ciclo:Para m ≥ 0 fazer

xm+1 = g(xm)ate

|xm+1 − xm| ≤ ε ou |f (xm+1)| ≤ ε

Metodo do ponto fixo

Luısa Morgado Equacoes nao lineares

Page 24: Equações não Lineares

Equacoes nao lineares

Supondo g ′(x) 6= 0, ∀x ∈]a, b[, o metodo do ponto fixo temconvergencia linear a admite a seguinte majoracao do erro

|z − xn+1| ≤ maxx∈[a,b]

∣∣g ′(x)∣∣ |z − xn| , n ≥ 0.

Se g e tal que

g ′(z) = . . . g (p−1)(z) = 0 e g (p)(z) 6= 0,

entao a ordem de convergencia do metodo e p e a estimativa parao erro e

|z − xn+1| ≤M

p!|z − xn|p , n ≥ 0,

com M = maxx∈]z−ε,z+ε[

∣∣g (p)(x)∣∣.

Luısa Morgado Equacoes nao lineares

Page 25: Equações não Lineares

Equacoes nao lineares

Exemplo

Vamos resolver a equacao algebrica x2 − 100x + 1 = 0 pelo metodo do ponto fixo.Usando a formula resolvente, sabemos que as raızes desta equacao sao x∗1 ' 0.01 ex∗2 ' 99.99.Ora,

x2 − 100x + 1 = 0⇔ x =1

100

(x2 + 1

)︸ ︷︷ ︸

g1(x)

.

Como g ′1(x) = 0.02x a escolha desta funcaoiteradora g1 e boa para aproximarmos x∗1 .

O esquema iterativo

x0 = 1

xn+1 =1

100

(x2

n + 1), n ≥ 0,

fornece as seguintes aproximacoes:

xi g1(xi )0.02 0.0100040.010004 0.01000100080.0100010008 0.01000100020.0100010002 0.0100010002

Analizando os resultados obtidos, concluımos que a partir da quarta iteracao se tem

xn ≈ g1(xn).

Luısa Morgado Equacoes nao lineares

Page 26: Equações não Lineares

Equacoes nao lineares

A funcao iteradora g1 ja nao e uma boa escolha quando se pretende aproximar a raızx∗2 pelo metodo do ponto fixo. Vamos entao escrever

x2 − 100x + 1 = 0⇔ x = 100−1

x︸ ︷︷ ︸g2(x)

.

Comecando com a aproximacao inicial x0 = 10, como g ′2(x) = 1x2 , o esquema iterativo

x0 = 10

xn+1 = 100−1

xn, n ≥ 0,

convergira para x∗2 .

xi g2(xi )99.9 99.989989999.9899899 99.989998998999.9899989989 99.989998999899.9899989998 99.9899989998

Luısa Morgado Equacoes nao lineares

Page 27: Equações não Lineares

Equacoes nao lineares

No scilab:

Exemplo

Exercıcio 21 dos problemas propostos:

function y=f(x), y=exp(x)-4*x^2, endfunction;

x=[-6:0.1:6]’;

plot(x,f(x));

f(4)

f(5)

function z=g(x), z=log(4*x^2), endfunction;

g(4)

g(5)

a=[4:0.1:5]’;

plot(a,g(a));

x0=4;it=1;tol=1;

while tol>10^(-5)

xi=g(x0);tol=abs(xi-x0);

printf(’it=%d\n’,it);

printf(’xi=%0.8f\n’,xi);

x0=xi;

it=it+1;

end;

Luısa Morgado Equacoes nao lineares

Page 28: Equações não Lineares

Equacoes nao lineares

Metodo de Newton

Seja f ∈ C 2[a, b], [a, b] ⊂ R e x∗ ∈ [a, b] a unica raız de f (x) = 0 nesse intervalo.Suponhamos que:

f (a)f (b) < 0

f ′(x) 6= 0 ∀x ∈ (a, b)

f ′′(x) de sinal constante em (a, b).

Pela formula de Taylor, sendo x0 ∈ [a, b],

f (x) = f (x0) + f ′(x0)(x − x0) +f ′′(η)

2(x − x0)2, η ∈ I{x , x0}

Podemos entao escrever

f (x) ≈ f (x0) + f ′(x0)(x − x0),

e obter uma aproximacao da raız de f (x) = 0 fazendo x = x1, de forma a que osegundo membro se anule, i.e.:

f (x0) + f ′(x0)(x1 − x0) = 0⇒ x1 = x0 −f (x0)

f ′(x0), f ′(x0) 6= 0.

Luısa Morgado Equacoes nao lineares

Page 29: Equações não Lineares

Equacoes nao lineares

Fazendo sucessivamente f (x) ≈ f (xn) + f ′(xn)(x − xn), vem a chamada formulaiteradora do metodo de Newton

xn+1 = xn −f (xn)

f ′(xn), n = 0, 1, . . . ,

desde que f ′(x) nunca se anule em nenhuma das iteracoes.

Nota: Note que y = xn − f (xn)f ′(xn)

e a equacao da recta tangente ao grafico de f no

ponto xn, razao pela qual o metodo de Newton tambem e conhecido pelo metodo da

tangente.

Luısa Morgado Equacoes nao lineares

Page 30: Equações não Lineares

Equacoes nao lineares

Interpretacao geometrica

Suponhamos que f (a) < 0, f (b) > 0 ef ′′(x) > 0.

Sendo x0 = b, consideremos a recta tangente a curva em x0. A equacao desta rectatangente e entao y − f (x0) = f ′(x0)(x − x0). Se considerarmos a interseccao destarecta com o eixo dos abcissas (fazendo y = 0), obtemos:

x = x0 −f (x0)

f ′(x0)︸ ︷︷ ︸x1

Se considerarmos a recta tangente a curva em x1:

y − f (x1) = f ′(x1)(x − x1)y=0=⇒ x = x1 −

f (x1)

f ′(x1)︸ ︷︷ ︸x2

e assim sucessivamente.Luısa Morgado Equacoes nao lineares

Page 31: Equações não Lineares

Equacoes nao lineares

Condicao suficiente de convergencia:f contınua em [a, b]f (a)f (b) < 0f ′(x), f ′′(x) 6= 0,∀x ∈ [a, b]f (x0)f ′′(x) > 0, ∀x ∈ [a, b]

Inicializacao:x0 escolhido de acordo com a ultimacondicao de convergencia

Ciclo:Para m ≥ 0 fazer

xm+1 = xm − f (xm)f ′(xm)

ate|xm+1 − xm| ≤ ε ou f (xm+1) ≤ ε

Metodo de Newton

Luısa Morgado Equacoes nao lineares

Page 32: Equações não Lineares

Equacoes nao lineares

Exemplo

Dado a > 0, determinemos, pelo metodo de Newton, uma aproximacao do seuinverso, 1

a.

O problema proposto e equivalente a determinacao da raız da equacao a = 1x

.

Consideremos entao a funcao f (x) = 1x− a Com a = 7, f (x) = 1

x− 7 e pode

localizar-se o zero desta funcao no intervalo [0.1, 0.2]. Como

f e contınua em [0.1, 0.2] e f (0.1) = 3 > 0, f (0.2) = −2 < 0,

f ′(x) = − 1x2 < 0, ∀x ∈ [0.1, 0.2],

f ′′(x) = 2x3 > 0, ∀x ∈ [0.1, 0.2],

com x0 = 0.1,

o metodo de Newton sera convergente para a solucao do problema fornecendo asseguintes aproximacoes:

x1 = 0.13x2 = 0.1417x3 = 0.14284777x4 = 0.1428571422x5 = 0.1428571429x5 = 0.1428571429

Luısa Morgado Equacoes nao lineares

Page 33: Equações não Lineares

Equacoes nao lineares

Condicoes suficientes de convergencia

Se f (a)f (b) < 0, f ′(x) 6= 0 e f ′′(x) 6= 0, ∀x ∈ [a, b], entao a sucessao {xn} econvergente para o unico zero de f em [a, b], desde que se considere a condicaof (x0)f ′′(x0) > 0.

Dem.: Suponhamos, sem perda de generalidade, quef (a) < 0, f (b) > 0, f ′(x), f ′′(x) > 0, x0 = b.Para provarmos que {xn} e convergente, mostraremos que {xn} e nao crescente elimitada inferiormente.

{xn} e limitada inferiormente: Usando a formula de Taylor

0 = f (x∗) = f (xn) + f ′(xn)(x∗ − xn) + f ′′(η)(x∗ − xn)2

2, ηn ∈ I{x∗, xn}

Dividindo tudo por f ′(x) 6= 0, temos:

0 = x∗ −(

xn −f (xn)

f ′(xn)

)︸ ︷︷ ︸

xn+1

+f ′′(ηn)

f ′(xn)

(x∗ − xn)2

2⇐⇒

⇐⇒ x∗ − xn+1 = −f ′′(ηn)

f ′(xn)

(x∗ − xn)2

2≤ 0

donde resulta que x∗ ≤ xn+1,∀n ∈ N0.

Luısa Morgado Equacoes nao lineares

Page 34: Equações não Lineares

Equacoes nao lineares

{xn} e nao crescente: Como x∗ ≤ xn, ∀n ∈ N, vem que f (xn) ≥ 0, ∀n ∈ N0.De

x1 − x0 = −f (x0)

f ′(x0)

e f (x0) > 0 resulta x1 < x0 e de

xn+1 − xn = −f (xn)

f ′(xn)(1)

e de f (xn) ≥ 0 resulta xn+1 < xn.

Provamos entao que a sucessao {xn} e convergente. Vejamos agora se xn −→ x∗.

Sendo α tal que xn −→ α, tomando o limite em (1) obtemos f (α) = 0. Mas como

este intervalo contem uma unica raız, temos que α ≡ x∗

Luısa Morgado Equacoes nao lineares

Page 35: Equações não Lineares

Equacoes nao lineares

Convergencia quadratica

Nas condicoes do teorema anterior

|x∗ − xn+1| ≤ M|x∗ − xn|2, n ∈ N0

onde

M =1

2

maxx∈[a,b] |f ′′(x)|minx∈[a,b] |f ′(x)|

Dem.: Seja x0 ∈ [a, b] tal que f (x0)f ′′(x0) > 0. Vimos que

|x∗ − xn+1| =

∣∣∣∣−1

2

f ′′(ηn)

f ′(xn)(x∗ − xn)2

∣∣∣∣ , ηn ∈ I{x∗, xn}

donde resulta imediatamente o pretendido.

Luısa Morgado Equacoes nao lineares

Page 36: Equações não Lineares

Equacoes nao lineares

No scilab:

Exemplo

Exercıcio 21 dos problemas propostos:

function y=f(x), y=5*10^(-2)-(4+x)./(((25-x)^2).*(30-x)), endfunction;

x=[10:0.1:20];

plot(x,f(x));

f(18)

f(19)

x0=19;it=1;tol=1;

while tol>10^(-8)

xi=x0+(f(x0))/(((25-x0)*(30-x0)+2*(4+x0)*(30-x0)+(4+x0))/((25-x0)^3*(30-x0)^2));

tol=abs(xi-x0);

printf(’it=%d\n’,it);

printf(’xi=%f\n’,xi);

x0=xi;

it=it+1;

end;

Luısa Morgado Equacoes nao lineares

Page 37: Equações não Lineares

Equacoes nao lineares

Metodo da secante

Este metodo conjuga a simplicidade do metodo da biseccao com arapidez do metodo de Newton, evitando as dificuldades desteultimo nos pontos onde nao se pode calcular a derivada.

Deduz-se tal como o metodo de Newton,mas em vez da tangente consideramos ainterseccao da recta secante que passapelos pontos (xn, f (xn)) e (xn−1, f (xn−1))com o eixo dos xx .obtendo-se a seguinte formula derecorrencia:

xn+1 = xn −f (xn)

f (xn)− f (xn−1)(xn − xn−1)

Tal como no metodo da bisseccao, este requer duas aproximacoesiniciais.

Luısa Morgado Equacoes nao lineares

Page 38: Equações não Lineares

Equacoes nao lineares

Condicao suficiente de convergencia:f contınua em [a, b]f (a)f (b) < 0f ′(x), f ′′(x) 6= 0,∀x ∈ [a, b]f (x−1)f ′′(x) > 0 e f (x0)f ′′(x) > 0, ∀x ∈ [a, b]

Inicializacao:x0 e x−1

Ciclo:Para m ≥ 0 fazer

xm+1 = xm − f (xm) xm−xm−1

f (xm)−f (xm−1)

ate|xm+1 − xm| ≤ ε ou f (xm+1) ≤ ε

Metodo da secante

Luısa Morgado Equacoes nao lineares

Page 39: Equações não Lineares

Equacoes nao lineares

Pode provar-se que

|x∗ − xn+1| ≤1

2

maxx∈[a,b] |f ′′(x)|minx∈[a,b] |f ′(x)|

|x∗ − xn| |x∗ − xn−1|

e que o metodo da secante tem convergencia supra-linear, naochegando a ser quadratica.Mais ainda, pode provar-se que a ordem de convergencia dometodo da secante e

p = Φ =1 +√

5

2,

o numero de ouro.

Luısa Morgado Equacoes nao lineares

Page 40: Equações não Lineares

Equacoes nao lineares

No scilab:

Exemplo

Exercıcio 30 dos problemas propostos:

function y=f(x), y=sqrt(x).*log(10000./2.51*sqrt(x))-1.1513, endfunction;

x=[0.01:0.001:0.05]’;

plot(x,f(x));

clf();

function

z=df(x), z=0.5*x^(-0.5).*(1+log(10000./2.51*sqrt(x))),

endfunction;

plot(x,df(x));

clf();

function

w=d2f(x), w=0.5.*x^(-0.5).*(-0.25*x^(-1).*(1+log(10000./2.51*sqrt(x)))+1),

endfunction;

plot(x,d2f(x));

f(0.01)

f(0.02)

f(0.05)

xm1=0.01;x0=0.02;it=1;tol=1;

while tol>10^(-8)

xi=x0-f(x0)*((x0-xm1)/(f(x0)-f(xm1)));tol=abs(xi-x0);

printf(’it=%d\n’,it);

printf(’xi=%0.8f\n’,xi);

xm1=x0;

x0=xi;

it=it+1;

end;

Luısa Morgado Equacoes nao lineares

Page 41: Equações não Lineares

Equacoes nao lineares

Equacoes algebricas

Um caso particular frequente de equacao nao linear e a equacaoalgebrica de grau n, com coeficientes reais:

p(x) = a0xn + a1xn−1 + · · ·+ an−1x + an = 0, a0 6= 0

Existem formulas de resolucao para n ≤ 4, mas sao em geral, dedifıcil implementacao e por vezes mal condicionadas do ponto devista numerico. Desta forma, e costume recorrer-se aos metodosnumericos para n ≥ 3, sendo estes obrigatorios sempre que n ≥ 5.

Luısa Morgado Equacoes nao lineares

Page 42: Equações não Lineares

Equacoes nao lineares

Teorema Fundamental da Algebra

Seja p(x) um polinomio de grau n ≥ 1 de coeficientes reais.Entao existe x∗ ∈ C tal que p(x∗) = 0.

E seus corolarios:

Se p(x) e um polinomio de grau n de coeficientes reais, entaop(x) admite n zeros, reais ou complexos, iguais ou distintos.

Um polinomio de grau ımpar admite pelo menos um zero real.

Luısa Morgado Equacoes nao lineares

Page 43: Equações não Lineares

Equacoes nao lineares

Teorema de Cauchy

Todos os zeros x∗ do polinomio p(x) =n∑

j=0

aj xn−j , com a0 6= 0, estao no interior

do circulo (do plano complexo) centrado na origem e raio

R = 1 + maxj=1,...,n

{∣∣∣∣ aj

a0

∣∣∣∣}

E seu corolario:

Os zeros x∗ do polinomio p(x) =n∑

j=0

aj xn−j , com a0 6= 0 e an 6= 0, estao no exterior

do circulo (do plano complexo) centrado na origem e raio

r =1

1 + maxj=0,...,n−1

{∣∣∣∣ aj

an

∣∣∣∣}

Luısa Morgado Equacoes nao lineares

Page 44: Equações não Lineares

Equacoes nao lineares

Exemplo

Localizemos os zeros dep(x) = 8x6 − 4x5 − 22x4 + 5x3 − 3x2 + 9x + 27.

R = 1 + max

{27

8,

9

8,

3

8,

5

8,

22

8,

4

8

}= 1 +

27

8=

35

8

r =1

1 + max

{8

27,

4

27,

22

27,

5

27,

3

27,

9

27

} =1

1 +22

27

=27

49

entao

0.55 =27

44< |x∗| < 35

8= 4.375

Luısa Morgado Equacoes nao lineares

Page 45: Equações não Lineares

Equacoes nao lineares

Regra de sinais de Descartes

O numero np de zeros reais positivos de um polinomio p(x) emenor ou igual ao numero de variacoes de sinal ν dos coeficientesde P(x). Mais ainda, ν−np e um inteiro par positivo. Da mesmamaneira, o numero de zeros reais negativos de P(x) e no maximoigual ao numero de variacoes de sinal dos coeficientes de P(−x).

Exemplo

p(x) = x4 − x3 − x2 + x − 1. Temos entao

1 3 zeros reais positivos um zero real negativo, ou

2 1 zero real positivo, 1 zero real negativo e dois zeros complexos conjugados.

Luısa Morgado Equacoes nao lineares

Page 46: Equações não Lineares

Equacoes nao lineares

Teorema de Newton

Se em c > 0 o polinomio p(x) =n∑

j=0

aj xn−j , com a0 > 0 e as suas sucessivas

derivadas pj (x), j = 1, 2, . . . , n − 1 sao nao negativas, entao qualquer zero realpositivo x∗ de p(x) e inferior a c.

Chamamos sequencia de Fourier de p(x) em [a, b], a sequencia formada por p epelas sucessivas derivadas p′, p′′, . . . , p(k) ate a primeira derivada p(k) que tem sinalconstante em [a, b].

O numero de raızes reais de p(x) = 0 em [a, b], onde p(a) 6= 0 e p(b) 6= 0, e igualao numero de variacoes de sinal perdidas pela sequencia de Fourier de p(x) de apara b ou um numero inferior e da mesma paridade.

Este ultimo resultado e o conhecido teorema de Fourier.

Luısa Morgado Equacoes nao lineares

Page 47: Equações não Lineares

Equacoes nao lineares

No caso de se pretender obter um zero real simples de umaequacao algebrica qualquer dos metodos numericos apresentadosanteriormente sao validos. No entanto para se determinar um zerocomplexo o metodo da bisseccao nao pode ser usado. O metodode Newton e o metodo da secante so convergirao para um zerocomplexo se a aproximacao inicial for um complexo (e obviamenteforem satisfeitas as condicoes de convergencia) sendo todo oprocesso realizado em aritmetica complexa. Note-se que uma vezdeterminada uma raız complexa, ficamos imediatamente aconhecer a sua conjugada.

Luısa Morgado Equacoes nao lineares