View of Newton's method in Riemannian manifolds

(1)

Rev. Anal. Num´er. Th´eor. Approx., vol. 37 (2008) no. 2, pp. 119–125 ictp.acad.ro/jnaat

NEWTON’S METHOD IN RIEMANNIAN MANIFOLDS

IOANNIS K. ARGYROS^∗

Abstract. Using more precise majorizing sequences than before [1], [8], and under the same computational cost, we provide a finer semilocal convergence analysis of Newton’s method in Riemannian manifolds with the following advantages: larger convergence domain, finer error bounds on the distances involved, and a more precise information on the location of the singularity of the vector field.

MSC 2000. 65H10, 65B05, 65G99, 47H17, 49M15.

Keywords. Newton’s method, Riemannian manifold, local/semilocal convergence, singularity of a vector field, Newton-Kantorovich method.

1. INTRODUCTION

We refer the reader to [1], [5], [7] for some of the concepts introduced but not detailed here.

Let X be a C¹ vector field defined on a connected, complete and finite-di- mensional Riemannian manifold (M, g). In this study we are concerned with the following problem:

(1.1) find p^∗ ∈M such that X(p^∗) =o∈T_p^∗M.

A point p^∗ satisfying (1.1) is called a singularity ofX.

The most popular method for generating a sequence{p_n} (n≥0) approxi- mating p^∗ is undoubtedly Newton’s method, described here as follows:

Assume there exists an initial guessp₀∈M such that the covariantX⁰(p₀) of X atp0 given by

(1.2) X⁰(p)v:=∇_vX(p) = (∇_yX)(p), v∈TpM,

is invertible, atp=p0, for each pair of continuously differentiable vector fields X,Y where the vector field∇_yX stands for the covariant derivative ofXwith respect toY.

Define the Riemannian-Newton method by

(1.3) pn+1 = exp_p

n[−X⁰(pn)⁻¹X(pn)], where exp_p:TpM →M is the exponential map at p.

∗Cameron university, Department of Mathematics Sciences, Lawton, OK 73505, USA, e-mail: [email protected].

(2)

A survey of local as well as semilocal convergence results for method (1.3) can be found in [1]–[10] and the references there.

Here we are motivated by optimization considerations and the recent excel- lent study [1] of the Riemannian analogue of the property used by Zabreijko and Nguen [10].

In particular we show:

Under weaker hypotheses and the same computational cost finer error bounds on the distances d(pn+1, pn), d(pn, p^∗) (n ≥ 0) and a more precise information on the location of the solution p^∗ are obtained.

All the above advantages are achieved because we use more precise error estimates on the distances involved than in [1] along the lines of our relevant works for Newton’s method for solving nonlinear equations on Banach spaces [2]–[6].

In Section 2 we cover the local whereas in Section 3 we study the semilocal convergence of method (1.3).

2. LOCAL CONVERGENCE ANALYSIS OF METHOD (1.3)

We need the definition [1], [5]:

Definition 2.1. Let G2(p0, r) denote the class of all the piecewise geodesic curves c: [0, T]→M which satisfy:

(a) c(0) =p₀ and the length of c is no greater thanr;

(b) there exists τ ∈ (0, T) such that c_[0,τ] is a minimizing geodesic and c

[τ,T] is a geodesic.

We can now introduce a Lipschitz as well as a center-Lipschitz-type conti- nuity of X⁰:

Let R >0. We suppose there exist continuous and nondecreasing functions

`₀, `: [0, R]→[0,+∞) such that: for every r∈[0, R] andc∈G₂(p₀, r),

X⁰(p₀)⁻¹P_c,b,0X⁰(c(b))−P_c,0,0X⁰(c(0))

p0 ≤`₀(r) Z b

0

|˙c|, 0≤b, (2.1)

X⁰(p₀)⁻¹P_c,b,0X⁰(c(b))−P_c,a,0X⁰(c(a))

p0 ≤`(r) Z b

a

|c|,˙ 0≤a≤b,

(2.2) where

(2.3) P_c,t,0T(c(t)) =T(c(0)) + Z t

0

P_c,s,0T⁰(c(s)) ˙c(s)ds.

Without loss of generality we assume `₀(r)>0, `(r)>0 on (0, R].

Remark 2.2. In general

(2.4) `₀(r)≤`(r), r∈[0, R]

(3)

holds and _`^`(r)

0(r) can be arbitrarily large [3]–[6]. It is convenient to define pa- rameter

(2.5) η=|X⁰(p₀)⁻¹X(p₀)|_p₀, functions v, w: [0, R]→[−∞,+∞) by

w(r) = η−r+ Z _r

0

(r−s)`(s)ds, (2.6)

v(r) = −1 +`₀(r) (2.7)

and iterations {t_n},{r_n}(n≥0) by

t₀= 0, t₁=η, t_n+1 = t_n−^w(t_v(tⁿ⁾

n) , (2.8)

r₀= 0, r_n+1 = r_n−_w^w(r0(rⁿn⁾)

(2.9)

for all n≥0.

Let us consider the assumption: the functionwgiven by (2.6) has a unique zero r^∗ in [0, R] with

(2.10) w(R)≤0.

We showed in [2] (see also [6], [7]):

Proposition2.3. Under hypothesis(2.10)iterations{t_n},{s_n}(n≥0)are well defined, monotonically increasing and convergent to t^∗, r^∗, respectively, with

(2.11) t^∗ ≤r^∗.

Moreover, the following estimates hold for all n≥0 tn ≤ rn,

(2.12)

t_n+1−t_n ≤ r_n+1−r_n, (2.13)

and

(2.14) t^∗−tn≤r^∗−rn.

Furthermore if (2.4) holds as a strict inequality so do (2.12) and (2.13) for n≥1. Since we shall show both{t_n}, {r_n}are majorizing sequences for{p_n}, it follows by Proposition 2.3 that the claims made in the introduction for the local convergence of method (1.3) hold true.

We can now state the main local convergence result for method (1.3) which improves the corresponding Theorem 3.1 in [1, p. 8]:

Theorem 2.4. Under hypotheses (2.1), (2.2)and (2.10) the following hold true:

(a) the vector field X admits a unique singularity p^∗ in U(p₀, R) = {p ∈ X | kp −p₀k ≤ R} which belongs to U(p₀, t^∗). If `₀(t^∗) < 0 then X⁰(p^∗)∈GL(T_p^∗M).

(4)

(b) Sequence {p_n} (n ≥0) generated by method (3) is well defined, pn ∈ U(p0, tn) for all n≥0, and lim

n→∞pn=p^∗. (c) The following estimates hold true for alln≥0:

(2.15) d(p_n+1, p_n)≤ |X⁰(p_n)⁻¹X(p_n)|_p_n ≤t_n+1−t_n≤r_n+1−r_n, and

(2.16) d(p_n, p^∗)≤t^∗−t_n≤r^∗−r_n.

Proof. Uses the more accurate (i.e. the one really needed) condition (2.1) in- stead of condition (2.2) used in [1] for the computation of the inversesX⁰(pn)⁻¹ (n≥0). The rest of the proof is identical to [1] and is omitted.

Remark 2.5.

(a) If `0(r) = `(r) our Theorem 2.4 reduces to Theorem 3.1 in [1]. Oth- erwise (see (2.4)) it is an improvement over it as already shown in Proposition 2.3. Note also that the rest of the bounds obtained in Theorem 3.1 in [1] (see parts (iv)-(v) of Theorem 3.1) hold true with {t_n}replacing sequence{r_n}there but we decided not to include those bounds here to avoid repetitions.

(b) Theorem 2.4 remains valid for a C¹ vector field X: D ⊂ M → T M which is defined only on an open subsetDofMprovidedU(p₀, R)⊆D [1], [5], [7].

(c) It follows from the proof of the theorem that the sharper (than {t_n}) scalar{t_n}(n≥0) given by

(2.17)

t₀ = 0, t₁ =η, t_n+2=t_n+1+₁₋_` ¹

0(tn+1)

Z 1 0

`(t_n+t(t_n+1−t_n))(t_n+1−t_n)dt(n≥0), is also a majorizing sequence for{p_n} (n≥0).

Sufficient convergence conditions for sequence (1.27) which are weaker than (2.10) have already been given in [3]–[7]. Note that

tn ≤ tn, (2.18)

t_n+1−t_n ≤ t_n+1−t_n, (2.19)

t^∗−t_n ≤ t^∗−t_n, (2.20)

and

(2.21) t^∗ ≤t^∗.