Determinação de Raizes Aquiles Burlamaque

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
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
*
*
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. Prentice-Hall, 2006.
*
*
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
*
*
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
*
*
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]
*
*
FASE I : ANÁLISE GRÁFICA
Figuras extraídas de [Ruggiero, 1996]
*
*
FASE I : ANÁLISE GRÁFICA
*
Figuras extraídas de [Ruggiero, 1996]
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 discutidas com mais detalhes em [Guidorizzi, 2001] e [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
*
*
FASE I : EXEMPLO COM PROCESSO I
*
Figuras extraídas de [Ruggiero, 1996]
*
FASE I : EXEMPLO COM PROCESSO II
*
Figuras extraídas de [Ruggiero, 1996]
*
FASE I : TABELA DE VARIAÇÃO DO SINAL
*
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
*
*
CRITÉRIOS DE PARADA
Existem vários tipo de critérios de parada
Analise do valor da funcao:
Erro absoluto:
Erro relativo:
Limites do intervalo:
*
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
*
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
*
*
FASE II: MÉTODO DA BISSEÇÃO
*
*
Ex: Achar a raiz da equação 
no intervalo [2,3] com o erro absoluto 
*
FASE II: MÉTODO DA BISSEÇÃO
Vantagens:
Simples
Converge sempre
Desvantagens:
convergencia lenta
*
*
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 NEWTON-RAPHSON
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: 
*
*
FASE II: MÉTODO DE NEWTON-RAPHSON
*
*
FASE II: MÉTODO DE NEWTON-RAPHSON (FORMULAÇÃO E ANÁLISE GRÁFICA)
*
Figuras extraídas de [Ruggiero, 1996]
*
Convergência
Caso se escolha x0 de forma que x1 saia do intervalo [a,b] o método poderá não convergir.
Ex: Ache a raiz da equação
para o erro relativo , ou seja:
FASE II: MÉTODO DE NEWTON-RAPHSON
*
Se
Então
x0=0,5
*
FASE II: MÉTODO DE NEWTON-RAPHSON
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
*
*
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) 
*
*
FASE II: MÉTODO DA SECANTE
*
*
*
Figuras extraídas de [Ruggiero, 1996]
FASE II: MÉTODO DA SECANTE
*
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
*
*
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
*
*
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
*
*
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
*
*
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
*
*
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
*
*
MÉTODOS NUMÉRICOS DE DETERMINAÇÃO DE RAÍZES: 
BISSEÇÃO, SECANTE E NEWTON-RAPHSON
Professor.: Manoel Azevedo
OBRIGADO!
FIM.
*
Convergência: Chegar a uma solução aproximada válida.
*
*
*
*
*