# Thresholds of the Inner Steps in Multi-Step Newton Method
## 1 Introduction  
There is currently an increasing interest in developing iterative methods for solving systems of nonlinear equations, \(F(x)=0\), \(F:D\subseteq R^{n}\to R^{n}\), with high order of convergence by using only the first derivative of \(F\) and its inverse. We will use the term \"Newton-type method\" for such an iterative procedure. A typical example of Newton-type method is the multi-step Newton method (other terms, \"modified Newton method\", \"multi-step frozen Jacobian version of the Newton method\" [1], etc.) in which the first derivative of \(F\) is re-evaluated periodically after \(m\) steps. If \(x\) denotes the current iteration, the next iteration \(x_{next}\) is obtained by the following scheme:  
\[x=current\ iteration,\ y_{1}=x;\] \[Compute\ F^{\prime}(x);\] \[For\ k=1\ to\ m\] \[Compute\ F(y_{k});\] \[Solve\ the\ linear\ system\ F^{\prime}(x)s=-F(y_{k});\] \[y_{k+1}=y_{k}+s;\] \[x_{next}:=y_{m+1}.\]  
The method has high convergence order, equal to \(m+1\), and the computational cost is due by the inner steps for the computation of \(y_{k}\). This cost can be estimated by the total number \(d\) of functional evaluations of \(F\) and \(F^{\prime}\) (in our case \(d=n^{2}+mn\)). The efficiency of the method can be then measured by the Ostrowski index of efficiency, given by \(I=\varrho^{\frac{1}{d}}\), where \(\varrho\) is the convergence order. A more accurate measurement of efficiency is the Traub index of efficiency, given by the same formula, but for which \(d\) is now the total number of arithmetical operations (usually products/divisions) necessary to obtain the next iteration (in our case \(d=(n^{3}+3 mn^{2}-n)/3\), that is, \((n^{3}-n)/3\) operations for \(LU\) factorization and \(mn^{2}\) operations for solving the triangular systems [2]).  
A plethora of high order Newton-type methods also exist, in which the inner steps do not involve any loop calculation, such as, for example, the four order Jarratt method [3], the fifth order \"M5\" method [2] and sixth order WKB method [4] (these methods will be used in this note as test examples).  
It is worth mentioning that M5 method has excellent computational properties (convergence order and complexity) and, as a consequence, a high efficiency index.  
The particular case \(m=2\) was considered by [PERSON] and [PERSON] [5]. Using non-discrete induction, they proved the order three of convergence and gave sharp a priori and a posteriori error for this particular case. Often it is called \"Potra-Ptak\" method [6; 7]. In the case of a single equation, Potra-Ptak method was considered by [PERSON] [8] (1982). [PERSON] and [PERSON] [9] proved order three of convergence for Potra-Ptak method in n-dimensional spaces (Theorem 10.2.4, [9]). Note that Potra-Ptak method is a particular case of a multipoint iterative process with order three of convergence considered by [PERSON] and [PERSON] [10].  
Numerical experiments show that the Ostrowski/Traub efficiency index of multi-step Newton method has the following property with respect to the other Newton-type method: Under some conditions, for given \(n\), there exists an interval \((m_{i},m_{s})\), such that for \(m\) inside of this interval, the efficiency index of multi-step Newton method is better than that of considered Newton-type method. We say that \(m_{i},m_{s}\) are the thresholds of \(m\), inferior and superior, respectively. This property was tested experimentally by the author for several high order Newton-type methods, like classical Newton, Jarratt, M5, WKG.  
In this paper, we give a simple condition ensuring that this property holds for some class of Newton-type methods. In particular, this condition is verified by classical Newton method and M5 method.