Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1997, pp. 23–29. Submitted: March 15, 1997. Published: July 28, 1997.

A NEW CONVERGENCE THEOREM FOR STEFFENSEN’S

METHOD ON BANACH SPACES AND APPLICATIONS

Ioannis K. Argyros

Abstract. We provide sufficient conditions for the convergence of Steffensen’s method to a locally unique solution of a nonlinear operator equation on a Banach space. We use a fixed point theorem and a special choice of divided differences. Some applications of our results are also provided.

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

Key Words and Phrases. Steffensen’s method, fixed point theorem, Banach space, divided differences.

I. INTRODUCTION

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

(1)  f(x) = 0,

where f is a continuous operator defined on a closed convex domain D of a Banach space E_{1} with values in a Banach space E_{2}.

We use Steffensen’s method

(2)  x_{n+1} = x_{n} − [x_{n}, g(x_{n}); f]^{−1}f(x_{n}) (n ≥ 0)

to generate a sequence converging to x^{∗}.

Here [x, y; f] ∈ L(E_{1}, E_{2}) is a divided difference of order one for the operator f on the points x, y ∈ D. Operator g: D ⊆ E_{1} → E_{1} is given and continuous on D. For g(x) = x (x ∈ D), method (2) reduces to Newton’s method [3], [4] provided that f is Fréchet-differentiable on D. If g(x_{n}) = x_{n−1} (n ≥ 0) we obtain secant method [3], [5] from (2). Several other choices for g are possible, including the most popular given by g(x) = x − f(x) (x ∈ D).

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}1997 Cameron University

We define the operator P: D ⊆ E_{1} → E_{2} by

(3)  P (x) = x − [x, g(x); f]^{−1}f(x),

in which case (2) can also be written in the form

(4)  x_{n+1} = P (x_{n}) (n ≥ 0) (x_{0} ∈ D).

A solution x^{∗} of equation (1) is said to be accessible from x_{0} by Steffensen’s method (2) if

(5)  x^{∗} = lim_{n→∞} x_{n} = lim_{n→∞} P^{n}(x_{0}).

The region of accessibility of x^{∗} by method (2) is defined to be the set of all x_{0} such that (5) is true.

Let us define operator L_{f} ∈ L(E_{1}, E_{2}) by

(6)  L_{f}(x) = P′(x) (x ∈ D).

This operator is the degree of logarithmic convexity of f on x and is a measure of the convexity of the function.

Here we assume that the divided difference [x, y; F] satisfies a certain Lipschitz condition that allows us to choose

(7)  [x, g(x); f] = ∫_{0}^{1} f′(x + t(g(x) − x))dt for all x, g(x) ∈ D.

Steffensen’s method (2) has been examined extensively under various assumptions (see [1]–[3], [6], [7] and the references there). In the above-mentioned references the authors have found a ball U(x_{0}, p) = {x ∈ E_{1} | ∥x − x_{0}∥ ≤ p} ⊆ D such that x^{∗} ∈ U(x_{0}, p) and method (2) converges to x^{∗} starting at x_{0} ∈ D. Here using the fixed point theorem [3], [5] on (4), and (6) we provide sufficient convergence conditions for the convergence of Steffensen’s method to x^{∗} ∈ U(x_{0}, q) for q > p. This way the region of convergence is enlarged.

II. CONVERGENCE ANALYSIS

Definition. The first order divided difference of f on the points u, v ∈ E_{1} is an application [u, v; f] ∈ L(E_{1}, E_{2}) which satisfies:

(i) [u, v; f](v − u) = f(v) − f(u); (8) (ii) if f is Fréchet differentiable at u ∈ E_{1} then [u, u; f] = f′(u). Let a, b, c, α be nonnegative numbers, x_{0} ∈ D be such that the inverse of

[x_{0}, g(x_{0}); f] exists on D, and define parameters d, δ, β, ε by

(9)  d = a(1 + b), δ = ∥[x_{0}, g(x_{0}); f]^{−1}f(x_{0})∥, β = a∥x_{0} − g(x_{0})∥

and

(10)  ε = \frac{∥x_{0} − g(x_{0})∥}{1 − b} (for 0 ≤ b < 1).

Moreover define real functions h_{1}, h_{2}, h_{3}, h_{4} on [0, +∞) by

(11)  h_{1}(r) = r − \frac{1}{d},

(12)  h_{2}(r) = 2d^{2}r^{2} − d(3 + c − β)r + 1 − β − dδ,
(13)  h_{3}(r) = 2d^{2}r^{3} − d(c + δd − β + 3)r^{2} + (1 − β + dδ)r − δ

and

(14)  h_{4}(r) = r − ε.

For our convergence theorem that follows we would like to be able to find an interval I which is a subset of the nonnegative axis such that

(15)  h_{1}(r) < 0,
(16)  h_{2}(r) > 0,
(17)  h_{3}(r) ≥ 0,
(18)  h_{4}(r) ≥ 0

and

(19)  U(x_{0}, r) ⊆ D

for all r ∈ I.

The example at the end of this study shows that this can happen.

We state and prove the following semilocal convergence theorem for method (2):

Theorem 1. Let f: D ⊆ E_{1} → E_{2}, g: D ⊆ E_{1} → E_{1} be continuous operators, D a closed convex subset of E_{1}, and E_{1}, E_{2} Banach spaces. Assume:

(a) f is twice and g once Fréchet-differentiable on D;

(b) there exist a, b, c > 0, x_{0} ∈ D such that

(20)  ∥[x_{0}, g(x_{0}); f]^{−1}([x, y; f] − [v, w; f])∥ ≤ a(∥x − v∥ + ∥y − w∥),
(21)  ∥g(x) − g(y)∥ ≤ b∥x − y∥, (b < 1),
(22)  ∥[x_{0}, g(x_{0}); f]^{−1}(f(x) − f(y))∥ ≤ c∥x − y∥

and

(23)  ∥[x_{0}, g(x_{0}); f]^{−1}([x, x, g(x); f] + [x, g(x), g(x); f]g′(x))∥ ≤ α

for all x, y, v, w ∈ D;

(c) conditions (15)–(19) hold on some interval I ⊆ R^{+} ∪ {0};

(d) hypotheses (c) and (d) of the Proposition hold.

Then the following hold:

(i) ∥P′(x)∥ ≤ c(r) < 1 (24) and

(25)  r ≥ \frac{δ}{1 − c(r)}

for all r ∈ I, where

(26)  c(r) = \frac{1}{(1 − dr)^{2}} [(1 − dr)(dr + β) + α(cr + δ)].

(ii) P has a unique fixed point x^{∗} in U(x_{0}, r).

(iii) Iteration x_{n+1} = P (x_{n}) (n ≥ 0) converges to x^{∗}. Moreover the following error bound holds for all n ≥ 0

(27)  ∥x_{n} − x^{∗}∥ ≤ c^{n}(r)r, r ∈ I.

Proof. (i) Let f(x), g(x) ∈ U(x_{0}, r) (r ∈ I) whenever x ∈ U(x_{0}, r). Using (3) and (7), we obtain

(28) P′(x) = I − ([x, g(x); f]^{−1})′f(x) − [x, g(x); f]^{−1}f′(x)
= I − [x, g(x); f]^{−1}[x, g(x); f]′[x, g(x); f]^{−1}f(x)
− [x, g(x); f]^{−1}f′(x)
= [x, g(x); f]^{−1}[x_{0}, g(x_{0}); f][x_{0}, g(x_{0}); f]^{−1}{([x, g(x); f] − f′(x)])
− ∫_{0}^{1} f′′(x + t(g(x) − x))(I + t(g′(x) − I))dt·
· [x, g(x); f]^{−1}[x_{0}, g(x_{0}); f][x_{0}, g(x_{0}); f]^{−1}f(x)}.

By (15), (20), (21) and the estimate

∥[x_{0}, g(x_{0}); f]^{−1}([x, g(x); f] − [x_{0}, g(x_{0}); f])∥ ≤ a(∥x − x_{0}∥ + ∥g(x) − g(x_{0})∥)
≤ a(r + br) = dr < 1,

and from the Banach lemma on invertible operators [3], [5] it follows that [x, g(x); f]^{−1} exists (x ∈ U(x_{0}, r) (r ∈ I)) and

(29)  ∥[x, g(x); f]^{−1}[x_{0}, g(x_{0}); f]∥ ≤ (1 − dr)^{−1}.

Condition (21) implies that f′(x) = [x, x; f] (x ∈ D) [3], [5], and

∥[x_{0}, g(x_{0}); f]^{−1}([x, g(x); f] − [x, x; f])∥ ≤ a∥x − g(x)∥

(30) ≤ a(∥x − x_{0}∥ + ∥x_{0} − g(x_{0})∥ + ∥g(x) − g(x_{0})∥) ≤ a(r + ∥x_{0} − g(x_{0})∥ + br).

Moreover by (20)–(23) and (29), the second member inside the braces in (28) is bounded above by

(31)  α(1 − dr)^{−1}(cr + δ).

Finally using majorizations (29), (30), and (31), (28) gives

∥P′(x)∥ ≤ c(r) (r ∈ I),

where function c(r) is given by (26). It now follows easily from (15) and (16) that c(r) ∈ [0, 1) which shows (24). Estimate (25) reduces to showing (17) which is true by hypothesis.

(ii) It follows from (18), (25) and (2) for n = 0 that ∥x_{1} − x_{0}∥ ≤ (1 − c(r))r ≤ r, and

∥g(x_{0}) − x_{0}∥ ≤ (1 − b)r < r,

which imply x_{1}, g(x_{0}) ∈ U(x_{0}, r). For all positive integers smaller or equal to n assume that

x_{n} ∈ U(x_{0}, r) and ∥x_{n} − x_{0}∥ ≤ (1 − c^{n}(r))r ≤ r.

Then we can get

∥g(x_{n}) − x_{0}∥ ≤ ∥g(x_{n}) − g(x_{0})∥ + ∥g(x_{0}) − x_{0}∥ ≤ b∥x_{n} − x_{0}∥ + ∥g(x_{0}) − x_{0}∥
≤ br + ∥g(x_{0}) − x_{0}∥ ≤ r (by (18)).

That is g(x_{n}) ∈ U(x_{0}, r). Using (4) and (24) we obtain

(32) ∥x_{n+1} − x_{n}∥ = ∥P (x_{n}) − P (x_{n−1})∥ ≤ sup_{y∈[x_{n−1},x_{n}]} ∥P′(y)∥ ∥x_{n} − x_{n−1}∥
≤ c(r)∥x_{n} − x_{n−1}∥ (r ∈ I).

Therefore we can obtain in turn

∥x_{n+1} − x_{n}∥ ≤ c(r)∥x_{n} − x_{n−1}∥ ≤ ⋯ ≤ c^{n}(r)∥x_{1} − x_{0}∥ = c^{n}(r)(1 − c(r))r,

and

∥x_{n+1} − x_{0}∥ ≤ ∥x_{n+1} − x_{n}∥ + ∥x_{n} − x_{0}∥ ≤ c^{n}(r)(1 − c(r))r + (1 − c^{n}(r))r
= (1 − c^{n+1}(r))r ≤ r.

That is we have shown x_{n} ∈ U(x_{0}, r) and ∥x_{n} − x_{0}∥ ≤ (1 − c^{n}(r))r ≤ r for all n ∈ N. From (32) it now follows that for m, n ∈ N

(33)  ∥x_{n+m} − x_{n}∥ ≤ (1 − c^{m}(r))c^{n}(r)r.

It follows from (33) that {x_{n}} (n ≥ 0) is a Cauchy sequence in a Banach space E_{1} and as such it converges to some limit x^{∗}. Using the continuity of f and g, (4) gives P (x^{∗}) = x^{∗}. To show uniqueness, assume y^{∗} ∈ U(x_{0}, r) and P (y^{∗}) = y^{∗}. Then by (24) we get

∥x^{∗} − y^{∗}∥ = ∥P (x^{∗}) − P (y^{∗})∥ ≤ sup_{z∈[x^{∗},y^{∗}]} ∥P′(z)∥ ∥x^{∗} − y^{∗}∥
≤ c(r)∥x^{∗} − y^{∗}∥

which shows x^{∗} = y^{∗}.

Finally by letting m → ∞ in (33) we obtain (27).

That completes the proof of Theorem 1.

The region of accessibility to x^{∗} can be extended also to a ball around x_{0} in a different way.

Theorem 2. Under the hypotheses of Theorem 1 iteration y_{n+1} = P (y_{n}), y_{0} ∈ U(x_{0}, r) (r ∈ I) converges to x^{∗}. Moreover the following error bounds hold for all n ≥ 0

∥x^{∗} − y_{n}∥ ≤ \frac{c^{n}(r)}{1 − c(r)}∥y_{1} − y_{0}∥

and

∥x^{∗} − y_{n}∥ ≤ c^{n}(r)∥x^{∗} − y_{0}∥.

Proof. For x ∈ U(x_{0}, r) we obtain by (3) and (24) that

∥x_{1} − p(x)∥ = ∥p(x_{0}) − p(x)∥ ≤ c(r)∥x − x_{0}∥ ≤ c(r)r.

That is P maps U(x_{0}, r) into U(x_{1}, c(r)r) with U(x_{1}, c(r)r) ⊆ U(x_{0}, r). Hence P: U(x_{0}, r) → U(x_{0}, r) is a contraction, with contraction factor c(r) < 1.

The result follows from the contraction mapping principle [3], [5].

We complete our study with a simple example that shows that our convergence ball includes the ones found in earlier results [6], [7].

Example. Let E_{1} = E_{2} = R, D = [−.1, .1], x_{0} = .01 and define f(x): D → E_{2} by

(34)  f(x) = x − x^{2}.

Then we have in turn

g(x) = x − f(x) = x − (x − x^{2}) = x^{2},

[x, y; f] = \frac{f(x) − f(y)}{x − y} = 1 − (x + y), [x, x, g(x); f] = −1,

[x, g(x), g(x); f]g′(x) = \frac{2x(x + 3)}{x − 1}, (x ≠ 0), α = 1.7061206,

a = ∥[x_{0}, g(x_{0}); f]^{−1}∥ = |\frac{1 − x_{0}}{1 − 2x_{0} + x_{0}^{3}} | = 1.010203,

|g(x) − g(y)| = |x + y| · |x − y| ⇒ b = .2,

|f(x) − f(y)| = |1 − (x + y)| |x − y| ⇒ c = d = 1.4546923,
δ = β = .010001 and ε = .012375.

The hypotheses of Theorem 1 are satisfied if h_{1}(r) = r − .6874306 < 0, h_{2}(r) = 4.2322594r^{2} − 6.465451r + .9754506 > 0, h_{3}(r) = 4.2322594r^{3} − 6.4866216r^{2} + 1.0045605r − .010001 ≥ 0 and h_{4}(r) = r − .012375 ≥ 0 for r belonging in a suitable subset I of the nonnegative axis, and such that U(x_{0}, r) ⊆ D. It is simple algebra to show that these conditions are satisfied if we set

(35)  I = [.012375, .09].

It follows from Theorem 2 and (35) that iteration y_{n+1} = P (y_{n}) converges to a solution x^{∗} = 0 of equation f(x) = 0, where f is given by (24) provided that

(36)  y_{0} ∈ [−.08, .1] = I_{A}.

To compare our results with the ones obtained in [6, p. 858] (similarly for [7]), we first note that no uniqueness result was given there. Moreover the convergence ball is U(.01, .039802). That means convergence is assured for

y_{0} ∈ [−.029802, .049802] = I_{P}

and by (36)

I_{P} ⊆ I_{A}.

Hence we showed that there exist infinitely many new starting points y_{0} ∈ I_{A} − I_{P} for which the convergence of iteration y_{n+1} = P (y_{n}) is assured via Theorem 2, whereas this is not the case for Theorem 1 in [6, p. 858].

REFERENCES

[1] Argyros, I.K. An error analysis for Steffensen’s method, Revue d’analyse Numerique et de theorie de l’approximation (to appear).

[2] Argyros, I.K. An error analysis for the Steffensen method under generalized Zabrejko-Nguen-type assumptions, Revue d’analyse Numerique et de theorie de l’approximation, 25, 1–2, (1996), 11-22.

[3] Argyros, I.K. and Szidarovszky, F. The Theory and Application of Iteration Methods, C.R.C. Press, Inc., Boca Raton, Florida, 1993.

[4] Cǎtinaş, E. On some iterative methods for solving nonlinear equations, Revue d’analyse Numerique et de theorie de l’approximation, 23, 1, (1994), 47–53.

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

[6] Pǎvǎloiu, I. Sur la methode de Steffensen pour la resolution des equations operationnelles nonlinearies, Revue Roumaine de Mathematiques pures et appliquees, XIII, 1, (1968), 149–158.

[7] Pǎvǎloiu, I. Sur une generalisation de la methode de Steffensen, Revue d’analyse Numerique et de theorie de l’approximation, 21, 1, (1992), 59–65.