Abstract
We study the monotone convergence of two general methods of Aitken-Steffenssen type. These methods are obtained from the Lagrange inverse interpolation polynomial of degree two, having controlled nodes. The obtained results provide information on controlling the errors at each iteration step.
Author
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)
Keywords
Aitken-Steffenssen methods; Lagrange inverse interpolation
PDF-LaTeX file (on the journal website).
Cite this paper as:
I. Păvăloiu, Bilateral approximations of the roots of scalar equations by Lagrange-Aitken-Steffensen method of order three, Rev. Anal. Numér. Théor. Approx., 35 (2006) no. 2, pp. 173-182. https://doi.org/10.33993/jnaat352-843
About this paper
Publisher Name
Print ISSN
1222-9024
Online ISSN
2457-8126
References
[1] Balazs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numer. Theor. Approx., 21 (2), pp. 111-117, 1992.
[2] Casulli, V., Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13 (1), pp. 25-44, 1997.
[3] Costabile, F., Gualtieri, I.M., Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87-100, 2001.
[4] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40, pp. 109-119, 2003.
[5] Grau, M., An improvement to the computing of nonlinear equation solutions, Numer. Algorithms., 34, pp. 1-12, 2003.
[6] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press, New York and London, 1973.
[7] Păvăloiu I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 1 (5), pp. 20-43, 1997.
[8] Păvăloiu I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32 (1-2), pp. 69-82, 1995.
[9] Păvăloiu I., Optimal problems concerning interpolation methods of solution of equations, Publications de L’Institut Mathematique, 52 (66), pp. 113-126, 1992.
[10] Păvăloiu I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numer. Theor. Approx., 29 (1), pp. 83-89, 2000.
[11] Păvăloiu I., Local convergence of general Steffensen type methods, Rev. Anal. Numer. Theor. Approx., 33 (1), pp. 79-86, 2004.
[12] Păvăloiu I., and Pop, N., Interpolation and Applications, Risoprint, Cluj-Napoca, 2005 (in Romanian).
[13] Păvăloiu I., On a Steffensen-Hermite-type Method for approximating the solution of nonlinear equations, Rev. Anal. Numer. Theor. Approx., 25 1, pp. 87-94, 2006.
[14] Păvăloiu I., Bilateral approximation of solutions of equations by order-three Steffensen type methods, Studia Univ. “Babeș-Bolyai”, Mathematica, Vol. LI, no. 3, pp. 105-114, 2006.
[15] Traub, J.F., Iterative Methods for Solutions of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[16] Turowicz, B. A., Sur les derivees d’ordre superieur d’une function inverse, Ann. Polon. Math., 8, pp. 265-269, 1960.
Paper (preprint) in HTML form
BILATERAL APPROXIMATIONS OF THE ROOTS OF SCALAR EQUATIONS BY
LAGRANGE-AITKEN-STEFFENSEN METHOD
OF ORDER THREE∗
Abstract.
We study the monotone convergence of two general methods of Aitken-Steffenssen type. These methods are obtained from the Lagrange inverse interpolation polynomial of degree two, having controlled nodes. The obtained results provide information on controlling the errors at each iteration step.
Key words and phrases:
Aitken-Steffenssen methods, Lagrange inverse interpolation.1991 Mathematics Subject Classification:
65H05.1. Introduction
It is well known that the Steffensen, Aitken, and Aitken-Steffensen methods are obtained from the inverse Lagrange interpolation polynomial of degree one, with controlled nodes [9]–[13], [7]. Consider the equation
| (1.1) |
where
We also consider the following three equations, each of them equivalent with equation (1.1):
| (1.2) |
and
| (1.3) | |||||
The Steffensen method in given by relations
| (1.4) |
and, analogously, the Aitken method is of the following form:
| (1.5) |
Finally, the Aitken-Steffensen method is given by the relations:
| (1.6) |
The order of convergence of all three methods (1.4)–(1.6) is at least two, and this order depends on the functions and respectively. Essentially, the methods (1.4)–(1.6) are obtained from the method of chord where the interpolation nodes depend on the functions and respectively In papers [2], [9], [10], [13] some conditions had to be considered in order that all the three methods (1.4)–(1.6) generate two sequences and with the properties:
) The sequence is increasing and the sequence is decreasing:
where is the root of equation (1.1),
Practically, such sequences are very interesting, because by inequalities
the errors of approximation at every step of iteration may be controlled.
Let be three nodes of interpolation, and let the values of the function , i.e.
Suppose that the function is bijective where
By relations (see [13])
and
using (1), one obtains the following approximation for
| (1.9) |
and the error:
| (1.10) |
Using the mean value formula for divided differences (see [13]) it follows that there exists such that
| (1.12) |
Because is bijective, it follows that there exists such that , and by (1.11) and (1.12) one obtains:
| (1.13) |
By (1.9), if one considers particular nodes it is possible to obtain different methods of Steffensen type, of Aitken type or of Aitken-Steffensen type.
Let be an approximation of the root of equation (1.1).
If , then one obtains the following method of Aitken-Steffensen type:
and finally, for one obtains the following method of Aitken type:
Using the symmetry of Lagrange polynomial with respect to nodes, by permutations of in methods (1)–(1), one obtains the same results for
In [15] conditions are given in order that method (1) generates sequences approximating the root of equation (1.1) bilaterally. In this paper we study methods (1) and (1) and we obtain same conditions in order that the sequences generated by there methods are bilateral approximations of the root of equations (1.1).
2. The convergence of Aitken-Steffensen method
In the following we study the method (1) and we search the conditions on the sequences and generated from this method in order that they are monotonic sequences, bilaterally approximating the root of equation (1.1).
We need the following hypothesis:
-
a)
is increasing on ;
-
b)
is continuous and decreasing on ;
-
c)
equation (1.1) has a solution and
-
d)
function is in and for every the following relation is fulfilled:
(2.1) -
e)
function satisfies inequality
where
Concerning the convergence of sequence generated by (1), the following Theorem holds:
Theorem 2.1.
Let and verify the following conditions:
-
i
is increasing on ;
-
ii
is convex on ;
-
iii
functions and verify hypotheses ;
-
iv
and
Then the sequences and generated by (1) verify the properties:
-
j
sequences and are decreasing and bounded from below by ;
-
jj
sequence is increasing and bounded from above by ;
-
jjj
at every iteration step the following inequalities hold:
(2.2) -
jv
Proof.
By hypotheses a) and it follows i.e Hypothesis e) implies From it follows and from b) and one obtains Now using it follows:
and
and by considering and for in (1) it follows that Using (1.13), by hypotheses d) and (1.10) for and it follows i.e By hypotheses a) and it follows and then, by b) one obtains and Let be an element of sequence generated by (1) and suppose that Then one obtains the relations:
| (2.3) |
Inequality follows from equality:
and from the hypothesis of the theorem.
Remark 2.2.
An analogous proof with that from Theorem 2.1 is valid for the following:
Theorem 2.3.
Let and verify the following conditions:
-
i
function is increasing on ;
-
ii
function is concave on ;
-
iii
functions and verify the hypotheses ;
-
iv
and
Then sequences and generated by (1) have the following properties:
-
j
sequences and are increasing and bounded from above by
-
jj
sequence is decreasing and bounded from below by
-
jjj
the following relations hold:
(2.4) -
jv
Remark 2.4.
If function is decreasing and convex, then defined by is increasing and concave, verifies all hypotheses of Theorem 2.3 and consequently all the conclusions hold.
3. Convergence of Aitken type method
In order to study the convergence of the sequences generated by (1) we must suppose that functions and verify hypotheses a)-e) of section 2.
The following theorem holds:
Theorem 3.1.
Let and the functions and verify the conditions:
-
i
is increasing an ;
-
ii
is convex an ;
-
iii
and verifies the hypotheses ;
-
iv
and
Then sequences and generated by (1) have the properties:
-
j
sequences and are decreasing and bounded from below by ;
-
jj
sequence is increasing and bounded from above by ;
-
jjj
the following relations hold,
-
jv
Proof.
Let be and where By a) it follows that and by b) . Using e) one obtains By hypothesis and , and by the above relations and (1), for it follows
Remark 3.2.
Analogously, the following result can be proved
Theorem 3.3.
Let and functions have the following properties:
-
i4)
is increasing on ;
-
ii
is concave on ;
-
iii
and verify hypothesis a)-e);
-
iv
and
Then sequences and generated by (1) verify the properties:
-
j
and are increasing and bounded from above by
-
jj
sequence is decreasing and bounded from below by
-
jjj
the following relations hold:
-
jv
4. The determination of the auxiliary functions
In the following, for every situation concerning the monotonicity and convexity of function functions and can be determined such that conditions a), b), c) and e) should be verified. In the following we thoroughly present the case in which function is increasing and convex.
Supposing that for every one considers the functions:
| (4.1) |
and
| (4.2) |
Then
for every and, consequently is increasing. Analogously
for every and then is a decreasing function. It follows that and verify hypotheses a) and b). The hypothesis e) is also verified because for every In the inequality holds. Because and the above inequality is verified if This follows, because ( is a decreasing functions). This means that the following relation must hold:
i.e.
Because and , for the veridicity of last inequality it is sufficient that
where is the root of equation (1.1). This last inequality may be realized if is sufficiently close to
5. Order of convergence
In the following we prove that every method (1) and (1) have the order of convergence three. The order of convergence for method (1) was treated in [15], and this order is at least three. Assume the following hypotheses:
) function verifies relation
for every where
for every where and are real numbers.
for every where .
References
- [1]
- [2] Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21 (2), pp. 111–117, 1992.
- [3] Casulli, V., Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13 (1), pp. 25–44, 1997.
- [4] Costabile, F., Gualtieri, I. M., Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87–100, 2001.
- [5] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40, pp. 109–119, 2003.
- [6] Grau, M., An improvement to the computing of nonlinear equation solutions, Numer. Algorithms., 34, pp. 1–12, 2003.
- [7] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press, New York and London, 1973.
- [8] Păvăloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 1 (5), pp. 20–43, 1997.
- [9] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32 (1–2), pp. 69–82, 1995.
- [10] Păvăloiu, I., Optimal problems concerning interpolation methods of solution of equations, Publications de L’Institut Mathématique, 52 (66), pp. 113–126, 1992.
- [11] Păvăloiu, I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numér. Théor. Approx., 29 (1), pp. 83–89, 2000.
- [12] Păvăloiu, I., Local convergence of general Steffensen type methods, Rev. Anal. Numér. Théor. Approx., 33 (1), pp. 79–86, 2004.
- [13] Păvăloiu, I. and Pop, N., Interpolation and Applications, Risoprint, Cluj-Napoca, 2005 (in Romanian).
- [14] Păvăloiu, I., On a Steffensen-Hermite-type Method for approximating the solution of nonlinear equations, Rev. Anal. Numér. Théor. Approx., 25 1, pp. 87–94, 2006.
- [15] Păvăloiu, I., Bilateral approximation of solutions of equations by order-three Steffensen type methods, Studia Univ. “Babeş-Bolyai”, Mathematica, Vol. LI, no. 3, pp. 105–114, 2006.
- [16] Traub, J. F., Iterative Methods for Solutions of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
- [17] Turowicz, B. A., Sur les derivées d’ordre supérieur d’une function inverse, Ann. Polon. Math., 8, pp. 265–269, 1960.
- [18]