On newton’s method for subanalytic equations

Ioannis K. Argyros$^\ast $ Santhosh George$^\S $

September 23, 2014.

$^\ast $Cameron University, Department of Mathematicsal Sciences, Lawton, OK 73505, USA, e-mail: ioannisa@cameron.edu.

$^\S $National Institute of Technology Karnataka, Department of Mathematical and Computational Sciences, India-575 025, e-mail: sgeorge@nitk.ac.in.

We present local and semilocal convergence results for Newton’s method in order to approximate solutions of subanalytic equations. The local convergence results are given under weaker conditions than in earlier studies such as [ 9 ] , [ 10 ] , [ 14 ] , [ 15 ] , [ 24 ] , [ 25 ] , [ 26 ] , resulting to a larger convergence ball and a smaller ratio of convergence. In the semilocal convergence case contravariant conditions not used before are employed to show the convergence of Newton’s method. Numerical examples illustrating the advantages of our approach are also presented in this study.

MSC. 65H10, 65G99, 65K10, 47H17, 49M15.

Keywords. Newton’s methods, convergence ball, local-semilocal convergence, subanalytic functions.

1 Introduction

In this study we are concerned with the problem of approximating a solution $x^\ast $ of the equation

\begin{equation} \label{1.1} F(x)=0,\end{equation}

where $F$ is a continuous mapping from a subset $D$ of $\mathbb {R}^n$ into $\mathbb {R}^n.$

Many problems in computational sciences and other disciplines can be brought in a form like (1) using mathematical modeling [ 3 ] , [ 7 ] , [ 8 ] , [ 9 ] , [ 14 ] , [ 16 ] , [ 17 ] , [ 22 ] , [ 24 ] – [ 28 ] . In general the solutions of equation (1) can not be found in closed form. Therefore iterative methods are used for obtaining approximate solutions of (1). In Numerical Functional Analysis, for finding solution $x^\ast $ of equation (1) is essentially connected to variants of Newton’s method. Newton’s method is defined by

\begin{equation} \label{1.2} x_{k+1}=x_k-F'(x_k)^{-1}F(x_k), \qquad \textnormal{for each}\, \, k=0,1,2,\ldots , \end{equation}

where $x_0$ is an initial point and $F$ is a continuously Fréchet differentiable function on $D$, i.e., $F$ is a smooth function.

The study about convergence matter of iterative procedures is usually based on two types: semi-local and local convergence analysis. The semi-local convergence matter is, based on the information around an initial point, to give conditions ensuring the convergence of the iterative procedure; while the local one is, based on the information around a solution, to find estimates of the radii of convergence balls. There exist many studies which deal with the local and semilocal convergence analysis of Newton’s methods (2) under various Lipschitz-type conditions on $F'.$ We refer the reader to [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 ] and the references therein for this type of results.

However, in many interesting applications $F$ is not a smooth function [ 3 ] , [ 7 ] , [ 8 ] , [ 23 ] , [ 24 ] , [ 26 ] , [ 28 ] . In particular, we are interested in the case when $F$ is a semismooth function. Then, we define Newton’s method

\begin{equation} \label{1.3} x_{k+1}=x_k-\Lambda (x_k)^{-1}F(x_k),\qquad \textnormal{for each},\qquad k=0,1,2,\ldots , \end{equation}

where $x_0\in \mathbb {R}^n$ is an initial point and $\Lambda (x_k)\in \partial F(x_k)$ the generalized Jacobian of $F$ as defined by Clarke [ 14 ] . We present local as well as semilocal convergence results under weaker conditions than in earlier studies such as [ 9 ] , [ 10 ] , [ 14 ] , [ 15 ] , [ 24 ] , [ 25 ] , [ 26 ] . In the case of local convergence, our convergence ball is larger and the ratio of convergence smaller than before [ 9 ] , [ 10 ] , [ 14 ] , [ 15 ] , [ 24 ] – [ 26 ] . These advantages are also obtained under weaker hypotheses. This type of improved convergence results are important in computational Mathematics, since this way we have a wider choice of initial guesses and we compute less iterates in order to obtain a desired error tolerance.

The rest of the paper is organized as follows: In order to make the paper as self contained as possible, we provide the definitions of semismooth, semianalytic and subanalytic functions as well as earlier results in Section 2. The semilocal and local convergence analysis of Newton’s method is given in Section 3. Finally the numerical examples illustrating the theoretical results are given in the concluding Section 4.

2 Semismooth, Semianalytic and Subanalytic Functions

In order to make the paper as self contained as possible we state some standard definitions and results. In [ 24 ] , Milfflin introduced the concept of semismoothness for functionals, later in [ 26 ] , L.Qi and J. Sun extended this concept for functions of several variable. In fact they showed that semismoothness is equivalent to the uniform convergence of directional derivatives in all directions.

Definition 1

(see [ 14 , p. 70 ] )Let $F: \mathbb {R}^n\rightarrow \mathbb {R}^n$ be a locally Lipschitz continuous function. The limiting Jacobian of $F$ at $x\in \mathbb {R}^n$ is defined as

\[ \partial ^\circ F(x)=\{ A\in L(\mathbb {R}^n, \mathbb {R}^m): \exists \, u^k\in D_F;F'(u^k)\rightarrow A, \, k\rightarrow \infty \} \]

where $D_F$ denotes the point of differentiability of $F.$ The Clarke Jacobian of $F$ at $x\in \mathbb {R}^n$ denoted $\partial F(x)$ is the subset of $X^\ast $ dual of $X,$ defined as the closed convex hull of $\partial ^\circ F(x).$

Definition 2

[ 26 ] We say that $F$ is semismooth at $x\in \mathbb {R}^n$ if $F$ is locally Lipschitzian at $x$ and

\[ \lim _{V\in F'(x+th'), h'\rightarrow h,\, t\downarrow 0} \{ Vh'\} \]

exists for any $h\in \mathbb {R}^n.$

Note that convex functions and smooth functions are semismooth functions, Further the product and sums of semismooth functions are semismooth functions (see [ 10 ] ). Moreover, semismoothness of $F$ implies

\[ \lim _{h'\rightarrow h, \, t\rightarrow 0} \tfrac {F(x+th’)-F(x)}{t} =\lim _{V\in F'(x+th'), h'\rightarrow h,\, t\downarrow 0} \{ Vh'\} . \]

Definition 3

[ 15 ] A subset $X$ of $\mathbb {R}^n$ is semianalytic if for each $a\in \mathbb {R}^n$ there is a neighbourhooh $U$ of a and real analytic functions $f_{i,j}$ on $U$ such that

\[ X\cap U=\bigcup _{i=1}^r\bigcap _{j=1}^{s_i}\{ x\in U|f_{i,j}\varepsilon _{i,j} 0\} \]

where $\varepsilon _{i,j}\in \{ {\lt}, {\gt}, =\} .$

Remark 4

$X$ is said to be semianalytic if $X=\mathbb {R}^n$ and $f_{i,j}$ are polynomials.

Definition 5

[ 15 ] A subset $X$ of $\mathbb {R}^n$ is subanalytic if for each $a\in \mathbb {R}^n$ admits a neighborhood $U$ such that $X\cap U$ is a projection of a relatively compact semianalytic set: there is a semianalytic bounded set $A$ in $\mathbb {R}^{n+p}$ such that $X\cap U=\prod (A)$ where $\prod :\mathbb {R}^{n+p}\rightarrow \mathbb {R}^{n}$ is the projection.

Definition 6

Let $X$be a subset of $\mathbb {R}^n.$ A function $F: X\rightarrow \mathbb {R}^{n}$ is semianalytic (resp. subanalytic) if its graph is semianalytic (resp. subanalytic).

It can be seen that the class of semianalytic (resp. subanalytic) sets are closed under elementary set operations, further the closure, the interior and the connected components of a semianalytic (resp. subanalytic) set are semianalytic(resp. subanalytic). But, the image of a bounded semianalytic set by a semianalytic functions is not stable under algebraic operations (see [ 23 ] , [ 13 ] ). That is why the subanalytic functions are introduced. If $X$ is a subanalytic and relatively compact set the image of $X$ by a subanalytic function is subanalytic (see [ 23 ] , [ 9 ] ). Further, if $F$ and $g$ are subanalytic continuous functions defined on a compact subanalytic set $K$ then $F+g$ is subanalytic.

For examples and properties of subanalytic or semianalytic functions we refer the interested reader to [ 1 ] , [ 14 ] , [ 16 ] , [ 17 ] , [ 24 ] , [ 25 ] , [ 27 ] , [ 28 ] . The following Propositions and Remark can be found in [ 10 ]

Proposition 7

[ 10 ] If $F: X\subset \mathbb {R}^n\rightarrow \mathbb {R}^n$ is a subanalytic locally Lipschitz mapping then for all $x\in X$

\[ \| F(x+d)-F(x)-F'(x;d)\| =o_x(\| d\| ). \]

Remark 8

[ 28 ] A subanalytic function $t\rightarrow o_c(t)$ admits a Puiseux development; so there exist a constant $c {\gt} 0,$ a real number $\epsilon {\gt} 0$ and a rational number $\gamma {\gt} 0$ such that $\| F(x+d)-F(x)-F'(x;d)\| =c\| d\| ^\gamma $ whenever $\| d\| \leq \epsilon .$

Proposition 9

[ 10 ] Let $F: \mathbb {R}^n\rightarrow \mathbb {R}^n$ be locally Lipschitz and subanalytic, there exists a positive rational number $\gamma $ such that:

\[ \| F(y)-F(x)-\Lambda (y)(y-x)\| =C_x\| y-x\| ^{1+\gamma } \]

where $y$ is close to $x,$ $\Lambda (y)$ is any element of $\partial F(y)$ and $C_x$ is a positive constant.

3 Convergence

We present semilocal and local convergence results for Newton’s method. First, we present a semilocal result for Newton’s method. Let $U(x,\rho ), \bar{U}(x, \rho )$ denote the open and closed balls in $\mathbb {R}^n$ with center $x$ and of radius $\rho {\gt} 0.$

Theorem 10

Let $F:D\subseteq \mathbb {R}^n \rightarrow \mathbb {R}^n$ is locally Lipschitz subanalytic on $D$. For any $\Lambda (x)\in \partial F(x), x\in D,\, \Lambda (x)$ nonsingular;

\begin{equation} \label{3.1} \| \Lambda (x_0)^{-1}F(x_0)\leq \eta ,\qquad \textnormal{for some}\, \, x_0\in D; \end{equation}

\begin{eqnarray} \label{3.2} \| \Lambda (y)^{-1}[F(y)-F(x)-\Lambda (y)(y-x)]\| & \leq & K\| y-x\| ^{1+\gamma }, \end{eqnarray}

for each $x,y\in D\, \, \textnormal{and some}\, \, \gamma \geq 0;$

\begin{eqnarray} \label{3.3} \| \Lambda (y)^{-1}(\Lambda (y)-\Lambda (x))(y-x)\| & \leq & M\| y-x\| ^{1+\gamma _0}, \end{eqnarray}

for each $x,y\in D\, \, \textnormal{and some}\, \, \gamma _0\geq 0;$

\begin{equation} \label{3.4} 0\leq \alpha :=K\eta ^\gamma +M\eta ^{\gamma _0} < 1 \end{equation}

and for

\begin{align} \label{3.5} r=& \tfrac {\eta }{1-\alpha } \end{align}

\[ \bar{U}(x^\ast , r) \subseteq D. \]

Then, sequence $\{ x_k\} $ generated by Newton’s method (3) is well defined, remains in $U(x_0, r)$ for each $k =0, 1, 2, \ldots $ and converges to $x^\ast \in \bar{U}(x_0,r)$ of equation $F(x)=0.$ Moreover, the following estimates hold:

\begin{equation} \label{3.7} \| x_{k+1}-x_k\| \leq \alpha \| x_k-x^\ast \| , \qquad \textnormal{for each}\, \, \, k=0,1,2,\ldots \end{equation}

and

\begin{equation} \label{3.8} \| x_k-x^\ast \| \leq \tfrac {\alpha ^k\eta }{1-\alpha }, \qquad \textnormal{for each}\, \, \, k=0,1,2,\ldots . \end{equation}

Proof â–¼

It follows from (1), (4), (5) and Newton’s method for $k=0$ that

\[ \| x_1-x_0\| =\| F'(x_0)^{-1}F(x_0)\| \leq \eta \leq \tfrac {\eta }{1-\alpha }=r. \]

Hence, $x_1\in \bar{U}(x_0,r).$ Using Newton’s method (3) for $k=1,$ we get the approximation

\begin{eqnarray} \nonumber F(x_1)& =& F(x_1)-F(x_0)-\Lambda (x_0)(x_1-x_0)\\ \label{3.9} & =& [F(x_1)-F(x_0)-\Lambda (x_1)(x_1-x_0)] +[\Lambda (x_1)-\Lambda (x_0)](x_1-x_0). \end{eqnarray}

Then, since $x_1\in D$ we have that $\Lambda (x_1)^{-1}\in L(Y,X).$ In view of (1), (2), (3), (4) and (8) we get that

\begin{eqnarray} \nonumber \| x_2-x_1\| & =& \| \Lambda (x_1)^{-1}F(x_1)\| \\ \nonumber & \leq & \| \Lambda (x_1)^{-1}(F(x_1)-F(x_0)-\Lambda (x_1)(x_1-x_0))\| \\ \nonumber & & +\| \Lambda (x_1)^{-1}(\Lambda (x_1)-\Lambda (x_0))(x_1-x_0)\| \\ \nonumber & \leq & K\| x_1-x_0\| ^{1+\gamma }+M\| x_1-x_0\| ^{1+\gamma _0}\\ \nonumber & =& (K\| x_1-x_0\| ^\gamma +M\| x_1-x_0\| ^{\gamma _0})\| x_1-x_0\| \\ \nonumber & \leq & (K\eta ^\gamma +M\eta ^{\gamma _0})\| x_1-x_0\| =\alpha \| x_1-x_0\| \end{eqnarray}

and

\begin{eqnarray} \nonumber \| x_2-x_0\| & \leq & \| x_2-x_1\| +\| x_1-x_0\| \leq (\alpha +1)\| x_1-x_0\| \\ \label{3.11} & =& \tfrac {1-\alpha ^2}{1-\alpha }\| x_1-x_0\| \leq \tfrac {1-\alpha ^2}{1-\alpha }\eta \leq r, \end{eqnarray}

which shows that (6) holds for $k=1$ and $x_2\in \bar{U}(x_0,r).$

Let us assume that (6) holds for all $i\leq k$ and $x_i\in \bar{U}(x_0,r).$ Then, by simply using $x_{i-1}, x_i$ in place of $x_0, x_1$ in (8)–(9) we get that

\[ \| x_{i+1}-x_i\| \leq \alpha \| x_i-x_{i-1}\| , \]

\[ \| x_{i+1}-x_0\| \leq \tfrac {1-\alpha ^{i+1}}{1-\alpha }\| x_1-x_0\| \leq \tfrac {1-\alpha ^{i+1}}{1-\alpha }\eta \leq r, \]

which complete the induction for (6) and $x_{i+1}\in \bar{U}(x_0,r).$ It follows that sequence $\{ x_k\} $ is complete in $\mathbb {R}^n$ and as such it converges to some $x^\ast \in \bar{U}(x_0,r)$ (since $ \bar{U}(x_0,r)$ is a closed set). By letting $i\rightarrow \infty $ in the estimate

\[ \| \Lambda (x_i)^{-1}F(x_i)\| =\| x_{i+1}-x_i\| \leq \alpha ^{i+1}\eta \]

and since $\Lambda (x_i)^{-1}\in L(Y,X),$ we get that $F(x^\ast )=0.$ We also have that

\begin{eqnarray} \nonumber \| x_{k+i}-x_k\| & \leq & \| x_{k+i}-x_{k+i-1}|+\| x_{k+i-1}-x_{k+i-2}\| +\ldots +\| x_{k+1}-x_k\| \\ \nonumber & \leq & (\alpha ^{k+i-1}+\alpha ^{k+i-2}+\ldots +\alpha ^k)\| x_1-x_0\| \\ \label{3.14} & =& \alpha ^k\tfrac {1-\alpha ^i}{1-\alpha }\| x_1-x_0\| \leq \alpha ^k\tfrac {1-\alpha ^i}{1-\alpha }\eta . \end{eqnarray}

By letting $i\rightarrow \infty $ in (10) we obtain (7).

Proof â–¼

Remark 11

(a) Condition (3) does not necessarily imply that $\Lambda $ is Lipschitz and cannot be avoided if you want to show convergence.

(b) If you use

\begin{equation} \label{3.15} \| \Lambda (y)^{-1}\| \leq K_1 \end{equation}

\begin{eqnarray} \label{3.16} \| F(y)-F(x)-\Lambda (y)(y-x)\| & \leq & K_2\| y-x\| ^{1+\gamma }, \end{eqnarray}

for each $x,y\in D, \, \, \textnormal{and some}\, \, \gamma \geq 0;$

\begin{eqnarray} \label{3.17} \| (\Lambda (y)-\Lambda (x))(y-x)\| & \leq & M_1\| y-x\| ^{1+\gamma _0}, \end{eqnarray}

for each $x,y\in D,$ and some $\gamma _0\geq 0,$ then, we have the estimates

\begin{eqnarray*} \| \Lambda (y)^{-1}[F(y)-F(x)-\Lambda (y)(y-x)]\| & \leq & \| \Lambda (y)^{-1}\| \\ & & \times \| F(y)-F(x)-\Lambda (y)(y-x)\| \\ & \leq & K_1K_2\| y-x\| ^{1+\gamma }\\ \| \Lambda (y)^{-1}[\Lambda (y)-\Lambda (x)](y-x)\| & \leq & \| \Lambda (y)^{-1}\| \| [\Lambda (y)-\Lambda (x)](y-x)\| \\ & \leq & K_1M_1\| y-x\| ^{1+\gamma _0}. \end{eqnarray*}

Set $K=K_1K_2,\, M=K_1M_1.$ If (1), (2) are replaced by (11), (12) and (13), then the conclusion of Theorem 10 hold in this stronger though setting.

\[ \| \Lambda (y)^{-1}[\Lambda (y)-\Lambda (x)](y-x)\| \leq \| \Lambda (y)^{-1}[\Lambda (y)-\Lambda (x)]\| \| y-x\| , \]

$M$ in (3) can be chosen to be an upper bound on $\| \Lambda (y)^{-1}[\Lambda (y)-\Lambda (x)]\| .$ That is

\[ \| \Lambda (y)^{-1}[\Lambda (y)-\Lambda (x)]\| \leq M. \]

Notice also that $\| \Lambda (y)-\Lambda (x)\| \leq M_2$ holds if e.g. $\Lambda $ is continuous. Then, we can choose e.g. $M= K_1 M_2$ for $\gamma _0=0.$

(d) If $\gamma _0=\gamma =0$ and (1)-(3) are given in non-invariant form, then Theorem 10 reduces to the corresponding one in [ 26 ] . Otherwise, our Theorem 10 is an extension of the one in [ 26 ] . Moreover, it is an improvement in the case $\gamma _0=\gamma =0,$ since our results are given in affine invariant form. The advantages of affine over non-affine invariant form results are well known in the literature [ 17 ] .

(e) It was shown in [ 10 ] that if $F: D\subseteq \mathbb {R}^n\rightarrow \mathbb {R}^n$ is locally Lipschitz and subanalytic, then (12) always holds. Therefore, (2) holds for $K=K_1K_2.$ â–¡

Next, we present a local convergence result for Newton’s method.

Theorem 12

Suppose $F: D\subseteq \mathbb {R}^n\rightarrow \mathbb {R}^n$ is locally Lipschitz and subanalytic; there exists a regular point $x^\ast \in D$ such that $F(x^\ast )=0;$ for any $\Lambda (x)\in \partial F(x), \, x\in D,\, \Lambda (x)$ is nonsingular;

\begin{eqnarray} \label{3.18} \| \Lambda (y)^{-1}[F(y)-F(x^\ast )-\Lambda (y)(y-x^\ast )]\| & \leq & \lambda \| y-x^\ast \| ^{1+\beta } \end{eqnarray}

for each $x,y \in D$ and some $\lambda {\gt}0,\, \, \beta {\gt}0,$ and for

\[ R=\min \{ \tfrac {1}{\lambda }, \tfrac {1}{\lambda ^\beta }\} \]

\[ \bar{U}(x_0,R)\subseteq D. \]

Then, sequence $\{ x_n\} $ generated by Newton’s method (3) converges to $x^\ast $ provided that $x_0\in U(x^\ast , R).$ Moreover, the following estimates hold for each $n=0,1,2,\ldots $

\begin{equation} \label{3.21} \| x_{n+1}-x^\ast \| \leq \lambda \| x_n-x^\ast \| ^{1+\beta }\leq \| x_0-x^\ast \| < R \end{equation}

and

\begin{equation} \label{3.22} \| x_{n+1}-x^\ast \| \leq \lambda ^{-\frac{1}{\beta }}(\lambda \| x_0-x^\ast \| )^{(1+\beta )^{n+1}}. \end{equation}

Proof â–¼

We have that $x_1\in U(x^\ast , R)$ by the choice of $R.$ Then, using the estimate

\[ x_2-x^\ast =-\Lambda (x_1)^{-1}[F(x_1)-F(x^\ast )-\Lambda (x_1)(x_1-x^\ast )] \]

and (14), we get that

\begin{eqnarray*} \nonumber \| x_2-x^\ast \| & =& \| \Lambda (x_1)^{-1}[F(x_1)-F(x^\ast )-\Lambda (x_1)(x_1-x^\ast )]\| \\ & \leq & \lambda \| x_1-x^\ast \| ^{1+\beta }\leq \| x_1-x^\ast \| {\lt} R \end{eqnarray*}

by the choice of $R,$ which shows (15) and (16) for $n=0.$ Suppose that (15) and (16) hold for each $k\leq n.$ Then, we have that

\begin{equation} \label{3.25} x_{k+1}-x^\ast =-\Lambda (x_k)^{-1}[F(x_k)-F(x^\ast )-\Lambda (x_k)(x_k-x^\ast )] \end{equation}

so by (14) and (16) we get that

\begin{eqnarray} \nonumber \| x_{k+1}-x^\ast \| & =& \| \Lambda (x_k)^{-1}[F(x_k)-F(x^\ast )-\Lambda (x_k)(x_k-x^\ast )]\| \\ \nonumber & \leq & \lambda \| x_k-x^\ast \| ^{1+\beta }\leq \lambda (\lambda \| x_{k-1}-x^\ast \| ^{1+\beta })^{1+\beta } \\ \nonumber & \leq & \lambda \lambda ^{1+\beta }(\| x_{k-1}-x^\ast \| )^{(1+\beta )^2}\\ \nonumber & \vdots & \\ \nonumber & =& \lambda ^{\frac{(1+\beta )^{k+1}+\ldots +(1+\beta )+1}{\beta }}\| x_0-x^\ast \| ^{(1+\beta )^{k+1}}\\ \nonumber & =& \lambda ^{-\frac{1}{\beta }}(\lambda \| x_0-x^\ast \| )^{k+1} \end{eqnarray}

which shows (15), (16) for all $n$ and that $\lim _{k\rightarrow \infty }x_k=x^\ast .$

Proof â–¼

Remark 13

Condition (14) certainly holds if replaced by the stronger

\begin{equation} \label{3.27} \| \Lambda (y)^{-1}[F(y)-F(x)-\Lambda (y)(y-x)]\| \leq \lambda _1\| y-x\| ^{1+\beta },\, \, \textnormal{for each}\, \, x, y\in D. \end{equation}

In this case however,

\begin{equation} \label{3.28} \lambda \leq \lambda _1 \end{equation}

holds in general and $\frac{\lambda _1}{\lambda }$ can be arbitrarily large [ 3 , 7 , 8 ] . Moreover, if $\lambda _1=\lambda $ and (14) is replaced by (18), then our result reduces to the corresponding one in [ 26 ] . Otherwise (i.e., if $\lambda {\lt} \lambda _1$), it constitutes an improvement with advantages:

(i) (14) is weaker than (17). That is (17) implies (14) but (14) does not necessarily imply (17).

(ii) If $\lambda {\lt} \lambda _1,$ the new error bounds on the distances $\| x_n-x^\ast \| $ are tighter and the ratio of convergence smaller. That means in practice fewer iterates are required to achieve a given error tolerance. Hence, the applicability of Newton’s method is expanded under less computational cost. Notice also that the computation of constant $\lambda $ requires the computation of constant $\lambda _1$ as a special case (see, Example 4.2). â–¡

Next, we present the corresponding semilocal and local convergence results under contravariant conditions [ 3 , 6 , 7 , 17 , 25 ] .

Theorem 14

Suppose: $F:D\subseteq \mathbb {R}^n\rightarrow \mathbb {R}^n$ is locally Lipschitz subanalytic; for ant $\Lambda (x)\in \partial F(x),\, x\in D,\, \Lambda (x)$ is nonsingular;

\begin{equation} \label{3.30*}\| F(y)-F(x)-\Lambda (y)(y-x)\| \leq \mu _0\| \Lambda (x)(y-x)\| ^{1+\gamma } \end{equation}

for some $\mu _0 {\gt} 0,\, \gamma {\gt}0$ and each $x, y\in D;$

\begin{equation} \label{3.31*}\| (\Lambda (y)-\Lambda (x))(y-x)\| \leq \mu _1\| \Lambda (x)(y-x)\| ^{1+\gamma } \end{equation}

for some $\mu _1 {\gt} 0$ and each $x, y\in D;$ Define the set $Q$ by

\[ Q=\{ x\in D:\| F(x)\| ^\gamma {\lt} \tfrac {1+\gamma }{\mu }\} , \]

and let $Q$ be bounded, where $\mu =\mu _0+\mu _1;\, x_0\in D$ is such that

\[ \| F(x_0)\| \leq \xi \]

and

\[ \xi \mu ^{\frac{1}{\gamma }} {\lt} (1+\gamma )^{\frac{1}{\gamma }} \]

(i.e., $x_0\in Q$). Then, sequence $\{ x_k\} $ generated for $x_0\in Q$ by Newton’s method (3) is well defined, remains in $Q$ for each $n=0,1,2,\ldots $ and converges to some $x^\ast \in Q$ such that $F(x^\ast )=0.$ Moreover, sequence $\{ F(x_k)\} $ converges to zero and satisfies

\[ \| F(x_{k+1})\| \leq \mu \| F(x_k)\| ^{1+\gamma },\qquad \textnormal{for each}\, \, k=0,1,2,\ldots \]

Proof â–¼

By hypothesis $x_0\in Q.$ Suppose $x_k\in Q.$ Then, using Newton’s method (3) we get the approximation

\begin{eqnarray} \label{3.29} F(x_{k+1}& =& [F(x_{k+1})-F(x_k)-\Lambda (x_{k+1})(x_{k+1}-x_k)]\\ \nonumber & & +[\Lambda (x_{k+1})-\Lambda (x_k)](x_{k+1}-x_k). \end{eqnarray}

Using (19), (20), (21) we get in turn that

\begin{eqnarray} \nonumber \| F(x_{k+1}\| & =& \| [F(x_{k+1})-F(x_k)-\Lambda (x_{k+1})(x_{k+1}-x_k)]\| \\ \nonumber & & +[\Lambda (x_{k+1})-\Lambda (x_k)](x_{k+1}-x_k)\\ \nonumber & \leq & \mu _0\| \Lambda (x_k)(x_{k+1}-x_k)\| ^{1+\gamma }+\mu _1\| \Lambda (x_k)(x_{k+1}-x_k)\| ^{1+\gamma }\\ \nonumber & =& \mu \| \Lambda (x_k)(x_{k+1}-x_k)\| ^{1+\gamma }. \end{eqnarray}

Since $x_k\in Q,$ we have that

\[ \| F(x_k)\| ^\gamma {\lt} \tfrac {1+\gamma }{\mu }. \]

Therefore, we get that

\begin{eqnarray*} \| F(x_{k+1}\| & \leq & \mu \| F(x_{k}\| ^{1+\gamma } {\lt} \mu \tfrac {\| F(x_{k}\| }{\mu }=\| F(x_{k}\| . \end{eqnarray*}

Notice also that

\[ \| F(x_{k+1}\| ^\gamma {\lt} \| F(x_{k}\| ^\gamma {\lt} \tfrac {1+\gamma }{\mu }. \]

We also have the implication

\[ x_{k+1} \in Q \Rightarrow \{ x_k\} \subseteq Q. \]

Set

\[ s_k=\mu ^{\frac{1}{\gamma }}\| F(x_k)\| . \]

Then, we have in turn

\begin{eqnarray*} s_{k+1}& \leq & \tfrac {1}{1+\gamma }s_k^{1+\gamma }s_{k+1}\leq \tfrac {1}{1+\gamma }s_k^{1+\gamma }\\ & \leq & \ldots \leq \tfrac {1}{1+\gamma }(\tfrac {1}{1+\gamma })^{\frac{(1+\gamma )[(1+\gamma )^k-1]}{\gamma }}s_0^{(1+\gamma )^{1+k}}\\ & =& (1+\gamma )^{\frac{1}{\gamma }}(\tfrac {s_0}{(1+\gamma )^{\frac{1}{\gamma }}})(1+\gamma )^{k+1}. \end{eqnarray*}

But we have that

\[ s_0=\xi \mu ^{\frac{1}{\gamma }} {\lt} (1+\gamma )^{\frac{1}{\gamma }}. \]

Hence, we obtain $\lim _{k\rightarrow \infty }s_k =0,$ which imply $\lim _{k\rightarrow \infty }\| F(x_k)\| =0.$ The set $Q$ is bounded, so there exists an accumulation point $x^\ast \in Q$ of sequence $\{ x_k\} $ such that $F(x^\ast )=0.$

Proof â–¼

If $F$ is Fréchet differentiable and $D$ is a convex set, then due to the estimate

\begin{equation} \label{3.36*}F(x_{k+1})=\int _0^1[F'(x_k+\theta (x_{k+1}-x_k))-F'(x_k)](x_{k+1}-x_k)d\theta \end{equation}

by repeating the proof of Theorem 14 using (22), we arrive at the following semilocal convergence result for Newton’s method (2) under contravariant conditions.

Theorem 15

Suppose :$F:D\subseteq \mathbb {R}^n\rightarrow \mathbb {R}^n$ is Fréchet-differentiable; for any $x\in D,\, F'(x)^{-1}\in L(\mathbb {R}^n);$

\[ \| (F'(y)-F'(x))(y-x)\| \leq \mu _1\| F'(x)(y-x)\| ^{1+\gamma } \]

for some $\mu _1 {\gt} 0$ and each $x, y\in D;$ Define the set $Q_1$ by

\[ Q_1=\{ x\in D: \| F(x)\| ^\gamma {\lt} \tfrac {1+\gamma }{\mu _1}\} ; \]

$x_0\in D$ is such that

\[ \| f(x_0)\| \leq \xi \]

and

\[ \xi \mu _1^{\frac{1}{\gamma }} {\lt} (1+\gamma )^{\frac{1}{\gamma }}. \]

Then, sequence $\{ x_k\} $ generated by Newton’s method (2) is well defined, remains in $Q$ for each $n=0,1,2,\ldots $ and converges to some $x^\ast \in Q$ such that $F(x^\ast )=0.$ Moreover, sequence $\{ F(x_k)\} $ converges to zero and satisfies

\[ \| F(x_{k+1})\| \leq \mu _1\| F(x_k)\| ^{1+\gamma },\qquad \textnormal{for each}\, \, k=0,1,2,\ldots . \]

Remark 16

If $\gamma =1,$ Theorem 15 reduces to the corresponding Theorem in [ 26 ] . However, there are examples where $\gamma \neq 1$ (see Example 17). Then, in this case the results in [ 26 ] cannot apply.â–¡

4 Numerical Examples

We present numerical examples to illustrate the theoretical results. First, we present an example under contravariant conditions.

Example 17

Let $X=Y=\mathbb {R}^2,\, \, D=\{ x=(x_1,x_2):\frac{1}{2} \leq x_i\leq 2, i=1,2\} $ equipped with the max-norm and define $F$ on $D$ for $x= (x_1,x_2)$ by

\[ F(x)=\left[\begin{array}{c} x_1^{\frac{3}{2}}-2x_1+x_2\\ x_1+x_2^{\frac{3}{2}}-2x_2 \end{array}\right]. \]

Then, the Fréchet-derivative is given by

\[ F'(x)=\left[ \begin{array}{cc} \frac{3}{2}x_1^{\frac{1}{2}}-2& 1\\ 1& \frac{3}{2}x_2^{\frac{1}{2}}-2 \end{array}\right]. \]

Therefore, for any $x, y\in D,$ we have in turn that

\begin{eqnarray*} \| F’(x)-F’(y)\| & =& \left\| \left[ \begin{array}{cc} \tfrac {3}{2}(x_1^{\frac{1}{2}}-y_1^{\frac{1}{2}})& 0\\ 0& \tfrac {3}{2}(x_2^{\frac{1}{2}}-y_2^{\frac{1}{2}}) \end{array}\right]\right\| \\ & =& \tfrac {3}{2}\max \{ |x_1^{\frac{1}{2}}-y_1^{\frac{1}{2}}|, |x_2^{\frac{1}{2}}-y_2^{\frac{1}{2}}|\} \\ & \leq & \tfrac {3}{2}\max \{ |x_1-y_1|^{\frac{1}{2}}, |x_2-y_2|^{\frac{1}{2}}\} \\ & \leq & \tfrac {3}{2}[\max \{ |x_1-y_1|, |x_2-y_2|\} ]^{\frac{1}{2}} =\tfrac {3}{2}|x-y|^\frac {1}{2}. \end{eqnarray*}

We also have that $\| F'(x)\| \leq 2$ for each $x\in D.$ Then, we get that

\[ \| (F'(x)-F'(y))(x-y)\| \leq \tfrac {3\sqrt{2}}{8}\| F'(x)(x-y)\| ^{\frac{3}{2}}. \]

Therefore, we can choose $\gamma =\frac{1}{2},\, \mu _1=\frac{3\sqrt{2}}{8}$ and

\[ Q_1=\{ x\in D:\| F(x)\| \leq 8\} . \]

The, conclusions of Theorem 15 hold and Newton’s method converges to $x^\ast =(1,1).$ â–¡

Next, we present an example for the local convergence case.

Example 18

Let $X=Y=\mathbb {R},\, D={U}(0,1)$ and define function $F$ on $D$ by

\begin{equation} \label{4.3} F(x)=e^x-1. \end{equation}

Then, we have that $x^\ast =0.$ Using (23) we get in turn that

\begin{align*} F’(y)^{-1}(F(y)-F(x^\ast )-F’(y)(y-x^\ast ))=& e^{-y}(e^y-1-e^yy)\\ =& 1-y-(1-y+\tfrac {y^2}{2!}-\tfrac {y^3}{3!}+\tfrac {y^4}{4!}-\ldots )\\ =& (\tfrac {1}{2!}-\tfrac {y}{3!}+\tfrac {y^2}{4!}-\ldots )y^2 \end{align*}

so,

\begin{eqnarray*} \| F’(y)^{-1}(F(y)-F(x^\ast )-F’(y)(y-x^\ast ))\| & =& |\tfrac {1}{2!}-\tfrac {y}{3!}+\tfrac {y^2}{4!}-\ldots ||y|^2\\ & \leq & (\tfrac {1}{2!}-\tfrac {|y|}{3!}+\tfrac {|y|^2}{4!}-\ldots )|y|^2\\ & \leq & (\tfrac {1}{2!}-\tfrac {1}{3!}+\tfrac {1}{4!}-\ldots )|y|^2\\ & =& (e-2)|y|^2. \end{eqnarray*}

Hence, we can choose $\lambda =e-2$ and $\beta =1.$ Moreover, we have that

\begin{eqnarray*} & & F’(y)^{-1}(F(y)-F(x)-F’(y)(y-x))=\\ & =& e^{-y}(e^y-1-e^x+1-e^y(y-x))\\ & =& 1-(y-x)-e^{x-y}\\ & =& 1+x-y-[1+(x-y)+\tfrac {(x-y)}{2!}+\tfrac {(x-y)^2}{3!}+\tfrac {(x-y)^3}{4!}-\ldots ]\\ & =& (\tfrac {1}{2!}+\tfrac {x-y}{3!}+\tfrac {(x-y)^2}{4!}+\ldots )(x-y)^2 \end{eqnarray*}

so,

\begin{align*} \| F’(y)^{-1}(F(y)-F(x)-F’(y)(y-x))\| =& |\tfrac {1}{2!}+\tfrac {x-y}{3!}+\tfrac {(x-y)^2}{4!}+\ldots ||y-x|^2\\ \leq & (\tfrac {1}{2!}+\tfrac {|x-y|}{3!}+\tfrac {|x-y|^2}{4!}+\ldots )|y-x|^2\\ \leq & (\tfrac {1}{2!}+\tfrac {|x-y|}{3!}+\tfrac {|x-y|^2}{4!}+\ldots )|y-x|^2\\ \leq & (\tfrac {1}{2!}+\tfrac {2}{3!}+\tfrac {2^2}{4!}+\ldots )|y-x|^2\\ =& (e^2-3)|y-x|^2. \end{align*}

Hence, we can choose $\lambda _1=e^2-3$ and $\beta =1.$ Therefore, we obtain

\[ R_1=\tfrac {1}{\lambda _1}=0.227839421 {\lt} 1.392211191=\tfrac {1}{\lambda }=R. \]

That is, we deduce that the new convergence ball is larger and the ratio of convergence smaller than the old convergence ball and the old ratio of convergence. Finally, the convergence of Newton’s method is guaranteed by Theorem 12 provided that $x_0\in U(x_0, R).$ â–¡

Bibliography

1: S. Amat, S. Busquier, J.M. Gutiérrez, Geometric constructions of iterative functions to solve nonlinear equations, J. Comput. Appl. Math., 157 (2003), 197–205. $\includegraphics[scale=0.1]{ext-link.png}$
2: I.K. Argyros, A unifying local-semilocal convergence analysis and applications for two-point Newton-like methods in Banach spaces, J. Math. Anal. Appl., 298 (2004), 374–397. $\includegraphics[scale=0.1]{ext-link.png}$
3: I.K. Argyros, Computational theory of iterative methods. Series: Studies in Computational Mathematics, 15, Editors: C.K. Chui and L. Wuytack, Elsevier Publ. Co. New York, U.S.A, 2007.
4: I.K. Argyros, Concerning the convergence of Newton’s method and quadratic majorants, J. Appl. Math. Comput., 29 (2009), 391–400. $\includegraphics[scale=0.1]{ext-link.png}$
5: I.K. Argyros, A semilocal convergence analysis for directional Newton methods, Math. Comput., 80 (2011), 327–343. $\includegraphics[scale=0.1]{ext-link.png}$
6: I.K. Argyros, S. Hilout, Weaker conditions for the convergence of Newton’s method, J. Complexity, 28 (2012), 364–387. $\includegraphics[scale=0.1]{ext-link.png}$
7: I.K. Argyros, Y.J. Cho, S. Hilout, Numerical methods for equations and its applications, CRC Press/Taylor and Francis Publ., New York, 2012.
8: I.K. Argyros, S. Hilout, Computational methods in nonlinear analysis, World Scientific Publ. Comp., New Jersey, USA 2013.
9: E. Bierstone, P.D. Milman, Semianalytic and subanalytic sets, IHES. Publications mathematiques, 67 (1988), 5–42. $\includegraphics[scale=0.1]{ext-link.png}$
10: J. Bolte, A. Daniilidis, A.S. Lewis, Tame mapping are semismooth, Math. Programming (series B), 117 (2009), 5–19. $\includegraphics[scale=0.1]{ext-link.png}$
11: V. Candela, A. Marquina, Recurrence relations for rational cubic methods I: The Halley method, Computing, 44 (1990), 169–184. $\includegraphics[scale=0.1]{ext-link.png}$
12: V. Candela, A. Marquina, Recurrence relations for rational cubic methods II: The Chebyshev method, Computing, 45 (1990), 355–367. $\includegraphics[scale=0.1]{ext-link.png}$
13: C. Chun, P. Stanica, B. Neta, Third order family of methods in Banach spaces, Computers Math. Appl., 61 (2011), 1665–1675. $\includegraphics[scale=0.1]{ext-link.png}$
14: F.H. Clarke, Optimization and Nonsmooth Analysis, Society for industrial and Applied Mathematics, 1990.
15: J.P. Dedieu, Penalty functions in subanalytic optimization, Optimization, 26 (1992), 27–32. $\includegraphics[scale=0.1]{ext-link.png}$
16: J.E. Dennis Jr, R.B. Schnabel, Numerical methods of unconstrained optimization and nonlinear equations, Pretice-Hall, Englewood Cliffs., 1982.
17: P. Deuflhard, Newton methods for nonlinear problems: Affine invariance and Adaptive Algorithms, Berlin: Springer-Verlag, 2004.
18: J.M. Gutiérrez, M.A. Hernández, Recurrence relations for the super-Halley method, Computers Math. Appl., 36 (1998), 1–8. $\includegraphics[scale=0.1]{ext-link.png}$
19: J.M. Gutiérrez, M.A. Hernández, Third-order iterative methods for operators with bounded second derivative, J. Comput. Appl. Math., 82 (1997), 171–183. $\includegraphics[scale=0.1]{ext-link.png}$
20: M.A. Hernández, M.A. Salanova, Modification of the Kantorovich assumptions for semilocal convergence of the Chebyshev method, Journal of Computational and Applied Mathematics, 126 (2000), 131–143. $\includegraphics[scale=0.1]{ext-link.png}$
21: M.A. Hernández, Chebyshev’s approximation algorithms and applications, Computers Math. Applic., 41 (2001), 433–455. $\includegraphics[scale=0.1]{ext-link.png}$
22: L.V. Kantorovich, G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982.
23: S. Lojasiewicz, Ensembles semi-analytiques, IHES Mimeographed notes, 1964.
24: R. Mifflin, Semi-smooth and semi-convex functions in constrained optimization, SIAM J. Control and Optimization, 15 (1977), 959–972. $\includegraphics[scale=0.1]{ext-link.png}$
25: J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic press, New York, 1970.
26: L. Qi, J. Sun, A non-smooth version of Newton’s method, Mathematical Programming, 58 (1993), 353–367. $\includegraphics[scale=0.1]{ext-link.png}$
27: R.T. Rockafellar, Favorable classes of Lipschitz-continuous functions in subgradient optimization, in E. Nurminski ed., Nondifferentiable Optimization (Pergamon Press, New York, 1982), 125–143.
28: L. Van Den Dries, C. Miller, Geometric categories and 0-minimal structures, Duke. Math. J., 84 (1996), 497–540. $\includegraphics[scale=0.1]{ext-link.png}$