Abstract
Let \(x_k\rightarrow x^\ast\in{\mathbb R}^N\); denote the errors by \( e_k: = \x^\ast – x_k\ \) and the quotient factors by \(Q_p(k)=\frac{e_{k+1}}{{e_k}^p}\) (\(p \geq 1\)).
Consider the following definitions of Qorders \(p_0>1\) of \(\{x_k\}\):
\begin{equation}\tag{$Q_\varepsilon$}\label{def Qe}
\begin{cases}
Q_p=0, & p \in [1,p_0),
\\
Q_p=+\infty, & p \in (p_0,+\infty)
\end{cases}
\Leftrightarrow
\begin{cases}
Q_{p_0\varepsilon}=0, & \forall \varepsilon >0, p_0\varepsilon>1,
\\
Q_{p_0+\varepsilon}=+\infty, & \forall \varepsilon >0
\end{cases}
\end{equation}
\begin{equation}\tag{$Q$}\label{def Q}
q_l=q_u, {\rm where}
\begin{cases}
q_l=\inf \big\{p\in[1,+\infty) : \bar{Q}_p=+\infty\big\}, \quad \bar{Q}_p=\limsup\limits_{k\rightarrow\infty}Q(k)
\\
q_u=\sup \big\{p\in[1,+\infty) : \underset{\bar{}}{Q}{}_p=0\big\}, \quad \underset{\bar{}}{Q}{}_p=\liminf\limits_{k\rightarrow\infty}Q(k)
\end{cases}
\end{equation}
\begin{equation}\tag{$Q_L$}\label{def Q_L}
\lim\limits_{k\rightarrow \infty}
\frac{\ln e_{k+1}}{\ln e_k}=p_0
\end{equation}
\(\forall \varepsilon>0, \exists A,B\geq 0, \ k_0 \geq 0\) s.t.
\begin{equation}\tag{$Q_{I,\varepsilon}$}\label{f. def Q_eps}
A\cdot e_k ^{p_{0}+\varepsilon}\leq e_{k+1} \leq B\cdot e_k^{p_{0}\varepsilon},\ \; \; \forall k\geq k_0
\end{equation}
\begin{equation}\tag{$Q_\Lambda$}\label{def Q_Lam}
\lim\limits_{k\rightarrow \infty}
\frac{\ln \frac{e_{k+2}}{e_{k+1}}}{\ln \frac{e_{k+1}}{e_k}}=p_0.
\end{equation}
Twenty years after the classical book of Ortega and Rheinboldt was published, the above definitions for the Qorders were independently and rigorously studied (i.e., some orders characterized in terms of others), by Potra (1989), resp. Beyer, Ebanks and Qualls (1990). The relationship between all the five definitions (only partially analyzed in each of the two papers) was not subsequently followed and, moreover, the second paper slept from the readers attention.
The main aim of this paper is to provide a rigorous, selfcontained, and, as much as possible, a comprehensive picture of the theoretical aspects of this topic, as the current literature has taken away the credit from authors who obtained important results long ago.
Moreover, this paper provides rigorous support for the numerical examples recently presented in an increasing number of papers, where the authors check the convergence orders of different iterative methods for solving nonlinear (systems of) equations.
Authors
Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)
Keywords
Cite this paper as
E. Cătinaş, A survey on the high convergence orders and computational convergence orders of sequences, Appl. Math. Comput., 343 (2019) 120.
doi: 10.1016/j.amc.2018.08.006
About this paper
Print ISSN
00963003
Online ISSN
Google Scholar citations
Errata
The sequence \(z_k\) from Example 2.8 actually does not have Qorder \(2\):
\[
z_k = \begin{cases} 2^{2^k/k}, & k \text{ odd}\\ 2^{k2^k}, & k \text{ even.} \end{cases}
\]
Post version
November 11, 2018: post created.
[1] W.A. Beyer, B.R. Ebanks, C.R. Qualls, Convergence rates and convergenceorder profiles for sequences, Acta Appl. Math. 20 (1990) 267284.
CrossRef (DOI)
[2] W.A. Beyer, P.R. Stein, Period doubling for trapezoid function iteration: metric theory, Adv. Appl. Math., 3 (1982), pp. 117.
CrossRef (DOI)
[3] W.A. Beyer, P.R. Stein, Further results on periods and period doubling for iterates of the trapezoid function, Adv. Appl. Math., 3 (1982), pp. 265287.
CrossRef (DOI)
[4] E. Bodewig, On types of convergence and on the behaviour of approximations in the neighborhood of a multiple root of an equation, Quart. Appl. Math., 7 (1949), pp. 325333
CrossRef (DOI)
[5] N. Bourbaki, Fonction d’une Variable Réelle. Livre 4. Chapitre 5. Hermann, Paris, 1951.
[6] R. Brent, The computational complexity of iterative methods for systems of nonlinear equations, in: Miller R.E., Thatcher J.W., Bohlinger J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA, 1972
[7] R.P. Brent, Some efficient algorithms for solving systems of nonlinear equations, SIAM J. Numer. Anal., 10 (1973), pp. 327344.
CrossRef (DOI)
[8] R.P. Brent, Algorithms for minimization without derivatives, PrenticeHall, Englewood Cliffs, New Jersey, 1973.
[9] R.P. Brent, S. Winograd, P. Wolfe, Optimal iterative processes for rootfinding, Numer. Math., 20 (1973), pp. 327341.
CrossREf (DOI)
[10] C. Brezinski, Comparaison des suites convergences, Revue Française d’Informatique et de Recherche Operationelle, 5 (1971) no. 2, pp. 9599.
CrossREf (DOI)
[11] C. Brezinski, Accélération de la Convergence en Analyse Numérique, SpringerVerlag, Berlin, 1977.
[12] C. Brezinski, Limiting relationships and comparison theorems for sequences, Rend. Circolo Mat. Palermo, Ser. II, vol. 28 (1979), pp. 273280.
CrossRef (DOI)
[13] C. Brezinski, Vitesse de convergence d’une suite, Rev. Roumaine Math. Pures Appl., 30 (1985), pp. 403417.
[14] W. Burmeister, J.W. Schmidt, On the ROrder of Coupled Sequences II, Computing, 29 1982, pp. 7381.
CrossRef (DOI)
[15] W. Burmeister, J.W. Schmidt, On the ROrder of Coupled Sequences III, Computing, 30 1983, pp. 157169.
CrossRef (DOI)
[16] E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, pp. 543570.
CrossRef (DOI)
[17] E. Cătinaş, On accelerating the convergence of the successive approximations method, Rev. Anal. Numér. Théor. Approx., 30 (2001) no. 1, pp. 38.
Paper on author’s website
[18] E. Cătinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473485.
CrossRef (DOI)
[19] E. Cătinaş, The inexact, inexact perturbed and quasiNewton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291301.
Crossref (DOI)
[20] R. Cavanagh, Difference equations and iterative processes, Doctoral thesis, Univ. of Maryland, College Park, 1970.
[21] A.I. Cohen, Rate of convergence and optimality properties of root finding and optimization algorithms, Doctoral dissertation, University of California, Berkeley, 1970.
[22] A. Cordero, J.R. Torregrosa, Variants of Newton’s method using fifthorder quadrature formulas, Appl. Math. Comput. 190 (1) (2007), 686698.
CrossRef (DOI)
[23] R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (2) (1982) 400408.
CrossRef (DOI)
[24] J.E. Dennis, On Newtonlike methods, Numer. Math. 11 (1968) 324330.
CrossRef (DOI)
[25] J.E. Dennis Jr., J.J. Moré, A characterization of superlinear convergence and its application to quasiNewton methods, Math. Comput. 28 (126) (1974) 549560.
CrossRef (DOI)
[26] F. Dubeau, On comparisons of ChebyshevHalley iteration functions based on their asymptotic constants, Int. J. Pure Appl. Math. 85 (5) (2013) 965981.
CrossRef (DOI)
[27] S.C. Eisenstat, H.F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput. 17 (1) (1996) 1632.
CrossRef (DOI)
[28] A. Feldstein, R.M. Firestone, Hermite interpolatory iteration theory and parallel numerical theory, Division of Applied Mathematics, Brown University, 1967 Report.
[29] A. Feldstein, R.M. Firestone, A study of Ostrowski efficiency for composite iteration algorithms, in: Proceedings of the 1969 24th National Conference, ACM, 1969.
CrossRef (DOI)
[30] A. Feldstein, Bounds on order and Ostrowski efficiency for interpolatory iteration algorithms, California University/Lawrence Livermore Lab., Livermore, USA, 1969 Report ucrl72238.
[31] J. Fourier, Question d’analyse algébrique, Bull. Sci. Soc. Philos. 67 (1818) (2018) 61–67. http://gallica.bnf.fr/ark:/12148/bpt6k33707/f248.item, accessed February 23, 2018
[32] M. GrauSánchez, M. Noguera, J.M. Gutiérrez, On some computational orders of convergence, Appl. Math. Lett. 23 (2010) 472478.
CrossRef (DOI)
[33] M. GrauSánchez, M. Noguera, A. Grau, J.R. Herrero, On new computational local orders of convergence, Appl. Math. Lett. 25 (2012) 20232030.
CrossRef (DOI)
[34] M. GrauSánchez, M. Noguera, On convergence and efficiency in the resolution of systems of nonlinear equations from a local analysis, in: S. Amat, S. Busquier (Eds.), Advances in Iterative Methods for Nonlinear Equations, SEMA SIMAI Springer Series, 10, Springer, 2016.
CrossRef (DOI)
[35] R. Hauser, J. Nedic, On the relationship between the convergence rates of iterative and continuous processes, SIAM J. Optim. Appl. 18 (1) (2007) 5264.
CrossRef (DOI)
[36] J. Herzberger, L. Metzner, On the qorders of convergence of coupled sequences arising in iterative numerical processes, Computing 57 (1976) 357–363.
CrossRef (DOI)
[37] N.J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008.
[38] M. Igarashi, T. Ypma, Empirical versus asymptotic rate of convergence of a class of methods for solving a polynomial equation, J. Comput. Appl. Math. 82 (1997) 229237.
CrossREf (DOI)
[39] L.O. Jay, A note on qorder of convergence, BIT 41 (2) (2001) 422429.
CrossRef (DOI)
[40] J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
CrossRef (DOI)
[41] J.M. Ortega, M.L. Rockoff, Nonlinear difference equations and GaussSeidel type iterative methods, SIAM J. Numer. Anal. 3 (3) (1966) 49–513.
CrossRef (DOI)
[42] A. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York, 1960 (2nd ed. 1966). 3rd edition published as Solution of Equations in Euclidean and Banach Spaces, Academic Press, 1973, New York and London.
[43] I. Pavaloiu, Sur l’ordre de convergence des méthodes d’itération, Mathematica, 23 46 (1) (1981) 261–272. (in French). http://ictp.acad.ro/convergenceorderiterativemethods/ accessed March 22, 2018.
paper on author’s website
[44] I. Pavaloiu, Approximation of the roots of equations by AitkenSteffensentype monotonic sequences, Calcolo 32 (1–2) (1995) 6982.
CrossRef (DOI), paper on author’s website
[45] I. Pavaloiu, Optimal algorithms concerning the solving of equations by interpolation, in: Research on Theory of Allure, Approximation, Convexity and Optimization, Editura Srima, ClujNapoca, Romania, 1999, pp. 222248. ISBN 9739855143. http://ictp.acad.ro/optimalalgorithmsconcerningsolvingequationsinterpolation/ accessed March 22, 2018.
paper on author’s website
[46] I. Pavaloiu, On the convergence of one step and multistep iterative methods, Unpublished manuscript, http://ictp.acad.ro/convergence one step multistep iterative methods/, accessed April 1st, 2018.
paper on author’s website
[47] F.A. Potra, On Qorder and Rorder of convergence, J. Optim. Theory Appl. 63 (3) (1989) 415431.
CrossRef (DOI)
[48] F.A. Potra, V. Pták, Nondiscrete Induction and Iterative Processes, Pitman, Boston, Massachusetts, 1984.
[49] F.A. Potra, Qsuperlinear convergence of the iterates in primaldual interiorpoint methods, Math. Program. Ser. A 91 (2001) 99115
CrossRef DOI)
[50] F.A. Potra, Primaldual affine scaling interior point methods for linear complementarity problems, SIAM J. Optim. 19 (1) (2008) 114143.
CrossRef (DOI)
[51] M. Raydan, Exact order of convergence of the secant method, J. Optim. Theory Appl. 78 (3) (1993) 541551.
CrossRef (DOI)
[52] W.C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, 2nd. ed., SIAM, Philadelphia, 1998
[53] J.W. Schmidt, On the rorder of coupled sequences, Computing 26 (1981) 333342.
CrossREf (DOI)
[54] H. Schwetlick, Numerische Lösung Nichtlinearer Gleichungen, VEB, Berlin, 1979.
[55] F. Soleymani, On finding robust approximate inverses for large sparse matrices, Linear Multilinear Algebra 62 (10) (2014) 13141334.
CrossRef (DOI)
[56] R.A. Tapia, J.E. Dennis Jr., J.P. Schäfermeyer, Inverse, shifted inverse, and Rayleigh quotient iteration as Newton’s method, SIAM Rev. 60 (1) (2018) 355.
CrossRef (DOI)
[57] L. Tornheim, Convergence of multipoint iterative methods, J. ACM 11 (1964) 210220.
CrossRef (DOI)
[58] J.F. Traub, Iterative Methods for the Solution of Equations, PrenticeHall, Englewood Cliffs, N.J., 1964.
[59] R. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, New Jersey, 1962.
[60] R.G. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, University of Maryland, College Park, Maryland, Ph.D. Diss.
[61] R.G. Voigt, Orders of convergence for iterative procedures, SIAM J. Numer. Anal. 8 (1971) 222243
CrossRef (DOI)
[62] H.F. Walker, An approach to continuation using Krylov subspace methods, in: J. Periaux (Ed.), Computational Science in the 21st Century, John Wiley and Sons, Ltd., 1997, pp. 7281
paper on author website
[63] D.D. Wall, The order of an iteration formula, Math. Comput. 10 (55) (1956) 167168.
CrossRef (DOI)
[64] L. Wang, Symbolic dynamics for a class of unimodal maps and a metric property of bifurcation in trapezoidal maps (period doubling, contiguity of harmonics, quadratic convergence), State University of New York at Buffalo, 1986 Ph.D. thesis.
[65] S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with accelerated thirdorder convergence, Appl. Math. Lett. 13 (8) (20 0 0) 8793.
CrossRef (DOI)
[66] S.J. Wright, PrimalDual InteriorPoint Methods, SIAM, Philadelphia, 1997.
[67] Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley, 1997.
[68] T.J. Ypma, Historical development of the NewtonRaphson method, SIAM Rev. 37 (4) (1995) 531551
CrossRef (DOI)
[69] R. Zhang, L. Wang, Two convergence problems for monotone sequences, Acta Appl. Math. 47 (1997) 213220.
CrossRef (DOI)
A survey on the high convergence orders and
computational convergence orders of sequences
author address: Tiberiu Popoviciu Institute of Numerical Analysis, Romanian
Academy, P.O. Box 681, ClujNapoca, Romania. email: ecatinas@ictp.acad.ro,
www.ictp.acad.ro/catinas
version submitted to Appl. Math. Comput., published with some changes in vol.
343 (2019) 120.
Abstract
Twenty years after the classical book of Ortega and Rheinboldt was
published, five definitions for the
convergence
orders of sequences were independently and rigorously studied (i.e.,
some orders characterized in terms of others), by Potra (1989), resp.
Beyer, Ebanks and Qualls (1990). The relationship between all the five
definitions (only partially analyzed in each of the two papers) was not
subsequently followed and, moreover, the second paper slept from the
readers attention.
The main aim of this paper is to provide a rigorous, selfcontained,
and, as much as possible, a comprehensive picture of the theoretical
aspects of this topic, as the current literature has taken away the credit
from authors who obtained important results long ago.
Moreover, this paper provides rigorous support for the numerical
examples recently presented in an increasing number of papers, where
the authors check the convergence orders of different iterative methods
for solving nonlinear (systems of) equations. Tight connections
between some asymptotic quantities defined by theoretical and
computational elements are shown to hold.
Keywords. convergent sequences in
${\mathbb{R}}^{n}$;
Q, C, and Rconvergence orders of sequences; computational convergence
orders.
MSC 2010. 65J05.
1 Introduction
Consider in the beginning a sequence
from
, which converges
to a finite limit
.
Its speed of convergence is characterized by several measures, called convergence
orders, which are fundamental notions in Mathematical and in Numerical
Analysis.
The relation
$$\underset{k\to \infty}{\mathrm{lim}}$$

(1) 
gives the classical definition of the convergence with order
, and,
in a less rigorous but sufficiently intuitive statement, it can be traced back in
1818, to Fourier [1]. Even deeper traces may be found in history: in a letter of
Newton dated in 1675, it appears he was aware of the rough doubling of the
number of correct significant digits in one step (characteristic to the
quadratic convergence) of the iterative method which bears his name
[2].
The existence of the nonzero value
is a
very restrictive condition not only in theory, but also in examples from
practice – not to mention that in the multidimensional setting it is a
normdependent problem. Moreover, as it requires the knowledge of both
and
,
relation (1 ) is only of theoretical use.
Still, such definition (along with the
superlinear convergence,
which requires
for
$p=1$)
is extremely important in studying the local convergence of the main
iterative methods for nonlinear problems, either of Newton type (see,
e.g., [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13]), or the more general
successive approximations (see, e.g., [3], [4, ch. 10], [6], [14], [15]) – which,
under some supplementary assumptions (including smoothness) may
be regarded in fact as equally general (see [14]). This definition is also
important in the field of the matrix function theory (polar decomposition,
matrix sign function, computing the matrix inverse by Schulz or different
iterative methods), in a setting where the matrix is an element of a normed
space (see, e.g., [16], [17]); we should also mention the acceleration of
the convergence of sequences (see, e.g., [18]), and perhaps other fields
too.
From a numerical standpoint, the aim is to define the socalled
computational convergence orders, that iteratively approximate the convergence
orders using only the elements of the sequence known at the step
.
To this end (or just for theoretical purposes) new definitions have been
introduced and studied. We attempt to follow the origin of each notion in the
following section; this is a difficult task, as most of the papers treat the
convergence orders as a collateral topic; no survey has been written since two
monographs containing entire chapters devoted to the rigorous analysis of the
– and
convergence
orders. The book of Ortega and Rheinboldt [4], though first published in 1970, is
a standard reference in the field of iterative methods and their convergence orders
(see also [6]); it was republished in 2000 in the Classics in Applied Mathematics
series of SIAM. The book of Potra and Pták (1984) [8] contains further,
complementary results.
Two important papers were subsequently published, independently and close
in time, where the equivalence of different definitions of (computational)
– and
convergence
orders were given. The complementary results of these two works allow us to
form a complete, simplified and rigorous picture of the topic. The first paper was
written by Potra (1989) [19]; as of November 2017, Scholar Google reported 96
citations of it, which shows that the mathematicians are aware of it. The other
paper however, written by Beyer, Ebanks and Qualls (1990) [20], is almost
unknown to the mathematical community: as of November 2017, we have found
only 6 citations in Google Scholar (out of which two papers in Chinese, two
papers in the field of Bioarchaeology, one paper solving an unsolved problem
from [20], and one paper dealing with the quadratic convergence in period
doubling for trapezoid maps).
Unfortunately, the fact that the paper of Beyer, Ebanks and
Qualls remained unknown, allowed some authors to (honestly)
reinvent such notions, e.g., in [21] and [22]. The very cited paper
[21]^{1}
has the distinctive feature that not only the definition of the
computational convergence order proposed there is not original
(nor proved, nor in fact entirely computational – as it requires
), but even
the iterative method itself (as it was given in the well known book of J.F. Traub [23,
formula (814), p. 164]^{2} ).
In numerous works, the classical
$Q$–
and
orders
defined by Ortega and Rheiboldt lead to statements expressed as
”
has
order (at
least)
and
order
(at least)
,
”. The
order
we study here is a completion to the classical one, and no
longer allows such conclusions. Instead, if having at all an order
,
the sequences will be only in one of the cases (the
order
is obtained by taking norms in (1)):
$\{{x}_{k}$has
$R$order
${p}_{0}$
(but neither
$C$–
$Q$
nororder);
$\{{x}_{k}$has the same
$R$–
$Q$
andorder
${p}_{0}$
(but no
$C$order);
$\{{x}_{k}$has the same
$R$,
$Q$
–
$C$
andorder
${p}_{0}$
.
In less words, the relation reads for
${p}_{0}$as
$$C\mathrm{\text{order}}{p}_{0}$$ 
with no converse implication holding in general.
Nonetheless, the comments of Tapia, Dennis Jr. and
Schäfermeyer [13, p. 49] remain true: “The distinction between
– and
convergence
is quite meaningful and useful and is essentially sacred to workers in the area of
computational optimization. However, for reasons not well understood,
computational scientists who are not computational optimizers seem to be at
best only tangentially aware of the distinction.”
The structure of this paper is the following: in Section 2 we
review, in chronological order, the definitions of convergence
orders. In Section 3 we analyze the high convergence orders
(
), giving full
proofs for
–
and
$Q$orders.
We present first the relation (implication, resp. equivalence) between the introduced
convergence orders; the results are based on the proofs from [19] and [20], which
we can simplify for some cases. Then we review the main properties of the
orders. We analyze next
the computational
– and
convergence orders
based on the corrections
(the approach was dealt with in [20], but the authors assumed real and monotone
sequences in treating certain cases; a result of Potra and Pták [8] and
the DennisMoré lemma [5] allow us to complete the proofs). We also
consider computational convergence orders based on the nonlinear residuals
,
when solving nonlinear systems of equations having the same number
of equations and unknowns. The section ends with a summary of all
the relations obtained, illustrated by a diagram. Finally, in Section 4
we recall, without proofs, the relationships between some convergence
orders in the linear case. Some conclusions are presented in the end of the
paper.
2 Definitions – a brief historical review
2.1 C and Qtype (computational) convergence orders.
2.1.1 Convergence orders based on the errors x*xk
We turn now our attention to a sequence
from
, which converges
to a finite limit
;
we prefer the common setting of a normed
space—
endowed with
a given norm
—though
most of the results from this paper can be presented in a
more general setting, of a metric space. We assume that
.
Since this leads to dealing with positive numbers, we can simplify the notations
and consider further only the errors (called such as a short for ”norms of errors”)
$${e}_{k}$$

As we have mentioned, the oldest definition of convergence with order
is
that
$$\underset{k\to \infty}{\mathrm{lim}}$$

(2) 
which we call, as in [20],
convergence with
order
(the linear
convergence requires
and
$0<{C}_{1}$)
–
comes from quotient. If it exists, it is uniquely defined and it implies that
such
that
$$({C}_{{p}_{0}}$$
</msubsup > 
(3) 
or, less sharp, the existence of
$A,B>0$such that
$$A{e}_{k}^{{p}_{0}}$$
</msubsup > 
(4) 
Remark 2.1 a) For example, if
and
${C}_{2}$is not too large, relation (3 ) says that the error is approximately squared at
each step
,
for
sufficiently large.
b) Some authors have used (4 ) to define the exact
$Q$order
of convergence
(see [24], [18], [25], [8], [26], [19]).
c) An inequality of the form (4 ) still holds if the limit in (2 ) does not exist, but
instead
and
$\mathrm{limsup}$are finite and nonzero. Denoting
$$\phantom{\rule{0.33em}{0ex}}{\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$$  (5) 
relation
$$0<{\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$$  (6) 
implies (4 ):
$0<{\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$attracts the
first inequality in (4 ), while
the second one (see also [4, 9.3.3]).
d) As widely known, the larger the order
, the
faster the speed of convergence.
The
$C$order
is a normdependent notion, as the following two examples show for the
orders
and
.
Example 2.2 [27] Let
,
the sequence
$${x}_{k}$$

(7) 
Consider the norms
$$\parallel (u,v){\parallel}_{A}$$ 
It follows
${C}_{1}$
the
norm, while
does not exist
for the
norm.
and
$${x}_{k}$$

(8) 
One obtains
${C}_{2}$when
considering the maximum norm
,
while
does not
exist for the norm
.
The following definition for the convergence order seems to be the
second oldest one (we adopt the notation from [20]). The sequence
has
convergence
order
if:
$${Q}_{L}$$

(9) 
Remark 2.4 a) As noticed by Brezinski in [28] and [26],
is a particular case of a definition used by Bourbaki [29] in order to compare
the convergence orders of two sequences.
The measure
${Q}_{L}$was then independently considered by Wall in 1956 [30] (see also [31], [4,
ch. 9], [32, ch. 2] and [25]), argued – for
instead of
$\mathrm{ln}$– as the limit of the quotient of two consecutive numbers of correct decimal
places in
resp.
${x}_{k}$(see also [8, p. 90]); in this sense, convergence for example with
${Q}_{L}$order
means intuitively that, from a certain step, the number of correct digits are
doubled the successive elements of
.
The logarithm base may be taken as any positive real number
;
we shall consider further the natural base
for simplicity.
b) In contrast to
${Q}_{{p}_{0}}$,
the expression
does not require the (usually unknown) value
${p}_{0}$of the order, but provides an approximation of it. This may be advantageous
in certain situations when evaluating the order, as it turned out, e.g., in the
books of Wright [33, p. 252 and Ch. 7], Ye [34, p. 210, p. 226] and in two
papers of Potra [35] and [36] (where the authors deal with
,
a quantity which we analyze in Proposition 3.3 ).
c) Brent, Winograd and Wolfe noticed in [37] that
$C$order
immediately implies
${Q}_{L}$order,
of same value.
d) We shall see later, in Remark 3.8 , that this notion (cf. [38]), as well as
the other
orders,
is normindependent (also noted by Potra [19]).
In 1967, Feldstein and Firestone [39] introduced essentially
the following convergence order, which we denote here by
.
The sequence
$\{{x}_{k}$has
${Q}_{}$convergence
order
if:
$$\begin{array}{}\end{array}$$
Condition
${p}_{0}$will be a standing assumption from here on, in all subsequent
formulas, while in Section 3 we will implicitely assume that
.
The convergence with
convergence
order
can be expressed in a more intuitive form (see also [20]):
$$\begin{array}{}\end{array}$$
Two years later, the same authors [40] expressed the above order
in an equivalent form, which in fact will be the same as the
order
defined below. Let
They noticed that
$0\le {\lambda}_{\ast}$, and
when
, the sequence was
said to have the order
.
In their classical book from 1970, Ortega and Rheinboldt [4,
Ch. 9] introduced and studied the quantity denoted in (5) by
for
all
:
$${}_{}$$

They shown the following behavior for
as a
”function” of
.
Proposition 2.5 [4, 9.1.2] Exactly one of the following conditions holds:
a)
b)
c)
$\exists {p}_{0}$s.t.
${\overline{Q}}_{p}$$\forall p\in [1,{p}_{0}$
and
${\overline{Q}}_{p}$$\forall p\in \left({p}_{0}\right).$
The quantity
$${q}_{l}$$

(12) 
(called in [4] as
$Q$convergence
with order at least
and denoted by O
${}_{Q}$)
stood there and in many subsequent works for a measure of
the convergence order. We call it, as in [20], the lower
order, and
denote it by
(instead of
${p}_{l}$used there). We shall see that the lower
order needs to be completed
by the upper
order for
obtaining the ”full”
order;
as a matter of fact,
,
the lower order from (11) defined in [40].
was said in [4, Def. 9.1.4] that converges faster than
if for
some
we
have
(it is interesting to note that if these two upper bounds are finite and nonzero, the
inequality may revert when changing the norm [4, p. 285]). However, in the case
of the even stronger relation
$$0<{C}_{{p}_{0}}$$ 
numerical evidence reveals that
$\{{x}_{k}$does not necessarily converge faster than
$\{{y}_{k}$,
as shown by Ypma and Igarashi [41].
On the other hand, as noticed by Brezinski [26], the sequences given by
,
have the same asymptotical constant,
,
though they converge with quite different speeds.
Some further comments on this topic will be made in Remark 2.11 .
In 1979, Schwetlick [25, B.4.2.3] defined the
convergence
order in the following way, which will be used throughout the paper. Let the lower
order
be
given in (12 ), recall the notation from (5)
$${}_{}$$

and define the upper
$Q$order
by
$${q}_{u}$$ 
Then the
$Q$convergence
is with order
if
${p}_{0}$This definition is equivalent to the one given by Feldstein and Firestone in (11),
as
and
${q}_{u}$.
In 1981, Schmidt [42] introduced the following type of convergence order, denoted here,
as in [20], by
:
has
convergence
order
if
$${Q}_{\Lambda}$$

(13) 
The author gave no result relating the
– and
orders he introduced,
and assumed that
is
equivalent to an
order
(while it is in fact a
order,
as we shall see).
In 1982, Beyer and Stein [43] independently introduced
the measure (19 ) below, which is somehow similar to
, and in fact
equivalent to
defined in subsubsection 2.1.2 .
In 1985, unaware of [42] and [43], Brezinski [26] considered the
convergence order
and, assuming that
$\{{x}_{k}$has the exact
$Q$order of
convergence
(as defined
by (4 )), he proved that
has the
${Q}_{\Lambda}$order
(and
order
as
well).
In 1989, Potra introduced in [19] the following type of convergence order (denoted
here by
,
with ”
”
from ”inequality”), which will be useful in obtaining some simplified
proofs.
The sequence
$\{{x}_{k}$has
${Q}_{I,}$convergence
order
if
$\forall >0,$ $\exists a,b>0$such
that
$$a{e}_{k}^{{p}_{0}}$$

(14) 
This can be regarded as a generalization of inequalities (4 ).
Potra shown some fundamental results in our study, that
convergence
with order
is
equivalent to
– and
to
convergence
of same order, which we denote here, as in [20], by symbols between curled
braces:
$$\left\{{Q}_{}\right\}.$$ 
Ortega and Rheinboldt [4, N.R. 9.2.2] have previously noticed a weaker property of
convergence with order
, namely that it implies
(partial)
convergence
with order
(i.e., in the
notations below, that
).
In the same paper, Potra has also considered the lower and upper
orders, when noting that if
a sequence has exact
order
then
.
In 1990, Beyer, Ebanks and Qualls [20], unaware of the definitions
and the results mentioned above, introduced the definitions of the
– and
orders
and shown some other fundamental results, that convergence with
order
is equivalent
to
and to
convergence
with same order:
$$\left\{Q,{Q}_{L}\right\}.$$ 
They considered
${Q}_{\Lambda}$inspired by the similar measure (19), as we have already mentioned.
We end the historical remarks by noting that the references [44], [45] and [46]
are cited in certain works as containing aspects referring to convergence orders,
but we were not able to consult them.
Lemma 3.1 from Section 3 shows that
(which justifies
the terminology lower/upper); when this inequality is strict, the sequence does not have
a
order,
as shown below.
$${}_{}$$

We get
$${}_{}$$

The graphical illustration of
and
leads to the so called convergence profile of the sequence, as termed in [20]
(see Fig. 1 ).
This sequence does not have a
order, as
, but it converges
with (exact)
order
,
as defined later. We note the classical statement in this case,
”
converges
with
order
(at least)
and
with
order
(at least)
”,
which no longer holds in the setting of this paper.
An elementary example shows that in case of convergence with
order
apart
of finite nonzero values of one (or both) of the asymptotical constants
, any
of the following relations may hold:
$${}_{}$$

It is easy to verify that for
${p}_{0}$the sequences
$\left\{{x}_{k}\right\},\left\{{y}_{k}\right\},\left\{{z}_{k}\right\}$verify respectively (15), (16) and (17) (
$\{{x}_{k}$was also considered in [20]).
Schwetlick [25, Ü.4.2.3, p. 93] also considered an example of the type
,
,
for the errors
converging with exact
$Q$order
.
Potra [19] considered
$${}_{}$$

which has
$Q$order
and
${\overline{Q}}_{2}$.
Jay [27] considered the sequence of the type
${x}_{k}$</msup >,
even,
${x}_{k}$</msup >
odd, which satisfies (17) for
${p}_{0}$.
One may easily find examples when
${\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$and
${\overline{Q}}_{{p}_{0}}$is finite, nonzero, or, on the other hand, when
${\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$is finite, nonzero and
${\overline{Q}}_{{p}_{0}}$.
Jay [27] considered the sequence
,
odd,
${x}_{k}$,
even, for
$q\ge 1$,
,
for which one obtains
and
${\overline{Q}}_{q}$.
Further examples, to be analyzed either elementary or with the aid of the
results from this paper, were given by Potra and Pták [8, p. 93]:
,
,
and also
${x}_{2k}$</msup >,
</msup >,
.
Remark 2.9 Despite the fact that conditions (15 )–(17 ) may seem rather
abstract (or, at least, suitable for scholar examples), they do occur in relevant
situations from theory or practice. For a nontrivial illustration, we refer
the reader to a computational optimization problem [33, p. 252 and Ch. 7],
where one has
and
${\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{2}$.
Remark 2.10 When
${\overline{Q}}_{1}$i.e.,
$$\underset{k\to \infty}{\mathrm{lim}}$$

it is said that the sequence converges (at least)
$Q$superlinearly.
The convergence is strict
superlinearly,
when
(i.e.,
${\overline{Q}}_{p}$,
);
there are three cases in this situation:
,
i.e.,
order
(see Example 3.6 ),
$1={q}_{l}$,
resp.
,
(see Example 2.14 b), formula (24)).
It is worth noting that one may also obtain
${q}_{l}$,
in lack of
$Q$superlinear
(and even linear) convergence, shown in Example 2.14 d), formula (25)), as
.
Remark 2.11 Returning to the comments from Remark 2.6 ,
we note that the comparison of the convergence of two sequences
,
having
errors
resp.
$\{{e}_{k}^{\prime \prime}$is
important in particular in the field of the acceleration of the convergence of sequences,
when sequences with (at most) linear convergence are considered; here it is said that
converges
faster than
if (see, e.g., [18]):
$$\underset{k\to \infty}{\mathrm{lim}}$$

(18) 
Now we see that this definition makes sense not only if the
orders
of the two sequences are different, but even if they are equal, as the above
condition is normindependent.
To show this, we consider the terminology proposed by Jay [27] for a sequence converging
with
order
, who
defined that the convergence is with:
$Q$suborder
${p}_{0}$
if
${\overline{Q}}_{{p}_{0}}$,
$Q$superorder
${p}_{0}$
if
${\overline{Q}}_{{p}_{0}}$.
The last terminology is in fact widely used – recall the superquadratic convergence
(for
),
supercubic, etc.).
Now we see that for sequences with
order
we
can briefly say that:
$Q$superconvergence
$Q$
is faster than exact exact
$Q$convergence
$Q$
is faster thansubconvergence;
 (consequently)
$Q$superconvergence
$Q$
is faster thansubconvergence.
This can be illustrated by the following sequences having
order
:
</msup >
superquadratic),
</msup >
order
),
</msup >
subquadratic).
2.1.2 Computational convergence orders, based on the corrections xk+1xk
and the nonlinear residuals F(xk)
We consider now some quantities which do not require the limit
,
for which we adopt the terminology computational convergence
orders. As some of them require the knowledge of the order
itself,
we keep in mind that perhaps a more proper terminology for those would be
semicomputational.
As a notation, for the corresponding convergence orders
based on corrections we shall add a prime mark (e.g.,
) as in
[20], while for those based on nonlinear residuals, two prime marks (e.g.,
).
Corrections.
We introduce another notation, for the corrections (including their norms
too):
$${s}_{k}$$ 
In 1974 Dennis and Moré [5] obtained a result which shows that if a sequence converges
superlinearly,
then the errors and corrections converge precisely at the same rate (Lemma 3.14
from subsubsection 3.2.1 ).
In 1984, Potra and Pták [8] shown that a sequence converges
superlinearly iff the corrections
converge
superlinearly
(Proposition 3.13 ); in 1997 Walker [47] gave a different proof, also presented
later.
In 1982, Beyer and Stein [43] considered, for sequences in
, the
quantity
$$\frac{log\frac{{s}_{k}}{{s}_{k+1}}log\frac{{s}_{k1}}{{s}_{k}},}{}$$  (19) 
equivalent to
${Q}_{\Lambda}^{\prime}$defined below.
Three years later, Brezinski [26] proposed the use of the corrections
instead of the
(unknown) errors
in the definitions of the convergence orders studied there
(
and exact
order).
In 1990, Beyer, Ebanks and Qualls [20], taking the same approach, considered
$${Q}_{{p}_{0}}^{\prime}$$

with the resulted definitions being denoted correspondingly by
and
; we use here the same
convention for denoting
.
These authors proved the following fundamental results: for
, the
errors and corrections converge simultaneously to zero with the same
convergence order, and therefore each convergence order is equivalent to
its corresponding computational one. The following extended relation
resulted:
$$\left\{{C}_{{p}_{0}}\right\}\Rightarrow \{Q,{Q}_{}$$

However, the considered assumptions were very strong when proving
and
”
”:
was assumed as a
monotone sequence from
(see [20, Sect. 4]). We shall see that for the general setting, some results from [8]
and [5] may be used instead to obtain simplified proofs.
In 2010, GrauSánchez, Noguera and Gutiérrez [48], while studying connections
between
– and
orders (in the case
of a sequence from
with
$C$order
)
considered the ”extrapolated convergence order”
$$\frac{ln\frac{{x}_{k+1}}{{x}_{k}}ln\frac{{x}_{k}}{{x}_{k1}},}{}$$  (20) 
where
${\stackrel{~}{\alpha}}_{k}$. This convergence order
was obtained from
by replacing the unknown limit with an extrapolation
given by
the Aitken
method (in order to use only the terms known at the step
).
However, this convergence order is valid only in the one dimensional case, since the
Aitken
acceleration process does not have a direct extension to
.
We do not pursue this definition as, for high convergence orders, it is equivalent
to
.
In 2012, GrauSánchez, Noguera, Grau and Herrero [49] considered another
extrapolated convergence order
$$\frac{ln\left{x}_{k}\right}{ln\left{x}_{k1}\right},$$  (21) 
for a sequence from
$\mathbb{R}$,
having
order
. Assuming
order,
they shown some connections to the convergence orders (22) and (23)
below.
In [48] and [49] the authors used the technique of asymptotic
expansions in order to relate different convergence orders of
,
and
for
sequences
from
$\mathbb{R}$.
However, this approach could not be extended to the case of several
dimensions.
Remark 2.12 It is important to keep in mind that the
,
,
orders
are semicomputational orders, as they require the (supposed) unknown order,
while the logarithmbased
–
and
orders
are (fully) computational orders, i.e., they require neither the limit
nor the order
$p$in their expressions.
As certain numerical experiments (see [50] and the references therein)
have not revealed a clear superiority of
over
${Q}_{L}^{\prime}$,
the later seems to be the most convenient to use in practice (and in theory
too: see [33, p. 252 and Ch. 7], [34, p. 210, p. 226], [35] and [36]). Moreover,
Propositin 3.3 and Theorem 3.15 will show, in terms we will define later,
that
and
${q}_{u}$.
Nonlinear residuals.
Other computational convergence orders were considered
in the context of solving nonlinear systems of equations
,
, with solution
. For simplicity,
we shall denote
(resp.
${f}_{k}$when
$n=1$).
In 1981, Păvăloiu [51] defined the exact convergence order
corresponding to (4) by
$$A\parallel {F}_{k}$$
</msup > 
while in 1995, he introduced in [52] the expression
$$\frac{ln{f}_{k+1}}{ln{f}_{k}}$$  (22) 
and shown its equivalence to
${Q}_{L}^{\prime}$.
Also, while extending his results from 1999 [53], he introduced in an unpublished
manuscript [54] (posted on his website) the measure
$$\frac{ln{f}_{k+1}}{ln{f}_{k}}$$  (23) 
in connection with the above ones. However, since the manuscript was not
published as of 2011, the credit of first publishing this measure goes to
Petković, who mentioned in passing the above expression in a note published in
SIAM J. Numer. Anal. (2011).
Several computational aspects regarding these quantities were subsequently
analyzed (see, e.g., [50] and the references therein).
2.2 Rconvergence orders.
The root convergence order (
$R$order)
requires weaker conditions than the
–
and
orders,
but unfortunately at the price of loosing its theoretical importance and its practical
applications. As we have quoted in the Introduction, “The distinction between
– and
convergence is […]
essentially sacred to workers in the area of computational optimization” [13, p. 49], meaning
that the
order
is a much less powerful notion.
In Example 3.11 is presented a sequence for which, depending on the parameters, the
lower
order
is arbitrary close to
from above, while
the (exact)
order
is arbitrary high (and even higher is the upper
order
).
We shall review certain results, but not treat all of them in the same detail as we
will for the
–
and
orders.
In 1970, Ortega and Rheinboldt [4, 9.2] introduced and
studied the root convergence factors, which we denote here by
:
$${}_{}$$

Unlike the quotient factors, the root factors do not relate each two
consecutive terms, but consider some averaged asymptotic quantities.
They proved a Proposition similar to Proposition 2.5 , but here
takes
the role of
for
${\overline{Q}}_{p}$.
Proposition 2.13 [4, 9.2.3] Exactly one of the following conditions holds:
a)
b)
c)
$\exists {p}_{0}$s.t.
${\overline{R}}_{p}$$\forall p\in [1,{p}_{0}$
and
${\overline{R}}_{p}$$\forall p\in \left({p}_{0}\right).$
The lower
$R$order,
which we denote here by
(instead of
${O}_{R}$in [4, 9.2]), defined by
$${}_{}$$

stood in [4] and in many subsequent works as the definition of the root
convergence order.
Remark 2.14 a) [4, p. 290] If there exists a
with
then for
any
with
there
exists a
such that either
$${e}_{k}$$

or
$${e}_{k}$$
</msup > 
b) The value
arises in the analysis of the speed of convergence of sequences with the errors
satisfying different recurrence inequalities.
The simplest ones appear in usual circumstances for the secant method (see
[3], [9], and also [37]):
$${e}_{k+1}$$ 
and they yield the wellknown
${r}_{l}$order
.
It is important to note that the secant method then attains the same value
also for the lower
order
For the more general inequalities
$${e}_{k+1}$$

Schmidt [42], Burmeister and Schmidt [55], [56] resp. Potra and Pták
[8, p. 107] determined in a series of works the lower
order
.
It is interesting to note that for such inequalities, Herzberger and Metzner
[57] and then Potra [19] gave certain sufficient conditions for the lower bound
. Potra
[19] has also noted that the above inequalities do not necessarily attract lower
order
${q}_{l}$greater than one: take
$${e}_{k+1}$$

(24) 
with
${e}_{0}$
satisfies
(which
immediately attracts
and
${r}_{l}$), but
in fact
,
(and
, as
we shall see).
Certain iterative methods have lead to some different inequalities, of the type
[4, Th. 9.2.9.]
$${e}_{k+1}$$

or of other types, analyzed in [23] (see also [58]).
c) As noted in [4, N.R. 9.2.1], the
factor has been used implicitly in much work concerning iterative processes for
linear systems of equations, see, e.g., Varga [59]. For nonlinear systems, it was
used explicitly by Ortega and Rockoff [60].
d) Some connections between the errors and their majorizing sequences were made
by Dennis Jr. in [61] (see also [13, p. 49]). Potra [19] has noticed that the lower
order
${r}_{l}$
is consistent with the natural ordering of sequences, while the lower
order
is not:
given
with
errors
,
resp.
, if
and
has
order
then so
has
;
however, this statement does not hold for the lower
order
, as one may take
from Example
2.7 and
</msup >.
A more disturbing example was given by Jay [27], for
</msup >and
$${x}_{k}$$

(25) 
At the first sight, since
${e}_{k}^{\prime}$,
the speed of
seems higher
than of the (exact)
quadratic
, but though,
does not attain even
linear convergence, as
(we shall see that in this
case the upper
order
is
).
Another example was given in (24) above.
In 1973, Brent, Winograd and Wolfe [37] considered the following expressions,
which we denote here by
(in [32] Brent considered in the same year only
). The sequence was said
that converges with
order
if
, i.e.,
in a single condition,
$$\underset{k\to \infty}{\mathrm{lim}}$$
</msup >1k =p˙0. (27) $$$$ They noted that the $C$order easily implies order . In 1979, Schwetlick [25] considered the upper order
and (in the notations of this paper)
he defined the convergence with order if Similarly to the case of the $Q$order, superlinearly
with then for with there such that either
or
In 1989, Potra [19] has introduced and studied some further measures for the convergence order, , :
The exact $R$order order (4) if $\exists A,B>0$, such
we see that this definition can be immediately connected to the following one,
Potra has also considered the lower and upper orders, when noting that if order then . Comparing the list of $Q$– orders, the was not given before, so we consider it here, by denoting the expressions
and by defining the ${R}_{\Lambda}$order when , i.e.,
3 Results relating the high (computational) convergence ordersIn this section we consider $p>1$and present the relationships of different definitions of the – and orders. 3.1 Relationships between the convergence ordersThe equivalences and implications mentioned in the previous section can be $$\begin{array}{}\end{array}$$
However, as we intend to provide a selfcontained orders, 3.1.1 C and Qconvergence ordersWe shall need the three auxiliary results below.
Relations (iii) and (iv) show that ${q}_{l}$and justify the terminology ”lower” and ”upper”. Proof. [20] For (i), if ${\overline{Q}}_{p}$and $s<p,$then
For (iii), suppose $p<{q}_{l}$and choose $s\in \left(p,{q}_{l}\right).$By then, ${\overline{Q}}_{s}$. Now, The other statements are proved in a similar manner. _
Potra obtained the following general result, interesting in its own, which will
and
Proof. [19] Let
Then for any $>0$with ${p}_{0}$, there such that
We may assume that $\mathrm{ln}{e}_{k}$,
so that
This proves that ${\overline{Q}}_{{p}_{0}}$and, by Lemma 3.1 (i), we get
Suppose that
It follows by Lemma 3.1 (iii) that so there such $\forall k\ge 0,$ i.e.,
But then
which leads to
which is a contradiction. Hence, we have proved that implies ${p}_{1}$_
then $\{{e}_{k}$is monotone decreasing starting from a step $k\ge {k}_{0}$. Proof. [20] For some some $>0$sufficiently small, $\exists {k}_{0}$such that ${Q}_{\Lambda}$$\forall k\ge {k}_{0}$ Hence, the
. , contradictory to the Therefore, _ We present now the result relating the – and orders,
in and a convergent to . Then, ,
Moreover,
Proof. We give the proof in five steps: A. , B. , C. , D. and A1 ( ${C}_{{p}_{0}}$). A2 ( ${Q}_{L}$) B. The relation is obvious. C1 ( ${Q}_{}$) such Since , it follows such that ${Q}_{{p}_{0}}$$\forall k\ge 0,$ i.e., the second inequality The first inequality is obtained in the same way. C2 ( ${Q}_{I,}$) Suppose and $>0$with ${p}_{0}$we have
The second inequality implies ${\overline{Q}}_{{p}_{0}}$and by Lemma 3.1 (i), $\mathrm{lim}{Q}_{q}$s.t. $1<q<{p}_{0}$The first inequality (valid for all $>0$) and again with $p+<s.$The assertion follows since $$can be taken arbitrarily small. D. [19, Prop. 1.1] Using the above result, we get and E1 ( ${Q}_{\Lambda}$) , so it suffices . Let ${Q}_{\Lambda}$For any $>0,$we have ${Q}_{\Lambda}$for all $k$sufficiently large, and using Lemma 3.4 we get
which gives
i.e., ${Q}_{{p}_{0}}$$\forall k\ge {k}_{0}$ Considering now $\frac{}{}$we obtain similarly that
We prove that the monotone sequence is Otherwise, if $\exists M>0$s.t. $\frac{{e}_{k+2}}{}$
i.e., then according to Lemma Similarly, one can prove that for any with we have for all sufficiently large E2 ( ${Q}_{L}$) [20] we have
_ It is interesting to notice that convergence with implies However, the reverse is not true superlinear convergence convergence ),
and
which converges superlinearly to $0.$Suppose there exists ${p}_{0}$such that $\left\{{x}_{k}\right\}$converges order (and order) ${p}_{0}$Then $\forall >0$with ${p}_{0}$s.t. ${x}_{k+1}$Hence,
for all $k$sufficiently large, which contradicts the well known limit $\underset{t\to \infty}{\mathrm{lim}}$
. , . b) Some simpler examples can be found either as explicitly given by [32, p. 22], ${x}_{k}$ ${x}_{k}$</msup >, [4, E.9.2.1.j]. To show these assertions we can also use that ${Q}_{L}$or ${Q}_{\Lambda}$.
do not have elements to define the strict $Q$superlinear and ${\overline{Q}}_{p}$$\forall p>1$ . The $Q$superlinear superlinear
In fact, ${\overline{R}}_{1}$is a in all norms from ${\mathbb{R}}^{n}$. It is interesting to see that sequences with infinite order exist too, </msup >(from the list of exercises in [4, E.9.2.1]).
the existence of the $C$order , finite, ${\overline{Q}}_{p}$are normindependent. The same hold for ${\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{p}$, order. orders It is important to recall that for sequences with $Q$order , while this $Q$order and ${\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}Q\phantom{\rule{4.32828pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{1.88583pt}{0ex}}\phantom{\rule{4.32828pt}{0ex}}}_{{p}_{0}}$however, if finite, are normdependent [4, E.9.11].
converges with $Q$order iff one of the the following sequences converges with the same order: $\{\frac{{e}_{k+1}}{}$
or $\{{({e}_{k}}^{\alpha}$( $\alpha >0$arbitrary, given). 3.1.2 Rconvergence ordersIn 1972, Brent [32] stated, while in 1984, Potra and Pták [8] shown
In 1989 Potra [19] stated the equivalence , In fact we may extend Theorem 3.5 and the above relations. For brevity, we choose to write as a generic form for all type . The same will be , , , and .
(with the equivalence of ${R}_{\Lambda}$requiring ). Moreover,
Proof. (cf. [19]) We notice first that order implies order (and , . The converse ” $Q\Leftarrow R$” has convergence (i.e., (28) in (28), this attracts order . The equivalence of the ${R}_{\Lambda}$order to the , and therefore all orders,
We note that there exist sequences (see, e.g., (25)), for which , and which can therefore orders. Relation (37) – which is a completion of the one stated and proved by Potra [19] for the – can be obtained again from the well known inequalities for positive numbers
taking ${a}_{k}$, The following example shows that one may find sequences with order ) arbitrary arbitrary close to 1 from above.
we construct a which has convergence and Let $0<<1$be given, with $q>1$such Define
The sequence $\left\{{x}_{k}\right\}$has convergence On the even we obtain
so that In fact, one obtains ${q}_{l}$( $>\tau $, order). This example is also suitable for justifying the mentioned comments from In (37), any inequality may be strict. Now we see (e.g., Examples order) order). This also shows that the sequences with order and superlinear order superlinearly. The proof
Remark 3.12 We notice that the $R$order 3.2 Results relating the computational convergence ordersIn this section, the errors ${x}^{\ast}$are or by the nonlinear residuals $F({x}_{k}$, and $F\left({x}_{k}\right)\ne 0,$$\forall k\ge 0.$ We present full proofs only for the – and convergence 3.2.1 Corrections$C$ , orders As we have mentioned, Beyer, Ebanks and Qualls [20] shown that, for , the – resp. type
However, for proving $\left\{C,{C}^{\prime}\right\}$and ${Q}^{\prime}$the considered assumptions were very strong: was considered as a (see [20, Sect. 4]). We shall extend relation (38 ) and show some simplified proofs. For that, we
converges $Q$superlinearly if and only if the sequence $\{{s}_{k}$converges $Q$superlinearly Proof. Necessity. [8] Suppose $\{{x}_{k}$converges $Q$superlinearly. Then such that
It follows that for $k\ge {k}_{0}$,
from which we deduce the superlinear convergence Sufficiency. [8] If we suppose that the sequence converges superlinearly, then there such that
For any $k\ge {k}_{0}$we have: $$\begin{array}{}\end{array}$$
we infer that $\{{x}_{k}$converges $Q$superlinearly. For necessity, an alternative proof in the one dimensional case can The necessity was proved in the general case even before, by Dennis and
converges superlinearly
Proof. [5] The result follows immediately from the equality
_ The assumption of this Lemma also implies that converges superlinearly The converse of this result does not hold, as an example given by the same authors
, . Another proof of the PotraPták lemma was independently given by Walker Proof of PotraPták lemma. Necessity [47]: the DennisMoré Lemma. Sufficiency. [47] Suppose ${s}_{k}$, superlinearly.
For each $k$, . and ${s}_{k+i}$for .
and it follows that ${x}_{k}$$Q$ superlinearly. We are now able to present the main result of this type resp. type orders, but also that orders
Moreover, $$\begin{array}{}\end{array}$$
Proof. The proof will consist of two steps. At step A, we prove , type and type A1 ( $C\Rightarrow {C}^{\prime}$) Suppose converges order Then converges superlinearly,
which shows that $\left\{{x}_{k}\right\}$converges with ${C}^{\prime}$order A2 ( ${C}^{\prime}$) B1 ( $Q$$\Rightarrow $ ${Q}^{\prime}$ ) Suppose converges with type Then converges order and therefore superlinearly;
i.e., $\left\{{x}_{k}\right\}$converges order One converges order so by the results in Subsection 3.1 , it converges with any $Q$ type , Relation (42) and Proposition 3.3 attract (39), while (41) implies B2 ( ${Q}^{\prime}$type $Q$ type a) Relation (40) shows in particular that if $\{{x}_{k}$has an exact $Q$order , order, b) We note that the normindependence of the $Q$type type $R$ orders Potra and Pták [8] have obtained some fundamental results in this direction,
(with the equivalence of the ${R}_{\Lambda}$orders ). The proof relies on the result [8, Prop. 6.20]
which leads by analogy to relation . The following three results show that the asymptotic constants from the convergence order
and $\left\{{x}_{k+1}\right\}$have exact $R$orders order
has an exact $R$order has an exact $R$order
be three real numbers with $0<c<1<r<s$and set
It is easy to see that $r$is the exact $R$order and $\left\{{y}_{k+1}\right\},$while the sequences $\left\{{x}_{k+1}\right\}$and $\left\{{y}_{k}\right\}$have no exact $R$order
Remark 3.21 One can easily show that the sequence $\{{x}_{k}$converges with $R$order iff one of the the following sequences converges with the same order: $\{{e}_{k+1}$or $\{{({e}_{k}}^{\alpha}$( $\alpha >0$arbitrary, given). The same holds for $\{\frac{{e}_{k+1}}{}$
. 3.2.2 Nonlinear residuals$F({x}_{k}$– relationships We consider now the solving of a system of nonlinear equations for a nonlinear , having . – in different formulae – were used not only to control the convergence of a given to , but also to determine the (see, e.g., the well known works of Dembo, Eisenstat and Steihaug [7], We assume here that A) $F$is differentiable B) ${F}^{\prime}$continuous at ${x}^{\ast}$C) ${F}^{\prime}$is Replacing the errors by the corresponding residuals, we denote
and similarly, the resulted definitions for the – and all the type , orders The following example shows that neither of and implies the other.
,
and the (linear) mapping $F:({\mathbb{R}}^{2}$, . has $C$order , does not have $C$order b) Let ${y}_{k}$,
and similarly the mapping $G(u,v)=(u,v\u22154)$. has no $C$order, has $C$order (in the maxnorm). One can also view Example 2.3 in the sense that if one takes as the identity , the from order , while does not order. Before the result relating the orders, we recall (without proof) an
is differentiable on , the continuous , with the Jacobian nonsingular at ${x}^{\ast}$: . Let
. Then there such with $\parallel x{x}^{\ast}\parallel \le $,
We notice that $\alpha >1$.
s.t. $\forall x$with $\parallel x{x}^{\ast}$we have
We obtain the final result from this paper, which shows in fact the equivalence of type
$$\begin{array}{}\end{array}$$
Proof. Assume $\left\{{x}_{k}\right\}$converges type order Then, by Lemma 3.23 , we have
which shows that ${Q}_{L}^{\prime \prime}$and further type The implication $({Q}_{L}^{\prime \prime}$$\Rightarrow $ $({Q}_{L}$ follows in a similar manner. _ The ${Q}^{\prime \prime}$convergence orders. $R$orders We may complete Theorem 3.17 by the generic relation
the proof relying on the inequality from Lemma 3.23 . 3.3 Summary of the high (computational) convergence ordersWe present the following diagram in order to have a complete . As in [20], we use ” for the and , while the equivalence of type orders requires . 4 Linear convergenceThe $Q$linear In contrast to the high convergence orders , in However, it is worth noting that different relations (e.g., ${Q}_{1}^{\prime}$ ) is a monotone Zhang and Wang [62] completed the diagram with two implications. The first one, was proved , was proved and $\mathrm{liminf}{a}_{k}$,
, . The 5 ConclusionsAs the completion ${q}_{u}$for the order orders order . Ortega and and ${r}_{l}$to measure the speed of convergence of some ”entire” iterative processes bounds ${q}_{l}$for a single sequence (instead of the whole method) were obtained by us [14], [63] It is interesting to note that results on the upper order exist order The further consideration only of the lower order may remain order exists ), the use of the may offer approximations to ${p}_{0}$, ) (and too). Acknowledgments. The author is grateful to an anonymous referee for the References
inexact Newton method, SIAM J. Sci. Comput., 17 (1996) no. 1, pp.
order order
orders
