PRÓ-REITORIA DE GRADUAÇÃO BACHARELADO EM CIÊNCIA E TECNOLOGIA INFORMÁTICA MÉTODOS NUMÉRICOS DE DETERMINAÇÃO DE RAÍZES: BISSEÇÃO, SECANTE E NEWTON-RAPHSON Professor.: Aquiles Burlamaqui CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa METODOLOGIA Aulas Teórico-Práticas: Em todas as aulas haverão uma discussão inicial, onde serão construídos os conceitos assim como as atividades práticas que servirão como parâmetros para avaliação. Avaliação: A avaliação será feita em cima das prática vistas em sala de aula assim como provas escritas e participação, de maneira a avaliar o aluno continuamente. “Eu escutei e esqueci. Eu vi e lembrei. Eu fiz e Entendi.” Confucius CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa CONTEXTO DA AULA NA DISCIPLINA Esta aula de está inserida no contexto da disciplina de Cálculo Numérico cujos objetivos são: Apresentar o cálculo do ponto de vista computacional. Desenvolver as técnicas destinadas a compensar as restrições das representações numéricas. Pré-requisitos: Cálculo I Introdução à Programação 6 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa BIBLIOGRAFIA Rugiero, Márcia A. G. & Lopes, Vera L.R. Cálculo Numérico: Aspectos Teóricos e Computacionais. 2 ed. Makron Books, 1996. Sperandio, Décio et al. Cálculo Numérico: Características Matemáticas e Computacionais. Prentice-Hall, 2003. Franco, Neide M.B.. Cálculo Numérico. PrenticeHall, 2006. 8 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa MOTIVAÇÃO A busca por zeros de funções: - em diversas áreas da ciência, surgem modelos matemáticos definidos por uma equação do tipo f(x) = 0 Algumas funções podem ter suas raízes calculadas analiticamente, porém outras são de difícil solução ou de solução desconhecida (polinômios de ordem maior que 3, por exemplo), sendo necessário a solução por métodos numéricos Desejamos portanto encontrar um valor x para x tal que f(x) = 0 Iremos discutir métodos numéricos de implementação computacionalmente viável para encontrar um valor para x dentro de um intervalo com uma precisão razoável 10 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa IDÉIA CENTRAL DOS MÉTODOS Fase I Localizar ou isolar uma região que contenha a raiz e definir um valor aproximado inicial Fase II Refinamento ou seja melhorar sucessivamente a aproximação inicial obtida na fase I até se obter uma aproximação para a raiz real dentro de uma precisão e prefixada 12 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE I Nesta fase fazemos uma análise teórica e gráfica da função f(x) O sucesso da fase II depende da precisão desta análise Usamos o Teorema de Cauchy: seja f(x) uma função contínua no intervalo [a, b] se f(a)f(b) < 0 então existe pelo menos um ponto x = x entre a e b que é zero de f(x) a prova deste teorema pode ser encontrada em [Guidorizzi, 2001] 14 FASE I : ANÁLISE GRÁFICA 15 Figuras extraídas de [Ruggiero, 1996] FASE I : ANÁLISE GRÁFICA se f(a)f(b) > 0 então podemos ter várias situações no intervalo [a, b]. Estas situações e a análise gráfica são 16 discutidas com mais detalhes em [Guidorizzi, 2001] e Figuras extraídas de [Ruggiero, 1996] [Leithold, 1994] FASE I : ANÁLISE GRÁFICA Vimos portanto, que a análise gráfica do função f(x) é fundamental para se obter boas aproximações para a raiz É suficiente o uso de um dos processos a seguir: i ) Esboçar o gráfico de f(x) e localizar a região onde a curva intercepta o eixo das abcissas; ii ) A partir da equação f(x) = 0 obter a equação equivalente g(x) = h(x) e esboçar seus gráficos. Os pontos de cruzamento das curvas são os zeros procurados, pois f(x)=0 g(x) = h(x) iii ) Usar softwares para traçar gráficos 17 FASE I : EXEMPLO COM PROCESSO I 18 Figuras extraídas de [Ruggiero, 1996] FASE I : EXEMPLO COM PROCESSO II 19 Figuras extraídas de [Ruggiero, 1996] FASE I : TABELA DE VARIAÇÃO DO SINAL 20 Figuras extraídas de [Ruggiero, 1996] CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE II: REFINAMENTO Há vários métodos para refinamento da raiz Todos pertencem a classe dos métodos iterativos onde um conjunto de instruções é repetido formando cada passo ou ciclo Eles fornecem uma aproximação da raiz É importante: Definir o critério de parada Estudar a convergência e sua eficiência 22 CRITÉRIOS DE PARADA Existem vários tipo de critérios de parada f (x) Analise do valor da funcao: Erro absoluto: xi xi i Erro relativo: xi xi i xi ba Limites do intervalo: 2 FASE II: PSEUDO-CÓDIGO Ler dados iniciais Realizar cálculos e aproximação iniciais k=1 Enquanto !criterioSatisfeito E k < limMax criterioSatisfeito = calcularNovaAproximacao() k=k+1 Fim enquanto ExibirResultados() FASE 1 FASE 2 24 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE II: MÉTODO DA BISSEÇÃO Usando-se o teorema já apresentado se f(a)f(b) < 0 então existe pelo menos um ponto x = x entre a e b que é zero de f(x) Divide-se ao meio o intervalo [a, b] sucessivamente até que (b-a) < e Cada novo xk = (ak + bk)/2 será o novo ak+1 ou bk+1 de modo a manter válido o teorema acima 26 FASE II: MÉTODO DA BISSEÇÃO 27 Achar a raiz da equação f ( x) x3 10 no intervalo [2,3] com o erro absoluto 0,1 Ex: f (2) * f (3) 2 *17 0 x0 (2 3) / 2 2,5 f (2,5) 5,62 a 2 b3 x1 (2 2,5) / 2 2,25 f (2,25) 1,39 a 2 b 2,5 x2 (2 2,25) / 2 2,12 f (2,15) 0,40 a 2 b 2,25 x3 (2,12 2,25) / 2 2,18 f (2,18) 0,46 a 2,12 b 2,25 e 2,18 2,12 0,06 FASE II: MÉTODO DA BISSEÇÃO Vantagens: Simples Converge sempre Desvantagens: convergencia lenta 29 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE II: MÉTODO DE NEWTONRAPHSON Supondo uma aproximação x0 para a raiz de f(x), no ponto (x0, f(x0)) passa apenas uma única reta tangente, que é a derivada de f(x) em x0. Esta reta tangente corta o eixo x na coordenada x1,definindo por sua vez, o ponto (x1, f(x1)) Por este novo ponto também passa uma única reta tangente que corta o eixo x em x2. Esta nova coordenada define outro ponto (x2, f(x2)) que repete todo o processo x0,x1,... são aproximações cada vez melhores para a raiz da função, o Xk+1 pode ser obtido a partir do Xk através da função: 31 FASE II: MÉTODO DE NEWTONRAPHSON 32 FASE II: MÉTODO DE NEWTON-RAPHSON (FORMULAÇÃO E ANÁLISE GRÁFICA) 33 Figuras extraídas de [Ruggiero, 1996] FASE II: MÉTODO DE NEWTONRAPHSON Convergência Caso se escolha x0 de forma que x1 saia do intervalo [a,b] o método poderá não convergir. 2 f ( x ) x ln(x) Ex: Ache a raiz da equação para o erro relativo , ou seja: Se f ( x) x 2 ln(x) Então f ( x) 2 x 1 x x0=0,5 f (0,5) 0,44 x1 0,5 0,5 0,65 f (0,5) 3 f (0,65) x2 0,65 0,65 0,65 0,65 f (0,65) 0,01 0,65 FASE II: MÉTODO DE NEWTONRAPHSON Vantagens: Simples Rápida convergência Desvantagens: Nem sempre converge Necessidade de se conhecer a derivada da função Muito sensível à estimativa inicial Se a derivada for nula o método falha 36 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE II: MÉTODO DA SECANTE Uma grande desvantagem do método de Newton é a necessidade de se obter f’(x) e calcular seu valor numérico a cada iteração Uma forma de se contornar este problema é substituir a derivada f’(x) pelo quociente das diferenças f’(xk) ( f(xk) - f(xk-1) ) / ( xk - xk-1) 38 FASE II: MÉTODO DA SECANTE 39 FASE II: MÉTODO DA SECANTE 40 Figuras extraídas de [Ruggiero, 1996] FASE II: MÉTODO DA SECANTE Vantagens: Simples Rápida convergência como o método deNewton e não necessita do conhecimento da derivada da função Desvantagens: Nem sempre converge Muito sensível à estimativa inicial Se a derivada for nula o método falha 41 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa FASE II: COMPARAÇÃO ENTRE OS MÉTODOS APRESENTADOS O método da Bisseção sempre converge para uma solução O esforço computacional do método da bisseção cresce demasiadamente quando se aumenta a exatidão da raiz desejada Deve ser usado apenas para diminuir o intervalo que contém a raiz para posterior aplicação de outro método, como o método de Newton, por exemplo O método da Secante é uma aproximação para o método de Newton Ao contrário do método da Bisseção o método da Secante e de Newton podem não convergir 43 FASE II: COMPARAÇÃO ENTRE OS MÉTODOS APRESENTADOS O método da bisseção é bastante simples por não exigir o conhecimento da derivada da equação em questão, porém possui uma convergência lenta O método de Newton é o que apresenta a convergência mais rápida, porém exige o conhecimento da derivada analítica da função em questão O método da Secante é mais lento que o de Newton, porém não exige o conhecimento da derivada analítica da função em questão 44 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa DEMONSTRAÇÃO PRÁTICA DOS MÉTODOS EM AÇÃO 46 EXERCÍCIOS PARA OS ALUNOS Implementar os métodos apresentados, de preferência com visualização gráfica Para uma coleção de funções dadas na lista de exercícios 47 CONTEÚDO Metodologia Contexto Bibliografia Motivação Idéia Central dos Métodos Fase I Fase II Método da Bisseção Método de Newton-Raphson Método da Secante Comparação dos métodos Prática Pesquisa PESQUISA Em cima de suas implementações: Encontrar situações de não convergência e explicar o que está acontecendo Definir diferentes critérios de parada, comparar os resultados obtidos e o número de iterações necessários para cada método 49 MÉTODOS NUMÉRICOS DE DETERMINAÇÃO DE RAÍZES: BISSEÇÃO, SECANTE E NEWTON-RAPHSON OBRIGADO! FIM. Professor.: Aquiles Burlamaqui [email protected] http://aquilesburlamaqui.wikidot.com