On a generalization of Steffensen's method

Ion Pavaloiu
(Cluj-Napoca)

Either $X$ a Banach space and

(1)

f\left(x\right)=\theta

an equation, where $f:X\rightarrow X$ is an application and $\theta$ is the zero element of the space $X$ .

Let us designate by $\left[u,v;f\right]$ the first-order divided difference of the application $f$ on the points $u,v\in X$ and by $\left[u,v,w;f\right]$ the second-order divided difference of this application on the points $u,v,w\in X$ . These differences were introduced in the works [ 1 ] , [ 2 ] , [ 5 ] , [ 6 ] , [ 7 ] . Let us assume their symmetry as functions of the points on which they are defined. Beside equation ( 1 ) we consider an application $g:X\rightarrow X$ with the help of which we construct the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the following iterative process:

(2)

x_{n+1}=x_{n}-\left[x_{n},g\left(x_{n}\right);f\right]^{-1}f\left(x_{n}\right)% ,\qquad n\in\mathbb{N}

$x_{0}$ being an arbitrary element of $X$ .

It is well known that the divided difference $\left[x_{n},g\left(x_{n}\right);f\right]$ is a linear application of $X$ in itself, the sequel $\left(x_{n}\right)_{n=0}^{\infty}$ will be well defined in the case where this application admits an inverse for each $n\in\mathbb{N}$ .

We will admit the fact that the application $\left[x_{0},g\left(x_{0}\right);f\right]$ admits an inverse $\left[x_{0},g\left(x_{0}\right);f\right]^{-1}$ and we will give additional conditions so that all the elements of the sequence $\left(\left[x_{n},g\left(x_{n}\right);f\right]\right)_{n=0}^{\infty}$ are invertible. At the same time we will give conditions for the convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ , provided by relation ( 2 ).

We note that the following $\left(x_{n}\right)_{n=0}^{\infty}$ , provided by method ( 2 ), coincides with the sequence $\left(y_{n}\right)_{n=0}^{\infty}$ given by the following equalities:

(3)

y_{n+1}=g\left(y_{n}\right)-\left[y_{n},g\left(y_{n}\right);f\right]^{-1}f% \left(g\left(y_{n}\right)\right),

Or $y_{0}=x_{0},\ n=1,2,\ldots$

Consider real and positive numbers $B_{0},\ K,\ \alpha,\ \rho,\ \lambda$ And $d_{0}=\left\|f\left(x_{0}\right)\right\|$ .

Let us designate by $q\geq 2$ any real number. Consider the set

(4)

S=\{x\in X:\left\|x-x_{0}\right\|\leq\lambda\},\qquad x_{0}\in X

and designate by $a$ the smallest root of the equation:

(5)

\left(1+\rho\right)t^{2}-\big{[}2\left(1+\rho\right)+\alpha d_{0}^{q-2}\big{]}% t+1+\rho=0.

Regarding the convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by ( 2 ) we have the following theorem:

Theorem 1 .

If the applications $f$ And $g$ and real numbers $B_{0},\ K,\ \alpha,$ $\rho,$ $\lambda$ And $q$ meet the following conditions:

i.

$\left\|f\left(g\left(x\right)\right)\right\|\leq\alpha\left\|f\left(x\right)% \right\|^{q-1}$ for each $x\in S;$
ii.

the divided difference $\left[u,v;g\right]$ is symmetric as a function of $in$ And $in$ And $\left\|\left[u,v;g\right]\right\|\leq\rho$ , for each $u,v\in S;$
iii.

$\left\|\left[u,v,w;f\right]\right\|\leq K,$ for each $u,v,w\in S;$
iv.

there is the application $\left[x_{0},g\left(x_{0}\right);f\right]^{-1}$ And $\big{\|}\left[x_{0},g\left(x_{0}\right);f\right]^{-1}\big{\|}\leq B_{0};$
in.

$B_{0}^{2}K\left(1+\rho\right)\left\|f\left(x_{0}\right)\right\|\leq a;$
we.

$\lambda\geq\max\{\mu,\rho\mu+\left\|g\left(x_{0}\right)-x_{0}\right\|\}$ Or

$\displaystyle\mu$ $\displaystyle=B_{0}b^{\frac{1}{q-1}}\cdot\tfrac{c\delta_{0}}{1-\left(c\delta_{% 0}\right)^{q-1}},\ c=\tfrac{1}{\left(1-a\right)^{2}},\ b=KB_{0}^{2}\alpha,$

$\displaystyle\delta_{0}$ $\displaystyle=b^{\frac{1}{q-1}}d_{0};$
vii.

$c\delta_{0}<1;$

then equation ( 1 ) has at least one solution $\bar{x}\in S,\ \bar{x}=\lim\ x_{n}$ and we have the following delimitation:

\left\|\bar{x}=x_{n}\right\|\leq B_{0}b^{-\frac{1}{q-1}}\cdot\tfrac{\left(c% \delta_{0}\right)^{q^{n}}}{1-\left(c\cdot\delta_{0}\right)^{q^{n}\left(q-1% \right)}}

Demonstration..

Let us designate by:

D_{i}=\left[x_{i},g\left(x_{i}\right);f\right]\quad\text{et~{}}\Gamma_{i}=D_{i% }^{-1},\quad i=0,1,\ldots

If we consider the above notations, we deduce from ( 2 ) and ( 3 ) the following relations:

(6)

x_{1}=x_{0}-\Gamma_{0}\cdot f\left(x_{0}\right)

(7)

x_{1}=g\left(x_{0}\right)-\Gamma_{0}\cdot f\left(g\left(x_{0}\right)\right)

from which we deduce:

(8)

\left\|x_{1}-x_{0}\right\|\leq B_{0}d_{0}

(9)

\left\|x_{1}-g\left(x_{0}\right)\right\|\leq B_{0}\alpha d_{0}^{q-1}

Using the identity:

f\left(x_{1}\right)=f\left(x_{0}\right)+\left[x_{0},g\left(x_{0}\right);f% \right]\left(x_{1}-x_{0}\right)+\left[x_{1},x_{0},g\left(x_{0}\right);f\right]% \left(x_{1}-x_{0}\right)\left(x_{1}-g\left(x_{0}\right)\right)

of iii, ( 6 ), ( 7 ), ( 8 ), ( 5 ) and the hypothesis $x_{1}\in S$ we deduce.

(10)

\left\|f\left(x_{1}\right)\right\|\leq KB_{0}^{2}\alpha d_{0}^{q}.

To prove that $x_{1}\in S$ we notice that the smallest root of equation ( 5 ) verifies the relation $0<a<1,$ SO $c=\frac{1}{\left(1-a\right)^{2}}>1$ .

Then from ( 8 ) it follows that:

\left\|x_{1}-x_{0}\right\|\leq B_{0}d_{0}\leq B_{0}b^{-\frac{1}{q-1}}\cdot cb^% {\frac{1}{q-1}}d_{0}\leq B_{0}\cdot b^{-\frac{1}{q-1}}\cdot c\delta_{0}\leq\mu\leq\lambda

that's to say $x_{1}\in S$ .

We then prove the existence of the application $\Gamma_{1}=D_{1}^{-1}$ .

Using the properties of divided differences and the hypotheses of the theorem we have:

(11)		$\displaystyle\left\\|D_{0}-D_{1}\right\\|=$
	$\displaystyle=\left\\|\left[x_{0},g\left(x_{0}\right);f\right]-\left[x_{1},g% \left(x_{1}\right);f\right]\right\\|$
	$\displaystyle\leq\left\\|\left[x_{0},g\left(x_{0}\right);f\right]-\left[x_{1},g% \left(x_{0}\right);f\right]\right\\|+\left\\|\left[x_{1},g\left(x_{0}\right);f% \right]-\left[x_{1}g\left(x_{1}\right);f\right]\right\\|$
	$\displaystyle\leq KB_{0}d_{0}+K\rho B_{0}d_{0}=K\left(1+\rho\right)B_{0}d_{0}.$

To establish the last inequality we use the fact that $g\left(x_{0}\right),\ g\left(x_{1}\right)\in S$ . Let us now demonstrate these memberships. Indeed we have:

\left\|g\left(x_{0}\right)-x_{0}\right\|<\left\|g\left(x_{0}\right)-x_{0}% \right\|+\rho\mu\leq\lambda

And

\left\|g\left(x_{1}-x_{0}\right)\right\|\leq\left\|g\left(x_{1}\right)-g\left(% x_{0}\right)\right\|+\left\|g\left(x_{0}\right)-x_{0}\right\|\leq\rho\mu+\left% \|g\left(x_{0}\right)-x_{0}\right\|\leq\lambda.

From ( 11 ) we deduce:

\left\|\Gamma_{0}\cdot\left(D_{0}-D_{1}\right)\right\|\leq B_{0}^{2}K\left(1+% \delta\right)d_{0}\leq a.

Because $0<a<1$ and from hypothesis (vi) it follows that we can reverse the operator

H_{0}=I-\Gamma_{0}\left(D_{0}-D_{1}\right),

Or $I$ represents the identical application.

On a:

\left\|H_{0}^{-1}\right\|\leq\tfrac{1}{1-a}.

Let us note subsequently that:

H_{0}=\Gamma_{0}D_{1}

that's to say

H_{0}^{-1}=D_{1}^{-1}\cdot\Gamma_{0}^{-1}

from which we deduce

D_{1}^{-1}=\Gamma_{1}=H_{0}^{-1}\cdot\Gamma_{0}

And

\left\|\Gamma_{1}\right\|\leq\tfrac{B_{0}}{1-a}.

If we designate by $B_{1}$ the expression $\left\|\Gamma_{1}\right\|,$ the above inequality becomes:

(12)

B_{1}\leq\tfrac{B_{0}}{1-a}

Now let us prove that:

B_{1}^{2}K\left(1+\rho\right)d_{1}<a.

Indeed from ( 10 ) and ( 12 ) we deduce

	$\displaystyle B_{1}^{2}K\left(1+\rho\right)d_{1}$	$\displaystyle\leq\tfrac{B_{0}^{4}K^{2}\left(1+\rho\right)\alpha d_{0}^{q}}{% \left(1-a\right)^{2}}=\tfrac{\left[B_{0}^{2}\cdot K\cdot\left(1+\rho\right)d_{% 0}\right]^{2}}{\left(1-a\right)^{2}\left(1+\rho\right)}\cdot\alpha\cdot d_{0}^% {q-2}$
		$\displaystyle\leq\tfrac{a^{2}\alpha d_{0}^{{}^{q-2}}}{\left(1-a\right)^{2}% \left(1+\rho\right)}=a.$

The last equality is justified by the fact that $a$ represents the smallest root of equation ( 5 ).

Let us then assume that the following hypotheses are verified:

$\alpha)$

there are operators $\Gamma_{0},\Gamma_{1},\ldots,\Gamma_{s};$
$\beta)$

$B_{i}\leq\frac{B_{i-1}}{1-a}$ Or $B_{i}=\left\|\Gamma_{i}\right\|\ i=1,2,\ldots,s;$
$\gamma)$

$B_{s}^{2}K\left(1+\rho\right)d_{s}\leq a,d_{s}=\left\|f\left(x_{s}\right)% \right\|;$
$\delta)$

$x_{i}\in S,\ g\left(x_{i}\right)\in S,\ \$ For $i=1,2,\ldots,s+1$

Under these assumptions, using an identity analogous to that from which we deduced the relation ( 10 ), we have the following inequality:

(13)

\left\|f\left(x_{s+1}\right)\right\|\leq KB_{s}^{2}\alpha\left\|f\left(x_{s}% \right)\right\|^{q}

that's to say:

d_{s+1}\leq KB_{s}^{2}\alpha d_{s}^{q}

More than $\beta)$ the following inequality results:

d_{s+1}\leq\tfrac{KB_{0}^{2}\alpha d_{s}^{q}}{\left(1-a\right)^{2s}}

(14)

d_{s+1}\leq bc^{s}d_{s}^{q}.

From the hypotheses of induction the following inequalities result:

d_{i+1}\leq bc^{i}d_{i}^{q},\qquad i=0,1,\ldots,s.

By multiplying by $\frac{1}{b^{q-1}}$ the terms of the last inequalities and designating by $\delta_{i}$ the expression:

\delta_{i}=b^{-\frac{1}{q-1}}d_{i},\qquad i=0,1,\ldots,s

we get:

\delta_{i+1}\leq c^{i}\cdot\delta_{i}^{q},\qquad i=0,1,\ldots,s.

Now let us admit the existence of numbers:

\alpha_{i}\ \text{et }\beta_{i},\quad i=0,1,\ldots,s

such as:

\delta_{i}\leq c^{\alpha_{i}}\delta^{\beta_{i}},\qquad i=1,2,\ldots,s

Or $\beta_{0}=1$ And $\alpha_{0}=0.$ So we have:

\delta_{i+1}\leq c^{i}c^{q\alpha_{i}}\delta_{0}^{\beta_{i}q}

that's to say

\delta_{i+1}\leq c^{q\alpha_{i}+i}\delta_{0}^{\beta_{i}q}=c^{\alpha_{i+1}}% \cdot\delta_{0}^{\beta_{i+1}}

Or $\alpha_{i+1}=q\alpha_{i}+i\ \alpha_{0}=0$ $i=0,1,\ldots,s;$ And $\beta_{i+1}=q\cdot\beta_{i},\beta_{0}=1$ $i=0,1,\ldots,s$ .

From the above relations we easily deduce that:

\alpha_{i}=\tfrac{i-1-iq+q^{i}}{\left(q-1\right)^{2}},\ \beta=q^{i},\qquad i=0% ,1,\ldots,s.

So if we consider the fact that $c>1$ , we deduce the following inequalities:

(15)

\delta_{i+1}\leq\left(c\delta_{0}\right)q^{q^{i+1}};\qquad i=0,1,\ldots,s.

Let us now demonstrate that the application $\Gamma_{s+1}$ exists.

In fact we have:

\left\|D_{s}-D_{s+1}\right\|=\left\|\left[x_{s},g\left(x_{s}\right);f\right]-% \left[x_{s+1},g\left(x_{s+1}\right);f\right]\right\|\leq K\left(1+\rho\right)% \left(B_{s}d_{s}\right)

And

\left\|\Gamma_{s}\left(D_{s}-D_{s+1}\right)\right\|\leq K\left(1+\rho\right)B_% {s}^{2}d_{s}\leq a.

Therefore the application

H_{s}=I-\Gamma_{s}\cdot\left(D_{s}-D_{s+1}\right)=\Gamma_{s}D_{s+1}

admits an inverse for which

\left\|H_{s}^{-1}\right\|\leq\tfrac{1}{1-a}.

From the above relations we deduce that:

D_{i+1}^{-1}=\Gamma_{i+1}=H_{i}^{-1}\cdot\Gamma_{i}

that's to say

\left\|\Gamma_{i+1}\right\|\leq\tfrac{B_{i}}{1-a}

which leads us to the following inequality:

(16)

B_{s+1}\leq\tfrac{B_{s}}{1-a}

that is to say to inequality $\beta)$ For $i=s+1$ .

Let us now demonstrate that we have the inequality $\gamma$ ) For $s+1$ that's to say:

B_{s+1}^{2}K\left(1+\rho\right)d_{s+1}\leq a.

Indeed from ( 15 ) it follows $d_{s}\leq d_{0}$ and then from ( 13 ) and ( 16 ) we deduce:

	$\displaystyle B_{s+1}^{2}K\left(1+\rho\right)d_{s+1}$	$\displaystyle\leq\tfrac{B_{s}^{2}K)1+\rho}{\left(1-a\right)^{2}}KB_{s}^{2}% \alpha d_{s}^{q}$
		$\displaystyle=\tfrac{B_{s}^{2}K\left(1+\rho\right)d_{s}}{\left(1-a\right)^{2}% \left(1+\rho\right)}\alpha d_{s}^{q-2}\leq\tfrac{a^{2}\alpha d_{s}^{q-2}}{% \left(1-a\right)^{2}\left(1+\delta\right)}\leq a.$

Let us subsequently demonstrate the membership of $x_{i+1}$ and that of $g\left(x_{s+1}\right)$ to the sphere $S$ .

It is easily demonstrated that $\alpha_{s+1}+\frac{s+1}{2}\leq q^{s+1},$ For $q\geq 2$ , for each $s\in\mathbb{N}$ ; then we deduce from ( 2 )

	$\displaystyle\left\\|x_{s+2}-x_{s+1}\right\\|$	$\displaystyle\leq\left\\|\Gamma_{s+1}\right\\|\cdot\left\\|f\left(x_{s+1}\right)% \right\\|\leq\tfrac{B_{0}}{(1-a)^{s+1}}$
		$\displaystyle\leq B_{0}\cdot c^{\frac{s+1}{2}}\cdot c^{\alpha_{s+1}}\cdot% \delta_{0}^{\beta_{s+1}}\cdot b^{-\frac{1}{q-1}}$
		$\displaystyle\leq c^{\alpha_{s+1}+\frac{s+1}{2}}\cdot\delta^{\beta_{s+1}}\cdot B% _{0}b^{{}^{-\frac{1}{q-1}}}$
		$\displaystyle\leq B_{0}b^{-\frac{1}{q-1}}\left(c\delta_{0}\right)^{q^{s+1}}.$

From the above relations the following inequalities result:

	$\displaystyle\left\\|x_{s+2}-x_{0}\right\\|$	$\displaystyle\leq\sum_{k=0}^{s+1}\left\\|x_{k+1}-x_{k}\right\\|\leq B_{0}b^{-% \frac{1}{q-1}}\sum_{k=0}^{s+1}\left(c\delta_{0}\right)^{q^{k}}$
		$\displaystyle<\tfrac{B_{0}\cdot b^{-^{\frac{1}{q-1}}}\cdot c\cdot\delta_{0}}{1% -\left(c\cdot\delta_{0}\right)^{q-1}}\leq\mu<\lambda$

And

	$\displaystyle\left\\|g\left(x_{s+2}\right)-x_{0}\right\\|\leq$
	$\displaystyle\leq\left\\|g\left(x_{s+2}\right)-g\left(x_{s+1}\right)\right\\|+% \cdots+\left\\|g\left(x_{1}\right)-g\left(x_{0}\right)\right\\|+\left\\|g\left(x_% {0}\right)-x_{0}\right\\|$
	$\displaystyle\leq\rho\mu+\left\\|g\left(x_{0}\right)-x_{0}\right\\|\leq\lambda,$

that's to say $x_{s+2}\in S$ And $g\left(x_{s+2}\right)\in S$ .

We then study the convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ .

Inequalities.

\left\|x_{k+1}-x_{k}\right\|\leq\tfrac{B_{0}}{b^{\frac{1}{q-1}}}\left(c\delta_% {0}\right)^{q^{k}},

that are true for each $k\in\mathbb{N}$ , it results

(17)		$\displaystyle\left\\|x_{n+p}-x_{n}\right\\|$	$\displaystyle\leq\sum_{k=n}^{n+p-1}\left\\|x_{k+1}-x_{k}\right\\|\leq B_{0}b^{-% \frac{1}{q-1}}\cdot\sum_{k=n}^{n+p-1}\cdot\left(c\delta_{0}\right)^{q^{k}}$
		$\displaystyle\leq\tfrac{B_{0}b^{-\frac{1}{q-1}}\left(c\delta_{0}\right)^{q^{n}% }}{1-\left(c\delta_{0}\right)^{\left(q-1\right)q^{n}}}$

for each $n,\ p\in\mathbb{N}$ .

Considering the fact that $c\cdot\delta_{0}<1$ and the fact that space $X$ is complete, it follows that the following $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent.

Let us designate by $\bar{x}$ the limit; $\lim\limits_{n\rightarrow\infty}x_{n}$ . From the inequality ( 17 ) in $and$ doing $p\rightarrow\infty$ we deduce:

\left\|\bar{x}-x_{n}\right\|\leq\tfrac{B_{0}b^{-\frac{1}{q-1}}\left(c\delta_{0% }\right)^{q^{n}}}{1-\left(c\delta_{0}\right)^{\left(q-1\right)q^{n}}}

Of $\delta_{n}\leq\left(c\delta_{0}\right)^{q^{n}}$ it follows that:

\lim_{n\rightarrow\infty}f\left(x_{n}\right)=f\left(\bar{x}\right)=\theta

which means that $\bar{x}$ is the solution to equation ( 1 ). ∎

Bibliography

[1] Balasz M. and Goldner G., Divided differences in Banach spaces and some of their applications . St. cerc. mat. 21, 7, (1969), pp. 985–995.
[2] ^†^†margin: homepage (papers soon) $\rightarrow$ Diaconu A., Interpolation in arbitrary spaces. Iterative methods for the resolution of operational equations obtained by inverse interpolation. III. Research Seminar of Functional Analysis and Numerical Methods, Preprint Nr.1 1985, pp. 21–70.
[3] Lică Dionis, Functional analysis and approximate solution of nonlinear equations. Scientific Publishing House, Chişinău, 1975.
[4] ^†^†margin: clickable $\rightarrow$ Păvăloiu I. On Steffensen's method for solving nonlinear operational equations , Romanian Review of Pure and Applied Mathematics. XIII , 1, (1968), pp. 149–158.

[5] Pavaloiu I., ^†^†margin: clickable $\rightarrow$ Introduction to the theory of approximation of solutions of equations . Dacia Publishing House, Cluj-Napoca, 1976.
[6] Ul'm, S., Ob obobscennîh razdelennîh raznostiah I , Izv. Acad. Nauk. Estonskoi SSR 16, 1, (1967), pp. 13–26.
[7] Ul'm, S. On generalized separated differences II , Izv. Acad. Nauk. Estonian SSR 16, 2, (1967), pp. 146–155
[8]

Received on 20.XII. 1990

Institute of Computing

37 Republic Street

3400 Cluj-Napoca

Romania

(11)		$\displaystyle\left\\|D_{0}-D_{1}\right\\|=$
	$\displaystyle=\left\\|\left[x_{0},g\left(x_{0}\right);f\right]-\left[x_{1},g% \left(x_{1}\right);f\right]\right\\|$
	$\displaystyle\leq\left\\|\left[x_{0},g\left(x_{0}\right);f\right]-\left[x_{1},g% \left(x_{0}\right);f\right]\right\\|+\left\\|\left[x_{1},g\left(x_{0}\right);f% \right]-\left[x_{1}g\left(x_{1}\right);f\right]\right\\|$
	$\displaystyle\leq KB_{0}d_{0}+K\rho B_{0}d_{0}=K\left(1+\rho\right)B_{0}d_{0}.$

On a generalization of the Steffensen method

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On a generalization of Steffensen's method

Theorem 1 .

Demonstration..

Bibliography

Related Posts

	$\displaystyle\mu$	$\displaystyle=B_{0}b^{\frac{1}{q-1}}\cdot\tfrac{c\delta_{0}}{1-\left(c\delta_{% 0}\right)^{q-1}},\ c=\tfrac{1}{\left(1-a\right)^{2}},\ b=KB_{0}^{2}\alpha,$
	$\displaystyle\delta_{0}$	$\displaystyle=b^{\frac{1}{q-1}}d_{0};$