* Bolsista de Iniciação Científica PIBIC/CNPq

Um estudo introdutório do método de Newton para minimização

funções de uma ou várias variáveis

Gracielle Lima de Oliveira* André Luís Machado Martinez Universidade Tecnológica Federal do Paraná, campus Cornélio Procópio, PR

Avenida Alberto Carazzai, 1640 CEP 86300-000

E-mail: graci_lima@yahoo.com.br

RESUMO

Neste trabalho realizamos um estudo sobre o método de Newton para a determinação de mínimo

de funções, deduzimos o método e trabalhamos com funções de uma e várias variáveis, testes

numéricos foram realizados e implementações foram feitas no software MatLab.

Palavras-chave: Método de Newton, Funções de uma e várias variáveis, Otimização,

Problemas irrestritos, MatLab.

MÉTODO DE NEWTON

Neste trabalho desenvolvemos um estudo introdutório do método Newton (sugerimos [1], [2],

[3] e [4]), uma das aplicações mais simples deste método é sua versão para a determinação de

zeros de funções de uma variável real. Para deduzirmos o método vamos precisar da fórmula de

Taylor (recomendamos [5]) apresentada no teorema a seguir.

Teorema Seja f: R→R uma função com derivadas contínuas até ordem n. Então

𝑓 𝑥 + ℎ = 𝑓 𝑥 + ℎ𝑓 ′ 𝑥 +ℎ2

2!𝑓 ′′ 𝑥 + ⋯+

ℎ𝑛

𝑛!𝑓𝑛 𝑥 + 𝑅𝑛

onde𝑅𝑛 = ℎ𝑛+1

𝑛+1 !𝑓𝑛+1(𝜁)para algum 𝜁 entre 𝑥 e 𝑥 + ℎ.

Dada uma aproximação 𝑥𝑘 para uma raiz 𝑟 da equação 𝑓 𝑥 = 0 (𝑓:𝑅 → 𝑅 uma função),

queremos determinar 𝑥𝑘+1 uma aproximação melhor que 𝑥𝑘 . Vamos escrever 𝑥𝑘+1 = 𝑥𝑘 + ℎ, a

melhor escolha para ℎ seria aquela tal que 𝑟 = 𝑥𝑘 + ℎ, aplicando a fórmula de Taylor com 𝑛 =2 obtemos:

0 = 𝑓 𝑟 = 𝑓 𝑥𝑘 + ℎ𝑓 ′ 𝑥𝑘 +ℎ2

2!𝑓 ′′ 𝜁

considerando 𝑥𝑘 próximo de 𝑟 então ℎ = 𝑟 − 𝑥𝑘 ≈ 0, assim desprezando o termo ℎ2

2!𝑓 ′′ 𝜁

podemos encontrar a seguinte aproximação ℎ ≈ −𝑓 𝑥𝑘

𝑓 ′ 𝑥𝑘 , então definimos a sequência de

Newton para o problema 𝑓(𝑥) = 0 como

𝑥𝑘+1 = 𝑥𝑘 −𝑓 𝑥𝑘

𝑓 ′ 𝑥𝑘 .

Supomos que a sequência 𝑥𝑘 de Newton seja convergente e converge para 𝑥, como 𝑥𝑘+1 =

𝑥𝑘 −𝑓 𝑥𝑘

𝑓 ′ 𝑥𝑘 se 𝑓 e 𝑓′ forem contínuas e 𝑓′(𝑥) ≠ 0 então considerando o limite quando 𝑛 → ∞ na

igualdade, obtemos 𝑥 = 𝑥 −𝑓 𝑥

𝑓 ′ 𝑥 ⟺ 𝑓 𝑥 = 0. Assim podemos concluir que caso a sequência

do Método de Newton converge para um determinado 𝑥, então 𝑥 será uma raiz da

equação𝑓(𝑥) = 0.

Utilizaremos o método de Newton na determinação de máximos e mínimos para funções de

uma variável real, para isto procuramos pontos críticos para a função f, ou seja, estamos

interessados em pontos 𝑥 no domínio de f onde ocorra 𝑓’(𝑥) = 0, portanto aplicaremos o

método descrito anteriormente para resolver a equação 𝑓’(𝑥) = 0. A seguir apresentamos uma

288

* Bolsista de Iniciação Científica PIBIC/CNPq

implementação feita no software MatLab (www.mathworks.com) do método de Newton para

mínimo de funções de uma variável real.

ALGORTMO 1 function [x]=metodo_newton(f,d1f,d2f,x,h)

% f função a ser minimizada

% d1f derivada de f

% d2f derivada segunda de f

% x aproximação inicial para o mínimo

% h precisão exigida

k=1;

erro=inf;

while (k<100) && (erro>h)

aux=d1f(x)/d2f(x);

x=x-aux;

erro=abs(aux);

k=k+1;

end

Na tabela a seguir são apresentados resultados obtidos pelo Algoritmo 1

Função 𝒌 𝒇(𝒙) 𝒙 𝒙𝟎 Convergente

2𝑥3 + 3𝑥2 − 12𝑥 13 −7 1 0 Sim

2𝑥3 − 3𝑥2 − 12𝑥 + 1 6 8 −1 0 Sim

−4𝑥3 + 3𝑥2 + 18𝑥 7 −11 −1 0 Sim

𝑥4

4−

5𝑥3

3+ 4𝑥2 − 4 2 −4 0

0 Sim

Tabela:Resultados do Algoritmo 1

Com o intuito de melhorar o desempenho do método de Newton incluímos ao Algoritmo

1 uma busca linear, ou seja, agora𝑥𝑘+1 = 𝑥𝑘 − 𝛼 𝑓’(𝑥𝑘)

𝑓’’(𝑥𝑘), onde 0 < 𝛼 < 1 é obtido pelo

algoritmo do retrocesso (recomendamos [2], [3]) e cumpre a condição de Armijo 𝑓 𝑥𝑘 −

𝛼 𝑓′ 𝑥𝑘 < 𝑓 𝑥𝑘 −𝛼

2𝑓′ 𝑥𝑘

𝑓′ 𝑥𝑘

𝑓′′ 𝑥𝑘 .

Repetimos os testes com o Método de Newton com busca linear, os resultados são

apresentados na tabela a seguir:

Função 𝒌 𝒇(𝒙) 𝒙 𝒙𝟎 Convergente

2𝑥3 + 3𝑥2 − 12𝑥 3 −7 1 0 Sim

2𝑥3 − 3𝑥2 − 12𝑥 + 1 3 −3 −2 0 Sim

18𝑥 + 3𝑥2 − 4𝑥3 6 −11 −1 0 Sim

𝑥4

4−

5𝑥3

3+ 4𝑥2 − 4 2 −4 0

0 Sim

Tabela 2: Resultados do Algoritmo 1 com retrocesso

Considerando funções de várias variáveis reais a valores reais, nosso método modifica-se, agora

nos contentamos com 𝑥, tal que ∇𝑓(𝑥) = 0, assim a sequência do método de Newton para a

determinação de mínimos torna-se 𝑥𝑘+1 = 𝑥𝑘 − [∇2f 𝑥𝑘 ]−1∇𝑓 𝑥𝑘 , apresentamos a seguir o

Algoritmo 2 como uma generalização do Algoritmo 1:

ALGORITMO 2 % g função a ser minimizada

% g1 vetor gradiente de g

% g2 matriz hessiana de g

% x aproximação inicial para o mínimo

% h precisão exigida

function [x]=metodo_newton_grad(g,g1,g2,h,x)

k=0;

erro=inf;

while (k<100) && (erro>h)

aux=g2(x)\g1(x)';

x=x-aux';

erro=max(abs(aux));

k=k+1;

289

* Bolsista de Iniciação Científica PIBIC/CNPq

end

Na tabela a seguir apresentados os resultados dos testes obtidos pelo Algoritmo 2

Funções 𝒌 𝒙 𝒇(𝒙) 𝒙𝟎 Convergência

𝑥3

3+ 2𝑥2 + 3𝑥 − 6 4 −1 −7,33

0

Sim

𝑥2 − 5𝑥 + 6 2 2,50 −0,25 0 Sim 𝑥

1 + 𝑥2 1 1 0,5

1 Não

𝑥3 + 2𝑦2 − 3𝑥 − 4𝑦 5 [1 1] −4 [1 1] Sim

−𝑥3 + 2𝑦2 − 4𝑥𝑦 − 𝑥 + 𝑦 − 1 2 [0 − 0,25] −1,125 [0 0] Sim

Tabela 3: Resultados do Algoritmo 2

Com o intuito de melhorar o desempenho do método de Newton incluímos ao Algoritmo

2 uma busca linear, ou seja, agora 𝑥𝑘+1 = 𝑥𝑘 − 𝛼[∇2f 𝑥𝑘 ]−1∇𝑓 𝑥𝑘 , onde 0 < 𝛼 < 1 é

obtido pelo algoritmo do retrocesso e cumpre a condição de Armijo 𝑓 𝑥𝑘 − 𝛼 ∇𝑓 𝑥𝑘 <

𝑓 𝑥𝑘 −𝛼

2∇𝑓 𝑥𝑘

𝑇[∇2f 𝑥𝑘 ]−1∇𝑓 𝑥𝑘 .

Repetimos os testes com o Método de Newton com busca linear, os resultados são

apresentados na tabela a seguir:

Funções 𝒌 𝒙 𝒇(𝒙) 𝒙𝟎 Convergência

𝑥3

3+ 2𝑥2 + 3𝑥 − 6 4 −1 −7,33

0

Sim

𝑥2 − 5𝑥 + 6 2 2,50 −0,25 0 Sim 𝑥

1 + 𝑥2 1 1 0,5

1 Não

𝑥3 + 2𝑦2 − 3𝑥 − 4𝑦 1 [1 1] −4 [1 1] Sim

−𝑥3 + 2𝑦2 − 4𝑥𝑦 − 𝑥 + 𝑦 − 1 2 [0 − 0,25] −1,125 [0 0] Sim

Tabela 4: Resultados do Algoritmo 2

CONCLUSÃO

Nosso estudo ainda encontra-se no inicio, mas já foi possível observar algumas particularidades

do método de Newton, o método falhou quando a derivada de segunda ordem se anulou ou

tornou-se muito próxima de zero para funções de uma variável real. Quando consideramos

funções de várias variáveis reais podemos observar na pratica que a direção fornecida pelo

método de Newton pode não ser uma direção de descida causando a divergência do método.

Pretendemos corrigir a direção de Newton caso a hessiana seja não definida positiva no ponto,

ou seja, quando a direção fornecida por Newton não for uma direção de descida vamos

considerar uma combinação das direções de Newton e de máxima descida e realizar mais testes.

Referências

[1] Jorge Nocedal, Stephen J. Wright, Numerical Optimization. SPRINGER, 2006.

[2] A. FRIDLANDER, Elementos de Programação não Linear, Editora Unicamp,1994.

[3] J. M. Martínez, S. A. Santos, Métodos Computacionais de Otimização -IMPA XX

Colóquio Brasileiro de Matemática - 1995.

[4] R. Fletcher, Practical Methods of Optimization, 2nd ed. , John Wiley Sons,1987.

[5] H. L. Guidorizzi, Cálculo. Vol. 1, Ed. LTC, 5ª edição, 2001.

290