Nesta seção nos concentramos na solução do problema em uma variável,
ou seja, desejamos encontrar tal que ,
onde .
O método, como o próprio nome sugere, foi proposto por Isaac Newton.
O método de Newton é um processo iterativo de fundamental importância no
desenvolvimento de muitos algoritmos de programação não-linear.
Seja a solução candidata na iteração , sendo a solução inicial
definida arbitrariamente.
A idéia básica do método de Newton está na aproximação de com uma
série de Taylor de primeira ordem em torno do ponto . Isso
nos leva a seguinte aproximação:
onde .
O método calcula a próxima solução candidata de forma a
resolver a aproximação linear.
Mais precisamente:
Tipicamente, não se espera que , mas que
defina uma solução candidata de ``melhor qualidade'' do que aquela
definida por .
Formalmente, espera-se que:
É importante ressaltar que o método de Newton apresenta uma taxa
de convergência quadrática.
Isso significa, de maneira informal, que o número de dígitos corretos
na solução candidata duplica a cada iteração. (O método de Newton
apresenta convergência Q-quadrática, ou seja, existe tal que para suficientemente grande se pertence à
região de convergência.)
Então qual é o problema com o método de Newton? O método de Newton pode
divergir.
Isso ocorre quando a solução inicial não é suficientemente próxima
da solução ótima.
O método de Newton se comporta bem na região próxima da solução, todavia não
apresenta convergência global como o método de descenso.
O Método de Newton para Minimização em uma Variável
Nesta seção tratamos do problema de encontrar um valor tal que
seja mínimo.
O método inicia, como no caso anterior, com uma aproximação da função em torno
da solução candidata corrente, , mas desta vez utilizamos
uma aproximação de segunda ordem.
Para que seja o mínimo da aproximação, necessitamos que:
Encontre um mínimo de .
Se iniciamos o processo iterativo no ponto , o método
converge para o ponto . Note que .
Se iniciamos no ponto , o método converge para o
ponto . Observe que
.
O que levou o método de Newton a convergir para um ponto de máximo?
Será que o método apresenta uma falha fundamental?
Note que o método de Newton gera uma seqüência de soluções
, , que converge para um ponto
estacionário, ou seja, .
Todavia, não é necessariamente um ponto de mínimo, podendo também
definir um ponto de inflexão (e.g., o ponto estacionário da função )
ou de máximo (e.g., o ponto estacionário da função ).
Abaixo relembramos as condições necessárias e suficientes
para mínimo local: