Abstract
The strict superlinear order (superlinear convergence) was usually regarded as having an intermediate speed between between linear and with order \(p>1\).
In this paper we analyze the superlinear convergence (superlinear order/rate) of sequences and we show that actually there are four distinct classes of strict superlinear order: “weak”, “medium”, “strong” and “mixed”. The speed of the sequences from the first three classes is increasingly much faster, termbyterm big Oh, i.e.,
\[x^\astx_k=\mathcal{O}(y^\asty_k^{\alpha}), \mbox{ as } k\rightarrow \infty, \forall \alpha>1 \mbox{ given},
\]whereas the speed of the “mixed” class cannot be assessed.
We prove that the speed of the sequences from the “medium” and “weak” classes is termbyterm slower than the speed of the sequences with high classical Corders \(p>1\) (in the sense of big Oh above), while an example shows that certain sequences from the “mixed” class may be termbyterm faster than some sequences with infinite Corder.
We also show that for a given sequence with strict superlinear convergence, one can evaluate numerically to which class it belongs.
Some recent results of Rodomanov and Nesterov (Math. Program., 2022), resp. Ye et al. (Math. Program., 2023) show that certain classical quasiNewton methods (DFP, BFGS and SR1) belong to the “weak” class.
Authors
Emil Cătinaş
“Tiberiu Popoviciu” Institute of Numerical Analysis
Keywords
convergent sequence, convergence order, convergence speed, superlinear order, Qorder, convergence rate, big Oh, quasiNewton method, DFP, BFGS, SR1.
Paper coordinates
E. Cătinaş, The strict superlinear order can be faster than the infinite order, Numer. Algor., (2023). https://doi.org/10.1007/s1107502301604y
About this paper
Journal
Numerical Algorithms
Publisher Name
Springer Nature
Print ISSN
10171398
Online ISSN
15729265
google scholar link
The strict superlinear order
can be faster than the infinite order
Abstract
The sequences with strict superlinear convergence are the output of numerous algorithms; such speed is clearly much faster than linear, but is it also slower than, say, quadratic?
In this note we show that actually there are four distinct classes of strict superlinear order: “weak”, “medium”, “strong” and “mixed”. The speed of the sequences from the first three classes is increasingly much faster (termbyterm big Oh, i.e., ${x}^{\ast}{x}_{k}=\mathcal{O}({{y}^{\ast}{y}_{k}}^{\alpha})$, as $k\to \mathrm{\infty},\forall \alpha >1$ given), whereas the speed of the “mixed” class cannot be assessed.
We prove that the speed of the sequences from the “medium” and “weak” classes is termbyterm slower than the speed of the sequences with high classical $C$orders $p>1$ (in the sense of big Oh above), while an example shows that certain sequences from the “mixed” class may be termbyterm faster than some sequences with infinite $C$order.
We also show that for a given sequence with strict superlinear convergence, one can evaluate numerically to which class it belongs.
Some recent results of Rodomanov and Nesterov (2022), resp. Qi et al. (2023) show that certain classical quasiNewton methods (DFP, BFGS and SR1) belong to the “weak” class.
Keywords: convergent sequence, convergence order, convergence speed, superlinear order, $Q$order, convergence rate, big Oh, quasiNewton method, DFP, BFGS, SR1.
MSC: 40A05.
1 Introduction
We consider here real sequences $\{{x}_{k}\}$ converging to finite limits, ${x}_{k}\to {x}^{\ast}\in \mathbb{R}$ and, since we analyze the behavior of the absolute value of their errors, we assume without loss of generality that ${x}^{\ast}=0$ and ${x}_{k}>0$ (i.e., ${x}_{k}={x}^{\ast}{x}_{k}$). A more general frame may be considered (normed or metric spaces), but the onedimensional setting is enough to analyze some essential properties.
First we recall some definitions and notations regarding orders other than superlinear. The quotient convergence factors are defined by [12, sect. 9.1]
$${Q}_{p}(k):=\frac{{x}^{\ast}{x}_{k+1}}{{{x}^{\ast}{x}_{k}}^{p}}=\frac{{x}_{k+1}}{{({x}_{k})}^{p}},k=0,1,\mathrm{\dots},(p\ge 1),$$ 
with their lower/upper limits given by $\text{stackunder}[1.2pt]Q{\text{}}_{p}=\underset{k\to \mathrm{\infty}}{lim\; inf}{Q}_{p}(k)$, resp. ${\overline{Q}}_{p}=\underset{k\to \mathrm{\infty}}{lim\; sup}{Q}_{p}(k)$ [1].
The sequence $\{{x}_{k}\}$ has $C$order ${p}_{0}>1$ if ${Q}_{{p}_{0}}:={lim}_{k\to \mathrm{\infty}}{Q}_{{p}_{0}}(k)\in (0,+\mathrm{\infty})$ (i.e., ${Q}_{{p}_{0}}$ exists and is finite and nonzero), the linear $C$order is attained when ${Q}_{1}:={lim}_{k\to \mathrm{\infty}}{Q}_{1}(k)\in (0,1)$, while the sublinear $C$order requires ${Q}_{1}=1$.
For the $Q$order ${p}_{0}>1$ there are four equivalent definitions (see [5], [15], [1], [7], [10]), but we consider here only two convenient ones
$\underset{k\to \mathrm{\infty}}{lim}{Q}_{L}(k)$  $={p}_{0},\text{with}{Q}_{L}(k):={\displaystyle \frac{\mathrm{ln}{x}_{k+1}}{\mathrm{ln}{x}_{k}}},k\ge 0,$  (${Q}_{L}$)  
$\underset{k\to \mathrm{\infty}}{lim}{Q}_{\mathrm{\Lambda}}(k)$  $={p}_{0},\text{with}{Q}_{\mathrm{\Lambda}}(k):={\displaystyle \frac{\mathrm{ln}\frac{{x}_{k+2}}{{x}_{k+1}}}{\mathrm{ln}\frac{{x}_{k+1}}{{x}_{k}}}},k\ge 0.$  (${Q}_{\mathrm{\Lambda}}$) 
The lower/upper $Q$orders, denoted by ${q}_{l}$ resp. ${q}_{u}$, are (see [1], [7] and [10])
$${q}_{l}=inf\{p\in [1,\mathrm{\infty}):{\overline{Q}}_{p}=+\mathrm{\infty}\},\text{resp.,}{q}_{u}=sup\{p\in [1,\mathrm{\infty}):\text{stackunder}[1.2pt]Q{\text{}}_{p}=0\},$$ 
and it holds:

•
${q}_{l}=lim\; inf{Q}_{L}(k)$, ${q}_{u}=lim\; sup{Q}_{L}(k)$ (retrieving ${q}_{l}\le {q}_{u}$ in another way),

•
(${Q}_{L}$)$\iff $(${Q}_{\mathrm{\Lambda}}$)$\iff {p}_{0}={q}_{l}={q}_{u}>1$,
the condition ${p}_{0}={q}_{l}={q}_{u}>1$ providing the third equivalent definition of the $Q$order ${p}_{0}>1$. When ${p}_{0}=1$, the four definitions are no longer equivalent, as shown in [1].
Remark 1
${Q}_{1}\in [0,1]$, when the limit exists (i.e., ${Q}_{1}>1$ cannot hold). When $\mathrm{\nexists}{Q}_{1}$ (and therefore $$) the “global speed” of $\{{x}_{k}\}$ may be difficult to assess.
The sequences with ${\overline{Q}}_{1}=\mathrm{\infty}$, called in [10] “with unbounded nonmonotone errors”^{3}^{3}3Recall that one cannot have ${Q}_{1}=+\mathrm{\infty}$ (as suggested by a typo in the abstract of [10]), but just ${\overline{Q}}_{1}=+\mathrm{\infty}$. despite not attaining $Q$linear order, were shown that sometimes may have fast speed, as, e.g., ${x}_{k}=\{\begin{array}{cc}{2}^{{4}^{k}},& k\mathrm{\mathit{e}\mathit{v}\mathit{e}\mathit{n}},\\ {2}^{{5}^{k}},& k\mathrm{\mathit{o}\mathit{d}\mathit{d}}\end{array}$ ${y}_{k}=\{\begin{array}{cc}{2}^{{3}^{{2}^{k}}},& k\mathrm{\mathit{e}\mathit{v}\mathit{e}\mathit{n}},\\ {2}^{{4}^{{2}^{k}}},& k\mathrm{\mathit{o}\mathit{d}\mathit{d}}\end{array}$ (see [10, Ex. 2.46]). Such sequences were also called subsequently there “with no $Q$order” [10, §2.2] but we notice here that such terminology is not suitable: ${z}_{k}=\{\begin{array}{c}\frac{1}{k},k\text{even}\\ \frac{1}{k\mathrm{ln}k},k\text{odd}\end{array}$ shows that one may have ${\overline{Q}}_{1}=\mathrm{\infty}$ and (${Q}_{L}$)order one.
As regarding the fast speed, it cannot be attained when $\text{stackunder}[1.2pt]Q{\text{}}_{1}0$ (due to the obvious lower bounds of the errors) and one necessarily needs $\text{stackunder}[1.2pt]Q{\text{}}_{1}=0$; however, condition $\text{stackunder}[1.2pt]Q{\text{}}_{1}=0$ alone is not also sufficient for fast speed: take $\{{z}_{k}\}$ above or ${u}_{k}=\{\begin{array}{c}\frac{1}{k},k\text{even}\\ \frac{1}{\sqrt{k}},k\text{odd.}\end{array}$
The $Q$superlinear convergence—which we call here simply as superlinear—requires (see [12, ch. 9], [4], [14], [7], [10])
$$\underset{k\to \mathrm{\infty}}{lim}\frac{{x}_{k+1}}{{x}_{k}}=0$$  (1) 
and it is usually understood as “at least superlinear order”: indeed, all $\{{x}_{k}\}$ with $Q$order ${p}_{0}={q}_{l}={q}_{u}>1$ or just with lower $Q$order ${q}_{l}>1$ are also superlinear (${q}_{l}>1$ implies $\forall p\in (1,{q}_{l}),\exists A>0$ s.t. $$, $k\ge 0$ [12, sect. 9.1], [10] and therefore $$).
Remark 2
There is another type of superlinear speed, the $R$superlinear order, usually defined by using rootconvergence factors (see [12, ch. 9], [14]), or (as for higher orders), simply by requiring that the errors are bounded by another sequence, converging to zero with $Q$superlinear order [19], [13, (37b)].
Tapia [19] noticed that convergence with (lower) $R$order ${p}_{0}$ arbitrary high does not imply $Q$superlinear convergence, while Boggs, Tolle and Wang [3] concluded that “because an $R$superlinearly convergent sequence need not be even $Q$linearly convergent, $R$superlinear convergence by itself is computationally meaningless”. We have seen in the previous Example that the fast sequence $\{{y}_{k}\}$ with $R$superlinear convergence (in fact with infinite $R$order) not only that does not attain some type of $Q$linear order, but even has unbounded nonmonotone errors (${\overline{Q}}_{1}=\mathrm{\infty}$).
The above Example therefore shows that the $Q$superlinear convergence is not necessary for high speed: $\{{y}_{k}\}$ there converges pretty fast despite ${\overline{Q}}_{1}=+\mathrm{\infty}$.
2 The strict superlinear (SSL) convergence
The strict superlinear (SSL) convergence requires additionally that [10]
$${\overline{Q}}_{p}=\underset{k\to \mathrm{\infty}}{lim\; sup}\frac{{x}_{k+1}}{x_{k}^{}{}_{}{}^{p}}=+\mathrm{\infty},\forall p>1,$$  (2) 
i.e., $\{{x}_{k}\}$ does attain neither some $Q$order ${p}_{0}>1$ nor some lower $Q$order ${q}_{l}>1$.
The SSL was usually seen as a fast convergence, with an intermediate speed between the linear and high orders. Indeed, the SSL is (much) faster than the linear $C$order, in the sense that
$${x}_{k}=\mathcal{O}({y}_{k}^{\alpha}),\text{as}k\to \mathrm{\infty}(\forall \alpha 1\text{given}).$$  (${x}_{k}=\mathcal{O}({y}_{k}^{\alpha})$) 
Proposition 3
If $\{{x}_{k}\}$ has SSL order and $\{{y}_{k}\}$ has $C$linear order then $\{{x}_{k}\}$ is $[$(${x}_{k}\mathit{=}\mathcal{O}\mathit{(}{y}_{k}^{\alpha}\mathit{)}$), $\forall \alpha >1]$ faster than $\{{y}_{k}\}$.
For the proof we use here (and later too) the well known ratio test for sequences.
Lemma 4
Given a sequence $\{{z}_{k}\}\subset \mathbb{R}$ with ${z}_{k}>0$ $k\ge 0$, if $\frac{{z}_{k+1}}{{z}_{k}}\to 0$ then ${z}_{k}\to 0$. The same conclusion holds if $\frac{{z}_{k+1}}{{z}_{k}}\to q\in (0,1)$.
However, the SSL convergence is not always slower than that with some $Q$order ${p}_{0}>1$, as we will show in Example 10. Before that, we further analyze the SSL order.
Example 5
The convergence of $\{\frac{1}{k!}\}$ and of $\{\frac{1}{{k}^{k}}\}$ is SSL—with the “strictness” implied by their ${Q}_{\mathrm{\Lambda}}$order one (${Q}_{\mathrm{\Lambda}}(k)\to 1$).
By denoting ${a}_{0}={x}_{0}$, ${a}_{k+1}=\frac{{x}_{k+1}}{{x}_{k}}>0$, $k\ge 0,$^{4}^{4}4When $\{{x}_{k}\}$ is starting from ${x}_{1}$, $\{{a}_{k}\}$ is starting from ${a}_{1}$ (as, e.g., $\{\frac{1}{{k}^{k}}\}$, $\{\frac{1}{k}\}$, etc.). condition (1) may be equivalently written as (see, e.g., [13, (37b)] and [10])
$${x}_{k}=\prod _{i=0}^{k}{a}_{i},\text{with}{a}_{k}\to 0,\text{as}k\to \mathrm{\infty}.$$  (3) 
For the SSL convergence of $\{{x}_{k}\}$, the $Q$order of $\{{a}_{k}\}$ cannot be greater than one.
Theorem 6
Let ${a}_{k}>0$ with ${a}_{k}\to 0$ as $k\to \mathrm{\infty}$. If $\{{a}_{k}\}$ has ${Q}_{L}$order ${p}_{0}=1,$ then $\{{x}_{k}\}$ from (3) has SSL order. If $\{{a}_{k}\}$ has $Q$order ${p}_{0}>1,$ then $\{{x}_{k}\}$ has $Q$order ${p}_{0}.$
Proof. The proof is obtained by using (${Q}_{\mathrm{\Lambda}}$).
Now, consider $\{{a}_{k}\}$, or just simply ask ourselves: how fast does $\{\frac{{x}_{k+1}}{{x}_{k}}\}$ converge to zero? We obtain the following classification of the SSL order:
 (a) (strong SSL)

${a}_{k}\to 0$ strict superlinearly: $\underset{k\to \mathrm{\infty}}{lim}\frac{{a}_{k+1}}{{a}_{k}}=\underset{k\to \mathrm{\infty}}{lim}\frac{{x}_{k+1}{x}_{k1}}{{x}_{k}^{2}}=0;$
 (b) (medium SSL)

${a}_{k}\to 0$ with $C$order $1$: $\underset{k\to \mathrm{\infty}}{lim}\frac{{a}_{k+1}}{{a}_{k}}=\underset{k\to \mathrm{\infty}}{lim}\frac{{x}_{k+1}{x}_{k1}}{{x}_{k}^{2}}=q\in (0,1);$
 (c) (weak SSL)

${a}_{k}\to 0$ $C$sublinearly: $\underset{k\to \mathrm{\infty}}{lim}\frac{{a}_{k+1}}{{a}_{k}}=\underset{k\to \mathrm{\infty}}{lim}\frac{{x}_{k+1}{x}_{k1}}{{x}_{k}^{2}}=1;$
 (d) (mixed SSL)

otherwise.
Remark 7
We note that the weak SSL order may be defined by requiring only that $$ (instead of requiring $C$linear order).
Example 8
One can show that $\{\frac{1}{{2}^{{k}^{2}}}\}$ has medium SSL while $\{\frac{1}{{2}^{{k}^{3}}}\}$ has strong SSL order.
Example 9
$\{\frac{1}{{k}^{k}}\}$ has weak SSL order (hint: ${a}_{k+1}=\frac{1}{k+1}\frac{1}{{(1+\frac{1}{k})}^{k}}\approx \frac{1}{e}\cdot \frac{1}{k+1}$).
Example 10
a) (strong SSL) ${a}_{k}=\frac{1}{k!},$ so ${x}_{k}=\frac{1}{1!2!\cdot \mathrm{\dots}\cdot k!}$; one may take further ${b}_{k}=\frac{1}{1!2!\cdot \mathrm{\dots}\cdot k!}$ and by theorem 6 ${y}_{k}={b}_{1}\mathrm{\dots}{b}_{k}$ is again SSL, etc. For another instance, take ${c}_{k}=\frac{1}{{k}^{k}}$, so ${z}_{k}=\frac{1}{{1}^{1}\cdot {2}^{2}\mathrm{\cdots}{k}^{k}},etc.;$
b) (medium SSL) for $q\in (0,1)$ fixed, take ${a}_{k}={q}^{k},$ so ${x}_{k}={q}^{1}\cdot \mathrm{\dots}\cdot {q}^{k}={q}^{\frac{k\left(k+1\right)}{2}};$
c) (weak SSL) ${a}_{k}=\frac{1}{k}$, so ${x}_{k}=\frac{1}{k!};$
For the mixed class, we may take (similar) sequences from Remark 1 as $\{{a}_{k}\}$.
d) (mixed SSL) ${a}_{k}=\{\begin{array}{c}\frac{1}{{2}^{{2}^{k}}},k\text{even}\\ \frac{1}{{2}^{{3}^{k}}},k\text{odd,}\end{array}$ ${b}_{k}=\{\begin{array}{c}\frac{1}{{2}^{{2}^{{2}^{k}}}},k\text{even}\\ \frac{1}{{2}^{{3}^{{2}^{k}}}},k\text{odd,}\end{array}$ ${c}_{k}=\{\begin{array}{c}\frac{1}{k},k\text{even}\\ \frac{1}{k\mathrm{ln}k},k\text{odd,}\end{array}$ ${d}_{k}=\{\begin{array}{c}\frac{1}{\sqrt{k}},k\text{even}\\ \frac{1}{\left(\mathrm{ln}k\right)\sqrt{k}},k\text{odd,}\end{array}$ etc., resulting the corresponding sequences $\{{x}_{k}\}$, $\{{y}_{k}\}$, $\{{z}_{k}\}$, resp. $\{{u}_{k}\}$.
We notice that $$, $k\ge 1$, i.e., the SSL $\{{y}_{k}\}$ is termbyterm faster than $\{{b}_{k}\}$ (with no $Q$order) which is in turn termbyterm faster than $\{\frac{1}{{2}^{{2}^{{2}^{k}}}}\}$ (with infinite $C$ and $Q$order).
In Figure 1 we have plotted some of these sequences ($k\ge 1$), computed using the Tikz/Pgf LaTeX package [18] (the cases $\{{x}_{k}\}$, $\{{z}_{k}\}$ from (a), $\{{x}_{k}\}$ from (c) and $\{{x}_{k}\}$, $\{{y}_{k}\}$ from (d), were first computed in Julia [2], using BigFloat with setprecision(10^4), and then passed to Tikz/Pgf).
The first values of the fastest sequence (in red), written truncated, are ${x}_{0}=2.5\cdot {10}^{1}$ (not plotted), ${x}_{1}=4.8\cdot {10}^{4}$, ${x}_{2}=7.4\cdot {10}^{9}$, ${x}_{3}=6.5\cdot {10}^{\mathrm{1\hspace{0.17em}984}}$, ${x}_{4}=3.2\cdot {10}^{\mathrm{21\hspace{0.17em}712}}$, and ${x}_{4}$ cannot therefore be plotted, being below the realmin$\approx {10}^{7100}$ from Tikz/Pgf.
The second fastest sequence (violet, with infinite $C$order) has the following iterates ${x}_{0}=2.5\cdot {10}^{1}$ (not plotted), ${x}_{1}=6.2\cdot {10}^{2}$, ${x}_{2}=1.5\cdot {10}^{5}$, ${x}_{3}=8.6\cdot {10}^{78}$, ${x}_{4}=4.9\cdot {10}^{\mathrm{19\hspace{0.17em}729}}$ (not plotted).
The strong SSL $\{\frac{1}{{2}^{{k}^{3}}}\}$ appears close to the quadratic $\{\frac{1}{{2}^{{2}^{k}}}\}$, but their speed is quite different (as also shown by the next Theorem): indeed, at $k=11$, $\{\frac{1}{{2}^{{2}^{k}}}\}$ has approximately the same value as $\{\frac{1}{{2}^{{k}^{3}}}\}$ at $k=16$; one more step of $\{\frac{1}{{2}^{{2}^{k}}}\}$ needs four steps of $\{\frac{1}{{2}^{{k}^{3}}}\}$ to get the same magnitude.
With the scales of Figure 1, the weak SSL of ${x}_{k}=\frac{1}{k!}$ appears only slightly faster than that of the linear $\{\frac{1}{{2}^{k}}\}$, but the conclusions of Proposition 3 hold.
The following result justifies the terminology of strong, medium and weak SSL.
Theorem 11
If $\{{x}_{k}\}$ has strong SSL and $\{{y}_{k}\}$ has medium SSL, then $\{{x}_{k}\}$ is $[$(${x}_{k}\mathit{=}\mathcal{O}\mathit{(}{y}_{k}^{\alpha}\mathit{)}$), $\forall \alpha >1]$ faster than $\{{y}_{k}\}$. The same conclusion holds for $\{{x}_{k}\}$ with medium SSL and $\{{y}_{k}\}$ with weak SSL order.
Proof. Let ${x}_{k}=\prod _{i=0}^{k}{a}_{i},{y}_{k}=\prod _{i=0}^{k}{b}_{i},$ with $lim\frac{{a}_{k+1}}{{a}_{k}}=0$ and $lim\frac{{b}_{k+1}}{{b}_{k}}=q\in (0,1)$.
As $\left(\frac{{x}_{k+1}}{{x}_{k}}/\frac{{x}_{k}}{{x}_{k1}}\right)/{\left(\frac{{y}_{k+1}}{{y}_{k}}/\frac{{y}_{k}}{{y}_{k1}}\right)}^{\alpha}=\frac{{a}_{k+1}}{{a}_{k}}/{\left(\frac{{b}_{k+1}}{{b}_{k}}\right)}^{\alpha}\to 0$, by Lemma 4 we get $\frac{{x}_{k+1}}{{x}_{k}}/{\left(\frac{{y}_{k+1}}{{y}_{k}}\right)}^{\alpha}\to 0$ and therefore $\frac{{x}_{k}}{{y}_{k}^{\alpha}}\to 0$. The second part is similar.
Remark 12
In [10, Rem. 2.50(b)] we noted (without proof) that “the $C$orders (i.e., sublinear, linear, strict superlinear, $$ and infinite) form classes in $[$(${x}_{k}\mathit{=}\mathcal{O}\mathit{(}{y}_{k}^{\alpha}\mathit{)}$), $\forall \alpha >1]$ increasing speed”. However, the SSL order was erroneously mentioned, as it is not a $C$order (its definition requires ${\overline{Q}}_{p}$, as noted in (2)) and moreover such a statement does not hold, as we have already seen in Example 10.
Here we prove that the weak and the medium SSL are (much) slower than the $C$orders $p>1$.
Theorem 13
If $\{{x}_{k}\}$ has $C$order ${p}_{0}>1$ and $\{{y}_{k}\}$ has weak or medium SSL then $\{{x}_{k}\}$ is $[$(${x}_{k}\mathit{=}\mathcal{O}\mathit{(}{y}_{k}^{\alpha}\mathit{)}$), $\forall \alpha >1]$ faster than $\{{y}_{k}\}$.
Proof. Let ${u}_{k}=\frac{{x}_{k}}{{y}_{k}^{\alpha}}$, ${v}_{k}=\frac{{u}_{k+1}}{{u}_{k}}$. As $\frac{{v}_{k+1}}{{v}_{k}}=\frac{{x}_{k+2}}{{x}_{k+1}^{{p}_{0}}}\frac{{x}_{k}^{{p}_{0}}}{{x}_{k+1}}{\left(\frac{{x}_{k+1}}{{x}_{k}}\right)}^{{p}_{0}1}{\left(\frac{{y}_{k+1}^{2}}{{y}_{k}{y}_{k+2}}\right)}^{\alpha}\to 0$, by Lemma 4 we successively get ${v}_{k},{u}_{k}\to 0$.
In some particular cases, the strong SSL is also (much) slower than $C$order $p>1$.
Theorem 14
Let $\{{x}_{k}\}$ have $C$order $p>1$ and $\{{y}_{k}\}$ have strong SSL order: ${b}_{k}=\frac{{a}_{k+1}}{{a}_{k}}\to 0$, ${a}_{k}=\frac{{y}_{k+1}}{{y}_{k}}$. If $\{{b}_{k}\}$ has weak or medium SSL then $\{{x}_{k}\}$ is $[$(${x}_{k}\mathit{=}\mathcal{O}\mathit{(}{y}_{k}^{\alpha}\mathit{)}$), $\forall \alpha >1]$ faster than $\{{y}_{k}\}$.
Proof. The proof is similar to the one of Theorem 13.
For the remaining part of this paper we denote the absolute value of errors by ${x}^{\ast}{x}_{k}$ (instead of simply by ${x}_{k}$).
In case of at least superlinear convergence, it was shown that the absolute value of the errors ${x}^{\ast}{x}_{k}$ and of the corrections ${x}_{k+1}{x}_{k}$ behave asymptotically in the same way (the result also holds in ${\mathbb{R}}^{N}$).
Lemma 15 (Potra–Pták Lemma, [14, Prop. 6.4]; see also [20])
${x}_{k}\to {x}^{\ast}\in \mathbb{R}$ at least $Q$superlinearly iff ${x}_{k+1}{x}_{k}\to 0$ at least $Q$superlinearly.
If $\{{x}_{k}\}$ has (at least) $Q$superlinear convergence, then it holds that (the Dennis–Moré Lemma [11])
$$\underset{k\to \mathrm{\infty}}{lim}\frac{{x}_{k+1}{x}_{k}}{{x}^{\ast}{x}_{k}}=1.$$  (4) 
We obtain the following immediate result, which holds in ${\mathbb{R}}^{N}$ as well.
Corollary 16
Given a sequence $\{{x}_{k}\}\subset \mathbb{R}$ s.t. ${x}_{k}\to {x}^{\ast}\in \mathbb{R}$ with SSL convergence, let ${\alpha}_{k}:=\frac{{x}_{k+2}{x}_{k+1}}{{x}_{k+1}{x}_{k}}$ and take
$$\frac{{\alpha}_{k+1}}{{\alpha}_{k}}=\frac{{x}_{k+2}{x}_{k+1}\cdot {x}_{k}{x}_{k1}}{{{x}_{k+1}{x}_{k}}^{2}}.$$  (5) 

•
If $\frac{{\alpha}_{k+1}}{{\alpha}_{k}}\to 1$ then $\{{x}_{k}\}$ has weak SSL;

•
if $\frac{{\alpha}_{k+1}}{{\alpha}_{k}}\to q\in (0,1)$ then $\{{x}_{k}\}$ has medium SSL;

•
if $\frac{{\alpha}_{k+1}}{{\alpha}_{k}}\to 0$ then $\{{x}_{k}\}$ has strong SSL;

•
if $\{\frac{{\alpha}_{k+1}}{{\alpha}_{k}}\}$ does not converge at all then $\{{x}_{k}\}$ has mixed SSL.
The proof is obvious, as the errors from the expressions $\frac{{a}_{k+1}}{{a}_{k}}=\frac{{x}_{k+1}{x}^{\ast}\cdot {x}_{k1}{x}^{\ast}}{{{x}_{k}{x}^{\ast}}^{2}}$ by (4) may be replaced by corrections.
Example 17
We consider the SSL sequences from Example 10 and for each of them we represent graphically in Figure 2 the expressions (5), using the same corresponding colors as in Figure 1 (here the limit ${x}^{\ast}=0$ is known, but formula (5) does not require its knowledge).
For the same precision as in Example 10 (setprecision(10^4)), we have obtained nonzero results for $k\le 17$; the (truncated) values of $\frac{{\alpha}_{k+1}}{{\alpha}_{k}}$ for $k=17$ are, for the following $\{{x}_{k}\}$’s: $\{\frac{1}{{k}^{k}}\}$ $0.943$ (true limit $1$); $\{\frac{1}{k!}\}$ $0.944$ (true limit $1$); $\{\frac{1}{{2}^{k(k+1)/2}}\}$ $0.4999990$ (true limit $\frac{1}{2}$); $\{\frac{1}{{2}^{{k}^{2}}}\}$ $0.2499999$ (true limit $\frac{1}{4}$); $\{\frac{1}{1!\mathrm{\cdots}k!}\}$ $0.055$ (true limit $0$, but very slow convergence); $\{\frac{1}{{1}^{1}\mathrm{\cdots}{k}^{k}}\}$ $0.0210$ (true limit $0$, but very slow convergence); $\{\frac{1}{{2}^{{k}^{3}}}\}$ $1.97\cdot {10}^{31}$ (true limit $0$).
In the last two cases (Example 10d, ${x}_{k}=\mathrm{\Pi}{a}_{i}$, resp. ${y}_{k}=\mathrm{\Pi}{b}_{i}$), much fewer relevant terms can be computed with this precision, and one clearly see we do not have convergence.
In each case it is confirmed numerically that the sequence belongs to the stated SSL class. However, it is worth noting that in some cases (e.g., $\{\frac{1}{1!\mathrm{\cdots}k!}\}$ and $\{\frac{1}{{1}^{1}\mathrm{\cdots}{k}^{k}}\}$) some more terms are needed to conclude that the sequence $\{\frac{{\alpha}_{k+1}}{{\alpha}_{k}}\}$ converges.
In certain applications it may be difficult to verify numerically whether $\frac{{\alpha}_{k+1}}{{\alpha}_{k}}$ converges to $0$, to $1$ or to some value in $(0,1)$ (if at all), especially when the convergence is slow.
Numerous methods from Computational Optimization were proved to be with (at least) superlinear order. Three classical methods have explicit expressions for their errors, and now their speed can be assessed.
Example 18
The quasiNewton methods for smooth unconstrained optimization are known for a long time that attain superlinear order, but it is only recently that some explicit expressions for the errors have been obtained.
Rodomanov and Nesterov [16] have shown for the Davidon–Fletcher–Powell (DFP) method that the errors are of the form ${e}_{k}={(\frac{a}{k})}^{\frac{k}{2}}$ ($a$ depending on the dimension problem, the Lipschitz constant and the strong convexity parameter) and for the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method that similarly ${e}_{k}={(\frac{b}{k})}^{\frac{k}{2}}$.
Subsequently, Ye et al. [21] have shown for the SymmetricRank 1 (SR1) method that ${e}_{k}={(\frac{c}{k})}^{\frac{k}{2}}$.
We see that all the three methods attain weak SSL order, and it becomes interesting to find methods with medium or perhaps strong SSL order, for the reason that their faster speed may appear from the first terms.
3 Conclusions
The main role of the convergence orders is to allow the comparison of the speed of different convergent sequences: we usually expect that the higher the order, the faster the speed; while this is in general true (as shown in [8] for orders $$), these notions are imperfect and there are some notable exceptions. Indeed, a sequence with no $Q$order was shown in [10] that may have fast speed (termbyterm faster than another sequence, with infinite order).
Here we have seen that a similar phenomenon holds in the case of the (mixed) superlinear convergence, as such a sequence may converge faster than another sequence, with infinite order (though, it is worth noting that not all sequences with mixed SSL order have such fast speed).
The explanation for such a behavior resides in the fact that both the superlinear and the $Q$orders rely on conditions on consecutive errors, not on “global” relations involving all the errors. The graph of the sequence from Example 10(d) (${x}_{k}=\mathrm{\Pi}{a}_{i}$) which was plotted in Figure 1 in olive color is perhaps most relevant: while its speed is high (steep slope), some of the consecutive errors do not have a high relative reduction.
A similar analysis may be taken for the linear convergence [9], and the higher orders [8], but with notable different particularities; we have also started to analyze the sublinear convergence.
In [6] we study the speed of $\{{Q}_{\mathrm{\Lambda}}(k)\}$ and $\{{Q}_{L}(k)\}$, while in [17] we obtain some simplified proofs for the $Q$order.
Data availability. All data generated or analysed during this study are included in this published article.
Conflict of interest. The author has no conflict of interests to declare that are relevant to the content of this article.
Ethical Approval. Not Applicable.
Availability of supporting data. Not Applicable.
Competing interests. Not Applicable.
Funding. Not Applicable.
Authors’ contributions. Not Applicable.
Acknowledgments. Not Applicable.
References
 [1] (1990) Convergence rates and convergenceorder profiles for sequences. Acta Appl. Math. 20 (), pp. 267–284. External Links: Document Cited by: §1, §1, §1.
 [2] (2017) Julia: a fresh approach to numerical computing. SIAM Review 59 (), pp. 65–98. External Links: Document Cited by: Example 10.
 [3] (1982) On the local convergence of quasinewton methods for constrained optimization. SIAM Journal on Control and Optimization 20 (2), pp. 161–171. External Links: Document, Link, https://doi.org/10.1137/0320014 Cited by: Remark 2.
 [4] (1977) Accélération de la convergence en analyse numérique. SpringerVerlag, Berlin. Cited by: §1.
 [5] (1985) Vitesse de convergence d’une suite. Rev. Roumaine Math. Pures Appl. 30, pp. 403–417. Cited by: §1.
 [6] (2021) Measuring the measures. Note: (manuscript) Cited by: §3.
 [7] (2019) A survey on the high convergence orders and computational convergence orders of sequences. Appl. Math. Comput. 343 (), pp. 1–20. External Links: Document Cited by: §1, §1, §1.
 [8] (2021) Characterizing the classical convergence orders. Note: manuscript, submitted Cited by: §3, §3.
 [9] (2021) Characterizing the classical linear convergence order. Note: manuscript Cited by: §3.
 [10] (2021) How many steps still left to $x$*?. SIAM Rev. 63 (3), pp. 585–624. External Links: Document Cited by: §1, §1, §1, §2, §2, §3, Remark 1, Remark 12, footnote 3.
 [11] (1974) A characterization of superlinear convergence and its application to quasiNewton methods. Math. Comp. 28 (126), pp. 549–560. External Links: Document Cited by: Lemma 15.
 [12] (2000) Iterative solution of nonlinear equations in several variables. SIAM, PA. External Links: Document Cited by: §1, §1, Remark 2.
 [13] (1997) Optimization. algorithms and consistent approximations. SpringerVerlag, New York. Cited by: §2, Remark 2.
 [14] (1984) Nondiscrete induction and iterative processes. Pitman, Boston, Massachusetts. Cited by: §1, Lemma 15, Remark 2.
 [15] (1989) On Qorder and Rorder of convergence. J. Optim. Theory Appl. 63 (3), pp. 415–431. External Links: Document Cited by: §1.
 [16] (2022) Rates of superlinear convergence for classical quasiNewton methods. Math. Program. 194 (12, Ser. A), pp. 159–190. External Links: ISSN 00255610, Document, Link Cited by: Example 18.
 [17] (2021) Simpler proofs for the Qorder. Note: manuscript Cited by: §3.
 [18] The tikz and pgf packages. Manual for version 3.1.5b34gff02ccd1. External Links: Link Cited by: Example 10.
 [19] (1977) Diagonalized multiplier methods and quasiNewton methods for constrained optimization. J. Optim. Theory Appl. 22 (2), pp. 135–194. External Links: ISSN 00223239, Document, Link Cited by: Remark 2, Remark 2.
 [20] (1997) An approach to continuation using Krylov subspace methods. Computational Science in the 21st Century, J. Periaux, ed., John Wiley and Sons, Ltd., pp. 72–81. Cited by: Lemma 15.
 [21] (2023) Towards explicit superlinear convergence rate for SR1. Math. Program. 199 (12, Ser. A), pp. 1273–1303. External Links: ISSN 00255610, Document, Link, MathReview Entry Cited by: Example 18.
Preprint html version of the paper:
[1] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. SIAM, PA (2000)
[2] Beyer, W.A., Ebanks, B.R., Qualls, C.R.: Convergence rates and convergenceorder profiles for sequences. Acta Appl. Math. 20, 267–284 (1990)
[3] Brezinski, C., Vitesse de convergence d’une suite. Rev. Roumaine Math. Pures Appl. 30, 403–417 (1985)
[4] Potra, F.A., On Qorder and Rorder of convergence. J. Optim. Theory Appl. 63(3), 415–431 (1989)
[5] Catinas, E., A survey on the high convergence orders and computational convergence orders of sequences. Appl. Math. Comput. 343, 1–20 (2019)
[6] Catinas, E., How many steps still left to x*? SIAM Rev. 63(3), 585–624 (2021)
[7] Brezinski, C., Accélération de la Convergence en Analyse Numérique. SpringerVerlag, Berlin (1977)
[8] Potra, F.A., Pták, V., Nondiscrete Induction and Iterative Processes. Pitman, Boston, Massachusetts (1984)
[9] Tapia, R.A., Diagonalized multiplier methods and quasiNewton methods for constrained optimization. J. Optim. Theory Appl. 22(2), 135–194 (1977)
[10] Polak, E., Optimization. Algorithms and Consistent Approximations. SpringerVerlag, New York (1997)
[11] Boggs, Paul T., Tolle, Jon W., Wang, Pyng, On the local convergence of QuasiNewton methods for constrained optimization. SIAM Journal on Control and Optimization 20(2), 161–171 (1982)
[12] Tantau, T., The tikz and pgf packages. Manual for version 3.1.5b34gff02ccd1
[13] Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Review 59, 65–98 (2017)
[14] Walker, H.F., An approach to continuation using Krylov subspace methods. In: Periaux, J. (ed.) Computational Science in the 21st Century, pp. 72–81. John Wiley and Sons, Ltd. (1997)
[15] Dennis, J.E., Jr., Moré, J.J., A characterization of superlinear convergence and its application to quasiNewton methods. Math. Comp. 28(126), 549–560 (1974)
[16] Rodomanov, A., Nesterov, Y., Rates of superlinear convergence for classical quasiNewton methods. Math. Program. 194(1–2, Ser. A), 159–190 (2022)
[17] Ye, H., Lin, D., Chang, X., Zhang, Z., Towards explicit superlinear convergence rate for SR1. Math. Program. 199(1–2, Ser. A), 1273–1303 (2023)
[18] Catinas, E., Characterizing the classical convergence orders. Manuscript, submitted (2021)
[19] Catinas, E., Characterizing the classical linear convergence order Manuscript. (2021)
[20] Catinas, E., Stan, A., Measuring the measures. (2021). (manuscript)
[21] Stan, A., Catinas, E., Simpler proofs for the Qorder. Manuscript (2021)