# Convergence order (order of convergence)

The convergence order (the order of convergence or convergence rate) are notions for measuring the convergence speed of convergent sequences $$x_k \rightarrow x^\ast\in X$$.

Usually, the higher the order, the faster the speed, but there are some notable exceptions. One expects that the fastest speed is achieved by the infinite order, but this is not always true: one may find sequences with no order or sequences with strict superlinear order, which which are term by term faster than some sequences with infinite order (see [Catinas, 2021] or [Catinas, 2023]).

The first survey paper on convergence orders was recently published, in [Catinas, 2019].

The convergence orders are defined using the errors $$x^\ast – x_k$$. For simplicity, let $$X={\mathbb R}$$ and let $$e_k: = |x^\ast – x_k|$$.

For a given $$p\geq 1$$, let $$Q_p(k)=\frac{e_{k+1}}{{e_k}^p}$$, $$k\geq 1$$ denote the quotient convergence factors.

## High convergence orders $$p_0>1$$

Three main classes exist, C (classic), Q (quotient) and R (root) convergence orders:

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

\tag{$Q_L$}\label{def Q_L}
\lim\limits_{k\rightarrow \infty}
\frac{\ln e_{k+1}}{\ln e_k}=p_0

$$\Leftrightarrow$$

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

$$\Leftrightarrow$$
\tag{$Q_Q$}\label{def Q_Q}
\begin{cases}
\lim\limits_{k\rightarrow \infty} Q_p(k)=0, & 1 \leq p < p_0 \\
\lim\limits_{k\rightarrow \infty} Q_p(k)=\infty, & p_0 < p \end{cases} $$\Leftrightarrow \forall \varepsilon>0, \exists A,B\geq 0, \ k_0 \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

### R-order $$p_0>1$$

when

\tag{$R_R$}\label{def R_R}
\begin{cases}
\lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=0, & 1\leq p<p_0, \\ \lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=1, & p_0<p
\end{cases}

$$\Leftrightarrow$$ $$\tag{R_L}\label{def R_L} \lim\limits_{k\rightarrow \infty} |\ln e_k|^{\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 clearly 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}}.%$

It holds that $$C \Rightarrow Q \Rightarrow R$$, i.e., convergence with C-order $$p_0>1$$ of a given sequence attracts convergence with Q-order $$p_0$$ which in turn attracts convergence with R-order $$p_0$$, and none of the converse is true.

## Superlinear convergence order (superlinear order of convergence / superlinear rate)

Superlinear convergence order holds when

$\lim\limits_{k\rightarrow \infty}\textstyle\frac{e_{k+1}}{e_k}=0$

In the recent paper [Catinas, 2023], it was shown that there are in fact four types of sequences with strict superlinear order (three of them being in increasing speed).

## Linear convergence order (convergence with order one)

The classical linear convergence holds when
$\lim \limits_{k\rightarrow \infty} Q_1(k)=Q_1\in(0,1) \qquad {\rm i.e.,}\ \lim\limits_{k\rightarrow \infty}\textstyle\frac{e_{k+1}}{e_k }=\lim\limits_{k\rightarrow \infty}\frac{| x^\ast – x_{k+1}|}{| x^\ast – x_k |}=Q_1\in(0,1),$
and $$Q_1$$ is usually called “the convergence rate”.

## Computational convergence orders

Instead of errors (usually not known), one may use computable quantities:

• the corrections $$x_{k+1}- x_k$$ or
• the nonlinear residuals $$f(x_k)$$, when solving iteratively nonlinear equations $$f(x)=0$$,

without requiring the knowledge of $$x^\ast$$ or $$p_0$$.

Let $$s_k := |x_{k+1} – x_k|$$, and by denoting $$Q^{\prime}_p(k)=\frac{s_{k+1}}{{s_k}^p}$$, construct in the similar way as above the $$C^{\prime}, Q^{\prime}, R^{\prime}$$ orders of convergence.

In the same way, let $$f_k := |f(x_k)|$$ $$Q^{\prime\prime}_p(k)=\frac{f_{k+1}}{{f_k}^p}$$ and construct $$C^{\prime\prime}, Q^{\prime\prime}, R^{\prime\prime}$$.

These notations were introduced in [Beyer, Ebanks & Qualls, 1990], the prime mark with no connection to differentiation.

Webpage under construction!!

## Computational orders of convergence of iterative methods for Richards’ equation

Abstract Numerical solutions for flows in partially saturated porous media pose challenges related to the non-linearity and elliptic-parabolic degeneracy of…

## The strict superlinear order can be faster than the infinite order

Abstract The strict superlinear order (superlinear convergence) was usually regarded as having an intermediate speed between between linear and with…

## How many steps still left to x*?

We survey the convergence orders of sequences and show the orders of the basic iterative sequences for solving nonlinear equations…

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

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

This is the first paper which surveys the rigorous definitions and relations of convergence orders (the Q-orders; the C-orders; the…

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