Exercício 29 (Desafio) - Projeto - Localizador Robusto de Raízes
Implemente em Python a função encontrar_raizes(f, fprime, a, b, tol, metodo), onde metodo pode ser ‘bissecao’, ‘pos_falsa’, ‘ponto_fixo’, ‘newton’ ou ‘secante’.
(a) A função deve detectar automaticamente subintervalos com troca de sinal em
, dividindo o intervalo em
partes iguais.
(b) Em cada subintervalo com troca de sinal, aplique o método escolhido com tolerância tol.
(c) Retorne uma lista com todas as raízes encontradas.
(d) Teste com:
-
raízes
;
-
(três raízes reais);
-
(múltiplas raízes em
).
(e) Para cada função de teste, compare o número de avaliações de
entre os cinco métodos.
- “A matemática é a linguagem com a qual Deus escreveu o universo.” — Galileu Galilei
Referências: Franco (2007); Ruggiero & Lopes (2006); Sperandio (2003); Oliveira, A. J. (2021).
(a) A função deve detectar automaticamente subintervalos com troca de sinal em
(b) Em cada subintervalo com troca de sinal, aplique o método escolhido com tolerância tol.
(c) Retorne uma lista com todas as raízes encontradas.
(d) Teste com:
(e) Para cada função de teste, compare o número de avaliações de
- “A matemática é a linguagem com a qual Deus escreveu o universo.” — Galileu Galilei
Referências: Franco (2007); Ruggiero & Lopes (2006); Sperandio (2003); Oliveira, A. J. (2021).
Passo 1
O enunciado pede a implementação de uma função em Python chamada
encontrar_raizes(f, fprime, a, b, tol, metodo) com as seguintes exigências principais:- Detectar automaticamente subintervalos com troca de sinal em
dividindo o intervalo em partes iguais. - Para cada subintervalo que contém uma troca de sinal, aplicar o método de raiz indicado por
metodo, que pode ser'bissecao','pos_falsa','ponto_fixo','newton'ou'secante', com tolerânciatol. - Retornar uma lista com todas as raízes encontradas (sem repetições).
- Testar com três funções de exemplo:
-
(raízes exatas: ); -
(possui três raízes reais); -
em (múltiplas raízes).
-
- Para cada função de teste, comparar o número de avaliações de
entre os cinco métodos.
Informações claramente dadas:
- Intervalo
, tolerância , método escolhido. - Divisão do intervalo em
subintervalos para detecção de troca de sinal (preciso usar exatamente). - Métodos a implementar: bisseção, falsa posição (regula falsi), ponto fixo, Newton e secante.
- É necessário contar/relatar o número de chamadas a
(para comparação entre métodos).
Passo 2
Plano geral (visão de alto nível, sem entrar ainda na implementação):
- Dividir
em subintervalos uniformes e avaliar nos nós para detectar sinais trocados. Quando exatamente ou , temos um candidato a raiz nesse subintervalo. - Para cada subintervalo com troca de sinal, aplicar o método de refinamento selecionado até satisfazer o critério de parada (por exemplo
ou tamanho do intervalo menor que ou diferença entre iterações menor que ). - Acumular as raízes encontradas, removendo duplicatas numéricas (duas raízes obtidas em subintervalos adjacentes podem representar a mesma raiz).
- Contabilizar o número de avaliações de
ao longo de todo o processo (tanto na detecção de trocas de sinal quanto nos refinamentos) para comparar os métodos.
Observação: vou implementar um wrapper contador para
nos testes; a função
encontrar_raizes aceitará qualquer callable f (o wrapper será passado pelo chamador nos testes) — assim o número de avaliações fica disponível externamente, sem alterar a assinatura pedida.Passo 3
Detecção automática de subintervalos com troca de sinal — ideia e detalhes práticos.
- Dividir o intervalo
em partes: o passo é . - Os nós são
, para . - Avaliar
para todos esses . Se (na prática se desejarmos) então é uma raiz exata detectada; se então existe pelo menos uma raiz em (por continuidade implícita do enunciado). - Para eficiência e contagem correta, usar cache das avaliações: não avaliar repetidamente
no mesmo ponto. - Observação: se o root for múltiplo par (por exemplo multiplicidade par) pode não haver troca de sinal. O enunciado diz dividir por troca de sinal, então assumimos que estamos procurando raízes simples ou que a maioria dos casos didáticos tem troca de sinal. Se houver raiz de multiplicidade par e sem troca de sinal, esse procedimento não a detecta; para robustez maior seria necessário analisar derivadas ou checar mínimos locais próximos a zero — aqui seguiremos o critério pedido (troca de sinal em N=100).
Passo 4
Critérios de parada e rodas gerais que usarei para todos os métodos:
- Tolerância principal:
. Usarei critérios combinados: -
, ou - diferença entre iterações
, ou - tamanho do intervalo (quando aplicável)
, ou - número máximo de iterações (por exemplo 1000) para evitar loop infinito.
-
- Ao terminar, retornar a aproximação
e garantir que o valor satisfaça (ou pelo menos a melhor aproximação obtida). O fator 10 é para evitar perda de raízes por arredondamento estrito; isto é pragmático.
Passo 5
Resumo didático dos métodos e as fórmulas que vou codificar (com explicação simples e exemplos):
- Bisseção
- Princípio: se
e têm sinais opostos então existe raiz em . Repetidamente tomar ponto médio . - Se
pare. Se então substitua senão . - Vai convergir linearmente e é robusta.
- Critério:
ou .
- Posição falsa (regula falsi)
- Fórmula do ponto de corte pela secante do intervalo:
- Substituir um dos extremos conforme o sinal de
. - Tende a ser mais rápida que bisseção para funções suaves, mas pode travar se um extremo não se mover (existem variantes melhoradas; implementaremos a versão clássica).
- Newton (método de Newton-Raphson)
- Iteração:
- Converge quadraticamente quando perto da raiz e quando
não é zero; exige a derivada (no enunciado fprimeé parâmetro). - Risco: diverge se o chute começar longe ou se
for pequeno.
- Secante
- Aproxima derivada numericamente usando dois pontos:
- Não precisa de
; costuma convergir superlinearly (ordem ~1.618) e é prática quando não está disponível.
- Ponto fixo
- Transformar
em e iterar . - Uma transformação simples e amplamente usada é relaxação:
onde é um parâmetro escalar que controla a convergência. - Se
numa vizinhança da raiz, a iteração converge linearmente. - Para escolher
de forma razoável: se estiver disponível, podemos avaliar no meio do subintervalo e usar (isso tende a manter em magnitude < 1 heurísticamente). Se não estiver, usar um pequeno , por exemplo . - Ponto fixo é o método menos robusto de todos e pode necessitar de ajustes do parâmetro
.
Passo 6
Decisões de implementação e detalhes práticos para tornar tudo robusto:
- Cachear avaliações de
em pontos já calculados (para não contar duas vezes e para economia). - Em refinamentos que exigem valores já computados em extremos do subintervalo, utilizar esses valores cacheados.
- Para evitar raízes duplicadas obtidas em subintervalos adjacentes, ao adicionar uma raiz
verificar se já existe alguma raiz na lista com . Se existir, manter a média, ou simplesmente descartar . - Ordenar as raízes no final antes de retornar.
- Permitir que
fprimesejaNone— nesse caso Newton não pode ser usado (ou lançará um erro). Paraponto_fixoposso usarfprimese disponível para calcular; caso contrário usar uma conservadora.
Passo 7
Como eu vou contabilizar as avaliações de
(requisito do item (e)):
- Nos testes, envolverei cada função
em um wrapper que incrementa um contador toda vez que é chamado. Esse wrapper será passado para encontrar_raizespara que o número total de chamadas aseja registrado (isso inclui as chamadas feitas durante a detecção de trocas de sinal e durante o refinamento). - Observação: não vou contar chamadas a
(derivada) no relatório pedido, pois o enunciado pediu comparar o número de avaliações de .
Passo 8
Resumo do que você (eu) vai receber como “resposta final” e como usar:
- Vou fornecer abaixo a implementação completa em Python da função
encontrar_raizesjuntamente com um pequeno “script de teste” que executa os três exemplos pedidos e imprime as raízes encontradas e o número de avaliações depara cada método. - Para usar: copiar o código Python, colar num arquivo
.pyou em um notebook e executar. O script fará as comparações e imprimirá os resultados.
Resposta
import math
def encontrar_raizes(f, fprime, a, b, tol, metodo):
"""
Encontrar raízes de f em [a,b] detectando subintervalos com troca de sinal
(N=100 subdivisões) e aplicando o método pedido em cada subintervalo.
metodo: 'bissecao', 'pos_falsa', 'ponto_fixo', 'newton', 'secante'
Retorna lista de raízes (aproximações).
Observação: f pode ser um wrapper que conta chamadas (para análise).
"""
N = 100
h = (b - a) / N
xs = [a + i * h for i in range(N + 1)]
# cache de avaliações
fcache = {}
def feval(x):
# cache por aproximação numérica: usar x diretamente (assumimos que chamamos com os mesmos floats)
if x in fcache:
return fcache[x]
v = f(x)
fcache[x] = v
return v
# refinadores
def bissecao_refine(xl, xr, fl, fr):
a_, b_ = xl, xr
fa, fb = fl, fr
m = None
max_iter = 1000
for _ in range(max_iter):
m = 0.5 * (a_ + b_)
fm = feval(m)
if abs(fm) < tol:
return m
if fa * fm < 0:
b_, fb = m, fm
else:
a_, fa = m, fm
if abs(b_ - a_) < tol:
return 0.5 * (a_ + b_)
return m
def pos_falsa_refine(xl, xr, fl, fr):
a_, b_ = xl, xr
fa, fb = fl, fr
c = None
max_iter = 1000
for _ in range(max_iter):
# evita divisão por zero
denom = (fb - fa)
if denom == 0:
c = 0.5 * (a_ + b_)
else:
c = b_ - fb * (b_ - a_) / denom
fc = feval\text{(c)}
if abs(fc) < tol or abs(b_ - a_) < tol:
return c
if fa * fc < 0:
b_, fb = c, fc
else:
a_, fa = c, fc
return c
def newton_refine(xl, xr, fl, fr):
# inicial: midpoint
x = 0.5 * (xl + xr)
max_iter = 200
for _ in range(max_iter):
fx = feval(x)
if abs(fx) < tol:
return x
if fprime is None:
# não podemos usar Newton se não houver derivada
break
fpx = fprime(x)
if fpx == 0:
break
xnew = x - fx / fpx
if abs(xnew - x) < tol:
return xnew
x = xnew
return x
def secante_refine(xl, xr, fl, fr):
x0, x1 = xl, xr
f0, f1 = fl, fr
max_iter = 200
for _ in range(max_iter):
if f1 - f0 == 0:
# fallback para média
x2 = 0.5 * (x0 + x1)
else:
x2 = x1 - f1 * (x1 - x0) / (f1 - f0)
f2 = feval(x2)
if abs(f2) < tol or abs(x2 - x1) < tol:
return x2
# desloca
x0, f0 = x1, f1
x1, f1 = x2, f2
return x1
def ponto_fixo_refine(xl, xr, fl, fr):
# g(x) = x - gamma * f(x)
mid = 0.5 * (xl + xr)
if fprime is not None:
try:
fpm = fprime(mid)
gamma = 1.0 / (1.0 + abs(fpm))
except Exception:
gamma = 0.1
else:
gamma = 0.1
x = mid
max_iter = 1000
for _ in range(max_iter):
fx = feval(x)
xnew = x - gamma * fx
if abs(feval(xnew)) < tol or abs(xnew - x) < tol:
return xnew
x = xnew
return x
# var para armazenar raízes
roots = []
# detectar trocas de sinal
for i in range(N):
x1 = xs[i]
x2 = xs[i + 1]
f1 = feval(x1)
f2 = feval(x2)
# se f1 é quase zero (usar critério absoluto comparando com tol)
if abs(f1) < tol:
r = x1
# adicionar se não duplicado
if not any(abs(r - s) < tol for s in roots):
roots.append(r)
# troca de sinal detectada
if f1 * f2 < 0:
# escolher o refinador
if metodo == 'bissecao':
r = bissecao_refine(x1, x2, f1, f2)
elif metodo == 'pos_falsa':
r = pos_falsa_refine(x1, x2, f1, f2)
elif metodo == 'newton':
r = newton_refine(x1, x2, f1, f2)
elif metodo == 'secante':
r = secante_refine(x1, x2, f1, f2)
elif metodo == 'ponto_fixo':
r = ponto_fixo_refine(x1, x2, f1, f2)
else:
raise ValueError("Método desconhecido: " + str(metodo))
# adicionar se não duplicado
if r is not None:
if not any(abs(r - s) < tol for s in roots):
roots.append(r)
# possível verificar último nó xN
xN = xs[-1]
fN = feval(xN)
if abs(fN) < tol and not any(abs(xN - s) < tol for s in roots):
roots.append(xN)
roots.sort()
return roots
# -----------------------
# Helper para testar e contar avaliações de f
# -----------------------
def make_counted(f):
counter = {'calls': 0}
def wrapped(x):
counter['calls'] += 1
return f(x)
return wrapped, counter
# -----------------------
# Funções de teste e suas derivadas (quando aplicável)
# -----------------------
def p_poly(x):
return x**4 - 10*x**3 + 35*x**2 - 50*x + 24
def p_poly_prime(x):
return 4*x**3 - 30*x**2 + 70*x - 50
def cubic(x):
return x**3 - 9*x + 3
def cubic_prime(x):
return 3*x**2 - 9
def seno(x):
return math.sin(5*x) - x/2
def seno_prime(x):
return 5*math.cos(5*x) - 0.5
# -----------------------
# Rodar testes para cada método e cada função, imprimir raízes e contagens
# -----------------------
if __name__ == "__main__":
testes = [
("p_poly", p_poly, p_poly_prime, 0.0, 5.0),
("cubic", cubic, cubic_prime, -5.0, 5.0),
("seno", seno, seno_prime, -math.pi, math.pi)
]
metodos = ['bissecao', 'pos_falsa', 'ponto_fixo', 'newton', 'secante']
tol = 1e-8
for nome, f, fp, a, b in testes:
print("=== Teste:", nome, "intervalo=[{:.3g}, {:.3g}] ===".format(a, b))
for metodo in metodos:
# envolver f para contar avaliações
f_counted, counter = make_counted(f)
# passar derivative "crua" (não-contada) para newton/ponto_fixo, pois só contamos f
roots = encontrar_raizes(f_counted, fp, a, b, tol, metodo)
print("Método:", metodo)
print(" raízes encontradas ({:d}):".format(len(roots)), ["{:.12g}".format(r) for r in roots])
print(" avaliações de f:", counter['calls'])
print()