# Thresholds of the Inner Steps in Multi-Step Newton Method
## The Threshold  
**Lemma 1**.: _Let \(g:[1,\infty)\times[1,\infty)\rightarrow\mathcal{R}\) be the real function in two variables defined by_  
\[g(m,n)=m-ln(m+1)^{m+1}+\frac{n^{2}-1}{3n},\]  
_where \(ln\) is the natural logarithm. Then for any \(n\in\mathcal{N}_{+},\ n\geq 2\) the equation \(g(m,n)=0\) has a unique solution \(m_{e}\in(1,\infty)\)._  
Proof.: The proof involves simple elementary calculus, such that some details are omitted.  
We have  
\[g(1,n)=1-ln(4)+\frac{n^{2}-1}{3n}>0.\]  
Suppose that  
\[m>e^{\frac{n^{2}-1}{3n}}-1,\]  
then \(g(m,n)<0\). Therefore, there exists \(m_{e}\) such that \(g(m_{e},n)=0\). The solution \(m_{e}\) of the equation \(g(m,n)=0\) is unique in \((1,\infty)\). Indeed, the derivative of \(g\) with respect to \(m\) is \(g^{\prime}(m,n)=-ln(m+1)\) and the function \(g\) is strictly decreasing on \([1,\infty)\).  
**Remark 1**.: _Suppose that, for some \(n\) and some \(p,\ 0<p<1\), the following is true_  
\[ln(n^{p}+1)^{n^{p}+1}>n^{p}+\frac{n^{2}-1}{3n}. \tag{1}\]  
_Then \(n^{p}>m_{e}\) (the proof is elementary). Note that, for given \(p\), (1) is not satisfied for any \(n\), but it is satisfied on some interval of \(n\), usually very large when \(p\approx 1\). For example, if \(p=2/3=0.666\dots\) then this interval is \([1,1.756\times 10^{3}]\); if \(p=0.8\) then the interval is \([1,1.257\times 10^{8}]\)._  
We consider next an iterative method of _Newton-type_ which has \(g\) as convergence order and which uses only the first derivative and its inverse in inner steps. Jarratt, M5 and WKG methods are examples of such Newton-type method. The main processing consists of the solution of one or several linear systems having the first derivative as matrix. The total number of products/divisions of such a method is given by \(d(n)=an^{3}+P(n)\), where \(a>0\) and \(P\) is a polynomial of degree 2.  
The theorem below gives a comparative analysis of Traub efficiency indexes of multi-step Newton method and this Newton-type method. Recall that the Traub efficiency index of multi-step Newton method, is:  
\[I_{m_{s}}(m,n)=(m+1)^{\frac{3}{n^{3}+3 mn^{2-m}}}.\]  
**Theorem 1**.: _Consider a Newton-type method with the convergence order \(\varrho\geq 2\) and the number of products/divisions  
The case \(I_{m_{s}}(1,n)=\varrho^{1/d(n)}\) is illustrated by classical Newton method (Figure 1a), the case \(I_{m_{s}}(1,n)>\varrho^{1/d(n)}\), by Jarratt method (Figure 1b) and the case \(I_{m_{s}}(1,n)<\varrho^{1/d(n)}\), by M5 method (Figure 1c).  
**Remark 2**.: _It is desirable that condition (2) to be satisfied for a large interval of \(n\), or even for all \(n\). If (1) is satisfied for some \(n\) and \(p\), then the condition (2) can be replaced by the following stronger condition_  
\[d(n)>n^{2}(n^{p}+1)ln\varrho, \tag{5}\]  
The condition (5) is easier to check, but it gives a more restrictive interval for \(n\).  
_Particular Cases_  
We check that the condition (2) is satisfied for classical Newton method and for M5 method and therefore Theorem 1 can be applied.  
It is easy to see that in the case of Newton method, the condition (2) is satisfied for all \(n\). The stronger condition (5) gives for \(n\) the interval \([7,1.756\times 10^{3}]\). For example, if \(n=15\) then the threshold for m is \(m_{s}=22.101\ldots\)  
In the case of M5 method, the condition (2) is satisfied for all \(n\in[32,\infty)\). The stronger condition (5) gives for \(n\) the interval \([100,1.756\times 10^{3}]\). For example, if \(n=40\) then the thresholds for m are \(m_{i}=5.229\ldots\), \(m_{s}=14.431\ldots\)