Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1995, pp. 30-36. Submitted: May 12, 1995. Published: October 16, 1995.

RESULTS ON CONTROLLING THE RESIDUALS OF

PERTURBED NEWTON-LIKE METHODS ON BANACH

SPACES WITH A CONVERGENCE STRUCTURE

Ioannis K. Argyros

Abstract. In this study, we provide sufficient conditions for controlling the residuals of perturbed Newton-like methods, in such a way that the convergence of such methods is ensured. In order to achieve this, we apply a theorem due to Kantorovich on a setting of a regular space with a convergence structure.

(1991) A.M.S. (MOS) Subject Classification Codes. 65J15, 65B05, 47D15, 47H17, 49D15.

Key Words and Phrases. Newton-like methods, residuals.

I. INTRODUCTION

In this study, we are concerned with approximating a solution x^{∗} of the nonlinear operator equation

F (x) + Q(x) = 0,  (1)

where F is a Frechet-differentiable operator defined on a convex subset D of a Banach space X with values in X, and Q is a non-differentiable nonlinear operator with the same domain and values in X.

We generate a sequence {x_{n}} (n ≥ 0) using the perturbed Newton-like method scheme given by

x_{n+1} = x_{n} + δ_{n} (n ≥ 0)  (2)

where the correction δ_{n} satisfies

A(x_{n})δ_{n} = −(F (x_{n}) + Q(x_{n})) + r_{n} (n ≥ 0)  (3)

for a suitable r_{n} ∈ X (n ≥ 0) called residual. The importance of studying perturbed Newton-like methods comes from the fact that variants of Newton’s method can be considered as procedures of this type. In fact, the approximations (2) and (3) characterize any iterative process in which the corrections are taken as approximate solutions of the Newton equations. This happens when approximation (2) is solved by any iterative method or when therein the derivative is replaced by a suitable approximation. In [4] we provided sufficient conditions for the convergence of iteration (2) to a solution x^{∗} of equation (1), by assuming that X is a Banach space with a convergence structure (to be precised later).

Here we derive sufficient conditions for controlling the residuals r_{n} in such a way that the convergence of the sequence {x_{n}} (n ≥ 0) to a solution of equation (1) is ensured.

We also refer the reader to [5], [6], [8] and the references there for relevant work, which however is valid on a Banach space X without a convergence structure. The advantages of working on a Banach space with a convergence structure have been explained in some detail in [4], [6], [7].

Typeset by AMS-TEX

Department of Mathematics, Cameron University, Lawton, OK 73505, U.S.A.

E-mail Address: ioannisa@cua.cameron.edu

\begin{matrix}c \\ ◯ \end{matrix}1995 Cameron University

II. PRELIMINARIES

We will need the definitions:

\underline{Definition 1}. The triple (X, V, E) is a Banach space with a convergence structure if (C_{1}) X, ∥ · ∥) is a real Banach space; (C_{2}) (V, C, ∥ ∥_{v}) is a real Banach space which is partially ordered by the closed convex cone C; the norm

∥ ∥_{v} is assumed to be monotone on C; (C_{3}) E is a closed convex cone in X × V satisfying {0} × C ⊆ E ⊆ X × C; (C_{4}) the operator | | : D → C is well defined:

|x| = inf{q ∈ C|(x, q) ∈ E}

for

x ∈ D = {x ∈ X|∃q ∈ C : (x, q) ∈ E};

and (C_{5}) for all x ∈ D ∥x∥ ≤ ∥|x|∥_{v}.

The set

U(a) = {x ∈ X|(x, a) ∈ E}

defines a sort of generalized neighborhood of zero.

\underline{Definition 2}. An operator L ∈ C^{1}(V_{1} → V) defined on an open subset V_{1} of an ordered Banach space V is order convex on [a, b] ⊆ V_{1} if

c, d ∈ [a, b], c ≤ d ⇒ L′(d) − L′(c) ∈ L_{+}(V),

where for m ≥ 0

L_{+}(V^{m}) = {L ∈ L(V^{m})|0 ≤ x_{i} ⇒ 0 ≤ L(x_{1}, x_{2}, …, x_{m})}

and L(V^{m}) denotes the space of m-linear, symmetric, bounded operators on V.

\underline{Definition 3}. The set of bounds for an operator H ∈ L(X^{m}) is defined to be

B(H) = {L ∈ L_{+}(V^{m})|(x_{i}, q_{i}) ∈ E ⇒ (H(x_{1}, …, x_{m}), L(q_{1}, …, q_{m})) ∈ E}.

\underline{Definition 4}. A partially ordered topological space V is called regular if every order bounded increasing sequence has a limit.

We will need the following proposition due to Kantorovich [3], [5].

Proposition. Let V be a regular partially ordered topological space (POTL-space) and let x, y be two points of V such that x ≤ y. If H : [x, y] → V is a continuous isotone operator having the property that x ≤ Hx and y ≥ Hy, then there exists a point z ∈ [x, y] such that z = Hz.

III. CONVERGENCE ANALYSIS

We will need the following basic result:

\underline{Lemma}. Let V be a regular partially ordered topological space, an operator L ∈ C^{1}(V_{1} → V) with [0, a] ⊆ V_{1} ⊆ V for some a ∈ V, an operator M ∈ C(V_{1} → V), operators R < I, B > I, T, K ∈ L_{+}(V), a point c ∈ V with c > 0 and a point p ∈ [0, a]. Assume:

(a) The equation

g(q) = BT [L(p + q) − L(p) − L′(p)q + M(p + q) − M(p) + K(p + q) − K(p)]
− (I − R)q + c = 0  (4)

has solutions in the interval [0, a] and denote by q^{∗} the least of them.

(b) Let G ∈ L_{+}(V) be given and R_{+} ∈ L_{+}(V), c_{+}, p_{+} ∈ V be such that the following conditions are satisfied:

R_{+} < min {(G − 2I)BT L′(p) + BT GL′(p_{+}) + G(R − I) + I, I} = α  (5)
0 < c_{+} ≤ BT G(L(p_{+}) + M(p_{+}) + K(p_{+})) + GBT (L(p) + M(p) + K(p))
−2BT (L(p) + M(p) + K(p)) + (R_{+} + G − I − BT GL′(p_{+}))c = β  (6)

and

0 ≤ p_{+} ≤ p + c,  (7)

where α and β are functions of the operators and points involved.

(c) The following estimate is true

M(p) ≤ M(p + q)  (8)

for all p, q ∈ [0, a].

Then the equation

g_{+}(q) = BGT [L(p_{+} + q) − L(p_{+}) − L′(p_{+})q + M(p_{+} + q) − M(p_{+}) + K(p_{+} + q) − K(p_{+})]
− (I − R_{+})q + c_{+} = 0  (9)

has nonnegative solutions and the least of them, denoted by q_{+}^{∗} lies in the interval [c_{+}, q^{∗} − c].

Proof. Using the hypothses g(q^{∗}) = 0 and R < I we deduce from (4) that c ≤ q^{∗}. We will show that

g_{+}(q^{∗} − c) ≤ 0.  (10)

From equation (9) and using (6), we obtain in turn

g_{+}(q^{∗} − c) ≤ BGT [L(p + c + q^{∗} − c) − L(p_{+}) − L′(p_{+})(q^{∗} − c)
+ M(p + c + q^{∗} − c) − M(p_{+}) + K(p + c + q^{∗} − c) − K(p_{+})] − (I − R_{+})(q^{∗} − c) + c_{+}
= g(q^{∗}) − BT [L(p + q^{∗}) − L(p) − L′(p)q^{∗} + M(p + q^{∗}) − M(p) + K(p + q^{∗}) − K(p)]

+ BT G[L(p + q^{∗}) − L(p_{+}) − L′(p_{+})(q^{∗} − c) + M(p + q^{∗}) − M(p_{+}) + K(p + q^{∗}) − K(p_{+})]

+ (I − R)q^{∗} − c − (I − R_{+})(q^{∗} − c) + c_{+}
= [BT L′(p) − BT GL′(p_{+}) + (I − R) − (I − R_{+})]q^{∗}
+ (G − I){(I − R)q^{∗} − c − BT [L(p) + M(p) + K(p) + L′(p)q^{∗}]}
+ BT [L(p) + M(p) + K(p) − GL(p_{+}) − GM(p_{+})]
+ BT GL′(p_{+})c + (I − R_{+})c + c_{+} − c
= [(2I − G)BT L′(p) − BT GL′(p_{+}) + R_{+} + G(I − R) − I]q^{∗}
+ 2BT (L(p) + M(p) + K(p)) − BT G(L(p_{+}) + M(p_{+}) + K(p_{+}))
− GBT (L(p) + M(p) + K(p)) + (BT GL′(p_{+}) − G + I − R_{+})c + c_{+} ≤ 0

since (5) and (6) are satisfied. Moreover from (9) for q = c_{+}, we obtain

g_{+}(c_{+}) ≥ 0.  (11)

By inequalities (10), (11), the fact that g is continuous and isotone on [c_{+}, q^{∗} − c], and since V is a regular partially ordered topological space, from the proposition, we deduce that there exists a point q_{+}^{∗} with

g_{+}(q_{+}^{∗}) = 0  (12)

and

c_{+} ≤ q_{+}^{∗} ≤ q^{∗} − c.  (13)

We can assume that q_{+}^{∗} denotes the least of the solutions of equation (9).

That completes the proof of the lemma.

The following result is a consequence of the above lemma.

\underline{Theorem 1}. Let \{c_{n}\} ∈ V, \{T_{n}\}, \{R_{n}\}, \{G_{n}\} ∈ L_{+}(V) (n ≥ 0) be sequences and V as in the above lemma. Assume:

(a) There exists a sequence {p_{n}} ∈ [0, a] ⊆ V_{1} ⊆ V for some a ∈ V with p_{0} = 0 and

p_{n+1} ≤ ∑_{j=0,1,...,n} c_{j} for n ≥ 0.  (14)

(b) R_{0} < I and the function

g_{0}(q) = BT_{0}[L(p_{0} + q) − L(p_{0}) − L′(p_{0})q + M(p_{0} + q) − M(p_{0}) + K(p_{0} + q) − K(p_{0})]
− (I − R_{0})q + c_{0} = 0  (15)

has roots on [0, a], where B, L, M, K are as in the above lemma. Denote by q_{0}^{∗} the least of them.

(c) The following conditions are satisfied for all n ≥ 0

R_{n+1} < α_{n+1},  (16)
0 < c_{n+1} ≤ β_{n+1}  (17)

and

0 ≤ p_{n+1} ≤ p_{n} + c_{n}.  (18)

(d) The linear operators T_{n} are boundedly invertible for all n ≥ 0, and set G_{n} = T_{n+1}T_{n}^{−1} (n ≥ 0).

(e) Condition (8) is satisfied.

Then, the equation

g_{n}(q) = BG_{n}T_{n}[L(p_{n} + q) − L(p_{n}) − L′(p_{n})q + M(p_{n} + q) − M(p_{n}) + K(p_{n} + q) − K(p_{n})]
− (I − R_{n})q + c_{n} = 0  (19)

has solutions in [0, a] for every n ≥ 0 and denoting by q_{n}^{∗} the least of them, we have

∑_{j=n,...,∞} c_{j} ≤ q_{n}^{∗} (n ≥ 0).  (20)

Proof. Let us assume that for some nonnegative integer n, I −R_{n} > 0, g_{n}(q) has roots on [0, a] and denote by q_{n}^{∗} the least of them. We use induction on n. We also observe that this is true by hypothesis (b) for n = 0. Using (14), (16), (17), (18), the lemma, and setting c = c_{n}, c_{+} = c_{n+1}, R = R_{n}, R_{+} = R_{n+1}, G = G_{n} we deduce that q_{n+1}^{∗} exists, and

c_{n+1} ≤ q_{n+1}^{∗} ≤ q_{n}^{∗} − c_{n}.  (21)

The induction is now complete and (20) follows immediately from (21).

That completes the proof of the theorem. From now on we assume that X is a Banach space with a convergence structure in the sense of [4].

The following result is an immediate consequence of Theorem 1.

\underline{Theorem 2}. Assume:

(a) the hypotheses of Theorem 1 are satisfied;

(b) there exists a sequence {x_{n}} (n ≥ 0) in a Banach space X with a convergence structure such that |x_{n+1} − x_{n}| ≤ c_{n}. Then

(i) the sequence {x_{n}} (n ≥ 0) converges to some point x^{∗}; (ii) moreover the following error bounds are true

|x^{∗} − x_{n}| ≤ q_{n}^{∗}  (22)

and

|x^{∗} − x_{n+1}| ≤ q_{n}^{∗} − c_{n} for all n ≥ 0.  (23)

We can introduce the main result:

\underline{Theorem 3}. Let X be a Banach space with convergence structure (X, V, E) with V = (V, C, ∥ ∥_{v}), an operator F ∈ C^{1}(D → X) with D ⊆ X, an operator Q ∈ C(D → X), an operator A(x) ∈ C(X → D), an operator L ∈ C^{1}(V_{1} → V) with V_{1} ⊆ V, an operator M ∈ C(V_{1} → V), an operator K ∈ L_{+}(V), and a point a ∈ C such that the following conditions are satisfied:

(a) the inclusions U(a) ⊆ D and [0, a] ⊆ V_{1} are true;

(b) L is order-convex on [0, a] and satisfies

K + L′(|x| + |y|) − L′(|x|) ∈ B(A(x) − F′(x + y))  (24)

for all x, y ∈ U(a) with |x| + |y| ≤ a;

(c) M satisfies the condition

0 ≤ (Q(x) − Q(x + y), M(|x| + |y|) − M(|x|) ∈ E, M(0) = 0  (25)

for all x, y ∈ U(a) with |x| + |y| ≤ a;

(d) for the sequences {c_{n}}, {T_{n}}, {R_{n}}, {G_{n}}, {p_{n}} (n ≥ 0) the hypotheses (14), (b), (16), (18) and (d) of Theorem 1 are satisfied;

(e) the following conditions are also satisfied

|δ_{n}| ≤ c_{n} ≤ T_{n}| − (F (x_{n}) + Q(x_{n}))| ≤ γ_{n} ≤ β_{n} (n ≥ 1),  (26)
| − r_{n}| ≤ T_{n}^{−1}R_{n}c_{n}  (27)

where

γ_{n} = T_{n}[L(p_{n} +c_{n})−L(p_{n})−L′(p_{n})c_{n} +M(p_{n} +c_{n})−M(p_{n})+K(p_{n} +c_{n})−K(p_{n})]+R_{n}c_{n} (n ≥ 1).

(28)

Then

(i) the sequence {x_{n}} (n ≥ 0) generated by

x_{n+1} = x_{n} + δ_{n} with x_{0} = 0

remains in \overline{U}(x_{0}, t_{0}^{∗}) and converges to a solution x^{∗} of equation F (x) = 0; (ii) moreover, the error estimates (22) and (23) are true where q_{n}^{∗} is the least root in [0, a] of the function

g_{n}(q) defined in (19), with p_{n} = ∥x_{n} − x_{0}∥ (n ≥ 0).

Proof. Let us assume that x_{n}, x_{n+1} ∈ U(x_{0}, q_{0}^{∗}), where the existence of q_{0}^{∗} is guaranteed from hypotheses (d). We note that |δ_{0}| ≤ c_{0}. Using the approximation

−(F (x_{n+1}) + Q(x_{n+1})) = (F (x_{n}) − F (x_{n+1}) + A(x_{n})(x_{n+1} − x_{n})) + (Q(x_{n}) − Q(x_{n+1})) − r_{n}, (29)

(24), (25), (27) and setting p_{n} = |x_{n} − x_{0}|, we obtain in turn

| − (F (x_{n+1}) + Q(x_{n+1}))| ≤ |F (x_{n}) − F (x_{n+1}) + A(x_{n})(x_{n+1} − x_{n})| + |Q(x_{n}) − Q(x_{n+1})| + | − r_{n}|

≤ ∫_{0}^{1} [L′(p_{n} + t|x_{n+1} − x_{n}|) − L′(p_{n}) + K]|x_{n+1} − x_{n}| dt + M(p_{n} + |x_{n+1} − x_{n}|) − M(p_{n}) + | − r_{n}|

≤ L(p_{n} + c_{n}) − L(p_{n}) − L′(p_{n})c_{n} + Kc_{n} + M(p_{n} + c_{n}) − M(p_{n}) + T_{n}^{−1}R_{n}c_{n}.

Hence, by (26) we get

c_{n+1} ≤ T_{n+1}| − (F (x_{n+1}) + Q(x_{n+1}))| ≤ γ_{n} ≤ β_{n} (n ≥ 1),

which shows (17).

It can easily be seen that by using induction on n, the hypotheses of Theorem 2 are satisfied. Hence, by (24) and (27) the iteration {x_{n}} (n ≥ 0) remains in U(x_{0}, q_{0}^{∗}) and converges to x^{∗} so that (22) and (23) are satisfied. Moreover, from the estimate

| − (F (x_{n}) + Q(x_{n}))| ≤ |A(x_{n}) − F′(x_{n})|c_{n} + |F′(x_{n})|c_{n} + | − r_{n}|,

(24), (27), the continuity of F, F′, A, T_{n}, R_{n} and c_{n} → 0 as n → ∞, we deduce that

F (x^{∗}) + Q(x^{∗}) = 0.

That completes the proof of the theorem.

IV. APPLICATIONS

We will complete this study with an example that shows how to choose L, M, in practical applications. For simplicity, we assume that A(x) = F′(x) for all x ∈ D.

Example. We discuss the case of a real Banach space with norm ∥ ∥. Assume that F′(0) = I and there exists a monotone operator

f : [0, a] → IR

such that

∥F′′(x)∥ ≤ f(∥x∥) for all x ∈ U(a)  (30)

and a continuous nondecreasing function ℓ on [0, r], r ≤ a such that

∥Q(x) − Q(y)∥ ≤ ℓ(r)∥x − y∥  (31)

for all x, y ∈ U(\frac{r}{2}).

We showed in [3], (see also [9]) that (18) implies that

∥Q(x + e) − Q(x)∥ ≤ h(r + ∥e∥) − h(r), x ∈ U(a), ∥e∥ ≤ a − r,  (32)

where

h(r) = ∫_{0}^{r} ℓ(t) dt.  (33)

Conversely, it is not hard to see that we may assume, without loss of generality, that the function h and all functions h(r + t) − h(r) are monotone in r. Hence, we may assume that h(r) is convex and hence differentiable from the right. Then, as in [9], we show that (32) implies (31) and ℓ(r) = h′(r + 0). Hence, we can set

L_{1}(q) = L(q) = ∥F (0) + Q(0)∥ + ∫_{0}^{q} ds ∫_{0}^{s} f(t) dt  (34)

and

M(q) = ∫_{0}^{q} ℓ(t) dt.  (35)

Define the functions f_{1}, f_{2}, f_{3} on [0, a] by

f_{1}(q) = L(q) − q, f_{2}(q) = f_{1}(q) + h(q) and f_{3}(q) = ∫_{0}^{q} f(t) dt.

Choose B = T_{0} = 1, R_{0} = K = 0 and p_{0} = 0. Then by (15) we get

g_{0}(q) = f_{2}(q).

It can easily be seen that with the above choices of L and M conditions (24) and (25) are satisfied. Suppose that the function g_{0} has a unique zero q_{0}^{∗} in [0, a] and g_{0}(a) ≤ 0. It is then known [3], [9] that

equation (1) admits a solution x^{∗} in U(q_{0}^{∗}), this solution is unique in U(a), and the iteration {x_{n}} (n ≥ 0) given by (2) is well defined, remains in U(q_{0}^{∗}) for all n ≥ 0 and converges to x^{∗}. By applying the Banach lemma on invertible operators we can show that A(x_{n}) is invertible and ∥A(x_{n})^{−1}∥ ≤ −f′_{1}(∥x_{n}∥)^{−1} = T_{n} (n ≥ 0).

Moreover, suppose that (30) is satisfied. Furthermore, assume that instead of conditions (16) and (17), the weaker condition (10) is satisfied. Using (30) and the approximation

r_{n} = [(F′(x_{n}) − F′(x_{0})) + F′(x_{0})]δ_{n} + F (x_{n}) + Q(x_{n})

we obtain

∥r_{n}∥ ≤ (f_{3}(∥x_{n}∥) + 1)c_{n} + T_{n}^{−1}γ_{n} (n ≥ 1).

The above estimate provides us with a possible (but not the only) choice for the R_{n}’s. Indeed, (27) will be true if the R_{n}’s (n ≥ 0) can be chosen so that

(f_{3}(∥x_{n}∥) + 1)c_{n} + T_{n}^{−1}γ_{n} ≤ T_{n}^{−1}R_{n}c_{n} (n ≥ 1).

Using the above choices and Theorem 3, it finally also follows that estimates (22) and (23) are satisfied for all n ≥ 0.

REFERENCES

[1] Argyros, I.K. The secant method in generalized Banach spaces, Appl. Math. Comp. 39, (1990), 111–121.

[2] . Newton-like methods in generalized Banach spaces, Functiones et Approximatio Commentarii Mathematici, XXII, (1993), 13–20.

[3] Argyros, I.K. and Szidarovszky, F. The Theory and Applications of iteration methods, C.R.C. Press, Inc. Boca Raton Florida, U.S.A. 1993.

[4] Argyros, I.K. Perturbed Newton-like methods and nondifferentiable operator equations on Banach spaces with a convergence structure, Southwest Journal of Pure and Applied Mathematics (SWJPAM) Vol. 1, No. 1 (1995), 1–12.

[5] Kantorovich, L.V. and Akilov, G.P. Functional Analysis in normed spaces, Academic Press, New York, 1978.

[6] Meyer, P.W. Newton’s method in generalized Banach spaces, Numer. Funct. Anal. Optimiz. 9 (3 and 4), (1987), 249–259.

[7] . A unifying theorem for Newton’s method, Numer. Funct. Anal. Optimiz. 13 (5 and 6), (1992), 463–473.

[8] Moret, I. A Kantorovich-type theorem for inexact Newton methods, Numer. Funct. Anal. and Optimiz. 10 (3 and 4), (1989), 351–365.

[9] Zabrejko, P.P. and Nguen, D.F. The majorant method in the theory of Newton-Kantorovich approximations and the Ptak error estimates, Numer. Funct. Anal. Optimiz. 9 (5 and 6), (1987), 671–684.