Uma das dificuldades do método de Newton é o fato de uma aproximação xk ser tal que f^prime(xk)=0. Uma modificação do algoritmo original para prever estes casos consiste em: dado lambda um número positivo próximo de zero e supondo f^prime(x0) >= lambda, a sequência xk é gerada através de:
xk+1=xk-f(xk) / F L, k=0,1,2, cdots
onde
F L= f^prime(xk), & se |f^prime(xk)|>lambda f^prime(xw), & caso contrário á
onde xw é a última aproximação obtida tal que f^prime(xw) mid >= lambda.
Pede-se:
baseado no algoritmo de Newton, escreva um algoritmo para este método;

Passo 1

Então, o enunciado diz que a gente tem o método de Newton tradicional, mas às vezes bate num ponto onde e aí não dá pra dividir. Para contornar isso, eles propõem uma pequena gambiarra: se a derivada em for muito pequena (menor que ), usar a derivada de uma iteração anterior em que ela era “grande o suficiente”.
Conteúdo: método de Newton (raiz de funções), derivadas, controle de fluxo em algoritmo. Vamos precisar entender como funciona Newton normal e depois encaixar essa regra do .

Passo 2

Antes de tudo, lembra do método de Newton “padrão”? Ele é:
xk+1 = xk - f(xk)f'(xk)
A ideia é usar a reta tangente em para chegar mais perto da raiz. Parada típica: quando fica abaixo de uma tolerância ou atingimos um número máximo de iterações.

Passo 3

O problema ocorre se : aí a divisão explode ou fica num “passo gigante” e não converge. A solução proposta é:
  • Defina um limiar .
  • Sempre que , tudo normal, usamos .
  • Se , aí voltamos e usamos a última derivada “válida” ( com ).
Isso garante que nunca dividimos por algo muito pequenininho.

Passo 4

Vamos montar o pseudocódigo, bem no estilo “amigo explicando”:
  1. Escolhe xk+1 = xk - fkFL e parâmetros: , tolerância , iterações máximas .
  2. Define (índice da última derivada válida).
  3. Para até :
    a) Calcula e .
    b) Se , então atualiza e usa .
    Caso contrário, usa .
    c) Atualiza d) Se , para e retorna .
  4. Se chegar ao fim sem convergir, avisa “não convergiu em iterações”.

Resposta

Entrada: f, f', x0, lambda > 0, tol, Nmax
w ← 0
x[0] ← x0

Para k de 0 até Nmax-1 faça:
    f_k  ← f(x[k])
    fp_k ← f'(x[k])
    
    Se |fp_k| ≥ lambda então
        w ← k
        FL ← fp_k
    Senão
        FL ← f'(x[w])
    FimSe
    
    x[k+1] ← x[k] - f_k / FL
    
    Se |f(x[k+1])| < tol então
        Retorne x[k+1]  // convergiu
    FimSe
FimPara

Retorne “Não convergiu em Nmax iterações”

Exercícios relacionados