**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\).