Algoritmo para método de Newton
Da fórmula de iteração a um algoritmo
Vamos lá?
Conhecer a fórmula da iteração de Newton é um grande passo para resolver equações não lineares, mas da fórmula à implementação do método de Newton existem alguns pontos que precisam ser discutidos e resolvidos. Nesta aula vamos discutir três questões que surgem nesse processo de criar um algoritmo para o método de Newton.
- 1
- 2
- 3
Quais questões não podem ser negligenciadas em uma implementação funcional do método de Newton.
Se não é possível computar O que se pode fazer?
O núcleo do algoritmo para o método de Newton é bem simples. Ele consiste apenas de computar sucessivamente uma aproximação linear para a função e resolver o problema de encontrar o zero dessa aproximação, tomando-o como nova estimativa para o zero da função.
Entretanto, ao sair do campo teórico para o computacional, devemos nos atentar a algumas questões importantes. Vimos que a convergência do método de Newton é assegurada apenas quando partimos de um ponto inicial próximo do zero da função. E se este não for o caso?
Quando dissemos que as aproximações são computadas sucessivamente, precisamos especificar até quando ou por quanto tempo, visto que na prática não é possível iterar ao infinito.
Por fim, como a fórmula de iteração do Método de Newton realiza uma divisão, pode acontecer do denominador,
Vamos começar lidando com as considerações sobre o ponto inicial. Como o método de Newton precisa de uma boa estimativa inicial, uma estratégia pode ser utilizar um método menos exigente, que funcione mesmo que essa aproximação inicial não seja tão boa. Depois desse método melhorá-la um pouco, então emprega-se o método de Newton. O método da bissecção poderia ser utilizado com essa finalidade. Claro que aí, recairíamos nas dificuldades do método da bissecção.
Outra estratégia é globalizar o método de Newton, ou seja, modificá-lo para que o método se torne robusto em relação ao ponto de partida. As duas principais formas de globalizar o método de Newton são através da inserção de uma busca linear na direção apontada pelo método de Newton ou através da definição de uma região de confiança, dentro da qual a aproximação linear é válida. Ambas as estratégias são melhor discutidas no contexto de métodos de otimização e fogem ao escopo desta aula. Para quem tem interesse, recomendo o livro de Dennis e Schnabel (1996).
Passando à segunda questão, um algoritmo computacional não pode deixar de explicitar o critério de parada de execução. O desejável seria pedir que o erro ficasse abaixo de um certo nı́vel aceitável, ou seja, dado um
Um dos critérios que sim podemos aplicar é sobre o valor da
Quando a sequência
Desta forma, usar como critério de parada
Na prática, os critérios mais usados, além de um limite máximo para o número de iterações, são:
ou seja, uma redução relativa no valor de função. Assim o parâmetro pode ser um número adimensional. O problema deste critério é que se for muito grande, o método pode parar ainda com muito grande. Por outro lado, se já for muito pequeno, então o método vai se esforçar exageradamente para reduzir demais o valor de ou seja, uma combinação entre uma tolerância relativa e uma absoluta para o valor de função. A escolha apropriada de e evita as mazelas do critério anterior. Por exemplo, tente entender o que acontece quando e com relação às diferentes possibilidades para para , ou seja, uma redução relativa no comprimento dos passos dados pelo método. Isso evita insistir nas iterações quando o método parece estagnar.
Ainda sobre o critério de parada, um último comentário é que, seja qual for sua escolha, sempre é importante limitar também o número de máximo de iterações. Esta é a única garantia de que o algoritmo de fato vai parar em algum momento.
Por fim, vamos discutir o último aspecto levantado no início desta aula, o caso em que
Claro que a chance de você acertar um ponto, no curso das iterações de Newton, que tenha a derivada exatamente nula, é muitíssima pequena, nula até. Será que podemos nos tranquilizar então?
Na prática, a derivada ser quase nula já é um problema. Como a reta tangente num ponto onde a derivada é muito pequena é praticamente paralela ao eixo horizontal, sua intersecção com o eixo (próximo iterando do método de Newton) estará muito distante. Com isto, o iterando pode se afastar da região onde procurávamos por um zero da função, levando à convergência para outro zero ou mesmo à divergência. Veja o exemplo da figura abaixo, onde a função tem o eixo
Para uma discussão mais aprofundada sobre a implementação do método de Newton, recomendo o livro Kelley (2003).
Referências
J. E. Dennis e R. B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, 1996.
C. T. Kelley. Solving Nonlinear Equations with Newton's Method. SIAM, 2003.
Considere o seguinte protótipo para uma implementação do método de Newton em Octave.
function [x, fx, n] = newton(f, g, x0, tol, N) x = x0; fx = f(x); n = 0; s = tol + 1; while (s > tol & n <= N) gx = g(x); s = - fx / gx; x = x + s; s = abs(s); fx = f(x); n = n + 1; endwhile endfunction
1. No modelo de implementação acima, identifique qual o papel de cada variável da função.
2. Utilize essa função no Octave, para aproximar os zeros das funções abaixo. Inicialmente, utilize como ponto inicial o
3. Sobre a implementação acima, qual o critério de parada que está sendo utilizado? Como a implementação deveria ser modificada para utilizar algum dos outros critérios apresentados? Quais pontos da discussão dessa aula não foram contemplados nessa implementação. Tente melhorar a função apresentada, tornando-a mais robustas, ou seja, menos suscetível a erros ou fracassos.
4. Baixe a rotina newtsol.m, distribuída juntamente com o livro Kelley (2003). Utilize-a nos mesmos testes do exercício 2. Estude como a essa rotina foi implementada. Tente identificar os pontos importantes da implementação.