Let \(X\) be a Banach space and \(Y\) a normed space, and \(P:X\rightarrow Y\) a nonlinear operator. In order to solve the equation \(P\left( x\right)=0\), we consider the iterative method \(x_{n+1}=x_{n}+\varphi \left(x_{n}\right) \), where \(\varphi:X\rightarrow X\). We give some sufficient semilocal conditions relating \(\varphi\) and \(P\) for these iterations to converge to a solution with a given convergence order. As particular instances, we obtain convergence results for the Newton, Chebyshev and Steffensen mehods.
Authors
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
Title
Original title (in French)
Sur les procedées itératifs à un ordre élevé de convergence
English translation of the title
On the iterative methods with high convergence orders
Keywords
iterative methods in normed spaces; convergence order; Newton type method; Chebyshev type method; Steffensen type method; semilocal convergence
I. Păvăloiu, Sur les procedées itérative à un order élevé de convergence, Mathématica, 12(35)(1970) no. 2, pp. 309-324 (in French).
About this paper
Journal
Mathematica
Publisher Name
Academia Republicii S.R.
DOI
Not available yet.
Print ISBN
Not available yet.
Online ISBN
Not available yet.
References
[1] Kantorovici, L. V., Functionalıi analiz i pricladnaia matematica. U.M.N., 28, 3 (1948).
[2] Kantorovici, L. V., O metodı Niutona. Trudı mat. i-ta im. Steklova. 28, pp. 104–144 (1949).
[3] Janko, B, si Goldner, G., Despre rezolvarea ecuatiilor operationale cu metoda lui Cebısev. (II), Studia Univ. Babes-Bolyai Cluj 2, pp. 55–58 (1968).
[4] Ghinea, Monique, Sur la resolution des equations operationnelles dans les espaces de Banach, Revue Francaise de traitement de l’information 8, pp. 3–22 (1965).
[5] Ostrowski, A. M., Resenie uravnenii i sistem uravnenii. Izd. inost. lit., Moskva, (1963).
[6] Pavaloiu, I., Asupra rezolvarii ecuatiilor operationale prin metode de iteratie de ordin superior. Lucrarile colocviului de teoria aproximarii functiilor (rezumat), Cluj 15-20 septembrie 1967.
[7] Pavaloiu, I., Sur la methode de Steffensen pour la resolution des equations operationnelles non lineaires. Revue Roumaine des Mathematiques Pures et Appliquees, XIII, (1968) 6, pp. 857–861.
[8] Pavaloiu, I., Asupra operatorilor iterativi, Studii si Cercetari matematice (in print); appeared as: 23 (1971) no. 10, pp. 1567–1574.
[9] Pavaloiu, I., Interpolation dans des espaces lineaires normes et applications. Mathematica, Cluj, vol. 12 (35), 1, 1970, pp. 149–158.
[10] Stein, M. L., Sufficient conditions for the Banach spaces. Proc. Amer. Math. Soc. 3, pp. 858–863 (1952).
[11] Traub, J, F., Iterative methods for the solution of equations. Prentice-Hall. Inc. Englewood Cliffs N. J. 1964.
On the iterative methods with high convergence orders
by
I. Pavaloiu
in Cluj
Eithera Banach space and
(1)
an operational equation where the operatoris defined on spaceand with values in the normed linear space.
For the resolution of equation ( 1 ) we generally consider another operatordefined on spaceand with values in the same space.
Definition 1 .
We say that the operatoris an iterative operator attached to equation ( 1 ) if any element
for which, is a fixed point for the operator
Using the iterative operatorwe will attach to equation ( 1 ) the following iterative process.
(2)
Definition 2 .
And, the iterative operatorand the real and positive numbermeet the conditions:
a) ForOr
is a natural number.
b)
Then we will say that the iterative process ( 2 ) has the order of convergence
Regarding the notion of order of convergence introduced previously, the following lemma takes place.
Lemme 1.
If the iterative process ( 2 )
has the order of convergenceSOmoreover, if the following
is convergent and the operator P is continuous, thenis a solution to equation ( 1 ) .
Demonstration.
Since the process ( 2 ) has the order of convergenceit follows that there is an element
for which
(3)
Oris a real and positive constant for which condition a) of definition 2 is also fulfilled.
Using condition a) of Definition 2, forwe get
from where, while writingwe deduce
If we apply this inequality successively forwe get
Andand the operator
is continuous, it follows that we have the equality:
That's to say
what needed to be demonstrated. ∎
In definition 2 where we specified the notion of order of convergence of an iterative operator we did not include the condition that the sequencegiven by the process ( 2 ) is convergent.
In this sense, we started from the idea that in practice we are quite rarely led by certain procedures to the exact solution of equations of form ( 1 ). Usually, for the needs of practice, we can limit ourselves to a single approximate solution. One of the simple criteria for assessing the fact thatis an approximate solution for equation ( 1 ) is to check to what extent the real and positive numberis close to zero. Obviously, the closer it is to zero, the more we will consider that the approximate solution found can more exactly satisfy the requirements of the practical problem.
In the following, in all the convergence problems that we will study, concerning equation ( 1 ) and procedure ( 2 ) we will examine both the way in which the sequenceconverges to zero than the way the approximate solution approaches the exact solution.
We will now present a general convergence criterion for the followingprovided by the method ( 2 ). This result can also be considered as a criterion for the existence of the solution for equation ( 1 ). For this we will assume that the iterative operatorhas the form:
(3′)
Theorem 2 .
[ 6 ] . LetAndIf the element
and the real numbercan be chosen so that in the spherethe following conditions are met:
a) the operatoradmits derivatives (in the Fréchet sense) up to orderinclusively andfor everything
b) There exists a real and non-negative constantfor which the inequality takes place
for everything
c) There exists a real and positive constantfor which the inequality takes place
d) Or
and)
Then we have the following properties for equation ( 1 ) and process
( 2 ) :
f') The iterative process ( 2 ) has the order of convergencewhere the sequelis provided by ( 2 ) wherehas the form
( 3 ′ ) .
Demonstration.
From condition c) the following inequality results
(4)
from which we deduce the following inequality:
that's to sayUsing hypotheses a), b) and c) and the generalized Taylor formula we deduce
that is to say that the inequality takes place
Sinceit follows that forinequality c' occurs).
It is now assumed thatfor everythingand we still assume that for the same values ofinequalities take place
In these hypotheses we will show that
and that the inequality c') also holds for
If we proceed in the same way as previously, starting from the hypotheses made we will obtain the following inequalities.
(5)
By multiplying these inequalities bywe deduce
and writing
there is a plow
(5′)
which, by successive application, gives
(6)
From inequalities ( 6 ) and hypothesis c) we deduce
from which the validity of conclusion c' results). From ( 6 ) also results conclusion e').
We will now demonstrate thatIn fact we have
from which it follows thatTo demonstrate the convergence of the sequencewe will show that this sequence is fundamental. Indeed for on a
(7)
from which taking into account hypothesis d) it results that the sequence is convergent sinceis a complete space.
Eitherthen passing to the limit in the inequality ( 7 ) for
on a
that is, inequality d'). From inequalities ( 5 ′ ) and hypothesis d) results property f').
Becauseis derivable init follows that it is a continuous operator and therefore by passing to the limit in the inequalities ( 6 ) we easily deduce thatthat's to saythat is, property a'). ∎
Noticed .
In the proof of Theorem 2 we did not use the fact that conditions b) and c) are fulfilled on the whole sphereWe obtain the same results if we assume that these conditions are met only for the elements of the sequenceprovided by the process ( 2 ). ∎
We will now apply Theorem 2 to present some results in the case of particular iterative processes.
EitherAndIf the elementand the real number
can be chosen so that the following conditions are met:
a) the operatoradmits derivatives (in the Fréchet sense) up to and including order three for allAnd
b) The operatorexists and it is bounded, that is to say for everything
c) Either
We assume that we have the inequality:
d)
Then all the conclusions of Theorem
2 are valid for
In the following, we will study the convergence of the Steffensen iterative process. In the work [ 8 ] it was shown that the Steffensen iterative operator provides us with the following two equivalent iterative processes:
(11)
And
(12)
Regarding this process, there is the following theorem:
Theorem 5 .
Eitheran item for which the following conditions are met:
a)
b) Real and non-negative numbersAndsatisfy inequality
is a natural number.
c) Eithera real, non-negative number.
We will write
Or
And It is assumed that for allthe divided difference
admits an inverse bounded by the numberthat's to say
d) For allthe divided differencesAndare symmetric with respect to the given nodes and we have the inequalities:
e) The iterative operatorhas the orderin the spherethat is to say we have the inequalityand the operatoris continuous in
If conditions a)–e) are met then we have the following properties:
a') The elements of the sequence
provided by the method ( 11 ) belong to the sphere.
b') The elements of the sequencebelong to the sphere
Following the terminology adopted by AM Ostrowski [ 5 ] , we note thatis a point of “contraction” for the equation ( 4 ′ ) since if we choosethen the iterative process ( 3 ′ ) converges and we haveOn the other hand the pointis a “repulsive” point for the equation ( 4 ′ ) since the function
Figure 1.
satisfies the condition:
Applying the results of Lemma 4.2 [ 5 , p. 36] we can deduce the conclusion that the process ( 3 ′ ) will never converge to the solution ( 6 ′ ) whatever the choice of the initial value.
Graphically, this fact is presented as follows (Fig. 1).
If we represent graphically in the coordinate system
the curvesAndthen the solutions of the equation ( 4 ′ ) are nothing other than the abscissas of the points of intersection of the two curves.
In the figure above we notice that by choosing for examplethere is a plowthat is to say that using the method ( 3 ′ ) we obtainAnd
SO
that is, the process ( 2 ′ ) is divergent. Taking for the numberthe approximate valueand by using the method ( 3 ′ ) we obtain the results included in table 1
222 In this table we have introduced only the values which are sufficient to deduce the necessary conclusions on the convergence of the corresponding iteration sequences.
Table 1
.
.
.
.
.
.
Obviously, the results of the calculations show us that if we take
then the sequence of successive approximations has as limit the valueIf we take for exampleSO
To better illustrate the validity of the conclusions, we have taken for
the valuewhich differs very little from the exact solution, but which is larger than it. In this case, by carrying out the sequence of successive iterations we notice that, even if after the first four iterations the third decimal digit of the result is preserved, which could give us the illusion of a possibility of convergence of the process, we will be convinced however, by continuing the process, that even in this case we have
It has been shown here, by several means, that the solutionof the equation ( 1 ′ ) can only be obtained by simple iteration. Starting from the same initial approximations, we will now solve the equation ( 1 ′ ) by applying the Steffensen method. For this, we will note that the equation ( 1 ′ ) can be put in the form
Or
Taking, as in the previous procedure, an initial solution of the formwe findand a simple calculation shows us that Steffensen's method gives us for the second approximationthe following expression
We deduce that in general, Steffensen's method leads us to the following sequence of approximations
Or
(7′)
Taking forthe valuesAndwe obtain the results included in Table 2.
Table 2
Analyzing this table, it follows that if we choose the initial approximation appropriatelyusing the Steffensen method we obtain the solution
If in the process ( 7 ′ ) we start from an initial approximation
close enough to zero, then we will obtain the second solutionThe example studied previously illustrates the validity of the theoretical results obtained in this note in the following senses:
- TheThere are cases where the simple iteration method does not converge to the desired solution, regardless of the choice of the initial approximation. But by applying the Steffensen method and choosing the initial approximation in a suitable way, the desired solution will be obtained. (This fact is valid for any method that has an order of convergence greater than or equal to 2).
-Steffensen's method converges quickly.
Note, for example, that starting from the initial approximation
the simple iteration method is divergent, while the Steffensen method leads us to the desired result in 6 steps.
Forwe will try to numerically illustrate the speed of convergence of the sequence
towards zero.
Table 3
In this tableAndare the approximate (numerical) values of the functionsand the operatorWe deduce that by takingso, for everythingthe inequalities are satisfied
These inequalities characterize the order of convergence of Steffensen's method. More precisely, they show us that it is equal to two.
[2] Kantorovich, L. V., The Newton Method . Trudy mad. i-ta im. Stacklover. 28 , p. 104–144 (1949).
[3] Jankó, B, and Goldner, G., On the solution of operational equations with the method of Cebişev . (II), Studia Univ. Babeş-Bolyai Cluj 2 , pp. 55–58 (1968).
[4] Ghinea, Monique, On the resolution of operational equations in Banach spaces , French Journal of Information Processing 8 , pp. 3–22 (1965).
[6] Păvăloiu, I.,
On the solution of operational equations by higher-order iteration methods . Proceedings of the colloquium on the theory of function approximation (abstract), Cluj, September 15-20, 1967.
