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

# Convergence orders

They are notions for measuring the convergence speed of sequences.

They are defined using either

• errors $$x^\ast – x_k$$,
• corrections $$x_{k+1}- x_k$$ or
• nonlinear residuals $$f(x_k)$$ (when solving nonlinear equations).

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

## Error-based convergence orders

### High orders

Three main classes (C-classic, Q-quotient, R-root):

• C-order $$p_0$$, when
$\lim\limits_{k\rightarrow \infty}\frac{\Vert x^\ast – x_{k+1}\Vert}{\Vert x^\ast – x_k \Vert^{p_0}}=C_{p_0}\in(0,\infty),$
• Q-order $$q_0$$ when

\beqin{equation}\tag{$Q_L$}\label{QL}
\lim\limits_{k\rightarrow \infty}\frac{\ln\Vert x^\ast – x_{k+1}\Vert}{\ln\Vert x^\ast – x_k \Vert}=p_0

or, equivalently, $$\forall \varepsilon>0, \exists A,B\geq$$ s.t.

\tag{$Q_{I,\varepsilon}$}\label{f. def Q_Ieps}
Ae_k ^{p_{0}+\varepsilon}\leq e_{k+1} \leq Be_k^{p_{0}-\varepsilon},\  \; \; \forall k\geq k_0.

or, equivalently,

\beqin{equation}\tag{$Q_\Lambda$} \label{QLam}
\lim\limits_{k\rightarrow \infty}\frac{\ln \frac{\Vert x^\ast – x_{k+1}\Vert}{\Vert x^\ast – x_{k+1}\Vert}}{\ln \frac{\Vert x^\ast – x_k \Vert}{\Vert x^\ast – x_{k+1}\Vert}}=p_0

• R-order $$r_0$$ when
$%\beqin{equation} \tag{R} \lim\limits_{k\rightarrow \infty}\big\vert\ln\Vert x^\ast – x_k\Vert\big\vert^{\frac 1k} =r_0 %$

The C-order is a particular class of the Q-order.

The definition of the Q-order above is not the usual one known, e.g., from the classical book of Ortega&Rheinboldt, but it is equivalent to saying that

Also, the definition of the R-order is equivalent to: $$\forall \varepsilon>0,\ \exists A,B>0, \ 0<\eta,\theta<1, \ k_0 \geq 0$$ s.t. $$\tag{R_{I,\varepsilon}}\label{f. def R_Ieps} A\, \eta^{\left( p_{0}+\varepsilon \right) ^{k}}\leq e_k \leq B\, \theta^{\left( p_{0}-\varepsilon \right) ^{k}% },\; \; \forall k\geq k_0.$$ 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.