Métodos Numéricos para Encontrar Zeros de Função: Método da Bisseção e Critérios de Parada

4 2 5 1 0011 0010 MÉTODOS NUMÉRICOS PARA ENCONTRAR ZERO DE FUNÇÃO 4 2 5 1 0011 0010 CRITÉRIOS DE PARADA Durante a aplicação de um método para determinarse a raíz necessitamos que uma certa condição seja satisfeita para estabelecer se o valor de xi está suficientemente próximo de r O valor de xi é raiz aproximada com precisão e se i e r xi ii e ix f 4 2 5 1 0011 0010 r ix fx x e e r x x f i i r ix x fx e e i i x f r x 4 2 5 1 0011 0010 e i 1 i x x e i i i x x x 1 Como não conhecemos o valor da raiz r para aplicar o teste i xi r e usamos freqüentemente os conceitos de erro absoluto e erro relativo para determinarmos o critério de parada a Erro absoluto b Erro relativo 4 2 5 1 0011 0010 2 Método da Bisseção 4 2 5 1 0011 0010 CONDIÇÕES DE APLICAÇÃO A função deve ser contínua no intervalo a b onde contém pelo menos uma raiz ou seja f a f b 0 Caso o intervalo contenha duas ou mais raízes o método encontrará uma delas 4 2 5 1 0011 0010 OBJETIVO DO MÉTODO DA BISSEÇÃO O objetivo deste método é reduzir a amplitude do intervalo inicial que contém a raiz até que seu comprimento seja menor que a precisão desejada usando para isso sucessivas divisões de a b ao meio 4 2 5 1 0011 0010 fx x Iteração 1 r a0 b0 x0 a1 b1 x0 a0 b0 2 f x0 0 a1 a0 b1 x0 r a1 b1 Iteração 2 x1 a1 b1 2 x1 f x1 0 a2 x1 a2 b2 b1 b2 r a2 b2 Iteração 3 x2 a2 b2 2 x2 f x2 0 a3 x2 a3 b3 b2 b3 r a3 b3 INTERPRETAÇÃO GEOMÉTRICA 4 2 5 1 0011 0010 Seja f x contínua em a b e tal que f a f b 0 1 Dados iniciais a intervalo inicial a b b precisão e 2 Se b a e então escolha para r FIM x a b 3 k 1 4 2 b a xk 5 Se faça Vá para o passo 7 0 kx f a f kx a 6 kx b 7 Se a b e escolha para r FIM x a b 8 k k 1 Volte ao passo 4 ALGORITMO 4 2 5 1 0011 0010 e 50 2 52 52 2 52 2 0 52 0 3 0 2 52 2 3 2 1 1 0 b a r f f f x EXEMPLO Use o método da Bisseção para calcular a raiz da função f x lnx senx que possui uma raiz única r 2 3 até que seja satisfeita a seguinte condição bi ai e para e 01 e 0 25 2 2 25 25 2 2 2 25 2 0 2 25 0 2 0 52 25 2 2 52 2 2 2 1 b a r f f f x Iteração 1 Iteração 2 4 2 5 1 0011 0010 e 0 0625 2 25 2 1875 25 2 1875 2 2 1875 2 25 0 2 1875 0 2 25 0 2 125 2 1875 2 2 25 125 2 4 4 3 b a r f f f x Iteração 4 3 2 1875 x r e 0 125 2 25 2 125 25 2 125 2 2 125 2 25 0 2 125 0 2 25 0 2 2 125 2 2 25 2 3 3 2 b a r f f f x Iteração 3 4 2 5 1 0011 0010 ESTIMATIVA DO NÚMERO DE ITERAÇÕES Dada uma precisão e e um intervalo a b vamos determinar quantas iterações k serão efetuadas pelo método da Bisseção até que bk ak e Sendo k um número inteiro a0 0b a1 1 b 2 a b 0 0 a2 2b 2 0 0 1 1 2 a b 2 a b a3 3 b 3 0 0 2 2 2 a b 2 a b k 0 0 2 b a 4 2 5 1 0011 0010 k a b k 2 log log log 0 0 e Devese obter o valor de k tal que ou seja e k k a b e e 0 0 0 0 2 2 a b a b k k e 0 0 log log2 a b k 4 2 5 1 0011 0010 Exemplo Determine o mínimo de iterações que são necessárias para determinarmos a raiz r 10 20 da função log com uma precisão e 106 2 x x sen x e y x 4 2 5 1 0011 0010 MÉTODO DA ITERAÇÃO LINEAR MÉTODO DO PONTO FIXO 4 2 5 1 0011 0010 Seja f x uma função contínua em a b intervalo que contém uma raiz r da equação f x 0 O Método da Iteração Linear MIL ou MPF consiste em transformar f x 0 em uma equação equivalente x jx onde jx é uma função de iteração A partir de uma aproximação inicial xi gerar uma seqüência xk de aproximações sucessivas através do processo iterativo dado por 2 1 1 i x x i i j 4 2 5 1 0011 0010 0x 1x 2x r x y x y j fx x INTERPRETAÇÃO GEOMÉTRICA Graficamente uma raiz da equação x jx é a abcissa do ponto de intersecção da reta y x e da curva y jx 4 2 5 1 0011 0010 x 0x 1x fx x j 2x Não Converge x 0x 1x 2x fx x j Não Converge x 0x 1x 2x fx x j Converge fx x 0x 1x x j Converge 2 x Analisemos alguns casos de função de iteração 4 2 5 1 0011 0010 ESTUDO DA CONVERGÊNCIA DO MIL Para que o MIL forneça uma solução da equação f x 0 é necessário que a seqüência gerada xk dada por seja convergente A convergência será dada pelo seguinte teorema Seja r uma raiz da equação f x 0 isolada num intervalo I centrado em r Seja jx uma função de iteração para a equação f x 0 Se então a seqüência xk gerada converge para a raiz r 1 k k x x j i jx e são contínuas em I x j I x M x 1 j ii x I iii 0 4 2 5 1 0011 0010 Considere a equação f x 0 e a equação equivalente x jx 1 Dados iniciais 0x a aproximação inicial 2 Se faça FIM 1 0 e f x 0x r 3 i 1 4 0 1 x x j 5 Se 1 1 e x f ou se 2 0 1 x e x então faça FIM 1x r 6 1 0 x x 7 i i 1 Volte ao passo 4 b e precisões 1e 2 e ALGORITMO 4 2 5 1 0011 0010 C e e p k k k lim 1 2 k C e e p k k para 1 ORDEM DE CONVERGÊNCIA Definição Seja xk uma seqüência que converge para um número r e seja o erro na iteração k Se existir um número p 1 e uma constante C 0 tais que então p é chamada de ordem de convergência da seqüência xk e C é a constante assintótica de erro Uma vez obtida a ordem de convergência p de um método iterativo ela nos dá uma informação sobre a rapidez de convergência do processo De 2 podemos escrever r x e k k 4 2 5 1 0011 0010 O MIL TEM CONVERGÊNCIA APENAS LINEAR Então para grandes valores de k o erro em qualquer iteração é proporcional ao erro na iteração anterior sendo jr o fator de proporcionalidade 1 e lim 1 C C r e e k k k j 4 2 5 1 0011 0010 MÉTODO DE NEWTONRAPHSON 4 2 5 1 0011 0010 1 I x M x j A x f x x x j 1 x A x f A x f x x j 1 1 r A r f r r A r f A r f r r j j No estudo do método do ponto fixo vimos que i uma das condições de convergência é que onde I contém a raiz r ii a convergência do método será mais rápida quanto menor for jr Com a finalidade de acelerar e garantir a convergência o MNR procura uma função de iteração jx tal que jr 0 Partindo da forma geral para jx iremos obter a função Ax tal que jr 0 4 2 5 1 0011 0010 x f f x x x j 2 2 2 1 x f x x f f x f x f x f x f x j 1 0 1 0 r f A r r A r f r j 1 x f A x 0 desde que r f 0 2 r f r f r f r j Assim donde tomamos Então dada f x a função de iteração representada por será tal que jr 0 pois como podemos verificar 4 2 5 1 0011 0010 0 x 1x 2x 0 L 1 L fx x f x r i i x f x x Li i i i i x x x f f x L x INTERPRETAÇÃO GEOMÉTRICA Dado o ponto traçamos a reta tangente à curva neste ponto dado por 4 2 5 1 0011 0010 ESTUDO DA CONVERGÊNCIA DO MNR 4 2 5 1 0011 0010 Seja f x 0 1 Dados iniciais a aproximação inicial 0x b precisão 1e 2 Se faça FIM erro 1e 0x r 3 k 1 4 0 0 0 1 x f f x x x 5 FIM faça Se 1 1 0 1 x r x x e 6 1 0 x x 7 k k 1 Volte ao passo 4 c erro erro inicial ALGORITMO 4 2 5 1 0011 0010 O MNR TEM CONVERGÊNCIA QUADRÁTICA Para i suficientemente grande o erro da iteração do MNR é proporcional ao quadrado do erro da iteração anterior Por isso dizse que a convergência é quadrática ou seja p 2 2 1 i i C e e C e e i i i 2 1 lim 4 2 5 1 0011 0010 Exemplo Encontre a raiz para a seguinte equação utilizando do MNR com um erro de 001 0 6 3 x x 4 2 5 1 0011 0010 OBJETIVO O objetivo do Método da Secante é eliminar a necessidade de se conhecer a derivada analítica da função que se deseja obter a raiz 4 2 5 1 0011 0010 Se fx é uma função contínua no intervalo ab e derivável em ab então existe um número c ab tal que TEOREMA DO VALOR MÉDIO a b f a f b f c 4 2 5 1 0011 0010 Considerando a fórmula de NewtonRaphson substituímos a derivada pela expressão do teorema do valor médio MÉTODO DA SECANTE n n n n n n n n n n n x x f x x f f x x x x f f x x x 1 1 1 1 4 2 5 1 0011 0010 n n n n n n n n n n n x x f x x f f x x x x f f x x x 1 1 1 1 Rearranjando 𝑥𝑖1 𝑥𝑖 𝑓 𝑥𝑖 𝑓 𝑥𝑖 𝑓 𝑥𝑖1 𝑥𝑖 𝑥𝑖1 Note que são necessárias DUAS aproximações para iniciar o processo iterativo 4 2 5 1 0011 0010 MÉTODO DAS SECANTES 4 2 5 1 0011 0010 MÉTODO DAS SECANTES 4 2 5 1 0011 0010 INTERPRETAÇÃO GEOMÉTRICA 4 2 5 1 0011 0010 ESTUDO DE CONVERGÊNCIA DO MÉTODO DA SECANTE 4 2 5 1 0011 0010 Seja f x 0 ALGORITMO 1 Dados iniciais a 𝑥0 𝑥1 aproximações iniciais b 𝜀1 𝜀2 precisões 2 Se 𝑓𝑥0 𝜀1 faça 𝑟 𝑥0 FIM 3 Se 𝑓𝑥1 𝜀1 𝑜𝑢 𝑥1 𝑥0 𝜀2 faça 𝑟 𝑥1 FIM 4 k 1 5 𝑥2 𝑥1 𝑓 𝑥1 𝑓 𝑥1 𝑓 𝑥0 𝑥1 𝑥0 6 Se 𝑓𝑥2 𝜀1 𝑜𝑢 𝑥2 𝑥1 𝜀2 faça 𝑟 𝑥1 FIM 7 𝑥0 𝑥1 𝑥1 𝑥2 8 k k 1 Volte ao passo 5 4 2 5 1 0011 0010 Exemplo Encontre a raiz para a seguinte equação utilizando do Método da Secante com um erro de 001 0 6 3 x x