Convergence orders

The convergence orders are notions introduced for measuring the convergence speed of sequences.

They are based

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

The later may be used to define computational orders – defined with the aid of the elements of a sequence known at a step k, without requiring the knowledge of the limit or order.

Error-based convergence orders

Three main classes of high orders (>1) exist (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}
    \lim\limits_{k\rightarrow \infty}\frac{\ln\Vert x^\ast – x_{k+1}\Vert}{\ln\Vert x^\ast – x_k \Vert}=p_0
    %\end{equation}
    \]
  • 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
    %\end{equation}
    \]

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 \(\forall \varepsilon>0,  \exists A,B>0\) s.t.
\begin{equation}\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.
\end{equation}

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.
\begin{equation}\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.
\end{equation}

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.

Related Posts

No results found.

Menu