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) xn+1=g(xn), x0 ∈[a, b], n= 0,1, ..., n∈N, wherex0 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) xn+1=xn− 2f(xn)
f0(xn)+√
[f0(xn)]2−2f(xn)f00(xn), x0∈[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{xn}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 x0 ∈∆, where ∆ ={x ∈R:|x−x0| ≤ δ} ⊆[a, b], we could assure that the following relations hold
a) the function f is of class Cs(∆), 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−11
and λ(1−µηµ0
0) ≤δ;
then the sequence {xn}n≥0 generated by (2)has the following properties:
i) it is convergent, and if x∗ = lim
n→∞xn thenf(x∗) = 0 and x∗ ∈∆;
ii) |xn+1−xn| ≤ ηµλsn0 , for anyn= 0,1, ..., n∈N; iii) |x∗−xn| ≤ ηµsn0
λ(1−µsn0 ), 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 {xn}n≥0 given by (3).
Theorem 2. If the function f, the real number δ >0 and x0 ∈∆,where
∆ ={x∈R:|x−x0| ≤δ} ⊆[a, b], verify the relations a) the functionf is of class C3(∆) and sup
x∈∆
|f000(x)|=M <∞;
b)
1 f0(x)
≤β for everyx∈∆, β ∈R, β >0;
c) f[f(x)f0(x)]00(x)2
not= Lf(x)≤ 12 for everyx∈∆;
d) λ= q8M
3! β3>0;
e) µ0 =λ|f(x0)|<1;
f) λ(1−µ2βµ0
0) ≤δ;
then the sequence{xn}n≥0 generated by(3)is convergent, and ifx∗ = lim
n→∞xn, the next relations hold
i) f(x∗) = 0 and x∗∈∆;
ii) xn∈∆, n= 0,1,2..., n∈N; iii) |f(xn)| ≤ µ3
n 0
λ , n= 0,1,2, ..., n∈N;
iv) |x∗−xn| ≤ 2βµ3
n 0
λ(1−µ30n), n= 0,1,2, ..., n∈N. Proof. We consider the functionϕof form
ϕ(x) =− 2f(x)
f0(x)+√
[f0(x)]2−2f(x)f00(x), x∈∆.
We’ll show that the elements of the sequence{xn}n≥0 generated by (3) are in
∆.
By conditions b), c) and f) we have
|x1−x0|=
f(x0) f0(x0)
2 1+√
1−2Lf(x0)
≤2
f(x0) f0(x0)
≤
≤2β|f(x0)|= 2λβ|f(xλ 0)|< λ(1−µ2βµ0
0) ≤δ⇒x1 ∈∆.
Applying the Taylor expansion of function f around x0 and taking into account that
ϕ(x) = −f
0(x)+√
[f0(x)]2−2f(x)f00(x)
f00(x) =
=−f0(x)−
√
[f0(x)]2−2f(x)f00(x) f00(x) ,
∀x∈∆, andϕ(x) is verifying the parable
ax2+bx+c= 0, wherec=f(x), b=f0(x), a= f002(x), we get
|f(x1)| ≤
f(x1)− f(x0) +f0(x0)(x1−x0) +12f00(x0)(x1−x0)2 + +
f(x0) +f0(x0)(x1−x0) +12f00(x0)(x1−x0)2 ≤
≤
f000(ξ)
3! (x1−x0)3 +
f(x0) +f0(x0)ϕ(x0) +12f00(x0)ϕ2(x0) ≤
≤ M3! |x1−x0|3≤ 8M β3! 3 |f(x0)|3= µλ30, ξ∈∆.
Because
1 f0(x1)
≤β, we have that
|x2−x1|=
f(x1) f0(x1)
2 1+
r
1−2f(x1)f00(x1) [f0(x1)]2
≤2
f(x1) f0(x1)
≤2β|f(x1)| ≤ 2βµλ30. From all that we have proved above, by using the induction, it results that the property iii) holds for every n∈N,
(4) |f(xn)| ≤ µ3
n 0
λ .
Analogously, from b), c) and (4) we can prove the following relation (5) |xn+1−xn|=
f(xn) f0(xn)
2 1+
r
1−2f(xn)f00(xn) [f0(xn)]2
≤ 2βµ3
n 0
λ , n= 0,1, ..., n∈N. From (5), e) and f) we get the relation ii)
|xn+1−x0| ≤
n
X
i=0
|xi+1−xi| ≤ (6)
≤
n
X
i=0 2βµ30i
λ ≤ 2βµλ0(1 +µ3−10 +µ302−1+...+µ30n−1)
< λ(1−µ2βµ0
0) ≤δ⇒xn+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
|xn+p−xn| ≤
n+p−1
X
i=n
|xi+1−xi| ≤
n+p−1
X
i=n 2βµ30i
λ <
(7)
< 2βµ3
n 0
λ (1 +µ30n+1−3n+...+µ30n+p−1−3n)
< 2βµ3
n 0
λ(1−µ30n), p∈N, n= 0,1,2, ..., n∈N.
Because µ0 < 1, it results that the sequence {xn}n≥0 is fundamental, so according to the Cauchy’s theorem, it is convergent.
If x∗ = lim
n→∞xn, for p → ∞, from the inequality (7) we obtain the relation iv)
(8) |x∗−xn| ≤ 2βµ3
n 0
λ(1−µ30n), 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→∞
µ30n λ = 0, that is, f(x∗) = 0.
From f) and the inequality (8) forn= 0, we obtain
|x∗−x0| ≤ 2βµ300
λ(1−µ300 ) ≤δ,
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.
f1(x) = ln(x2−3), x∗ =−2, x∈[−2.35,−1.9], f2(x) =x3−3x2−13x+ 15, x∗= 5, x∈[4.5,5.5], f3(x) =x5−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 f10(x) = −3+x2x 2, f100(x) = (−3+x−4x22)2 +−3+x2 2,
f1000(x) = (−3+x16x32)3 −(−3+x12x2)2, from which we get β = 0.536702 andM = 422.22;
f20(x) = 3x2−6x−13, f200(x) = 6x−6, f2000(x) = 6, from which we get β = 0.0481928 andM = 6;
f30(x) = 5x4, f300(x) = 20x3, f3000(x) = 60x2, from which we get β = 0.333503 andM = 114.264.
In the Table 1 are listed the values for x0,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.
