Webpage under construction!!
They are notions for measuring the convergence speed of sequences \( x_k \rightarrow x^\ast\in X\). For simplicity, let \(X={\mathbb R}\).
They are defined using either
- the errors \( x^\ast – x_k \),
- the corrections \(x_{k+1}- x_k \) or
- the nonlinear residuals \(f(x_k)\) (when solving \(f(x)=0\)).
Let \( e_k: = |x^\ast – x_k| \), \( s_k := |x_{k+1} – x_k| \), \(|f_k| := |f(x_k)|\).
Let \(Q_p(k)=\frac{e_{k+1}}{{e_k}^p}\) denote the quotient factor.
Error-based convergence orders
High orders \(p_0>1\)
Three main classes exist, C (classic), Q (quotient) and R (root):
C-order \(p_0>1\), when
\[
\lim \limits_{k\rightarrow \infty} Q_{p_0}(k)=Q_{p_0}\in(0,\infty)
\qquad {\rm i.e.,}\
\lim\limits_{k\rightarrow \infty}\textstyle\frac{e_{k+1}}{e_k ^{p_0}}=\lim\limits_{k\rightarrow \infty}\frac{| x^\ast – x_{k+1}|}{| x^\ast – x_k |^{p_0}}=Q_{p_0}\in(0,\infty),
\]
Q-order \(p_0>1\) when
\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}
\(\Leftrightarrow \)
\begin{equation}\tag{$Q_Q$}\label{def Q_Q}
\lim\limits_{k\rightarrow \infty} Q_p(k)=0 \ \ (1\leq p<p_0) \ \ \ and \ \ \lim\limits_{k\rightarrow \infty} Q_p(k)=\infty, \ (\forall p>p_0)
\end{equation}
\(\Leftrightarrow \forall \varepsilon>0, \exists A,B\geq 0, \ k_0 \geq 0\) s.t.
\begin{equation}\tag{$Q_\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}
\(\Leftrightarrow \)
\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}
R-order \(p_0>1\) when
\begin{equation}\tag{$R_R$}\label{def R_R}
\lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=0, \ p<p_0, \ \ \ and \ \ \lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=1, \ p>p_0
\end{equation}
\(\Leftrightarrow \)
\begin{equation} \tag{\(R_L\)}
\lim\limits_{k\rightarrow \infty}\big|\ln e_k\big|^{\frac 1k} =p_0
\end{equation}
\(\Leftrightarrow \) \(\forall \varepsilon>0,\ \exists A,B>0, \ 0<\eta,\theta<1, \ k_0 \geq 0\) s.t.
\begin{equation}\tag{$R_{\varepsilon}$}\label{f. def R_eps}
A\cdot \eta^{\left( p_{0}+\varepsilon \right) ^{k}}\leq e_k \leq B\cdot \theta^{\left( p_{0}-\varepsilon \right) ^{k}%
},\; \; \forall k\geq k_0.
\end{equation}
The C-order is a particular class of the Q-order.
Relevant results can be found in the classical book of Ortega & Rheinboldt (1970), and in the book of Potra and Ptak (1984).
Tight connections between these orders were first shown by Potra (1989), then by Beyer, Ebanks & Qualls (1990). In two recent survey papers, Catinas (2019) and Catinas (2021) has made a rigorous presentation of all the aspects concerning this topic: definitions, connections, historical, computational aspects.
The connection between the Q- and R-orders can be seen taking \(a_k=\big \vert \ln e_k \big \vert \) in the classical inequalities
\[
\liminf \limits_{k\rightarrow \infty}\frac{a_{k+1}}{a_{k}}\leq \liminf
\limits_{k\rightarrow \infty}\left \vert a_{k}\right \vert ^{\frac{1}{k}}%
\leq \limsup_{k\rightarrow \infty}\left \vert a_{k}\right \vert ^{\frac{1}{k}}
\leq \limsup_{k\rightarrow \infty}\frac{a_{k+1}}{a_{k}}.%
\]
Computational convergence orders
They use the corrections \(s_k\) or the residuals \(|f(x_k)|\), without requiring the knowledge of \(x^\ast\) or \(p_0\).
