O METODO DE NEWTON

Prévia do material em texto

O ME´TODO DE NEWTON
O. P. Ferreira∗
20 de Marc¸o de 2012
Resumo
Nestas notas e´ apresentada uma ana´lise de convergeˆncia local para o me´todo de Newton baseada para
func¸o˜es reais. A ana´lise apresentada permite obter a melhor estimativa para o raio de convergeˆncia do
me´todo de Newton, assim como raio da maior bola onde se tem soluc¸a˜o u´nica.
1 Introduc¸a˜o
sec:int
O me´todo de Newton e sua variac¸o˜es sa˜o os mais eficientes me´todos conhecidos para resolver sistemas de
equac¸o˜es na˜o lineares, incluindo busca por mı´nimo local de func¸o˜es e muitas outras aplicac¸o˜es. Um das
mais importantes aplicac¸o˜es do me´todo de Newton e´ no desenvolvimento da teoria de algoritmos de tempo
polinomial em programac¸a˜o convexa, veja Nesterov and Nemirovskii [6]. Ale´m das suas aplicac¸o˜es pra´ticas,
o me´todo de Newton e´ tambe´m uma ferramenta teo´rica poderosa tendo um vasto domı´nio de aplicac¸o˜es em
matema´tica pura, veja Blum, Cucker, Shub and Smale [1], Krantz and Parks [3], Moser [4], Nash [5] and
Wayne [10]. Uma perspectiva histo´rica recente das aplicaco˜es do me´todo de Newton pode ser encontrada
em Polyak [7].
A convergeˆncia do me´todo de Newton pode falhar, ou mesmo deixar de gerar uma sequeˆncia infinita
quando um ponto singular da derivada e´ encontrado. Para assegurar convergeˆncia do me´todo para uma
soluc¸a˜o da equac¸a˜o na˜o-linear, algumas condic¸o˜es devem ser impostas a func¸a˜o que define esta equac¸a˜o.
Por exemplo, a ana´lise de convergeˆncia local cla´ssica do me´todo requer que o ponto inicial esteja suficiente
pro´ximo da soluc¸a˜o e que a derivada da func¸a˜o na˜o-linear, que define a equac¸a˜o, deve ser na˜o singular
na soluc¸a˜o. Ale´m disso, continuidade Lipschitz da derivada e´ assumida, veja por exemplo, Dennis and
Schnabel [2] and Traub and Wozniakowski [9]. O problema da ana´lise de convergeˆncia local e´ que a soluc¸a˜o
deve ser conhecida ou dada a priori. Por outro lado, ele tem a vantagem de dar o maior intevalo de
convergeˆncia com respeito a constante de Lipschitz, see Rall [8], Traub and Wozniakowski [9].
2 O Me´todo de Newton
lkant
A ide´ia ba´sica do me´todo de Newton, para encontrar um zero de uma func¸a˜o diferencia´vel na˜o-linear, e´
bastante simples. Ela consiste em aproximar o zero da func¸a˜o na˜o liner por zeros de aproximac¸o˜es lineares
sucessivas em uma vizinhanc¸a apropriada. Mais precisamente, queremos resolver a equac¸a˜o
F (x) = 0, x ∈ I,
∗IME/UFG, Campus II- Caixa Postal 131, CEP 74001-970 - Goiaˆnia, GO, Brazil (E-mail:orizon@mat.ufg.br).
1
onde I ⊂ R e´ um intervalo aberto e f : I → Rn e´ uma func¸a˜o continuamente diferencia´vel na˜o-linear.
Comec¸amos com um ponto inicial x0 ∈ I, e constru´ımos a aproximac¸a˜o linear de F neste ponto, isto e´,
f(x) ≈ f(x0) + f ′(x0)(x− x0).
Enta˜o ao inve´s de resolver a equac¸a˜o na˜o-linear F (x) = 0, resolvemos a equac¸a˜o linear
f(x0) + f
′(x0)(x− x0) = 0.
Se a derivada F ′(x0) for na˜o-singular a equac¸a˜o linear acima tem uma u´nica soluc¸a˜o, digamos
x1 = x0 − f(x0)/f ′(x0).
Note que x1 pode ou na˜o pertencer a I, ou ainda, f
′(x1) pode ser singular. Para assegurar que o procedimento
possa ser repetido, precisamos de hipo´teses adequadas sobre f e o ponto inicial x0. Suponhamos, por um
momento, que o processo possa ser repetido indefinidamente, isto e´, x1 ∈ I e f ′(x1) e´ na˜o-singular e assim
sucessivamente. Portanto, podemos definir uma sequ¨eˆncia {xk} contida em I dada por
xk+1 = xk − f(xk)/f ′(xk), k = 0, 1, . . . . (1) eq:DNM
ainda assim na˜o temos a garantia de convergeˆncia da sequeˆncia {xk} para um zero de f . Novamente,
necessitamos de hipo´teses adequadas sobre f e o ponto inicial x0 para garantir convergeˆncia (quadra´tica) da
sequ¨eˆncia para um zero de f .
r:con Observac¸a˜o 1. Suponhamos que I ⊂ R seja um conjuto aberto e f : I¯ → R e´ uma func¸a˜o diferencia´vel em
I e cont´ınua em I¯ o fecho de I. Se {xk} esta´ bem definida (xk ∈ I e f ′(xk) 6= 0 ∀ k), converge para algum
x∗ ∈ I¯ e {f ′(xk)} e´ limitada, enta˜o f(x∗) = 0. De fato, de (1) temos
f(xk) + f
′(xk)(xk+1 − xk) = 0.
Tomando limite nesta equac¸a˜o, segue-se que f(x∗) = 0, pois {xk} ⊂ I, limk→∞ xk = x∗ ∈ I¯, f e´ cont´ınua
em I¯ e {f ′(xk)} e´ limitada. Em particular, sempre que f ′ for cont´ınua enta˜o {f ′(xk)} e´ limitada.
2.1 Exemplos
ex:0 Exemplo 1. Seja f : R → R dada por f(x) = x1/3. Sabemos que x = 0 e´ a u´nica ra´ız de f , que f e´ uma
func¸a˜o continuamente diferencia´vel em R/{0} e cont´ınua em R. Note que f ′(x) = (1/3)x−2/3 6= 0 se x 6= 0
e que para x0 6= 0 a sequeˆncia de Newton {xk} e´ dada por
xk+1 = −2xk , k = 0, 1, 2, . . . ,
ou equivalentemente,
xk = (−2)k x0 , k = 0, 1, 2, . . . .
Portanto, para todo ponto inicial x0 6= 0 temos que a sequeˆncia de Newton {xk} esta´ bem definida e na˜o
converge. Note ainda que limx→0 |f ′(x)| = +∞.
2
ex:0 Exemplo 2. Seja f : R → R dada por f(x) = x2/3. Sabemos que x = 0 e´ a u´nica ra´ız de f , que f e´ uma
func¸a˜o continuamente diferencia´vel em R/{0} e cont´ınua em R. Note que f ′(x) = (2/3)x−1/3 6= 0 se x 6= 0
e que para x0 6= 0 a sequeˆncia de Newton {xk} e´ dada por
xk+1 = −xk/2 , k = 0, 1, 2, . . . ,
ou equivalentemente,
xk = (−1/2)k x0 , k = 0, 1, 2, . . . .
Portanto, para todo ponto inicial x0 6= 0 temos que a sequeˆncia de Newton {xk} esta´ bem definida e converge.
Note ainda que limx→0 |f ′(x)| = +∞. Assim, a condic¸a˜o de limitac¸a˜o da derivada pro´ximo da ra´ız na
Observac¸a˜o 1 e´ apenas suficiente.
ex:1 Exemplo 3. Seja f : R → R dada por f(x) = x3. Sabemos que x = 0 e´ a u´nica ra´ız de f . Note que
f ′(x) = 3x2 6= 0 se x 6= 0 e que para x0 6= 0 a sequeˆncia de Newton {xk} e´ dada por
xk+1 =
2
3
xk , k = 0, 1, 2, . . . ,
ou equivalentemente,
xk = (2/3)
k x0 , k = 0, 1, 2, . . . .
Portanto, temos que independente da escolha do ponto inicial, a sequ¨eˆncia de Newton para resolver f(x) = 0
esta´ bem definida e converge para a u´nico zero da func¸a˜o, x∗ = 0. Neste caso, a taxa de convergeˆncia da
sequeˆncia {xk} e´ linear, como veremos, isto e´ devido ao fato que f ′(x∗) = 0.
ex:0 Exemplo 4. Seja f : R → R dada por f(x) = x5/3 + x. Sabemos que x = 0 e´ a u´nica ra´ız de f , que f e´
uma func¸a˜o continuamente diferencia´vel . Note que f ′(x) = (5/3)x2/3 + 1 6= 0 e que para x0 6= 0 a sequeˆncia
de Newton {xk} e´ dada por
xk+1 =
2
5
x
5/3
k
(5/3)x
2/3
k + 1
, k = 0, 1, 2, . . . ,
o que implica,
xk+1 ≤ 2
5
x
5/3
k =
[
2
5
x
2/3
k
]
xk , k = 0, 1, 2, .
Portanto, para todo ponto inicial x0 6= 0 temos que a sequeˆncia de Newton {xk} esta´ bem definida e converge
para a u´nico zero da func¸a˜o, x∗ = 0. Neste caso, a taxa de convergeˆncia da sequeˆncia {xk} e´ super-linear,
como veremos, isto e´ devido ao fato que limx→0 |f ′′(x)| = +∞.
ex:exitenewton Exemplo 5. Considere a func¸a˜o f : R→ R dada por f(x) = x/√1 + x2. Note que x = 0 e´ a u´nica zero de
f e que
f ′(x) =
1
(1 + x2)3/2
6= 0, ∀ x ∈ R.
Para todo ponto inicial x0 6= 0 temos que a sequ¨eˆncia de Newton {xk} esta´ bem definida e vale
xk+1 = −x3k, k = 0, 1, 2, . . . .
ou equivalentemente,
xk = (−1)k x3k0 , k = 0, 1, 2, . . . .
Assim e´ fa´cil concluir que:
3
i) se |x0| = 1, enta˜o a sequeˆncia de Newton {xk} oscila entre os valores 1 e −1;
ii) se |x0| < 1, enta˜o a sequeˆncia de Newton {xk} converge para x∗ = 0 com taxa cu´bica;
iii) se |x0| > 1, enta˜o a sequeˆncia de Newton {xk} diverge, isto e´, limk→∞ |xk| =∞.
Isto mostra que a escolha do ponto inicial e´ importante para garantir a convergeˆncia da sequeˆncia de Newton.
Se o ponto inicial na˜o for escolhido adequadamente a sequeˆncia de Newton pode oscilar ou divergir.
Exemplo 6. Considere a func¸a˜o f : (0,+∞) → R dada por f(x) = 1 − 1/x. Note que x∗ = 1 e´ o u´nico
zero de f e que f ′(x) = 1/x2 6= 0 para todo x ∈ (0,+∞). A sequeˆncia de Newton {xk} para encontrar uma
ra´ı da equac¸a˜of(x) = 0 e´ formalmente dada por
xk+1 = xk(2− xk), k = 0, 1, 2, . . . .
Neste caso, podemos verificar que:
i) se x0 ≥ 2, enta˜o x1 6∈ (0,+∞). Assim, a sequeˆncia de Newton na˜o esta´ bem definida. Neste caso, a
boa definic¸a˜o falhar porque o me´todo de Newton gera um ponto fora do dominio da func¸a˜o.
ii) se 0 < x0 < 2, enta˜o a sequeˆncia esta´ bem definida e converge para x∗ = 1.
Portanto, temos que a boa definic¸a˜o da sequeˆncia de Newton {xk}, bem como sua convergeˆncia, esta condi-
cionada ao ponto inicial ser tomado em um intevalo adquado.
Exemplo 7. Considere a func¸a˜o f : R → R dada por f(x) = x(x − 1)(x + 1) = x3 − x. Note que os zeros
de f sa˜o 0, 1 e −1. Observe que f ′(x) = 3x2 − 1 e a sequ¨eˆncia de Newton para encontrar uma zero de f e´
dada formalmente por
xk+1 =
2x3k
3x2k − 1
, k = 0, 1, 2, . . . .
Assim, podemos verifivar facilmente que:
i) se |x0| = 1/
√
5, enta˜o a sequeˆncia de Newton oscila entre 1/
√
5 e −1/√5;
ii) se |x0| = 1/2 , enta˜o a sequeˆncia de Newton e´ finita (converge!). Portanto, a sequeˆncia de Newton e´
finita (converge!);
iii) Para x0 = −0, 46544 . . ., isto e´, um zero do polinoˆmio p(x) = 2
√
3x3 − 3x2 + 1, temos que
1√
3
=
2x30
3x20 − 1
.
Neste caso, o me´todo de Newton gera o ponto x1 = 1/
√
3. Assim, o me´todo de Newton gera um ponto
singular da derivada, neste caso, a sequeˆncia de Newton na˜o esta bem definida.
Portanto, tomando |x0| = 1/2 temos que a sequeˆncia de Newton converge em um u´nico passo!. Agora
tomando x0 como sendo a ra´ız real do polinoˆmio q(x) = 2
√
3x3 + 3x2 − 1, teremos x1 = −1/
√
3 que e´ um
ponto singular da derivada. Isto mostra que a sequeˆncia de Newton pode na˜o estar bem definida com essa
escolha de x0.
4
2.2 Teoremas de Convergeˆncia Local do Me´todo de Newton
lkant
Nesta sec¸a˜o vamos estudar algumas propriedades de convergeˆncias do me´todo de Newton. Vamos mostrar
primeiro que sob certas hipo´teses o me´todo de Newton converge quando o ponto inicial esta pro´ximo a
soluc¸a˜o e enta˜o, sob hipo´teses adicionais, vamos estimar a raio de convergeˆncia do me´todo.
2.2.1 Teorema de Convergeˆncia Ba´sico
Nesta sec¸a˜o vamos mostrar que sob certas hipo´teses, existe um intervalo que conte´m a soluc¸a˜o tal que
tomando o ponto inicial neste intervalo o me´todo de Newton converge.
th:nlocII Theorema 1. Seja I um intervalo aberto, f : I → R uma func¸a˜o continuamente diferencia´vel e x∗ ∈ I.
Suponhamos que a derivada f ′ seja cont´ınua em x∗, f(x∗) = 0 e f ′(x∗) 6= 0. Enta˜o, existe δ > 0 tal
que a sequeˆncia gerada pelo me´todo de Newton para resolver a equac¸a˜o f(x) = 0, com ponto inicial x0 ∈
(x∗ − δ, x∗ + δ) ⊂ I,
xk+1 = xk − (f(xk)− y)/f ′(xk), k = 0, 1, . . . , (2) eq:dnsII
esta´ bem definida, esta´ contida em (x∗ − δ, x∗ + δ), converge para x∗ e vale
lim
k→∞
|xk+1 − x∗|
|xk − x∗| = 0.
Para provar o teorema acima precisaremos de alguns resultados.
eq:banach Lema 2. Seja κ := sup{t > 0 : (x∗ − t, x∗ + t) ⊂ I}. Se f ′ e´ cont´ınua em x∗ e f ′(x∗) 6= 0 enta˜o existe
0 < δ¯ < κ tal que para x ∈ (x∗ − δ¯, x∗ + δ¯) tem-se que f ′(x) 6= 0 e
1
|f ′(x)| <
2
|f ′(x∗)| .
Demonstrac¸a˜o. Como f ′ e´ cont´ınua em x∗ e pela definic¸a˜o de continuidade, dado ε > 0 existe 0 < δ¯ < κ tal
que |x− x∗| < δ¯ implica em |f ′(x)− f ′(x∗)| < ε. Assim, considerando ε = |f ′(x∗)|/2 e usando propriedades
do mo´dulo, temos
||f ′(x)| − |f ′(x∗)|| ≤ |f ′(x)− f ′(x∗)| < |f
′(x∗)|
2
.
Apo´s algumas manipulac¸o˜es alge´bicas simples na desigualdade acima e´ fa´cil ver que
|f ′(x∗)|
2
< |f ′(x)|,
o que implica f ′(x) 6= 0. Como a desigualdade anterior e´ equivalente a desigualdade desejada, o lema esta
provado.
O Lema 2 garante que f ′ 6= 0 no intervalo (x∗ − δ¯, x∗ + δ¯) e assim obtemos a boa definic¸a˜o da func¸a˜o
iterac¸a˜o de nf Newton neste intervalo
nf : (x∗ − δ¯, x∗ + δ¯) → R
x 7→ x− f(x)/f ′(x). (3) NF0II
5
le:bd Lema 3. Seja nf como definido em (3). Enta˜o nf e´ deriva´vel em x∗ e n′f (x∗) = 0. Ale´m disso, dado
0 < β < 1, existe 0 < δ < δ¯ tal que
|nf (x)− nf (x∗)| < β|x− x∗|, ∀ x ∈ (x∗ − δ, x∗ + δ). (4) eq:bd
Como consequeˆncia,
nf ((x∗ − δ, x∗ + δ)) ⊂ (x∗ − δ, x∗ + δ).
Demonstrac¸a˜o. Seja 0 < δ¯ como no Lema 2. Enta˜o usando a hipo´tese f(x∗) = 0, a definic¸a˜o da func¸a˜o
iterac¸a˜o de Newton e nf (x∗) = x∗, e´ fa´cil ver que
nf (x)− nf (x∗)
x− x∗ =
1
f ′(x)
[
f ′(x)−
(
f(x)− f(x∗)
x− x∗
)]
, ∀ x ∈ (x∗ − δ¯, x∗ + δ¯), x 6= x∗.
Tomando limite na igualdade acima com x tendendo a x∗ e considerando que f ′ e´ cont´ınua em x∗ e f ′(x∗) 6= 0
conclu´ımos que
lim
x→x∗
nf (x)− nf (x∗)
x− x∗ = 0.
que e´ o resultado desejado da primeira parte do lema. Para demonstrar a inclusa˜o, primeiro fixe 0 < β < 1.
Assim, segue da igualdade acima que existe 0 < δ < δ¯ tal que
|nf (x)− nf (x∗)|
|x− x∗| < β, ∀ x ∈ R; |x− x∗| < δ,
o que e´ equivalentemente a (4). Agora, como nf (x∗) = x∗, 0 < β < 1, a desigualdade (4) implica que
|nf (x)− x∗| < δ para todo x ∈ R tal que |x− x∗| < δ, o que nos da´ a inclusa˜o desejada.
Prova do Teorema 1
Agora ja´ temos todos os resultados necessa´rios para demonstrar o Teorema 1. Primeiro note que a
sequeˆncia de Newton {xk} descrita em (2) pode, via a definic¸a˜o (3), ser escrita equivalentemente na forma
xk+1 = nf (xk), k = 0, 1, . . . . (5) eq:dnsII_1
Demonstrac¸a˜o. Seja 0 < β < 1 e δ > 0 como no Lema 3. Como nf (x∗) = x∗, segue do Lema 3 que
|nf (x)− x∗| < β|x− x∗|, ∀ x ∈ (x∗ − δ, x∗ + δ). (6) eq:bd1
Seja x0 ∈ (x∗ − δ, x∗ + δ). Segue imediatamente da inclusa˜o no Lema 3 que a sequeˆnia xk+1 = nf (xk) com
ponto inicial x0 esta´ bem definida e esta´ contida no intervalo (x∗ − δ, x∗ + δ). Para provar que a sequeˆncia
{xk} converge para x∗, vamos primeiro mostra por induc¸a˜o a seguinte desigualdade:
|xk − x∗| < βk|x0 − x∗|, k = 0, 1, . . . . (7) eq:csII
Vamos mostrar que a desigualdade e´ va´lida para k = 1. Usando a definic¸a˜o (3) temos x1 = nf (x0). Assim,
como nf (x∗) = x∗, segue do Lema 3 que
|x1 − x∗| < β|x0 − x∗|.
6
Agora suponhamos que (7) e´ va´lida. Usando a definic¸a˜o (3) temos xk+1 = nf (xk). Assim, como nf (x∗) = x∗
e xk ∈ (x∗ − δ, x∗ + δ), segue novamente do Lema 3 que
|xk+1 − x∗| < β|xk − x∗|,
e enta˜o, usando a hipo´tese de induc¸a˜o, a desigualdade acima se reduz a
|xk+1 − x∗| < βk+1|x0 − x∗|,
o que conclui a prova por induc¸a˜o. Portanto, como 0 < β < 1 tomando limite em (7) com k tendendo a
infinito, conclu´ımos que {xk} converge para x∗.
Para provar u´ltima igualdade, primeiro note que o Lema 3 nos fornece |n′f (x∗)| = 0. Como {xk} converge
para x∗ quando k tende ao infinito, conclu´ımos
lim
k→∞
|nf (xk)− nf (x∗)|
|xk − x∗| = 0,
que e´ equivalente a desigualdade desejada. A u´tlima afrimac¸a˜o do Teorema segue do Lema
2.2.2 Teorema de Convergeˆncia Sob a Condic¸a˜o Lipschitz
Nesta sec¸a˜o vamos mostrar que adicionando hipo´teses a derivada do func¸a˜o na˜o linear podemos estimar
o intervalo de conergeˆncia do me´todo de Newton. A otimalidade do intervalo de convergeˆncia do Me´todo
de Newton, contidos no pro´ximo teorema, foram formulados a partir dos artigos Rall [8] and Traub and
Wozniakowski [9].
th:nloc Theorema 4. Sejam I ⊂ R um intervalo aberto e f : I → R e x∗ ∈ I. Suponha que f e´ continuamente
diferencia´vel em I, f ′(x∗) na˜o-singular, f(x∗) = 0 e existe K > 0 tal que
|f ′(x∗)−1[f ′(x)− f ′(y)]| ≤ K|x− y|, ∀ x, y ∈ I. (8) eq:lip1
Sejam κ := sup{t > 0 : (x∗ − t, x∗ + t) ⊂ I} e r := min{κ, 2/(3K)}. Enta˜o, a sequeˆncia gerada pelo me´todo
de Newton para resolver f(x) = 0 com ponto inicial x0 ∈ (x∗ − r, x∗ + r),
xk+1 = xk − f(xk)/f ′(xk), k = 0, 1, . . . , (9) eq:dns
esta bem definida, esta contida em (x∗ − r, x∗ + r), converge para x∗ e vale
|x∗ − xk+1| ≤ K
2(1−K|x0 − x∗|) |xk − x∗|
2, k = 0, 1, . . .
Ale´m disso, o ponto x∗ e´ o u´nico zero de f no intervalo(x∗ − 2/K, x∗ + 2/K) e se 2/(3K) < κ enta˜o
(x∗ − 2/(3K), x∗ + 2/(3K)) e´ o maior intervalo de convergeˆncia poss´ıvel.
Observac¸a˜o 2. Como ‖x∗ − x0‖ < 2/(3K) a u´ltima equac¸a˜o no Theorem 4 implica que
|x∗ − xk+1| ≤ [3K/2]|xk − x∗|2, k = 0, 1, . . .
A partir desta equac¸a˜o podemos mostrar, por induc¸a˜o, que
|x∗ − xk| ≤ [2/(3K)] ([3K/2] |x0 − x∗|)2
k
, k = 0, 1, . . . .
Esta desigualdade implica, em particular, que para dobrar o nu´mero de d´ıgitos exatos basta aplicar uma
iterac¸a˜o de Newton.
7
Observac¸a˜o 3. Se a func¸a˜o f : Ω→ R satisfaz a cla´ssica condic¸a˜o de Lipschitz para a derivada
|f ′(x)− f ′(y)| ≤ L|x− y|, x, y ∈ I,
onde L > 0. Enta˜o ela tambe´m satisfaz (8) com K = L|f ′(x∗)−1|. Neste caso, o raio de convergeˆncia do
me´todo de Newton e´ r = 2/(3L|f ′(x∗)−1|). Note que, se f : Ω→ R e´ duas vezes deriva´vel enta˜o a condic¸a˜o
Lipschitz e´ equivalente a derivada segunda ser limitada. Assim, o Exemplo 4 mostra que e´ razoa´vel pedir que
f satisfac¸a a condic¸a˜o Lipschitz para se obter convergeˆncia quadra´tica.
Theorema 5. ( Teorema cla´ssico ) Sejam I ⊂ R um intervalo aberto e f : I → R e x∗ ∈ I. Suponha que fth:nloc2
e´ continuamente diferencia´vel em Ω, f ′(x∗) na˜o-singular, f(x∗) = 0 e existe L > 0 tal que
|f ′(x)− f ′(y)| ≤ L|x− y|, ∀ x, y ∈ I. (10) eq:lip2
Sejam
κ := sup{t > 0 : (x∗ − t, x∗ + t) ⊂ I}, r := min
{
κ,
2|f ′(x∗)|
3L
}
.
Enta˜o, a sequeˆncia {xk} gerada pelo me´todo de Newton para resolver a equac¸a˜o f(x) = 0, com ponto inicial
x0 ∈ (x∗ − r, x∗ + r),
xk+1 = xk − f(xk)/f ′(xk), k = 0, 1, . . . , (11) eq:dns
esta bem definida, esta contida em (x∗ − r, x∗ + r), converge para x∗ e vale
|x∗ − xk+1| ≤ L
2 (|f ′(x∗)| − L|x0 − x∗|) |xk − x∗|
2, k = 0, 1, . . . .
Para provar o teorema acima precisamos de alguns resultados preliminares. De agora em diante vamos
assumir que todas as hipo´teses do teorema sa˜o va´lidas.
wdns Lema 6. Seja x ∈ I. Se x ∈ (x∗ − 1/K, x∗ + 1/K), enta˜o f ′(x) 6= 0 e∣∣∣∣f(x∗)f ′(x)
∣∣∣∣ ≤ 11−K|x− x∗| .
Em particular, f ′(x) 6= 0 para todo x ∈ (x∗ − r, x∗ + r).
Demonstrac¸a˜o. Seja x ∈ Ω. Como |x− x∗| < 1/K temos de (8) que
|f ′(x)/f ′(x∗)− 1| = |f ′(x∗)−1[f ′(x)− f ′(x∗)]| ≤ K|x− x∗| < 1.
Enta˜o, a u´ltima desiqualdade implica que f ′(x∗)−1f ′(x) 6= 0, e assim f ′(x) 6= 0, e vale
|f ′(x)−1f ′(x∗)| ≤ 1
1− |f ′(x∗)−1f ′(x)− 1| ≤
1
1−K|x− x∗|
Como r ≤ 2/(3K) < 1/K a u´ltima afirmac¸a˜o do lema segue-se.
pr:taylor Lema 7. Se x ∈ (x∗ − κ, x∗ + κ), enta˜o vale
|f ′(x∗)−1(f(y)− [f(x) + f ′(x)(y − x)])| ≤ K
2
|x− y|2.
8
Demonstrac¸a˜o. Note que x∗ + (1− u)(x− x∗) ∈ (x∗ − κ, x∗ + κ), para 0 ≤ u ≤ 1. Como f e´ continuamente
diferencia´vel em I, temos
f ′(x∗)−1[f(y)− f(x)− f ′(x)(y − x)] ≤
∫ 1
0
f ′(x∗)−1 [f ′(x)− f ′(y + (1− u)(x− y))] ‖x− y‖ du.
E´ fa´cil concluir a partir da u´ltima equac¸a˜o e da hipo´tese (8) que
|f ′(x∗)−1(f(y)− [f(x) + f ′(x)(y − x)])| ≤
∫ 1
0
K|x− x∗|2 u du.
Calculando a integral obtemos o resultado desejado.
O Lemma 6 garante na˜o-singularidade de f ′ em (x∗ − r, x∗ + r) e assim boa definic¸a˜o da applicac¸a˜o
iterac¸a˜o de Newton nf nesta regia˜o
nf : (x∗ − r, x∗ + r) → R
x 7→ x− f(x)/f ′(x). (12) NF
Note que podemos aplicar uma iterac¸a˜o de Newton em qualquer x ∈ (x∗− r, x∗+ r) para obter nf (x) o qual
pode ou na˜o pertencer ao intervalo (x∗ − r, x∗ + r), ou ainda, pode na˜o pertencer ao domı´nio de f . Assim,
isto e´ suficiente apenas para garanir boa definic¸a˜o de apenas uma iterac¸a˜o. Para assegurar que a iterac¸a˜o de
Newton possa ser repetida indefinidamente, precisamos de mais alguns resultados adicionais.
le:cl Lema 8. Seja x ∈ I. Se x ∈ (x∗ − r, x∗ + r) enta˜o
|nf (x)− x∗| ≤ K
2(1−K|x− x∗|) |x− x∗|
2 < |x− x∗|.
Em particular, nf ((x∗ − r, x∗ + r)) ⊂ (x∗ − r, x∗ + r).
Demonstrac¸a˜o. Como r < 1/K, o Lema 6 implica que f ′(x) e´ na˜o-singular. Enta˜o, como f(x∗) = 0 algumas
manipulac¸o˜es implicam
x∗ − nf (x) = −f ′(x)−1 [f(x∗)− f(x)− f ′(x)(x∗ − x)] ,
Combinando a equac¸a˜o acima, Lema 6 e Lema 7 obtemos
|x∗ − nf (x)| ≤ | − f ′(x)−1f ′(x∗)| |f ′(x∗)−1[f(x∗)− f(x)− f ′(x)(x∗ − x)]| ≤ K|x− x∗|
2/2
1−K|x− x∗| .
que e´ a primeira desigualdade. Agora, como |x − x∗| < r ≤ 2/(3K) obtemos imediatamente a u´ltima
desigualdade. A u´tima afirmac¸a˜o e´ imediata da u´ltima desiguialdade.
l:uniq Lema 9. O ponto x∗ e´ o u´nico zero de f no intervalo (x∗ − 2/K, x∗ + 2/K).
Demonstrac¸a˜o. Suponhamos que f(y) = 0 e |y − x∗| < 2/K. Como f(x∗) = 0 e F (y) = 0 temos
y − x∗ = −
∫ 1
0
f ′(x∗)−1 [f ′(x∗ + u(y − x∗))− f ′(x∗)] (y − x∗)du.
9
Usando (8) com x = x∗ + u(y − x∗) e y = x∗ e´ fa´cil concluir da u´ltima igualdade que
|y − x∗| ≤
∫ 1
0
K|y − x∗|2u du = K
2
|y − x∗|2.
Se y 6= x∗, enta˜o obtemos da u´ltima desigualdade que 2/K ≤ |y − x∗| o que e´ absurdo. Portanto, y = x∗ e
assim x∗ e´ o u´nico zero de f no intervalo (x∗ − 2/K, x∗ + 2/K).
l:best Lema 10. Se 2/(3K) < κ, enta˜o r = 2/(3K) e´ o maior raio de convergeˆncia poss´ıvel.
Demonstrac¸a˜o. Suponhamos que 2/(3K) < κ. Defina a func¸a˜o h : (−κ, κ)→ R por
h(t) = −K
2
t2 − t, para t ∈ (−κ, 0], e h(t) = K
2
t2 − t, para t ∈ [0, κ). (13) eq:dh
Note que h(0) = 0, h′(t) = K|t| − 1 para t ∈ (−κ, κ). Enta˜o temos∣∣h′(0)−1 [h′(t)− h′(u)]∣∣ ≤ K| |t| − |u| | ≤ K|t− u|, t, u ∈ (−κ, κ).
Assim, f = h satisfaz todas as hipoo´teses do Theorem 4. Enta˜o como ρ < κ e´ suficiente mostrar que o
me´todo de Newton para resolver a equac¸a˜o h(t) = 0, com ponto inicial t0 = −2/(3K) na˜o converge. Pela
definic¸a˜o de h em (13) temos
t1 = −2/(3K)− h(−2/(3K))/h′(−2/(3K)) = 2/(3K).
Novamente, a definic¸a˜o de h em (13) implica
t2 = 2/(3K)− h(2/(3K))/h′(2/(3K)) = −2/(3K).
Portanto, o me´todo de Newton para resolver a equac¸a˜o h(t) = 0, com ponto inicial t0 = −2/(3K), produz a
sequeˆncia
t0 = −2/(3K), t1 = 2/(3K), t2 = −2/(3K), . . . ,
em particular ela na˜o converge e o lema esta provado.
Prova do Teorema 4
Primeiro note que a equac¸a˜o (11) junto com (12) implicam that a sequeˆncia {xk} satisfaz
xk+1 = nf (xk), k = 0, 1, . . . , (14) NFS
que e´ de fato uma definic¸a˜o equivalente para esta sequeˆncia.
Demonstrac¸a˜o. Como x0 ∈ (x∗ − r, x∗ + r). Usando (14), inclusa˜o nf ((x∗ − r, x∗ + r)) ⊂ (x∗ − r, x∗ + r) do
Lema 8 e o Lema 6, concluimos que {xk} esta bem definita e contida na bola (x∗ − r, x∗ + r).
Agora vamos provar a convergeˆncia de {xk}. Primeiro note que, como {xk} esta contida na bola (x∗ −
r, x∗ + r), temos de (14) e Lema 8 que
|xk+1 − x∗| = |nf (xk)− x∗| < |xk − x∗|.
Assim, a sequeˆncia {|xk − x∗|} e´ estritamente decrescente. Enta˜o, tambe´m pelo Lema 8 temos que
|xk+1 − x∗| = |nf (xk)− x∗| ≤ K
2(1−K|xk − x∗|) |xk − x∗|
2 <
K
2(1−K|x0 − x∗|) |xk − x∗|
2, k = 0, 1, . . . .
10
Por outro lado, como |x0 − x∗| < r ≤ 2/(3K) temos da desigualdade acima que
|xk+1 − x∗| ≤ K|x0 − x∗|
2(1−K|x0 − x∗|) |xk − x∗|,
K
2(1−K|x0 − x∗|) < 1, k = 0, 1, . . . .
e isto mostra que a sequeˆncia {‖xk − x∗‖} converge para zero, isto e´, que {xk} converge para x∗. A u´ltima
parte do teorema segue do Lema 9 e Lema 10.
Refereˆncias
BCSS97 [1] Blum, L., Cucker, F. Shub, M. and Smale, S. Complexity and real computation, Springer-Verlag, New
York, (1997).
DS96 [2] Dennis, J. E. Jr., Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear
Equations, SIAM Classics in Applied Mathematics, Philadelphia, 1996.
KP02 [3] Krantz, S. G., Parks ,H. R., The implicit function theorem : history, theory, and applications, Boston,
Birkha¨user, (2002).
M61 [4] Moser, J., A new techniques for the construction of solutions of nonlinear differential equations, Proc.
Nat. Acad. sci. USA, 47 (1961), pp. 1824-1831.
N56 [5] Nash, J., The embedding problem for Riemannian manifolds, Ann. of Math. 63, (1956), pp. 20–63.
NN-94 [6] Nesterov, Y. and Nemirovskii, A. Interior-Point Polynomial Algorithmsin Convex Programming, SIAM
Studies in Applied Mathematics, 13, Philadelphia, (1994).
P04 [7] Polyak, B. T., Newton’s method and its use in optimization. To appear in European Journal of Opera-
tional Research (2006), doi:10.1016/j.ejor.2005.06.076.
r74 [8] Rall, L. B., A note on the convergence of Newton’s Method, SIAM J. Numer. Anal. 11, 1 (19974), pp.
34–36.
TW79 [9] Traub, J. F. and H. Wozniakowski, ,Convergence and complexity of Newton iteration for operator equa-
tion, Journal of the Association Computing Machinery, 26, 2 (1979), pp. 250 - 258.
W96 [10] Wayne, C. E., An introduction to KAM theory. Dynamical systems and probabilistic methods in partial
differential equation, Lectures in Appl. Math., 31, Amer. Math. Soc., Providence, 1996.
11