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

\begin{equation}\tag{$Q_Q$}\label{def Q_Q}
\lim\limits_{k\rightarrow \infty} Q_p(k)=0, p<p_0 \qquad {\rm and} \quad
\lim\limits_{k\rightarrow \infty} Q_p(k)=+\infty, \ p>p_0;
\(\Leftrightarrow \forall \varepsilon>0,  \exists A,B\geq 0\) s.t.
\begin{equation}\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 \)

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

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