## Convergence orders

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
\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;

$$\Leftrightarrow$$

\tag{$Q_Q$}\label{def Q_Q}
\lim\limits_{k\rightarrow \infty} Q_p(k)=+\infty, \ p>p_0;

$$\Leftrightarrow \forall \varepsilon>0, \exists A,B\geq 0$$ s.t.
\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;

$$\Leftrightarrow$$

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

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

$$\Leftrightarrow$$ $$\forall \varepsilon>0,\ \exists A,B>0, \ 0<\eta,\theta<1, \ k_0 \geq 0$$ s.t.

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

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.

## Methods of Newton and Newton-Krylov type

Book summaryLocal convergence results on Newton-type methods for nonlinear systems of equations are studied. Solving of large linear systems by…

## Numerical benchmark study for flow in highly heterogeneous aquifers

AbstractThis article presents numerical investigations on accuracy and convergence properties of several numerical approaches for simulating steady state flows in…

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

AbstractTwenty years after the classical book of Ortega and Rheinboldt was published, five definitions for the (Q)-convergence orders of sequences…

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

Abstract AuthorIon Păvăloiu Keywordsnonlinear equations in R; one step iterative methods; multistep iterative methods; convergence order. ReferencesPDFScanned manuscript (in Romanian).…

## 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…