The Convergence of the Euler’s method

Raluca Anamaria (Pomian) Salajan\(^\ast \)

October 23, 2010.

\(^\ast \)Secondary School Vasile Alecsandri, Strada Păşunii, Nr. 2A, Baia Mare, Romania, e-mail: salajanraluca@yahoo.com.

In this article we study the Euler’s iterative method. For this method we give a global theorem of convergence. In the last section of the paper we give a numerical example which illustrates the result exposed in this work.

MSC. 37C25, 12D10.

Keywords. Euler’s method, fixed point, one-point iteration method

1 Introduction

We consider the problem of finding a zero of the equation

\begin{equation} f(x)=0, \end{equation}

where \(f:[a,b]\subset \mathbb {R}\rightarrow \mathbb {R}\) is an analytic function with simple roots. This zero can be determined as a fixed point of some iteration functions \(g:[a,b]\rightarrow [a,b]\), by means of the one-point iteration method

\begin{equation} x_{n+1}=g(x_{n}), \ x_{0} \in [a,b], \ n=0,1,..., \ n \in \mathbb {N}, \end{equation}

where \(x_{0}\) is the starting value and \(g\) is a function of form

\begin{equation*} g(x)=x+\varphi (x). \end{equation*}

In this article we analyze the Euler’s method for approximating the solution \(x^{\ast }\in [a,b]\) of the equation (1). This method is defined by the relation

\begin{equation} x_{n+1}=x_{n}-\tfrac {2f(x_{n})}{f^{\prime }(x_{n})+\sqrt{[f^{\prime }(x_{n})]^{2}-2f(x_{n})f^{\prime \prime }(x_{n})}}, x_{0} \in [a,b],\ n\geq 0,\ n \in \mathbb {N}. \end{equation}

The Euler’s method has been rediscovered by several authors, see for example [1], [2], [5], [6], [7], [8], and references therein.

2 Theorems of convergence

Next we will study sufficient conditions in order that the sequence \(\left\{ x_{n}\right\} _{n\geq 0}\) generated through (3) would be convergent, and if \(x^{\ast }=\lim \limits _{n\rightarrow \infty }x_{n}\), then
\(f(x^{\ast })=0\).

In order to prove the convergence of the method of form (3), we would use the next result.

Theorem 1

( [ 3 ] , [ 4 ] ) If we consider the function \(f\), the real number \(\delta {\gt}0\) and \(x_{0}\in \Delta ,\) where \(\ \Delta =\{ x\in \mathbb {R}:\left| x-x_{0 }\right| \leq \delta \} \subseteq [a,b]\), we could assure that the following relations hold

the function \(f\) is of class \(C^{s}(\Delta )\), \(s\geq 2, \ s \in \mathbb {N}\) and \(\sup \limits _{x\in \Delta }\left| f^{(s)}(x)\right| = M{\lt}\infty ;\)
we have the relation \(\left| \sum \limits _{i=0}^{s-1}\tfrac {1}{i!}f^{(i)}(x)\varphi ^{i}(x)\right| \) \(\leq \gamma \left| f(x)\right| ^{s}\) for every
\(x\in \Delta ,\) where \(\gamma \in \mathbb {R,}\gamma \geq 0;\)
the function \(\varphi \) verifies the relation \(\left| \varphi (x)\right| \leq \eta \left| f(x)\right| ,\) for every \(x\in \Delta ,\) where \(\eta \in \mathbb {R}, \eta {\gt}0;\)
the numbers \(\lambda ,\eta ,M\) and \(\delta \) verify the relations:

\(\mu _{0}=\lambda \left| f(x_{0})\right| {\lt}1\), where \(\lambda =\left( \gamma +\tfrac {M\eta ^{s}}{s!}\right) ^{\tfrac {1}{s-1}}\) and \(\tfrac {\eta \mu _{0}}{\lambda (1-\mu _{0})}\leq \delta ;\)

then the sequence \(\left\{ x_{n}\right\} _{n\geq 0}\) generated by \((2)\) has the following properties:

it is convergent, and if \(\ x^{\ast }=\lim \limits _{n\rightarrow \infty }x_{n} \) then \(f(x^{\ast })=0\) and \(x^{\ast }\in \Delta ;\)
\(\left| x_{n+1}-x_{n}\right| \leq \tfrac {\eta \mu _{0}^{s^{n}}}{\lambda }\), for any \(n=0,1,..., n \in \mathbb {N};\)
\(\left| x^{\ast }-x_{n}\right| \leq \tfrac {\eta \mu _{0}^{s^{n}}}{\lambda (1-\mu _{0}^{s^{n}})}, n=0,1,2,..., n \in \mathbb {N}.\)

Proof â–¼

See [3], [4]. Based on Theorem 1, in our next result we would analyze the convergence of sequence \(\{ x_{n}\} _{n\geq 0}\) given by (3).

Theorem 2

If the function \(f\), the real number \(\delta {\gt}0\) and \(x_{0}\in \Delta ,\) where \(\ \Delta =\{ x\in \mathbb {R}:\left| x-x_{0 }\right| \leq \delta \} \subseteq [a,b]\), verify the relations

the function \(f\) is of class \(C^{3}(\Delta )\) and \(\ \sup \limits _{x\in \Delta }\left| f^{\prime \prime \prime }(x)\right| =M{\lt}\infty ;\)
\(\ \ \left| \tfrac {1}{f^{\prime }(x)}\right| \leq \beta \) for every \(x\in \Delta ,\ \beta \in \mathbb {R}, \beta {\gt}0; \)
\(\ \tfrac {f(x)f^{\prime \prime }(x)}{[f^{\prime }(x)]^{2}}\stackrel{not}{=}L_{f}(x)\leq \tfrac {1}{2}\) for every \(x\in \Delta ;\)
\(\lambda =\sqrt{\tfrac {8M}{3!}\beta ^{3}}{\gt}0;\)
\(\ \mu _{0}=\lambda \left| f(x_{0})\right| {\lt}1;\)
\(\ \tfrac {2\beta \mu _{0}}{\lambda (1-\mu _{0})}\leq \delta ;\)

then the sequence \(\{ x_{n}\} _{n\geq 0}\) generated by \((3)\) is convergent, and if \(x^{\ast }=\lim \limits _{n\rightarrow \infty }x_{n}\), the next relations hold

\(f(x^{\ast })=0\) and \(x^{\ast }\in \Delta ; \)
\(x_{n}\in \Delta ,\) \(n=0,1,2..., n \in \mathbb {N};\)
\(\left| f(x_{n})\right| \leq \tfrac {\mu _{0}^{3^{n}}}{\lambda },\ n=0,1,2,..., n \in \mathbb {N};\)
\(\left| x^{\ast }-x_{n}\right| \leq \tfrac {2\beta \mu _{0}^{3^{n}}}{\lambda (1-\mu _{0}^{3^{n}})},\ n=0,1,2,..., n \in \mathbb {N}.\)

Proof â–¼

We consider the function \(\varphi \) of form

\begin{equation*} \varphi (x)=-\tfrac {2f(x)}{f^{\prime }(x)+\sqrt{ [f^{\prime }(x)]^{2}-2f(x)f^{\prime \prime }(x)}},\ x \in \Delta . \end{equation*}

We’ll show that the elements of the sequence \(\{ x_{n}\} _{n\geq 0}\) generated by (3) are in \(\Delta \).

By conditions b), c) and f) we have

\begin{align*} \left| x_{1}-x_{0}\right| & =\left| \tfrac {f(x_{0})}{f^{\prime }(x_{0})}\right| \left| \tfrac {2}{1+\sqrt{1-2L_{f}(x_{0})}}\right| \leq 2\left| \tfrac {f(x_{0})}{f^{\prime }(x_{0})}\right|\leq \\ & \leq 2\beta \left| f(x_{0})\right| =\tfrac {2\lambda \beta \left| f(x_{0})\right| }{\lambda }{\lt} \tfrac {2\beta \mu _{0}}{\lambda (1-\mu _{0})}\leq \delta \Rightarrow x_{1}\in \Delta . \end{align*}

Applying the Taylor expansion of function \(f\) around \(x_{0}\) and taking into account that

\begin{align*} \varphi (x)& = \tfrac {-f^{\prime }(x)+\sqrt{[f^{\prime }(x)]^{2}-2f(x)f^{\prime \prime }(x)}}{f^{\prime \prime }(x)}=\\ & =-\tfrac {f^{\prime }(x)-\sqrt{[f^{\prime }(x)]^{2}-2f(x)f^{\prime \prime }(x)}}{f^{\prime \prime }(x)}, \end{align*}

\(\forall x\in \Delta \), and \(\varphi (x)\) is verifying the parable

\begin{equation*} ax^{2}+bx+c=0, \ \textnormal{where} \ c=f(x),b=f^{\prime }(x),a=\tfrac {f^{\prime \prime }(x)}{2}, \end{equation*}

we get

\begin{align*} \left| f(x_{1})\right| & \leq \left| f(x_{1})-\left(f(x_{0})+f^{\prime }(x_{0})(x_{1}-x_{0})+\tfrac {1}{2}f^{\prime \prime }(x_{0})(x_{1}-x_{0})^{2}\right)\right| + \label{ineq:formula one} \\ & \quad +\left| f(x_{0})+f^{\prime }(x_{0})(x_{1}-x_{0})+\tfrac {1}{2}f^{\prime \prime }(x_{0})(x_{1}-x_{0})^{2}\right| \leq \\ & \leq \left| \tfrac {f^{\prime \prime \prime }(\xi )}{3!}(x_{1}-x_{0})^{3}\right|+\left|f(x_{0})+f^{\prime }(x_{0})\varphi (x_{0})+\tfrac {1}{2}f^{\prime \prime }(x_{0})\varphi ^2(x_{0}) \right| \leq \\ & \leq \tfrac {M}{3!}\left| x_{1}-x_{0}\right| ^{3}\leq \tfrac {8M\beta ^{3}}{3!}\left| f(x_{0})\right| ^{3}=\tfrac {\mu _{0}^{3}}{\lambda }, \ \xi \in \Delta . \end{align*}

Because \(\left| \tfrac {1}{f^{\prime }(x_{1})}\right| \leq \beta \), we have that
\(\footnotesize {\left| x_{2}-x_{1}\right| =\left| \tfrac {f(x_{1})}{f^{\prime }(x_{1})}\right| \left| \tfrac {2}{1+\sqrt{1-2\tfrac {f(x_{1})f^{\prime \prime }(x_{1})}{[f^{\prime }(x_{1})]^{2}}}}\right| \leq 2 \left| \tfrac {f(x_{1})}{f^{\prime }(x_{1})}\right| \leq 2 \beta \left| f(x_{1})\right| \leq \tfrac {2\beta \mu _{0}^{3}}{\lambda }}\).

From all that we have proved above, by using the induction, it results that the property iii) holds for every \(n\in \mathbb {N},\)

\begin{equation} \left| f(x_{n})\right| \leq \tfrac {\mu _{0}^{3^{n}}}{\lambda }. \end{equation}

Analogously, from b), c) and (4) we can prove the following relation

\begin{equation} \ \left| x_{n+1}-x_{n}\right| =\left| \tfrac {f(x_{n})}{f^{\prime }(x_{n})}\right| \left| \tfrac {2}{1+\sqrt{1-2\tfrac {f(x_{n})f^{\prime \prime }(x_{n})}{[f^{\prime }(x_{n})]^{2}}}}\right| \leq \tfrac {2\beta \mu _{0}^{3^{n}}}{\lambda },\ n=0,1,..., n \in \mathbb {N}. \end{equation}

From (5), e) and f) we get the relation ii)

\begin{align} \left| x_{n+1}-x_{0}\right| & \leq \sum \limits _{i=0}^{n}\left| x_{i+1}-x_{i}\right| \label{ineq:formula one}\leq \\ & \leq \sum \limits _{i=0}^{n}\tfrac {2\beta \mu _{0}^{3^{i}}}{\lambda }\leq \tfrac {2\beta \mu _{0}}{\lambda }(1+\mu _{0}^{3-1}+\mu _{0}^{3^{2}-1}+...+\mu _{0}^{3^{n}-1}) \nonumber \\ & {\lt} \tfrac {2\beta \mu _{0}}{\lambda (1-\mu _{0})}\leq \delta \Rightarrow x_{n+1}\in \Delta ,\ n=0,1,2,..., n \in \mathbb {N}. \nonumber \end{align}

For the convergence of the sequence given by (3) we shall use the Cauchy’s theorem. By relation (5) and e) we deduce that

\begin{align} \left| x_{n+p}-x_{n}\right| & \leq \sum \limits _{i=n}^{n+p-1}\left| x_{i+1}-x_{i}\right| \leq \sum \limits _{i=n}^{n+p-1}\tfrac {2\beta \mu _{0}^{3^{i}}}{\lambda } \label{ineq:formula one}{\lt} \\ & {\lt}\tfrac {2\beta \mu _{0}^{3^{n}}}{\lambda }(1+\mu _{0}^{3^{n+1}-3^{n}}+...+\mu _{0}^{3^{n+p-1}-3^{n}}) \nonumber \\ & {\lt} \tfrac {2\beta \mu _{0}^{3^{n}}}{\lambda (1-\mu _{0}^{3^{n}})},\ p\in \mathbb {N},\ n=0,1,2,..., n \in \mathbb {N}. \nonumber \end{align}

Because \(\mu _{0}{\lt}1\), it results that the sequence \(\{ x_{n}\} _{n\geq 0}\) is fundamental, so according to the Cauchy’s theorem, it is convergent.

If \(x^{\ast }=\lim \limits _{n\rightarrow \infty }x_{n},\) for \(p\rightarrow \infty \), from the inequality (7) we obtain the
relation iv)

\begin{equation} \left| x^{\ast }-x_{n}\right| \leq \tfrac {2\beta \mu _{0}^{3^{n}}}{\lambda (1-\mu _{0}^{3^{n}})},\ n=0,1,2,..., n \in \mathbb {N}. \end{equation}

We show now that the relations i) hold, that is, \(x^{\ast }\) is a root of equation (1) and \(x^{\ast } \in \Delta \).

From the continuity of function \(f\) and from (4) for \(n\rightarrow \infty , \) it results

\begin{equation*} 0\leq \left| f(x^{\ast })\right| \leq \lim \limits _{n\rightarrow \infty }\tfrac {\mu _{0}^{3^{n}}}{\lambda }=0, \end{equation*}

that is, \(f(x^{\ast })=0\).

From f) and the inequality (8) for \(n=0\), we obtain

\begin{equation*} \left| x^{\ast }-x_{0}\right| \leq \tfrac {2\beta \mu _{0}^{3^{0}}}{\lambda (1-\mu _{0}^{3^{0}})}\leq \delta , \end{equation*}

so, \(x^{\ast }\in \Delta \).

Proof â–¼

It is evidently that all the assumptions of Theorem 1 are verified for \(s=3\), \(\gamma =0\) and \(\eta =2\beta \).

3 Numerical example

We shall present a numerical example, which illustrates the result exposed in Theorem 2.

Example 3

We used the following test functions and display the zeros \(x^{\ast }\) found.

\begin{align*} & f_{1}(x)={\rm ln}(x^2-3), \ x^{\ast }=-2, \ x \in [-2.35,-1.9],\\ & f_{2}(x)=x^{3}-3x^{2}-13x+15, \ x^{\ast }=5, \ x \in [4.5,5.5],\\ & f_{3}(x)=x^5-1, \ x^{\ast }=1, \ x \in [0.88,1.38]. \end{align*}

For the derivatives of order 1, 2 and 3 of \(f_{i},\ i=1,2,3\), we have the relations

\begin{align*} & f^{\prime }_{1}(x)=\tfrac {2x}{-3+x^2}, \ f^{\prime \prime }_{1}(x)=\tfrac {-4x^2}{(-3+x^2)^2}+\tfrac {2}{-3+x^2}, \\ & f^{\prime \prime \prime }_{1}(x)=\tfrac {16x^3}{(-3+x^2)^3}-\tfrac {12x}{(-3+x^2)^2}, \end{align*}

from which we get \(\beta =0.536702\) and \(M=422.22\);

\begin{align*} f^{\prime }_{2}(x)=3x^2-6x-13, \ f^{\prime \prime }_{2}(x)=6x-6, \ f^{\prime \prime \prime }_{2}(x)=6, \end{align*}

from which we get \(\beta =0.0481928\) and \(M=6\);

\begin{align*} f^{\prime }_{3}(x)=5x^4, \ f^{\prime \prime }_{3}(x)=20x^3, \ f^{\prime \prime \prime }_{3}(x)=60x^2, \end{align*}

from which we get \(\beta =0.333503\) and \(M=114.264\).

In the Table 1 are listed the values for \(x_{0}\), \(M\), \(\beta \), \(\lambda \), \(\mu _{0}\), \(\delta \) and \(\tfrac {2\beta \mu _{0}}{\lambda (1-\mu _{0})}\), for each test functions.

\(i\)	\(x_{0}\)	\(M\)	\(\beta \)	\(\lambda \)	\(\mu _{0}\)	\(\delta \)	\(\tfrac {2\beta \mu _{0}}{\lambda (1-\mu _{0})}{\lt}\delta \)
1	-1.989	422.22	0.53670	9.32908	0.41860	0.089	0.08284
2	4.875	6	0.04819	0.02992	0.11414	0.625	0.41503
3	1.035	114.264	0.33350	2.37724	0.33873	0.353	0.14372

Table 1

The implementations were done in Mathematica 7.0 with double precision. From the Table 1 we can conclude that all the assumptions a)–f) of Theorem 2 are verified.

In the next Table 2 we can observe that, the convergence is faster and the method (3) converges at \(x^{\ast }\).

\(i\)	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)	\(x_{3}=x^{\ast }\)
1	-1.989	-2.0000063482540900	-1.9999999999999990	-2
2	4.875	5.0000611233335144	4.999999999999993	5
3	1.027	0.999958832170524	1.000000000000139	1

Table 2

Bibliography

1: Amat, S., Busquier, S. and Plaza, S., Review of some iterative root-finding methods from a dynamical point of view, Scientia, Series A: Mathematical Sciences, 10, pp. 3–35, 2004.
2: Osada, N., A one parameter family of locally quartically convergent zero-finding methods, J. Comput. Appl. Math., 205, pp. 116–128, 2007.
3: Păvăloiu, I., Sur les procedées itérative à un order élevé de convergence, Mathématica, 12(35), no. 2, pp. 309–324, 1970.
4: Păvăloiu, I. and Pop, N., Interpolare şi aplicaţii , Editura Risoprint, Cluj-Napoca, 2005.
5: Petković, L. D., Petković, M. S. and Z̆iviković, D., Hansen-Patrick’s family is of Laguerre’s type, Novi Sad J. Math., 33, no. 1, pp. 109–115, 2003.
6: Petrović, M., Tričković, S. and Herceg, D., Higher order Euler-like methods, Novi Sad J. Math., 28, no. 3, pp. 129–136, 1998.
7: Varona, J., Graphic and numerical comparison between iterative methods, The Mathematical Intelligencer, 24, no. 1, pp. 37–46, 2002.
8: Ye, X. and Li, C., Convergence of the family of the deformed Euler-Halley iterations under the Hölder condition of the second derivative, Journal of Computational and Applied Mathematics, 194, pp. 294–308, 2006.