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 [a, b], dividindo o intervalo em N=100 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:
  • p(x)=x^{4}-10 x^{3}+35 x^{2}-50 x+24( raízes 1,2,3,4);
  • f(x)=x^{3}-9 x+3 (três raízes reais);
  • f(x)=\sin (5 x)-x / 2 (múltiplas raízes em [-\pi, \pi] ).
    (e) Para cada função de teste, compare o número de avaliações de f entre os cinco métodos.

  1. “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 [a,b] dividindo o intervalo em N=100 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ância tol.
  • Retornar uma lista com todas as raízes encontradas (sem repetições).
  • Testar com três funções de exemplo:
    • p(x)=x^{4}-10x^{3}+35x^{2}-50x+24 (raízes exatas: 1,2,3,4);
    • f(x)=x^{3}-9x+3 (possui três raízes reais);
    • f(x)=\sin(5x)-x/2 em [-\pi,\pi] (múltiplas raízes).
  • Para cada função de teste, comparar o número de avaliações de f entre os cinco métodos.
Informações claramente dadas:
  • Intervalo [a,b], tolerância \text{tol}, método escolhido.
  • Divisão do intervalo em N=100 subintervalos para detecção de troca de sinal (preciso usar N=100 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 f (para comparação entre métodos).

Passo 2

Plano geral (visão de alto nível, sem entrar ainda na implementação):
  1. Dividir [a,b] em N=100 subintervalos uniformes e avaliar f nos nós para detectar sinais trocados. Quando f(x_i)=0 exatamente ou \operatorname{sign} f(x_i)\neq \operatorname{sign} f(x_{i+1}), temos um candidato a raiz nesse subintervalo.
  2. Para cada subintervalo com troca de sinal, aplicar o método de refinamento selecionado até satisfazer o critério de parada (por exemplo |f(x)|<\text{tol} ou tamanho do intervalo menor que \text{tol} ou diferença entre iterações menor que \text{tol}).
  3. Acumular as raízes encontradas, removendo duplicatas numéricas (duas raízes obtidas em subintervalos adjacentes podem representar a mesma raiz).
  4. Contabilizar o número de avaliações de f 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 f 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 [a,b] em N=100 partes: o passo é h=(b-a)/N.
  • Os nós são x_i = a + i h, para i=0,\dots,N.
  • Avaliar f(x_i) para todos esses x_i. Se f(x_i)=0 (na prática |f(x_i)|<\text{tol} se desejarmos) então x_i é uma raiz exata detectada; se f(x_i)\cdot f(x_{i+1})<0 então existe pelo menos uma raiz em [x_i,x_{i+1}] (por continuidade implícita do enunciado).
  • Para eficiência e contagem correta, usar cache das avaliações: não avaliar repetidamente f 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: \text{tol}. Usarei critérios combinados:
    • |f(x_k)| < \text{tol}, ou
    • diferença entre iterações |x_{k+1}-x_k| < \text{tol}, ou
    • tamanho do intervalo (quando aplicável) |b-a| < \text{tol}, ou
    • número máximo de iterações (por exemplo 1000) para evitar loop infinito.
  • Ao terminar, retornar a aproximação x e garantir que o valor satisfaça |f(x)|<10\cdot\text{tol} (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):
  1. Bisseção
  • Princípio: se f(a) e f(b) têm sinais opostos então existe raiz em [a,b]. Repetidamente tomar ponto médio m=(a+b)/2.
  • Se f(m)=0 pare. Se \operatorname{sign} f(m)=\operatorname{sign} f(a) então substitua a\leftarrow m senão b\leftarrow m.
  • Vai convergir linearmente e é robusta.
  • Critério: (b-a)/2 < \text{tol} ou |f(m)|<\text{tol}.
  1. Posição falsa (regula falsi)
  • Fórmula do ponto de corte pela secante do intervalo: c = b - f(b)\frac{b-a}{f(b)-f(a)}.
  • Substituir um dos extremos conforme o sinal de f\text{(c)}.
  • 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).
  1. Newton (método de Newton-Raphson)
  • Iteração: x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.
  • Converge quadraticamente quando perto da raiz e quando f' não é zero; exige a derivada f' (no enunciado fprime é parâmetro).
  • Risco: diverge se o chute começar longe ou se f' for pequeno.
  1. Secante
  • Aproxima derivada numericamente usando dois pontos: x_{n+1} = x_n - f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}.
  • Não precisa de f'; costuma convergir superlinearly (ordem ~1.618) e é prática quando f' não está disponível.
  1. Ponto fixo
  • Transformar f(x)=0 em x=g(x) e iterar x_{n+1}=g(x_n).
  • Uma transformação simples e amplamente usada é relaxação: g(x) = x - \gamma f(x),onde \gamma é um parâmetro escalar que controla a convergência.
  • Se |g'(x)|<1 numa vizinhança da raiz, a iteração converge linearmente.
  • Para escolher \gamma de forma razoável: se f' estiver disponível, podemos avaliar |f'(m)| no meio do subintervalo e usar \gamma = \frac{1}{1 + |f'(m)|}(isso tende a manter g' em magnitude < 1 heurísticamente). Se f' não estiver, usar um pequeno \gamma, por exemplo \gamma=0{,}1.
  • Ponto fixo é o método menos robusto de todos e pode necessitar de ajustes do parâmetro \gamma.

Passo 6

Decisões de implementação e detalhes práticos para tornar tudo robusto:
  • Cachear avaliações de f 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 r verificar se já existe alguma raiz s na lista com |r-s|<\text{tol}. Se existir, manter a média, ou simplesmente descartar r.
  • Ordenar as raízes no final antes de retornar.
  • Permitir que fprime seja None — nesse caso Newton não pode ser usado (ou lançará um erro). Para ponto_fixo posso usar fprime se disponível para calcular \gamma; caso contrário usar uma \gamma conservadora.

Passo 7

Como eu vou contabilizar as avaliações de f (requisito do item (e)):
  • Nos testes, envolverei cada função f em um wrapper que incrementa um contador toda vez que f é chamado. Esse wrapper será passado para encontrar_raizes para que o número total de chamadas a f seja 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 f' (derivada) no relatório pedido, pois o enunciado pediu comparar o número de avaliações de f.

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_raizes juntamente 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 de f para cada método.
  • Para usar: copiar o código Python, colar num arquivo .py ou 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()

Exercícios relacionados