We study a general Steffensen type method based on the inverse interpolation Lagrange polynomial of second degree. We show how the auxiliary functions may be constructed and we analyze some conditions on them which lead to monotone approximations. We obtain some local convergence results, which are illustrated by some numerical examples.
nonlinear equations in R; Steffensen type method; inverse interpolation Lagrange polynomial of second degree; monotone iterations; local convergence; numerical examples.
Cite this paper as:
I. Păvăloiu, E. Cătinaş, On a Steffensen type method, IEEE Proceedings, 2007, pp. 369-375.
[1] I. K. Argyros. An error analysis for Steffensen’s method. Panamer. Math. J., 10(4):27–33, 2000.
[2] M. Balasz. A bilateral approximating method for finding the real roots of real equations. Rev. Anal. Numer. Theor. Approx., 21(2):111–117, 1992.
[3] B. A. Bel’tyukov. An analogue of the Aitken-Steffensen method with a controllable step (in russian). Zh. Vychisl. Mat. i Mat. Fiz., 27(6):803–817, 1987.
[4] C. Iancu, I. Pavaloiu, and I. Serb. Methodes it erative optimales de type Steffensen obtenues par interpolation inverse. Research Seminar on Functional Analysis and Numerical Methods, Preprint, 1:81–88, 1983.
[5] W. L. Johnson and R. D. Scholz. On Steffensen’s method. SIAM J. Numer. Anal., 5(2):296–302, 1968.
[6] M. A. Ostrowski. Solution of Equations and Systems of Equations. Academic Press, New York, 1980.
[7] I. Pavaloiu. Solutions of Equations by Interpolation (in Romanian). Dacia, Cluj-Napoca, Romania, 1981.
[8] I. Pavaloiu. Optimal problems concerning interpolation methods of solution of equations. Publ. l’Inst. Math. Beograd, 52 (66):113–126, 1992.
[9] I. Pavaloiu. On the monotonicity of the sequences of approximations obtained by Steffensen’s method. Mathematica (Cluj), 35 (58)(1):71–76, 1993.
[10] I. Pavaloiu. Bilateral approximations for the solutions of scalar equations. Rev. Anal. Numer. Theor. Approx. , 23(1):95–100, 1994.
[11] I. Pavaloiu. Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences. Calcolo, 32(1-2):69–82, 1995.
[12] I. Pavaloiu and N. Pop. Interpolation and Applications (in Romanian). Risoprint, Cluj-Napoca, Romania, 2005.
[13] J. R. Sharma. A composite third order Newton-Steffensen method for solving nonlinear equations. Appl. Math. Comput., 169(1):242–246, 2005.
[14] J. F. Traub. Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, N.J., 1964.
[15] B. A. Turowicz. Sur les derivees d’ordre superieur d’une fonction inverse. Ann. Polon. Math., 8:265–269, 1960.
I. Păvăloiu and E. Cătinaş
”T. Popoviciu” Institute of Numerical Analysis
P.O. Box 68-1, Cluj-Napoca
Romania
{pavaloiu,ecatinas}@ictp.acad.ro
Abstract
We study a general Steffensen type method based on the inverse
interpolation Lagrange polynomial of second degree.
We show how the auxiliary functions may be constructed and we
analyze some conditions on them which lead to monotone
approximations. We obtain some local convergence results, which are
illustrated by some numerical examples.
1 Introduction
As it is well known, the Steffensen method for approximating the
solutions of equations is an interpolatory type method with
controlled nodes [3], [4],
[6], [8],
[9].
More precisely, if we generate in the Lagrange polynomial of inverse
interpolation of degree 1, the nodes of interpolation, in a
particular way, we obtain one of the known variants of the
Steffensen’s method [1], [5], [12], [9],
[13], [14].
Consider the equation
(1)
where In
a sufficiently general case, in order to obtain approximations of a
root of equation (1), we
shall consider another equation, equivalent to (1), of the
form
(2)
Let be the set of values of the function for
We suppose that is one to one, i.e. there exists We consider the interpolation nodes and the values
of function at these nodes. The Lagrange interpolation
polynomial of first degree for the function
on the nodes has the form:
(3)
Taking into account relation for
from (3), we obtain an approximation of root
, given by
relation
from which, if we take into account equality
(4)
we obtain:
(5)
i.e. the regula falsi, which leads us to the chord method.
Let be an
approximation of root of equation (1). If in
(5) we take and , we obtain
the Steffensen’s method, which
is written as:
(6)
In the present work we shall study a Steffensen type method, more
general than (6), which will rely on the Lagrange
polynomial of inverse interpolation of second degree. Accordingly,
let be three nodes of interpolation, and The Lagrange interpolation polynomial of second
degree, for the
inverse function has the form:
It is easy to see that the following equality takes place:
(10)
From (4), (9) and (10) we obtain for
the approximation
(11)
with the error given by relation
(12)
Further on, we shall suppose that and
for every Hence
, and the following relation takes place
(13)
where , [6], [8],
[7], [15]. From the mean
value theorem
for divided differences, it results that there exists so that
(14)
If we take into account that is one to one and onto, it results
that for there exists
so that and from
(14) and (13) we have:
(15)
Using as in (6) function for the control of
interpolation nodes, we shall obtain, from (11), a
generalized method of Steffensen type.
Thus, let an
approximation of solution of equation (1);
then, we shall obtain approximation from (11)
considering
i.e.
(16)
We shall name the method (16), the Steffensen’s method of
degree three.
For the study of convergence of sequences and
generated by (16), we shall analyze
first the
conditions on functions and , as well as on initial value so that the two considered sequences to be
monotonically. This fact will give us the possibility to control the
error at each iteration step. We also study the local convergence,
and we shall show that, under certain assumptions, function can
be chosen to assure assumptions regarding monotonous convergence
[2], [10],
[11], [12].
2 The Convergence of Steffensen Method of Order Three
In the following we shall study the convergence of sequences
and given by
(16).
We shall consider the following assumptions on the functions and
:
From , and
(21) it follows that results
and which together with (22) lead us to
relation By use of Newton’s identity
(9) we obtain, for the nodes considered in (16)
(23)
From (15) and (21) it follows that there exists such that (23) can be represented in the form:
(24)
Taking into account and assumption
from (24) we obtain i.e.
The last relation, together with
lead us to relations
and from we have From the facts proven above, it is obvious that
relations
(19) hold. If then we shall use identity
(25)
As then, from andrelations
imply the stated result.
From (17) it is easy to see that relation
takes place, i.e. we have:
From the above relation it results that
and and from (25) and
(16) it results From (24) for
it results
which, together with leads us to relations
(20).
The consequence is a result of relation
(19) or (20). For from
(19), respectively (20), it results that it exists
Getting to the limit for in
(16) we obtain , and from assumption
it results i.e. and Thus, Theorem 1 is proven.
Proof. (Theorem 2). We notice that if instead of equation
(1) we consider equation then function
verifies all
assumptions of Theorem 1 relating to If
then and hold. Also, if
verifies from relation it results
that verifies too
Obviously, assumptions and are
verified by Also, relations (16) do not
change if we replace by Taking into account Theorem 1, it
is obvious that the consequences from Theorem 2 take place.
Proof.(Theorem 3). Let for which
an approximation
of Suppose then, obviously, form it results and
From
taking into account the last relations, and from
(16) it results From (24),
and
it results i.e. From and from it results
Relation (20) results from the facts
proven
above. If then, obviously and By use of relation
(25) from
and (16) it results and
From (24), and
taking into account the
last relations, it results i.e. and thus relations (19) hold. Consequence
results from (19) and
(20).
Proof.(Theorem 4.) We shall use the same
reasoning as in the case of Theorem 2, i.e. we shall notice that if
verifies the assumptions of Theorem 4, then
verifies the
assumptions of Theorem 3. We notice that for
every and thus is also verified for
Also, function verifies assumptions
and It thus follows that the consequences of
Theorem 3 take place, which imply the proof of Theorem 4. As one can
notice, in every case, relation offers us a
control of error at every step of iteration.
3 The Local Convergence of Steffensen’s Method of Order Three
In the following, in order to point out the convergence order of
method (16), we shall provide a result concerning the local
convergence of this method. Accordingly, we shall admit that
functions and verify the following assumptions:
there exists ,
so thatfor every
there exists so
thatfor every
The following theorem holds:
Theorem 5
If functions and verify assumptions
,
and for some
the following relations are verified:
(26)
(27)
then, the elements of sequences
and remain in the interval , and for
every
the following relations hold:
(28)
i.e.
Proof. From and (26)
it results and, more, If
we take account of (24), for and of assumptions
and
the following relation results:
(29)
From (26), (27) and (29) it results
and relation (28) for holds. If we
suppose that for
, then, from (24), proceeding as above, we deduce:
(30)
or
(31)
From (30) results , and from (31)
results (28). Relations (26) and (28) imply
Remark 6
Relations (28) show that the
-convergence order of the method given by (16) is at
least 3.
4 Construction of Auxiliary Function
Further on, we shall show that, within supplementary assumptions
upon depending on its monotony and convexity, we can construct
the functions which fulfill, respectively, the assumptions of
Theorems 1–4. More precisely, the essential assumptions upon
function are given by
and or, analogously,
The following theorems take place:
Theorem 7
If verifies assumptions and
of Theorem 1 and moreover, if it exists so that
then, function given by relation
(32)
where fulfills the conditions given by assumptions
and
Proof. From and it results
and for every
It is obvious that function given by (32) verifies
For and it is sufficient that function
should verify relations
It is not difficult to show that if verifies (34),
then
verifies
i.e. assumptions and are verified.
Theorem 8
If assumptions and
of Theorem 2 are fulfilled, and, moreover, if for
an , relation
takes place, then, function
given by relation (32), where
verifies the conditions given by assumptions
and
Proof. From and it results
and for every
Let given by
relation then has
the form
From relation it results that function
is increasing, and moreover for every
It is thus obvious that the following relations
are valid i.e.
(35)
Function given by (32) verifies assumption
For
and the following relations are sufficient:
It is obvious that if verifies (38), from
(39) it results that verifies (37), i.e.
(36) takes place, and thus function verifies
and
Theorem 9
If assumptions and
of Theorem 3 are fulfilled, and, moreover, if for
an , , relation
, takes place, then, function
, given by relation (32), where
verifies assumptions and
Proof.We consider again function ,
From and results
and i.e. function
is decreasing, and
the following relations hold:
(40)
for every In order that verifies
and
the following relations are sufficient:
(41)
If we take into account the substitution considered, and the
assumption upon parameter from (40), we deduce
that verifies (41).
Assumption assures us that the
set of values which could take is not a void one.
Theorem 10
If function verifies assumptions
and of Theorem 4, and
if, moreover, for an , , relation
takes place, then function
given by (32) where verifies
assumptions and .
Proof. From it results that function is
decreasing, i.e. the following relations take place:
(42)
for every
From relation , the following relations
result, for
Which shows us that if
then, relation (43) is verified, which assures us that
assumptions and are verified. Relation
assures us that the set of
values of is not empty.
5 Numerical Examples
Further on, we shall present two numerical examples, which
illustrate some of the obtained results.
Example 1
Let
(44)
for Because and
for , we construct
function in such a manner that Theorem 1 can be applied to this
example.
Function is given by relation
It is clear that for every It is
shown at once
that if we take function given by relation
(45)
then assumptions
and upon
function are verified for and and
thus is an acceptable value.
If in (16) we consider functions and given by
(44), respectively (45), then we obtain, for the
root of equation (44) the
approximations given in Table 1.
Obviously, sequence generated from (16)
in the conditions of Theorem 1, verifies its conclusions, i.e.
sequences and are
increasing, and sequence is decreasing. From
Table 1, by use of
the following relation clearly results:
where is the root of the given equation.
0
0
0.5
0.39187978821665
1
0.41440725449098
0.41442110496351
0.41441761121909
2
0.41441831498704
0.41441831498704
0.41441831498704
Table 1: Numerical results for .
Example 2
We consider equation:
(46)
for For the derivatives of order 1 and 2 of ,
we have
relations
Once more, we shall show that the Theorem 1 can be applied. It is
easy to see that
function may be put in the form:
An elementary reasoning leads us to conclusion for
every
We consider function given by relation
(47)
We conclude that all the assumptions of Theorem 1 are verified. By
use of relations (16) we obtain the results from Table 2.
In this case we notice that sequences and
are decreasing, and sequence
is increasing. For the error,
we have relation:
0
0
-0.8
-0.8881073657412
1
-0.90850552567187
-0.90845262256514
-0.90844243232071
2
-0.90844000122266
-0.90844000122266
-0.90844000122266
Table 2: Numerical results for .
Acknowledgement. This work has been supported by MEdC under Grant
2CEEX-06-11-96.
References
[1]I. K. Argyros (2000)An error analysis for Steffensen’s method.
Panamer. Math. J.10 (4), pp. 27–33.
Cited by: §1.
[2]M. Balasz (1992)A bilateral approximating method for finding the real roots of real equations.
Rev. Anal. Numér. Théor. Approx.21 (2), pp. 111–117.
Cited by: §1.
[3]B. A. Bel’tyukov (1987)An analogue of the Aitken-Steffensen method with a controllable step (in russian).
Zh. Vychisl. Mat. i Mat. Fiz.27 (6), pp. 803–817.
Cited by: §1.
[4]C. Iancu, I. Păvăloiu, and I. Serb (1983)Methodes itérative optimales de type Steffensen obtenues par interpolation inverse.
Research Seminar on Functional Analysis and Numerical Methods, Preprint1, pp. 81–88.
Cited by: §1.
[5]W. L. Johnson and R. D. Scholz (1968)On Steffensen’s method.
SIAM J. Numer. Anal.5 (2), pp. 296–302.
Cited by: §1.
[6]M. A. Ostrowski (1980)Solution of equations and systems of equations.
Academic Press, New York.
Cited by: §1,
§1.
[7]I. Păvăloiu and N. Pop (2005)Interpolation and applications (in romanian).
Risoprint, Cluj-Napoca, Romania.
Cited by: §1.
[8]I. Păvăloiu (1981)Solutions of equations by interpolation (in romanian).
Dacia, Cluj-Napoca, Romania.
Cited by: §1,
§1.
[9]I. Păvăloiu (1992)Optimal problems concerning interpolation methods of solution of equations.
Publ. l’Inst. Math. Beograd52 (66), pp. 113–126.
Cited by: §1,
§1.
[10]I. Păvăloiu (1993)On the monotonicity of the sequences of approximations obtained by Steffensen’s method.
Mathematica (Cluj)35 (58) (1), pp. 71–76.
Cited by: §1.
[11]I. Păvăloiu (1994)Bilateral approximations for the solutions of scalar equations.
Rev. Anal. Numér. Théor. Approx.23 (1), pp. 95–100.
Cited by: §1.
[12]I. Păvăloiu (1995)Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences.
Calcolo32 (1-2), pp. 69–82.
Cited by: §1,
§1.
[13]J. R. Sharma (2005)A composite third order Newton-Steffensen method for solving nonlinear equations.
Appl. Math. Comput.169 (1), pp. 242–246.
Cited by: §1.
[14]J. F. Traub (1964)Iterative methods for the solution of equations.
Prentice-Hall, Englewood Cliffs, N.J..
Cited by: §1.
[15]B. A. Turowicz (1960)Sur les derivées d’ordre superieur d’une fonction inverse.
Ann. Polon. Math.8, pp. 265–269.
Cited by: §1.
