View of Enlarging the convergence ball of Newton's method on Lie groups

J. Numer. Anal. Approx. Theory, vol. 44 (2015) no. 1, pp. 11–24 ictp.acad.ro/jnaat

ENLARGING THE CONVERGENCE BALL OF NEWTON’S METHOD ON LIE GROUPS

IOANNIS K. ARGYROS^∗and SA¨ID HILOUT^„

Dedicated to prof. I. P˘av˘aloiu on the occasion of his 75th anniversary

Abstract. We present a local convergence analysis of Newton’s method for approximating a zero of a mapping from a Lie group into its Lie algebra. Using more precise estimates than before [55, 56] and under the same computational cost, we obtain a larger convergence ball and more precise error bounds on the distances involved. Some examples are presented to further validate the theoretical results.

MSC 2010. 65G99, 65J15, 47H17, 49M15, 90C90.

Keywords. Newton’s method, Lie group, Lie algebra, Riemannian manifold, convergence ball, Kantorovich hypothesis.

1. INTRODUCTION

In this paper, we are concerned with the problem of approximating a zero x^? of C¹-mappingF : G−→Q, where Gis a Lie group andQthe Lie algebra of G that is the tangent space TeGof G ate, equipped with the Lie bracket [., .] : Q×Q−→Q[7, 21, 28, 29, 53].

The study of numerical algorithms on manifolds for solving eigenvalue or optimization problems on Lie groups [1]–[12], [33]–[36], [54]–[57] is very im- portant in Computational Mathematics. Newton-type methods are the most popular iterative procedures used to solve equations, when these equations contain differentiable operators. The study about convergence matter of New- ton’s method is usually centered on two types: semilocal and local conver- gence analysis. The semilocal convergence matter is, based on the information around an initial point, to give criteria ensuring the convergence of Newton’s method; while the local one is, based on the information around a solution, to find estimates of the radii of convergence balls. There is a plethora of studies on the weakness and/or extension of the hypothesis made on the underlying operators; see for example (cf. [7, 11, 16] and references theiren). A local as

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

„Poitiers University, Laboratoire de Math´ematiques et Applications, Bd. Pierre et Marie Curie, T´el´eport 2, B.P. 30179, 86962 Futuroscope Chasseneuil Cedex, France, e-mail:

[email protected].

well as a semilocal convergence of Newton-type methods has been given by several authors under various conditions [2]–[58]. Recently in [15], we pre- sented a finer semilocal convergence analysis for Newton’s method than in earlier studies [7, 32, 34, 36, 54, 55, 56].

Newton’s method with initial point x0 ∈Gwas first introduced by Owren and Welfert [43] in the form

(1.1) xn+1=xn·exp (−dF_x⁻¹_n F(xn)) for each n= 0,1, . . . .

Newton’s method is undoubtedly the most popular method for generating a sequence {x_n} approximating x^? [7, 11, 15, 16, 32, 34, 36], [54]–[56]. In the present paper we establish a finer local convergence analysis with the advantages (A_l):

(i) Larger convergence ball;

and

(ii) Tighter error bounds on the distances involved.

The necessary background on Lie groups can be found in [7, 11, 15, 16] and the references therein. The paper is organized as follows. In Section 2, we present the local convergence analysis of Newton’s method. Finally, numerical examples are given in the concluding Section 3.

2. LOCAL CONVERGENCE ANALYSIS FOR NEWTON’S METHOD

We shall study the semilocal/local convergence of Newton’s method. In the rest of the paper we assume h·,·ithe inner product and k · kon Q. As in [56]

we define a distance on Gforx, y∈Gas follows:

m(x, y) = inf _k

P

i=1

kzik: there exist k≥1 andz1,· · · , zk ∈Q (2.1)

such that y=x·exp z₁· · ·expz_k

.

By convention inf ∅ = +∞. It is easy to see that m(·,·) is a distance on G and the topology induced is equivalent to the original one on G. Let w∈ G and r >0, we denote by

U(w, r) ={y∈G : m(w, y)< r}

the open ball centered at wand of radius r. Moreover, we denote the closure ofU(w, r) byU(w, r). Let alsoL(Q) denotes the set of all linear operators on Q.

We need the definition of Lipschitz continuity for a mapping.

Definition 2.1. Let M : G−→L(Q), x^? ∈Gand r >0. We say that M satisfies the L-Lipschitz condition on U(x^?, r) if

(2.2) kM(x·exp u)−M(x)k≤L kuk

holds for any u∈Q andx∈U(x^?, r) such thatkuk+m(x, x^?)< r .

It follows from (2.2) that there exists L? such that

(2.3) kM(x·exp u)−M(x^?)k≤L?(kuk+m(x, x^?)) holds for any u∈Q andx∈U(x^?, r) such thatkuk+m(x, x^?)< r.

We then say M satisfies the L_?-center Lipschitz condition at x^? ∈ G on U(x^?, r). Note that ifM satisfies theL-Lipschitz condition onU(x^?, r), then it also satisfies theL_?-center Lipschitz condition at x^? ∈GonU(x^?, r). Clearly,

(2.4) L? ≤L

holds in general andL/L? can be arbitrarily large [4]–[16].

Let us show that (2.2) indeed implies (2.3). If (2.2) holds, then for x=x^? there existsK ∈(0, L] such that

kM(x^?·expu)−M(x^?)k≤K kuk for any u∈Q such that kuk< r.

There exist k ≥1 andz₀, z₁,· · · , z_k ∈Q such that x =x^?·expz₀· · ·expz_k. Let y0 =x^?,yi+1 =yi·exp ui,i= 0,1,· · ·, k. Then, we have that x =y_k+1. We can write the identity

M(x·exp u)−M(x^?) =

= (M(x·expu)−M(x)) + (M(x)−M(x^?))

= (M(x·expu)−M(x)) + (M(y_k·expu_k)−M(y_k)) + (M(y_k)−M(x^?))

= (M(x·expu)−M(x)) + (M(y_k·expu_k)−M(y_k)) +(M(yk−1·exp uk−1)−M(x^?))

= (M(x·expu)−M(x)) + (M(y_k·expu_k)−M(y_k)) +· · ·+ +(M(y1·exp u1)−M(y1)) + (M(x^?·exp u0)−M(x^?)).

Using (2.2) and the triangle inequality, we obtain in turn that kM(x·exp u)−M(x^?)k≤

≤kM(x·expu)−M(x)k+kM(yk·expuk)−M(yk)k+· · · +kM(y₁·expu₁)−M(y₁)k+kM(x^?·exp u₀)−M(x^?)k

≤L(kuk+ku_k k+· · ·+ku₁ k) +K ku₀k

=L(kuk+ku_k k+· · ·+ku₀ k) + (K−L) ku₀ k

≤L(kuk+kuk k+· · ·+ku0 k), which implies (2.3).

We need a Banach type lemma on invertible mappings.

Lemma 2.2. Suppose that dF_x⁻¹? exists and let 0 < r ≤ _L¹

?. Suppose dF_x⁻¹? dF satisfies the L?-center Lipschitz condition at x^? ∈ G on U(x^?, r);

for x ∈ U(x^?, r), there exist k ≥ 1 and z₀, z₁,· · · , z_k ∈ Q, such that x = x^?·expz0· · ·expz_k and

k

P

i=0

kzi k< r. Then, linear mapping dF_x⁻¹ exists and

(2.5) kdF_x⁻¹dFx^? k≤

1−L?

k

P

i=0

kzi k ⁻¹

.

Proof. Let y_k = x^? ·expz0 ·expz1 · · ·exp zk−1. Then, we deduce y_k ∈ U(x^?, r), since

k−1

P

i=0

k zi k< r. Note that x = yk·expzk. Using (2.3) for M =dF_x⁻¹? dF, we get in turn

(2.6)

kdF_x⁻¹? (dF_x−dF_x^?)k≤L_?(kz_kk+m(y_k, x^?))≤L_? ^Pk

i=0

kz_ik< L_?r≤1.

It follows from (2.6) and the Banach lemma on invertible operators [7], [32]

thatdF_x⁻¹exists and (2.5) holds. That completes the proof of Lemma 2.2.

Next, we study the convergence domain of Newton’s method around a zero x^? of mapping F. First from Lemma 2.3 until Corollary 2.9, we present the local result for Newton’s method when G is an Abelian group. Then, the corresponding local results follow whenGis not necessarily an Abelian group.

Lemma 2.3. Let G be an Abelian group and 0< r≤ _L¹

?. Let F : G−→Q be a C¹-mapping. Let x^? ∈G be a zero of mapping F. Suppose dF_x⁻¹? exists and let L? >0; there exist j≥1 and z1, z2,· · · , zj ∈Q such that

(2.7) x0=x^?·expz1· · ·expzj f or

j

P

i=1

kzi k< r;

dF_x⁻¹? dF satisfies the L?-center Lipschitz condition at x^? on U(x^?, r). Then, linear mapping dF_x⁻¹₀ exists and

(2.8) kdF_x⁻¹₀ F(x0)k≤

2+L?

j

P

i=1

kz_ik _j

P

i=1

kz_ik

2

1−L?

j

P

i=1

kzi k

.

Proof. Using hypothesisdF_x⁻¹? dF satisfies theL_?-center Lipschitz condition atx^? on U(x^?, 1

L?

), we have that

(2.9) kdF_x⁻¹? (dFx·expu−dF_x^?)k≤L_?(kuk+m(x, x^?))

for all u ∈ Q, x ∈ U(x^?, r) such that k u k +m(x, x^?) < r. Let z = z₁ + z2+· · ·+zj. Then, since G is an Abelian group, expz1·expz2· · ·expzj = exp (z₁+z₂+· · ·+z_j) = expz, so, we can writex₀ =x^?·expz. It then follows from Lemma 2.2 that dF_x⁻¹₀ exists and

(2.10) kdF_x⁻¹₀ dFx^?)k≤

1−L?

j

P

i=1

kzi k ⁻¹

. We also have the following identity

(2.11)

F(x0) = F(x^?·expz)−F(x^?)

= Z 1

0

dF_x^?_{·exp (tz)}z dt= Z 1

0

(dF_x^?_{·exp (tz)}−dF_x^?)z dt+dF_x^?z.

In view of (2.9) and (2.11), we get that (2.12)

kdF_x⁻¹? F(x0)k ≤ Z 1

0

kdF_x⁻¹? (dF_x^?·exp (t z)−dFx^?)k kzk dt+kzk

≤ Z 1

0

kL?(t kzk) kzk dt+kzk

≤

L?

2 j

P

i=1

kzi k+1 _j

P

i=1

kzi k. Moreover, by (2.10) and (2.12), we obtain that

kdF_x⁻¹₀ F(x₀)k≤kdF_x⁻¹₀ dF_x^? k kdF_x⁻¹? F(x₀)k≤

2+L?

j

P

i=1

kzi k _j

P

i=1

kzi k

2

1−L?

j

P

i=1

kz_ik

.

That completes the proof of Lemma 2.3.

Remark2.4. The proof of Lemma 2.3 reduces to [56, Lemma 3.2] ifL? =L.

Otherwise (i.e., if L? < L) it constitutes an improvement. We have also included the proof although similar to the corresponding one in [56] because it is not straightforward to see thatL? can replace L in the derivation of the crucial estimate (2.8). Note also that (2.9) can holds for some L¹_? ∈ (0, L_?].

If L¹_? < L?, then according to the proof of Lemma 2.3, L¹_? can replace L? in (2.8).

Let us define parameter α forβ = ^L_L^? by

(2.13) α=





 4

√

1+3β−(1+β)

β(1−β) , if L? 6=L

1, if L_? =L.

Then, it is can easily be seen that

(2.14) α≥1.

We have the local convergence result for Newton’s method.

Theorem2.5. LetGbe an Abelian group. Let0< r≤ ₄^α_L, whereαin given in (2.13). LetF : G−→Qbe aC¹-mapping. Suppose there existsx^? ∈Gsuch that F(x^?) = 0, dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition onU(x^?,_1−L^3r

?r). Then, sequence {x_n}(n≥0) generated by Newton’s method starting at x0 ∈U(x^?, r)is well defined, remains inU(x^?,_1−L^3r

?r) for alln≥0 and converges to a zero y^? of mapping F such that

m(x^?, y^?)< _1−L^3r

?r.

Proof. It follows from hypothesis x0 ∈ U(x^?, r) that there exist j ≥ 1 and z1, z2,· · ·, zj ∈ Q such that (2.7) holds. If dF_x⁻¹? dF is L-Lipschitz on U(x^?,_1−L^3r

?r), then it is L_?-center Lipschitz atx^? on U(x^?,_1−L^3r

?r). Note also

that ₄^α_L ≤ _L¹

? by the choice of α. It follows from Lemma 2.3 that linear mappingdF_x⁻¹₀ exists and

(2.15) η=kdF_x⁻¹₀ F(x0)k≤

2+L?

j

P

i=1

kz_i k _j

P

i=1

kz_ik

2

1−L?

j

P

i=1

kzi k

.

Set

L= ^L

1−L_? j

P

i=1

kz_ik

and r = ^(2+L_1−L^?r)r

?r .

We shall show mappingdF_x⁻¹₀ dF satisfies theL-Lipschitz condition onU(x₀, r).

Indeed, let x ∈U(x0, r) and z∈Q be such that k zk +m(x0, x) < r. Then, we get that

kzk+m(x, x^?)<kzk+m(x, x0) +m(x0, x^?)< r+r≤ _1−L^3r

?r. Using Lemma 2.2, we have that

kdF_x⁻¹₀ (dFx·expz−dFx)k ≤ kdF_x⁻¹₀ dFx^? k kdF_x⁻¹? (dFx·expz−dFx)k

≤ ^Lkzk

1−L?

j

P

i=1

kz_ik

=L kzk.

Set

(2.16) h=L η and r₁ = ^2η

1+

√

1−2h

≤2η.

Then, by (2.15), we obtain that

(2.17) r1 ≤

2+L?

j

P

i=1

kz_ik _j

P

i=1

kz_ik

1−L?

j

P

i=1

kzi k

≤ ^(2+L_1−L^?r)r

?r =r and

(2.18) h≤ ^(2+L_{2 (1−L}^{?r)L r}

?r)² ≤ ¹₂,

by the choice of r and α. By standard majorization techniques [7], {x_k} converges to some zeroy^? of mappingF andm(x0, y^?)≤r1. Furthermore, we obtain that

m(x^?, y^?)≤m(x^?, x0) +m(x0, y^?)≤r+r1 ≤r+r≤ _1−L^3r

?r.

That completes the proof of Theorem 2.5.

The proofs of remaining results in this Section are omitted, since they can be obtained from the corresponding ones in [56].

Corollary 2.6. Let G be an Abelian group. Let F : G −→ Q be a C¹-mapping. Let x^? ∈ G be a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?). Let also x0 ∈ U(x^?,₄^α_L). Then, sequence{x_n} (n≥0) generated by Newton’s method start- ing at x₀ is well defined, remains in U(x^?,₄^α_L) for all n≥0 and converges to a zero y^? of mapping F such that m(x^?, y^?)< _L¹

?. We denote in the following Corollary

B(0, r) ={z∈Q :kzk< r}.

Corollary 2.7. Let G be an Abelian group. Let F : G −→ Q be a C¹-mapping. Let x^? ∈ G be a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?). Let also x0 ∈ U(x^?,_L¹

?). Let σ be the maximal number such that U(e, σ) ⊆exp (B(0,_L¹

?)).

Set r = minⁿ_3+L^σ

?σ, ₄^α_L^o and N(x^?, r) = x^?exp(B(0, r)). Then, sequence {x_n} (n ≥ 0) generated by Newton’s method starting at x₀ ∈ N(x^?, r) con- verges tox^?.

Corollary 2.8. Let G be an Abelian group. Let F : G −→ Q be a C¹-mapping, where G is a compact connected Lie group equipped with a bi- invariant Riemannian metric. Letx^? ∈Gbe a zero of mappingF and0< r <

α

4L. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_1−L^3r

?r). Let also x0 ∈U(x^?, r). Then, sequence {x_n} (n≥0) generated by Newton’s method starting at x0, remains inU(x^?,_1−L^3r

?r) for all n≥0 and converges to x^?.

Corollary 2.9. Let G be an Abelian group. Let F : G −→ Q be a C¹-mapping, where G is a compact connected Lie group equipped with a bi- invariant Riemannian metric. Let x^? ∈ G be a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?).

Let also x0 ∈U(x^?,₄^α_L). Then, sequence {x_n} (n≥0) generated by Newton’s method starting at x0, remains in U(x^?,₄^α_L) for all n ≥ 0 and converges to x^?.

Lemma 2.10. Let 0 < r ≤ _L¹. Let F : G −→ Q be a C¹-mapping. Let x^? ∈ G be a zero of mapping F. Suppose dF_x⁻¹? exists; there exist j ≥ 1 and z₁, z₂,· · · , z_j ∈ Q such that x₀ = x^? ·expz₁· · ·expz_j for

j

P

i=1

k z_i k< r and dF_x⁻¹? dF satisfies the L-Lipschitz condition atx^? onU(x^?, r). Then, the following assertions hold

(i)

kdF_x⁻¹? (dF_x^?·expz−dF_x^?)k≤K_? kzk for each z∈Q withkzk< r and some K_? ∈(0, L].

(ii)

kdF_x⁻¹? (F⁰(x0)−F⁰(x^?))k≤L? j

P

i=1

kzi k f or some L?∈(0, L].

(iii) Linear mappingdF_x⁻¹₀ exists and

kdF_x⁻¹₀ F(x0)k≤

2+L j

P

i=1

kz_i k _j

P

i=1

kz_i k

2

1−L?

j

P

i=1

kz_i k .

Proof. (i) This assertion follows from the hypothesis thatdF_x⁻¹? dF sat- isfies theL-Lipschitz condition atx^? on U(x^?, r).

(ii) Let w₀ =x^?, w_i+1 =w_i·expz_i+1, i= 1,2,· · ·, j−1. Then, we have wj = wj−1·expzj = x0. Using the L-Lipschitz condition, we get in turn that

kdF_x⁻¹? (dFwj−dFx^?)k

≤kdF_x⁻¹? (dF_wj−1·expzj−dF_wj−1)k+· · ·+kdF_x⁻¹? (dF_w1·expz2−dF_w1)k+ kdF_x⁻¹? (dFx^?·expz1 −dFx^?)k

≤L(kz_j k+· · ·+kz₂k) +K_? kz₁ k

=L(kzj k+· · ·+kz1 k) + (K_?−L) kz1 k≤L(kzj k+· · ·+kz1 k) which shows (ii).

(iii) We have by (ii) that

kdF_x⁻¹? (dFx0 −dFx^?)k≤L?(kzj k+· · ·+kz1 k)≤L r <1.

Hence,dF_x⁻¹₀ exists and (2.19) kdF_x⁻¹₀ dF_x^? k≤

1−L_?

j

P

i=1

kz_i k −1

. We have that

dF_x⁻¹? (F(w_i)−F(wi−1)) =dF_x⁻¹?

Z 1 0

dF_{wi−1·exp (t zi)}z_idt

= Z 1

0

dF_x⁻¹? (dF_{wi−1·exp (t zi)}−dF_x^?)z_idt+z_i. Hence, we get that

kdF_x⁻¹? (dF_{wk−1·exp (zk)} −dF_wk−1)k≤L kz_kk for each k= 1,2,· · ·, j.

Therefore, we obtain that kdF_x⁻¹? (dF_wi−1·exp (t z_i)−dFx^?)k ≤

≤ ^i−1P

k=1

kdF_x⁻¹? (dF_{wk−1·exp(zk)}−dF_wk−1)k+kdF_x⁻¹? (dF_{wi−1·exp(twi)}−dF_wi−1)k

≤L

i−1

P

k=1

kz_kk+Ltkz_ik.

We have thatF(x₀) =

j

P

i=1

(F(wi)−F(wi−1)). That is, we can get

(2.20)

kdF_x⁻¹? F(x₀)k

≤

j

P

i=1

Z ₁

0

kdF_x⁻¹? (dF_{wi−1·exp (t zi)}−dFx^?)k kzi k dt+kzik

≤

j

P

i=1

Z ₁

0

L _i−1

P

k=1

kz_kk+t kz_ik

kz_ik dt+kz_ik

≤

L 2

j

P

i=1

kz_i k+1 _j

P

i=1

kz_i k.

The result now follows from (2.19), (2.20) and

kdF_x⁻¹₀ F(x₀)k≤kdF_x⁻¹₀ dF_x^?k kdF_x⁻¹? F(x₀)k≤

2+L j

P

i=1

kzi k _j

P

i=1

kzi k

2

1−L_? j

P

i=1

kz_ik .

The proof of Lemma 2.10 is complete.

Let us define parameter δ by

(2.21) δ=

( 4

√2 (1+β)−(1+β)

1−β² , if L_? 6=L

1, if L_? =L.

We have that

δ ≥1.

Theorem 2.11. Let 0 < r ≤ ₄^δ_L, where δ in given in (2.21). Let F : G−→Q be a C¹-mapping. Suppose there exists x^? ∈G such that F(x^?) = 0, dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?, R =

3+(L−L_?)r

1−L?r r). Then, sequence {x_n} (n ≥ 0) generated by Newton’s method starting at x₀ ∈ U(x^?, r) is well defined, remains in U(x^?, R) for all n ≥ 0 and converges to a zero y^? of mapping F such thatm(x^?, y^?)< R.

Proof. The proof is similar to the proof of Theorem 2.5. Note thatr in the proof of Theorem 2.5 is replaced by

r = ^{(2+L r)}_1−L ^r

?r

and η satisfies the new condition

η≤

2+L j

P

i=1

kzik _j

P

i=1

kzik

2

1−L_? j

P

i=1

kzi k .

The proof of Theorem 2.11 is complete.

Corollary 2.12. Let F : G−→Qbe aC¹-mapping. Letx^?∈Gbe a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?). Let also x0 ∈ U(x^?,₄^δ_L). Then, the conclusions of Corollary 2.6 hold.

Corollary 2.13. Let F : G−→Qbe aC¹-mapping. Letx^?∈Gbe a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?). Let also x₀ ∈ U(x^?,_L¹

?). Let σ and N(x^?, r) as in Corollary 2.7. Set r= minⁿr0, r1, ₄^δ_L^o, where

r₀=







−(L?+3L)+

√

(L?+3L)²+4L(L−L?)

2L(L−L?) , if L? 6=L

1

4L, if L? =L

and

r₁=







−(3+σ L?)+√

(3+σ L?)²+4σ(L−L?)

2 (L−L?) , if L?6=L

σ

3+σ L, if L_?=L.

Then, sequence {x_n} (n≥0) generated by Newton’s method starting at x₀ ∈ N(x^?, r) converges to x^?.

Corollary 2.14. Let F : G −→ Q be a C¹-mapping, where G is a com- pact connected Lie group equipped with a bi-invariant Riemannian metric. Let x^? ∈ G be a zero of mapping F and 0 < r < ₄^δ_L. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies theL-Lipschitz condition on U(x^?, R), whereR is defined in Theorem2.11. Let alsox0∈U(x^?, r). Then, sequence{x_n} (n≥0) generated by Newton’s method starting at x₀, remains in U(x^?, R) for all n ≥ 0 and converges to x^?.

Corollary 2.15. Let F : G −→ Q be a C¹-mapping, where G is a com- pact connected Lie group equipped with a bi-invariant Riemannian metric. Let x^? ∈ G be a zero of mapping F. Suppose dF_x⁻¹? exists and dF_x⁻¹? dF satisfies the L-Lipschitz condition on U(x^?,_L¹

?). Let also x₀ ∈ U(x^?,₄^δ_L). Then, se- quence {x_n} (n≥0) generated by Newton’s method starting at x₀, remains in U(x^?,₄^δ_L) for all n≥0 and converges tox^?.

Remark 2.16. (a) The local results reduce to the corresponding ones in [56] if L =L_?. Otherwise (i.e., if L_? < L), they constitute an improvement under the same computational cost with advantages as already stated in the Introduction of this study. Note also thatα >1,δ >1 ifL? < Landα−→ ∞, δ −→ ∞if _L^L

? −→ ∞.

(b) The local results if G is an Abelian group are weaker and tighter than the ones when G is not necessarily an Abelian group. We have for example thatr < r,δ < α, _1−L^3r

?r < Rand the upper bound onη is smaller if L_? < L.

(c) It is obvious that finer results can be immediately obtained if similar conditions as the semilocal case (see [15, Section 1, L_? instead L₀]) are used

instead of Kantorovich condition for L? < L. However, we decided to leave this part of analysis to the motivated reader. We refer the reader to [14] for such results involving nonlinear equations in a Banach space setting. We also refer the reader to [7, 11, 15, 16] for examples.

3. NUMERICAL EXAMPLES

In this Section we present two numerical examples in the more general setting of a nonlinear equation on a Hilbert space where L_?< L.

Example 3.1. Let X =Y =R, x^? = 0. Define F by F(x) = −d₂sin 1 + d₁x +d₂ sin e^d3x, where d₁, d₂, d₃ are given real numbers. We have that F(x^?) = 0. Moreover, ifd3 is sufficiently large andd2 sufficiently small,L/L?

can be arbitrarily large.

Example 3.2. Let X = Y = R³, D = U(0,1) and x^? = (0,0,0). Define functionF on D forw= (x, y, z) by

(3.1) F(w) = (e^x−1,^e−1₂ y²+y, z).

Then, the Fr´echet derivative ofF is given by F⁰(w) =





e^x 0 0

0 (e−1)y+ 1 0

0 0 1





Notice that we have F(x^?) = 0, F⁰(x^?) = F⁰(x^?)⁻¹ = diag{1,1,1} and L? = e−1< L= e.

REFERENCES

[1] Absil, P.–A., Baker, C.G.andGallivan, K.A.,Trust-region methods on Riemann- ian manifolds, Found. Comput. Math.,7(2007), pp. 303–330.

[2] Adler, R.L., Dedieu, J.P., Margulies, J.Y., Martens, M.andShub, M.,Newton’s method on Riemannian manifolds and a geometric model for the human spine, IMA J.

Numer. Anal.,22(2002), pp. 359–390.

[3] Alvarez, F., Bolte, J.andMunier, J.,A unifying local convergence result for New- ton’s method in Riemannian manifolds, Found. Comput. Math.,8(2008), pp. 197–226.

[4] Argyros, I.K.,An improved unifying convergence analysis of Newton’s method in Rie- mannian manifolds, J. Appl. Math. Comput.,25(2007), pp. 345–351.

[5] Argyros, I.K.,On the local convergence of Newton’s method on Lie groups, Pan Amer.

Math. J.,17(2007), pp. 101–109.

[6] Argyros, I.K.,A Kantorovich analysis of Newton’s method on Lie groups, J. Concrete Appl. Anal., 6(2008), pp. 21–32.

[7] Argyros, I.K.,Convergence and Applications of Newton-type Iterations, Springer Ver- lag Publ., New York, 2008.

[8] Argyros, I.K.,Newton’s method in Riemannian manifolds, Rev. Anal. Num´er. Th´eor.

Approx.,37(2008), pp. 119–125.

[9] Argyros, I.K.,Newton’s method on Lie groups, J. Appl. Math. Comput., 31(2009), pp. 217–228.

[10] Argyros, I.K.,A semilocal convergence analysis for directional Newton methods, Math.

Comp. AMS,80(2011), pp. 327–343.

[11] Argyros, I.K., Cho, Y.J.and Hilout, S.,Numerical methods for equations and its applications, CRC Press/Taylor and Francis Group, New-York, 2012.

[12] Argyros, I.K. and Hilout, S., Newton’s method for approximating zeros of vector fields on Riemannian manifolds, J. Appl. Math. Comput.,29(2009), pp. 417–427.

[13] Argyros, I.K.andHilout, S.,Extending the Newton-Kantorovich hypothesis for solv- ing equations, J. Comput. Appl. Math.,234(2010), pp. 2993–3006.

[14] Argyros, I.K. and Hilout, S., Weaker conditions for the convergence of Newton’s method, J. Complexity,28(2012), pp. 364–387.

[15] Argyros, I.K.andHilout, S.,Extending the applicability of Newton’s method on Lie groups, Appl. Math. Comput., to appear.

[16] Argyros, I.K. andHilout, S.,Numerical methods in nonlinear analysis, World Sci- entific Publ., ISBN-13: 978-9814405829, to appear.

[17] Bayer, D.A.andLagarias, J.C.,The nonlinear geometry of linear programming. I.

Affine and projective scaling trajectories, Trans. Amer. Math. Soc.,314(1989), pp. 499–

526.

[18] Brockett, R.W.,Differential geometry and the design of gradient algorithms. Differ- ential geometry: partial differential equations on manifolds (Los Angeles, CA, 1990), pp. 69–92, Proc. Sympos. Pure Math.,54, Part 1, Amer. Math. Soc., Providence, RI, 1993.

[19] Chu, M.T.andDriessel, K.R.,The projected gradient method for least squares matrix approximations with spectral constraints, SIAM J. Numer. Anal.,27(1990), pp. 1050–

1060.

[20] Dedieu, J.P., Priouret, P.andMalajovich, G.,Newton’s method on Riemannian manifolds: Convariantαtheory, IMA J. Numer. Anal.,23(2003), pp. 395–419.

[21] Do Carmo, M.P.,Riemannian Geometry, Boston, Birkhauser, 1992.

[22] Edelman, A., Arias, T.A.andSmith, S.T.,The geometry of algorithms with orthog- onality constraints, SIAM J. Matrix Anal. Appl.,20(1999), pp. 303–353.

[23] Ezquerro, J.A. and Hern´andez, M.A., Generalized differentiability conditions for Newton’s method, IMA J. Numer. Anal.,22(2002), pp. 187–205.

[24] Ezquerro, J.A. and Hern´andez, M.A., On an application of Newton’s method to nonlinear operators with ω-conditioned second derivative, BIT,42(2002), pp. 519–530.

[25] Ferreira, O.P. and Svaiter, B.F., Kantorovich’s theorem on Newton’s method in Reimannian manifolds, J. Complexity,18(2002), pp. 304–329.

[26] Gabay, D.,Minimizing a differentiable function over a differential manifold, J. Optim.

Theory Appl.,37(1982), pp. 177–219.

[27] Guti´errez, J.M. andHern´andez, M.A.,Newton’s method under weak Kantorovich conditions, IMA J. Numer. Anal.,20(2000), pp. 521–532.

[28] Hall, B.C.,Lie groups, Lie algebras and representations. An elementary introduction, Graduate Texts in Mathematics,222, Springer-Verlag, New York, 2003.

[29] Helgason, S.,Differential geometry, Lie groups and symmetric spaces, Pure and Ap- plied Mathematics, 80, Academic Press, Inc. Harcourt Brace Jovanovich, Publishers, New York-London, 1978.

[30] Helmke, U. and Moore, J.B., Singular-value decomposition via gradient and self- equivalent flows, Linear Algebra Appl.,169(1992), pp. 223–248.

[31] Helmke, U. and Moore, J.B., Optimization and dynamical systems. With a fore- word by R. Brockett, Communications and Control Engineering Series. Springer-Verlag London, Ltd., London, 1994.

[32] Kantorovich, L.V.andAkilov, G.P.,Functional analysis in normed spaces, Perga- mon Press, New York, 1982.