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

ba

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 b3
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
Download

Slide 1 - Aquiles Burlamaqui