View of The convergence of the Euler's method

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₀ ∈[a, b], n= 0,1, ..., n∈N, wherex₀ 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(xn)

f⁰(xn)+√

[f⁰(xn)]²−2f(xn)f⁰⁰(xn), x₀∈[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₀ ∈∆, where ∆ ={x ∈R:|x−x₀| ≤ δ} ⊆[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⁽ⁱ⁾(x)ϕⁱ(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¹

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| ≤ ^ηµ_λ^sn0 , for anyn= 0,1, ..., n∈N; iii) |x^∗−xn| ≤ ^ηµsn0

λ(1−µ^sn₀ ), 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₀| ≤δ} ⊆[a, b], verify the relations a) the functionf is of class C³(∆) and sup

x∈∆

|f⁰⁰⁰(x)|=M <∞;

b)

1 f⁰(x)

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

c) ^f_[f^(x)f0(x)]^00(x)2

not= L_f(x)≤ ¹₂ for everyx∈∆;

d) λ= q8M

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−µ³₀ⁿ), n= 0,1,2, ..., n∈N. Proof. We consider the functionϕof form

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

f⁰(x)+√

[f⁰(x)]²−2f(x)f⁰⁰(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₁−x₀|=

f(x0) f⁰(x0)

2 1+√

1−2Lf(x0)

≤2

f(x0) f⁰(x0)

≤

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

0) ≤δ⇒x₁ ∈∆.

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

ϕ(x) = ^−f

0(x)+√

[f⁰(x)]²−2f(x)f⁰⁰(x)

f⁰⁰(x) =

=−^f0(x)−

√

[f⁰(x)]²−2f(x)f⁰⁰(x) f⁰⁰(x) ,

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

ax²+bx+c= 0, wherec=f(x), b=f⁰(x), a= ^f00₂^(x), we get

|f(x₁)| ≤

f(x1)− f(x0) +f⁰(x0)(x1−x0) +¹₂f⁰⁰(x0)(x1−x0)² + +

f(x0) +f⁰(x0)(x1−x0) +¹₂f⁰⁰(x0)(x1−x0)² ≤

≤

f⁰⁰⁰(ξ)

3! (x1−x0)³ +

f(x0) +f⁰(x0)ϕ(x0) +¹₂f⁰⁰(x0)ϕ²(x0) ≤

≤ ^M_3! |x₁−x₀|³≤ ^{8M β}_3! ³ |f(x₀)|³= ^µ_λ³⁰, ξ∈∆.

Because

1 f⁰(x1)

≤β, we have that

|x₂−x1|=

f(x1) f⁰(x1)

2 1+

r

1−2f(x1)f⁰⁰(x1) [f⁰(x1)]²

≤2

f(x1) f⁰(x1)

≤2β|f(x1)| ≤ ^2βµ_λ³⁰. 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⁰(xn)

2 1+

r

1−2f(xn)f⁰⁰(xn) [f⁰(xn)]²

≤ ^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βµ³₀ⁱ

λ ≤ ^2βµ_λ⁰(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βµ³₀ⁱ

λ <

(7)

< ^2βµ3

n 0

λ (1 +µ³₀ⁿ⁺¹⁻³ⁿ+...+µ³₀^n+p−1−3n)

< ^2βµ3

n 0

λ(1−µ³₀ⁿ), p∈N, n= 0,1,2, ..., n∈N.

Because µ₀ < 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−µ³₀ⁿ), 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→∞

µ³₀ⁿ λ = 0, that is, f(x^∗) = 0.

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

|x^∗−x0| ≤ ^2βµ300

λ(1−µ³⁰₀ ) ≤δ,

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₁(x) = ln(x²−3), x^∗ =−2, x∈[−2.35,−1.9], f2(x) =x³−3x²−13x+ 15, x^∗= 5, x∈[4.5,5.5], f₃(x) =x⁵−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₁⁰(x) = _−3+x^2x 2, f₁⁰⁰(x) = _(−3+x^−4x22)² +_−3+x² 2,

f₁⁰⁰⁰(x) = _(−3+x^16x32)³ −_(−3+x^12x₂₎₂, from which we get β = 0.536702 andM = 422.22;

f₂⁰(x) = 3x²−6x−13, f₂⁰⁰(x) = 6x−6, f₂⁰⁰⁰(x) = 6, from which we get β = 0.0481928 andM = 6;

f₃⁰(x) = 5x⁴, f₃⁰⁰(x) = 20x³, f₃⁰⁰⁰(x) = 60x², from which we get β = 0.333503 andM = 114.264.

In the Table 1 are listed the values for x₀,M,β,λ,µ₀, δ 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.