ads:
UNIVERSIDADE FEDERAL DE GOI
´
AS
INSTITUTO DE MATEM
´
ATICA E ESTAT
´
ISTICA
Convergˆencia Local do M´etodo de Newton Inexato
e Suas Varia¸c˜oes do Ponto de Vista do Princ´ıpio
Majorante de Kantorovich
por
Max Leandro Nobre Gon¸calves
Orientador: Dr. Orizon Pereira Ferreira
Disserta¸c˜ao de Mestrado em Matem´atica
Goiˆania, Goi´as
2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ads:
UNIVERSIDADE FEDERAL DE GOI
´
AS
INSTITUTO DE MATEM
´
ATICA E ESTAT
´
ISTICA
COORDENAC¸
˜
AO DE P
´
OS-GRADUAC¸
˜
AO EM MATEM
´
ATICA
Convergˆencia Local do M´etodo de Newton Inexato
e Suas Varia¸c˜oes do Ponto de Vista do Princ´ıpio
Majorante de Kantorovich
por
Max Leandro Nobre Gon¸calves
´
Area de Concentra¸c˜ao : Matem´atica Aplicada
Orientador: Dr. Orizon Pereira Ferreira
Disserta¸c˜ao submetida `a Banca Examinadora designada pelo Conselho Diretor do
Instituto de Matem´atica e Estat´ıstica da Universidade Federal de Goi´as, como parte dos
requisitos necess´arios `a obten¸c˜ao do grau de Mestre em Matem´atica.
Goiˆania, Goi´as
2007
Aos meus queridos pais;
Jurandir e Maria de Lourdes
Agradecimentos
`
A Deus, pela prote¸c˜ao durante este percurso da minha carreira estudantil, por ter me
dado a oportunidade e a capacidade, pois sem Deus nada disso seria poss´ıvel.
`
A ele toda
honra e toda gl´oria.
Ao Prof. Dr. Orizon Pereira Ferreira, pela amizade, paciˆencia e dedica¸c˜ao que foram
indispens´aveis para a concretiza¸c˜ao deste trabalho.
`
A minha esposa Ana Paula, pela amizade, compreens˜ao e pelas constantes ajudas.
`
A todos os meus familiares e amigos, que apoiaram-me em mais um degrau de minha
vida. Em especial, aos colegas de mestrado, que ajudaram-me nos momentos de dificul-
dades, n˜ao vou esquecer nenhum de vocˆes.
`
A (CAPES), pela Bolsa de Estudos Concedida, sem a qual seria dif´ıcil a realiza¸c˜ao
desta disserta¸c˜ao
1
1
Este trabalho teve suporte financeiro da CAPES.
Sum´ario
1 Introdu¸c˜ao 1
2 Conceitos B´asicos 5
2.1 No¸c˜oes Topol´ogicas no Espa¸co Euclidiano . . . . . . . . . . . . . . . . . . . 5
2.1.1 No¸c˜oes de An´alise no Espa¸co Euclidiano . . . . . . . . . . . . . . . 7
2.1.2 No¸c˜oes de Norma de Operador no Espa¸co Euclidiano . . . . . . . . 8
2.2 No¸c˜oes de An´alise Convexa . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 A Fun¸c˜ao Majorante 15
3.1 An´alise de uma Fun¸c˜ao Escalar (f) . . . . . . . . . . . . . . . . . . . . . . 15
3.2 A Fun¸c˜ao Majorante Radial (f
r
) . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 A Fun¸c˜ao Majorante Central (f
c
) . . . . . . . . . . . . . . . . . . . . . . . 23
4 M´etodo de Newton Inexato 26
4.1 Convergˆencia do M´etodo de Newton Inexato . . . . . . . . . . . . . . . . . 27
4.1.1 Prova do Teorema 4.1 . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Convergˆencia para Condi¸c˜ao Radial Lipschitz . . . . . . . . . . . . . . . . 30
5 M´etodo Quase-Newton Inexato 32
5.1 Convergˆencia do M´etodo Quase-Newton Inexato . . . . . . . . . . . . . . . 32
5.1.1 Prova do Teorema 5.1 . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Resultados para Condi¸c˜ao Radial Lipschitz . . . . . . . . . . . . . . . . . . 36
6 M´etodo de Newton Modificado Inexato 39
6.1 Convergˆencia do m´etodo de Newton modificado inexato . . . . . . . . . . . 39
6.1.1 Prova do Teorema 6.1 . . . . . . . . . . . . . . . . . . . . . . . . 42
6.2 Resultados para Condi¸c˜ao Central Lipschitz . . . . . . . . . . . . . . . . . 43
Considera¸c˜oes Finais 46
Referˆencias Bibliogr´aficas 49
8
Resumo
A busca por solu¸c˜oes de equa¸c˜oes n˜ao-lineares nos espa¸cos Euclidianos ´e objeto de interesse
em v´arias ´areas da ciˆencia e das engenharias. Devido a sua velocidade de convergˆencia
e eficiˆencia computacional, o m´etodo de Newton inexato e suas varia¸c˜oes tˆem sido bas-
tante utilizados para o prop´osito de obter solu¸c˜oes dessas equa¸c˜oes. Nesta disserta¸c˜ao
apresentamos uma an´alise de convergˆencia local do m´etodo de Newton inexato e algumas
de suas varia¸c˜oes, mais especificamente, o m´etodo quase-Newton inexato e o m´etodo de
Newton modificado inexato. Esta an´alise tem a desvantagem de exigir o conhecimento
pr´evio de um zero do operador em considera¸c˜ao e hip´oteses sobre o comportamento do
operador nesse zero, mas por outro lado ela fornece informa¸c˜oes sobre a taxa e o raio de
convergˆencia.
Abstract
The search for solutions of nonlinear equations in the Euclidean spaces is object of interest
in some areas of science and engineerings. Due the speed of convergence and computa-
tional efficiency, the inexact Newton method and its variations have been sufficiently used
to obtain solutions of these equations. In this dissertation we present a local analysis of
convergence of the inexact Newton method and some of its variations, more specifically,
the inexact Newton-like method and the inexact modified Newton method. This analy-
sis has the disadvantage to demand the previous knowledge of a zero of the operator in
consideration and the hypotheses on the behavior of the operator at this zero, but on the
other hand it supplies to information on the convergence rate and convergence radius.
Cap´ıtulo 1
Introdu¸c˜ao
Resolver um sistema de equa¸c˜oes n˜ao-lineares ´e encontrar um ponto que satisfa¸ca todas
as equa¸c˜oes simultaneamente. Existem v´arios m´etodos para resolver um sistema n˜ao-
linear, mas o m´etodo de Newton e suas varia¸c˜oes s˜ao os mais eficientes. Neste trabalho,
analisaremos a convergˆencia do m´etodo de Newton inexato e algumas de suas varia¸c˜oes.
Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
uma fun¸c˜ao continuamente di-
ferenci´avel. Considere o sistema de equa¸c˜oes n˜ao-lineares
F (x) = 0. (1.1)
Os processos iterativos cl´assicos usados para resolver (1.1) s˜ao formalmente descritos como:
dado x
0
∈ Ω defina
x
k+1
= x
k
+ s
k
, B
k
s
k
= −F (x
k
), k = 0, 1, .... (1.2)
Em particular, o processo acima ´e o m´etodo de Newton se B
k
= F
(x
k
), ´e o m´etodo Newton
modificado se B
k
= F
(x
0
) ou ´e o m´etodo quase-Newton se B
k
´e uma aproxima¸c˜ao de
F
(x
k
). Uma perspectiva hist´orica recente das aplica¸c˜oes do m´etodo de Newton pode ser
encontrada em [11].
´
E bem conhecido que, sob certas condi¸c˜oes, o m´etodo de Newton tem
convergˆencia local quadr´atica para uma solu¸c˜ao de (1.1), veja por exemplo, [1], [2] e [5].
No entanto, resolver em cada passo o sistema linear (1.2) pode ser computacionalmente
muito “caro”se o n´umero de inc´ognitas for muito grande, e isto n˜ao se justifica quando
a iterada corrente est´a longe da solu¸c˜ao. Uma alternativa ´e resolver aproximadamente o
sistema linear, o que da origem a uma nova classe de processos iterativos, os quais s˜ao
1
2
conhecidos como m´etodos inexatos. Os m´etodos inexatos usados para resolver (1.1) s˜ao
formalmente descritos como: dado x
0
∈ Ω defina
x
k+1
= x
k
+ s
k
, B
k
s
k
= −F (x
k
) + r
k
, r
k
≤ θ
k
F (x
k
), k = 0, 1, ..., (1.3)
onde a seq¨uˆencia de n´umeros reais {θ
k
} ´e dada. A seq¨uˆencia {θ
k
} ´e usualmente chamada de
seq¨uˆencia “forcing”e ´e tomada uniformemente limitada por 1. Em particular, o processo
acima ´e o m´etodo de Newton inexato se B
k
= F
(x
k
), ´e o m´etodo Newton modificado
inexato se B
k
= F
(x
0
) ou ´e o m´etodo quase-Newton inexato se B
k
´e uma aproxima¸c˜ao
de F
(x
k
). Observe que se anularmos a seq¨uˆencia“forcing”, isto ´e, θ
k
= 0 para todo k, o
m´etodo de Newton inexato e suas varia¸c˜oes se reduzem aos m´etodos cl´assicos de Newton
e suas varia¸c˜oes.
Para o m´etodo de Newton inexato e suas varia¸c˜oes a convergˆencia local pode ser
medida em termos da seq¨uˆencia“forcing”θ
k
. Seja . qualquer norma em R
n
subordinada
a uma norma de matriz R
n×n
. Em [3] ´e mostrado que sob a hip´otese usual, ou seja, θ
k
uniformemente limitada por 1, o m´etodo de Newton inexato define uma seq¨uˆencia {x
k
}
linearmente convergente na norma y
∗
= F
(x
∗
)y para uma solu¸c˜ao x
∗
de (1.1). V´arios
autores (veja [4]-[7]) tˆem proposto diferentes aplica¸c˜oes para o m´etodo de Newton inexato
no campo da an´alise num´erica e tˆem ressaltado a dif´ıcil aplica¸c˜ao do resultado obtido em
[3]. De fato, tais resultados s˜ao dependentes da norma .
∗
, que por sua vez depende da
solu¸c˜ao e assim n˜ao pode ser calculada a priori. Ent˜ao, eles focalizam a an´alise no controle
do crit´erio de parada r
k
≤ θ
k
F (x
k
) e seu efeito nas propriedades de convergˆencia.
Morini (veja [8]) considerou o m´etodo inexato, onde um controle residual relativo
escalado ´e feito em cada itera¸c˜ao. O m´etodo ´e formalmente descrito como: dado x
0
∈ Ω
defina
x
k+1
= x
k
+ s
k
, B
k
s
k
= −F (x
k
) + r
k
, P
k
r
k
≤ θ
k
P
k
F (x
k
), k = 0, 1, ..., (1.4)
onde as seq¨uencias {θ
k
} e {P
k
}, respectivamente de n´umeros reais e de matrizes n × n
invert´ıveis, s˜ao dadas. Observamos que se P
k
= I para todo k, ent˜ao (1.4) se reduz ao
caso (1.3). A vantagem de se introduzir a matriz P
k
´e que, se o sistema linear em (1.4)
for mal condicionado, esta matriz faz uma corre¸c˜ao. Por outro lado, o resultado obtido
em [8] n˜ao torna claro qual o maior raio de convergˆencia da seq¨uˆencia.
3
Nosso objetivo neste trabalho ´e determinar condi¸c˜oes, usando o princ´ıpio majorante
de Kantorovich (veja [12]), que garantam a convergˆencia linear do m´etodo de Newton
inexato e suas varia¸c˜oes, onde o controle residual relativo escalado ´e considerado em cada
itera¸c˜ao da mesma maneira proposta por Morini (veja [8]). Esta nova abordagem deixa
claro a rela¸c˜ao entre a fun¸c˜ao majorante com o operador n˜ao-linear em considera¸c˜ao, o
que n˜ao esta expl´ıcito nas provas anteriores, veja [3], [8] e [10]. Com isso, os resultados
apresentados aqui torna a prova mais simples e mais did´atica. Uma outro objetivo ´e fazer
um estudo completo da fun¸c˜ao majorante, onde quase todos os resultados necess´arios para
a convergˆencia dos m´etodos de Newton e suas varia¸c˜oes s˜ao demonstrados, deixando o
texto “auto-contido”.
Em particular, os resultados alcan¸cados d´a uma id´eia do maior raio de convergˆencia
da seq¨uˆencia. Vale mencionar que, esta an´alise inclui o m´etodo de Newton inexato e suas
varia¸c˜oes como apresentadas em (1.3), bem como, o m´etodo cl´assico de Newton e suas
varia¸c˜oes apresentadas em (1.2). Al´em disso, mostramos nas considera¸c˜oes finais que as
condi¸c˜oes para a convergˆencia obtidas aqui est˜ao de acordo com as teorias apresentadas
em [9] e [10].
Esta disserta¸c˜ao est´a organizada da seguinte forma.
No cap´ıtulo 2, revisamos alguns t´opicos de top ologia, an´alise e norma nos espa¸cos
euclidianos e estudamos conceitos b´asicos de an´alise convexa. Acreditamos obter um
bom embasamento te´orico para a compreens˜ao dos demais cap´ıtulos.
No cap´ıtulo 3, provamos as principais rela¸c˜oes entre a fun¸c˜ao majorante e o operador
n˜ao-linear. Iniciamos com uma an´alise de uma determinada fun¸c˜ao escalar e o m´odulo
da itera¸c˜ao de Newton associada a ela, a qual dar´a resultados importantes para o estudo
das fun¸c˜oes majorante radial e central. Os resultados obtidos aqui s˜ao os principais
instrumentos utilizados no estudo da convergˆencia linear para o m´etodo de Newton inexato
e suas varia¸c˜oes.
No cap´ıtulo 4, concentra-se a discuss˜ao sobre os m´etodos inexatos. Mostramos que sob
certas condi¸c˜oes, a seq¨uˆencia gerada pelo m´etodo de Newton inexato est´a bem definida e
converge para uma solu¸c˜ao de (1.1) com taxa de convergˆencia linear. Por fim, aplicamos
os resultados obtidos para a condi¸c˜ao radial Lipschitz.
No cap´ıtulo 5, mostramos que sob certas condi¸c˜oes, a seq¨uˆencia gerada pelo m´etodo
4
quase-Newton inexato est´a bem definida e converge para uma solu¸c˜ao de (1.1) com taxa
de convergˆencia linear. Por fim, aplicamos os resultados obtidos para a condi¸c˜ao radial
Lipschitz.
No cap´ıtulo 6, mostramos que sob certas condi¸c˜oes, a seq¨uˆencia gerada pelo m´etodo
de Newton modificado inexato est´a bem definida e converge para uma solu¸c˜ao de (1.1)
com taxa de convergˆencia linear. Por fim, aplicamos os resultados obtidos para a condi¸c˜ao
central Lipschitz.
Finalmente, encerramos esta disserta¸c˜ao exp ondo algumas considera¸c˜oes finais e apre-
sentando um exemplo, onde anulando a seq¨uˆencia “forcing”o raio de convergˆencia para o
m´etodo de Newton inexato obtido ´e o maior poss´ıvel.
Cap´ıtulo 2
Conceitos B´asicos
Nosso objetivo neste cap´ıtulo ´e revisar alguns t´opicos dos espa¸cos euclidianos e an´alise con-
vexa, incluindo alguns resultados de caracteriza¸c˜ao das fun¸c˜oes convexas diferenci´aveis de
vari´avel real. Estes assuntos ser˜ao necess´arios ao desenvolvimento dos cap´ıtulos seguintes,
dando um fundamento te´orico para uma boa compreens˜ao do texto.
2.1 No¸c˜oes Topol´ogicas no Espa¸co Euclidiano
Nesta se¸c˜ao definiremos alguns conjuntos importante do espa¸co euclidiano R
n
, seq¨uencias
no R
n
e taxa de convergˆencia. Provaremos um resultado sobre convergˆencia de seq¨uˆencias
que ser´a necess´ario posteriormente. Iniciaremos definindo bola aberta e fechada.
Sejam dados o ponto a ∈ R
n
e o n´umero real δ > 0. A bola aberta de centro a e raio
δ ´e o conjunto
B(a, δ) = {x ∈ R
n
; x − a < δ},
isto ´e, o conjunto dos p ontos x ∈ R
n
cuja a distˆancia ao ponto a ´e menor do que δ.
Analogamente a bola fechada de centro a e raio δ ´e o conjunto
B[a, δ] = {x ∈ R
n
; x − a δ}.
Um conjunto U ⊂ R
n
´e aberto quando todos os seus pontos s˜ao interiores, ou seja,
para cada a ∈ U existe δ > 0 tal que B(a, δ) ⊂ U . O conjunto dos pontos interiores de
U ser´a representado pela nota¸c˜ao int(U ). Similarmente um conjunto U ⊂ R
n
´e fechado
5
6
quando cont´em todos os seus pontos de aderˆencia, ou seja, para todo ponto a ∈ R
n
onde
qualquer vizinhan¸ca de a cont´em algum elemento de U, ent˜ao a ∈ U. O conjunto dos
pontos de aderˆencia de U ser´a representado pela nota¸c˜ao
¯
U.
Seja U ⊂ R
n
. Um ponto a ∈ R
n
diz-se ponto de acumula¸c˜ao do conjunto U quando
toda bola de centro a cont´em algum ponto do conjunto U diferente do ponto a, ou seja,
para todo > 0, deve existir x ∈ U tal que 0 < x − a < . O conjunto dos pontos de
acumula¸c˜ao ser´a representado pela nota¸c˜ao U
.
Uma seq¨uˆencia {x
k
} ⊂ R
n
´e uma aplica¸c˜ao x: N → R
n
, que associa a cada n´umero
k ∈ N um vetor x
k
∈ R
n
. Diz-se que a seq¨uˆencia {x
k
} ´e limitada quando o conjunto
dos seus termos ´e limitado em R
n
, ou seja, quando existe um n´umero real c > 0 tal que
x
k
≤ c para todo k ∈ N.
Uma seq¨uˆencia {x
k
} de n´umeros reais diz-se mon´otona n˜ao-decrescente quando se tem
x
k
≤ x
k+1
para todo k ∈ N e diz-se mon´otona n˜ao-crescente quando se tem x
k+1
≤ x
k
para todo k ∈ N.
Defini¸c˜ao 2.1. Diz-se que uma seq¨uˆencia {x
k
} converge para x
∗
∈ R
n
se dado > 0
existe n
0
tal que
||x
k
− x
∗
|| < , ∀ k n
0
.
Uma seq¨uˆencia {x
n
} ´e chamada seq¨uˆencia de Cauchy se dado > 0 existe n
0
tal que
||x
m
− x
k
|| < , ∀ m, k n
0
.
Tem-se lim x
k
= x
∗
⇔ lim x
k
− x
∗
= 0. Isto reduz a convergˆencia em R
n
`a con-
vergˆencia de n´umeros reais ≥ 0. Um resultado bem conhecido e cuja demonstra¸c˜ao pode
ser encontrada na p´agina 18 em [14], e que toda seq¨uˆencia {x
k
} em R
n
´e de Cauchy se, e
somente se, ´e convergente.
Proposi¸c˜ao 2.2. Seja { x
k
} uma seq ¨uˆencia em R
n
. Se existe um n´umero real α < 1 tal
que
x
k+1
− x
∗
≤ αx
k
− x
∗
, ∀ k, (2.1)
ent˜ao {x
k
} converge para x
∗
.
7
Demonstra¸c˜ao.
´
E f´acil ver de (2.1), que
0 ≤ x
k
− x
∗
≤ α
k
x
0
− x
∗
.
Fazendo k → ∞ na desigualdade acima, temos lim
k→∞
x
k
− x
∗
= 0. Assim, tˆem-se
{x
k
} converge para x
∗
.
Defini¸c˜ao 2.3. Seja a seq¨uˆencia {x
k
} ⊂ R
n
convergente para x
∗
, ent˜ao
i) Diz-se que {x
k
} converge linearmente se existe c ∈ [0, 1), tal que
x
k+1
− x
∗
≤ cx
k
− x
∗
, ∀ k.
ii) Diz-se que {x
k
} converge quadraticamente se existe c > 0, tal que
x
k+1
− x
∗
≤ cx
k
− x
∗
2
, ∀ k.
2.1.1 No¸c˜oes de An´alise no Espa¸co Euclidiano
Nossa meta nesta se¸c˜ao ´e obter algumas defini¸c˜oes e proposi¸c˜oes da an´alise dos espa¸cos
euclidianos que auxiliar˜ao na demonstra¸c˜ao de resultados futuros nessa disserta¸c˜ao. Por
tratarem de resultados b´asicos as demonstra¸c˜oes ser˜ao omitidas e poder˜ao ser encontradas
nas referˆencias [13] e [14]. Iniciaremos definindo fun¸c˜oes cont´ınuas.
Defini¸c˜ao 2.4. Seja Φ: U → R
n
uma aplica¸c˜ao definida no conjunto U ⊂ R
m
. Diz-se
que Φ ´e cont´ınua no ponto a ∈ U quando, para qualquer > 0 dado, se pode obter δ > 0
tal que x − a < δ implica |Φ(x) − Φ(a)| < . Se Φ: U → R
n
´e cont´ınua em todos os
pontos do conjunto U, diz-se simplesmente que Φ ´e uma fun¸c˜ao cont´ınua.
Defini¸c˜ao 2.5. Seja Φ: U → R
n
uma aplica¸c˜ao definida no conjunto aberto U ⊂ R
m
.
Diz-se que Φ ´e diferenci´avel no ponto x ∈ U quando existe uma transforma¸c˜ao linear
Φ
: R
m
→ R
n
tal que
Φ(x + h) = Φ(x) + Φ
(x)h + s(h), onde lim
h→0
s(h)
h
= 0.
Se Φ: U → R
n
´e diferenci´avel em todos os pontos do conjunto U, diz-se simplesmente que
Φ ´e uma fun¸c˜ao diferenci´avel.
8
A aplica¸c˜ao Φ
(x) diz-se a derivada de Φ no ponto x. Por outro lado, a igualdade
Φ(x + h) = Φ(x) + Φ
(x)h + s(h) ´e simplesmente a defini¸c˜ao do “resto”s(h) ∈ R
n
. A
diferenciabilidade de Φ no p onto x nos diz que o resto ´e um “infinit´esimo de ordem
superior a s”, isto ´e, lim
h→0
s(h)/h = 0.
Consideremos o conjunto L(R
m
, R
n
) dos operadores lineares de R
m
em R
n
.
Defini¸c˜ao 2.6. Seja Φ: U → R
n
uma aplica¸c˜ao definida no conjunto aberto U ⊂ R
m
.
Diz-se que Φ ´e continuamente diferenci´avel em U, ou que Φ ´e de classe C
1
, e escreveremos
Φ ∈ C
1
, quando Φ for diferenci´avel e, al´em disso, Φ
: U → L(R
m
, R
n
) for cont´ınua.
Proposi¸c˜ao 2.7. (Teorema Fundamental do C´alculo) Seja U ⊂ R
m
um conjunto aberto.
Dada Φ : U → R
n
de classe C
1
, suponha que o segmento de reta [x, x + h] esteja em U.
Ent˜ao
Φ(x + h) − Φ(x) =
1
0
Φ
(x + th) · h dt
Proposi¸c˜ao 2.8. (Teorema da Permanˆencia do Sinal) Sejam U ⊂ R, Φ : U → R e
a ∈ U
. Se lim
x→a
Φ(x) = L e α < L < β com α, β ∈ R, ent˜ao existe δ > 0 tal que para
todo x ∈ U e 0 < |x − a| < δ, temos α < Φ(x) < β.
Proposi¸c˜ao 2.9. (Teorema do Valor M´edio) Seja φ : [a, b] → R uma aplica¸c˜ao cont´ınua
e diferenci´avel no intervalo aberto (a, b). Ent˜ao existe c ∈ ( a, b) para o qual
φ
(c) =
φ(b) − φ(a)
b − a
.
2.1.2 No¸c˜oes de Norma de Operador no Espa¸co Euclidiano
Nesta se¸c˜ao estudaremos algumas propriedades da norma de operadores definido no espa¸co
euclidiano R
n
. Demonstraremos o conhecido Lema de Banach. Encerraremos definindo
os importantes conceitos de operador n˜ao-singular e condicionamento de operador. Ini-
ciaremos definindo norma de um operador em R
n
.
Consideremos o conjunto L(R
n
, R
n
) dos operadores lineares de R
n
em R
n
. Defina a
norma de operadores . como
T := sup
x=0
T x
x
. (2.2)
9
´
E f´acil ver, que a aplica¸c˜ao T → T cumpre todas as condi¸c˜oes exigidas para uma
norma, isto ´e, dados T, S ∈ L(R
n
, R
n
), temos:
N1. T = 0 ⇒ T > 0;
N2. α T ≤ |α|T para todo α ∈ R;
N3. T + S ≤ T + S.
A condi¸c˜ao N3 ´e conhecida como desigualdade triangular. Al´em disso, a aplica¸c˜ao
norma goza das seguintes propriedades.
Lema 2.10. Dados T, S ∈ L(R
n
, R
n
) e x ∈ R
n
, ent˜ao s˜ao v´alidas as seguintes pro-
priedades:
i) Tx ≤ T x;
ii) TS ≤ T S;
iii) T
k
≤ T
k
para todo k = 0, 1, 2, . . ..
Demonstra¸c˜ao. i) Se x ´e o vetor nulo segue imediato de (2.2). Se x n˜ao ´e o vetor nulo,
considere o vetor y = x/x e usando (2.2) temos
T ≥ T y =
1
x
T x.
Portanto T x ≤ T x.
ii)
´
E f´acil ver de (2.2), item i e propriedades do supremo que
T S = sup
x=0
T Sx
x
≤ sup
x=0
T Sx
x
= T S.
iii)
´
E conseq¨uˆencia imediato do item ii.
Lema 2.11. (Lema de Banach) Sejam B ∈ L(R
n
, R
n
) um operador linear e I o operador
identidade de R
n
. Se B − I < 1, ent˜ao B ´e n˜ao-singular e vale
B
−1
≤
1
1 − B − I
. (2.3)
Demonstra¸c˜ao. Primeiro, vamos mostrar que se T ∈ L(R
n
, R
n
) ´e tal que T < 1, ent˜ao
I − T ´e invers´ıvel e vale
(I − T )
−1
≤
1
1 − T
.
10
Para isso, considere as seguintes seq¨uˆencias {S
k
} e {t
k
} definidas respectivamente por:
S
k
= I + T + T
2
+ · · · + T
k
, t
k
= 1 + T + T
2
+ · · · + T
k
.
Primeiro, note que
S
k+1
− S
k
= (I + T + · · · + T
k+1
) − (I + T + · · · + T
k
) ≤ T
k+1
= t
k+1
− t
k
.
Agora, como T < 1, temos que {t
k
} ´e uma seq¨uˆencia mon´otona crescente e convergente,
com limite t
∗
= 1/(1 − T ). Portanto, deste fato e da equa¸c˜ao acima, {S
k
} ´e uma
seq¨uˆencia de Cauchy em L(R
n
, R
n
) e assim existe lim
n→∞
S
n
. Agora, observe que
S
k
(I − T ) = (I + T + · · · + T
k
)(I − T ) = I − T
k+1
. (2.4)
Por outro lado, temos que lim
k→∞
I − T
k
= I, pois
I − (I − T
k
) = T
k
≤ T
k
, lim
k→∞
T
k
= 0.
Assim, pela ´ultima equa¸c˜ao e (2.4), concluimos que lim
k→∞
S
k
= (I − T )
−1
. Note ainda que
(I − T )
−1
= lim
k→∞
S
k
lim
k→∞
I + T + · · · + T
k
≤ lim
k→∞
t
k
= 1/(1 − T ).
Agora, tomando T = I − B e observando a hip´otese B − I < 1, temos que (I − T ) = B
´e invers´ıvel e vale a estimativa dada em (2.3) para a norma da inversa B
−1
.
Um operador T ∈ L(R
n
, R
n
) ´e n˜ao-singular se seu determinante ´e n˜ao-nulo. Um
resultado bem conhecido, cuja demonstra¸c˜ao pode ser encontrada na p´agina 76 em [15],
´e que todo operador n˜ao-singular tem inverso.
Um problema ´e dito mal condicionado quando um pequeno arredondamento num dado
de entrada muda muito os dados de sa´ıda.
Defini¸c˜ao 2.12. O n´umero de condicionamento do operador T ∈ L(R
n
, R
n
), denotado
cond(T ), ´e o n´umero real
cond(T ) = T
−1
T .
Note que, cond(T ) = T
−1
T ≥ I = 1. Quanto maior o n´umero de condiciona-
mento pior ser´a o condicionamento do operador T .
11
2.2 No¸c˜oes de An´alise Convexa
Destinamos esta se¸c˜ao a um estudo dos conceitos relacionados aos conjuntos convexos e
as fun¸c˜oes convexas. Caracterizaremos as fun¸c˜oes convexas diferenci´aveis de uma vari´avel
real. Para tornar este trabalho “auto-contido”, demonstraremos a grande maioria dos
resultados. Para mais informa¸c˜oes sobre an´alise convexa veja [16], [17] e [18] . Iniciaremos
definindo conjunto convexo.
Defini¸c˜ao 2.13. Um conjunto D ⊂ R
n
´e dito convexo, se
λx + (1 − λ)y ∈ D, ∀ x, y ∈ D, λ ∈ [0, 1].
Geometricamente, esta defini¸c˜ao nos diz que o segmento de reta
[x, y] := {λx + (1 − λ)y : 0 ≤ λ ≤ 1}
est´a inteiramente contido em D, sempre que os pontos extremos x e y est˜ao em D.
Exemplo 2.14. O espa¸co euclidiano R
n
, o espa¸co euclidiano n˜ao-negativo R
n
+
e a bola
aberta de centro a ∈ R
n
e raio δ B(a, δ) s˜ao exemplos de conjuntos convexo.
Defini¸c˜ao 2.15. Seja I ⊂ R um intervalo. Uma fun¸c˜ao ϕ : I → R ´e dita convexa quando,
para todo x, y ∈ I e todo λ ∈ [0, 1]
ϕ(λx + (1 − λ)y) ≤ λϕ(x) + (1 − λ)ϕ(y), (2.5)
e ´e estritamente convexa se (2.5) ´e estrita para todo x, y ∈ I com x = y e todo λ ∈ (0, 1).
Proposi¸c˜ao 2.16. Sejam I ⊂ R um intervalo e ϕ : I → R uma fun¸c˜ao convexa. Ent˜ao
dados a, b e c ∈ I, com a < b < c, temos
ϕ(b) − ϕ(a)
b − a
≤
ϕ(c) − ϕ(a)
c − a
≤
ϕ(c) − ϕ(b)
c − b
. (2.6)
Se ϕ ´e estritamente convexa, as desigualdades (2.6) s˜ao estritas.
Demonstra¸c˜ao. Visto que a < b < c, obtemos ap´os algumas manipula¸c˜oes alg´ebricas que
b =
c − b
c − a
a +
b − a
c − a
c, (2.7)
12
onde (c − b)/(c − a) < 1 e (b − a)/(c − a) < 1. Como ϕ ´e convexa, segue de (2.7) e alguns
c´alculos que
ϕ(b) − ϕ(a) ≤
c − b
c − a
− 1
ϕ(a) +
b − a
c − a
ϕ(c), (2.8)
que ´e equivalente a
ϕ(b) − ϕ(a)
b − a
≤
ϕ(c) − ϕ(a)
c − a
,
o que prova a primeira desigualdade em (2.6). A segunda desigualdade em (2.6) ´e feita de
modo an´alogo. Agora, se ϕ ´e estrita para todo a, b ∈ I, ent˜ao (2.8) vale para desigualdade
estrita e segue-se o resultado.
Corol´ario 2.17. Sejam > 0 e τ ∈ [0, 1]. Se a fun¸c˜ao ϕ : [0, ) → R ´e convexa, ent˜ao a
fun¸c˜ao l : (0, ) → R definida por
l(x) =
ϕ(x) − ϕ(τx)
x
,
´e n˜ao-decrescente. Se ϕ ´e estritamente convexa e τ = 1, ent˜ao l ´e crescente.
Demonstra¸c˜ao. Dados x, y ∈ (0, ) com 0 < x < y.
Para τ = 1 ´e trivial. Para τ = 0 a prova segue como conseq¨uˆencia da primeira
desigualdade na Proposi¸c˜ao 2.16 com a = 0, b = x e c = y.
Agora, supondo que τ ∈ (0, 1), ent˜ao τx < x < y e da primeira desigualdade na
Proposi¸c˜ao 2.16, temos
ϕ(x) − ϕ(τx)
x − τx
≤
ϕ(y) − ϕ(τx)
y − τx
. (2.9)
Novamente, como τ ∈ (0, 1), tamb´em vale que τx < τ y < y. Assim, da segunda desigual-
dade da Proposi¸c˜ao 2.16, segue que
ϕ(y) − ϕ(τx)
y − τx
≤
ϕ(y) − ϕ(τy)
y − τy
. (2.10)
Combinando (2.9) e (2.10), temos que l ´e n˜ao-decrescente. Agora, se ϕ ´e estritamente
convexa as desigualdades na Proposi¸c˜ao 2.16 valem para desigualdades estritas e analoga-
mente conclu´ımos que l ´e crescente.
A seguir apresentaremos a caracteriza¸c˜ao de fun¸c˜oes convexas de uma vari´avel real.
13
Proposi¸c˜ao 2.18. Sejam I ⊂ R um intervalo e ϕ : I → R uma fun¸c˜ao diferenci´avel.
Ent˜ao ϕ ´e convexa se, e somente se,
ϕ(y) ≥ ϕ(x) + ϕ
(x)(y − x), ∀ y ∈ I, x ∈ int(I). (2.11)
Se (2.11) ´e estrita para todo y ∈ I e x ∈ int(I), ent˜ao ϕ ´e estritamente convexa.
Demonstra¸c˜ao. Dados y ∈ I e x ∈ int(I), temos por hip´otese que
ϕ
λy + (1 − λ)x
≤ λϕ(y) + (1 − λ )ϕ(x).
Ap´os algumas manipula¸c˜oes alg´ebricas segue-se que
ϕ
x + λ(y − x)
− ϕ(x)
λ
≤ ϕ(y) − ϕ(x),
para todo λ ∈ [0, 1]. Fazendo λ → 0 na ´ultima desigualdade, temos
ϕ
(x)(y − x) + ϕ(x) ≤ ϕ(y),
que prova a primeira parte.
Reciprocamente, dados x, y ∈ I. Com λ = 0 e λ = 1, a convexidade ´e imediata.
Agora, supondo que λ ∈ (0, 1) tome z = λx + (1 − λ)y ∈ int(I), ent˜ao da equa¸c˜ao (2.11)
segue que
ϕ
λx + (1 − λ)y
(1 − λ)(x − y) + ϕ
λx + (1 − λ)y
≤ ϕ(x) (2.12)
e
ϕ
λx + (1 − λ)y
λ(y − x) + ϕ
λx + (1 − λ)y
≤ ϕ(y). (2.13)
Multiplicando (2.12) por λ e (2.13) por (1 − λ) e adicionando o resultado obtemos que
ϕ
λx + (1 − λ)y
≤ λϕ(x) + (1 − λ)ϕ(y).
Portanto ϕ ´e convexa. Agora, se (2.11) ´e estrita para todo x, y ∈ I, ent˜ao (2.12) e
(2.13) valem para desigualdade estrita e analogamente conclu´ımos que ϕ ´e estritamente
convexa.
Proposi¸c˜ao 2.19. Sejam I ⊂ R um intervalo e ϕ : I → R uma fun¸c˜ao diferenci´avel.
Ent˜ao ϕ ´e convexa se, e somente se,
ϕ
(x) − ϕ
(y)
(x − y) ≥ 0, ∀ x, y ∈ int(I). (2.14)
Se (2.14) ´e estrita para todo x, y ∈ int(I), ent˜ao ϕ ´e estritamente convexa.
14
Demonstra¸c˜ao. Tome x, y ∈ int(I), como ϕ ´e convexa em I temos pela Proposi¸c˜ao 2.18
que
ϕ
(x)(y − x) + ϕ(x) ≤ ϕ(y) e ϕ
(y)(x − y) + ϕ(y) ≤ ϕ(x), (2.15)
para todo x, y no interior de I. Ent˜ao, segue-se de (2.15) que
ϕ(x) + ϕ
(x)(y − x) ≤ ϕ(y) ≤ ϕ(x) + ϕ
(y)(y − x),
isto implica que
ϕ
(x)−ϕ
(y)
(x−y) ≥ 0, para todo x, y no int(I), o que prova a primeira
parte.
Reciprocamente, ´e claro que o resultado ´e v´alido para x = y. Agora, dados x, y ∈ I
com x = y e λ ∈ [0, 1], temos pelo Teorema do Valor M´edio que, para todo a ∈ (x, y),
existem c
e c
com c
∈ (x, a) e c
∈ (a, y) tais que
ϕ(a) − ϕ(x) = ϕ
(c
)(a − x) e ϕ(y) − ϕ(a) = ϕ
(c
)(y − a).
Multiplicando a primeira igualdade por −λ, a segunda por 1−λ, tomando a = λx+(1−λ)y
e adicionando o resultado obtemos a seguinte igualdade
λϕ(x)+ (1−λ)ϕ(y)−ϕ
λx+ (1−λ)y
= ϕ
(c
)(1− λ)λ(y−x)−ϕ
(c
)λ(1− λ)(y−x). (2.16)
Note que existe k > 0 tal que c
− c
= k(y − x), ou seja, y − x = (c
− c
)/k. Assim a
igualdade anterior se reduz a
λϕ(x) + (1 − λ)ϕ(y) − ϕ
λx + (1 − λ)y
=
(1 − λ)λ
k
ϕ
(c
) − ϕ
(c
)
(c
− c
). (2.17)
Como k > 0 e λ ∈ [0, 1] segue da igualdade anterior e desigualdade (2.14) que
ϕ
λx + (1 − λ)y
≤ λϕ(x) + (1 − λ)ϕ(y),
e portanto ϕ ´e convexa. Agora, se (2.14) ´e estrita para todo x, y ∈ int(I) e como k > 0 e
λ ∈ (0, 1) na equa¸c˜ao (2.16), ent˜ao (2.17) vale para desigualdade estrita e ϕ ´e estritamente
convexa.
No pr´oximo cap´ıtulo, estaremos interessados em analisar algumas fun¸c˜oes em particu-
lar e obter equa¸c˜oes que ser˜ao utilizadas na prova da convergˆencia do m´etodo de Newton
inexato e suas varia¸c˜oes.
Cap´ıtulo 3
A Fun¸c˜ao Majorante
Para provarmos a convergˆencia local do m´etodo de Newton inexato e suas varia¸c˜oes usa-
remos o princ´ıpio majorante de Kantorovich, veja [12]. Neste cap´ıtulo, mostraremos as
principais rela¸c˜oes entre a fun¸c˜ao majorante e o operador n˜ao-linear. Iniciaremos com uma
an´alise de uma determinada fun¸c˜ao escalar e o m´odulo da itera¸c˜ao de Newton associada
a ela, a qual dar´a resultados importantes para o estudo das fun¸c˜oes majorantes definidas
nas se¸c˜oes 3.2 e 3.3. Os resultados obtidos aqui s˜ao os principais instrumentos utilizados
no estudo da convergˆencia linear.
3.1 An´alise de uma Fun¸c˜ao Escalar (f)
Nesta se¸c˜ao nosso objetivo ´e analisar o comportamento de uma determinada fun¸c˜ao escalar
e o m´odulo da itera¸c˜ao de Newton associada a ela.
Inicialmente, seja R > 0 e uma fun¸c˜ao escalar continuamente diferenci´avel f : [0, R) →
R satisfazendo as seguintes condi¸c˜oes:
h1) f(0) = 0 e f
(0) = −1;
h2) f
´e convexa e crescente.
Observa¸c˜ao 3.1. Para uniformizar as nota¸c˜oes sempre que usarmos f para uma fun¸c˜ao
nesta disserta¸c˜ao, estaremos referindo a fun¸c˜ao escalar definida acima.
A seguir faremos uma an´alise da fun¸c˜ao f.
15
16
Proposi¸c˜ao 3.2. Seja ν := sup{t ∈ [0, R) : f
(t) < 0}. Ent˜ao valem as seguintes
afirma¸c˜oes:
i) ν ´e positivo;
ii) f
(t) < 0, ∀ t ∈ [0, ν);
iii) A fun¸c˜ao [0, ν) t → 1/|f
(t)| ´e crescente;
iv) t − f(t)/f
(t) < 0, ∀ t ∈ (0, ν).
Demonstra¸c˜ao. Como f
(0) = −1 e f
´e cont´ınua em [0, R), existe δ > 0 tal que f
(t) < 0
para todo t ∈ [0, δ). Assim, ν > 0. Isto prova o item i.
Para provar do item ii, note que de h2 temos que f
´e crescente em [0, R), isto junto
com o item i implica que f
< 0 em [0, ν).
Para provar o item iii, note novamente que de h2 temos que f
´e crescente em [0, R),
isto junto com o item ii implica que a fun¸c˜ao [0, ν) t → 1/|f
(t)| ´e crescente.
Prova do item iv. De h2 temos que f
´e crescente em [0, R), ent˜ao pela Proposi¸c˜ao 2.19
temos que f ´e estritamente convexa em [0, R). Assim, usando a Proposi¸c˜ao 2.18 com
ϕ = f, y = 0 e x = t obtemos que
f(0) > f(t) − tf
(t), ∀ t ∈ (0, R).
Lembrando que f(0) = 0 e f
< 0 em (0, ν), a desigualdade do item iv segue facilmente
da desigualdade acima.
Proposi¸c˜ao 3.3. A fun¸c˜ao ψ : (0, ν) → R definida por
ψ(t) =
f(t) + 2t
t
,
´e n˜ao-decrescente.
Demonstra¸c˜ao. Sejam 0 < t
1
< t
2
< ν. Fazendo algumas manipula¸c˜oes alg´ebricas, segue-
se de h1 e do Teorema Fundamental do C´alculo que
ψ(t
2
) − ψ(t
1
) =
f(t
2
)
t
2
−
f(t
1
)
t
1
=
1
0
(f
(τt
2
) − f
(τt
1
)) dτ.
17
Agora, de h2 temos que f
´e crescente. Portanto, a equa¸c˜ao anterior implica que ψ(t
2
) −
ψ(t
1
) ≥ 0. Isto prova o resultado.
Seja n
f
a fun¸c˜ao itera¸c˜ao de Newton associada a fun¸c˜ao escalar f, definida por
n
f
: [0, ν) → (−∞, 0]
t → t − f(t)/f
(t).
(3.1)
Da Proposi¸c˜ao 3.2, temos que f
< 0 em [0, ν). Assim, a fun¸c˜ao itera¸c˜ao de Newton
associada a fun¸c˜ao escalar f est´a bem definida em [0, ν).
Proposi¸c˜ao 3.4. A fun¸c˜ao (0, ν) t → |n
f
(t)|/t
2
´e n˜ao-decrescente.
Demonstra¸c˜ao. Usando o item iv da Proposi¸c˜ao 3.2, o Teorema Fundamental do C´alculo
e h1 obtemos ap´os algumas manipula¸c˜oes alg´ebricas que
|n
f
(t)| =
1
|f
(t)|
tf
(t) −
1
0
f
(τt)tdτ
, ∀ t ∈ [0, ν).
Segue imediatamente que
|n
f
(t)|
t
2
=
1
|f
(t)|
1
0
f
(t) − f
(τt)
t
dτ, ∀ t ∈ (0, ν). (3.2)
Agora, segue de h2 que f
´e crescente e como τ ∈ [0, 1] temos que a aplica¸c˜ao
(0, ν) t →
f
(t) − f
(τt)
t
, (3.3)
´e n˜ao-negativa, tamb´em de h2 temos que f
´e convexa e assim pelo Corol´ario 2.17 com
f
= ϕ, = ν e x = t segue que a aplica¸c˜ao (3.3) ´e n˜ao-decrescente. Por outro lado, a
Proposi¸c˜ao 3.2 implica que a fun¸c˜ao
(0, ν) t → 1/|f
(t)|, (3.4)
´e positiva e crescente. Portanto, como as fun¸c˜oes definidas em (3.3) e (3.4) s˜ao n˜ao-
decrescentes e n˜ao-negativas, segue de (3.2) que a fun¸c˜ao (0, ν) t → |n
f
(t)|/t
2
´e n˜ao-
decrescente.
Corol´ario 3.5. A fun¸c˜ao (0, ν) t → |n
f
(t)|/t ´e n˜ao-decrescente.
18
Demonstra¸c˜ao.
´
E imediato, basta notar que |n
f
(t)|/t = (|n
f
(t)|/t
2
)t, que ´e o produto de
fun¸c˜oes n˜ao-decrescentes e n˜ao-negativas.
Proposi¸c˜ao 3.6. Dado 0 ≤ ¯v < 1. Defina a constante
¯ρ := sup {t ∈ (0, ν) : (1 + ¯v)[f(t)/(tf
(t)) − 1] + ¯v < 1} .
Ent˜ao, ¯ρ ´e positiva e vale a seguinte desigualdade
(1 + ¯v)|n
f
(t)|/t + ¯v < 1, ∀ t ∈ (0, ¯ρ).
Demonstra¸c˜ao. Usando a defini¸c˜ao em (3.1) e Proposi¸c˜ao 3.2, temos que
0 < f(t)/(tf
(t)) − 1 =
f(t)/(f
(t)) − t
/t = |n
f
(t)|/t, ∀ t ∈ (0, ν). (3.5)
Assim sendo,
lim
t→0
|n
f
(t)|/t = lim
t→0
(|n
f
(t)|/t
2
) t = 0 , (3.6)
pois a Proposi¸c˜ao 3.4 implica que |n
f
(t)|/t
2
´e limitada pr´oximo de zero. Portanto, como
(1 − ¯v)/(1 + ¯v) > 0, usando o Teorema da Permanˆencia do Sinal, temos de (3.5) e (3.6)
que existe
¯
δ > 0 tal que
0 < (f(t)/(tf
(t)) − 1) < (1 − ¯v)/(1 + ¯v), ∀ t ∈ (0,
¯
δ),
que pode ser escrita equivalentemente da seguinte maneira
0 < (1 + ¯v)[f (t)/(tf
(t)) − 1] + ¯v < 1, ∀ t ∈ (0,
¯
δ). (3.7)
Da´ı segue que ¯ρ ´e positivo.
Finalmente, pelo Corol´ario 3.5 temos que a fun¸c˜ao (0, ν) t → |n
f
(t)|/t ´e n˜ao-
decrescente. Em vista disso, para concluir a prova basta combinar (3.5) e (3.7) com a
defini¸c˜ao de ¯ρ.
Proposi¸c˜ao 3.7. Dadas as constantes n˜ao-negativas ˜v, ω
1
e ω
2
satisfazendo ˜v < 1 e
ω
1
˜v + ω
2
< 1. Defina
˜ρ := sup{t ∈ (0, ν) : ω
1
(1 + ˜v)[f (t)/(tf
(t)) − 1] + ω
1
˜v + ω
2
< 1}.
Ent˜ao a constante ˜ρ ´e positiva e vale a seguinte desigualdade
ω
1
(1 + ˜v)|n
f
(t)|/t + ω
1
˜v + ω
2
< 1, ∀ t ∈ (0, ˜ρ).
19
Demonstra¸c˜ao. Usando a defini¸c˜ao (3.1) e Proposi¸c˜ao 3.2, temos que
0 < f(t)/(tf
(t)) − 1 =
f(t)/(f
(t)) − t
/t = |n
f
(t)|/t, ∀ t ∈ (0, ν). (3.8)
Assim sendo,
lim
t→0
|n
f
(t)|/t = lim
t→0
(|n
f
(t)|/t
2
) t = 0 , (3.9)
pois pela Proposi¸c˜ao 3.4 implica que |n
f
(t)|/t
2
´e limitada pr´oximo de zero. Portanto,
como 1 − (ω
1
˜v + ω
2
)/ω
1
(1 + ˜v) > 0, usando o Teorema da Permanˆencia do Sinal, temos
de (3.8) e (3.9) que existe
˜
δ > 0 tal que
0 < (f(t)/(tf
(t)) − 1) < 1 − (ω
1
˜v + ω
2
)/ω
1
(1 + ˜v), ∀ t ∈ (0,
˜
δ),
que pode ser escrita equivalentemente da seguinte maneira
0 < ω
1
(1 + ˜v)[f (t)/(tf
(t)) − 1] + ω
1
˜v + ω
2
< 1, ∀ t ∈ (0,
˜
δ). (3.10)
Da´ı segue que ¯ρ ´e positivo.
Finalmente, pelo Corol´ario 3.5 temos que a fun¸c˜ao (0, ν) t → |n
f
(t)|/t ´e n˜ao-
decrescente. Em visto disso, para concluir a prova basta combinar (3.8) e (3.10) com a
defini¸c˜ao de ˜ρ.
Proposi¸c˜ao 3.8. Dado 0 ≤ ˆv < 1. Defina a constante
ˆρ := sup{t ∈ (0, ν) : −(1 + ˆv)(f(t) + 2t)/tf
(t) − 1 < 1}.
Ent˜ao, a constante ˆρ ´e positiva e vale a seguinte desigualdade
(1 + ˆv)(f (t) + 2t)/t|f
(t)| − 1 < 1, ∀ t ∈ (0, ˆρ).
Demonstra¸c˜ao. Primeiro, note que
lim
t→0
−(1 + ˆv)
f(t)
tf
(t)
+
2
f
(t)
− 1 = lim
t→0
−(1 + ˆv)
f(t)
t
1
f
(t)
+
2
f
(t)
− 1 = ˆv,
pois de h1 temos f
(0) = −1 e f(0) = 0. Agora, como ˆv < 1 usando o Teorema da
Permanˆencia do Sinal, temos que existe
ˆ
δ > 0 tal que
0 < −(1 + ˆv)[f (t)/(tf
(t)) + 2/f
(t)] − 1 < 1, ∀ t ∈ (0,
ˆ
δ),
20
que pode ser escrita equivalentemente da seguinte maneira
0 < −(1 + ˆv)(f (t) + 2)/tf
(t) − 1 < 1, ∀ t ∈ (0,
ˆ
δ). (3.11)
Da´ı segue que ˆρ ´e positivo.
Finalmente, pelas Proposi¸c˜ao 3.2 e Proposi¸c˜ao 3.3 temos respectivamente que as
fun¸c˜oes (0, ν) t → 1/|f(t)| e (0, ν) t → f (t) + 2t/t s˜ao n˜ao-decrescente. Em
vista disso, para concluir a prova basta combinar (3.11) com a defini¸c˜ao de ˆρ.
3.2 A Fun¸c˜ao Majorante Radial (f
r
)
Nesta se¸c˜ao definiremos o conceito de fun¸c˜ao majorante radial. Apresentaremos a rela¸c˜ao
entre a fun¸c˜ao majorante radial e o operador n˜ao linear, obtendo as equa¸c˜oes que auxilia-
r˜ao nos Cap´ıtulos 4 e Cap´ıtulos 5.
Defini¸c˜ao 3.9. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω, R > 0 e seja κ := sup{t ∈ [0, R) : B(x
∗
, t) ⊂ Ω}.
Suponha que F
(x
∗
) seja n˜ao-singular e F (x
∗
) = 0. Dizemos que a fun¸c˜ao continuamente
diferenci´avel f
r
: [0, R) → R, ´e uma fun¸c˜ao majorante radial para o operador F se
satisfaz as hip´oteses h1, h2 e a condi¸c˜ao
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ f
r
(x − x
∗
) − f
r
(τx − x
∗
) , (3.12)
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R.
Observa¸c˜ao 3.10. Para uniformizar as nota¸c˜oes sempre que usarmos f
r
para uma fun¸c˜ao
nesta disserta¸c˜ao, estaremos referindo a fun¸c˜ao majorante radial definida acima, isto ´e,
satisfazendo as hip´oteses h1, h2 e a condi¸c˜ao (3.12). Portanto, a Se¸c˜ao 3.1 ser´a usada
aqui, inclusive as nota¸c˜oes.
A seguir, apresentaremos as rela¸c˜oes entre o operador n˜ao-linear F e a fun¸c˜ao majo-
rante radial f
r
.
Lema 3.11. Seja x ∈ Ω. Se x − x
∗
< min{ν, κ}, ent˜ao F
(x) ´e n˜ao-singular e
F
(x)
−1
F
(x
∗
) 1/|f
r
(x − x
∗
)|.
Em particular, se x − x
∗
< σ ≤ min{ν, κ}, ent˜ao F
´e n˜ao-singular em B(x
∗
, σ).
21
Demonstra¸c˜ao. Seja x ∈ Ω tal que x − x
∗
< min{ν, κ}. Portanto f
r
(x − x
∗
) < 0, o
que junto com (3.12) e h1, implica
F
(x
∗
)
−1
F
(x) − I = F
(x
∗
)
−1
[F
(x) − F
(x
∗
)] ≤ f
r
(x − x
∗
) − f
r
(0) < −f
(0) = 1.
Considerando a inequa¸c˜ao anterior e o Lema de Banach, temos que F
(x
∗
)
−1
F
(x) ´e n˜ao-
singular. Como F
(x
∗
)
−1
´e n˜ao-singular, po demos concluir que F
(x) ´e n˜ao-singular. Al´em
disso, ainda pelo Lema de Banach
F
(x)
−1
F
(x
∗
) ≤
1
1 − F
(x
∗
)
−1
F
(x) − I
.
Por outro lado, usamos (3.12), h1 e que f
r
< 0 em [0, ν), temos
1
1 − F
(x
∗
)
−1
F
(x) − I
≤
1
1 − (f
r
(x − x
∗
) − f
r
(0))
=
1
|f
r
(x − x
∗
)|
.
Portanto, o resultado segue combinando as duas equa¸c˜oes acima. A ´ultima parte do lema
´e imediata.
A itera¸c˜ao de Newton produz um ponto que ´e o zero da lineariza¸c˜ao de F , tal ponto,
tamb´em ´e a primeira-ordem da expans˜ao de Taylor para F . Assim, estudaremos o erro
linear para cada ponto em Ω
E
F
(x, y) := F (y) − [F (x) + F
(x)(y − x)] , x, y ∈ Ω. (3.13)
Iremos limitar este erro pelo erro da lineariza¸c˜ao da fun¸c˜ao majorante radial f
r
e
f
r
(t, u) := f
r
(u) − [f
r
(t) + f
r
(t)(u − t)] , t, u ∈ [0, R). (3.14)
Lema 3.12. Se x
∗
− x < κ, ent˜ao vale F
(x
∗
)
−1
E
F
(x, x
∗
) ≤ e
f
r
(x − x
∗
, 0).
Demonstra¸c˜ao. Como B(x
∗
, κ) ´e um conjunto convexo, segue x
∗
+ τ(x − x
∗
) ∈ B(x
∗
, κ),
para 0 ≤ τ ≤ 1. Ent˜ao, da defini¸c˜ao (3.13) e usando o Teorema Fundamental do C´alculo
e propriedades da norma, temos
F
(x
∗
)
−1
E
F
(x, x
∗
) = F
(x
∗
)
−1
F (x
∗
) − [F (x) + F
(x)(x
∗
− x)]
= F
(x
∗
)
−1
[F
(x)(x − x
∗
) −
1
0
F
(x
∗
+ τ(x − x
∗
))dτ(x − x
∗
)]
≤
1
0
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
x − x
∗
dτ.
22
Agora, considerando a inequa¸c˜ao anterior, (3.12) e o Teorema Fundamental do C´alculo,
obtemos que
F
(x
∗
)
−1
E
F
(x, x
∗
) ≤
1
0
[f
r
(x − x
∗
) − f
r
(τx − x
∗
)] x − x
∗
dτ
= f
r
(x − x
∗
)x − x
∗
−
1
0
f
r
(τx − x
∗
)x − x
∗
dτ
= f
r
(0) − f
r
(x − x
∗
) + f
r
(x − x
∗
)x − x
∗
.
Portanto, combinando a ´ultima desigualdade com a defini¸c˜ao (3.14) segue a desigualdade
desejada.
Denominamos como o passo de Newton para a fun¸c˜ao F e f
r
as igualdades
S
F
(x) := F
(x)
−1
F (x), s
f
r
(t) := f
r
(t)
−1
f
r
(t), (3.15)
respectivamente.
Lema 3.13. Se x − x
∗
< min{ν, κ}, ent˜ao vale S
F
(x) ≤ s
f
r
(x − x
∗
).
Demonstra¸c˜ao. Usando que F (x
∗
) = 0 juntamente com algumas manipula¸c˜oes alg´ebricas,
segue das propriedades da norma e de (3.13) que
F
(x)
−1
F (x) = − F
(x)
−1
(F (x
∗
) − [F (x) + F
(x)(x
∗
− x)]) + (x
∗
− x)
≤ F
(x)
−1
F
(x
∗
)F
(x
∗
)
−1
(F (x
∗
) − [F (x) + F
(x)(x
∗
− x)]) + x
∗
− x
= F
(x)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x, x
∗
) + x − x
∗
.
Considerando a ´ultima inequa¸c˜ao, Lema 3.11 e Lema 3.12, temos
F
(x)
−1
F (x) ≤
e
f
r
(x − x
∗
, 0)
|f
r
(x − x
∗
)|
+ x − x
∗
.
Como x − x
∗
< min{ν, κ} e f
r
< 0 em [0, ν), segue da ´ultima desigualdade, defini¸c˜ao
em (3.14) e h1, que
F
(x)
−1
F (x) ≤
f
r
(0) − f
r
(x − x
∗
) + f
r
(x − x
∗
)x − x
∗
−f
r
(x − x
∗
)
+ x − x
∗
=
f
r
(x − x
∗
)
f
r
(x − x
∗
)
.
Portanto, esta desigualdade junto com (3.15) implica a desigualdade desejada.
23
3.3 A Fun¸c˜ao Majorante Central (f
c
)
Nesta se¸c˜ao definiremos o conceito de fun¸c˜ao majorante central. Apresentaremos a rela¸c˜ao
entre a fun¸c˜ao majorante central e o operador n˜ao linear, obtendo as equa¸c˜oes que auxilia-
r˜ao no Cap´ıtulo 6.
Defini¸c˜ao 3.14. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω, R > 0 e seja κ := sup{t ∈ [0, R) : B(x
∗
, t) ⊂ Ω}.
Suponha que F
(x
∗
) seja n˜ao-singular e F (x
∗
) = 0. Dizemos que a fun¸c˜ao continuamente
diferenci´avel f
c
: [0, R) → R, ´e uma fun¸c˜ao majorante central para o operador F se
satisfaz as hip´oteses h1, h2 e a condi¸c˜ao
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
)]
≤ f
c
(τx − x
∗
) − f
c
(0) , (3.16)
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R.
Observa¸c˜ao 3.15. Para uniformizar as nota¸c˜oes sempre que usarmos f
c
para uma fun¸c˜ao
nesta disserta¸c˜ao, estaremos referindo a fun¸c˜ao majorante central definida acima, isto ´e,
satisfazendo as hip´oteses h1, h2 e a condi¸c˜ao (3.16). Portanto, a Se¸c˜ao 3.1 ser´a usada
aqui, inclusive as nota¸c˜oes.
A seguir, apresentaremos as rela¸c˜oes entre o operador n˜ao-linear F e a fun¸c˜ao majo-
rante central f
c
.
Lema 3.16. Seja x ∈ Ω. Se x − x
∗
< min{ν, κ}, ent˜ao F
(x) ´e n˜ao-singular e
F
(x)
−1
F
(x
∗
) 1/|f
c
(x − x
∗
)|.
Em particular, se x − x
∗
< σ ≤ min{ν, κ}, ent˜ao F
´e n˜ao-singular em B(x
∗
, σ).
Demonstra¸c˜ao. Seja x ∈ Ω tal que x − x
∗
< min{ν, κ}. Portanto f
c
(x − x
∗
) < 0, o
que junto com (3.16) e h1, implica
F
(x
∗
)
−1
F
(x) − I = F
(x
∗
)
−1
[F
(x) − F
(x
∗
)] ≤ f
c
(x − x
∗
) − f
c
(0) < −f
c
(0) = 1.
Considerando a inequa¸c˜ao anterior e o Lema Banach temos que F
(x
∗
)
−1
F
(x) ´e n˜ao-
singular. Assim, como F
(x
∗
)
−1
´e n˜ao-singular, concluimos que F
(x) tamb´em ´e n˜ao-
singular. Al´em disso, ainda pelo Lema de Banach
F
(x)
−1
F
(x
∗
) ≤
1
1 − F
(x
∗
)
−1
F
(x) − I
.
24
Por outro lado, usamos (3.16), h1 e que f
c
< 0 em [0, ν), temos
1
1 − F
(x
∗
)
−1
F
(x) − I
≤
1
1 − (f
c
(x − x
∗
) − f
c
(0))
=
1
|f
c
(x − x
∗
)|
.
Portanto, o resultado segue combinando as duas equa¸c˜oes acima. A ´ultima parte do lema
´e imediata.
Lema 3.17. Se x, y ∈ B(x
∗
, κ), ent˜ao vale
1
0
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(y)]x − x
∗
dτ
≤ f
c
(x − x
∗
) + 2x − x
∗
+ f
c
(y − x
∗
)x − x
∗
.
Demonstra¸c˜ao. Usando propriedades da norma, a desigualdade (3.16) e h1, obtemos ap´os
simples manipula¸c˜ao alg´ebrica, que
1
0
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(y)]x − x
∗
dτ
≤
1
0
(F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
)]x − x
∗
dτ
+
1
0
F
(x
∗
)
−1
[F
(x
∗
) − F
(y)]x − x
∗
dτ ≤
1
0
[f
c
(τx − x
∗
)x − x
∗
+ x − x
∗
] dτ
+ f
c
(y − x
∗
)x − x
∗
+ x − x
∗
.
Agora, considerando a ´ultima desigualdade e o Teorema Fundamental do C´alculo,
segue de h1 que
1
0
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(y)]x − x
∗
dτ
≤ f
c
(x − x
∗
) + 2x − x
∗
+ f
c
(y − x
∗
)x − x
∗
,
o que prova a desigualdade.
Lema 3.18. Se x − x
∗
< min{ν, κ} e y − x
∗
< min{ν, κ}, ent˜ao vale
F
(y)
−1
F (x) ≤ (f
c
(x − x
∗
) + 2x − x
∗
)/|f
c
(y − x
∗
)|.
25
Demonstra¸c˜ao. Usando F (x
∗
) = 0, propriedades da norma e o Teorema Fundamental do
C´alculo, obtemos ap´os simples manipula¸c˜oes alg´ebricas que
F
(y)
−1
F (x) = F
(y)
−1
F
(x
∗
)F
(x
∗
)
−1
(F (x) − F (x
∗
))
= F
(y)
−1
F
(x
∗
)F
(x
∗
)
−1
1
0
F
(x
∗
+ τ(x − x
∗
))(x − x
∗
)dτ
≤ F
(y)
−1
F
(x
∗
)
1
0
F
(x
∗
)
−1
(F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
))x − x
∗
dτ
+ F
(y)
−1
F
(x
∗
)x − x
∗
.
Agora, combinando a ´ultima desigualdade com (3.16) segue do Lema 3.16 e de h1 que
F
(y)
−1
F (x) ≤
1
0
f
c
(τx − x
∗
)x − x
∗
− f
c
(0)x − x
∗
|f
c
(y − x
∗
)|
dτ +
x − x
∗
|f
c
(y − x
∗
)|
≤
1
0
f
c
(τx − x
∗
)x − x
∗
|f
c
(y − x
∗
)|
dτ +
2x − x
∗
|f
c
(y − x
∗
)|
´
E f´acil ver que da ´ultima desigualdade junto com o Teorema Fundamental do C´alculo,
segue de h1 que
F
(y)
−1
F (x) =
f
c
(x − x
∗
) + 2x − x
∗
|f
c
(y − x
∗
)|
,
o que prova o lema.
Agora com os resultados obtidos neste cap´ıtulo, estamos aptos a provar a convergˆencia
do m´etodo de Newton inexato e suas varia¸c˜oes.
Cap´ıtulo 4
M´etodo de Newton Inexato
Neste cap´ıtulo ´e feita uma discuss˜ao sobre os m´etodos inexatos para resolver sistemas de
equa¸c˜oes n˜ao-lineares. Comprovaremos que sob certas condi¸c˜oes a seq¨uˆencia gerada pelo
m´etodo de Newton Inexato est´a bem definida e converge linearmente para uma solu¸c˜ao do
sistema em considera¸c˜ao. Encerraremos aplicando os resultados obtidos em uma situa¸c˜ao
particular.
Inicialmente, sejam Ω ⊆ R
n
um conjunto aberto e uma fun¸c˜ao F : Ω → R
n
continua-
mente diferenci´avel em Ω. Considere o sistema de equa¸c˜oes n˜ao-lineares
F (x) = 0. (4.1)
Os m´etodos inexatos com controle residual relativo escalado usados para resolver (4.1) s˜ao
formalmente descritos como: dado x
0
∈ Ω defina
x
k+1
= x
k
+ s
k
, B
k
s
k
= −F (x
k
) + r
k
, P
k
r
k
≤ θ
k
P
k
F (x
k
), k = 0, 1, ..., (4.2)
onde as seq¨uˆencias {θ
k
} e {P
k
}, respectivamente de n´umeros reais e de matrizes n × n
invert´ıveis, s˜ao dadas. A seq¨uˆencias {θ
k
} ´e usualmente chamada de seq¨uˆencia“forcing” e
´e tomada uniformemente limitada por 1. Em particular, o processo acima ´e o m´etodo de
Newton inexato se B
k
= F
(x
k
), ´e o m´etodo de Newton inexato modificado se B
k
= F
(x
0
)
ou ´e o m´etodo quase-Newton inexato se B
k
´e uma aproxima¸c˜ao de F
(x
k
).
Primeiro, examinaremos o m´etodo de Newton inexato, depois examinaremos os m´etodos
inexatos quase-Newton e Newton modificado nos cap´ıtulos 5 e 6, respectivamente.
26
27
4.1 Convergˆencia do M´etodo de Newton Inexato
Nesta se¸c˜ao provaremos a convergˆencia para o m´etodo de Newton inexato. Admitindo que
o sistema n˜ao-linear (4.1) tem solu¸c˜ao, mostraremos que, tomando o ponto inicial x
0
numa
vizinhan¸ca apropriada da solu¸c˜ao, a seq¨uˆencia gerada pelo m´etodo de Newton inexato
est´a bem definida e converge linearmente para uma solu¸c˜ao de (4.1). Est´a afirma¸c˜ao ´e o
teorema:
Teorema 4.1. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente dife-
renci´avel em Ω. Tome x
∗
∈ Ω, R > 0 e seja κ := sup{t ∈ [0, R) : B(x
∗
, t) ⊂ Ω}. Suponha
que F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe uma fun¸c˜ao continuamente diferenci´avel
f
r
: [0, R) → R tal que
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ f
r
(x − x
∗
) − f
r
(τx − x
∗
) , (4.3)
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R, onde
h1) f
r
(0) = 0 e f
r
(0) = −1;
h2) f
r
´e convexa e crescente.
Dado 0 ≤ ¯v < 1. Sejam as seguintes constantes positivas ν := sup {t ∈ [0, R) : f
r
(t) < 0},
¯ρ := sup{t ∈ (0, ν) : (1 + ¯v)[f
r
(t)/(tf
r
(t)) − 1] + ¯v < 1}, σ := min {κ, ¯ρ} .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis, respectiva-
mente, considere a seq¨uˆencia {x
k
}, definida por
x
k+1
= x
k
− F
(x
k
)
−1
F (x
k
) + F
(x
k
)
−1
r
k
, k = 0, 1, . . . , (4.4)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
). (4.5)
Seja v
k
:= θ
k
cond(P
k
F
(x
k
)). Se v
k
≤ ¯v, para todo k = 0, 1, . . .. Ent˜ao, a seq ¨uˆencia (4.4)
gerada pelo m´etodo de Newton inexato com controle residual relativo escalado e com ponto
inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida na B(x
∗
, σ), converge para x
∗
e vale
x
k+1
−x
∗
≤
(1+¯v)
f
r
(x
0
− x
∗
)
x
0
− x
∗
f
r
(x
0
− x
∗
)
−1
+¯v
x
k
−x
∗
, ∀ k = 0, 1, . . . . (4.6)
28
Observa¸c˜ao 4.2. Combinando a desigualdade (4.6), a defini¸c˜ao de σ e a Proposi¸c˜ao 3.6,
obtemos que {x
k
} converge linearmente para x
∗
.
Para provar o Teorema 4.1 precisaremos de alguns resultados. Para isso, assumimos
que as hip´oteses do Teorema 4.1 s˜ao v´alidas.
Observamos que todas as afirma¸c˜oes que faremos nesta se¸c˜ao envolvendo a fun¸c˜ao
majorante radial f
r
, o m´odulo da itera¸c˜ao de Newton associada a ela n
f
r
e as suas rela¸c˜oes
com operador n˜ao-linear considerado foram provadas nas Se¸c˜oes 3.1 e 3.2, respectivamente.
Primeiramente, como Ω ´e aberto ´e imediato concluir que κ > 0. Agora, segue das
Proposi¸c˜ao 3.2 com f = f
r
e Proposi¸c˜ao 3.6 que as constantes ν e ¯ρ s˜ao positivas. Con-
seq¨uentemente, σ > 0.
Para facilitar a demonstra¸c˜ao do Teorema 4.1 apresentamos o seguinte resultado auxi-
liar.
Lema 4.3. Seja a seq¨uˆencia {x
k
} como definida no Teorema 4.1. Se x
k
∈ B(x
∗
, σ)/{x
∗
},
ent˜ao
x
k+1
− x
∗
≤
(1 + ¯v)
|n
f
r
(x
k
− x
∗
)|
x
k
− x
∗
+ ¯v
x
k
− x
∗
< x
k
− x
∗
. (4.7)
Como consequˆencia, a sequˆencia {x
k
} est´a bem definida e {x
k
} ⊂ B(x
∗
, σ).
Demonstra¸c˜ao. Como x
k
∈ B(x
∗
, σ)/{x
∗
} segue do Lema 3.11 que F
(x
k
) ´e n˜ao-singular.
Assim, x
k+1
est´a bem definida. J´a que F (x
∗
) = 0, usando a defini¸c˜ao em (3.13) obtemos,
ap´os simples c´alculos, que
x
k+1
− x
∗
= x
k
− x
∗
− F
(x
k
)
−1
(F (x
k
) − F (x
∗
)) + F
(x
k
)
−1
r
k
= F
(x
k
)
−1
(F (x
∗
) − [F (x
k
) + F
(x
k
)(x
∗
− x
k
)]) + F
(x
k
)
−1
r
k
= F
(x
k
)
−1
E
F
(x
k
, x
∗
) + F
(x
k
)
−1
r
k
.
Reunindo a ´ultima igualdade com algumas propriedades da norma, obtemos ap´os simples
manipula¸c˜oes alg´ebrica que
x
k+1
− x
∗
≤ F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
) + F
(x
k
)
−1
P
−1
k
P
k
r
k
.
Agora, considerando a desigualdade acima junto com (4.5) ´e f´acil ver que
x
k+1
− x
∗
≤ F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
) + θ
k
F
(x
k
)
−1
P
−1
k
P
k
F (x).
29
Sendo v
k
= θ
k
(P
k
F (x
k
))
−1
P
k
F
(x
k
) ≤ ¯v < 1, para k = 0, 1, . . . , segue da defini¸c˜ao
em (3.15) que
θ
k
F
(x
k
)
−1
P
−1
k
P
k
F (x
k
) ≤ θ
k
(P
k
F (x
k
))
−1
P
k
F
(x
k
)S
F
(x
k
) ≤ ¯vS
F
(x
k
).
Assim, obtemos imediatamente das duas ´ultimas equa¸c˜oes que
x
k+1
− x
∗
≤ F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
) + ¯vS
F
(x
k
).
Combinando a desigualdade anterior com o Lema 3.11, Lema 3.12 e Lema 3.13, obtemos
x
k+1
− x
∗
≤
e
f
r
(||x
k
− x
∗
||, 0)
|f
r
(||x
k
− x
∗
||)|
+ ¯v s
f
r
(||x
k
− x
∗
||).
Por outro lado, usando as defini¸c˜oes em (3.14), (3.1) e (3.15), segue de h1 que
e
f
r
(x
k
− x
∗
, 0)
|f
r
(x
k
− x
∗
)|
= |n
f
r
(x
k
− x
∗
)|, s
f
r
(||x
k
− x
∗
||) = |n
f
r
(x
k
− x
∗
)| + x
k
− x
∗
.
Portanto, usando a desigualdade acima e as duas ´ultimas igualdades conclu´ımos que
x
k+1
− x
∗
≤ (1 + ¯v)|n
f
r
(x
k
− x
∗
)| + ¯vx
k
− x
∗
,
que ´e obviamente equivalente a primeira desigualdade do lema. Agora, pelas hip´oteses
do Teorema 4.1 temos que σ ≤ ¯ρ e v
k
≤ ¯v < 1. Assim pelas Proposi¸c˜ao 3.6 obtemos a
seguinte desigualdade (1 + ¯v)|n
f
r
(x
k
− x
∗
)|/x
k
− x
∗
+ ¯v < 1. Diante disso, segue da
primeira desigualdade em (4.7) que
x
k+1
− x
∗
< x
k
− x
∗
,
concluindo a primeira parte.
Para concluir a prova, note que por hip´otese x
0
∈ B(x
∗
, σ)/{x
∗
}. Suponhamos por
indu¸c˜ao que x
k
∈ B(x
∗
, σ)/{x
∗
}. Como j´a observamos F
(x
k
) ´e n˜ao-singular e assim x
k+1
est´a bem definido. Agora, desde que x
k
− x
∗
< σ segue da ´ultima desigualdade do lema
que x
k+1
− x
∗
< σ, isto ´e, x
k+1
∈ B(x
∗
, σ)/{x
∗
} o que conclui a prova.
4.1.1 Prova do Teorema 4.1
Fa¸camos agora a demonstra¸c˜ao do Teorema 4.1.
30
Demonstra¸c˜ao. Primeiro, note que estamos sob as hip´oteses σ ≤ ¯ρ < ν, x
0
∈ B(x
∗
, σ) e
v
k
= θ
k
cond(P
k
F
(x
k
)) ≤ ¯v < 1, ∀ k = 0, 1, . . . .
Usando o Lema 4.3 podemos concluir que {x
k
} ´e bem definida e est´a contida em B(x
∗
, σ).
Ainda pelo Lema 4.3 conclu´ımos que a seq¨uˆencia {x
k
− x
∗
} ´e decrescente, isto ´e,
x
k+1
− x
∗
< x
k
− x
∗
, ∀ k = 0, 1, . . . . (4.8)
Agora, iremos provar a convergˆencia de {x
k
}. Visto que, o Corol´ario 3.5 implica, em par-
ticular, que a aplica¸c˜ao (0, σ) t → |n
f
r
(t)|/t ´e n˜ao-decrescente, segue das desigualdades
(4.8) e da primeira desigualdade em (4.7) que
x
k+1
− x
∗
≤
(1 + ¯v)
|n
f
r
(x
0
− x
∗
)|
x
0
− x
∗
+ ¯v
x
k
− x
∗
, ∀ k = 0, 1, . . . . (4.9)
J´a que, pela Proposi¸c˜ao 3.6 temos que (1 + ¯v)|n
f
r
(x
0
− x
∗
)|/x
0
− x
∗
+ ¯v < 1, a
desigualdade (4.9) junto com a Proposi¸c˜ao 2.2 implica que a seq¨uˆencia {x
k
} converge
para x
∗
.
Finalmente, usando a defini¸c˜ao (3.1) na inequa¸c˜ao (4.9), obtemos ap´os simples c´alculos que
x
k+1
− x
∗
≤
(1 + ¯v)
f
r
(x
0
− x
∗
)
x
0
− x
∗
f
r
(x
0
− x
∗
)
− 1
+ ¯v
x
k
− x
∗
∀ k = 0, 1, . . . ,
concluindo a prova.
4.2 Convergˆencia para Condi¸c˜ao Radial Lipschitz
Em nosso estudo para o m´etodo de Newton inexato, assumimos a hip´otese (4.3) que relaxa
a hip´otese da derivada ser radial Lipschitz, que por sua vez, relaxa a hip´otese tradicional,
a sab er, da derivada ser Lipschitz. Nesta se¸c˜ao, aplicaremos os resultados para a condi¸c˜ao
radial Lipschitz.
Corol´ario 4.4. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω e seja κ := sup{t > 0 : B(x
∗
, t) ⊂ Ω}. Suponha que
F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe K > 0 tal que
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ (1 − τ)Kx − x
∗
,
31
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R.
Dado 0 ≤ ¯v < 1. Seja
σ := min {κ, 2(1 − ¯v)/ (K(3 − ¯v)}) .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis, respectiva-
mente, considere a seq¨uˆencia {x
k
}, definida por
x
k+1
= x
k
− F
(x
k
)
−1
F (x
k
) + F
(x
k
)
−1
r
k
, k = 0, 1, . . . . (4.10)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
).
Seja v
k
= θ
k
cond(P
k
F
(x
k
)). Se v
k
≤ ¯v, para todo k = 0, 1, . . .. Ent˜ao, a seq¨uˆencia (4.10)
gerada pelo m´etodo de Newton inexato com controle residual relativo escalado e com ponto
inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida em B(x
∗
, σ), converge para x
∗
e vale
x
k+1
− x
∗
≤
¯v +
Kx
0
− x
∗
(1 + ¯v)
2(1 − Kx
0
− x
∗
)
x
k
− x
∗
, k = 0, 1, . . . .
Demonstra¸c˜ao.
´
E imediato que h : [0, κ) → R, definida por h(t) = Kt
2
/2 − t, satisfaz as
condi¸c˜oes h1 e h2 no Teorema 4.1. Tamb´em, note que para t < 1/K
h
(t) = Kt − 1 < 0.
Al´em disso, para t < 2(1 − ¯v)/K(3 − ¯v) temos
(1 + ¯v)[h(t)/(th
(t)) − 1] + ¯v < 1.
Portanto, as constantes ¯ρ e ν definidas no Teorema 4.1 s˜ao
¯ρ = 2(1 − ¯v)/ (K(3 − ¯v)) ≤ ν = 1/K.
Assim, tomando f
r
= h, temos F , σ, h e x
0
satisfazendo todas as hip´oteses do Teorema
4.1. Portanto, todas afirma¸c˜oes deste teorema est˜ao provadas como conseq¨uˆencia do
Teorema 4.1.
No pr´oximo cap´ıtulo, estaremos interessados em provar a convergˆencia do m´etodo
quase-Newton inexato. Utilizaremos racioc´ınio an´alogo ao deste cap´ıtulo.
Cap´ıtulo 5
M´etodo Quase-Newton Inexato
Neste cap´ıtulo provaremos a convergˆencia do m´etodo quase-Newton inexato para resolver
sistemas de equa¸c˜oes n˜ao-lineares. Comprovaremos que sob certas condi¸c˜oes a seq¨uˆencia
gerada pelo m´etodo est´a bem definida e converge linearmente para uma solu¸c˜ao do sis-
tema em considera¸c˜ao. Encerraremos, aplicando os resultados obtidos em uma situa¸c˜ao
particular.
5.1 Convergˆencia do M´etodo Quase-Newton Inexato
Nesta se¸c˜ao provaremos a convergˆencia para o m´etodo quase-Newton inexato.
Inicialmente, sejam Ω ⊆ R
n
um conjunto aberto e uma fun¸c˜ao F : Ω → R
n
continua-
mente diferenci´avel em Ω. Considere o sistema de equa¸c˜oes n˜ao-lineares
F (x) = 0. (5.1)
O m´etodo quase-Newton inexato usado para resolver (5.1) ´e o caso onde admitimos
que B
k
seja uma aproxima¸c˜ao de F
(x
k
) em (4.2).
Supondo que o sistema n˜ao-linear (5.1) tem solu¸c˜ao, mostraremos que, tomando o
ponto inicial x
0
numa vizinhan¸ca apropriada da solu¸c˜ao, a seq¨uˆencia gerada pelo m´etodo
quase-Newton inexato est´a bem definida e converge linearmente para uma solu¸c˜ao de
(5.1). Est´a afirma¸c˜ao ´e o teorema:
32
33
Teorema 5.1. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω, R > 0 e seja κ := sup{t ∈ [0, R) : B(x
∗
, t) ⊂ Ω}.
Suponha que F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe uma fun¸c˜ao continuamente
diferenci´avel f
r
: [0, R) → R tal que
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ f
r
(x − x
∗
) − f
r
(τx − x
∗
) , (5.2)
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R, onde
h1) f
r
(0) = 0 e f
r
(0) = −1;
h2) f
r
´e convexa e crescente.
Dada as constantes n˜ao-negativas ˜v, ω
1
e ω
2
satisfazendo ˜v < 1 e ω
1
˜v + ω
2
< 1, considere
as constante positivas ν := sup{t ∈ [0, κ) : f
r
(t) < 0},
˜ρ := sup{t ∈ (0, ν) : ω
1
(1 + ˜v)[f
r
(t)/(tf
r
(t)) − 1] + ω
1
˜v + ω
2
< 1}, σ := min {κ, ˜ρ} .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis respectiva-
mente, considere B(x
k
) uma aproxima¸c˜ao para F
(x
k
), onde B(x
k
) ´e invert´ıvel e satisfaz
B(x
k
)
−1
F
(x
k
) ≤ ω
1
, B(x
k
)
−1
F
(x
k
) − I ≤ ω
2
, ∀ k = 0, 1, . . . . (5.3)
Considere a seq¨uˆencia
x
k+1
= x
k
− B(x
k
)
−1
F (x
k
) + B(x
k
)
−1
r
k
, ∀ k = 0, 1, . . . , (5.4)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
). (5.5)
Seja v
k
= θ
k
cond(P
k
F
(x
k
)). Se v
k
≤ ˜v, para todo k = 0, 1, . . .. Ent˜ao, a seq¨uˆencia (5.4)
gerada pelo m´etodo quase-Newton inexato com controle residual relativo escalado e com
ponto inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida na B(x
∗
, σ), converge
para x
∗
e vale
x
k+1
− x
∗
≤
ω
1
(1 + ˜v)
f
r
(x
0
− x
∗
)
x
0
− x
∗
f
r
(x
0
− x
∗
)
− 1
+ ω
1
˜v + ω
2
x
k
− x
∗
, (5.6)
para todo k = 0, 1 , . . . .
34
Observa¸c˜ao 5.2. Combinando a desigualdade (5.6), a defini¸c˜ao de σ e a Proposi¸c˜ao 3.7,
obtemos que {x
k
} converge linearmente para x
∗
.
Para provar o Teorema 5.1 precisaremos de alguns resultados. Para isso, assumimos
que as hip´oteses do Teorema 5.1 s˜ao v´alidas.
Observamos que todas as afirma¸c˜oes que faremos nesta se¸c˜ao envolvendo a fun¸c˜ao
majorante radial f
r
, o m´odulo da itera¸c˜ao de Newton associada a ela n
f
r
e as suas rela¸c˜oes
com operador n˜ao-linear considerado foram provadas nas Se¸c˜oes 3.1 e 3.2, respectivamente.
Primeiramente, como Ω ´e aberto ´e imediato concluir que κ > 0. Agora, segue das
Proposi¸c˜ao 3.2 com f = f
r
e Proposi¸c˜ao 3.7 que as constantes ν e ¯ρ s˜ao positivas. Con-
seq¨uentemente, σ > 0.
Para facilitar a demonstra¸c˜ao do Teorema 5.1 apresentamos o seguinte resultado auxi-
liar.
Lema 5.3. Seja a seq¨uˆencia {x
k
} como definida no Teorema 5.1. Se x
k
∈ B(x
∗
, σ)/{x
∗
},
ent˜ao
x
k+1
− x
∗
≤
ω
1
(1 + ˜v)
|n
f
(x
k
− x
∗
)|
x
k
− x
∗
+ ω
1
˜v + ω
2
x
k
− x
∗
< x
k
− x
∗
. (5.7)
Como consequˆencia, a sequˆencia {x
k
} est´a bem definida e {x
k
} ⊂ B(x
∗
, σ).
Demonstra¸c˜ao. Como x
k
∈ B(x
∗
, σ)/{x
∗
} segue do Lema 3.11 que F
(x
k
) ´e n˜ao-singular.
Assim, x
k+1
est´a bem definida. J´a que F (x
∗
) = 0, usando a defini¸c˜ao em (3.13), obtemos
ap´os simples c´alculos que
x
k+1
− x
∗
= x
k
− x
∗
− B(x
k
)
−1
(F (x
k
) − F (x
∗
)) + B(x
k
)
−1
r
k
= B(x
k
)
−1
F (x
∗
) − [F (x
k
) + F
(x
k
)(x
∗
− x
k
)]
+ (B(x
k
)
−1
F
(x
k
) − I)(x
∗
− x
k
)
+ B(x
k
)
−1
r
k
= B(x
k
)
−1
E
F
(x
k
, x
∗
) + (B(x
k
)
−1
F
(x
k
) − I)(x
∗
− x
k
) + B
−1
(x
k
)r
k
.
Reunindo a ´ultima igualdade com algumas propriedades da norma, obtemos ap´os simples
manipula¸c˜oes alg´ebricas que
x
k+1
− x
∗
≤ B(x
k
)
−1
F
(x
k
)F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
)
+ B(x
k
)
−1
F
(x
k
) − Ix
k
− x
∗
+ B(x
k
)
−1
F
(x
k
)F
(x
k
)
−1
P
−1
k
P
k
r
k
.
35
Considerando a desigualdade acima junto com as hip´oteses (5.3) e (5.5) ´e f´acil ver, que
x
k+1
− x
∗
≤ ω
1
F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
)
+ ω
2
x
k
− x
∗
+ ω
1
θF
(x
k
)
−1
P
−1
k
P
k
F (x
k
).
Sendo v
k
= θ
k
(P
k
F (x
k
))
−1
P
k
F
(x
k
) ≤ ˜v < 1, para k = 0, 1, . . . , segue da defini¸c˜ao
em (3.15) que
ω
1
θ
k
F
(x
k
)
−1
P
−1
k
P
k
F (x
k
) ≤ ω
1
θ
k
(P
k
F (x
k
))
−1
P
k
F
(x
k
)S
F
(x
k
) ≤ ω
1
˜vS
F
(x
k
).
Assim, obtemos imediatamente das duas ´ultimas equa¸c˜oes que
x
k+1
− x
∗
≤ ω
1
F
(x
k
)
−1
F
(x
∗
)F
(x
∗
)
−1
E
F
(x
k
, x
∗
) + ω
2
x
k
− x
∗
+ ω
1
˜vS
F
(x
k
).
Combinando a ´ultima desigualdade com o Lemas 3.11, Lema 3.12 e Lema 3.13, obtemos
x
k+1
− x
∗
≤ ω
1
e
f
r
(||x
k
− x
∗
||, 0)
|f
r
(||x
k
− x
∗
||)|
+ ω
2
x
k
− x
∗
+ ω
1
˜v s
f
r
(||x
k
− x
∗
||).
Por outro lado, usando as defini¸c˜oes em (3.14), (3.1) e (3.15), segue de h1 que
e
f
r
(x
k
− x
∗
, 0)
|f
r
(x
k
− x
∗
)|
= |n
f
r
(x
k
− x
∗
)|, s
f
r
(||x
k
− x
∗
||) = |n
f
r
(x
k
− x
∗
)| + x
k
− x
∗
.
Portanto, usando a desigualdade acima e as duas ´ultimas igualdades conclu´ımos que
x
k+1
− x
∗
≤ ω
1
(1 + ˜v)|n
f
r
(x
k
− x
∗
)| + ω
2
x
k
− x
∗
+ ω
1
˜vx
k
− x
∗
,
que ´e obviamente equivalente a primeira desigualdade do lema. Agora, pelas hip´oteses do
Teorema 5.1 temos que σ ≤ ˜ρ, v
k
≤ ˜v < 1 e ω
1
˜v + ω
2
< 1. Assim pela Proposi¸c˜ao 3.7
obtemos a seguinte desigualdade ω
1
(1 + ˜v)|n
f
r
(x
k
− x
∗
)|/x
k
− x
∗
+ ω
1
˜v + ω
2
< 1.
Diante disso, segue da primeira desigualdade em (5.7) que
x
k+1
− x
∗
< x
k
− x
∗
,
concluindo a primeira parte.
Para concluir a prova, note que por hip´otese x
0
∈ B(x
∗
, σ)/{x
∗
}. Suponhamos por
indu¸c˜ao que x
k
∈ B(x
∗
, σ)/{x
∗
}. Como j´a observamos F
(x
k
) ´e n˜ao-singular e assim x
k+1
est´a bem definido. Agora, desde que x
k
− x
∗
< σ segue da ´ultima desigualdade do lema
que x
k+1
− x
∗
< σ, isto ´e, x
k+1
∈ B(x
∗
, σ)/{x
∗
} o que conclui a prova.
36
5.1.1 Prova do Teorema 5.1
Fa¸camos agora a demonstra¸c˜ao do Teorema 5.1.
Demonstra¸c˜ao. Primeiro, note que estamos sob as hip´oteses que σ ≤ ˜ρ < ν, ω
1
+ ω
2
≤ 1,
x
0
∈ B(x
∗
, σ) e
v
k
= θ
k
cond(P
k
F
(x
k
)) ≤ ˜v < 1 ∀ k = 0, 1, . . . .
Usando o Lema 5.3 podemos concluir que {x
k
} ´e bem definida e est´a contida em B(x
∗
, σ).
Ainda pelo Lema 5.3 conclu´ımos que a seq¨uˆencia {x
k
− x
∗
} ´e decrescente, isto ´e,
x
k+1
− x
∗
< x
k
− x
∗
, ∀ k = 0, 1, . . . . (5.8)
Agora, iremos provar a convergˆencia de {x
k
}. Visto que, o Corol´ario 3.5 implica, em
particular, que a aplica¸c˜ao (0, σ) t → |n
f
r
(t)|/t ´e n˜ao-decrescente, segue da desigualdade
(5.8) e da primeira desigualdade em (4.7) que
x
k+1
− x
∗
≤
ω
1
(1 + ˜v)
|n
f
r
(x
0
− x
∗
)|
x
0
− x
∗
+ ω
1
˜v + ω
2
x
k
− x
∗
, ∀ k = 0, 1, . . . . (5.9)
J´a que, pela Proposi¸c˜ao 3.7 temos que ω
1
(1 + ˜v)|n
f
r
(x
0
− x
∗
)|/x
0
− x
∗
+ ω
1
˜v + ω
2
< 1,
a desigualdade (5.9) junto com a Proposi¸c˜ao 2.2 implica que a seq¨uˆencia {x
k
} converge
para x
∗
.
Finalmente, usando a defini¸c˜ao 3.1 na equa¸c˜ao 5.9, obtemos ap´os simples c´alculos que
x
∗
− x
k+1
≤
ω
1
(1 + ˜v)
f
r
(x
0
− x
∗
)
x
0
− x
∗
f
r
(x
0
− x
∗
)
− 1
+ ω
1
˜v + ω
2
x
k
− x
∗
,
para todo k = 0, 1, . . . , concluindo a prova.
5.2 Resultados para Condi¸c˜ao Radial Lipschitz
Em nosso estudo para o m´etodo quase-Newton inexato, assumimos a hip´otese (5.2) que
relaxa a hip´otese da derivada ser radial Lipschitz, que por sua vez, relaxa a hip´otese
tradicional, a saber, da derivada ser Lipschitz. Nesta se¸c˜ao, aplicaremos os resultados
para a condi¸c˜ao radial Lipschitz.
37
Corol´ario 5.4. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω e seja κ := sup{t > 0 : B(x
∗
, t) ⊂ Ω}. Suponha que
F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe K > 0 tal que
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ (1 − τ)Kx − x
∗
,
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R.
Dadas as constantes n˜ao-negativas ˜v, ω
1
e ω
2
satisfazendo ˜v < 1 e ω
1
˜v +ω
2
< 1, considere
σ := min {κ, 2(1 − ˜vω
1
− ω
2
)/ (K(2 + ω
1
− ˜vω
1
− 2ω
2
))} .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis respectiva-
mente, considere B(x
k
) uma aproxima¸c˜ao para F
(x
k
), onde B(x
k
) ´e invert´ıvel e
B(x
k
)
−1
F
(x
k
) ≤ ω
1
, B(x
k
)
−1
F
(x
k
) − I ≤ ω
2
, ∀ k = 0, 1, . . . .
Considere a seq¨uˆencia
x
k+1
= x
k
− B(x
k
)
−1
F (x
k
) + B(x
k
)
−1
r
k
, ∀ k = 0, 1, . . . , (5.10)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
).
Seja v
k
= θ
k
cond(P
k
F
(x
k
)). Se v
k
≤ ˜v, para todo k = 0, 1, . . .. Ent˜ao, a seq¨uˆencia (5.10)
gerada pelo m´etodo quase-Newton inexato com controle residual relativo escalado e com
ponto inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida na B(x
∗
, σ), converge
para x
∗
e vale
x
k+1−x
∗
≤
ω
1
˜v +
Kx
0
− x
∗
ω
1
(1 + ˜v)
2(1 − Kx
0
− x
∗
)
+ ω
2
x
k
− x
∗
, ∀ k = 0, 1, . . . .
Demonstra¸c˜ao.
´
E imediato que h : [0, κ) → R, definida por h(t) = Kt
2
/2 − t, satisfaz as
condi¸c˜oes h1 e h2 no Teorema 5.4. Tamb´em, note que para t < 1/K
h
(t) = Kt − 1 < 0.
Al´em disso, para t < 2(1 − ˜vω
1
− ω
2
)/K(2 + ω
1
− ˜vω
1
− 2ω
2
) temos
ω
1
(1 + ˜v)[h(t)/(th
(t)) − 1] + + ω
1
˜v + ω
2
< 1.
38
Portanto, as constantes ˜ρ e ν definidos no Teorema 5.1 s˜ao
˜ρ = 2(1 − ˜vω
1
− ω
2
)/ (K(2 + ω
1
− ˜vω
1
− 2ω
2
)) ≤ ν = 1/K,
Assim, tomando f
r
= h, temos F , σ, h e x
0
satisfazendo todas as hip´oteses do Teorema
5.1. Portanto, todas afirma¸c˜oes deste teorema est˜ao provadas como conseq¨uˆencia do
Teorema 5.1.
No pr´oximo cap´ıtulo, estaremos interessados em provar a convergˆencia do m´etodo de
Newton modificado inexato. Para isso, trocaremos a fun¸c˜ao majorante radial pela fun¸c˜ao
majorante central e utilizaremos racioc´ınio an´alogo ao deste cap´ıtulo.
Cap´ıtulo 6
M´etodo de Newton Modificado
Inexato
Neste cap´ıtulo provaremos a convergˆencia do m´etodo de Newton modificado inexato para
resolver sistemas de equa¸c˜oes n˜ao-lineares. Comprovaremos que sob certas condi¸c˜oes a
seq¨uˆencia gerada pelo m´etodo est´a bem definida e converge linearmente para uma solu¸c˜ao
do sistema em considera¸c˜ao. Encerraremos, aplicando os resultados obtidos em uma
situa¸c˜ao particular.
6.1 Convergˆencia do m´etodo de Newton modificado
inexato
Nesta se¸c˜ao provaremos a convergˆencia para o m´etodo de Newton modificado inexato.
Inicialmente, sejam Ω ⊆ R
n
um conjunto aberto e uma fun¸c˜ao F : Ω → R
n
continua-
mente diferenci´avel em Ω. Considere o sistema de equa¸c˜oes n˜ao-lineares
F (x) = 0. (6.1)
O m´etodo de Newton modificado inexato usado para resolver (6.1) ´e o caso onde ad-
mitimos que B
k
= F
(x
0
) em (4.2).
Supondo que o sistema n˜ao-linear (6.1) tem solu¸c˜ao, mostraremos que tomando o
ponto inicial x
0
numa vizinhan¸ca apropriada da solu¸c˜ao, a seq¨uˆencia gerada pelo m´etodo
39
40
de Newton modificado inexato est´a bem definida e converge linearmente para uma solu¸c˜ao
de (6.1). Est´a afirma¸c˜ao ´e o teorema:
Teorema 6.1. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω, R > 0 e seja κ := sup{t ∈ [0, R) : B(x
∗
, t) ⊂ Ω}.
Suponha que F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe uma fun¸c˜ao continuamente
diferenci´avel f
c
: [0, R) → R tal que
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
)]
≤ f
c
(τx − x
∗
) − f
c
(0) , (6.2)
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R, onde
h1) f
c
(0) = 0 e f
c
(0) = −1;
h2) f
c
´e convexa e crescente.
Dado 0 ≤ ˆv < 1, considere as constantes positivas ν := sup{t ∈ [0, κ) : f
c
(t) < 0},
ˆρ := sup{t ∈ (0, ν) : −(1 + ˆv)(f
c
(t) + 2t)/ (tf
c
(t)) − 1 < 1}, σ := min {κ, ˆρ} .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis respectiva-
mente, considere a seq¨uˆencia
x
k+1
= x
k
− F
(x
0
)
−1
F (x
k
) + F
(x
0
)
−1
r
k
, k = 0, 1, . . . , (6.3)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
), k = 0, 1, . . . . (6.4)
Seja v
k
= θ
k
cond(P
k
F
(x
0
)). Se v
k
≤ ˆv, para todo k = 0, 1, . . .. Ent˜ao, a seq¨uˆencia (6.3)
gerada pelo m´etodo de Newton modificado inexato com controle residual relativo escalado
e com ponto inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida em B(x
∗
, σ),
converge para x
∗
e vale
x
k+1
− x
∗
≤
− (1 + ˆv)
f
c
(x
0
− x
∗
) + 2x
0
− x
∗
x
0
− x
∗
f
c
(x
0
− x
∗
)
− 1
x
k
− x
∗
, (6.5)
para todo k = 0, 1 , . . . .
41
Observa¸c˜ao 6.2. Combinando a desigualdade (6.5), a defini¸c˜ao de σ e a Proposi¸c˜ao 3.8,
obtemos que {x
k
} converge linearmente para x
∗
.
Para provar o Teorema 6.1 precisaremos de alguns resultados. Para isso, assumimos
que as hip´oteses do Teorema 6.1 s˜ao v´alidas.
Observamos que todas as afirma¸c˜oes que faremos nesta se¸c˜ao envolvendo a fun¸c˜ao
majorante central f
c
, o m´odulo da itera¸c˜ao de Newton associada a ela n
f
c
e as suas rela¸c˜oes
com operador n˜ao-linear considerado foram provadas nas Se¸c˜oes 3.1 e 3.3, respectivamente.
Primeiramente, como Ω ´e aberto ´e imediato concluir que κ > 0. Agora, segue das
Proposi¸c˜ao 3.2 com f = f
c
e Proposi¸c˜ao 3.8 que as constantes ν e ˆρ s˜ao positivas. Con-
seq¨uentemente, σ > 0.
Para facilitar a demonstra¸c˜ao do Teorema 6.1 apresentamos o seguinte resultado auxi-
liar.
Lema 6.3. Seja a seq¨uˆencia {x
k
} como definida no Teorema 6.1. Se x
k
∈ B(x
∗
, σ)/{x
∗
},
ent˜ao
x
k+1
− x
∗
≤
(1 + ˆv)
f
c
(x
k
− x
∗
) + 2x
k
− x
∗
x
k
− x
∗
|f
c
(x
0
− x
∗
)|
− 1
x
k
− x
∗
.
Demonstra¸c˜ao. Como x
k
∈ B(x
∗
, r)/{x
∗
} segue do Lema 3.16 que F
(x
k
) ´e n˜ao-singular.
Assim, x
k+1
est´a bem definida. Usando F (x
∗
) = 0 e o Teorema Fundamental do c´alculo
obtemos, ap´os algumas manipula¸c˜oes alg´ebrica que
x
k+1
− x
∗
= x
k
− x
∗
− F
(x
0
)
−1
(F (x
k
) − F (x
∗
)) + F
(x
0
)
−1
r
k
= x
k
− x
∗
− F
(x
0
)
−1
1
0
F
(x
∗
+ τ(x
k
− x
∗
))(x
k
− x
∗
)dτ + F
(x
0
)
−1
r
k
= −F
(x
0
)
−1
1
0
(F
(x
∗
+ τ(x
k
− x
∗
)) − F
(x
0
)) (x
k
− x
∗
)dτ + F
(x
0
)
−1
P
−1
k
P
k
r
k
.
Reunindo a ´ultima igualdade com algumas propriedades da norma, obtemos ap´os simples
c´alculos que
x
k+1
− x
∗
≤ F
(x
0
)
−1
F
(x
∗
)
1
0
F
(x
∗
)
−1
(F
(x
∗
+ τ(x
k
− x
∗
)) − F
(x
0
))dτx
k
− x
∗
+ F
(x
0
)
−1
P
−1
k
P
k
r
k
.
42
Agora, considerando a desigualdade acima junto com (6.4) ´e f´acil ver que
x
k+1
− x
∗
≤ F
(x
0
)
−1
F
(x
∗
)
1
0
F
(x
∗
)
−1
(F
(x
∗
+ τ(x
k
− x
∗
)) − F
(x
0
))dτx
k
− x
∗
+ θ
k
F
(x
0
)
−1
P
−1
k
P
k
F (x
k
).
Por outro lado, como v
k
= θ
k
(P
k
F (x
0
))
−1
P
k
F
(x
0
) ≤ ˆv < 1, para k = 0, 1, . . . ,
obtemos ap´os simples manipula¸c˜oes alg´ebricas que
θ
k
F
(x
0
)
−1
P
−1
k
P
k
F (x
k
) ≤ θ
k
(P
k
F (x
0
))
−1
P
k
F
(x
0
)F
(x
0
)
−1
F (x
k
)
≤ ˆvF
(x
0
)
−1
F (x
k
).
Assim, obtemos imediatamente das duas ´ultimas equa¸c˜oes que
x
k+1
− x
∗
≤ F
(x
0
)
−1
F
(x
∗
)
1
0
F
(x
∗
)
−1
(F
(x
∗
+ τ(x
k
− x
∗
)) − F
(x
0
))dτx
k
− x
∗
+ ˆvF
(x
0
)
−1
F (x
k
).
Combinando a ´ultima desigualdade, com o Lemas 3.16, Lema 3.17 e Lema 3.18, obtemos
x
k+1
− x
∗
≤
f
c
(x
k
− x
∗
) + 2x
k
− x
∗
+ f
c
(x
0
− x
∗
)x
k
− x
∗
|f
c
(||x
0
− x
∗
||)|
+ ˆv
f
c
(x
k
− x
∗
) + 2x
k
− x
∗
|f
c
(x
0
− x
∗
)|
.
Como f
(x
0
− x
∗
) < 0 em (0, σ), a desigualdade acima corresponde a
x
k+1
− x
∗
≤ (1 + ˆv)
f
c
(x
k
− x
∗
) + 2x
k
− x
∗
|f
c
(x
0
− x
∗
)|
− x
k
− x
∗
,
que ´e equivalente a desigualdade desejada.
6.1.1 Prova do Teorema 6.1
Fa¸camos agora a demonstra¸c˜ao do Teorema 6.1.
Demonstra¸c˜ao. Note que estamos sob as hip´oteses que σ ≤ ˆρ < ν, x
0
∈ B(x
∗
, σ) e
v
k
= θ
k
cond(P
k
F
(x
0
)) ≤ ˆv < 1, ∀ k = 0, 1, . . . .
43
Primeiro, mostraremos por indu¸c˜ao que a seq¨uencia {x
k
− x
∗
} ´e decrescente, isto ´e,
x
k+1
− x
∗
< x
k
− x
∗
, k = 0, 1, . . . . (6.6)
Como x
0
est´a contida na B(x
∗
, σ), obtemos do Lema 6.3 que
x
1
− x
∗
≤
(1 + ˆv)
f
c
(x
0
− x
∗
) + 2x
0
− x
∗
x
0
− x
∗
|f
c
(x
0
− x
∗
)|
− 1
x
0
− x
∗
.
Por outro lado, como x
0
est´a contida na B(x
∗
, σ) segue da Proposi¸c˜ao 3.8 a seguinte
desigualdade
[(1 + ˆv)(f
c
(x
0
− x
∗
) + 2x
0
− x
∗
/ (x
0
− x
∗
|f
c
(x
0
− x
∗
)|) 1] < 1. (6.7)
Da´ı, combinando as duas ´ultimas desigualdades conclu´ımos que x
1
− x
∗
< x
0
− x
∗
.
Agora, suponha que (6.6) seja v´alido para k, isto ´e, que x
k
− x
∗
< x
0
− x
∗
< σ.
Visto que, a Proposi¸c˜ao 3.3 implica, em particular, que a aplica¸c˜ao (0, σ) t → f(t)+2t/t
´e n˜ao-decrescente, segue do Lema 6.3 e da hip´otese de indu¸c˜ao que
x
k+1
− x
∗
≤
(1 + ˆv)
f
c
(x
0
− x
∗
) + 2x
0
− x
∗
x
0
− x
∗
|f
c
(x
0
− x
∗
)|
− 1
x
k
− x
∗
. (6.8)
Assim, da equa¸c˜ao anterior e (6.7) conclu´ımos que (6.6) ´e v´alida, isto ´e, {x
k
− x
∗
} ´e
decrescente.
Agora, como {x
k
− x
∗
} ´e decrescente obtemos do Lema 3.16 que {x
k
} est´a bem
definida e do Lema 6.3 que {x
k
} est´a contida na B(x
∗
, σ).
Por outro lado, obtemos das desigualdades (6.7) e (6.8) junto com a Proposi¸c˜ao 2.2
que a seq¨uˆencia {x
k
} converge para x
∗
.
Finalmente, usando que f
< 0 em (0, σ) a desigualdade (6.8) ´e equivalente a desigual-
dade do teorema.
6.2 Resultados para Condi¸c˜ao Central Lipschitz
Em nosso estudo para o m´etodo de Newton modificado inexato, assumimos a hip´otese
(6.2) que relaxa a hip´otese da derivada ser radial Lipschitz, que por sua vez, relaxa a
hip´otese tradicional, a saber, da derivada ser Lipschitz. Nesta se¸c˜ao, aplicaremos os
resultados para a condi¸c˜ao radial Lipschitz.
44
Corol´ario 6.4. Sejam Ω ⊆ R
n
um conjunto aberto e F : Ω → R
n
continuamente di-
ferenci´avel em Ω. Tome x
∗
∈ Ω e seja κ := sup{t > 0 : B(x
∗
, t) ⊂ Ω}. Suponha que
F
(x
∗
) seja n˜ao-singular, F (x
∗
) = 0 e existe K > 0 tal que
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
)]
≤ τKx − x
∗
,
para τ ∈ [0, 1], x ∈ B(x
∗
, κ), x − x
∗
< R.
Dado 0 ≤ ˆv < 1, considere
σ := min {κ, 2(1 − ˆv)/ (K(5 + ˆv))} .
Dadas as seq¨uˆencias {θ
k
} e {P
k
}, de n´umeros reais e de matrizes invert´ıveis respectiva-
mente, considere a seq¨uˆencia
x
k+1
= x
k
− F
(x
0
)
−1
F (x
k
) + F
(x
0
)
−1
r
k
, k = 0, 1, . . . , (6.9)
onde o vetor erro r
k
satisfaz a seguinte condi¸c˜ao
P
k
r
k
≤ θ
k
P
k
F (x
k
).
Seja v
k
= θ
k
cond(P
k
F
(x
0
)). Se v
k
≤ ˆv, para todo k = 0, 1, . . .. Ent˜ao, a seq¨uˆencia (6.9)
gerada pelo m´etodo de Newton modificado inexato com controle residual relativo escalado
e com ponto inicial x
0
∈ B(x
∗
, σ)/{x
∗
} est´a bem definida, est´a contida em B(x
∗
, σ),
converge para x
∗
e vale
x
k+1
− x
∗
≤
(1 + ˆv)(2 + Kx
0
− x
∗
)
2(1 − Kx
0
− x
∗
)
− 1
x
k
− x
∗
, ∀ k = 0, 1, . . . .
Demonstra¸c˜ao.
´
E imediato que h : [0, κ) → R, definida por h(t) = Kt
2
/2 − t, satisfaz as
condi¸c˜oes h1 e h2 no Teorema 6.1. Tamb´em, note que para t < 1/K
h
(t) = Kt − 1 < 0.
Al´em disso, para t < 2(1 − ˆv)/K(5 + ˆv) temos
(1 + ˆv)[−h(t)/(th
(t)) − 2/h
(t)] − 1 < 1.
Portanto, as constantes ˆρ e ν definidas no Teorema 6.1 s˜ao
ˆρ = 2(1 − ˆv)/K(5 + ˆv) ≤ ν = 1/K.
45
Assim, tomando f
c
= h, temos F , σ, h e x
0
satisfazendo todas as hip´oteses do Teorema
6.1. Portanto, todas afirma¸c˜oes deste teorema est˜ao provadas como conseq¨uˆencia do
Teorema 6.1.
Desta forma, com este cap´ıtulo encerramos nossa an´alise da convergˆencia linear do
m´etodo de Newton inexato e suas varia¸c˜oes, sob o ponto de vista do princ´ıpio majorante
de Kantorovich.
Considera¸c˜oes Finais
Neste trabalho, estudamos e demonstramos resultados acerca de convergˆencia local do
m´etodo de Newton inexato e suas varia¸c˜oes.
A convergˆencia do m´etodo de Newton inexato e suas varia¸c˜oes foram estudadas nas
referˆencias [3], [8] e [10]. A demonstra¸c˜ao feita em [3] ´e trabalhosa e seus resultados s˜ao
de dif´ıceis aplica¸c˜oes. Enquanto que em [8] e [10] as provas s˜ao um pouco mais simples,
por´em, as condi¸c˜oes para que ocorra a convergˆencia n˜ao est˜ao claras. Especificamente,
nesta ´ultima, as hip´oteses de convergˆencia diferem das adotadas nesta disserta¸c˜ao com
respeito a:
• no, lugar da seguinte condi¸c˜ao que utilizamos nos Teoremas 4.1 e 5.1
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤ f
r
(x − x
∗
) − f
r
(τx − x
∗
) ,
onde f
r
´e a fun¸c˜ao majorante radial, ´e utilizada a condi¸c˜ao radial Lipschitz relaxada
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤
x−x
∗
τ x−x
∗
L(u)du, o ≤ τ ≤ 1, (6.10)
onde L ´e uma fun¸c˜ao escalar n˜ao-decrescente.
• no, lugar da seguinte condi¸c˜ao que utilizamos no Teorema 6.1
F
(x
∗
)
−1
[F
(x
∗
+ τ(x − x
∗
)) − F
(x
∗
)]
≤ f
c
(τx − x
∗
) − f
c
(0) ,
onde f
c
´e a fun¸c˜ao majorante central, ´e utilizada a condi¸c˜ao central Lipschitz relaxada
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
≤
τ x−x
∗
0
L(u)du, o ≤ τ ≤ 1, (6.11)
46
47
onde L ´e uma fun¸c˜ao escalar n˜ao-decrescente.
Entretanto, note que as condi¸c˜oes (6.10) e (6.11) podem ser vistas como um caso
particular da fun¸c˜ao majorante radial e central, resp ectivamente. Para verificarmos esta
afirma¸c˜ao, basta escolhermos as fun¸c˜oes majorantes radial e central da seguinte forma:
f
r
(t) = f
c
(t) =
t
0
L(u)(t − u)du − t.
Temos que as fun¸c˜oes f
r
(t) e f
c
(t) definidas acima satisfazem as hip´oteses h1 e h2. Al´em
disso, tamb´em temos que
f
r
(t) = f
c
(t) =
t
0
L(u)du − 1.
Assim, obtemos ap´os alguns c´alculos que
f
r
(x−x
∗
)−f
r
(τx−x
∗
) =
x−x
∗
τ x−x
∗
L(u)du, f
c
(τx−x
∗
)−f
c
(0) =
τ x−x
∗
0
L(u)du,
o que prova nossa afirma¸c˜ao. De fato, podemos mostrar que as condi¸c˜oes da fun¸c˜ao
majorante radial e central, s˜ao equivalentes as condi¸c˜oes (6.10) e (6.11) respectivamente.
Mas, como adotadas aqui s˜ao mais naturais e deixam claro as suas rela¸c˜oes com o operador
n˜ao-linear, refletindo de maneira sim´etrica em todos os resultados.
Nossa contribui¸c˜ao foi reformular os teoremas de convergˆencia para o m´etodo de New-
ton e suas varia¸c˜oes usando o princ´ıpio majorante de Kantorovich. Esta nova abordagem
deixou claro a rela¸c˜ao entre a fun¸c˜ao majorante com o operador n˜ao-linear em conside-
ra¸c˜ao, o que n˜ao estava expl´ıcito nas outras demonstra¸c˜oes. Com isso, os resultados
apresentados aqui tornaram a prova mais simples e mais did´atica.
Uma outra contribui¸c˜ao foi fazer um estudo completo da fun¸c˜ao majorante, onde
quase todos os resultados necess´arios para a convergˆencia dos m´etodos de Newton e suas
varia¸c˜oes foram demonstrados, deixando o texto “auto-contido”.
Os Teoremas 4.1, 5.1 e 6.1 com seus respectivos Corol´arios 4.4, 5.4 e 6.4 d˜ao uma
estimativa para o raio de convergˆencia dos m´etodos de Newton inexatos e suas varia¸c˜oes.
At´e aqui sabemos que, tomando o ponto inicial x
0
em B(x
∗
, σ) a seq¨uˆencia gerada por
estes m´etodos converge linearmente para uma solu¸c˜ao do sistema n˜ao-linear. Note que,
em cada caso, σ depende de ¯v, ˜v e ˆv. Agora, para ¯v, ˜v e ˆv fixos podemos fazer a seguinte
48
pergunta: Qual ser´a o maior raio de convergˆencia? No pr´oximo exemplo, mostraremos
que se considerarmos o caso em que anulamos a seq ¨uˆencia “forcing,”o raio de convergˆencia
dado pelo Corol´ario 4.4 ´e o maior poss´ıvel.
Exemplo 6.5. Considere a fun¸c˜ao
F (x) =
−x +
1
3
x
2
, 0 ≤ x ≤ 2;
−x −
1
3
x
2
, −2 ≤ x < 0.
Ent˜ao,
F
(x) =
−1 +
2
3
x, 0 ≤ x ≤ 2;
−1 −
2
3
x
,
−2 ≤ x < 0.
Obviamente, x
∗
= 0 ´e um zero de F e F
(x) satisfaz
F
(x
∗
)
−1
[F
(x) − F
(x
∗
+ τ(x − x
∗
))]
=
2
3
(1 − τ)x − x
∗
.
Da´ı, usando os m´etodos inexatos de Newton e suas varia¸c˜oes, obtemos atrav´es dos Corol´arios
4.4, 5.4 e 6.4 para cada ¯v, ˜v e ˆv, respectivamente, uma estimativa para o raio de con-
vergˆencia.
Al´em disso, se para a fun¸c˜ao acima escolhermos ¯v = 0, o raio σ = 1 dado pelo
Corol´ario 4.4 ´e o maior poss´ıvel, pois tomando x
0
= 1, a seq¨uˆencia gerada pelo m´etodo
de Newton inexato diverge. De fato, se x
0
= 1 e ¯v = 0, n´os temos
x
1
= x
0
− F
(x
0
)
−1
F (x
0
) = x
0
−
1
−1 +
2
3
x
0
−x
0
+
1
3
x
2
0
= x
0
− 2x
0
= −1,
x
2
= x
1
− F
(x
1
)
−1
F (x
1
) = x
1
−
1
−1 −
2
3
x
1
−x
1
−
1
3
x
2
1
= x
1
− 2x
1
= 1.
Repetindo o processo, obtemos, x
n
= (−1)
n
, n = 1, 2, . . . , que por sua vez ´e uma seq¨uˆencia
divergente.
Portanto, se x
0
for tomado na fronteira da B(x
∗
, σ) a seq¨uˆencia gerada pelo m´etodo de
Newton inexato diverge. Conseq ¨uentemente, neste caso σ ´e o maior raio de convergˆencia
poss´ıvel.
Referˆencias Bibliogr´aficas
[1] J.E.Dennis, R.B.Schnabel, Numerical methods for unconstrained optimization and
nonlinear equations, Prentice-Hall, Englewood Cliffs, NJ, 1983.
[2] J.M.Ortega, W.C.Rheinboldt, Iterative Solution of Nonlinear Equations in Several
Variables, Academic Press, New York,1970.
[3] R.S.Dembo, S.C.Eisenstat,T.Steihaug, Inexact Newton methods, SIAM.Numer.Anal.
19 (1982) 400-408.
[4] K.R.Jackson, The numerical solution of large systems of stiff IVPs for ODEs, Appl.
Numer.Math. 20 (1996) 5-20.
[5] L.V.Kantorovich, G.P.Akilov, Functional Analysis, second ed., Pergamon Press, Ox-
ford, 1982.
[6] R.Kress, Numerical Analysis, Springer, New York, 1998.
[7] J.M.Martinez, L.Qi, Inexact Newton methods for solving nonsmooth equations, J.
Comput. Appl. Math. 60 (1995) 127-145.
[8] B.Morini, Convergence behaviour of inexact Newton methods, Math. Comp.68 (1999)
1605-1613.
[9] X.Wang, Convergence of Newton methods and uniqueness of the solution of equations
in Banach space, IMA J. Numer. Anal. 20 (2000) 123-134.
[10] C.Jinhai, L.Weiguo, Convergence behaviour of inexact Newton methods under weak
Lipschtz condition, Appl.Math.Comput. 191 (2006) 143-164.
49
50
[11] B.T.Polav, Newton’s method and its use in optimization. To appear in European
Journal of Operational Research (2006). doi 10.1016/j.ejor.2005.06.076.
[12] L.V.Kantorovich, Principe of majorants and Newton’s method Doklady AN SSSR,
76, 1(1951), pp 104-144.
[13] E.L.Lima, Curso de an´alise - Volume 1. IMPA, 12
a
edi¸c˜ao, 2007.
[14] E.L.Lima, Curso de an´alise - Volume 2. IMPA, 9
a
edi¸c˜ao, 2006.
[15] J.L.Boldrini,
´
Algebra Linear I, Harper& Row do Brasil, S˜ao Paulo, 1980.
[16] J.B.Hiriart-Urruty, C. Lemar´echal, Convex analysis and minimization algorithms I
and II, Springer-Verlag (1993).
[17] R.T.Rockafellar, Convex analysis, Princeton University Press, Princeton, 1970.
[18] J.V.Tiel, Convex analysis an introductory text, Royal Netherlands Meteorological
Institute, 1984.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
