How Many Steps Still Left to $x$*?

Abstract

The high speed of $x_{k}\rightarrow x^\ast\in{\mathbb R}$ is usually measured using the $C$-, $Q$-, or $R$-orders: \[ \lim \frac {|x^\ast - x_{k+1}|}{|x^\ast - x_k|^{p_0}}\in(0,+\infty), \qquad \lim \frac {\ln |x^\ast - x_{k+1}|}{\ln |x^\ast - x_k|} =q_0, \qquad \mbox{or} \quad \lim \big\vert\ln |x^\ast - x_k| \big \vert ^\frac1k =r_0. \] By connecting them to the natural, term-by-term comparison of the errors of two sequences, we find that the $C$-orders---including (sub)linear---are in agreement. Weird relations may appear though for the $Q$-orders: we expect $|x^\ast - x_k|=\mathcal{O}(|x^\ast - y_k|^\alpha)$ $\forall\alpha>1$ to imply “$\geq$" for the $Q$-orders of $\{x_{k}\}$ vs. $\{y_{k}\}$; the contrary is shown by an example providing no vs. infinite $Q$-orders. The $R$-orders appear to be even worse: an $\{x_{k}\}$ with infinite $R$-order may have unbounded nonmonotone errors: \(\limsup \frac{|x^\ast - x_{k+1}|}{|x^\ast - x_k|}= +\infty\). Such aspects motivate the study of equivalent definitions, computational variants, and so on. These orders are also the perspective from which we analyze the three basic iterative methods for nonlinear equations in $\mathbb R$. The Newton method, widely known for its quadratic convergence, may in fact attain any $C$-order from $[1,+\infty]$ (including sublinear); we briefly recall such convergence results, along with connected aspects (such as historical notes, known asymptotic constants, floating point arithmetic issues, and radius of attraction balls), and provide examples. This approach leads to similar results for the successive approximations method, while the secant method exhibits different behavior: it may not have high $C$-orders, but only $Q$-orders.

Topics & Concepts