A survey on the high convergence orders and computational convergence orders of sequences

This is the first paper which surveys the rigorous definitions and relations of convergence orders (the Q-orders; the C-orders; the R-orders) of convergent sequences, and the computational variants.

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 Q-orders \(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 Q-orders 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

Convergent sequences in \(\mathbb{R}^n\); (Q)-convergence orders; (C)-convergence orders; (R)-convergence orders; convergence rates; rates of convergence; convergence speed; speed of convergence; computational convergence orders.

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) 1-20.
doi: 10.1016/j.amc.2018.08.006

PDF

About this paper

Print ISSN

0096-3003

Online ISSN

Google Scholar citations

Errata

The sequence \(z_k\) from Example 2.8 actually does not have Q-order \(2\):
\[
z_k = \begin{cases} 2^{-2^k/k}, & k \text{  odd}\\ 2^{-k2^k}, & k \text{  even.} \end{cases}
\]

Post version

November 7, 2021: errata added.

November 11, 2018: post created.

[1] W.A. Beyer, B.R. Ebanks, C.R. Qualls, Convergence rates and convergence-order profiles for sequences, Acta Appl. Math. 20 (1990) 267-284.
CrossRef (DOI)

[2] W.A. Beyer, P.R. Stein, Period doubling for trapezoid function iteration: metric theory, Adv. Appl. Math., 3 (1982), pp. 1-17.
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. 265-287.
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. 325-333
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. 327-344.
CrossRef (DOI)

[8] R.P. Brent, Algorithms for minimization without derivatives, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.

[9] R.P. Brent, S. Winograd, P. Wolfe, Optimal iterative processes for root-finding, Numer. Math., 20 (1973), pp. 327-341.
CrossREf (DOI)

[10] C. Brezinski, Comparaison des suites convergences, Revue Française d’Informatique et de Recherche Operationelle, 5 (1971) no. 2, pp. 95-99.
CrossREf (DOI)

[11] C. Brezinski, Accélération de la Convergence en Analyse Numérique, Springer-Verlag, Berlin, 1977.

[12] C. Brezinski, Limiting relationships and comparison theorems for sequences, Rend. Circolo Mat. Palermo, Ser. II, vol. 28 (1979), pp. 273-280.
CrossRef (DOI)

[13] C. Brezinski, Vitesse de convergence d’une suite, Rev. Roumaine Math. Pures Appl., 30 (1985), pp. 403-417.

[14] W. Burmeister, J.W. Schmidt, On the R-Order of Coupled Sequences II, Computing, 29 1982, pp. 73-81.
CrossRef (DOI)

[15] W. Burmeister, J.W. Schmidt, On the R-Order of Coupled Sequences III, Computing, 30 1983, pp. 157-169.
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. 543-570.
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. 3-8.
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. 473-485.
CrossRef (DOI)

[19] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301.
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 fifth-order quadrature formulas, Appl. Math. Comput. 190 (1) (2007), 686-698.
CrossRef (DOI)

[23] R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (2) (1982) 400-408.
CrossRef (DOI)

[24] J.E. Dennis, On Newton-like methods, Numer. Math. 11 (1968) 324-330.
CrossRef (DOI)

[25] J.E. Dennis Jr., J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comput. 28 (126) (1974) 549-560.
CrossRef (DOI)

[26] F. Dubeau, On comparisons of Chebyshev-Halley iteration functions based on their asymptotic constants, Int. J. Pure Appl. Math. 85 (5) (2013) 965-981.
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) 16-32.
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 ucrl-72238.

[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. Grau-Sánchez, M. Noguera, J.M. Gutiérrez, On some computational orders of convergence, Appl. Math. Lett. 23 (2010) 472-478.
CrossRef (DOI)

[33] M. Grau-Sánchez, M. Noguera, A. Grau, J.R. Herrero, On new computational local orders of convergence, Appl. Math. Lett. 25 (2012) 2023-2030.
CrossRef (DOI)

[34] M. Grau-Sá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) 52-64.
CrossRef (DOI)

[36] J. Herzberger, L. Metzner, On the q-orders 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) 229-237.
CrossREf (DOI)

[39] L.O. Jay, A note on q-order of convergence, BIT 41 (2) (2001) 422-429.
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 Gauss-Seidel 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). https://ictp.acad.ro/convergence-order-iterative-methods/ accessed March 22, 2018.
paper on author’s website

[44] I. Pavaloiu, Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32 (1–2) (1995) 69-82.
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, Cluj-Napoca, Romania, 1999, pp. 222-248. ISBN 973-98551-4-3. https://ictp.acad.ro/optimal-algorithms-concerning-solving-equations-interpolation/ accessed March 22, 2018.
paper on author’s website

[46] I. Pavaloiu, On the convergence of one step and multistep iterative methods, Unpublished manuscript, https://ictp.acad.ro/convergence- one- step- multistep- iterative- methods/, accessed April 1st, 2018.
paper on author’s website

[47] F.A. Potra, On Q-order and R-order of convergence, J. Optim. Theory Appl. 63 (3) (1989) 415-431.
CrossRef (DOI)

[48] F.A. Potra, V. Pták, Nondiscrete Induction and Iterative Processes, Pitman, Boston, Massachusetts, 1984.

[49] F.A. Potra, Q-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Program. Ser. A 91 (2001) 99-115
CrossRef DOI)

[50] F.A. Potra, Primal-dual affine scaling interior point methods for linear complementarity problems, SIAM J. Optim. 19 (1) (2008) 114-143.
CrossRef (DOI)

[51] M. Raydan, Exact order of convergence of the secant method, J. Optim. Theory Appl. 78 (3) (1993) 541-551.
CrossRef (DOI)

[52] W.C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, 2nd. ed., SIAM, Philadelphia, 1998

[53] J.W. Schmidt, On the r-order of coupled sequences, Computing 26 (1981) 333-342.
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) 1314-1334.
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) 3-55.
CrossRef (DOI)

[57] L. Tornheim, Convergence of multipoint iterative methods, J. ACM 11 (1964) 210-220.
CrossRef (DOI)

[58] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, 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) 222-243
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. 72-81
paper on author website

[63] D.D. Wall, The order of an iteration formula, Math. Comput. 10 (55) (1956) 167-168.
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 third-order convergence, Appl. Math. Lett. 13 (8) (20 0 0) 87-93.
CrossRef (DOI)

[66]  S.J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, 1997.

[67] Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley, 1997.

[68] T.J. Ypma, Historical development of the Newton-Raphson method, SIAM Rev. 37 (4) (1995) 531-551
CrossRef (DOI)

[69] R. Zhang, L. Wang, Two convergence problems for monotone sequences, Acta Appl. Math. 47 (1997) 213-220.
CrossRef (DOI)

A survey on the high convergence orders and
computational convergence orders of sequences

Emil Cătinaş

 

author address: Tiberiu Popoviciu Institute of Numerical Analysis, Romanian
Academy, P.O. Box 68-1, Cluj-Napoca, Romania. e-mail: ecatinas@ictp.acad.ro,
www.ictp.acad.ro/catinas

version submitted to Appl. Math. Comput., published with some changes in vol.
343 (2019) 1-20.

Abstract

Twenty years after the classical book of Ortega and Rheinboldt was
published, five definitions for the

Q-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

n</msup >;
Q-, C-, and R-convergence orders of sequences; computational convergence
orders.

MSC 2010. 65J05.

1 Introduction

Consider in the beginning a sequence

{xk</msub >}

from

, which converges
to a finite limit

x</msup >

.
Its speed of convergence is characterized by several measures, called convergence
orders, which are fundamental notions in Mathematical and in Numerical
Analysis.

The relation

lim k</munder > |x</msup >xk+1</msub >| |x</msup >xk</msub >|p</msup > = Cp</msub > (0,+)
(1)

gives the classical definition of the convergence with order

p > 1

, 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

Cp</msub >

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
norm-dependent problem. Moreover, as it requires the knowledge of both

p

and

x</msup >

,
relation (1 ) is only of theoretical use.

Still, such definition (along with the

Q

-superlinear convergence,
which requires

C1</msub > = 0

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 so-called
computational convergence orders, that iteratively approximate the convergence
orders using only the elements of the sequence known at the step

k

.
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

Q

– and

R

-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)

C

– and

Q

-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

x</msup >

), but even
the iterative method itself (as it was given in the well known book of J.F. Traub [23,
formula (8-14), p. 164]2 ).

In numerous works, the classical

Q


and

R

-orders
defined by Ortega and Rheiboldt lead to statements expressed as

{xk</msub >}

has

Q

-order (at
least)

p0</msub > > 1

and

R

-order
(at least)

p1</msub >

,

p1</msub > > p0</msub >

”. The

Q

-order
we study here is a completion to the classical one, and no
longer allows such conclusions. Instead, if having at all an order

p0</msub > > 1

,
the sequences will be only in one of the cases (the

C

-order
is obtained by taking norms in (1)):


  • {xk</msub >}has

    R-order

    p0</msub > > 1(but neither

    C
    nor

    Q-order);


  • {xk</msub >}has the same

    R
    and

    Q-order

    p0</msub > > 1(but no

    C-order);


  • {xk</msub >}has the same

    R-,

    Q
    and

    C-order

    p0</msub > > 1.

In less words, the relation reads for

p0</msub > > 1

as

C-order p0</msub > Q-order p0</msub > R-order p0</msub >,

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

Q

– and

R

-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
(

p > 1

), giving full
proofs for

C

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

R

-orders. We analyze next
the computational

C

– and

Q

-convergence orders
based on the corrections

xk+1</msub > xk</msub >

(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 Dennis-Moré lemma [5] allow us to complete the proofs). We also
consider computational convergence orders based on the nonlinear residuals

F(xk</msub >)

,
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 Q-type (computational) convergence orders.

2.1.1 Convergence orders based on the errors x*-xk

We turn now our attention to a sequence

{xk</msub >}

from

n</msup >

, which converges
to a finite limit

x</msup >

;
we prefer the common setting of a normed
space—

n</msup >

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

xk</msub >x</msup >,

k 0

.
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”)

ek</msub > = x</msup > xk</msub >.

As we have mentioned, the oldest definition of convergence with order

p0</msub > > 1

is
that

lim k</munder >Qp0</msub ></msub > (k) := lim k</munder > ek+1</msub >(ek</msub >)p0</msub ></msup > = Cp0</msub ></msub > (0,+),
(2)

which we call, as in [20],

C

-convergence with
order

p0</msub >

(the linear
convergence requires

p0</msub > = 1

and

0 < C1</msub > < 1

)

Q

comes from quotient. If it exists, it is uniquely defined and it implies that

> 0,k0</msub > 0

such
that

(Cp0</msub ></msub > )ekp0</msub ></msubsup > ek+1</msub > (Cp0</msub ></msub > + )ekp0</msub >
</msubsup >,k k0</msub >,
(3)

or, less sharp, the existence of

A,B > 0

such that

Aekp0</msub ></msubsup > ek+1</msub > Bekp0</msub >
</msubsup >,k 0.
(4)


Remark 2.1
a) For example, if

p0</msub > = 2and

C2</msub >is not too large, relation (3 ) says that the error is approximately squared at
each step

k,
for

ksufficiently large.

b) Some authors have used (4 ) to define the exact

Q-order
of convergence

p0</msub >(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

liminf and

limsup are finite and nonzero. Denoting

Q p0</msub ></msub > := liminf k</munder >Qp0</msub ></msub >(k),Q¯p0</msub ></msub > := limsup k</munder >Qp0</msub ></msub >(k), (5)

relation

0 < Q p0</msub ></msub > < Q¯p0</msub ></msub > < + (6)

implies (4 ):

0 < Q p0</msub ></msub >attracts the
first inequality in (4 ), while

Q¯p0</msub ></msub > < +the second one (see also [4, 9.3.3]).

d) As widely known, the larger the order

p0</msub >, the
faster the speed of convergence.

The

C

-order
is a norm-dependent notion, as the following two examples show for the

C

-orders

1

and

2

.


Example 2.2
[27] Let

x</msup > = (0,0) 2</msup >,
the sequence

xk</msub > = { (2k</msup >,0), keven,(0,2k+1</msup >),k odd. (7)

Consider the norms

(u,v)A</msub > = 2|u| + |v|,(u,v)B</msub > = |u| + 2|v|.

It follows

C1</msub > = 12for
the

A-norm, while

C1</msub >does not exist
for the

B-norm.


Example 2.3
Let

x</msup > = (0,0) 2</msup >and

xk</msub > = { (22k</msup ></msup >,0), kodd, (22k</msup >
</msup >,22k</msup >
</msup >),
k even.
(8)

One obtains

C2</msub > = 1when
considering the maximum norm

</msub >,
while

C2</msub >does not
exist for the norm

1</msub >.

The following definition for the convergence order seems to be the
second oldest one (we adopt the notation from [20]). The sequence

{xk</msub >}

has

QL</msub >

-convergence
order

p0</msub > 1

if:

QL</msub > (k) := ln ek+1</msub > ln ek</msub > p0</msub >,as k .
(9)


Remark 2.4
a) As noticed by Brezinski in [28] and [26],

QL</msub >is a particular case of a definition used by Bourbaki [29] in order to compare
the convergence orders of two sequences.

The measure

QL</msub >was then independently considered by Wall in 1956 [30] (see also [31], [4,
ch. 9], [32, ch. 2] and [25]), argued – for

lg instead of

ln – as the limit of the quotient of two consecutive numbers of correct decimal
places in

xk+1</msub >resp.

xk</msub >(see also [8, p. 90]); in this sense, convergence for example with

QL</msub >-order

2means intuitively that, from a certain step, the number of correct digits are
doubled the successive elements of

{xk</msub >}.
The logarithm base may be taken as any positive real number

a1;
we shall consider further the natural base

e for simplicity.

b) In contrast to

Qp0</msub ></msub >(k),
the expression

QL</msub >(k)does not require the (usually unknown) value

p0</msub >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

Q L</msub > := liminf k</msub >QL</msub >(k),
a quantity which we analyze in Proposition 3.3 ).

c) Brent, Winograd and Wolfe noticed in [37] that

C-order

p0</msub >immediately implies

QL</msub >-order,
of same value.

d) We shall see later, in Remark 3.8 , that this notion (cf. [38]), as well as
the other

Q-orders,
is norm-independent (also noted by Potra [19]).

In 1967, Feldstein and Firestone [39] introduced essentially
the following convergence order, which we denote here by

Q</msub >

.

The sequence

{xk</msub >}

has

Q</msub >

-convergence
order

p0</msub >

if:

lim k</munder >Qp0</msub ></msub > (k) = 0, > 0 with p0</msub > 1, (10)
lim k</munder >Qp0</msub >+</msub > (k) = , > 0.

Condition

p0</msub > 1

will be a standing assumption from here on, in all subsequent
formulas, while in Section 3 we will implicitely assume that

p0</msub > > 1

.

The convergence with

Q</msub >

-convergence
order

p0</msub > > 1

can be expressed in a more intuitive form (see also [20]):

lim k</munder >Qp</msub >(k) = 0,1 < p < p0</msub >,
lim k</munder >Qp</msub >(k) = + ,p > p0</msub >.

Two years later, the same authors [40] expressed the above order
in an equivalent form, which in fact will be the same as the

Q

-order
defined below. Let

λ</msub > = sup {p : lim k</munder >Qp</msub >(k) = 0 }, (11)
λ</msup > = inf {p : lim
k
</munder >Qp</msub >(k) = }.

They noticed that

0 λ</msub > λ</msup >

, and
when

p0</msub > = λ</msub > = λ</msup >

, the sequence was
said to have the order

p0</msub >

.

In their classical book from 1970, Ortega and Rheinboldt [4,
Ch. 9] introduced and studied the quantity denoted in (5) by

Q¯p</msub >,

for
all

p 1

:

Q¯p</msub > = limsup k</munder >Qp</msub > (k).

They shown the following behavior for

Q¯p</msub >

as a
”function” of

p

.


Proposition 2.5
[4, 9.1.2] Exactly one of the following conditions holds:

a)

Q¯p</msub > = 0,p [1,+);b)

Q¯p</msub > = +,p [1,+);c)

p0</msub > [1,+)s.t.  

Q¯p</msub > = 0, p [1,p0</msub >)and

Q¯p</msub > = +, p (p0</msub >,+).

The quantity

ql</msub > = { ,   if  Q¯p</msub > = 0,p 1 inf {p [1,) : Q¯p</msub > = + } (12)

(called in [4] as

Q

-convergence
with order at least

ql</msub >

and denoted by O

Q</msub >{xk</msub >}

)
stood there and in many subsequent works for a measure of
the convergence order. We call it, as in [20], the lower

Q

-order, and
denote it by

ql</msub >

(instead of

pl</msub >

used there). We shall see that the lower

Q

-order needs to be completed
by the upper

Q

-order for
obtaining the ”full”

Q

-order;
as a matter of fact,

ql</msub > = λ</msub >

,
the lower order from (11) defined in [40].


Remark 2.6
The sequence

{xk</msub >}was said in [4, Def. 9.1.4] that converges faster than

{yk</msub >}if for
some

p0</msub > 1,we
have

Q¯p0</msub ></msub >{xk</msub >} < Q¯p0</msub ></msub >{yk</msub >}(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 < Cp0</msub ></msub >{xk</msub >} < Cp0</msub ></msub >{yk</msub >} < +,

numerical evidence reveals that

{xk</msub >}does not necessarily converge faster than

{yk</msub >},
as shown by Ypma and Igarashi [41].

On the other hand, as noticed by Brezinski [26], the sequences given by

xk</msub > = 1kand

yk</msub > = 1k2</msup >,

k 0,
have the same asymptotical constant,

Q1</msub >{xk</msub >} = Q1</msub >{yk</msub >},
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

Q

-convergence
order in the following way, which will be used throughout the paper. Let the lower

Q

-order

ql</msub >

be
given in (12 ), recall the notation from (5)

Q p</msub > = liminf k</munder >Qp</msub > (k)

and define the upper

Q

-order

qu</msub >

by

qu</msub > = sup {p [1,+) : Q p</msub > = 0 }.

Then the

Q

-convergence
is with order 

p0</msub >

if

p0</msub > = ql</msub > = qu</msub >.

This definition is equivalent to the one given by Feldstein and Firestone in (11),
as

ql</msub > = λ</msub >

and

qu</msub > = λ</msup >

.

In 1981, Schmidt [42] introduced the following type of convergence order, denoted here,
as in [20], by

QΛ</msub >

:

{xk</msub >}

has

QΛ</msub >

-convergence
order

p0</msub >

if

QΛ</msub > (k) = ln ek+2</msub >ek+1</msub >
ln ek+1</msub >
ek</msub >
p0</msub >,   as  k .
(13)

The author gave no result relating the

Q

– and

QΛ</msub >

-orders he introduced,
and assumed that

QΛ</msub >

is
equivalent to an

R

-order
(while it is in fact a

Q

-order,
as we shall see).

In 1982, Beyer and Stein [43] independently introduced
the measure (19 ) below, which is somehow similar to

QΛ</msub >

, and in fact
equivalent to

QΛ</msubsup >

defined in subsubsection 2.1.2 .

In 1985, unaware of [42] and [43], Brezinski [26] considered the

QΛ</msub >

-convergence order

and, assuming that

{xk</msub >}

has the exact

Q

-order of
convergence

p0</msub > > 1

(as defined
by (4 )), he proved that

{xk</msub >}

has the

QΛ</msub >

-order

p0</msub >

(and

QL</msub >

-order

p0</msub >

as
well).

In 1989, Potra introduced in [19] the following type of convergence order (denoted
here by

QI,</msub >

,
with ”

I


from ”inequality”), which will be useful in obtaining some simplified
proofs.

The sequence

{xk</msub >}

has

QI,</msub >

-convergence
order

p0</msub >

if

> 0,

a,b > 0

such
that

aekp0</msub >+</msubsup > ek+1</msub > bekp0</msub ></msubsup >,k 0.
(14)

This can be regarded as a generalization of inequalities (4 ).

Potra shown some fundamental results in our study, that

QI,</msub >

-convergence
with order

p0</msub > > 1

is
equivalent to

Q</msub >

– and
to

QL</msub >

-convergence
of same order, which we denote here, as in [20], by symbols between curled
braces:

{Q</msub >,QI,</msub >,QL</msub >} .

Ortega and Rheinboldt [4, N.R. 9.2.2] have previously noticed a weaker property of

QL</msub >

-convergence with order

p0</msub >

, namely that it implies
(partial)

R

-convergence
with order

p0</msub >

(i.e., in the
notations below, that

p0</msub > = rl</msub >

).

In the same paper, Potra has also considered the lower and upper

Q

-orders, when noting that if
a sequence has exact

Q

-order

p0</msub >

then

ql</msub > = qu</msub > = p0</msub >

.

In 1990, Beyer, Ebanks and Qualls [20], unaware of the definitions
and the results mentioned above, introduced the definitions of the

Q

– and

QΛ</msub >

-orders
and shown some other fundamental results, that convergence with

Q

-order

p0</msub > > 1

is equivalent
to

QΛ</msub >

and to

QL</msub >

-convergence
with same order:

{Q,QL</msub >,QΛ</msub >} .

They considered

QΛ</msub >

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

ql</msub > qu</msub >

(which justifies
the terminology lower/upper); when this inequality is strict, the sequence does not have
a

Q

-order,
as shown below.


Example 2.7
Let

xk</msub > = { 22k</msup ></msup >,keven,
32k</msup >
</msup >,
kodd.

We get

Q¯p</msub > = { 0, 1 p < log 3</msub >4,
1, p = log 3</msub >4,
+,p > log 3</msub >4,
and  Q p</msub > = { 0, 1 p < 4log 4</msub >3,
1, p = 4log 4</msub >3,
+,p > 4log 4</msub >3.

The graphical illustration of

Q¯p</msub >and

Q p</msub >for

p 1leads to the so called convergence profile of the sequence, as termed in [20]
(see Fig. 1 ).

pict
Figure 1: Q 

convergence-order profile for

{xk</msub >}defined in Example 2.7 . This is a graph of the limit points of

 

Qp</msub >(k)as a function of

 

p.
The vertical scale is not to scale.

This sequence does not have a

Q-order, as

ql</msub > = log 3</msub >4 1.26 < qu</msub > = 4log 4</msub >3 3.17, but it converges
with (exact)

R-order

2,
as defined later. We note the classical statement in this case,

{xk</msub >}converges
with

Q-order
(at least)

log 3</msub >4 1.26and
with

R-order
(at least)

2”,
which no longer holds in the setting of this paper.

An elementary example shows that in case of convergence with

Q

-order

p0</msub >,

apart
of finite nonzero values of one (or both) of the asymptotical constants

Q

p0</msub ></msub > Q¯p0</msub ></msub >

, any
of the following relations may hold:

Q p0</msub ></msub > = Q¯p0</msub ></msub > = +, (15)
Q p0</msub ></msub > = Q¯p0</msub ></msub > = 0, (16)
Q p0</msub ></msub > = 0 andQ¯p0</msub ></msub > = +. (17)


Example 2.8
Let

xk</msub > = 22k</msup >k</msup >,y
k
</msub > = 2k2k</msup >
</msup >,zk</msub > = { xk</msub >,kodd,
yk</msub >,k even.

It is easy to verify that for

p0</msub > = 2,the sequences

{xk</msub >} , {yk</msub >} , {zk</msub >}verify respectively (15), (16) and (17) (

{xk</msub >}was also considered in [20]).

Schwetlick [25, Ü.4.2.3, p. 93] also considered an example of the type

xk</msub > = ek</msub >|ln ek</msub >|,

yk</msub > = ek</msub >|ln ek</msub >|,
for the errors

ek</msub >converging with exact

Q-order

2.

Potra [19] considered

ek</msub > = { ek+1</msub > = 2ek</msub >ek12</msubsup >,keven,
ek+1</msub > = ek</msub >ek12</msubsup >, k odd,

which has

Q-order

2and

Q¯2</msub > = +.

Jay [27] considered the sequence of the type

xk</msub > = k22k</msup ></msup >,

keven,

xk</msub > = 22k</msup ></msup >k,

kodd, which satisfies (17) for

p0</msub > = 2.

One may easily find examples when

Q p0</msub ></msub > = 0and

Q¯p0</msub ></msub >is finite, nonzero, or, on the other hand, when

Q p0</msub ></msub >is finite, nonzero and

Q¯p0</msub ></msub > = +.
Jay [27] considered the sequence

xk</msub > = xk1q</msubsup >k,

kodd,

xk</msub > = xk1q</msubsup >,

keven, for

q 1,

x0</msub > = 1,
for which one obtains

Q q</msub > = 0and

Q¯q</msub > = 1.

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]:

xk+1</msub > = (xk</msub >)p1k </msup >,

k 1,

x1</msub > = ,

0 < < 1and also

x2k</msub > = (rs)k</msup ></msup >,

x2k+1</msub > = rk</msup >sk+1</msup ></msup >,

0 < < 1 < r < s.


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

p0</msub > = 2and

Q 2</msub > = Q¯2</msub > = +.

 

Remark 2.10 When

Q¯1</msub > = 0,i.e.,

lim k</munder >ek+1</msub >ek</msub > = 0,

it is said that the sequence converges (at least)

Q-superlinearly.
The convergence is strict

Q-superlinearly,
when

ql</msub > = 1(i.e.,

Q¯p</msub > = +,

p > 1);
there are three cases in this situation:

ql</msub > = qu</msub > = 1,
i.e.,

Q-order

1(see Example 3.6 ),

1 = ql</msub > < qu</msub > < +,
resp.

1 = ql</msub >,

qu</msub > = +(see Example 2.14 b), formula (24)).

It is worth noting that one may also obtain

ql</msub > = 1,

qu</msub > = +in lack of

Q-superlinear
(and even linear) convergence, shown in Example 2.14 d), formula (25)), as

Q¯1</msub > = +.


Remark 2.11
Returning to the comments from Remark 2.6 ,
we note that the comparison of the convergence of two sequences

{xk</msub >},

{yk</msub >}having
errors

{ek</msubsup >}resp.

{ek</msubsup >}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

{xk</msub >}converges
faster than

{yk</msub >}if (see, e.g., [18]):

lim k</munder >ek</msubsup >ek</msubsup > = 0(also denoted by ek</msubsup > = o(e
k
</msubsup >), as  k ).
(18)

Now we see that this definition makes sense not only if the

Q-orders
of the two sequences are different, but even if they are equal, as the above
condition is norm-independent.

To show this, we consider the terminology proposed by Jay [27] for a sequence converging
with

Q-order

p0</msub > > 1, who
defined that the convergence is with:


  • Q-suborder

    p0</msub >if

    Q¯p0</msub ></msub > = ,


  • Q-superorder

    p0</msub >if

    Q¯p0</msub ></msub > = 0.

The last terminology is in fact widely used – recall the superquadratic convergence
(for

Q¯2</msub > = 0),
supercubic, etc.).

Now we see that for sequences with

Q-order

p0</msub > > 1we
can briefly say that:


  • Q-superconvergence
    is faster than exact

    Q-convergence
    (in the sense of (4) or (6));

  • exact
    Q-convergence
    is faster than

    Q-subconvergence;

  • (consequently)
    Q-superconvergence
    is faster than

    Q-subconvergence.

This can be illustrated by the following sequences having

Q-order

2:

{2k2k</msup ></msup >}(

Q-superquadratic),

{22k</msup ></msup >}(exact

Q-order

2),

{22k</msup >k</msup >}(

Q-subquadratic).

2.1.2 Computational convergence orders, based on the corrections xk+1-xk
and the nonlinear residuals F(xk)

We consider now some quantities which do not require the limit

x</msup >

,
for which we adopt the terminology computational convergence
orders
. As some of them require the knowledge of the order

p0</msub >

itself,
we keep in mind that perhaps a more proper terminology for those would be
semi-computational.

As a notation, for the corresponding convergence orders
based on corrections we shall add a prime mark (e.g.,

C</msup >

) as in
[20], while for those based on nonlinear residuals, two prime marks (e.g.,

C</msup >

).

Corrections.

We introduce another notation, for the corrections (including their norms
too):

sk</msub > = xk+1</msub > xk</msub >.

In 1974 Dennis and Moré [5] obtained a result which shows that if a sequence converges

Q

-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

Q

-superlinearly iff the corrections
converge

Q

-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

log sk</msub > sk+1</msub > log sk−1</msub > sk</msub > , (19)

equivalent to

QΛ</msubsup >

defined below.

Three years later, Brezinski [26] proposed the use of the corrections

xk+1</msub > xk</msub >

instead of the
(unknown) errors

x</msup > xk</msub >

in the definitions of the convergence orders studied there
(

QL</msub >,QΛ</msub >

and exact

Q

-order).

In 1990, Beyer, Ebanks and Qualls [20], taking the same approach, considered

Qp0</msub ></msubsup > (k) := sk+1</msub >skp0</msub ></msubsup >

with the resulted definitions being denoted correspondingly by

C</msup >,Q</msup >,QL</msubsup >

and

QΛ</msubsup >

; we use here the same
convention for denoting

Q</msubsup >,QI,</msubsup >

.
These authors proved the following fundamental results: for

p0</msub > > 1

, 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:

{Cp0</msub ></msub >,Cp0</msub ></msubsup >} {Q,QL</msub >,QΛ</msub >,Q</msup >,Q
L
</msubsup >,Q
Λ
</msubsup >
}.

However, the considered assumptions were very strong when proving

{Cp0</msub ></msub >,Cp0</msub ></msubsup >}

and

Q</msup > Q

”:

{xk</msub >}

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, Grau-Sánchez, Noguera and Gutiérrez [48], while studying connections
between

QΛ</msub >

– and

QΛ</msubsup >

-orders (in the case
of a sequence from

with

C

-order

p

)
considered the ”extrapolated convergence order”

ln |xk+1</msub >−α~k+1</msub >| |xk</msub >−α~k</msub >| ln |xk</msub >−α~k</msub >| |xk−1</msub >−α~k−1</msub >|, (20)

where

α~k</msub > = xk</msub > (Δxk1</msub >)2</msup >

Δ2</msup >xk2</msub > ,

k 2,

Δxk</msub > = xk+1</msub > xk</msub >

. This convergence order
was obtained from

QΛ</msub >

by replacing the unknown limit with an extrapolation

α~k</msub >

given by
the Aitken

Δ2</msup >

method (in order to use only the terms known at the step

k

).
However, this convergence order is valid only in the one dimensional case, since the
Aitken

Δ2</msup >

acceleration process does not have a direct extension to

n</msup >

.

We do not pursue this definition as, for high convergence orders, it is equivalent
to

QΛ</msubsup >

.

In 2012, Grau-Sánchez, Noguera, Grau and Herrero [49] considered another
extrapolated convergence order

ln |xk</msub >−α~k</msub >| ln |xk−1</msub >−α~k−1</msub >|, (21)

for a sequence from

,
having

C

-order

p

. Assuming

C

-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

{ek</msub >}

,

{sk</msub >}

and

{f(xk</msub >)}

for
sequences

{xk</msub >}

from

.
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

C</msup >-,

Q</msubsup >-,

QI,</msubsup >-orders
are semi-computational orders, as they require the (supposed) unknown order,
while the logarithm-based

QL</msubsup >
and

QΛ</msubsup >-orders
are (fully) computational orders, i.e., they require neither the limit

x</msup >nor the order

pin their expressions.

As certain numerical experiments (see [50] and the references therein)
have not revealed a clear superiority of

QΛ</msubsup >over

QL</msubsup >,
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

ql</msub > = ql</msubsup > = Q L</msub >and

qu</msub > = qu</msubsup > = Q¯L</msub >.

Nonlinear residuals.

Other computational convergence orders were considered
in the context of solving nonlinear systems of equations

F(x) = 0

,

F : n</msup > n</msup >

, with solution

x</msup >

. For simplicity,
we shall denote

Fk</msub > := F(xk</msub >)

(resp.

fk</msub >

when

n = 1

).

In 1981, Păvăloiu [51] defined the exact convergence order

p0</msub > > 1

corresponding to (4) by

AFk</msub >p0</msub ></msup > Fk+1</msub > BFk</msub >p0</msub >
</msup >,k 0,

while in 1995, he introduced in [52] the expression

ln|fk+1</msub >| ln|fk</msub >| (22)

and shown its equivalence to

QL</msubsup >

.
Also, while extending his results from 1999 [53], he introduced in an unpublished
manuscript [54] (posted on his website) the measure

ln|fk+1</msub >∕fk</msub >| ln|fk</msub >∕fk−1</msub >| (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 R-convergence orders.

The root convergence order (

R

-order)
requires weaker conditions than the

C


and

Q

-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

Q

– and

R

-convergence is […]
essentially sacred to workers in the area of computational optimization” [13, p. 49], meaning
that the

R

-order
is a much less powerful notion.

In Example 3.11 is presented a sequence for which, depending on the parameters, the
lower

Q

-order

ql</msub >

is arbitrary close to

1

from above, while
the (exact)

R

-order
is arbitrary high (and even higher is the upper

Q

-order

qu</msub >

).

We shall review certain results, but not treat all of them in the same detail as we
will for the

C


and

Q

-orders.

In 1970, Ortega and Rheinboldt [4, 9.2] introduced and
studied the root convergence factors, which we denote here by

R¯p</msub > {xk</msub >}

:

R¯p</msub > {xk</msub >} = { limsup k</munder >(ek</msub >)1
k
</msup >, ifp = 1,

limsup k</munder >(ek</msub >) 1
pk</msup >
</msup >, ifp > 1.

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

1

takes
the role of

+

for

Q¯p</msub >

.


Proposition 2.13
[4, 9.2.3] Exactly one of the following conditions holds:

a)

R¯p</msub > = 0,p [1,+);b)

R¯p</msub > = 1,p [1,+);c)

p0</msub > [1,+)s.t.  

R¯p</msub > = 0, p [1,p0</msub >)and

R¯p</msub > = 1, p (p0</msub >,+).

The lower

R

-order,
which we denote here by

rl</msub >

(instead of

OR</msub > {xk</msub >}

in [4, 9.2]), defined by

rl</msub > = { ,   if  R¯p</msub > = 0,p 1,
inf {p [1,) : R¯p</msub > = 1 },

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

p0</msub >with

R¯p0</msub ></msub > < 1,then for
any

> 0with

R¯p0</msub ></msub > + < 1,there
exists a

k0</msub > 0such that either

ek</msub > (R¯p0</msub ></msub > + )k</msup >,k k0</msub >, ifp0</msub > = 1,

or

ek</msub > (R¯p0</msub ></msub > + )p0k</msubsup ></msup >,k k0</msub >, ifp0</msub > > 1.

b) The value

rl</msub >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]):

ek+1</msub > Aek</msub > ek1</msub >

and they yield the well-known

rl</msub >-order

(1 + 5)2 1.6.
It is important to note that the secant method then attains the same value
also for the lower

Q-order

ql</msub >(see [3], [9]).

For the more general inequalities

ek+1</msub > Ai=0m</munderover >(eki</msub >)αi</msub ></msup >,k m,ck</msub >,αk</msub > 0,

Schmidt [42], Burmeister and Schmidt [55], [56] resp. Potra and Pták
[8, p. 107] determined in a series of works the lower

R-order

rl</msub >.

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

ql</msub >. Potra
[19] has also noted that the above inequalities do not necessarily attract lower

order

ql</msub >greater than one: take

ek+1</msub > = { (ek</msub >)k</msup >, k > 1is a power of 2,ek</msub >ek1</msub >,otherwise, (24)

with

e0</msub > = e1</msub > = 12. This sequence
satisfies

ek+1</msub > ek</msub >ek1</msub >(which
immediately attracts

Q¯1</msub > = 0and

rl</msub > (1 + 5)2), but
in fact

Q¯p</msub > = +,

p > 1(and

qu</msub > = Q¯L</msub > = +, as
we shall see).

Certain iterative methods have lead to some different inequalities, of the type
[4, Th. 9.2.9.]

ek+1</msub > ek</msub >j=0m</munderover >γ
j
</msub >ekj</msub >,k m, with γ1</msub >,...,γm</msub > 0,

or of other types, analyzed in [23] (see also [58]).

c) As noted in [4, N.R. 9.2.1], the

R¯1</msub >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

R-order

rl</msub >is consistent with the natural ordering of sequences, while the lower

Q-order

ql</msub >is not:
given

{xk</msub >},{yk</msub >}with
errors

{ek</msubsup >},
resp.

{ek</msubsup >}, if

ek</msubsup > ek</msubsup >and

{yk</msub >}has

rl</msub >order

p0</msub >then so
has

{xk</msub >};
however, this statement does not hold for the lower

Q-order

ql</msub >, as one may take

{xk</msub >}from Example
2.7 and

yk</msub > = 22k</msup ></msup >.
A more disturbing example was given by Jay [27], for

yk</msub > = 22k</msup ></msup >and

xk</msub > = { 22k</msup ></msup >,keven,23k</msup >
</msup >,
kodd.
(25)

At the first sight, since

ek</msubsup > ek</msubsup >,
the speed of

{xk</msub >}seems higher
than of the (exact)

Q-quadratic

{yk</msub >}, but though,

{xk</msub >}does not attain even

Q-linear convergence, as

Q¯1</msub > = (we shall see that in this
case the upper

Q-order
is

qu</msub > = Q¯Λ</msub > = ).
Another example was given in (24) above.

In 1973, Brent, Winograd and Wolfe [37] considered the following expressions,
which we denote here by

R L</msub > := liminf k</munder > |ln ek</msub > |1
k
</msup >,
(26)
R¯L</msub > := limsup k</munder > |ln ek</msub > |1
k
</msup >

(in [32] Brent considered in the same year only

R L</msub >

). The sequence was said
that converges with

RL</msub >

-order

p0</msub > > 1

if

R L</msub > = R¯L</msub > = p0</msub >

, i.e.,
in a single condition,

lim k</munder > |ln ek</msub > |</msup >1k =p˙0. (27)

They noted that the

C-order

p0</msub > > 1easily implies

RL</msub >-order

p0</msub >.

In 1979, Schwetlick [25] considered the upper

R-order

R p</msub > {xk</msub >} = { liminf k</munder >(ek</msub >)1
k
</msup >,
 ifp = 1,
liminf k</munder >(ek</msub >) 1
pk</msup >
</msup >,
 ifp > 1,

and (in the notations of this paper)

ru</msub > = { ,   if   R p</msub > = 0,p 1,
sup {p [1,) : R p</msub > = 0 },

he defined the convergence with

R-order

p0</msub >if

p0</msub > = rl</msub > = ru</msub >.Similarly to the case of the

Q-order,
the sequence is said that converges

R-superlinearly
if

lim k</munder >(ek</msub >)1k </msup > = R¯1</msub > = 0.


Remark 2.15
Analogously to Remark 2.14 , whenever exists a

p0</msub >with

R p0</msub ></msub > > 0,then for
any

> 0with

0 < R p0</msub ></msub > ,there
is a

k0</msub > 0such that either

( R p0</msub ></msub > )k</msup > e
k
</msub >,k k0</msub >, ifp0</msub > = 1,

or

( R p0</msub ></msub > )p0k</msubsup >
</msup > ek</msub >,k k0</msub >, ifp0</msub > > 1.

In 1989, Potra [19] has introduced and studied some further measures for the

R-convergence order,
which we denote here by

R</msub >,
resp.

RI,</msub >:


  • {xk</msub >}converges
    with

    R</msub >-order

    p0</msub > > 1if

    lim k</munder >(ek</msub >) 1
    (p0</msub >)k</msup >
    </msup >
    = 0, > 0,
    lim k</munder >(ek</msub >) 1
    (p0</msub >+)k</msup >
    </msup >
    = 1, > 0;


  • {xk</msub >}converges
    with

    RI,</msub >-order

    p0</msub > > 1if

    > 0,

    a,b > 0and

    0 < η, < 1such that

    aη (p0</msub >+)k</msup ></msup > ek</msub > b (p0</msub >)k</msup >
    </msup >,k 0.

The exact

R-order
of convergence was also defined here – analogously to the definition of the exact

Q-order (4)
– as being

p0</msub > > 1if

A,B > 0,

0 < η, < 1such
that

A η(p0</msub >)k</msup ></msup > ek</msub > B (p0</msub >)k</msup >
</msup >,k 0;
(28)

we see that this definition can be immediately connected to the following one,
analogous to (6):

0 < R p0</msub ></msub > < R¯p0</msub ></msub > < . (29)

Potra has also considered the lower and upper

R-orders, when noting that if
a sequence has exact

R-order

p0</msub >then

rl</msub > = ru</msub > = p0</msub >.

Comparing the list of

Q
and

R-orders, the
definition of

RΛ</msub >was not given before, so we consider it here, by denoting the expressions

R Λ</msub > := liminf k</munder > |ln ek+1</msub >
ek</msub >
|1
k
</msup >,R¯Λ</msub > := limsup k</munder > |ln ek+1</msub >
ek</msub >
|1
k
</msup >

and by defining the

RΛ</msub >-order

p0</msub > 1when

R Λ</msub > = R¯Λ</msub > = p0</msub >, i.e.,
when

lim k</munder > |ln ek+1</msub >ek</msub > |1
k
</msup > = p0</msub >.
(30)

3 Results relating the high (computational) convergence orders

In this section we consider

p > 1and present the relationships of different definitions of the
(computational) convergence orders, with full proofs in the case of the

C– and

Q-orders.

3.1 Relationships between the convergence orders

The equivalences and implications mentioned in the previous section can be
summarized as:

{Q</msub >,QI,</msub >,QL</msub >} {R</msub >,RI,</msub >,RL</msub >} , [19],
Cp0</msub ></msub > {Q,QL</msub >,QΛ</msub >} , [20].
At this point we can simply merge the equivalences from the two statements
above and write the conclusion.

However, as we intend to provide a self-contained
material, we include the proofs of the equivalence of the

Q-orders,
some of them much simplified.

3.1.1 C- and Q-convergence orders

We shall need the three auxiliary results below.


Lemma 3.1
[20, lemma 2.1]

(i)
If

Q¯p</msub > < ,then

Qs</msub > (k) 0for all

s < p,
and so

p ql</msub >;

(ii)
if

Q p</msub > > 0,then

Qs</msub > (k) for all

p < sand so

qu</msub > p;

(iii)
if

p < ql</msub >,then

Qp</msub > (k) 0;

(iv)
if

qu</msub > < p,then

Qp</msub > (k) .

Relations (iii) and (iv) show that

ql</msub > qu</msub >and justify the terminology ”lower” and ”upper”.

Proof. [20] For (i), if

Q¯p</msub > < and

s < p,then

Qs</msub >(k) = ek+1</msub >eks</msubsup > = ekps</msubsup >Q
p
</msub >(k) 0,as k .

For (iii), suppose

p < ql</msub >and choose

s (p,ql</msub >) .By
definition of

ql</msub >,then,

Q¯s</msub > < . Now,
by (i),

Qp</msub > (k) 0.The other statements are proved in a similar manner.  _


Remark 3.2
Ortega and Rheinboldt have previously obtained (i) and (ii)
in [4, 9.1], see Proposition 2.5 .

Potra obtained the following general result, interesting in its own, which will
help us relating some quantities to their corresponding computational
versions.


Proposition 3.3
[19, Prop. 1.1] The following relations hold:

Q L</msub > := liminf k</munder >ln ek+1</msub > ln ek</msub > = ql</msub >
(31)

and

Q¯L</msub > := limsup k</munder >ln ek+1</msub >
ln ek</msub >
= qu</msub >.

Proof. [19] Let

1 < Q L</msub > = p0</msub >.

Then for any

> 0with

p0</msub > > 1, there
exists

k0</msub >such that

ln ek+1</msub >
ln ek</msub > > p0</msub > ,k k0</msub >.

We may assume that

ln ek</msub > < 0,
and we obtain

ln ek+1</msub > < (p0</msub > )ln ek</msub >,k k0</msub >,

so that

ek+1</msub > < ekp0</msub ></msubsup >,k k0</msub >.

This proves that

Q¯p0</msub ></msub > 1 < and, by Lemma 3.1 (i), we get

p0</msub > ql</msub >.

Suppose that

p0</msub > < s < ql</msub >.

It follows by Lemma 3.1 (iii) that

Qs</msub > (k) 0,so there
is

c > 0such
that

Qs</msub > (k) c, k 0,i.e.,

ek+1</msub > ceks</msubsup >,k 0.

But then

ln ek+1</msub > ln c + sln ek</msub >,

which leads to

liminf k</munder >ln ek+1</msub >ln ek</msub > s + lim k</munder > ln c
ln ek</msub >
= s > p0</msub >,

which is a contradiction. Hence, we have proved that

Q L</msub > = ql</msub >.Analogously,

Q¯L</msub > = p1</msub >implies

p1</msub > = qu</msub >. _


Lemma 3.4
[20, lemma 3.3] If

lim inf QΛ</msub > (k) > 0,

then

{ek</msub >}is monotone decreasing starting from a step

k k0</msub >.

Proof. [20] For some some

> 0sufficiently small,

k0</msub > 0such that

QΛ</msub >(k) > , k k0</msub >.Hence, the
numbers

ln ek+1</msub >ek</msub >all have
the same sign

k k0</msub >.
If they were positive, then we would have

ek+1</msub > > ek</msub >, contradictory to the
convergence of

{xk</msub >}.Therefore,
they are all negative and

ek+1</msub > < ek</msub >. _

We present now the result relating the

C– and

Q-orders,
and we choose to incorporate Proposition 3.3 .


Theorem 3.5
(cf. [19], [20]) Consider a given norm

in

n</msup >and a convergent
sequence

{xk</msub >}to
some

x</msup > n</msup >. Then,
given some

p0</msub > > 1,
in the above notations we have:

Cp0</msub ></msub > {Q,Q</msub >,QI,</msub >,QL</msub >,QΛ</msub >} . (32)

Moreover,

Q L</msub > = ql</msub >and Q¯L</msub > = qu</msub >. (33)

Proof. We give the proof in five steps: A.

Cp0</msub ></msub > QL</msub >, B.

Q Q</msub >, C.

Q</msub > QI,</msub >, D.

Q QL</msub >and
E.

QΛ</msub > QL</msub >A1 (

Cp0</msub ></msub > QL</msub >).
The simplest approach is (also mentioned in [37]) to take logarithms in (2). The
proof in [20] used an approach similar to Lemma 3.1 .

A2 (

QL</msub > Cp0</msub ></msub >)
[20] Consider any of the sequences from Example 2.8 .

B. The relation is obvious.

C1 (

Q</msub > QI,</msub >)
Let

> 0such
that

p0</msub > > 1.Since

Qp</msub > 0, it follows
that exists

bsuch that

Qp0</msub ></msub > b, k 0,i.e., the second inequality
in the definition of

QI,</msub >.The first inequality is obtained in the same way.

C2 (

QI,</msub > Q</msub >) Suppose
for some

p0</msub > > 1and

> 0with

p0</msub > > 1we have

a(ek</msub >)p0</msub >+</msup > ek+1</msub > b(ek</msub >)p0</msub ></msup >,k 0.

The second inequality implies

Q¯p0</msub ></msub > b < ,and by Lemma 3.1 (i),

lim Qq</msub > (k) = 0,qs.t.

1 < q < p0</msub > .The first inequality (valid for all

> 0)
implies

Q p0</msub >+</msub > a > 0and again
by Lemma 3.1 (ii),

lim Qs</msub > (k) = +,swith

p + < s.The assertion follows since

can be taken arbitrarily small.

D. [19, Prop. 1.1] Using the above result, we get

QL</msub > Q¯L</msub > = Q L</msub > = p0</msub > ql</msub > = qu</msub > = p0</msub > Qand
vice versa.

E1 (

QΛ</msub > QL</msub >)
[20] We notice that, by B and D, we have that

QL</msub > Q</msub >, so it suffices
to show that

QΛ</msub > Q</msub >.

Let

QΛ</msub >(k) p0</msub > > 1.For any

> 0,we have

QΛ</msub >(k) < p0</msub > + for all

ksufficiently large, and using Lemma 3.4 we get

ln ek+2</msub >ek+1</msub > > (p0</msub > + )ln ek+1</msub >
ek</msub >
,

which gives

ek+2</msub >
(ek+1</msub >)p0</msub >+</msup > > ek+1</msub >
(ek</msub >)p0</msub >+</msup >
,

i.e.,

Qp0</msub >+</msub > (k + 1) > Qp0</msub >+</msub > (k), k k0</msub >.Considering now

2instead of

,we obtain similarly that

Qp0</msub >+2 </msub > (k + 1) > Qp0</msub >+
2
</msub > (k),k k1</msub >.
(34)

We prove that the monotone sequence

{Qp0</msub >+</msub > (k)}is
unbounded:

Qp0</msub >+</msub > (k) .Otherwise, if

M > 0s.t.

ek+2</msub >(ek+1</msub >)p0</msub >+</msup > < M,for
all

k,i.e.,

Q¯p0</msub >+</msub > < M,then according to Lemma
3.1 (i), this implies

Q¯p0</msub >+2 </msub > = 0in contradiction to the monotony from (34 ).

Similarly, one can prove that for any

> 0with

p0</msub > > 1,we have

QΛ</msub > (k) > p0</msub > for all

ksufficiently large
and we get

Qp0</msub ></msub > (k) 0.E2 (

QL</msub > QΛ</msub >) [20]
Assuming

QL</msub >(k) p0</msub > > 1,we have

lim k</munder >QΛ</msub >(k) = lim k</munder >QL</msub > (k) QL</msub > (k+1)1QL</msub > (k)1 = p0</msub >p0</msub >1
p0</msub >1
= p0</msub >.

_

It is interesting to notice that

Q-convergence with
order

p0</msub > > 1implies

Q¯1</msub > = 0.However, the reverse is not true
(i.e.,

Q-superlinear convergence
does not imply

Q-convergence
with order

p0</msub > > 1),
as the following examples show.


Example 3.6
a) [4, E 10.1.4] (we follow here [8, p. 94]) Let

0 < c < 1eand
consider the sequence

xk+1</msub > = xk</msub >ln xk</msub >,k 0,x0</msub > = c,

which converges superlinearly to

0.Suppose there exists

p0</msub > > 1such that

{xk</msub >}converges
with

Q-order (and
therefore with

QI,</msub >order)

p0</msub >.Then

> 0with

p0</msub > > 1,b > 0s.t.

xk+1</msub > bxkp0</msub ></msubsup >.Hence,

xk</msub >ln xk</msub > bxkp0</msub ></msubsup >or ( 1
xk</msub >
)p0</msub >1</msup >

ln 1
xk</msub >
b,

for all

ksufficiently large, which contradicts the well known limit

lim t</munder > tα</msup >ln t = ,
for any

α > 0.
As

QL</msub >(k) 1,
we get

ql</msub > = qu</msub > = 1.

b) Some simpler examples can be found either as explicitly given by

xk</msub > = kk</msup >[32, p. 22],

xk</msub > = 10k2</msup ></msup >[26], [20],

xk</msub > = 1k![27], or in the list of exercises, by

xk</msub > = ck2</msup ></msup >,

c > 1[4, E.9.2.1.j]. To show these assertions we can also use that

QL</msub >(k)or

QΛ</msub >(k) 1.
Expression (24) of Potra gives yet another example.


Remark 3.7
We notice that the orders

Q</msub >,QI,</msub >,QL</msub >,QΛ</msub >do not have elements to define the strict

Q-superlinear
convergence, when

Q¯1</msub > = 0and

Q¯p</msub > = +, p > 1.

The

Q-superlinear
convergence implies

R-superlinear
convergence, as in any norm [4, 9.3.1]

R¯1</msub > Q¯1</msub >.

In fact,

R¯1</msub >is a
lower bound for

Q¯1</msub >in all norms from

n</msup >.

It is interesting to see that sequences with infinite

Q-order exist too,
as one can take

xk</msub > = 222k</msup ></msup ></msup >(from the list of exercises in [4, E.9.2.1]).


Remark 3.8
An important aspect we address now is the problem of changing
the norms, as we have seen in Example 2.3 that for a given sequence in

n</msup >the existence of the

C-order
is norm-dependent. Ortega and Rheinboldt [4, 9.1.6] proved that the three
relations

Q¯p</msub > = 0,

Q¯p</msub >finite,

Q¯p</msub > = are norm-independent. The same hold for

Q p</msub >,
as one can easily verify (using also Lemma 3.1 ), which shows the norm-independence
of the

Q-order.
By the equivalence from Theorem 3.5 , we conclude that the rest of the

Q-orders
are norm independent too. This assertion will be further completed by the
computational convergence orders, as we shall see in the following subsection.

It is important to recall that for sequences with

Q-order

p0</msub > > 1,

while this

Q-order
is norm-independent, the values of the quantities

Q¯p0</msub ></msub >and

Q p0</msub ></msub >however, if finite, are norm-dependent [4, E.9.1-1].


Remark 3.9
One can easily show that the sequence

{xk</msub >}converges with

Q-order

p0</msub > > 1iff one of the the following sequences converges with the same order:

{ek+1</msub >ek</msub > },

{ek+1</msub > ek</msub >}or

{(ek</msub >)α</msup >}(

α > 0arbitrary, given).

3.1.2 R-convergence orders

In 1972, Brent [32] stated, while in 1984, Potra and Pták [8] shown
that

rl</msub > = R L</msub > := liminf k</munder > |ln ek</msub > |1k </msup >. (35)

In 1989 Potra [19] stated the equivalence

{R</msub >,RI,</msub >,RL</msub >},
which can be easily proved.

In fact we may extend Theorem 3.5 and the above relations. For brevity, we choose to write

{Q}as a generic form for all
the five equivalent

Q-type
orders,

{Q,Q</msub >,QI,</msub >,QL</msub >,QΛ</msub >}. The same will be
written in the sequel for

{Q</msup >},

{Q</msup >},

{R},

{R</msup >}and

{R</msup >}.


Theorem 3.10
(cf. [19]) In the assumptions of Theorem 3.5 , we have:

Cp0</msub ></msub > {Q} {R,R</msub >,RI,</msub >,RL</msub >,RΛ</msub >} (36)

(with the equivalence of

RΛ</msub >requiring
the additional assumption

1 < ql</msub > qu</msub > < ).

Moreover,

ql</msub > = Q L</msub > R L</msub > = R Λ</msub > = rl</msub > ru</msub > = R¯L</msub > = R¯Λ</msub > Q¯L</msub > = qu</msub >. (37)

Proof. (cf. [19]) We notice first that

QI,</msub >-order

p0</msub >implies

RI,</msub >-order

p0</msub >(and
therefore

{Q}{R</msub >,RI,</msub >,RL</msub >},
as mentioned above); this is obtained from the proofs of Propositions
9.3.2 and 9.3.3 in [4] and taking into account Proposition 2.13
above. A simpler approach results by considering directly (37), with

ql</msub > = qu</msub >.

The converse ”

Q R
is false, even if

{xk</msub >}has
exact

R-convergence
order

p0</msub >(i.e., (28)
or (29) hold), as shown in Examples 2.7 and 3.11 . One can easily show however that if

η = in (28), this attracts
convergence with

Q-order

p0</msub >.

The equivalence of the

RΛ</msub >-order

p0</msub >to the

RL</msub >, and therefore all
remaining

R-orders,
is based on the relation

ln ek+1</msub >ek</msub > = (ln ek</msub >) (ln ek+1</msub >
ln ek</msub >
1 ).

We note that there exist sequences (see, e.g., (25)), for which

ql</msub > = Q L</msub > < qu</msub > = Q¯L</msub > = , and which can therefore
be studied for the

R-orders.

Relation (37) – which is a completion of the one stated and proved by Potra [19] for the
lower orders

ql</msub >, Q L</msub >, R L</msub >,rl</msub >– can be obtained again from the well known inequalities for positive numbers

liminf k</munder >ak+1</msub >ak</msub > liminf k</munder > |ak</msub >| 1
k
</msup > limsup k</munder > |ak</msub >| 1
k
</msup > limsup k</munder >ak+1</msub >
ak</msub >

taking

ak</msub > = |ln ek</msub > |,
and then considering (31 ) and (35 ).  _

The following example shows that one may find sequences with

R-order
(

rl</msub > = ru</msub > = τ) arbitrary
high and

ql</msub >arbitrary close to 1 from above.


Example 3.11
[19] Given any numbers

1 < s < τ,we construct a
sequence

{xk</msub >}which has
the exact

R-convergence
order

τand
for which

ql</msub > s.Let

0 < < 1be given,
and take

η = q</msup >with

q > 1such
that

qs > τ.Define

xk</msub > = { τk</msup ></msup >,kodd,
ητk</msup >
</msup >,
keven.

The sequence

{xk</msub >}has
exact

R-convergence
order

τ.On the
other hand, for

keven we obtain

xk+1</msub >xks</msubsup > = (τ</msup >) τk</msup >
</msup >

(ηs</msup >) τk</msup >
</msup >
= ( τ</msup >
qs</msup >
)τk</msup >
</msup > ,

so that

ql</msub > s.In fact, one obtains

ql</msub > = Q L</msub > = τqwhile

qu</msub > = Q¯L</msub > = τq(

> τ,
this value representing the exact

R-order).

This example is also suitable for justifying the mentioned comments from
[13].

In (37), any inequality may be strict. Now we see (e.g., Examples
2.7 and 3.11 ) that the inner inequality may be equality (i.e., obtain

R-order)
while one of the outer inequalities may be strict (i.e., no

Q-order).

This also shows that the sequences with

Q-order

1and

Q-superlinear
convergence (see Example 3.6 ) cannot have (upper)

R-order
greater than one, i.e., they converge strict

R-superlinearly. The proof
is based on relation

R¯1</msub > Q¯1</msub > = 0(see [4]) and on (37).

 

Remark 3.12 We notice that the

R-order
is also a norm independent notion, as it can be proved by some results of
Ortega and Rheinboldt [4, 9.2.2].

3.2 Results relating the computational convergence orders

In this section, the errors

x</msup > xk</msub >are
replaced either by the corrections

xk+1</msub > xk</msub >,or by the nonlinear residuals

F(xk</msub >),
when solving nonlinear systems having the same number of equations and unknowns. We
shall assume that

sk</msub >0and

F (xk</msub >) 0, k 0.We present full proofs only for the

C– and

Q-convergence
orders.

3.2.1 Corrections

C-,

Q-orders
and corrections

As we have mentioned, Beyer, Ebanks and Qualls [20] shown that, for

p0</msub > > 1, the
errors and corrections converge simultaneously to zero with the same

C– resp.

Q-type
convergence order, and therefore each convergence order is equivalent to its
corresponding computational one. The following relation resulted:

{C,C</msup >} {Q,QL</msub >,QΛ</msub >,Q</msup >,Q
L
</msubsup >,Q
Λ
</msubsup >
}.
(38)

However, for proving

{C,C</msup >}and

Q</msup > Q,the considered assumptions were very strong:

{xk</msub >}was considered as a
monotone sequence from

(see [20, Sect. 4]).

We shall extend relation (38 ) and show some simplified proofs. For that, we
first present two auxiliary results.


Proposition 3.13
(Potra-Pták Lemma) [8, Prop. 6.4] The sequence

{xk</msub >}converges

Q-superlinearly
to

x</msup >if and only if the sequence

{sk</msub >}converges

Q-superlinearly
to zero.

Proof. Necessity. [8] Suppose

{xk</msub >}converges

Q-superlinearly. Then
there exists a positive integer

k0</msub >such that

ek+1</msub > 12ek</msub >,   for all k k0</msub >.

It follows that for

k k0</msub >,
we have:

sk+1</msub >
sk</msub > ek+1</msub >+ek+2</msub >
ek</msub >ek+1</msub >
3ek+1</msub >
ek</msub >
,

from which we deduce the

Q-superlinear convergence
of the sequence

{sk</msub >}.Sufficiency. [8] If we suppose that the sequence

{sk</msub >}converges

Q-superlinearly, then there
exists a positive integer

k0</msub >such that

sk</msub > 13sk1</msub >,   for all k k0</msub >.

For any

k k0</msub >we have:

ek+1</msub >
j=1</munderover >sk+j</msub > sk+2</msub >
j=0</munderover >3j</msup > = 3
2
sk+1</msub > 1
2
sk</msub >.

Finally, writing

ek+1</msub >
ek</msub > 3
2
sk+1</msub >

sk</msub >ek+1</msub >
3sk+1</msub >
sk</msub >
,

we infer that

{xk</msub >}converges

Q-superlinearly.
_

For necessity, an alternative proof in the one dimensional case can
be obtained using the Brezinski’s ”l’Hospital’s rule for sequences” (see
[28]).

The necessity was proved in the general case even before, by Dennis and
Moré.


Lemma 3.14
(Dennis-Moré) [5] If the sequence

{xk</msub >}converges

Q-superlinearly
then

lim k</munder >sk</msub >ek</msub > = 1.

Proof. [5] The result follows immediately from the equality

xk+1</msub >xk</msub >x</msup >xk</msub > x</msup >xk</msub >
x</msup >xk</msub >
= ek+1</msub >
ek</msub >
.

_

The assumption of this Lemma also implies that

{sk</msub >}converges

Q-superlinearly
to zero too.

The converse of this result does not hold, as an example given by the same authors
shows [5]:

x2k1</msub > = 1k!,

x2k</msub > = 2x2k1</msub >,

k 1.

Another proof of the Potra-Pták lemma was independently given by Walker
[47], in 1997.

Proof of Potra-Pták lemma. Necessity [47]: the Dennis-Moré Lemma.

Sufficiency. [47] Suppose

sk</msub > 0,

Q-superlinearly.
Then

ek+1</msub >ek</msub > =
k+1</munderover >(xj+1</msub > xj</msub >)


k</munderover >(xj+1</msub > xj</msub >)

k+1</munderover >sj</msub >

sk</msub >
k+1</munderover >sj</msub >
=
k+1</munderover >sj</msub >
sk</msub >

1
k+1</munderover >sj</msub >
sk</msub >
.

For each

k,
define

ρk</msub > := max jk</munder >sj+1</msub >sj</msub >.
Note that

lim k</munder >ρk</msub > = 0and

sk+i</msub >sk</msub > ρki</msubsup >for
each

i 0.
Then

ek+1</msub >ek</msub > ρk</msub >
1ρk</msub >

1 ρk</msub >
1ρk</msub >
= ρk</msub >
1 2ρk</msub >
0,

and it follows that

xk</msub > x</msup > Q-superlinearly.
_

We are now able to present the main result of this
subsubsection, which shows not only equivalence of

C-type resp.

Q-type orders, but also that
the lower and upper

Q-orders
are limits of some (truly) computational quantities.


Theorem 3.15
(cf. [20]) In the assumptions of Theorem 3.5 and notations
above, the following (generic) relations hold:

{C,C</msup >}{Q,Q</msup >}.

Moreover,

Q L</msub > = Q L</msubsup > = q
l
</msub >and   Q¯L</msub > = Q¯L</msubsup > = q
u
</msub >,
(39)
Q qu</msub ></msub > = Q qu</msub ></msubsup >and   Q¯
q
l</msub >
</msub > = Q¯ql</msub ></msubsup >.
(40)

Proof. The proof will consist of two steps. At step A, we prove

{C,C</msup >},
while at step B we prove the equivalence of the

Q-type and

Q</msup >-type
orders. Relations (39) and (40) follow along the way.

A1 (

C C</msup >) Suppose

{xk</msub >}converges
with

C-order

p0</msub > > 1.Then

{xk</msub >}converges

Q-superlinearly,
and by the Potra-Pták and Dennis-Moré Lemmas, we get

lim k</munder >ek+1</msub >(sk</msub >)p0</msub ></msup >(ek</msub >)p0</msub ></msup >sk+1</msub > = 1, (41)

which shows that

{xk</msub >}converges with

C</msup >-order

p0</msub >.A2 (

C</msup > C)
A2 is proved similarly to A1.

B1 (

Q Q</msup >) Suppose

{xk</msub >}converges with
some

Q-type
order

p0</msub >.Then

{xk</msub >}converges
with

Q-order

p0</msub >and therefore

Q-superlinearly;
by the Potra-Pták and Dennis-Moré Lemmas, it follows that

lim k</munder >ln sk+1</msub >ln sk</msub > = lim k</munder >ln (sk+1</msub >
ek+1</msub >
ek+1</msub > )

ln (sk</msub >
ek</msub >
ek</msub > )
= p0</msub >,
(42)

i.e.,

{xk</msub >}converges
with

QL</msubsup >-order

p0</msub >.One
can view the previous statement from a different viewpoint: the sequence

{sk</msub >}converges
with

QL</msub >-order

p0</msub >,so by the results in Subsection 3.1 , it converges with any

Q-type
order

p0</msub >,
whence the conclusion.

Relation (42) and Proposition 3.3 attract (39), while (41) implies
(40).

B2 (

Q</msup >-type

Q-type
order) The reverse implication is proved similarly.  _


Remark 3.16

a) Relation (40) shows in particular that if

{xk</msub >}has an exact

Q-order
of convergence

p0</msub > > 1,
then the sequence of corrections has not only the same

Q-order,
but even the same asymptotic constants.

b) We note that the norm-independence of the

Q-type
orders attract the same property for the

Q</msup >-type
orders.

R-orders
and corrections

Potra and Pták [8] have obtained some fundamental results in this direction,
which can be easily completed:


Theorem 3.17
(cf. [8, Prop. 6.20]) In the assumptions of Theorem 3.5 and
notations above, the following (generic) relations hold:

{R,R</msup >}

(with the equivalence of the

RΛ</msub >,RΛ</msubsup >-orders
requiring the additional assumption

1 < ql</msub > qu</msub > < ).

The proof relies on the result [8, Prop. 6.20]

rl</msub >{xk</msub >} = rl</msub >{xk+1</msub > xk</msub >},

which leads by analogy to relation

ru</msub >{xk</msub >} = ru</msub >{xk+1</msub > xk</msub >}.

The following three results show that the asymptotic constants from the

R-convergence
orders of the (errors of a) sequence and of its corrections are
not so tightly connected as in the case of convergence with

Q-order
(relation (40)).


Corollary 3.18
[8, p. 111] If

{xk</msub >}and

{xk+1</msub > xk</msub >}have exact

R-orders
of convergence, then they must have the same exact

R-order
of convergence.


Proposition 3.19
[8, p. 111] If

{xk</msub >}has an exact

R-order
of convergence this does not imply that

{xk+1</msub > xk</msub >}has an exact

R-order
of convergence, and vice versa.


Example 3.20
[8, p. 111] Let

c,r,sbe three real numbers with

0 < c < 1 < r < sand set

xk</msub > = { crk</msup ></msup >, k even,
crk1</msup >
</msup > + csk1</msup >
</msup >,
k odd,
yk</msub > = { crk</msup ></msup >,k even,
csk1</msup >
</msup >,
k odd.

It is easy to see that

ris the exact

R-order
of convergence of the sequences

{xk</msub >}and

{yk+1</msub > yk</msub >} ,while the sequences

{xk+1</msub > xk</msub >}and

{yk</msub >}have no exact

R-order
of convergence.

 

Remark 3.21 One can easily show that the sequence

{xk</msub >}converges with

R-order

p0</msub > > 1iff one of the the following sequences converges with the same order:

{ek+1</msub > ek</msub >}or

{(ek</msub >)α</msup >}(

α > 0arbitrary, given). The same holds for

{ek+1</msub >ek</msub > },
but under the supplementary assumption that

1 < ql</msub > qu</msub > < .

3.2.2 Nonlinear residuals F(xk</msub >)

– relationships

We consider now the solving of a system of nonlinear equations

F(x) = 0for a nonlinear
mapping

F : D n</msup > n</msup >, having
a solution

x</msup > D.
The quantities

F(xk</msub >)– in different formulae – were used not only to control the convergence of a given
sequence

{xk</msub >}to

x</msup >, but also to determine
at each step

kthe
next element,

xk+1</msub >(see, e.g., the well known works of Dembo, Eisenstat and Steihaug [7],
Eisenstat and Waker [10] and some extensions we have obtained in [11],
[12]).

We assume here that

A)

Fis differentiable
on the open domain

D;B)

F</msup >continuous at

x</msup >;C)

F</msup >is
invertible at

x</msup >.Replacing the errors by the corresponding residuals, we denote

Qp0</msub ></msubsup > (k) := Fk+1</msub >Fk</msub >p0</msub ></msup >

and similarly, the resulted definitions for the

C</msup >– and all the
rest of

Q</msup >-type
orders.

C-,

Q-orders
and nonlinear residuals

The following example shows that neither of

{C,C</msup >}and

C</msup >implies the other.


Example 3.22
a) Consider

xk</msub > x</msup > = 0 2</msup >,
with

xk</msub > = { (22k</msup ></msup >,0), kodd,
(22k</msup >
</msup >,22k</msup >1
</msup >),
keven,

and the (linear) mapping

F : (2</msup >,</msub >) (2</msup >,</msub >),

F(u,v) = (u,4v).
One can see that conditions A)–C) are satisfied, and further,

{xk</msub >}has

C-order

2,
while

{Fk</msub >}does not have

C-order
(in the max-norm).

b) Let

yk</msub > 2</msup >,
with

yk</msub > = { (22k</msup ></msup >,0), kodd,
(22k</msup >
</msup >,22k</msup >+1
</msup >),
keven,

and similarly the mapping

G(u,v) = (u,v4).
Now

{yk</msub >}has no

C-order,
while

{Gk</msub >}has

C-order

2(in the max-norm).

One can also view Example 2.3 in the sense that if one takes

F : (2</msup >,</msub >) (2</msup >,1</msub >)as the identity
operator,

F = I, the
sequence

{xk</msub >}from
(8) has

C-order

2, while

{Fk</msub >}does not
have

C-order.

Before the result relating the orders, we recall (without proof) an
auxiliary result, which is presented in different standard monographs and
papers.


Lemma 3.23
[7] Assume the mapping

Fis differentiable on
the open set

D, the
derivative

F</msup >continuous
at the solution

x</msup >, with the

Jacobian nonsingular at

x</msup >:

F</msup >(x</msup >)1</msup > n×n</msup >. Let

α = max {F</msup > (x</msup >) + 12β,2β }, where

β = F</msup > (x</msup >)1</msup >. Then there
exists

> 0such
that for any

x n</msup >with

x x</msup > ,
one has

1
α x x</msup > F (x) α x x</msup >.

We notice that

α > 1.
The sharpest bounds seem to be obtained by Rheinboldt [6, Th.4.2]: given

0 < < 1F</msup >(x</msup >)1</msup >, there
exists

δ > 0s.t.

xwith

x x</msup > < δwe have

( 1F</msup >(x</msup >)1</msup > ) x x</msup > F (x) (F</msup > (x</msup >) + )x x</msup >.

We obtain the final result from this paper, which shows in fact the equivalence of
all

Q-type
orders.


Theorem 3.24
Under the assumptions of Theorem 3.5 , A)–C) and with the
above notations, the following (generic) relations hold:

{Q,Q</msup >,Q</msup >},
{C,C</msup >} C</msup >,
{C,C</msup >} C</msup >,
C</msup >{Q,Q</msup >,Q</msup >}.

Proof. Assume

{xk</msub >}converges
with some

Q-type
order, say

QL</msub >-order

p0</msub > > 1.Then, by Lemma 3.23 , we have

ln ek+1</msub >ln α
ln ek</msub >+ln α ln Fk+1</msub >
ln Fk</msub >
ln ek+1</msub >+ln α
ln ek</msub >ln α
,

which shows that

QL</msubsup > (k) p0</msub >,and further
the equivalence of the

Q</msup >-type
orders.

The implication

(QL</msubsup > (k) p0</msub >) (QL</msub > (k) p0</msub >)follows in a similar manner.  _

The

Q</msup >-convergence
orders are norm-independent, being equivalent to the

Q-orders.

R-orders
and nonlinear residuals

We may complete Theorem 3.17 by the generic relation

{R,R</msup >,R</msup >},

the proof relying on the inequality from Lemma 3.23 .

3.3 Summary of the high (computational) convergence orders

We present the following diagram in order to have a complete
picture on the implications/equivalences of the high orders

p > 1. As in [20], we use
the symbol ”

” for the
conjunction of

and

, while the equivalence of
the

RΛ</msub >-type orders requires
the additional assumption

1 < ql</msub > qu</msub > < .

C{{⁄⇑′{QR⁄⇓′C,,,QRC′,′,′QR}′′′′}}

4 Linear convergence

The

Q-linear
convergence is less attractive in numerical applications, but remains an important
theoretical topic (e.g., in the field of Dynamical Systems, as noted in
[20]).

In contrast to the high convergence orders

p > 1, in
the linear case there are fewer equivalences and more negative results,
illustrated by counterexamples. Beyer, Ebanks and Qualls [20] did most of the
work in providing them, in [20], which we also summarize in the diagram
below:

{{{{{∖∖CΛΛLL,′}′,C},QQ′′}}}

However, it is worth noting that different relations (e.g.,

{C1</msub >,C1</msubsup >}, Q1</msubsup > Q1</msub >)
were obtained under the strong assumption that

{xk</msub >}is a monotone
sequence from

.Zhang and Wang [62] completed the diagram with two implications. The first one,

Λ1</msub > L1</msubsup >,was proved
again under the monotony assumption on the sequence of real numbers. The second one,

Λ1</msubsup > Λ1</msub >, was proved
under some even further supplementary assumptions (we mark this by dashed line in the
diagram):

limsup ak</msub > < 1and

liminf ak</msub > > 0,
where

ak+2</msub > = xk+2</msub >xk+1</msub >xk+1</msub >xk</msub >,

a1</msub > = x1</msub > x0</msub >,

a0</msub > = x0</msub >. The
following completed diagram resulted.

{{{{{CΛΛLL,′}′,C},QQ′′}}}

5 Conclusions

As the completion

qu</msub >for the
definition of the

Q-order
of Beyer, Ebanks and Qualls remained unknown, most of the results on the

Q-orders
of different iterative methods were given only in terms of the lower

Q-order

ql</msub >. Ortega and
Rheinboldt used

ql</msub >and

rl</msub >to measure the speed of convergence of some ”entire” iterative processes
both for fixed point problems (the Ostrowski local attraction theorem [4,
Th. 10.1.3, Th. 10.1.6, Th. 10.1.7]) and for nonlinear systems of equations (the
Newton attraction theorem [4, Th. 10.2.2]). Further results for characterizing the lower

bounds

ql</msub >for a single sequence (instead of the whole method) were obtained by us [14], [63]
– in the case of (perturbed) successive approximations – respectively by Dembo,
Eisenstat and Steihaug [7] and us [11], [14], in the case of different Newton-type
iterations in presence of error sources.

It is interesting to note that results on the upper

Q-order

qu</msub >exist
too. One can find them (where else?) in the book of Ortega and Rheinboldt, both
for the successive approximations [4, Th.10.1.7], and for the Newton method [4,
Th.10.2.2]. It seems interesting to clarify the conditions ensuring the upper

Q-order
for individual sequences.

The further consideration only of the lower

Q-order

ql</msub >may remain
a powerful theoretical tool in measuring the convergence rate of sequences. In the case
when a

Q-order

p0</msub >exists
(

p0</msub > = ql</msub > = qu</msub >), the use of the
computational quotients

QL</msubsup >(k)may offer approximations to

p0</msub >,
while otherwise (when

ql</msub > < qu</msub >)
the use of the computational quotients may hopefully offer just an idea about the value
of

ql</msub > = Q L</msubsup >(and
perhaps

qu</msub > = Q¯L</msubsup >too).

Acknowledgments. The author is grateful to an anonymous referee for the
careful reading of the manuscript and for several constructive remarks, that
improved the presentation (specially in Section 3 ).

References


[1]    
J. Fourier, Question d’analyse algébrique, Bull. des Science par la
Societe Philo., 67 (1818), pp.
61–67. http://gallica.bnf.fr/ark:/12148/bpt6k33707/f248.item accessed
February 23, 2018.


[2]    
T.J. Ypma, Historical development of the Newton-Raphson method,
SIAM Review, 37 (1995) no. 4, pp. 531–551.


[3]    
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.


[4]    
J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear
Equations in Several Variables, Academic Press, New York, 1970.


[5]    
J.E. Dennis, Jr. and J.J. Moré, A characterization of superlinear
convergence and its application to quasi-Newton methods
, Math.
Comput., 28 (1974) no. 126, pp. 549–560.


[6]    
W.C. Rheinboldt, Methods for Solving Systems of Nonlinear
Equations, 2nd ed., SIAM, Philadelphia, 1998.


[7]    
R.S. Dembo, S.C. Eisenstat and T. Steihaug, Inexact Newton
methods
, SIAM J. Numer. Anal., 19 (1982) no.2, pp. 400–408.


[8]    
F.A. Potra, V. Pták, Nondiscrete Induction and Iterative
Processes, Pitman, Boston, Massachusetts, 1984.


[9]    
M. Raydan, Exact order of convergence of the secant method, J.
Optim. Theory Appl., 78 (1993) 3, pp. 541–551.


[10]    
S.C. Eisenstat, H.F. Walker, Choosing the forcing terms in an

inexact Newton method, SIAM J. Sci. Comput., 17 (1996) no. 1, pp.
16–32.


[11]    
E. Cătinaş, Inexact perturbed Newton methods and applications
to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3,
pp. 543–570.


[12]    
E. Cătinaş, The inexact, inexact perturbed and quasi-Newton
methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp.
291–301.


[13]    
R.A. Tapia, J.E. Dennis, Jr., J.P. Schäfermeyer, Inverse, shifted
inverse, and Rayleigh quotient iteration as Newton’s method, SIAM
Review, 60 (2018) no. 1, pp. 3–55. DOI 10.1137/15M1049956.


[14]    
E. Cătinaş, On the superlinear convergence of the successive
approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp.
473–485.


[15]    
R. Hauser, J. Nedić, On the relationship between the convergence
rates of iterative and continuous processes, SIAM J. Optim. Appl., 18
(2007) no. 1, pp. 52–64.


[16]    
N.J. Higham, Functions of Matrices: Theory and Computation,
SIAM, Philadelphia, 2008.


[17]    
F. Soleymani, On finding robust approximate inverses for large
sparse matrices, Linear and Multilinear Algebra, 62 (2014) no. 10,
1314-1334.


[18]    
C. Brezinski, Accélération de la Convergence en Analyse
Numérique, Springer-Verlag, Berlin, 1977.


[19]    
F.A. Potra, On

Q-order
and

R-order
of convergence, J. Optim. Theory Appl., 63 (1989) no. 3, pp. 415–431.


[20]    
W.A. Beyer, B.R. Ebanks, C.R. Qualls, Convergence rates and
convergence-order profiles for sequences, Acta Appl. Math., 20 (1990),
pp. 267–284.


[21]    
S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with
accelerated third-order convergence, Appl. Math. Lett., 13 (2000) no. 8,
pp. 87–93.


[22]    
A. Cordero, J.R. Torregrosa, Variants of Newton’s method using
fifth-order quadrature formulas, Appl. Math. Comput., 190 (2007) no.
1, pp. 686–698.


[23]    
J.F. Traub, Iterative Methods for the Solution of Equations,
Prentice-Hall, Englewood Cliffs, N.J., 1964.


[24]    
C. Brezinski, Comparaison des suites convergences, Revue
Française d’Informatique et de Recherche Operationelle, 5 (1971) no.
2, pp. 95–99.


[25]    
H. Schwetlick, Numerische Lösung Nichtlinearer Gleichungen,
VEB, Berlin, 1979.


[26]    
C. Brezinski, Vitesse de convergence d’une suite, Rev. Roumaine
Math. Pures Appl., 30 (1985), pp. 403–417.


[27]    
L.O. Jay, A note on Q-order of convergence, BIT, 41 (2001) no. 2,
pp. 422–429.


[28]    
C. Brezinski, Limiting relationships and comparison theorems for
sequences, Rend. Circolo Mat. Palermo, Ser. II, vol. 28 (1979), pp.
273–280.


[29]    
N. Bourbaki, Fonction d’une Variable Réelle. Livre 4. Chapitre 5.
Hermann, Paris, 1951.


[30]    
D.D. Wall, The order of an iteration formula, Math. Comp., 10
(1956) no. 55, pp. 167–168.


[31]    
L. Tornheim, Convergence of multipoint iterative methods, J. ACM,
11 (1964), pp. 210–220.


[32]    
R.P. Brent, Some efficient algorithms for solving systems of
nonlinear equations, SIAM J. Numer. Anal., 10 (1973), pp. 327–344.


[33]    
S.J. Wright, Primal-Dual Interior-Point Methods, SIAM,
Philadelphia, 1997.


[34]    
Y. Ye, Interior Point Algorithms: Theory and Analysis, Wiley, 1997.


[35]    
F.A. Potra, Q-superlinear convergence of the iterates in primal-dual
interior-point methods, Math. Program., Ser. A 91 (2001), pp. 99—115,
DOI 10.1007/s101070100230.


[36]    
F.A. Potra, Primal-dual affine scaling interior point methods for
linear complementarity problems, SIAM J. Optim., 19 (2008) no. 1, pp.
114-–143.


[37]    
R.P. Brent, S. Winograd, P. Wolfe, Optimal iterative processes for
root-finding, Numer. Math., 20 (1973), pp. 327–341.


[38]    
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.


[39]    
A. Feldstein, R.M. Firestone, Hermite interpolatory iteration
theory and parallel numerical theory, Report, Division of Applied
Mathematics, Brown University, 1967.


[40]    
A. Feldstein, R.M. Firestone, A study of Ostrowski efficiency for
composite iteration algorithms, Proceedings of the 1969 24th national
conference, ACM, 1969.


[41]    
M. Igarashi, T. Ypma, Empirical versus asymptotic rate of
convergence of a class of methods for solving a polynomial equation, J.
Comp. Appl. Math., 82 (1997), 229–237.


[42]    
J.W. Schmidt, On the R-order of coupled sequences, Computing, 26
(1981), pp. 333—342.


[43]    
W.A. Beyer, P.R. Stein, Period doubling for trapezoid function
iteration: metric theory, Adv. Appl. Math., 3 (1982), pp. 1–17.


[44]    
R. Cavanagh, Difference equations and iterative processes, Doctoral
thesis, Univ. of Maryland, College Park, 1970.


[45]    
A.I. Cohen, Rate of convergence and optimality properties of root
finding and optimization algorithms, Doctoral dissertation, University
of California, Berkeley, 1970.


[46]    
Li 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), PhD thesis, State
University of New York at Buffalo, 1986.


[47]    
H.F. Walker, An approach to continuation using Krylov subspace
methods, Computational Science in the 21st Century, J. Periaux, ed.,
John Wiley and Sons, Ltd., 1997, pp. 72–81.


[48]    
M. Grau-Sánchez, M. Noguera, J.M. Gutiérrez, On some
computational orders of convergence, Appl. Math. Lett., 23 (2010), pp.
472–478.


[49]    
M. Grau-Sánchez, M. Noguera, À. Grau, J.R. Herrero, On new
computational local orders of convergence, Appl. Math. Lett., 25 (2012),
pp. 2023–2030.


[50]    
M. Grau-Sánchez, M. Noguera, On Convergence and efficiency in
the resolution of systems of nonlinear equations from a local analysis. In:
Amat S., Busquier S. (eds) Advances in Iterative Methods for Nonlinear
Equations. SEMA SIMAI Springer Series, vol 10. Springer, 2016.


[51]    
I. Păvăloiu, Sur l’ordre de convergence des méthodes
d’itération, Mathématica, 23 (46) (1981) no. 1, pp. 261–272
(in French). https://ictp.acad.ro/convergence-order-iterative-methods/
accessed March 22, 2018.


[52]    
I. Păvăloiu, Approximation of the roots of equations by
Aitken-Steffensen-type monotonic sequences, Calcolo, 32 (1995) nos.
1-2, pp. 69–82. DOI 10.1007/BF02576543.


[53]    
I. Păvăloiu, Optimal algorithms concerning the solving
of equations by interpolation, Research on Theory of Allure,
Approximation, Convexity and Optimization, Ed. Srima,
Cluj-Napoca (1999), pp. 222–248, ISBN 973-98551-4-3.

Optimal algorithms concerning the solving of equations by interpolation


accessed March 22, 2018.


[54]    
I. Păvăloiu, On the convergence of one step and
multistep iterative methods, unpublished manuscript,
https://ictp.acad.ro/convergence-one-step-multistep-iterative-methods/,
accessed April 1st, 2018.


[55]    
W. Burmeister, J.W. Schmidt, On the R-order of coupled sequences
II
, Computing, 29 1982, pp. 73–81.


[56]    
W. Burmeister, J.W. Schmidt, On the R-order of coupled sequences
III
, Computing, 30 1983, pp. 157–169.


[57]    
J. Herzberger, L. Metzner, On the

Q-orders
of convergence of coupled sequences arising in iterative numerical
processes, Computing, 57 (1976), pp. 357–363.


[58]    
R.G. Voigt, Orders of convergence for iterative procedures, SIAM J.
Numer. Anal., 8 (1971), pp. 222–243.


[59]    
R. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs,
New Jersey, 1962.


[60]    
J.M. Ortega, M.L. Rockoff, Nonlinear difference equations and
Gauss-Seidel type iterative methods, SIAM J. Numer. Anal., 3 (1966)
no. 3, pp. 497–513.


[61]    
J.E. Dennis, On Newton-like methods, Numer. Math., 11 (1968),
pp. 324–330.


[62]    
R. Zhang, L. Wang, Two convergence problems for monotone
sequences, Acta Appl. Math., 47 (1997), pp. 213–220.


[63]    
E. Cătinaş, On accelerating the convergence of the successive
approximations method, Rev. Anal. Numér. Théor. Approx., 30
(2001) no. 1, pp. 3–8.

A survey on the high convergence orders and
computational convergence orders of sequences

Emil Cătinaş

 

author address: Tiberiu Popoviciu Institute of Numerical Analysis, Romanian
Academy, P.O. Box 68-1, Cluj-Napoca, Romania. e-mail: ecatinas@ictp.acad.ro,
www.ictp.acad.ro/catinas

version submitted to Appl. Math. Comput., published with some changes in vol.
343 (2019) 1-20.

Abstract

Twenty years after the classical book of Ortega and Rheinboldt was
published, five definitions for the

Q-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

n</msup >;
Q-, C-, and R-convergence orders of sequences; computational convergence
orders.

MSC 2010. 65J05.

1 Introduction

Consider in the beginning a sequence

{xk</msub >}from

, which converges
to a finite limit

x</msup >.
Its speed of convergence is characterized by several measures, called convergence
orders, which are fundamental notions in Mathematical and in Numerical
Analysis.

The relation

lim k</munder > |x</msup >xk+1</msub >| |x</msup >xk</msub >|p</msup > = Cp</msub > (0,+)

(1)

gives the classical definition of the convergence with order

p > 1, 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

Cp</msub >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
norm-dependent problem. Moreover, as it requires the knowledge of both

pand

x</msup >,
relation (1 ) is only of theoretical use.

Still, such definition (along with the

Q-superlinear convergence,
which requires

C1</msub > = 0for

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 so-called
computational convergence orders, that iteratively approximate the convergence
orders using only the elements of the sequence known at the step

k.
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

Q– and

R-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)

C– and

Q-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

x</msup >), but even
the iterative method itself (as it was given in the well known book of J.F. Traub [23,
formula (8-14), p. 164]2 ).

In numerous works, the classical

Q
and

R-orders
defined by Ortega and Rheiboldt lead to statements expressed as

{xk</msub >}has

Q-order (at
least)

p0</msub > > 1and

R-order
(at least)

p1</msub >,

p1</msub > > p0</msub >”. The

Q-order
we study here is a completion to the classical one, and no
longer allows such conclusions. Instead, if having at all an order

p0</msub > > 1,
the sequences will be only in one of the cases (the

C-order
is obtained by taking norms in (1)):


  • {xk</msub >}has

    R-order

    p0</msub > > 1(but neither

    C
    nor

    Q-order);


  • {xk</msub >}has the same

    R
    and

    Q-order

    p0</msub > > 1(but no

    C-order);


  • {xk</msub >}has the same

    R-,

    Q
    and

    C-order

    p0</msub > > 1.

In less words, the relation reads for

p0</msub > > 1as

C-order p0</msub > Q-order p0</msub > R-order p0</msub >,

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

Q– and

R-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
(

p > 1), giving full
proofs for

C

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

R-orders. We analyze next
the computational

C– and

Q-convergence orders
based on the corrections

xk+1</msub > xk</msub >(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 Dennis-Moré lemma [5] allow us to complete the proofs). We also
consider computational convergence orders based on the nonlinear residuals

F(xk</msub >),
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 Q-type (computational) convergence orders.

2.1.1 Convergence orders based on the errors x*-xk

We turn now our attention to a sequence

{xk</msub >}from

n</msup >, which converges
to a finite limit

x</msup >;
we prefer the common setting of a normed
space—

n</msup >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

xk</msub >x</msup >,

k 0.
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”)

ek</msub > = x</msup > xk</msub >.

As we have mentioned, the oldest definition of convergence with order

p0</msub > > 1is
that

lim k</munder >Qp0</msub ></msub > (k) := lim k</munder > ek+1</msub >(ek</msub >)p0</msub ></msup > = Cp0</msub ></msub > (0,+),

(2)

which we call, as in [20],

C-convergence with
order

p0</msub >(the linear
convergence requires

p0</msub > = 1and

0 < C1</msub > < 1)

Qcomes from quotient. If it exists, it is uniquely defined and it implies that

> 0,k0</msub > 0such
that

(Cp0</msub ></msub > )ekp0</msub ></msubsup > ek+1</msub > (Cp0</msub ></msub > + )ekp0</msub >
</msubsup >,k k0</msub >,

(3)

or, less sharp, the existence of

A,B > 0such that

Aekp0</msub ></msubsup > ek+1</msub > Bekp0</msub >
</msubsup >,k 0.

(4)


Remark 2.1
a) For example, if

p0</msub > = 2and

C2</msub >is not too large, relation (3 ) says that the error is approximately squared at
each step

k,
for

ksufficiently large.

b) Some authors have used (4 ) to define the exact

Q-order
of convergence

p0</msub >(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

liminf and

limsup are finite and nonzero. Denoting

Q p0</msub ></msub > := liminf k</munder >Qp0</msub ></msub >(k),Q¯p0</msub ></msub > := limsup k</munder >Qp0</msub ></msub >(k),

(5)

relation

0 < Q p0</msub ></msub > < Q¯p0</msub ></msub > < +

(6)

implies (4 ):

0 < Q p0</msub ></msub >attracts the
first inequality in (4 ), while

Q¯p0</msub ></msub > < +the second one (see also [4, 9.3.3]).

d) As widely known, the larger the order

p0</msub >, the
faster the speed of convergence.

The

C-order
is a norm-dependent notion, as the following two examples show for the

C-orders

1and

2.


Example 2.2
[27] Let

x</msup > = (0,0) 2</msup >,
the sequence

xk</msub > = { (2k</msup >,0), keven,(0,2k+1</msup >),k odd.

(7)

Consider the norms

(u,v)A</msub > = 2|u| + |v|,(u,v)B</msub > = |u| + 2|v|.

It follows

C1</msub > = 12for
the

A-norm, while

C1</msub >does not exist
for the

B-norm.


Example 2.3
Let

x</msup > = (0,0) 2</msup >and

xk</msub > = { (22k</msup ></msup >,0), kodd, (22k</msup >
</msup >,22k</msup >
</msup >),
k even.

(8)

One obtains

C2</msub > = 1when
considering the maximum norm

</msub >,
while

C2</msub >does not
exist for the norm

1</msub >.

The following definition for the convergence order seems to be the
second oldest one (we adopt the notation from [20]). The sequence

{xk</msub >}has

QL</msub >-convergence
order

p0</msub > 1if:

QL</msub > (k) := ln ek+1</msub > ln ek</msub > p0</msub >,as k .

(9)


Remark 2.4
a) As noticed by Brezinski in [28] and [26],

QL</msub >is a particular case of a definition used by Bourbaki [29] in order to compare
the convergence orders of two sequences.

The measure

QL</msub >was then independently considered by Wall in 1956 [30] (see also [31], [4,
ch. 9], [32, ch. 2] and [25]), argued – for

lg instead of

ln – as the limit of the quotient of two consecutive numbers of correct decimal
places in

xk+1</msub >resp.

xk</msub >(see also [8, p. 90]); in this sense, convergence for example with

QL</msub >-order

2means intuitively that, from a certain step, the number of correct digits are
doubled the successive elements of

{xk</msub >}.
The logarithm base may be taken as any positive real number

a1;
we shall consider further the natural base

e for simplicity.

b) In contrast to

Qp0</msub ></msub >(k),
the expression

QL</msub >(k)does not require the (usually unknown) value

p0</msub >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

Q L</msub > := liminf k</msub >QL</msub >(k),
a quantity which we analyze in Proposition 3.3 ).

c) Brent, Winograd and Wolfe noticed in [37] that

C-order

p0</msub >immediately implies

QL</msub >-order,
of same value.

d) We shall see later, in Remark 3.8 , that this notion (cf. [38]), as well as
the other

Q-orders,
is norm-independent (also noted by Potra [19]).

In 1967, Feldstein and Firestone [39] introduced essentially
the following convergence order, which we denote here by

Q</msub >.

The sequence

{xk</msub >}has

Q</msub >-convergence
order

p0</msub >if:

lim k</munder >Qp0</msub ></msub > (k) = 0, > 0 with p0</msub > 1, (10)
lim k</munder >Qp0</msub >+</msub > (k) = , > 0.
Condition

p0</msub > 1will be a standing assumption from here on, in all subsequent
formulas, while in Section 3 we will implicitely assume that

p0</msub > > 1.

The convergence with

Q</msub >-convergence
order

p0</msub > > 1can be expressed in a more intuitive form (see also [20]):

lim k</munder >Qp</msub >(k) = 0,1 < p < p0</msub >,
lim k</munder >Qp</msub >(k) = + ,p > p0</msub >.
Two years later, the same authors [40] expressed the above order
in an equivalent form, which in fact will be the same as the

Q-order
defined below. Let

λ</msub > = sup {p : lim k</munder >Qp</msub >(k) = 0 }, (11)
λ</msup > = inf {p : lim
k
</munder >Qp</msub >(k) = }.

They noticed that

0 λ</msub > λ</msup >, and
when

p0</msub > = λ</msub > = λ</msup >, the sequence was
said to have the order

p0</msub >.

In their classical book from 1970, Ortega and Rheinboldt [4,
Ch. 9] introduced and studied the quantity denoted in (5) by

Q¯p</msub >,for
all

p 1:

Q¯p</msub > = limsup k</munder >Qp</msub > (k).

They shown the following behavior for

Q¯p</msub >as a
”function” of

p.


Proposition 2.5
[4, 9.1.2] Exactly one of the following conditions holds:

a)

Q¯p</msub > = 0,p [1,+);b)

Q¯p</msub > = +,p [1,+);c)

p0</msub > [1,+)s.t.  

Q¯p</msub > = 0,

p [1,p0</msub >)and

Q¯p</msub > = +,

p (p0</msub >,+).

The quantity

ql</msub > = { ,   if  Q¯p</msub > = 0,p 1 inf {p [1,) : Q¯p</msub > = + }

(12)

(called in [4] as

Q-convergence
with order at least

ql</msub >and denoted by O

Q</msub >{xk</msub >})
stood there and in many subsequent works for a measure of
the convergence order. We call it, as in [20], the lower

Q-order, and
denote it by

ql</msub >(instead of

pl</msub >used there). We shall see that the lower

Q-order needs to be completed
by the upper

Q-order for
obtaining the ”full”

Q-order;
as a matter of fact,

ql</msub > = λ</msub >,
the lower order from (11) defined in [40].


Remark 2.6
The sequence

{xk</msub >}was said in [4, Def. 9.1.4] that converges faster than

{yk</msub >}if for
some

p0</msub > 1,we
have

Q¯p0</msub ></msub >{xk</msub >} < Q¯p0</msub ></msub >{yk</msub >}(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 < Cp0</msub ></msub >{xk</msub >} < Cp0</msub ></msub >{yk</msub >} < +,

numerical evidence reveals that

{xk</msub >}does not necessarily converge faster than

{yk</msub >},
as shown by Ypma and Igarashi [41].

On the other hand, as noticed by Brezinski [26], the sequences given by

xk</msub > = 1kand

yk</msub > = 1k2</msup >,

k 0,
have the same asymptotical constant,

Q1</msub >{xk</msub >} = Q1</msub >{yk</msub >},
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

Q-convergence
order in the following way, which will be used throughout the paper. Let the lower

Q-order

ql</msub >be
given in (12 ), recall the notation from (5)

Q p</msub > = liminf k</munder >Qp</msub > (k)

and define the upper

Q-order

qu</msub >by

qu</msub > = sup {p [1,+) : Q p</msub > = 0 }.

Then the

Q-convergence
is with order 

p0</msub >if

p0</msub > = ql</msub > = qu</msub >.This definition is equivalent to the one given by Feldstein and Firestone in (11),
as

ql</msub > = λ</msub >and

qu</msub > = λ</msup >.

In 1981, Schmidt [42] introduced the following type of convergence order, denoted here,
as in [20], by

QΛ</msub >:

{xk</msub >}has

QΛ</msub >-convergence
order

p0</msub >if

QΛ</msub > (k) = ln ek+2</msub >ek+1</msub >
ln ek+1</msub >
ek</msub >
p0</msub >,   as  k .

(13)

The author gave no result relating the

Q– and

QΛ</msub >-orders he introduced,
and assumed that

QΛ</msub >is
equivalent to an

R-order
(while it is in fact a

Q-order,
as we shall see).

In 1982, Beyer and Stein [43] independently introduced
the measure (19 ) below, which is somehow similar to

QΛ</msub >, and in fact
equivalent to

QΛ</msubsup >defined in subsubsection 2.1.2 .

In 1985, unaware of [42] and [43], Brezinski [26] considered the

QΛ</msub >-convergence order

and, assuming that

{xk</msub >}has the exact

Q-order of
convergence

p0</msub > > 1(as defined
by (4 )), he proved that

{xk</msub >}has the

QΛ</msub >-order

p0</msub >(and

QL</msub >-order

p0</msub >as
well).

In 1989, Potra introduced in [19] the following type of convergence order (denoted
here by

QI,</msub >,
with ”

I
from ”inequality”), which will be useful in obtaining some simplified
proofs.

The sequence

{xk</msub >}has

QI,</msub >-convergence
order

p0</msub >if

> 0,

a,b > 0such
that

aekp0</msub >+</msubsup > ek+1</msub > bekp0</msub ></msubsup >,k 0.

(14)

This can be regarded as a generalization of inequalities (4 ).

Potra shown some fundamental results in our study, that

QI,</msub >-convergence
with order

p0</msub > > 1is
equivalent to

Q</msub >– and
to

QL</msub >-convergence
of same order, which we denote here, as in [20], by symbols between curled
braces:

{Q</msub >,QI,</msub >,QL</msub >} .

Ortega and Rheinboldt [4, N.R. 9.2.2] have previously noticed a weaker property of

QL</msub >-convergence with order

p0</msub >, namely that it implies
(partial)

R-convergence
with order

p0</msub >(i.e., in the
notations below, that

p0</msub > = rl</msub >).

In the same paper, Potra has also considered the lower and upper

Q-orders, when noting that if
a sequence has exact

Q-order

p0</msub >then

ql</msub > = qu</msub > = p0</msub >.

In 1990, Beyer, Ebanks and Qualls [20], unaware of the definitions
and the results mentioned above, introduced the definitions of the

Q– and

QΛ</msub >-orders
and shown some other fundamental results, that convergence with

Q-order

p0</msub > > 1is equivalent
to

QΛ</msub >and to

QL</msub >-convergence
with same order:

{Q,QL</msub >,QΛ</msub >} .

They considered

QΛ</msub >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

ql</msub > qu</msub >(which justifies
the terminology lower/upper); when this inequality is strict, the sequence does not have
a

Q-order,
as shown below.


Example 2.7
Let

xk</msub > = { 22k</msup ></msup >,keven,
32k</msup >
</msup >,
kodd.

We get

Q¯p</msub > = { 0, 1 p < log 3</msub >4,
1, p = log 3</msub >4,
+,p > log 3</msub >4,
and  Q p</msub > = { 0, 1 p < 4log 4</msub >3,
1, p = 4log 4</msub >3,
+,p > 4log 4</msub >3.

The graphical illustration of

Q¯p</msub >and

Q p</msub >for

p 1leads to the so called convergence profile of the sequence, as termed in [20]
(see Fig. 1 ).

pict
Figure 1: Q 

convergence-order profile for  

{xk</msub >}defined in Example 2.7 . This is a graph of the limit points of

 

Qp</msub >(k)as a function of

 

p.
The vertical scale is not to scale.

This sequence does not have a

Q-order, as

ql</msub > = log 3</msub >4 1.26 < qu</msub > = 4log 4</msub >3 3.17, but it converges
with (exact)

R-order

2,
as defined later. We note the classical statement in this case,

{xk</msub >}converges
with

Q-order
(at least)

log 3</msub >4 1.26and
with

R-order
(at least)

2”,
which no longer holds in the setting of this paper.

An elementary example shows that in case of convergence with

Q-order

p0</msub >,apart
of finite nonzero values of one (or both) of the asymptotical constants

Q p0</msub ></msub > Q¯p0</msub ></msub >, any
of the following relations may hold:

Q p0</msub ></msub > = Q¯p0</msub ></msub > = +, (15)
Q p0</msub ></msub > = Q¯p0</msub ></msub > = 0, (16)
Q p0</msub ></msub > = 0 andQ¯p0</msub ></msub > = +. (17)


Example 2.8
Let

xk</msub > = 22k</msup >k</msup >,y
k
</msub > = 2k2k</msup >
</msup >,zk</msub > = { xk</msub >,kodd,
yk</msub >,k even.

It is easy to verify that for

p0</msub > = 2,the sequences

{xk</msub >} , {yk</msub >} , {zk</msub >}verify respectively (15), (16) and (17) (

{xk</msub >}was also considered in [20]).

Schwetlick [25, Ü.4.2.3, p. 93] also considered an example of the type

xk</msub > = ek</msub >|ln ek</msub >|,

yk</msub > = ek</msub >|ln ek</msub >|,
for the errors

ek</msub >converging with exact

Q-order

2.

Potra [19] considered

ek</msub > = { ek+1</msub > = 2ek</msub >ek12</msubsup >,keven,
ek+1</msub > = ek</msub >ek12</msubsup >, k odd,

which has

Q-order

2and

Q¯2</msub > = +.

Jay [27] considered the sequence of the type

xk</msub > = k22k</msup ></msup >,

keven,

xk</msub > = 22k</msup ></msup >k,

kodd, which satisfies (17) for

p0</msub > = 2.

One may easily find examples when

Q p0</msub ></msub > = 0and

Q¯p0</msub ></msub >is finite, nonzero, or, on the other hand, when

Q p0</msub ></msub >is finite, nonzero and

Q¯p0</msub ></msub > = +.
Jay [27] considered the sequence

xk</msub > = xk1q</msubsup >k,

kodd,

xk</msub > = xk1q</msubsup >,

keven, for

q 1,

x0</msub > = 1,
for which one obtains

Q q</msub > = 0and

Q¯q</msub > = 1.

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]:

xk+1</msub > = (xk</msub >)p1k </msup >,

k 1,

x1</msub > = ,

0 < < 1and also

x2k</msub > = (rs)k</msup ></msup >,

x2k+1</msub > = rk</msup >sk+1</msup ></msup >,

0 < < 1 < r < s.


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

p0</msub > = 2and

Q 2</msub > = Q¯2</msub > = +.

 

Remark 2.10 When

Q¯1</msub > = 0,i.e.,

lim k</munder >ek+1</msub >ek</msub > = 0,

it is said that the sequence converges (at least)

Q-superlinearly.
The convergence is strict

Q-superlinearly,
when

ql</msub > = 1(i.e.,

Q¯p</msub > = +,

p > 1);
there are three cases in this situation:

ql</msub > = qu</msub > = 1,
i.e.,

Q-order

1(see Example 3.6 ),

1 = ql</msub > < qu</msub > < +,
resp.

1 = ql</msub >,

qu</msub > = +(see Example 2.14 b), formula (24)).

It is worth noting that one may also obtain

ql</msub > = 1,

qu</msub > = +in lack of

Q-superlinear
(and even linear) convergence, shown in Example 2.14 d), formula (25)), as

Q¯1</msub > = +.


Remark 2.11
Returning to the comments from Remark 2.6 ,
we note that the comparison of the convergence of two sequences

{xk</msub >},

{yk</msub >}having
errors

{ek</msubsup >}resp.

{ek</msubsup >}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

{xk</msub >}converges
faster than

{yk</msub >}if (see, e.g., [18]):

lim k</munder >ek</msubsup >ek</msubsup > = 0(also denoted by ek</msubsup > = o(e
k
</msubsup >), as  k ).

(18)

Now we see that this definition makes sense not only if the

Q-orders
of the two sequences are different, but even if they are equal, as the above
condition is norm-independent.

To show this, we consider the terminology proposed by Jay [27] for a sequence converging
with

Q-order

p0</msub > > 1, who
defined that the convergence is with:


  • Q-suborder

    p0</msub >if

    Q¯p0</msub ></msub > = ,


  • Q-superorder

    p0</msub >if

    Q¯p0</msub ></msub > = 0.

The last terminology is in fact widely used – recall the superquadratic convergence
(for

Q¯2</msub > = 0),
supercubic, etc.).

Now we see that for sequences with

Q-order

p0</msub > > 1we
can briefly say that:


  • Q-superconvergence
    is faster than exact

    Q-convergence
    (in the sense of (4) or (6));

  • exact
    Q-convergence
    is faster than

    Q-subconvergence;

  • (consequently)
    Q-superconvergence
    is faster than

    Q-subconvergence.

This can be illustrated by the following sequences having

Q-order

2:

{2k2k</msup ></msup >}(

Q-superquadratic),

{22k</msup ></msup >}(exact

Q-order

2),

{22k</msup >k</msup >}(

Q-subquadratic).

2.1.2 Computational convergence orders, based on the corrections xk+1-xk
and the nonlinear residuals F(xk)

We consider now some quantities which do not require the limit

x</msup >,
for which we adopt the terminology computational convergence
orders
. As some of them require the knowledge of the order

p0</msub >itself,
we keep in mind that perhaps a more proper terminology for those would be
semi-computational.

As a notation, for the corresponding convergence orders
based on corrections we shall add a prime mark (e.g.,

C</msup >) as in
[20], while for those based on nonlinear residuals, two prime marks (e.g.,

C</msup >).

Corrections.

We introduce another notation, for the corrections (including their norms
too):

sk</msub > = xk+1</msub > xk</msub >.

In 1974 Dennis and Moré [5] obtained a result which shows that if a sequence converges

Q-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

Q-superlinearly iff the corrections
converge

Q-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

log sk</msub > sk+1</msub > log sk−1</msub > sk</msub > ,

(19)

equivalent to

QΛ</msubsup >defined below.

Three years later, Brezinski [26] proposed the use of the corrections

xk+1</msub > xk</msub >instead of the
(unknown) errors

x</msup > xk</msub >in the definitions of the convergence orders studied there
(

QL</msub >,QΛ</msub >and exact

Q-order).

In 1990, Beyer, Ebanks and Qualls [20], taking the same approach, considered

Qp0</msub ></msubsup > (k) := sk+1</msub >skp0</msub ></msubsup >

with the resulted definitions being denoted correspondingly by

C</msup >,Q</msup >,QL</msubsup >and

QΛ</msubsup >; we use here the same
convention for denoting

Q</msubsup >,QI,</msubsup >.
These authors proved the following fundamental results: for

p0</msub > > 1, 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:

{Cp0</msub ></msub >,Cp0</msub ></msubsup >} {Q,QL</msub >,QΛ</msub >,Q</msup >,Q
L
</msubsup >,Q
Λ
</msubsup >
}.

However, the considered assumptions were very strong when proving

{Cp0</msub ></msub >,Cp0</msub ></msubsup >}and

Q</msup > Q”:

{xk</msub >}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, Grau-Sánchez, Noguera and Gutiérrez [48], while studying connections
between

QΛ</msub >– and

QΛ</msubsup >-orders (in the case
of a sequence from

with

C-order

p)
considered the ”extrapolated convergence order”

ln |xk+1</msub >−α~k+1</msub >| |xk</msub >−α~k</msub >| ln |xk</msub >−α~k</msub >| |xk−1</msub >−α~k−1</msub >|,

(20)

where

α~k</msub > = xk</msub > (Δxk1</msub >)2</msup >Δ2</msup >xk2</msub > ,

k 2,

Δxk</msub > = xk+1</msub > xk</msub >. This convergence order
was obtained from

QΛ</msub >by replacing the unknown limit with an extrapolation

α~k</msub >given by
the Aitken

Δ2</msup >method (in order to use only the terms known at the step

k).
However, this convergence order is valid only in the one dimensional case, since the
Aitken

Δ2</msup >acceleration process does not have a direct extension to

n</msup >.

We do not pursue this definition as, for high convergence orders, it is equivalent
to

QΛ</msubsup >.

In 2012, Grau-Sánchez, Noguera, Grau and Herrero [49] considered another
extrapolated convergence order

ln |xk</msub >−α~k</msub >| ln |xk−1</msub >−α~k−1</msub >|,

(21)

for a sequence from

,
having

C-order

p. Assuming

C-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

{ek</msub >},

{sk</msub >}and

{f(xk</msub >)}for
sequences

{xk</msub >}from

.
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

C</msup >-,

Q</msubsup >-,

QI,</msubsup >-orders
are semi-computational orders, as they require the (supposed) unknown order,
while the logarithm-based

QL</msubsup >
and

QΛ</msubsup >-orders
are (fully) computational orders, i.e., they require neither the limit

x</msup >nor the order

pin their expressions.

As certain numerical experiments (see [50] and the references therein)
have not revealed a clear superiority of

QΛ</msubsup >over

QL</msubsup >,
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

ql</msub > = ql</msubsup > = Q L</msub >and

qu</msub > = qu</msubsup > = Q¯L</msub >.

Nonlinear residuals.

Other computational convergence orders were considered
in the context of solving nonlinear systems of equations

F(x) = 0,

F : n</msup > n</msup >, with solution

x</msup >. For simplicity,
we shall denote

Fk</msub > := F(xk</msub >)(resp.

fk</msub >when

n = 1).

In 1981, Păvăloiu [51] defined the exact convergence order

p0</msub > > 1corresponding to (4) by

AFk</msub >p0</msub ></msup > Fk+1</msub > BFk</msub >p0</msub >
</msup >,k 0,

while in 1995, he introduced in [52] the expression

ln|fk+1</msub >| ln|fk</msub >|

(22)

and shown its equivalence to

QL</msubsup >.
Also, while extending his results from 1999 [53], he introduced in an unpublished
manuscript [54] (posted on his website) the measure

ln|fk+1</msub >∕fk</msub >| ln|fk</msub >∕fk−1</msub >|

(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 R-convergence orders.

The root convergence order (

R-order)
requires weaker conditions than the

C
and

Q-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

Q– and

R-convergence is […]
essentially sacred to workers in the area of computational optimization” [13, p. 49], meaning
that the

R-order
is a much less powerful notion.

In Example 3.11 is presented a sequence for which, depending on the parameters, the
lower

Q-order

ql</msub >is arbitrary close to

1from above, while
the (exact)

R-order
is arbitrary high (and even higher is the upper

Q-order

qu</msub >).

We shall review certain results, but not treat all of them in the same detail as we
will for the

C
and

Q-orders.

In 1970, Ortega and Rheinboldt [4, 9.2] introduced and
studied the root convergence factors, which we denote here by

R¯p</msub > {xk</msub >}:

R¯p</msub > {xk</msub >} = { limsup k</munder >(ek</msub >)1
k
</msup >, ifp = 1,

limsup k</munder >(ek</msub >) 1
pk</msup >
</msup >, ifp > 1.

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

1takes
the role of

+ for

Q¯p</msub >.


Proposition 2.13
[4, 9.2.3] Exactly one of the following conditions holds:

a)

R¯p</msub > = 0,p [1,+);b)

R¯p</msub > = 1,p [1,+);c)

p0</msub > [1,+)s.t.  

R¯p</msub > = 0,

p [1,p0</msub >)and

R¯p</msub > = 1,

p (p0</msub >,+).

The lower

R-order,
which we denote here by

rl</msub >(instead of

OR</msub > {xk</msub >}in [4, 9.2]), defined by

rl</msub > = { ,   if  R¯p</msub > = 0,p 1,
inf {p [1,) : R¯p</msub > = 1 },

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

p0</msub >with

R¯p0</msub ></msub > < 1,then for
any

> 0with

R¯p0</msub ></msub > + < 1,there
exists a

k0</msub > 0such that either

ek</msub > (R¯p0</msub ></msub > + )k</msup >,k k0</msub >, ifp0</msub > = 1,

or

ek</msub > (R¯p0</msub ></msub > + )p0k</msubsup ></msup >,k k0</msub >, ifp0</msub > > 1.

b) The value

rl</msub >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]):

ek+1</msub > Aek</msub > ek1</msub >

and they yield the well-known

rl</msub >-order

(1 + 5)2 1.6.
It is important to note that the secant method then attains the same value
also for the lower

Q-order

ql</msub >(see [3], [9]).

For the more general inequalities

ek+1</msub > Ai=0m</munderover >(eki</msub >)αi</msub ></msup >,k m,ck</msub >,αk</msub > 0,

Schmidt [42], Burmeister and Schmidt [55], [56] resp. Potra and Pták
[8, p. 107] determined in a series of works the lower

R-order

rl</msub >.

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

ql</msub >. Potra
[19] has also noted that the above inequalities do not necessarily attract lower

order

ql</msub >greater than one: take

ek+1</msub > = { (ek</msub >)k</msup >, k > 1is a power of 2,ek</msub >ek1</msub >,otherwise,

(24)

with

e0</msub > = e1</msub > = 12. This sequence
satisfies

ek+1</msub > ek</msub >ek1</msub >(which
immediately attracts

Q¯1</msub > = 0and

rl</msub > (1 + 5)2), but
in fact

Q¯p</msub > = +,

p > 1(and

qu</msub > = Q¯L</msub > = +, as
we shall see).

Certain iterative methods have lead to some different inequalities, of the type
[4, Th. 9.2.9.]

ek+1</msub > ek</msub >j=0m</munderover >γ
j
</msub >ekj</msub >,k m, with γ1</msub >,...,γm</msub > 0,

or of other types, analyzed in [23] (see also [58]).

c) As noted in [4, N.R. 9.2.1], the

R¯1</msub >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

R-order

rl</msub >is consistent with the natural ordering of sequences, while the lower

Q-order

ql</msub >is not:
given

{xk</msub >},{yk</msub >}with
errors

{ek</msubsup >},
resp.

{ek</msubsup >}, if

ek</msubsup > ek</msubsup >and

{yk</msub >}has

rl</msub >order

p0</msub >then so
has

{xk</msub >};
however, this statement does not hold for the lower

Q-order

ql</msub >, as one may take

{xk</msub >}from Example
2.7 and

yk</msub > = 22k</msup ></msup >.
A more disturbing example was given by Jay [27], for

yk</msub > = 22k</msup ></msup >and

xk</msub > = { 22k</msup ></msup >,keven,23k</msup >
</msup >,
kodd.

(25)

At the first sight, since

ek</msubsup > ek</msubsup >,
the speed of

{xk</msub >}seems higher
than of the (exact)

Q-quadratic

{yk</msub >}, but though,

{xk</msub >}does not attain even

Q-linear convergence, as

Q¯1</msub > = (we shall see that in this
case the upper

Q-order
is

qu</msub > = Q¯Λ</msub > = ).
Another example was given in (24) above.

In 1973, Brent, Winograd and Wolfe [37] considered the following expressions,
which we denote here by

R L</msub > := liminf k</munder > |ln ek</msub > |1
k
</msup >,
(26)
R¯L</msub > := limsup k</munder > |ln ek</msub > |1
k
</msup >

(in [32] Brent considered in the same year only

R L</msub >). The sequence was said
that converges with

RL</msub >-order

p0</msub > > 1if

R L</msub > = R¯L</msub > = p0</msub >, i.e.,
in a single condition,

lim k</munder > |ln ek</msub > |</msup >1k =p˙0. (27)

They noted that the

C-order

p0</msub > > 1easily implies

RL</msub >-order

p0</msub >.

In 1979, Schwetlick [25] considered the upper

R-order

R p</msub > {xk</msub >} = { liminf k</munder >(ek</msub >)1
k
</msup >,
 ifp = 1,
liminf k</munder >(ek</msub >) 1
pk</msup >
</msup >,
 ifp > 1,

and (in the notations of this paper)

ru</msub > = { ,   if   R p</msub > = 0,p 1,
sup {p [1,) : R p</msub > = 0 },

he defined the convergence with

R-order

p0</msub >if

p0</msub > = rl</msub > = ru</msub >.Similarly to the case of the

Q-order,
the sequence is said that converges

R-superlinearly
if

lim k</munder >(ek</msub >)1k </msup > = R¯1</msub > = 0.


Remark 2.15
Analogously to Remark 2.14 , whenever exists a

p0</msub >with

R p0</msub ></msub > > 0,then for
any

> 0with

0 < R p0</msub ></msub > ,there
is a

k0</msub > 0such that either

( R p0</msub ></msub > )k</msup > e
k
</msub >,k k0</msub >, ifp0</msub > = 1,

or

( R p0</msub ></msub > )p0k</msubsup >
</msup > ek</msub >,k k0</msub >, ifp0</msub > > 1.

In 1989, Potra [19] has introduced and studied some further measures for the

R-convergence order,
which we denote here by

R</msub >,
resp.

RI,</msub >:


  • {xk</msub >}converges
    with

    R</msub >-order

    p0</msub > > 1if

    lim k</munder >(ek</msub >) 1
    (p0</msub >)k</msup >
    </msup >
    = 0, > 0,
    lim k</munder >(ek</msub >) 1
    (p0</msub >+)k</msup >
    </msup >
    = 1, > 0;


  • {xk</msub >}converges
    with

    RI,</msub >-order

    p0</msub > > 1if

    > 0, a,b > 0and

    0 < η, < 1such that

    aη (p0</msub >+)k</msup ></msup > ek</msub > b (p0</msub >)k</msup >
    </msup >,k 0.

The exact

R-order
of convergence was also defined here – analogously to the definition of the exact

Q-order (4)
– as being

p0</msub > > 1if

A,B > 0,

0 < η, < 1such
that

A η(p0</msub >)k</msup ></msup > ek</msub > B (p0</msub >)k</msup >
</msup >,k 0;

(28)

we see that this definition can be immediately connected to the following one,
analogous to (6):

0 < R p0</msub ></msub > < R¯p0</msub ></msub > < .

(29)

Potra has also considered the lower and upper

R-orders, when noting that if
a sequence has exact

R-order

p0</msub >then

rl</msub > = ru</msub > = p0</msub >.

Comparing the list of

Q
and

R-orders, the
definition of

RΛ</msub >was not given before, so we consider it here, by denoting the expressions

R Λ</msub > := liminf k</munder > |ln ek+1</msub >
ek</msub >
|1
k
</msup >,R¯Λ</msub > := limsup k</munder > |ln ek+1</msub >
ek</msub >
|1
k
</msup >

and by defining the

RΛ</msub >-order

p0</msub > 1when

R Λ</msub > = R¯Λ</msub > = p0</msub >, i.e.,
when

lim k</munder > |ln ek+1</msub >ek</msub > |1
k
</msup > = p0</msub >.

(30)

3 Results relating the high (computational) convergence orders

In this section we consider

p > 1and present the relationships of different definitions of the
(computational) convergence orders, with full proofs in the case of the

C– and

Q-orders.

3.1 Relationships between the convergence orders

The equivalences and implications mentioned in the previous section can be
summarized as:

{Q</msub >,QI,</msub >,QL</msub >} {R</msub >,RI,</msub >,RL</msub >} , [19],
Cp0</msub ></msub > {Q,QL</msub >,QΛ</msub >} , [20].
At this point we can simply merge the equivalences from the two statements
above and write the conclusion.

However, as we intend to provide a self-contained
material, we include the proofs of the equivalence of the

Q-orders,
some of them much simplified.

3.1.1 C- and Q-convergence orders

We shall need the three auxiliary results below.


Lemma 3.1
[20, lemma 2.1]

(i)
If

Q¯p</msub > < ,then

Qs</msub > (k) 0for all

s < p,
and so

p ql</msub >;

(ii)
if

Q p</msub > > 0,then

Qs</msub > (k) for all

p < sand so

qu</msub > p;

(iii)
if

p < ql</msub >,then

Qp</msub > (k) 0;

(iv)
if

qu</msub > < p,then

Qp</msub > (k) .

Relations (iii) and (iv) show that

ql</msub > qu</msub >and justify the terminology ”lower” and ”upper”.

Proof. [20] For (i), if

Q¯p</msub > < and

s < p,then

Qs</msub >(k) = ek+1</msub >eks</msubsup > = ekps</msubsup >Q
p
</msub >(k) 0,as k .

For (iii), suppose

p < ql</msub >and choose

s (p,ql</msub >) .By
definition of

ql</msub >,then,

Q¯s</msub > < . Now,
by (i),

Qp</msub > (k) 0.The other statements are proved in a similar manner.  _


Remark 3.2
Ortega and Rheinboldt have previously obtained (i) and (ii)
in [4, 9.1], see Proposition 2.5 .

Potra obtained the following general result, interesting in its own, which will
help us relating some quantities to their corresponding computational
versions.


Proposition 3.3
[19, Prop. 1.1] The following relations hold:

Q L</msub > := liminf k</munder >ln ek+1</msub > ln ek</msub > = ql</msub >

(31)

and

Q¯L</msub > := limsup k</munder >ln ek+1</msub >
ln ek</msub >
= qu</msub >.

Proof. [19] Let

1 < Q L</msub > = p0</msub >.

Then for any

> 0with

p0</msub > > 1, there
exists

k0</msub >such that

ln ek+1</msub >
ln ek</msub > > p0</msub > ,k k0</msub >.

We may assume that

ln ek</msub > < 0,
and we obtain

ln ek+1</msub > < (p0</msub > )ln ek</msub >,k k0</msub >,

so that

ek+1</msub > < ekp0</msub ></msubsup >,k k0</msub >.

This proves that

Q¯p0</msub ></msub > 1 < and, by Lemma 3.1 (i), we get

p0</msub > ql</msub >.

Suppose that

p0</msub > < s < ql</msub >.

It follows by Lemma 3.1 (iii) that

Qs</msub > (k) 0,so there
is

c > 0such
that

Qs</msub > (k) c,

k 0,i.e.,

ek+1</msub > ceks</msubsup >,k 0.

But then

ln ek+1</msub > ln c + sln ek</msub >,

which leads to

liminf k</munder >ln ek+1</msub >ln ek</msub > s + lim k</munder > ln c
ln ek</msub >
= s > p0</msub >,

which is a contradiction. Hence, we have proved that

Q L</msub > = ql</msub >.Analogously,

Q¯L</msub > = p1</msub >implies

p1</msub > = qu</msub >. _


Lemma 3.4
[20, lemma 3.3] If

lim inf QΛ</msub > (k) > 0,

then

{ek</msub >}is monotone decreasing starting from a step

k k0</msub >.

Proof. [20] For some some

> 0sufficiently small,

k0</msub > 0such that

QΛ</msub >(k) > ,

k k0</msub >.Hence, the
numbers

ln ek+1</msub >ek</msub >all have
the same sign

k k0</msub >.
If they were positive, then we would have

ek+1</msub > > ek</msub >, contradictory to the
convergence of

{xk</msub >}.Therefore,
they are all negative and

ek+1</msub > < ek</msub >. _

We present now the result relating the

C– and

Q-orders,
and we choose to incorporate Proposition 3.3 .


Theorem 3.5
(cf. [19], [20]) Consider a given norm

in

n</msup >and a convergent
sequence

{xk</msub >}to
some

x</msup > n</msup >. Then,
given some

p0</msub > > 1,
in the above notations we have:

Cp0</msub ></msub > {Q,Q</msub >,QI,</msub >,QL</msub >,QΛ</msub >} .

(32)

Moreover,

Q L</msub > = ql</msub >and Q¯L</msub > = qu</msub >.

(33)

Proof. We give the proof in five steps: A.

Cp0</msub ></msub > QL</msub >, B.

Q Q</msub >, C.

Q</msub > QI,</msub >, D.

Q QL</msub >and
E.

QΛ</msub > QL</msub >A1 (

Cp0</msub ></msub > QL</msub >).
The simplest approach is (also mentioned in [37]) to take logarithms in (2). The
proof in [20] used an approach similar to Lemma 3.1 .

A2 (

QL</msub > Cp0</msub ></msub >)
[20] Consider any of the sequences from Example 2.8 .

B. The relation is obvious.

C1 (

Q</msub > QI,</msub >)
Let

> 0such
that

p0</msub > > 1.Since

Qp</msub > 0, it follows
that exists

bsuch that

Qp0</msub ></msub > b,

k 0,i.e., the second inequality
in the definition of

QI,</msub >.The first inequality is obtained in the same way.

C2 (

QI,</msub > Q</msub >) Suppose
for some

p0</msub > > 1and

> 0with

p0</msub > > 1we have

a(ek</msub >)p0</msub >+</msup > ek+1</msub > b(ek</msub >)p0</msub ></msup >,k 0.

The second inequality implies

Q¯p0</msub ></msub > b < ,and by Lemma 3.1 (i),

lim Qq</msub > (k) = 0,qs.t.

1 < q < p0</msub > .The first inequality (valid for all

> 0)
implies

Q p0</msub >+</msub > a > 0and again
by Lemma 3.1 (ii),

lim Qs</msub > (k) = +,swith

p + < s.The assertion follows since

can be taken arbitrarily small.

D. [19, Prop. 1.1] Using the above result, we get

QL</msub > Q¯L</msub > = Q L</msub > = p0</msub > ql</msub > = qu</msub > = p0</msub > Qand
vice versa.

E1 (

QΛ</msub > QL</msub >)
[20] We notice that, by B and D, we have that

QL</msub > Q</msub >, so it suffices
to show that

QΛ</msub > Q</msub >.

Let

QΛ</msub >(k) p0</msub > > 1.For any

> 0,we have

QΛ</msub >(k) < p0</msub > + for all

ksufficiently large, and using Lemma 3.4 we get

ln ek+2</msub >ek+1</msub > > (p0</msub > + )ln ek+1</msub >
ek</msub >
,

which gives

ek+2</msub >
(ek+1</msub >)p0</msub >+</msup > > ek+1</msub >
(ek</msub >)p0</msub >+</msup >
,

i.e.,

Qp0</msub >+</msub > (k + 1) > Qp0</msub >+</msub > (k),

k k0</msub >.Considering now

2instead of

,we obtain similarly that

Qp0</msub >+2 </msub > (k + 1) > Qp0</msub >+
2
</msub > (k),k k1</msub >.

(34)

We prove that the monotone sequence

{Qp0</msub >+</msub > (k)}is
unbounded:

Qp0</msub >+</msub > (k) .Otherwise, if

M > 0s.t.

ek+2</msub >(ek+1</msub >)p0</msub >+</msup > < M,for
all

k,i.e.,

Q¯p0</msub >+</msub > < M,then according to Lemma
3.1 (i), this implies

Q¯p0</msub >+2 </msub > = 0in contradiction to the monotony from (34 ).

Similarly, one can prove that for any

> 0with

p0</msub > > 1,we have

QΛ</msub > (k) > p0</msub > for all

ksufficiently large
and we get

Qp0</msub ></msub > (k) 0.E2 (

QL</msub > QΛ</msub >) [20]
Assuming

QL</msub >(k) p0</msub > > 1,we have

lim k</munder >QΛ</msub >(k) = lim k</munder >QL</msub > (k) QL</msub > (k+1)1QL</msub > (k)1 = p0</msub >p0</msub >1
p0</msub >1
= p0</msub >.

_

It is interesting to notice that

Q-convergence with
order

p0</msub > > 1implies

Q¯1</msub > = 0.However, the reverse is not true
(i.e.,

Q-superlinear convergence
does not imply

Q-convergence
with order

p0</msub > > 1),
as the following examples show.


Example 3.6
a) [4, E 10.1.4] (we follow here [8, p. 94]) Let

0 < c < 1eand
consider the sequence

xk+1</msub > = xk</msub >ln xk</msub >,k 0,x0</msub > = c,

which converges superlinearly to

0.Suppose there exists

p0</msub > > 1such that

{xk</msub >}converges
with

Q-order (and
therefore with

QI,</msub >order)

p0</msub >.Then

> 0with

p0</msub > > 1,b > 0s.t.

xk+1</msub > bxkp0</msub ></msubsup >.Hence,

xk</msub >ln xk</msub > bxkp0</msub ></msubsup >or ( 1
xk</msub >
)p0</msub >1</msup >

ln 1
xk</msub >
b,

for all

ksufficiently large, which contradicts the well known limit

lim t</munder > tα</msup >ln t = ,
for any

α > 0.
As

QL</msub >(k) 1,
we get

ql</msub > = qu</msub > = 1.

b) Some simpler examples can be found either as explicitly given by

xk</msub > = kk</msup >[32, p. 22],

xk</msub > = 10k2</msup ></msup >[26], [20],

xk</msub > = 1k![27], or in the list of exercises, by

xk</msub > = ck2</msup ></msup >,

c > 1[4, E.9.2.1.j]. To show these assertions we can also use that

QL</msub >(k)or

QΛ</msub >(k) 1.
Expression (24) of Potra gives yet another example.


Remark 3.7
We notice that the orders

Q</msub >,QI,</msub >,QL</msub >,QΛ</msub >do not have elements to define the strict

Q-superlinear
convergence, when

Q¯1</msub > = 0and

Q¯p</msub > = +,

p > 1.

The

Q-superlinear
convergence implies

R-superlinear
convergence, as in any norm [4, 9.3.1]

R¯1</msub > Q¯1</msub >.

In fact,

R¯1</msub >is a
lower bound for

Q¯1</msub >in all norms from

n</msup >.

It is interesting to see that sequences with infinite

Q-order exist too,
as one can take

xk</msub > = 222k</msup ></msup ></msup >(from the list of exercises in [4, E.9.2.1]).


Remark 3.8
An important aspect we address now is the problem of changing
the norms, as we have seen in Example 2.3 that for a given sequence in

n</msup >the existence of the

C-order
is norm-dependent. Ortega and Rheinboldt [4, 9.1.6] proved that the three
relations

Q¯p</msub > = 0,

Q¯p</msub >finite,

Q¯p</msub > = are norm-independent. The same hold for

Q p</msub >,
as one can easily verify (using also Lemma 3.1 ), which shows the norm-independence
of the

Q-order.
By the equivalence from Theorem 3.5 , we conclude that the rest of the

Q-orders
are norm independent too. This assertion will be further completed by the
computational convergence orders, as we shall see in the following subsection.

It is important to recall that for sequences with

Q-order

p0</msub > > 1,

while this

Q-order
is norm-independent, the values of the quantities

Q¯p0</msub ></msub >and

Q p0</msub ></msub >however, if finite, are norm-dependent [4, E.9.1-1].


Remark 3.9
One can easily show that the sequence

{xk</msub >}converges with

Q-order

p0</msub > > 1iff one of the the following sequences converges with the same order:

{ek+1</msub >ek</msub > },

{ek+1</msub > ek</msub >}or

{(ek</msub >)α</msup >}(

α > 0arbitrary, given).

3.1.2 R-convergence orders

In 1972, Brent [32] stated, while in 1984, Potra and Pták [8] shown
that

rl</msub > =