On the Steffensen method for solving nonlinear operator equations^∗

by
Ion Pavaloiu
(Cluj)

Abstract.

This work represents a contribution to the study of the convergence of the generalized Steffensen process. Starting from work [2], improvements are made to the theorems of existence and uniqueness of the solution of the equation

x=A\left(x\right)

Or $A$ is a nonlinear operator defined in space $X$ of the Banach type and which transforms this space into itself.

^∗ Work communicated at the communications session of April 30, 1967 of the Institute of Calculation, Cluj.

Let the equation be given

(1)

F\left(x\right)=x-A\left(x\right)=\theta

Or $A$ is a nonlinear operator that transforms the Banach space $X$ in itself.

JW Schmith [ 1 ] defined generalized divided differences using a linear operator $\left[x,y;F\right]$ who owns the property:

(2)

F\left(y\right)-F\left(x\right)=\left[x,y;F\right]\left(y-x\right),\qquad x,y% \in X.

For equation ( 1 ) the generalized Steffensen method has the following form:

(3)

x_{n+1}=x_{n}-\left[x_{n},A\left(x_{n}\right);F\right]^{-1}F\left(x_{n}\right)

This method is equivalent to the following

(4)

x_{n+1}=A\left(x_{n}\right)-\left[x_{n},A\left(x_{n}\right);F\right]^{-1}F% \left(A\left(x_{n}\right)\right)

S. Ulm [ 2 ] gave a theorem in which he established convergence conditions for such a procedure. In this work the author also gave a theorem of uniqueness of the solution of equation ( 1 ) obtained by procedure ( 3 ).

The aim of our work is to establish another convergence theorem of the process ( 3 ) under other hypotheses.

To simplify, we will designate by $\Gamma_{n}$ the operator $\left[x_{n},A\left(x_{n}\right);F\right]^{-1}.$

The process ( 3 ) can also be written in the form

(5)

x_{n+1}=x_{n}-\Gamma_{n}F\left(x_{n}\right)

and ( 4 ) will then take the form

x_{n+1}=A\left(x_{n}\right)-\Gamma_{n}F\left(A\left(x_{n}\right)\right).

In the following we will assume that the operator $A$ is continuous in a suitable domain.

Theorem 1 .

And

a)

$\Gamma_{0}$ is limited, that is to say $\left\|\Gamma_{0}\right\|\leq B_{0};$
b)

$\max\left\{\left\|x_{1}-x_{0}\right\|,\left\|x_{1}-A\left(x_{0}\right)\right\|% \right\}\leq h_{0};$
c)

$\left\|\left[x^{\prime},x^{\prime\prime};A\right]-\left[x^{\prime\prime},x^{% \prime\prime\prime};A\right]\right\|\leq K\left\|x^{\prime}-x^{\prime\prime% \prime}\right\|$ for everything $x^{\prime}$ , $x^{\prime\prime}$ , $x^{\prime\prime\prime}\in S;$
c’)

$\left\|\left[x^{\prime},x^{\prime\prime};A\right]\right\|\leq M$ for everything $x^{\prime},x^{\prime\prime}\in S$ And $M<1$

Or

$S=\left\{x\in X;\left\|x-x_{0}\right\|\leq 2h_{0}\right\}$
d)

$\eta_{0}=B_{0}Kh_{0}<\frac{1}{4}$

then in the spheres $S$ from space $X$ equation ( 1 ) has only one solution $x^{\ast}$ which we obtain as the limit of the sequence generated by the process ( 3 ) or ( 4 ) and for which we have

(6) $\left\|x^{\ast}-x_{n}\right\|\leq\tfrac{h_{0}}{2^{n-1}}$

(7) $\left\|x^{\ast}-x_{n}\right\|\leq B_{n}K\left\|x^{\ast}-x_{n-1}\right\|\ \left% \|x^{\ast}-A\left(x_{n-1}\right)\right\|$

Or

$B_{n}=\left\|\Gamma_{n}\right\|.$

Demonstration.

If we take into account hypothesis c) we have

\big\|\Gamma_{0}\big\{\left[x_{0},A\left(x_{0}\right);F\right]-\left[x_{1}A% \left(x_{1}\right);F\right]\big\}\big\|\leq 2B_{0}Kh_{0}=2\eta_{0}<\tfrac{1}{2}

so the operator

\bigtriangleup_{0}=E-\Gamma_{0}\left\{[x_{0},A\left(x_{0}\right);F]-\left[x_{1% },A\left(x_{1}\right);F\right]\right\}

admits an inverse for which we have

\left\|\bigtriangleup_{0}^{-1}\right\|\leq\tfrac{1}{1-2\eta_{0}}.

A simple calculation shows us that

\Gamma_{1}=\bigtriangleup_{0}^{-1}\Gamma_{0}\qquad\text{et \qquad}\left\|% \Gamma_{1}\right\|\leq\left\|\bigtriangleup_{0}^{-1}\right\|\ \left\|\Gamma_{0% }\right\|\leq\tfrac{B_{0}}{1-2\eta_{0}}

From ( 3 ) we deduce

\left\|x_{2}-x_{1}\right\|\leq\left\|\Gamma_{1}\right\|\ \left\|F\left(x_{1}% \right)\right\|.

But from ( 2 ) we can easily deduce the identity

	$\displaystyle F\left(x_{1}\right)=$	$\displaystyle F\left(x_{0}\right)+\left[x_{0},A\left(x_{0}\right);F\right]% \left(x_{1}-x_{0}\right)+$
		$\displaystyle+\big\{\left[x_{1},x_{0};F\right]-\left[x_{0},A\left(x_{0}\right)% ;F\right]\big\}\left(x_{1}-x_{0}\right).$

If we take into account the first iteration again, we deduce

\left\|F\left(x_{1}\right)\right\|\leq Kh_{0}^{2}.

Which leads to the following assessment regarding the norm of difference $x_{2}-x_{1}$

\left\|x_{2}-x_{1}\right\|\leq\tfrac{B_{0}Kh_{0}^{2}}{1-2\eta_{0}}.

Now taking into account inequality d) we have

\left\|x_{2}-x_{1}\right\|\leq\tfrac{B_{0}Kh_{0}^{2}}{1-2\eta_{0}}\leq\tfrac{1% }{2}h_{0}.

Reasoning in a similar way we deduce that

\left\|x_{2}-A\left(x_{1}\right)\right\|\leq\tfrac{B_{0}Kh_{0}^{2}}{1-2\eta_{0% }}\leq\tfrac{1}{2}h_{0}.

We will designate by $\eta_{1}=B_{1}Kh_{1}$ so we have

\max\left\{\left\|x_{2}-A\left(x_{1}\right)\right\|,\ \left\|x_{2}-x_{1}\right% \|\right\}\leq\tfrac{B_{0}Kh_{0}^{2}}{1-2\eta_{0}}=h_{1}

\eta_{1}=B_{1}Kh_{1}\leq\tfrac{B_{0}^{2}K^{2}h_{0}^{2}}{\left(1-2\eta_{0}% \right)^{2}}<\frac{1}{4}.

By induction we can easily demonstrate that the following relationships hold:

(8)

B_{n}=\left\|\Gamma_{n}\right\|\leq\tfrac{B_{n-1}}{1-2\eta_{n-1}}

(9)

\eta_{n-1}\leq\tfrac{1}{4}

(10)

h_{n}=\tfrac{B_{n-1}Kh_{n-1}^{2}}{1-2\eta_{n-1}}

(11)

\max\big\{\left\|x_{n+1}-x_{n}\right\|,\left\|x_{n+1}-A\left(x_{n}\right)% \right\|\big\}\leq\tfrac{B_{n-1}Kh_{n-1}^{2}}{1-2\eta_{n-1}}=h_{n}

for everything $n=1,2,\ldots$

We can notice that the sequence of numbers

\left\|x_{1}-x_{0}\right\|,\ \left\|x_{2}-x_{1}\right\|,\ldots,\left\|x_{n}-x_% {n-1}\right\|,\ldots,

satisfies the following property:

\left\|x_{i}-x_{i-1}\right\|\leq h_{i-1},\qquad\text{pour tout }i=1,2,\ldots,

And

h_{i-1}\leq\tfrac{1}{2}h_{i-2}

We will now show that the elements of the sequence:

(12)

x_{0},x_{1},\ldots,x_{n},\ldots

belong to the sphere $S$ .

Indeed for everything $n$ on a

\left\|x_{n}-x_{0}\right\|\leq h_{0}\sum_{i=0}^{n-1}\tfrac{1}{2^{i}}\leq 2h_{0}

from which it follows that $x_{n}\in S$ for everything $n=1,2,\ldots$ We will now show that the sequence ( 12 ) is a fundamental sequence.

In fact we have

	$\displaystyle\left\\|x_{n+p}-x_{n}\right\\|$	$\displaystyle\leq\left\\|x_{n+p}-x_{n+p-1}\right\\|+\ldots+\left\\|x_{n+1}-x_{n}\right\\|$
		$\displaystyle\leq h_{0}\left(\tfrac{1}{2^{n+p-1}}+\ldots+\tfrac{1}{2^{n}}% \right)\leq\tfrac{h_{0}}{2^{n-1}}.$

Passing the limit when $p\rightarrow\infty$ we deduce from this

(13)

\left\|x^{\ast}-x_{n}\right\|\leq\tfrac{h_{0}}{2^{n-1}}.

It follows that the sequence ( 12 ) is convergent and $x^{\ast}\in S.$ We can also easily deduce that we have

(14)

\left\|x^{\ast}-A\left(x_{n}\right)\right\|\leq\tfrac{h_{0}}{2^{n-1}}.

Inequality ( 7 ) is easily deduced; this is why we will not give a demonstration of it in this work.

Passing to the limit in equality ( 3 ) and taking into account the fact that $\left[x_{n},A\left(x_{0}\right);F\right]$ is an additive and bounded operator for all $n$ , it follows that $x^{\ast}$ verifies equation ( 1 ).

We will demonstrate that $x^{\ast}$ is the unique solution to equation ( 1 ).

Indeed, assuming that $x^{\ast}$ And $x^{\ast\ast}$ are two solutions of equation ( 1 ) which belong to the sphere $S$ on a

\left\|x^{\ast}-x^{\ast\ast}\right\|\leq M\left\|x^{\ast}-x^{\ast\ast}\right\|% <\left\|x^{\ast}-x^{\ast\ast}\right\|

which is only possible if $x^{\ast}=x^{\ast\ast.}$ ∎

Noticed .

And $B_{n}$ is bounded, then the order of convergence of the Steffensen process is 2. This follows from inequality ( 10 ). That is, $\left\|B_{n}\right\|\leq B$ for everything $n$ on a

h_{n}\leq 2B\,K\,h_{n-1}^{2}

and we can further deduce that

h_{n}\leq\tfrac{(2B\,K\,h_{0})^{2n}}{2B\,K}.\displayqed

Received June 6, 1967

Computing Institute, Cluj

Bibliography

[1] JW Schmith, Convergence speed of the in Banach space . ZAMM, 1966, 46, 2, 146-148.
[2] S. ULM, Generalization of Steffensen's method for solving nonlinear operator equations . "Jur. vácisl. mat. mat. fiziki", 1964, 4 , 6, 1093-1097.
[3] AM OSTROVSKI, Reşenie uravnenij i sistema uravnenij. ”Mat. izd-vo in. lit.”, 1963.
[4] LV KANTOROVICI, Functional analysis and applied mathematics . "UMN", 1948 (28), 3 , 6.
[5]

On the Steffensen method for solving nonlinear operator equations

Abstract

Original title (in French)

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On the Steffensen method for solving nonlinear operator equations^∗

Abstract.

Theorem 1 .

Demonstration.

Noticed .

Bibliography

Related Posts

On the Steffensen method for solving nonlinear operator equations

Abstract

Original title (in French)

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On the Steffensen method for solving nonlinear operator equations∗

Abstract.

Theorem 1 .

Demonstration.

Noticed .

Bibliography

Related Posts

On the Steffensen method for solving nonlinear operator equations^∗