# Convergence order

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

## How many steps still left to x*?

Abstract The high speed of $$x_{k}\rightarrow x^\ast\in{\mathbb R}$$ is usually measured using the C-, Q- or R-orders: \begin{equation}\tag{$C$} \lim \frac…

## Global random walk solvers for fully coupled flow and transport in saturated/unsaturated porous media

AbstractIn this article, we present new random walk methods to solve flow and transport problems in saturated/unsaturated porous media, including coupled flow…

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

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…

## On the convergence of some one step and multistep iterative methods

Abstract AuthorIon Păvăloiu (Tiberiu Popoviciu Institute of Numerical Analysis) Keywordsnonlinear equations in R; one step iterative methods; multistep iterative methods;…

## On the r-convergence orders of the inexact perturbed Newton methods

Abstract The inexact perturbed Newton methods recently introduced by us are variant of Newton method, which assume that at each step…

## Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences

Abstract We study the conditions under which the well-known Aitken-Steffensen method for solving equations leads to monotonic sequences whose terms…

## On the convergence order of the iterative methods

Abstract We study the connection between the convergence order of two sequences. We show that the exist sequences that do…

## Optimal algorithms concerning the solving of equations by interpolation

Abstract In this paper we approach two aspects concerning the optimality problems arising from the consideration of the iterative methods for…