**Webpage under construction!!**

The convergence orders are notions for measuring the convergence speed of sequences \( x_k \rightarrow x^\ast\in {\mathbb R}^N\). For simplicity we consider below \(N=1\).

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 nonlinear equations \(f(x)=0\)).

The computational orders use corrections or residuals, without requiring the knowledge of the limit \(x^\ast\) or the order \(p_0\).

Let us denote \( 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)=C_{p_0}\in(0,\infty)

\qquad {\rm i.e.,}\

\lim\limits_{k\rightarrow \infty}\frac{| x^\ast – x_{k+1}|}{| x^\ast – x_k |^{p_0}}=C_{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 |x^\ast – x_{k+1}|}{\ln |x^\ast – x_k|}=p_0;

\end{equation}

\(\Leftrightarrow \)

\begin{equation}\tag{$Q_Q$}\label{def Q_Q}

\lim\limits_{k\rightarrow \infty} Q_p(k)=0, p<p_0 \qquad {\rm and} \quad

\lim\limits_{k\rightarrow \infty} Q_p(k)=+\infty, \ p>p_0;

\end{equation}

\(\Leftrightarrow \forall \varepsilon>0, \exists A,B\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{|x^\ast – x_{k+2}|}{|x^\ast – x_{k+1}|}}{\ln \frac{|x^\ast – x_{k+1} |}{|x^\ast – x_k|}}=p_0.

\end{equation}

**R-order** \(p_0>1\) when

\[

%\beqin{equation} \tag{R}

\lim\limits_{k\rightarrow \infty}\big|\ln |x^\ast – x_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 a recent survey paper, Catinas (2019) has made a rigorous presentation of all the aspects concerning this topic: definitions, connections, historical, computational aspects.

The connection between the definition of Q- and R-orders can be seen from 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}}%

\]

taking \(a_k=\big \vert \ln e_k \big \vert \).

The Newton method (the most known iterative method with high convergence speed), has, under some standard assumptions, quadratic convergence (i.e., order 2).

### Computational convergence orders

**The computational convergence orders** (numerical convergence speed) do not require the knowledge of the limit of the sequence or the value of the order. They are defined with the aid of the elements of a sequence known at a step *k, *and the convergence order is obtained as the limit of these approximating expressions.