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

    or, equivalently, \(\forall \varepsilon>0,  \exists A,B\geq\) 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}

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

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

Menu