Baixe o app para aproveitar ainda mais
Prévia do material em texto
Zeros de Funções ReaisFunções Reais Métodos iterativos - Zeros I. Método da Bissecção II. Método da Posição Falsa III. Método do Ponto FixoIII. Método do Ponto Fixo IV. Método de Newton-Raphson V. Método da Secante Métodos iterativos - Zeros I. Método da Bissecção Seja com zero em As iterações são realizadas da forma 1) )(xf ( ) ∈ξ < + 000 ,0)( xaafba ],[ ba 1) 2) 3) Continue o processo até que e = = > >⇒== + = 01 01 0 000 00 0 0)( 0)( 2 xb aa xf bfSebbaabax então e com ( ) = = ∈ξ < > < ⇒ + = 12 12 11 1 1 1 11 1 , 0)( 0)( 0)( 2 bb xa bx xf bf af Sebax então ( ) ε<nn ba , ),( é nn bax∈∀ξ % Metodo da Bisseccao ( funcao bisseccao.m ) clc; clear all; format long; x0 = input('digite o limite inferior (a) = '); x1 = input('digite o limite superior (b) = '); e = input('digite o valor de epsilon(e) = '); max = input('digite o valor maximo de iteracoes = '); Código MatLab max = input('digite o valor maximo de iteracoes = '); x=sym('x'); f=x.^3-9.*x+3 %input('digite a expressao da funcao: '); f0=subs(f,x,x0); f1=subs(f,x,x1); if f0.*f1<0 & abs(x1-x0)/abs(x1)<e disp('CONVERGIU '); solucao=[0 xm fm abs(x1-x0)/abs(x1)]; fprintf('%6.5d %6.12e %6.12e %6.12e\n',solucao); break; end for k=1:max xm=(x0+x1)/2; fm=subs(f,x,xm); if f0.*fm<0 x1=xm; f1=fm; else x0=xm; f0=fm; end if abs(x1-x0)/abs(x1)<e disp('CONVERGIU '); solucao=[k xm fm abs(x1-x0)/abs(x1)];solucao=[k xm fm abs(x1-x0)/abs(x1)]; fprintf('%6.5d %6.12e %6.12e %6.12e\n',solucao); break; end solucao=[k xm fm abs(x1-x0)/abs(x1)]; fprintf('%6.5d %6.12e %6.12e %6.12e\n',solucao); end if k==max disp('NAO CONVERGIU '); end Métodos iterativos - Zeros II. Método da Posição Falsa Seja contínua em , tal que . Se preserva o sinal em então o intervalo contem uma única raiz )(xf ],[ ba 0)()( <bfaf )(xf ′ ),( ba ),( baentão o intervalo contem uma única raiz de . Objetivo: reduzir a amplitude do intervalo que contém a raiz até que , dividindo por meio de uma média aritmética ponderada em . ε<− )( ab ],[ ba )(xf ],[ ba ),( ba Métodos iterativos - Zeros II. Método da Posição Falsa Podemos esperar conseguir a raiz aproximada usando as informações sob os valores de disponíveis a cada iteração. )(xf disponíveis a cada iteração. Métodos iterativos - Zeros )(xf a b Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )(xf )( 0af b=b0 a=a0 Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )( 0xr )(xf )( 0af b=b0 a=a0 x0 fazendo ( )00 0 0 0 00 0000 0 , então 0)( 0)( 0)( Se )()( )()( xa xf bf af bfaf afbbfa x ∈ > > < ⇒ + + = ξdesconsidera este ponto Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )( 0xr )(xf )( 0af b=b0 a=a0 x0 Graficamente, o ponto é a intersecção entre o eixo x e a reta que passa por e ou equivalentemente e . 0x )( 0xr ( ))(, afa ( ))(, bfb( ))(, 00 afa ( ))(, 00 bfb Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )( 0xf )( 0xr )(xf )( 0af b=b0 a=a0 x0 fazendo ( )00 0 0 0 00 0000 0 , então 0)( 0)( 0)( Se )()( )()( xa xf bf af bfaf afbbfa x ∈ > > < ⇒ + + = ξdesconsidera este ponto Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )( 0xr )(xf )( 0af b=b0 a=a0 x0 fazendo ( )00 0 0 0 00 0000 0 , então 0)( 0)( 0)( Se )()( )()( xa xf bf af bfaf afbbfa x ∈ > > < ⇒ + + = ξdesconsidera este ponto Métodos iterativos - Zeros )( 0bf e 00 bbaa ==Considerando )( 0xr )(xf ξ )( 0af b=b0 a=a0 x0 fazendo ( )00 0 0 00 0000 0 , então 0)( 0)( Se )()( )()( xa xf af bfaf afbbfa x ∈ > < ⇒ + + = ξ Métodos iterativos - Zeros )( 1bf Considerando e 0101 xbaa == )(xf )( 1af a=a0=a1 x0=b1 Métodos iterativos - Zeros )( 1bf Considerando e 0101 xbaa == )(xf )( 1af a=a0=a1 x0=b1 fazendo ( )11 1 1 1 11 1111 1 , então 0)( 0)( 0)( Se )()( )()( bx xf bf af bfaf afbbfa x ∈ < > < ⇒ + + = ξ Métodos iterativos - Zeros )( 1bf Considerando )( 1xr e 0101 xbaa == )(xf )( 1af a=a0=a1 x0=b1 fazendo ( )11 1 1 1 11 1111 1 , então 0)( 0)( 0)( Se )()( )()( bx xf bf af bfaf afbbfa x ∈ < > < ⇒ + + = ξ Métodos iterativos - Zeros )( 1bf Considerando )( 1xr e 0101 xbaa == )(xf )( 1af a=a0=a1 x0=b1 fazendo ( )11 1 1 1 11 1111 1 , então 0)( 0)( 0)( Se )()( )()( bx xf bf af bfaf afbbfa x ∈ < > < ⇒ + + = ξContinua o processo até que ε<)( kxf kx=ξ Método da Posição Falsa II. Método da Posição Falsa Seja com um zero em . As iterações são realizadas da forma )(xf ],[ ba 1) 2) Continue o processo até que e . ( ) = = ∈ξ > > < ⇒ + + = 01 01 00 0 0 0 00 0000 0 , 0)( 0)( 0)( )()( )()( xb aa xa xf bf af bfaf afbbfa x então Se ε<)( kxf kx=ξ Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Obtemos em três iterações. O Método da bissecção necessitava de 10 iterações para tal precisão. 3376.0=x Iteração ak bk xk f(xk) bk-ak k=1 0 1 0.375 -3.2226 0.375 k=2 0 0.375 0.3386 -8.7902X10-3 0.3386 k=3 0 0.3386 0.3376 -2.2588X10-4 0.3376 Um dos critérios de parada foi atingido Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Obtemos em três iterações. O Método da bissecção necessitava de 10 iterações para tal precisão. 3376.0=x Iteração ak bk xk f(xk) bk-ak k=1 0 1 0.375 -3.2226 0.375 k=2 0 0.375 0.3386 -8.7902X10-3 0.3386 k=3 0 0.3386 0.3376 -2.2588X10-4 0.3376 Um dos critérios de parada foi atingido Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Obtemos em três iterações. O Método da bissecção necessitava de 10 iterações para tal precisão. 3376.0=x Iteraçãoak bk xk f(xk) bk-ak k=1 0 1 0.375 -3.2226 0.375 k=2 0 0.375 0.3386 -8.7902X10-3 0.3386 k=3 0 0.3386 0.3376 -2.2588X10-4 0.3376 Um dos critérios de parada foi atingido Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Iteração ak bk xk f(xk) bk-ak k=1 0 1 0.375 -3.2226 0.375 k=2 0 0.375 0.3386 -8.7902X10-3 0.3386 k=3 0 0.3386 0.3376 -2.2588X10-4 0.3376 Um dos critérios de parada foi atingido Método da Posição Falsa II. Método da Posição Falsa - Exemplo Seja com e . Temos . 39)( 3 +−= xxxf ]1,0[=I 310−=ε 0)1(e0)0( <> ff Obtemos em três iterações. O Método da bissecção necessitava de 10 iterações para tal precisão. 3376.0=x Iteração ak bk xk f(xk) bk-ak k=1 0 1 0.375 -3.2226 0.375 k=2 0 0.375 0.3386 -8.7902X10-3 0.3386 k=3 0 0.3386 0.3376 -2.2588X10-4 0.3376 Um dos critérios de parada foi atingido Método da Posição Falsa I. Estudo da Convergência Teorema: O método da posição falsa gera uma sequência convergente se for contínua em )(xfsequência convergente se for contínua em com e se preserva o sinal em . Comentário: A convergência é mais rápida que no método da bisecção. )(xf ],[ ba 0)()( <bfaf )(xf ′ ),( ba Método do Ponto Fixo (MPF) � Seja contínua em , intervalo este contendo uma raiz da equação . )(xf ],[ ba 0)( =xf � O MPF consiste em transformar esta equação em uma equação equivalente e a partir de um gerar uma sequência de aproximações para através da relação => Processo Recursivo )(xx ϕ= 0x }{ kxξ )(1 kk xx ϕ=+ Método do ponto fixo (MPF) - Graficamente Método do ponto fixo (MPF) � Exemplo1. Considere a equação 062 =−+ xx −= 6)( 21 xxϕ � Possíveis funções de iterações + = −= −±= −= 1 6)( 16)( 6)( 6)( 4 3 2 1 x x x x xx xx ϕ ϕ ϕ ϕ Método do ponto fixo (MPF) � Exemplo1. Considere a equação 062 =−+ xx 22 6 06 xxxx −=⇒=−+ xxxxxx −±=⇒−=⇒=−+ 6 6 06 22 )1( 6 06)1( 062 x xxxxx + =⇒=−+⇒=−+ xxxxxx −±=⇒−=⇒=−+ 6 6 06 22 16 061 062 −=⇒=−+⇒=−+ x x x xxx Método do ponto fixo (MPF) � Forma geral das funções de iteração: )()()( xfxAxx +=ϕ com a condição . Exemplo: 0)( ≠ξA )6(6)( 606 22 )( 22 −+−=−=⇒ −=⇒=−+ xxxxx xxxx x ϕ ϕ 321 Método do ponto fixo (MPF) � As raízes da equação são e . Consideremos e a função de iteração . Tomando 062 =−+ xx 31 −=ξ 22 =ξ 22 =ξ 2 1 6)( xx −=ϕ 5.1=x , temos5.10 =x )(1 kk xx ϕ=+ −=−−== −=−== =−== M 003906.59)0625.8(6)( 0625.8)75.3(6)( 75.3)5.1(6)( 2 23 2 12 2 01 xx xx xx ϕ ϕ ϕ não está convergindo para}{ kx 22 =ξ Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x0 x Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x0 x Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x0 x x1 Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x0 x x1 Método do ponto fixo (MPF) - Graficamente 2 1 6)( xx −=ϕ x0 x x1 Método do ponto fixo (MPF) - Graficamente x2 2 1 6)( xx −=ϕ x0 não está convergindo para}{ kx 22 =ξ Método do ponto fixo (MPF) - Graficamente xx −= 6)(2ϕ xx0 Método do ponto fixo (MPF) - Graficamente xx −= 6)(2ϕ xx0 Método do ponto fixo (MPF) - Graficamente xx −= 6)(2ϕ xx0 Método do ponto fixo (MPF) - Graficamente xx −= 6)(2ϕ xx0 Método do ponto fixo (MPF) � Consideremos agora a função de iteração com xx −= 6)(2ϕ 5.10 =x =−=ϕ= 12132.25.16)( 01 xx )(1 kk xx ϕ=+ =−=ϕ= =−=ϕ= =−=ϕ= =−=ϕ= M 00048.299809.16)( 99809.100763.26)( 00763.296944.16)( 96944.112132.26)( 45 34 23 12 01 xx xx xx xx está convergindo para}{ kx 22 =ξ Método do ponto fixo (MPF) � Teorema: Seja uma raiz da equação , isolada num intervalo I centrado em . E seja uma função de iteração de . ξ 0)( =xf ξ )(xϕ uma função de iteração de . Se (i) e são contínuas em I, (ii) e (iii) , então converge para . )(xϕ′)(xϕ IxMx ∈∀<≤′ ,1|)(|ϕ Ix ∈0 }{ kx ξ 0)( =xf Método do ponto fixo (MPF) � Demonstração do teorema MPF: � 1ª parte: se , então . Se , então: . Ix ∈0 ( )ξϕ=ξ⇒=ξ 0)(f ℑ∈∀∈ kIxk , ( ) ( )ξϕ−ϕ=ξ−+ kk xx 1Se , então: . Do Teorema do Valor Médio, se é contínua e diferenciável, então: Obs: O intervalo seguinte é menor e centrado em . )(xϕ ( )ξϕ=ξ⇒=ξ 0)(f ( ) ( )ξϕ−ϕ=ξ−+ kk xx 1 ( )[ ]( ) ( )ξ∈ξ−ϕ′=ξ−+ ,1 kkkkk xcxcx ( ) ( )[ ] IxIxcxx kkkkk ∈⇒∈<ϕ′ξ−<ξ− ++ 11 Se.1pois ξ Método do ponto fixo (MPF) � Demonstração do teorema MPF: � 2ª parte: Provar que .ξ= ∞→ kk xLim ( )ξ−≤ξ− xMx Obs: Como , então . ( )ξ−≤ξ− 01 xMx ( ) ( )ξ−≤ξ−≤ξ− 0212 xMxMx ( ) ( )ξ−≤ξ−≤ξ− − 01 xMxMx k kk 10 <<M ξ= ∞→ kk xLim Estudo da Convergência do MPF � Estudo da raiz da equação quando consideramos a função de iteração 062 =−+ xx2=ξ 2 1 6)( xx −=ϕ � A- e são contínuas. � B- . Não existe intervalo em torno de que satisfaça a condição do teorema MPF. 2 1 6)( xx −=ϕ xx 2)(1 −=′ϕ 2 1 2 11)(1 << − ⇔<′ϕ xx 2=ξ Estudo da Convergência do MPF � Estudo da raiz da equação quando consideramos a função de iteração 062 =−+ xx2=ξ xx −=ϕ 6)(2 � A- e são contínuas se . Em torno de a condição é satisfeita. � B- No intervalo em torno de a condição do teorema MPF é satisfeita. 6<x 2=ξ xx −=ϕ 6)(2 ( ) 12 62)( −−−=′ϕ xx ( ) 75.51621)( 12 <⇒<−⇒<′ϕ − xxx 2=ξ Método do ponto fixo (MPF) � Critérios de Parada do MPF Critério 1: ( ) ε<−ϕ=− −−− 111 kkkk xxxxCritério 1: Critério2: ( ) ε<−ϕ=− −−− 111 kkkk xxxx ( ) ε<kxf Método do ponto fixo (MPF) � Exemplo do critério de parada do MPF � Seja a função com equação equivalente , e . ( ) 393 +−= xxxf ( ) 3/19/3 +=ϕ xx ( ) 5.0com1,0 0 =∈ξ x 4105 −×=εe .105×=ε Iteração x f(x) 1 0.3472 -0.8314X10-1 2 0.3380 -0.3253X10-2 3 0.3376 -0.1240X10-3 ε=<==−=− −− 4423 10x510x40004.03380.03376.0xx Método do ponto fixo (MPF) � Ordem de convergência Seja uma sequência que converge para e seja o erro na iteração . Se existir um número { }kx ξ−=ε kk x ξ k 1≥p e uma constante , tais que Então é chamada de ordem da convergência e é a constante assintótica. CLim p k k k = ε ε + ∞→ 1 0>C p C Método do ponto fixo (MPF) � Do Teorema doValor Médio, se é contínua e diferenciável, então )(xϕ ( )[ ]( ) ( )ξ∈ξ−ϕ′=ξ−+ ,1 kkkkk xcxcx � Ordem de convergência do MPF Vimos que no MPF para que haja convergência ( ) ( ) 11 <ξϕ′=ϕ′= ξ− ξ− ∞→ + ∞→ kk k k k cLim x x Lim ( )[ ]( ) ( )+ ,1 kkkkk xcxcx Método do ponto fixo (MPF) Obs1: O MPF converge linearmente. Obs2: A convergência é mais rápida quanto menor for o valor de . ( )ξϕ′ Método Newton-Raphson (MNR) Vimos que no MPF, para que haja convergência, 1: e 2: a convergência é mais rápida quanto menor for o valor de . ( )ξϕ′ ( ) 1<ξϕ′ valor de . O MNR é MPF com convergência acelerada. Consiste em escolher tal que . ( )ξϕ′ ( ) 0=ξϕ′( )ξϕ Método Newton-Raphson (MNR) Temos para o Método de Newton-Raphson ( ) ( ) ( ) ( ) )()()()(1)()( xfxAxfxAxxfxAxx ′+′+=′⇒+= ϕϕ ( ) ( ) ( ) ( ) )( )( )( 1)( Logo, )( 1)(0)()(10 Queremos )()(1)()()()(1 xf xf xx xfxA fAfA fAfAfA ′ −=⇒ ′ − = ′ − =⇒=′+⇒=′ ′+=′⇒′+′+=′ ϕ ξξξξξϕ ξξξϕξξξξξϕ Método Newton-Raphson (MNR) Exemplo do Método de Newton-Raphson. Seja a função com . Seja . Do MNR devemos escolher a função equivalente ( ) 62 −+= xxxf 2=ξ 5.10 =x 6)( 2 −+ −=ϕ xxxxequivalente Obtemos � A convergência do MNR é mais rápida que aquela do MPF 12 6)( + −+ −=ϕ x xx xx 0625.2)5.1(1 =ϕ=x5.10 =x 0008.2)0625.2(2 =ϕ=x 0000.2)0008.2(3 =ϕ=x Método Newton-Raphson (MNR) Teorema: Sejam contínuas num intervalo que contem a raiz de . Suponha que , então existe um intervalo contendo a raiz , tal que se , a ξ=x )(),(),( xfxfxf ′′′ 0)( =xf Ix ∈0 I 0)( ≠ξ′f II ⊂ ξcontendo a raiz , tal que se , a sequência gerada pela fórmula recursiva , convergirá para a raiz. Ix ∈0 { }kx II ⊂ ξ )( )( 1 k k kk xf xf xx ′ −=+ Método Newton-Raphson (MNR) � Ordem de convergência do MNR Suponha que o MNR gere uma sequência que converge para . A ordem de convergência do MNR é { }kxξconverge para . A ordem de convergência do MNR é quadrática. Comentário: A ordem de convergência do MPF é linear, mas o fato da exigência de , faz a convergência do MNR ser quadrática. ξ ( ) 0=ξϕ′ Método da Secante No método de Newton há a necessidade de calcular e o seu valor numérico a cada iteração. Esta é uma desvantagem do MNR. O Método da Secante substitui a derivada ( )xf ′ O Método da Secante substitui a derivada pela secante. Assim ( ) ( ) ( ) ( ) ( ) ( ) ( )1 11 1 1 1 − −− − − + − − = − − −= kk kkkk kk kk k kk xfxf xfxxfx xx xfxf xf xx Método da Secante No método de Newton há a necessidade de calcular e o seu valor numérico a cada iteração. Esta é uma desvantagem do MNR. O Método da Secante substitui a derivada ( )xf ′ O Método da Secante substitui a derivada pela secante. Assim Note que são necessárias duas aproximações para iniciar o Método da Secante. ( ) ( ) ( ) ( ) ( ) ( ) ( )1 11 1 1 1 − −− − − + − − = − − −= kk kkkk kk kk k kk xfxf xfxxfx xx xfxf xf xx Método da Secante Exemplo do Método da Secante Seja a função com . Seja e . Do Método da Secante obtemos a seqüência ( ) 62 −+= xxxf 2=ξ 5.10 =x 7.11 =x 7.11 =x 5.10 =x ( ) ( ) ( ) ( ) ( ) ( ) 0335.2 25.241.1 25.27.141.15.1 01 0110 2 = +− −−− = − − = xfxf xfxxfx x ( ) ( ) ( ) ( ) ( ) ( ) 9977.1 41.11798.0 41.10357.21798.07.1 12 1221 3 = + −− = − − = xfxf xfxxfx x ( ) ( ) ( ) ( ) 0000.223 2332 4 = − − = xfxf xfxxfx x Método da Secante Ordem de Convergência do Método da Secante Mostra-se que a ordem de convergência do Método da Secante é maior que aquela do MPF (p=1) e menor que aquela do MNR (p=2). Verifica-se que a ordem de convergência do Método da Secante é p=1.618 ... Comparação dos Métodos � O MPF, MNR e MS têm convergência mais rápida que os Métodos da Bissecção e da Posição Falsa, considerando apenas o número de iterações. � Por outro lado, o MNR é aquele que efetua o maior número de operações, pois calcula o valor da número de operações, pois calcula o valor da derivada de f(x) a cada iteração. � O esforço computacional depende do número de operações efetuadas a cada iteração, a complexidade destas operações, de número de decisões lógicas, do número de avaliações de funções a cada iteração e do número de iterações. Comparação dos Métodos No caso geral, não há método melhor!!!!! Obs: Se o cálculo da derivada de f(x) não for muito elaborado, o MNR é indicado, caso contrário o MS é aconselhável. Exercícios Resolver os seguintes exercícios do capítulo 2 11, 12, 16, 19
Compartilhar