# Posts by Emil Cătinaş

## Abstract

The high speed of $$x_{k}\rightarrow x^\ast\in{\mathbb R}$$ is usually measured using the C-, Q- or R-orders:
\tag{$C$}
\lim \frac {|x^\ast – x_{k+1}|}{|x^\ast – x_k|^{p_0}}\in(0,+\infty),

\tag{$Q$}
\lim \frac {\ln |x^\ast – x_{k+1}|}{\ln |x^\ast – x_k|} =q_0,

\tag{$R$}
\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), \qquad\forall\alpha>1,$
to attract “$$\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 seem even worse: an $$\{x_{k}\}$$ with infinite R-order may have unbounded nonmonotone errors: $$\limsup$$$$|x^\ast – x_{k+1}|/|x^\ast – x_k|= +\infty$$.

Such aspects motivate the study of equivalent definitions, computational variants, etc.

The orders are also the perspective from which we analyze the three basic iterative methods for nonlinear equations. 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 (historical notes, known asymptotic constants, floating point arithmetic issues, radius of attraction balls, etc.) and provide examples.

This approach leads to similar results for the successive approximations, while the secant method exhibits different behavior: it may not have high C-, but just Q-orders.

## Authors

Emil Cătinaş
“Tiberiu Popoviciu” Institute of Numerical Analysis, Romanian Academy

## Keywords

(computational) convergence orders, iterative methods, Newton method, secant method, successive approximations, asymptotic rates.

## PDF

freely available at the publisher: http://doi.org/10.1137/19M1244858

##### Paper coordinates:

E. Catinas, How many steps still left to x*?, SIAM Rev., 63 (2021) no. 3, pp. 585–624, doi: 10.1137/19M1244858

0036-1445

1095-7200

## Github

Some small codes in LaTeX and Julia have been posted on Github in order to illustrate some aspects.

We will post soon in Python too.

## Notes

Working with the SIAM staff was an amazing experience. I would like to thank to Louis Primus for his solicitude and professionalism.

Some references I have missed:

(these were included in the initial submission, but missing in the final version, as not cited in text, and we switched to BibTeX)

known to me, but still missing (nobody is perfect):

found after sending the revised version:

• J. H. Wilkinson, The evaluation of the zeros of ill-conditioned polynomials. part ii, Numer. Math., 1 (1959), pp. 167–180, doi: 10.1007/BF01386382
• D. F. Bailey and J. M. Borwein, Ancient indian square roots: an exercise in forensic paleo mathematics, Amer. Math. Monthly, 119 (2012), pp. 646–657, doi 10.4169/amer.math.monthly.119.08.646.
• E. Halley, Methodus nova accurata & facilis inveniendi radices aeqnationum quarumcumque generaliter, sine praviae reductione, Phil. Trans. R. Soc., 18 (1694), pp. 136–148, https://doi.org/10.1098/rstl.1694.0029.
• A. Ralston and P. Rabinowitz, A First Course in Numerical Analysis, 2nd ed., 1978.
• M. A. Nordgaard, The origin and development of our present method of extracting the square and cube roots of numbers, The Mathematics Teacher, 17 (1924), pp. 223–238, https://doi.org/https://www.jstor.org/stable/27950616.

and others (to be completed)

Version: October 30, 2021.

## 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: \tag{$C$} \lim \frac…

## On the nonmonotone behavior of the Newton‐GMBACK method

AbstractGMBACK is a Krylov solver for large linear systems, which is based on backward error minimization properties. The minimum backward…

## 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…

## On the convergence of the Newton-GMBACK method

AbstractWhen the GMBACK solver is used in the Newton iterates, the iterates may be written either as inexact Newton iterates…

## Local and global convergence results for a class of Steffensen-Aitken-type methods

Abstract? AuthorsI. K. Argyros Department of Mathematics, Cameron University E. Catinas Tiberiu Popoviciu Institute of Numerical Analysis I. Pavaloiu Tiberiu Popoviciu Institute…

## Conditions for the convergence of perturbed Steffensen methods on a Banach space with a convergence structure

Abstract? Authors I.K. Argyros Department of Mathematics, Cameron University E. Catinas Tiberiu Popoviciu Institute of Numerical Analysis I. Pavaloiu Tiberiu Popoviciu Institute of…

## On some general iterative methods for solving nonlinear operator equations containing a nondifferentiable term

Abstract? Authors I.K. Argyros Department of Mathematics, Cameron University E. Catinas Tiberiu Popoviciu Institute of Numerical Analysis I. Pavaloiu Tiberiu Popoviciu Institute of…

## A survey on the high convergence orders and computational convergence orders of sequences

Abstract Let $$x_k\rightarrow x^\ast\in{\mathbb R}^N$$; denote the errors by $$e_k: = \|x^\ast – x_k\|$$ and the quotient factors…

## Achievements in Mathematics and in IT at Tiberiu Popoviciu Institute of Numerical Analysis

We present some historical aspects regarding pioneering results obtained at our Institute more than half a century ago, illustrated by…

## On the r-convergence orders of the inexact perturbed Newton methods

Abstract The inexact perturbed Newton methods recently introduced by us are variant of Newton method, which assume that at each step…