Uma das dificuldades do método de Newton é o fato de uma aproximação
ser tal que
. Uma modificação do algoritmo original para prever estes casos consiste em: dado
um número positivo próximo de zero e supondo
, a sequência
é gerada através de:
onde
onde
é a última aproximação obtida tal que
.
Pede-se:
baseado no algoritmo de Newton, escreva um algoritmo para este método;
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 .
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 é:
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”:
- Escolhe
e parâmetros: , tolerância , iterações máximas . - Define
(índice da última derivada válida). - Para
até :
a) Calculae .
b) Se, então atualiza e usa .
Caso contrário, usa.
c) Atualizad) Se , para e retorna . - 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”