Convergence orders

Webpage under construction!!

They are notions for measuring the convergence speed of sequences \(  x_k \rightarrow x^\ast\in X\). For simplicity, let \(X={\mathbb R}\).

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 \(f(x)=0\)).

Let \( 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)=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

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

\(\Leftrightarrow \)
\begin{equation}\tag{$Q_Q$}\label{def Q_Q}
\lim\limits_{k\rightarrow \infty} Q_p(k)=0 \ \ (1\leq p<p_0) \ \ \ and \ \ \lim\limits_{k\rightarrow \infty} Q_p(k)=\infty, \ (\forall p>p_0)
\(\Leftrightarrow \forall \varepsilon>0,  \exists A,B\geq 0, \ k_0 \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{e_{k+2}}{e_{k+1}}}{\ln \frac{e_{k+1}}{e_k}}=p_0.

R-order \(p_0>1\) when

\begin{equation}\tag{$R_R$}\label{def R_R}
\lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=0, \ p<p_0, \ \ \ and \ \ \lim\limits_{k\rightarrow \infty} e_k^{1/p^k}=1, \ p>p_0

\(\Leftrightarrow \)
\begin{equation} \tag{\(R_L\)}
\lim\limits_{k\rightarrow \infty}\big|\ln e_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 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}}.%

Computational convergence orders

They use the corrections \(s_k\) or the residuals \(|f(x_k)|\), without requiring the knowledge of \(x^\ast\) or \(p_0\).

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…