Rev. Anal. Num´er. Th´eor. Approx., vol. 39 (2010) no. 1, pp. 87–92 ictp.acad.ro/jnaat

THE CONVERGENCE OF THE EULER’S METHOD

RALUCA ANAMARIA (POMIAN) SALAJAN^{∗}

Abstract. 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 2000. 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

(1) f(x) = 0,

where f : [a, b]⊂R→ Ris an analytic function with simple roots. This zero can be determined as a fixed point of some iteration functionsg: [a, b]→[a, b], by means of the one-point iteration method

(2) x_{n+1}=g(x_{n}), x_{0} ∈[a, b], n= 0,1, ..., n∈N,
wherex_{0} is the starting value and g is a function of form

g(x) =x+ϕ(x).

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

(3) x_{n+1}=x_{n}− ^{2f(x}^{n}^{)}

f^{0}(xn)+√

[f^{0}(xn)]^{2}−2f(xn)f^{00}(xn), x_{0}∈[a, b], n≥0, n∈N.
The Euler’s method has been rediscovered by several authors, see for exam-
ple [1], [2], [5], [6], [7], [8], and references therein.

∗Secondary School Vasile Alecsandri, Strada P˘a¸sunii, Nr. 2A, Baia Mare, Romania, e- mail: [email protected]

2. THEOREMS OF CONVERGENCE

Next we will study sufficient conditions in order that the sequence{x_{n}}_{n≥0}
generated through (3) would be convergent, and if x^{∗} = lim

n→∞xn, then
f(x^{∗}) = 0.

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

Theorem1. ([3], [4])If we consider the functionf, the real number δ >0
and x_{0} ∈∆, where ∆ ={x ∈R:|x−x_{0}| ≤ δ} ⊆[a, b], we could assure that
the following relations hold

a) the function f is of class C^{s}(∆), s ≥ 2, s ∈ N and sup

x∈∆

f^{(s)}(x)
=
M <∞;

b) we have the relation

s−1

P

i=0 1

i!f^{(i)}(x)ϕ^{i}(x)

≤γ|f(x)|^{s} for every
x∈∆,where γ ∈R,γ ≥0;

c) the functionϕverifies the relation |ϕ(x)| ≤η|f(x)|,for everyx∈∆, where η∈R, η >0;

d) the numbers λ, η, M and δ verify the relations:

µ0 =λ|f(x0)|<1, where λ=

γ+^{M η}_{s!}^{s}
_{s−1}^{1}

and _{λ(1−µ}^{ηµ}^{0}

0) ≤δ;

then the sequence {x_{n}}_{n≥0} generated by (2)has the following properties:

i) it is convergent, and if x^{∗} = lim

n→∞x_{n} thenf(x^{∗}) = 0 and x^{∗} ∈∆;

ii) |x_{n+1}−xn| ≤ ^{ηµ}_{λ}^{sn}^{0} , for anyn= 0,1, ..., n∈N;
iii) |x^{∗}−xn| ≤ ^{ηµ}^{sn}^{0}

λ(1−µ^{sn}_{0} ), n= 0,1,2, ..., n∈N.

Proof. See [3], [4].

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

Theorem 2. If the function f, the real number δ >0 and x0 ∈∆,where

∆ ={x∈R:|x−x_{0}| ≤δ} ⊆[a, b], verify the relations
a) the functionf is of class C^{3}(∆) and sup

x∈∆

|f^{000}(x)|=M <∞;

b)

1
f^{0}(x)

≤β for everyx∈∆, β ∈R, β >0;

c) ^{f}_{[f}^{(x)f}0(x)]^{00}^{(x)}^{2}

not= L_{f}(x)≤ ^{1}_{2} for everyx∈∆;

d) λ= q8M

3! β^{3}>0;

e) µ0 =λ|f(x0)|<1;

f) _{λ(1−µ}^{2βµ}^{0}

0) ≤δ;

then the sequence{x_{n}}_{n≥0} generated by(3)is convergent, and ifx^{∗} = lim

n→∞x_{n},
the next relations hold

i) f(x^{∗}) = 0 and x^{∗}∈∆;

ii) x_{n}∈∆, n= 0,1,2..., n∈N;
iii) |f(xn)| ≤ ^{µ}^{3}

n 0

λ , n= 0,1,2, ..., n∈N;

iv) |x^{∗}−x_{n}| ≤ ^{2βµ}^{3}

n 0

λ(1−µ^{3}_{0}^{n}), n= 0,1,2, ..., n∈N.
Proof. We consider the functionϕof form

ϕ(x) =− ^{2f(x)}

f^{0}(x)+√

[f^{0}(x)]^{2}−2f(x)f^{00}(x), x∈∆.

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

∆.

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

|x_{1}−x_{0}|=

f(x0)
f^{0}(x0)

2 1+√

1−2Lf(x0)

≤2

f(x0)
f^{0}(x0)

≤

≤2β|f(x_{0})|= ^{2λβ|f(x}_{λ} ^{0}^{)|}< _{λ(1−µ}^{2βµ}^{0}

0) ≤δ⇒x_{1} ∈∆.

Applying the Taylor expansion of function f around x0 and taking into account that

ϕ(x) = ^{−f}

0(x)+√

[f^{0}(x)]^{2}−2f(x)f^{00}(x)

f^{00}(x) =

=−^{f}^{0}^{(x)−}

√

[f^{0}(x)]^{2}−2f(x)f^{00}(x)
f^{00}(x) ,

∀x∈∆, andϕ(x) is verifying the parable

ax^{2}+bx+c= 0, wherec=f(x), b=f^{0}(x), a= ^{f}^{00}_{2}^{(x)},
we get

|f(x_{1})| ≤

f(x1)− f(x0) +f^{0}(x0)(x1−x0) +^{1}_{2}f^{00}(x0)(x1−x0)^{2}
+
+

f(x0) +f^{0}(x0)(x1−x0) +^{1}_{2}f^{00}(x0)(x1−x0)^{2}
≤

≤

f^{000}(ξ)

3! (x1−x0)^{3}
+

f(x0) +f^{0}(x0)ϕ(x0) +^{1}_{2}f^{00}(x0)ϕ^{2}(x0)
≤

≤ ^{M}_{3!} |x_{1}−x_{0}|^{3}≤ ^{8M β}_{3!} ^{3} |f(x_{0})|^{3}= ^{µ}_{λ}^{3}^{0}, ξ∈∆.

Because

1
f^{0}(x1)

≤β, we have that

|x_{2}−x1|=

f(x1)
f^{0}(x1)

2 1+

r

1−2f(x1)f^{00}(x1)
[f^{0}(x1)]^{2}

≤2

f(x1)
f^{0}(x1)

≤2β|f(x1)| ≤ ^{2βµ}_{λ}^{3}^{0}.
From all that we have proved above, by using the induction, it results that
the property iii) holds for every n∈N,

(4) |f(x_{n})| ≤ ^{µ}^{3}

n 0

λ .

Analogously, from b), c) and (4) we can prove the following relation
(5) |x_{n+1}−x_{n}|=

f(xn)
f^{0}(xn)

2 1+

r

1−2f(xn)f^{00}(xn)
[f^{0}(xn)]^{2}

≤ ^{2βµ}^{3}

n 0

λ , n= 0,1, ..., n∈N. From (5), e) and f) we get the relation ii)

|x_{n+1}−x0| ≤

n

X

i=0

|x_{i+1}−xi| ≤
(6)

≤

n

X

i=0
2βµ^{3}_{0}^{i}

λ ≤ ^{2βµ}_{λ}^{0}(1 +µ^{3−1}_{0} +µ^{3}_{0}^{2}^{−1}+...+µ^{3}_{0}^{n}^{−1})

< _{λ(1−µ}^{2βµ}^{0}

0) ≤δ⇒x_{n+1} ∈∆, n= 0,1,2, ..., n∈N.

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

|x_{n+p}−x_{n}| ≤

n+p−1

X

i=n

|x_{i+1}−x_{i}| ≤

n+p−1

X

i=n
2βµ^{3}_{0}^{i}

λ <

(7)

< ^{2βµ}^{3}

n 0

λ (1 +µ^{3}_{0}^{n+1}^{−3}^{n}+...+µ^{3}_{0}^{n+p−1}^{−3}^{n})

< ^{2βµ}^{3}

n 0

λ(1−µ^{3}_{0}^{n}), p∈N, n= 0,1,2, ..., n∈N.

Because µ_{0} < 1, it results that the sequence {x_{n}}_{n≥0} is fundamental, so
according to the Cauchy’s theorem, it is convergent.

If x^{∗} = lim

n→∞x_{n}, for p → ∞, from the inequality (7) we obtain the
relation iv)

(8) |x^{∗}−xn| ≤ ^{2βµ}^{3}

n 0

λ(1−µ^{3}_{0}^{n}), n= 0,1,2, ..., n∈N.

We show now that the relations i) hold, that is,x^{∗} is a root of equation (1)
and x^{∗} ∈∆.

From the continuity of functionf and from (4) for n→ ∞,it results
0≤ |f(x^{∗})| ≤ lim

n→∞

µ^{3}_{0}^{n}
λ = 0,
that is, f(x^{∗}) = 0.

From f) and the inequality (8) forn= 0, we obtain

|x^{∗}−x0| ≤ ^{2βµ}^{30}^{0}

λ(1−µ^{30}_{0} ) ≤δ,

so, x^{∗} ∈∆.

It is evidently that all the assumptions of Theorem 1 are verified for s= 3, γ = 0 and η= 2β.

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 zerosx^{∗}
found.

f_{1}(x) = ln(x^{2}−3), x^{∗} =−2, x∈[−2.35,−1.9],
f2(x) =x^{3}−3x^{2}−13x+ 15, x^{∗}= 5, x∈[4.5,5.5],
f_{3}(x) =x^{5}−1, x^{∗} = 1, x∈[0.88,1.38].

For the derivatives of order 1, 2 and 3 offi, i= 1,2,3, we have the relations
f_{1}^{0}(x) = _{−3+x}^{2x} 2, f_{1}^{00}(x) = _{(−3+x}^{−4x}^{2}2)^{2} +_{−3+x}^{2} 2,

f_{1}^{000}(x) = _{(−3+x}^{16x}^{3}2)^{3} −_{(−3+x}^{12x}_{2}_{)}_{2},
from which we get β = 0.536702 andM = 422.22;

f_{2}^{0}(x) = 3x^{2}−6x−13, f_{2}^{00}(x) = 6x−6, f_{2}^{000}(x) = 6,
from which we get β = 0.0481928 andM = 6;

f_{3}^{0}(x) = 5x^{4}, f_{3}^{00}(x) = 20x^{3}, f_{3}^{000}(x) = 60x^{2},
from which we get β = 0.333503 andM = 114.264.

In the Table 1 are listed the values for x_{0},M,β,λ,µ_{0}, δ and _{λ(1−µ}^{2βµ}^{0}

0), for each test functions.

i x0 M β λ µ0 δ _{λ(1−µ}^{2βµ}^{0}

0) < δ 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 atx^{∗}.

i x0 x1 x2 x3=x^{∗}

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.

REFERENCES

[1] Amat, S.,Busquier, S.andPlaza, 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˘av˘aloiu, I.,Sur les proced´ees it´erative `a un order ´elev´e de convergence, Math´ematica, 12(35), no. 2, pp. 309–324, 1970.

[4] P˘av˘aloiu, I. and Pop, N., Interpolare ¸si aplicat¸ii , Editura Risoprint, Cluj-Napoca, 2005.

[5] Petkovi´c, L. D., Petkovi´c, M. S.andZivikovi´˘ c, D.,Hansen-Patrick’s family is of Laguerre’s type, Novi Sad J. Math.,33, no. 1, pp. 109–115, 2003.

[6] Petrovi´c, M.,Triˇckovi´c, S.andHerceg, 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 Mathe- matical 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¨older condition of the second derivative, Journal of Computational and Applied Mathematics,194, pp. 294–308, 2006.

Received by the editors: October 23, 2010.