Zeitschrift für Analysis und ihre Anwendungen

Journal for Analysis and its Applications Volume 18 (1999), No. 3, 785–792

Concerning the Convergence of a Modified Newton-Like Method

Ioannis K. Argyros

Abstract. We provide sufficient convergence conditions for a certain Newton-like method to a locally unique solution of a nonlinear equation in a Banach space. We assume that the Fréchet-derivative of the operator involved satisfies in some sense uniformly continuous conditions, which are weaker than earlier ones. We show that our results apply where earlier ones fail. Finally, we solve a nonlinear integral equation of Uryson-type that cannot be solved using Proposition 2 in [10].

Keywords: Modified Newton-like method, Banach spaces, Uryson integral equations, uniformly continuity

AMS subject classification: 65 J 15, 65 B 05, 47 H 17, 49 D 15

1. Introduction

In this study we are concerned with the problem of approximating a locally unique solution x^{∗} of the equation

F (x) = 0,  (1)

where F is a Fréchet-differentiable operator defined on a convex subset D of a Banach space E_{1} with values in a Banach space E_{2}. We propose the modified Newton-like method

x_{n+1} = x_{n} − A^{−1}F (x_{n})  (n ≥ 0, x_{0} ∈ D)  (2)

to generate a sequence {x_{n}}_{n≥0} converging to x^{∗}. Here A ∈ L(E_{1}, E_{2}), the space of bounded linear operators from E_{1} into E_{2}. For A = F′(x_{0}) we obtain the modified Newton method, whereas for A = [x_{−1}, x_{0}; F] (divided difference of order one) we obtain the modified Secant method. Several other choices are also possible [5, 6, 8, 9].

Let x_{0} ∈ D, U(x_{0}, R) = {x ∈ E_{1}| ∥x − x_{0}∥ < R} ⊆ D, and assume that

∥A^{−1}(F′(x) − F′(x_{0}))∥ ≤ w(∥x − x_{0}∥)  (x ∈ Ū(x_{0}, r); 0 ≤ r < R)  (3)

for some monotonically increasing function w satisfying

lim_{t→0} w(t) = 0.  (4)

I. K. Argyros: Cameron Univ., Dept. Math., Lawton, OK 73505, U.S.A.

ISSN 0232-2064 / $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag Berlin

In the elegant paper [2] stronger conditions of the form

∥F′(x_{1}) − F′(x_{2})∥ ≤ v(∥x_{1} − x_{2}∥)  (x_{1}, x_{2} ∈ U(x_{0}, R))  (5)

or, more generally,

∥F′(x_{1}) − F′(x_{2})∥ ≤ v_{1}(r, ∥x_{1} − x_{2}∥)  (x_{1}, x_{2} ∈ Ū(x_{0}, r); 0 ≤ r < R)  (6)

have been used for some monotonically increasing positive functions v and v_{1} with

lim_{t→0} v(t) = 0 = lim_{t→0} v_{1}(r, t)  (0 ≤ r < R),  (7)

in connection with Newton’s method

x_{n+1} = x_{n} − F′(x_{n})^{−1}F (x_{n})  (n ≥ 0, x_{0} ∈ D).  (8)

Conditions of type (5) and (6) have also been studied in the special cases when v(t) = kt^{λ} or v_{1}(r, t) = k(r)t^{λ} for λ ∈ [0, 1] in connection with (8) or more generally with Newtonlike methods of the form

x_{n+1} = x_{n} − A(x_{n})^{−1}F (x_{n})  (n ≥ 0, x_{0} ∈ D  (9)

[3 - 6]. Here for each fixed x ∈ D, A(x) ∈ L(E_{1}, E_{2}).

A semilocal convergence theorem is provided here for method (2) under the weak condition (3). In order to demonstrate the importance of condition (3), we apply our results to solve a nonlinear integral equation of Uryson type using method (2) for A = F′(x_{0}). At the same time we show that corresponding results in the above-mentioned papers do not guarantee the convergence of method (2) to a solution of equation (1). Finally, we note that the results obtained here are in an affine invariant form, whereas the ones in [2, 8, 10] are not. The advantages of results given in affine invariant form over corresponding ones not in this form have been explained in [5, 7].

For example, the Newton-Kantorovich theorem guarantees the existence of a solution of equation (1) if

2∥x_{1} − x_{0}∥ ∥F′(x_{0})^{−1}∥ℓ_{1} ≤ 1  or  2∥x_{1} − x_{0}∥ℓ ≤ 1,

where

∥F′(x) − F′(y)∥ ≤ ℓ_{1}∥x − y∥ or ∥F′(x_{0})^{−1}(F′(x) − F′(y))∥ ≤ ℓ∥x − y∥

for all x, y ∈ D. However, for linear operators L_{1}, L_{2} ∈ L(E_{1}, E_{2}) we have ∥L_{1}L_{2}∥ ≤ ∥L_{1}∥ · ∥L_{2}∥. Hence if the first inequality holds above so does the second. However, the converse is not necessarily true (see [7: p. 2/Example 1]). Moreover, in some iterative methods, the generated sequence is known in some subset S of all affine transformations with domain E_{2}. In these cases, it is reasonable to require only S-invariance for the associated convergence theorems. This means that both the assumptions and the statements of the theorems should remain unaltered, when F is replaced by LF for any L ∈ S.

2. Convergence analysis

It is convenient to define the number

a = ∥A^{−1}F (x_{0})∥,  (10)

the function

f(r) = a − r + ∫_{0}^{r} w(t) dt,  (11)

the equation

f(r) = 0  (12)

and the iteration

\begin{matrix}t_{0} & = 0 \\ t_{n+1} & = t_{n} + f(t_{n}) (n ≥ 0). \end{matrix} \}  (13)

We need the following lemma concerning the convergence of iteration (13). A similar result is shown in [10: p. 675]. However, our proof is slightly difference, since we make the assumption about the existence and the uniqueness of solution r^{∗} of equation (12).

Lemma. Assume that equation (12) has a unique solution r^{∗} ∈ [0, R], and that f(R) ≤ 0. Then iteration {t_{n}}_{n≥0} generated by (13) is monotonically increasing and converges to r^{∗}.

Proof. The function g(t) = t + f(t) is clearly increasing on [0, r^{∗}] and f(t) ≥ 0 for t ∈ [0, r^{∗}]. So, if t_{k} ∈ [0, r^{∗}] for some k, we get

t_{k} ≤ t_{k} + f(t_{k}) = t_{k+1}  and  t_{k+1} = t_{k} + f(t_{k}) ≤ r^{∗} + f(r^{∗}) = r^{∗}.

This proves the lemma by induction

We can now show the main semilocal convergence theorem for method (2).

Theorem. Assume that F is Fréchet-differentiable with (3) and (4), and let f be defined by (11). Suppose that equation (12) has a unique solution r^{∗} ∈ [0, R] and f(R) ≤ 0. Then equation (1) has a solution x^{∗} ∈ Ū(x_{0}, r^{∗}); this solution is unique in U(x_{0}, R). Moreover, method (2) generates a sequence {x_{n}}_{n≥0} which converges to x^{∗}. Furthermore, the error bounds

∥x_{n+1} − x_{n}∥ ≤ t_{n+1} − t_{n}  (14)
∥x^{∗} − x_{n}∥ ≤ r^{∗} − t_{n}  (15)

hold for all n ≥ 0.

Proof. We first show estimate (14) using induction on the integer n. For n = 0,

(2) and (10) give ∥x_{1} − x_{0}∥ ≤ a = t_{1} − t_{0}, which shows (14) in this case. Suppose (14) holds for n = 0, 1, …, k − 1; this implies, in particular, that

∥x_{k} − x_{0}∥ ≤ ∥x_{k} − x_{k−1}∥ + … + ∥x_{1} − x_{0}∥
≤ (t_{k} − t_{k−1}) + … + (t_{1} − t_{0})
= t_{k} − t_{0}
= t_{k}
≤ r^{∗}.

Using the approximation

\begin{aligned}F (x_{k}) & = F (x_{k}) − F (x_{k−1}) − A(x_{k} − x_{k−1}) \\ & = ∫_{0}^{1} [F′(x_{k−1} + t(x_{k} − t_{k−1})) − A](x_{k} − x_{k−1}) dt, \end{aligned}  (16)

hypothesis (3), (13), and the induction hypothesis, we obtain in turn

\begin{aligned}∥x_{k+1} − x_{k}∥ & = ∥A^{−1}F (x_{k})∥ \\ & = ∥∫_{0}^{1} A^{−1}[F′(x_{k−1} + t(x_{k} − x_{k−1})) − A](x_{k} − x_{k−1}) dt∥ \\ & ≤ ∫_{0}^{1} ∥A^{−1}[F′(x_{k−1} + t(x_{k} − x_{k−1})) − A] · ∥x_{k} − x_{k−1}∥ dt \\ & ≤ ∫_{0}^{1} w(∥x_{k−1} + t(x_{k} − x_{k−1}) − x_{0}∥)∥x_{k} − x_{k−1}∥ dt \\ & ≤ ∫_{0}^{1} w((1 − t)∥x_{k−1} − x_{0}∥ + t∥x_{k} − x_{0}∥)∥x_{k} − x_{k−1}∥ dt \\ & ≤ ∫_{0}^{1} w((1 − t)t_{k−1} + t_{k})(t_{k} − t_{k−1}) dt \\ & = ∫_{t_{k−1}}^{t_{k}} w(t) dt \\ & = f(t_{k}) \\ & = t_{k+1} − t_{k}. \end{aligned}  (17)

Hence, estimate (14) is true for all n ≥ 0. Moreover, estimate (15) follows from (14) by using standard majorization techniques [5, 8, 10].

To show uniqueness, let us assume that y ∈ U(x_{0}, R) with F (y) = 0. Using (2), (3) and the approximation

\begin{aligned}x_{k+1} − y^{∗} & = x_{k} − y^{∗} − A^{−1}F (x_{k}) \\ & = A^{−1}[A(x_{k} − y^{∗}) − (F (x_{k}) − F (y))] \\ & = −A^{−1} [∫_{0}^{1} (F′(y + t(x_{k} − y)) − A)] (x_{k} − y) dt, \}cr \end{aligned}  (18)

we get as in (17)

∥x_{k+1} − y^{∗}∥ ≤ ∫_{0}^{1} w((1 − t)∥x_{0} − y∥ + t∥x_{k} − x_{0}∥)∥x_{k} − y∥ dt.  (19)

If y ∈ Ū(x_{0}, r^{∗}), then ∥x_{0} − y^{∗}∥ ≤ r^{∗} and (19) gives

∥x_{k+1} − y∥ ≤ w(r^{∗})∥x_{k} − y^{∗}∥ ≤ w(r^{∗})^{k+1}r^{∗}.  (20)

If y ∈ U(x_{0}, R) and r^{∗} ≠ R, then ∥y − x_{0}∥ = μR (0 < μ < 1), and (19) can give

∥x_{k+1} − y∥ ≤ (\frac{1}{R − r^{∗}} ∫_{r^{∗}}^{R} w(t) dt)^{k+1} R.  (21)

It follows from the Lemma and (11) that 0 ≤ w(t) < 1 for t ∈ [0, R]. Hence it follows from (20) and (21) that lim_{k→∞} x_{k} = y. That completes the proof of the theorem

Remark 1. It was explained in [2], why sometimes it is useful to pass from the function w to the function

w̄(r) = sup {w(u) + w(v) : u + v = r}.  (22)

Consider the function

f̄(r) = ā − r + ∫_{0}^{r} ¯ w̄(t) dt (r ∈ [0, R])

where ā = \frac{a}{1+w(a)} and ¯ w̄(r) = \frac{1}{1+w(a)} w̄(r) (r ∈ [0, R]), the equation

f̄(r) = 0

and the iteration

\begin{matrix}t̄_{0} & = 0 \\ t̄_{n+1} & = ∫ t̄_{n} ; 0 w̄(t) dt − w(a)t̄_{n} + a (n ≥ 0). \end{matrix} \}

Replace f by f̄ in the above theorem. Then it can easily be seen by following the proof of the theorem that the conclusions obtained there hold in this setting also.

The following result is a consequence of the contraction mapping principle [4, 7].

Proposition. Let

θ = sup_{x∈D_{0}} ∥I − A^{−1}F′(x)∥ < 1

where D_{0} = U(x_{0}, r_{1}) ⊆ D and r_{1} = \frac{a}{1−θ}. Then equation (1) has a unique solution x^{∗} in U(x_{0}, r_{1}). Moreover, iteration {x_{n}}_{n≥0} generated by (2) is well defined, remains in U(x_{0}, r_{1}) for all n ≥ 0 and converges to x^{∗}. Furthermore, the error bounds

∥x_{n} − x^{∗}∥ ≤ \frac{θ}{1 − θ} ∥x_{n} − x_{n−1}∥ ≤ \frac{θ^{n}}{1 − θ} ∥x_{1} − x_{0}∥ = \frac{θ^{n}a}{1 − θ}

hold for all n ≥ 1.

To compare our results with the ones obtained in [10: Proposition 2] or in [2: Theorem 1], we set A = F′(x_{0}), and assume that (6) holds for v_{1}(r, t) = k(r)t for some non-decreasing function k on [0, R]. As in [2, 10] define the function

χ(r) = a + b ∫_{0}^{r}(r − t)k(t) dt − r  (23)

where

b = ∥F′(x_{0})^{−1}∥  (24)

and the equation

χ(r) = 0.  (25)

We now provide a favorable example for our theorem.

Example. Let E_{1} = E_{2} = D = C = C[0, 1], the space of continuous functions on [0, 1] equipped with the sup-norm. Consider the nonlinear integral equation of Uryson type given by

F (x)(t) = x(t) − ∫_{0}^{1} p(t, s, x(s)) ds.  (26)

Let x_{0} = 0 and A = F′(0). Suppose p(t, s, u) = p_{1}(t)p_{2}(s)p_{3}(u) with two continuous functions p_{1}, p_{2} and p_{3} ∈ C^{2}. Setting

γ = ∫_{0}^{1} p_{2}(s) ds  and  δ = ∫_{0}^{1} p_{1}(s)p_{2}(s) ds,  (27)

using formulas (23), (25) - (29) in [1: p. 278], (10), and (24), we get the function

k(r) = ∥p_{1}∥_{C} · γ · sup_{∥u∥≤r} ∥p′′_{3}(u)∥  (28)

and the constants

a = \frac{γp_{3}(0)}{1 − δp′_{3}(0)}∥p_{1}∥_{C}  (29)
b = 1 + \frac{γp′_{3}(0)}{1 − δp′_{3}(0)}∥p_{1}∥_{C}  (30)

provided that

δp′_{3}(0) < 1.  (31)

Choose

p_{1}(s) = \frac{1}{(s + 1)\sqrt{s + 1}}, p_{2}(s) = β\sqrt{s + 1}, β = \frac{3}{20(2\sqrt{2} − 1)}, p_{3}(s) = e^{s}.

Then by (27) we get γ = \frac{2}{3}β(2\sqrt{2} − 1) and δ = β ln 2. Condition (31) becomes

δp′_{3}(0) = β ln 2 = .5686421 < 1,

which is true. Moreover, by (28) - (30) and the above values we get

a = \frac{2β(2\sqrt{2} − 1)}{3(1 − β ln 2)} = .0027389  and  b = 1 + \frac{2β(2\sqrt{2} − 1)}{3(1 − β ln 2)} = 1.0027389

and k(r) = \frac{b}{10}e^{r}. By (23) and the above values we get

χ(r) = .1106029e^{r} − 1.1106029r − .0045736.

It is simple calculus to show that min_{r∈[0,+∞)} χ(r) = .1060293 > 0, χ is increasing on

[2.306712, +∞) and decreasing on [0, 2.306712]. Proposition 2 in [10: p. 674] fails to

Convergence of a Newton-Like Method 791

apply since χ(r) has no zero in the interval [0, R] and χ(R) > 0 for all R ∈ [0, +∞). However, our theorem applies.

Indeed, by setting

w(r) = \frac{b}{10}r,  (32)

using (11) and the above values we get f(r) = \frac{b}{20}r^{2} − r + a. The hypothesis of our theorem is now satisfied if we set

r^{∗} = .0027395  and  R = 19.942632.

Hence, according to our theorem iteration (2) converges to a solution x^{∗} ∈ Ū(0, r^{∗}) of equation F (x)(t) = 0 where F is given by (26). Moreover, x^{∗} is the unique solution of the same equation in U(0, R). Furthermore, estimates (14) and (15) hold in this case for all n ≥ 0.

Remark 2. Using the choices of the w-functions given in the example we see that k̄(r) = \frac{1}{10} ≤ k(r) for r ∈ [0, R] and by (11) and (23) we get

f(r) ≤ χ(r) for all r ∈ [0, R].

If χ(R) ≤ 0, then f(R) ≤ 0 also. That means that whenever Proposition 2 in [10: p. 674] applies so does our theorem. The converse is not true as we showed in the above example.

Remark 3. Assume that the k-functions in Remark 2 are constants (Lipschitz) denoted by k̄ and k, respectively. The Newton-Kantorovich conditions in this case become

h̄ = k̄ · η ≤ \frac{1}{2}  and  h = k · η ≤ \frac{1}{2}.

Since in general k̄ ≤ k if the second inequality is satisfied so does the first one. However, the converse is not true in general. That means that our conditions are weaker than the corresponding ones in Theorems 1 - 3 and 4 (1.XVIII) of [8].

References

[1] Appell, J., De Pascale, E. and P. P. Zabrejko: On the application of the Newton-Kantoro-vich method to nonlinear integral equations of Uryson type. Numer. Funct. Anal. Optimiz. 12 (1991), 271 – 283.

[2] Appell, J., De Pascale, E., Lysenko, J. V. and P. P. Zabrejko: New results on Newton-Kantorovich approximations with applications to nonlinear integral equations. Numer. Funct. Anal. Optimiz. 18 (1997), 1 – 17.

[3] Argyros, I. K.: A convergence theorem for Newton-like methods under generalized Chen-Yamamoto-type assumptions. Appl. Math. Comp. 62 (1994), 1 – 15.

[4] Argyros, I. K. and F. Szidarovszky: On the convergence of modified contractions. J. Comp. Appl. Math. 55 (1994), 183 – 189.

[5] Argyros, I. K. and F. Szidarovszky: The Theory and Applications of Iteration Methods. Boca Raton (Florida, USA): C.R.C. Press Inc. 1993.

[6] Chen, X. T. and Yamamoto: Convergence domains of certain iterative methods for solving nonlinear equations. Numer. Funct. Anal. Optimiz. 10 (1989), 37 – 48.

[7] Deuflhard, P. and G. Heindl: Affine invariant convergence theorems for Newton’s method and extensions to related methods. SIAM J. Numer. Anal. 16 (1979), 1 – 10.

[8] Kantorovich, L. V. and G. P. Akilov: Functional Analaysis in Normed Spaces. New York: Pergamon Press 1964.

[9] Szidarovszky, F. and O. Palusinski: A special matrix equation and its applications in microelectronics. Appl. Math. Comp. 64 (1994), 115 – 119.

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

Received 22.01.1998; in revised form 01.02.1999