Volume 22, No. 2, June 2009
A STUDY ON CONVERGENCE OF EXTENDED LEAP-FROGGING NEWTON’S METHOD LOCATING
MULTIPLE ZEROS
Young Hee Geum*
Abstract. Assuming that a given nonlinear function f : R → R has a zero α with integer multiplicity m ≥ 1 and is sufficiently smooth in a small neighborhood of α, we define extended leap- frogging Newton’s method. We investigate the order of conver- gence and the asymptotic error constant of the proposed method as a function of multiplicity m. Numerical experiments for various test functions show a satisfactory agreement with the theory pre- sented in this paper and are throughly verified via Mathematica programming with its high-precision computability.
1. Introduction
Traub[10] and Kasturiarachi[6] introduced leap-frogging Newton’s me thod that is also called the Newton-secant method. They investigated convergence behavior of the method for a simple zero. For a given non- linear equation f (x) = 0, unlike the usual approach as shown in [10], Geum[5] has adopted a different approach to show the correct asymp- totic error constant as 14(f00(α)/f0(α))2 with cubic convergence at a simple root α.
In this paper, we describe extended leap-frogging Newton’s method and its convergence properties for a multiple root with inetger multiplic- ity. Our main aim is to express the asymptotic error constant[1-3,8,9] for the method in terms of the root multiplicity. We show that it converges cubically[4,7] to a simple root and quadratically to a multiple root.
Received March 23, 2009; Revised May 20, 2009; Accepted May 21, 2009.
2000 Mathematics Subject Classification: Primary 65H05, 65H99.
Key words and phrases: leap-frogging Newton’s method, cubic convergence, as- ymptotic error constant, multiple root, simple root.
Research of Y. H. Geum was supported by the Korean Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2006-352-00006).
Let f : R → R have a root α with integer multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. We rewrite f (x) = 0 in the form x = g(x) with g : R → R which is sufficiently smooth in a small neighborhood of α. Suppose that the iterative function g(x) is defined by
g(x) =
½ x − H(x), if x 6= α
x − limx→αH(x), if x = α, (1.1) where
H(x) = λf (x)2
f0(x) · (f (x) − f (z)), z = x − mh(x), (1.2) h(x) =
½ f (x)/f0(x), if x 6= α limx→αf (x)/f0(x), if x = α,
and λ is a constant parameter to be chosen for maximal order of con- vergence. Hence our proposed numerical method is given by
xn+1 = g(xn), n = 0, 1, 2, · · · , (1.3) and is called extended leap-frogging Newton’s method. As expected with λ = m = 1, it becomes leap-frogging Newton’s method.
The following lemma describing some local properties of h(x) can be easily proved by repeated use of L’Hospital’s rule and Leibnitz’s rule for differentiation.
Lemma 1.1. In view of multiplicity of α, let c=ff(m+1)(m)(α)(α), d =
f(m+2)(α)
f(m)(α) . Then the function h(x) and its derivatives up to order 3 evaluated at α are found to be the following:
(i) h(α) = 0 (ii) h0(α) = m1
(iii) h00(α) = −m2(m+1)2 c (iv) h000(α) = m2(m+1)6
n1
mc2−m+22 d o
From Eq.(1.1), we need to investigate some local properties of g(x) in a small neighborhood of α. From the definition of g(x) as described in Eq.(1.1), we rewrite
(g − x) · f0(x)(f (x) − f (z)) = −λ · f (x)2. (1.4)
Using Eq.(1.4), our aim is to establish some relationships between λ, m, g0(α), g00(α) and g000(α), for maximal order of convergence. The next lemma is useful to calculate g0(α), g00(α) and g000(α).
Lemma 1.2. Let f : R → R have a multiple root α with multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. Let z(x) = x − mh(x) and h(x) be defined by Eq.(1.1). Let p ≥ 0 be an integer. Then the following hold:
(i) If m = 1, then dp
dxpf (z)
¯¯
¯¯
¯x=α
=
0, if p = 0, 1
f00(α), if p = 2
−f0(α)h000(α), if p = 3
−f0(α)h(4)(α) + 3f00(x)h00(α)2, if p = 4
(1.5)
(ii) If m ≥ 2, then dp dxpf (z)
¯¯
¯¯
¯x=α
= [f (z)](p)|x=α= 0 f or 0 ≤ p ≤ m + 1 (1.6) Proof. We first try to get an insight for f (z) with lower values of p as follows.
If p = 0, then
f (z)|x=α= f (z(α)) = f (α) = 0.
If p = 1, then
f0(z) · z0|x=α= f0(α) · z0(α) = f0(α) · (1 − mh0)(α) = f0(α) · 0 = 0.
If p = 2, then
f00(z) · z02|x=α+ f0(z) · z00|x=α = 0.
If p = 3, then f000(z) · z03
¯¯
¯¯
¯x=α
+(1 + 2)f00(z) · z0· z00|x=α+ f0(z) · z000|x=α = 0.
If p = 4, then
f(4)(z) · z04+ (1 + 2 + 3)f(3)(z) · z02· z00+ (1 + 2)f00(z) · (z0· z000+ z002) +f00(z) · z0· z000+ f0(z) · z(4)
¯¯
¯¯
¯x=α
= 0.
Continuing in this manner, we get the following expression when m ≥ k and p = k + 1:
· f (z)
¸(p)
x=α
= f(k+1)(z) · z0(k+1)+k(k + 1)
2 f(k)(z) · z0(k−1)· z00 +
k−1X
j=1
f(j)(z) · φj(z(1), z(2), · · · z(k+1))
¯¯
¯¯
x=α
= 0,
where φj(z(1), z(2), · · · z(k+1)) is a nonlinear function of variables z(1), z(2),
· · · z(k+1) and φj|x=α has a finite value.
Now we put k = m and have [f (z)](p)x=α = 0 for (0 ≤ p ≤ m + 1) , when m ≥ 2. But when m = 1, we get the following relations by direct computation:
[f (z)](p)|x=α =
0, if p = 0, 1
f00(α), if p = 2
−f0(α)h000(α), if p = 3
−f0(α)h(4)(α) + f00(x)h00(α)2, if p = 4, from which the proof is completed.
2. Convergence analysis
In this section, we investigate the order of convergence p and the asymptotic error constant η of extended leap-frogging Newton’s method.
We differentiate 2m times both sides of Eq(1.6) with respect to x and substitute x = α to obtain
·
(g − x) · f0(x) {f (x) − f (z)}
¸(2m)
x=α
= −λ
· f (x)2
¸(2m)
x=α
= X2m r=0
µ2m r
¶
(g − x)(2m−r)(x) · [f0(x) · {f (x) − f (z)}](r)
¯¯
¯¯
x=α
= −λ X2m r=0
µ2m r
¶
f(r)(x) · f(2m−r)(x)
¯¯
¯¯
x=α
. (1.7)
In the third of Eq.(1.7) with 0 ≤ r ≤ 2m − 1 , we calculate the range of value r such that [f0(x) · f (x) − f (z)](r)x=α 6= 0. We find f (α) = f0(α) =
· · · = f(m−1)(α) = 0, f(m)(α) 6= 0 in view of multiplicity m. Therefore, we have ·
f (z)
¸(p)
x=α
=
½ f00(α), if m = 1, p = 2
0, otherwise.
When m ≥ 2, for 0 ≤ p ≤ m + 1, we find
r ≥ m − 1 + m = 2m − 1.
If r = 2m − 1, we have
·
f0(x) · {f (x) − f (z)}
¸(2m−1)
x=α
=
µ2m − 1 m − 1
¶
f(m)(α) · f(m)(α).
We evaluate Eq.(1.7) at x = α by Lemma 1.2. In Eq.(1.7), all the terms of the left side vanishes except for the values of r = 2m − 1 to yield:
2m · (g0− 1) ·
µ2m − 1 m − 1
¶
f(m)(α)2 = −λ µ2m
m
¶
· f(m)(α)2.
Next we determine the value λ such that g0(α) = 0 when m ≥ 2 and find
λ = (2m)!
m!(m − 1)!
Á(2m)!
m!m! = m. (1.8)
We put m = 1 in Eq.(1.7) to obtain X2
r=0
µ2 r
¶
(g − x)(2−r)
¯¯
¯¯
x=α
·
·
f0(x) {f (x) − f (z)}
¸(r)
x=α
= −2λf0(α)2 µ2
1
¶
(g0− 1) ·
·
f0(x) {f (x) − f (z)}
¸
x=α
= 2(−1) · f0(α)2 = −2λf0(α)2. Thus
λ = 1. (1.9)
Combining Eq.(1.8) with Eq.(1.9), we choose λ = m for all integers m ≥ 1. To find g00(α), we first differentiate 2m + 1 times both sides of Eq(1.4) with respect to x and substitute x = α as follows.
·
(g − x) · f0(x) · {f (x) − f (z)}
¸(2m+1)
x=α
= −2λ
½ f (x)2
¾(2m+1)
x=α
=
2m+1X
r=0
µ2m + 1 r
¶
(g − x)(2m+1−r)
¯¯
¯¯
x=α
·©
f0(x)[f (x) − f (z)]ª(r)
x=α
= −2λ
2m+1X
r=0
µ2m + 1 r
¶
f (x)(r)· f (x)(2m+1−r)
¯¯
¯¯
x=α
. (1.10)
When 0 ≤ r ≤ 2m in the left side of Eq.(1.10), we choose the range of value r such that [f0(x) · {f (x) − f (z)}](r)x=α 6= 0.
When m ≥ 2, we get (i) r = 2m − 1
·
f0(x) · {f (x) − f (z)}
¸(2m−1)
x=α
=
µ2m − 1 m − 1
¶
· f(m)(α)2. (ii) r = 2m
·
f0(x) · {f (x) − f (z)}
¸(2m)
x=α
=
·µ2m m
¶ +
µ 2m m − 1
¶¸
f(m)(α) · f(m+1)(α).
Therefore, we let g0(α) = 0 in the left side of Eq.(1.10) to find the following.
(2m + 1)(g0(α) − 1) ·
·µ2m m
¶ +
µ 2m m − 1
¶¸
f(m)(α)f(m+1)(α) + (2m + 1)2m
2
µ2m − 1 m
¶
g00(α)f(m)(α)2
= −λ
·µ2m + 1 m
¶
f(m)(α)f(m+1)(α) +
µ2m + 1 m + 1
¶
f(m+1)(α)f(m)(α)
¸ . Hence we obtain with λ = m after some algebraic manipulation:
g00(α) = 2 m(m + 1)
f(m+1)(α)
f(m)(α) , m ≥ 2.
When m = 1, substituting m = 1 into Eq.(1.10) yields X3
r=0
µ3 r
¶
(g − x)(3−r)
¯¯
¯¯
x=α
·[f0(x) {f (x) − f (z)}
¸(r)
x=α
= −6f0(α)f00(α) = 3g00(α)f00(α)2− 3 · 2f0(α)f00(α) and
g00(α) = 0.
Hence we need to further investigate g000(α) with m = 1. Differentiating 4 times both sides of Eq(1.6) with respect to x and substituting x = α leads us to the equation below:
X4 r=0
µ4 r
¶
(g − x)(4−r)|x=α·
·
f0(x) {f (x) − f (z)}
¸(r)
x=α
= −λ X4 r=0
µ4 r
¶
f (α)(r)f (α)(4−r)
= µ4
1
¶
g000(α) · f0(α)2+ µ4
2
¶ g00(α) ·
·
f0(x) {f (x) − f (z)}(2)x=α
¸
+ µ4
3
¶
(g0(α) − 1) ·
·
f0(x) {f (x) − f (z)}(3)x=α
¸
= −λ
½µ4 1
¶
f0(α)f000(α) + µ4
2
¶
f00(α)2+ µ4
3
¶
f000(α)f0(α)
¾ .
After substituting λ = m = 1 into the above equation and rearranging, we obtain
g000(α) = 3 2
à f00(α)
f0(α)
!2 .
As a result of the preceeding discussion, we state the main theorem regarding the convergence of extended leap-frogging Newton’s method.
Theorem 2.1. Let f : R → R have a zero α with integer multiplicity m ≥ 1 and be sufficiently smooth in a small neighborhood of α. Let x0 be an initial guess chosen in a sufficiently small neighborhood of α.
Then extended leap-frogging Newton’s method(1.3) has order p and its asymptotic error constant η as follows:
p =
½ 2, if m ≥ 2
3, if m = 1
η =
1 m(m+1)
f(m+1)(α)
f(m)(α) , if m ≥ 2
14 ·
³f00(α) f0(α)
´2
, if m = 1.
3. Algorithm, numerical results and discussions
The symbolic and computational ability of Mathematica[11] leads us to a zero-finding algorithm based on the analysis studied in Sections 1 and 2.
Algorithm 3.1 (Zero-Finding Algorithm)
Step 1. For k ∈ N ∪ {0}, construct iteration scheme (1.1) with the given function f at a multiple zero α as stated in Section 1.
Step 2. Set the minimum number of precision digits. With exact zero α or most accurate zero, supply the theoretical asymptotic error constant
η. Set the error range ², the maximum iteration number nmax and the initial value x0. Compute f (x0) and |x0− α |.
Step 3. Compute xn+1 in (1.1) for 0 ≤ n ≤ nmax and display the computed values of n, xn, f (xn), |xn− α|, |en+1/enp| and η.
In these experiments, we choose 250 as the minimum number of digits of precision by assigning $MinPrecision=250 in Mathematica to achieve the specified nominal accuracy. We set the error bound ² to 0.5 × 10−235 for | xn−α | < ² and evaluate the nthorder derivative of the complicated nonlinear functions using the Mathematica command D[f, {x, n}].
As an example for the convergence of extended leap-frogging New- ton’s method, we first illustrate the order of convergence and the as- ymptotic error constant with a function
f (x) = (1 + x2) cos(πx/8)
having a simple real zero α = 4.0. We choose x0 = 3.49 as an ini- tial guess. Table 1 lists the numerical results for approximated zeros of f (x) computed with Mathematica programming and verifies cubic con- vergence apparently. As a second example, we illustrate the order of convergence and the asymptotic error constant with a function
f (x) = n
x10−√
3x3cos(πx/6) + 1/(x2+ 1) o
(x − 1)
having a multiple real zero α = 1 of multiplicity 2. We choose x0= 0.92 as an initial guess. Table 2 shows a good agreement with the theory developed in this paper.
Table 1. Convergence for f (x) = (1 + x2) cos(πx/8)
n xn f (xn) | xn− α | en+1/en3 η
0 3.49000000000000 2.62205 0.510000 0.2214532872
1 3.94534313747757 0.355535 0.0546569 0.4120350583 2 3.99996137559441 0.000257847 0.0000386244 0.2365525937 3 3.99999999999999 8.51915 × 10−14 1.27611 × 10−14 0.2214635569 4 4.00000000000000 3.07223 × 10−42 4.60199 × 10−43 0.2214532872 5 4.00000000000000 1.44088 × 10−127 2.15833 × 10−128 0.2214532872 6 4.00000000000000 0.0 × 10−248 0.0 × 10−249
As another numerical example to confirm the convergence, we take f (x) = (−1 + e−30+7x+x2)(−3 + x)2
with a zero 3 of multiplicity 3. Table 3 clearly reflects the theoretical convergence presented in this paper. The computed asymptotic error
Table 2. Convergence of the extended leap-frogging Newton’s method for
f (x) =©
x10−√
3x3cos(πx/6) + 1/(x2+ 1)ª
(x − 1)
n xn f (xn) | xn− α | en+1/en2 η
0 0.920000000000000 -0.00501924 0.800000
1 0.991249484161490 -0.0000440460 0.0121355 1.367268100 3.03354251 2 0.999794338683744 −2.31460 × 10−8 0.000360502 2.685871931
3 0.999999872081448 −8.94329 × 10−15 3.35582 × 1−−7 3.024323988 4 0.999999999999950 −1.34667 × 10−27 2.91278 × 10−14 3.033536758 5 1.00000000000000 −3.05348 × 10−53 2.19446 × 10−27 3.033542510 6 1.00000000000000 −1.56986 × 10−104 1.24557 × 10−52 3.033542510 7 1.00000000000000 −4.14947 × 10−207 4.01279 × 10−104 3.033542510 8 1.00000000000000 −2.89905 × 10−412 4.16489 × 10−207 3.033542510 9 1.00000000000000 −2.89905 × 10−799 −2.89905 × 10−400
constants are in good agreement with theoretical asymptotic error con- stants η up to 10 significant digits. The computed root is rounded to be accurate up to the 235 significant digits.
Table 3. Convergence of the extended leap-frogging Newton’s method for
f (x) = (−1 + e−30+7x+x2)(−3 + x)2
n xn f (xn) | xn− α | en+1/en2 η
0 3.50000000000000 213.265 0.500000 2.192307692
1 3.32582570969854 8.05275 0.325826 1.303302839 2 3.17016897270441 0.243364 0.170169 1.602911989 3 3.05596879088136 0.00337242 0.0559688 1.932792228 4 3.00674617976831 4.17384 × 10−6 0.00674618 2.153605047 5 3.00009979932255 1.29304 × 10−11 0.0000997993 2.192864382 6 3.00000002183539 1.35340 × 10−22 2.18354 × 10−8 2.192329399 7 3.00000000000000 1.48461 × 10−44 1.04526 × 10−15 2.192307697 8 3.00000000000000 1.78644 × 10−88 2.39524 × 10−30 2.192307692 9 3.00000000000000 2.58666 × 10−176 1.25776 × 10−59 2.192307692 10 3.00000000000000 5.42299 × 10−356 3.46816 × 10−118 2.192307692 11 3.00000000000000 2.38363 × 10−703 2.63693 × 10−235 2.192307692 12 3.00000000000000 0.0 × 10−1199 0.0 × 10−399
Our analysis has been further confirmed through more test functions that are listed below:
f1(x) = cos x − x
f2(x) = (sin2x − x2+ 1)(cos 2x + 2x2− 3) f3(x) = (sin(πx/2√
2) − x4+ 3)(x2− 2)2(sin(πx/2√
2) − x4+ 3) f4(x) = (x8− 14x4sin(πx/4) − 32)(x2− 4x + 4) log(x − 1)
f5(x) = (3x7− 37x4+ 208) sin (πx/2) log[x − 1]3 f6(x) = (e(x2+7x−30)− 1)(x − 3) sin4πx/3
f7(x) = (e−xsin x+log[1+(x−π)2])(x−π) sin3x(log[x−π+1])2 f8(x) = (x2sin (πx/8) + e(x−2)2− 1 − 2√
2)(x − 2)3sin4(πx/2) Table 4 shows convergence behavior for the above test functions with the multiplicity m, the initial guess x0, the order of convergence p, the least iteration number ν and the asymptotic error constant η.
Let d denote the number of new function or derivative evaluations per iteration. For our proposed method, d is found to be 3. We remark from [10] that both the computational efficiency EFF
EF F = p d =
½ 3
3, if m = 1
23 ≈ 0.6667, if m ≥ 2, and the efficiency index ∗EF F
∗EF F = p1/d = (
313 ≈ 1.44225, if m = 1 213 ≈ 1.25992, if m ≥ 2,
display a good measure of computation compared to the classical new- ton’s method with
EF F = p d =
½ 1, if m = 1
1
2, if m ≥ 2, and
∗EF F = p1/d = (
212 ≈ 1.41421, if m = 1 112 = 1, if m ≥ 2.
Table 4. Convergence of the extended leap-frogging Newton’s method for
f (x) α m x0 en p ν η
f1(x) 0.739085133215161 1 0.490 6.13024 × 10−293 3 5 0.04875502284 f2(x) 1.40449164821534 2 1.290 4.51173 × 10−253 2 8 0.7835709502
f3(x) √
2 3 1.080 0. × 10−249 2 10 5.119146433 f4(x) 2.00000000000000 4 2.190 1.18904 × 10−261 2 8 0.5369302217 f5(x) 2.00000000000000 5 2.270 2.41280 × 10−398 2 9 1.11 f6(x) 3.00000000000001 6 2.790 2.52653 × 10−359 2 9 1.096153846 f7(x) π 7 2.590 1.92369 × 10−587 2 10 3.591527519 f8(x) 2.00000000000000 8 1.590 1.90760 × 10−308 2 8 0.08249684013
Various numerical experiments prove the order of convergence and the asymptotic error constant of the extended leap-frogging Newton’s
method. This proposed development will play a important part in find- ing zeros of the nonlinear equation with highly accuracy. The current investigation will be extended to different methods at a multiple zero.
References
[1] R. G. Bartle, The Elements of Real Analysis, 2nd ed., John Wiley & Sons., New York, 1976.
[2] Ward Cheney and David Kincaid, Numerical Mathematics and Computing, Brooks/Cole Publishing Company, Monterey, California 1980
[3] S. D. Conte and Carl de Boor, Elementary Numerical Analysis, McGraw-Hill Inc., 1980
[4] Qiang Du, Ming Jin, T. Y. Li and Z. Zeng, The Quasi-Laguerre Iteration, Mathematics of Computation, 66 (1997), no. 217, 345-361.
[5] Y. H. Geum, The asymptotic error constant of leap-frogging Newtons method locating a simple real zero, Applied Mathematics of Computation 189 (2007), no. 217, 963-969.
[6] A. Bathi Kasturiarachi, Leap-frogging Newton’s Method, INT. J. MATH.
EDUC. SCI. TECHNOL. 33 (2002), no. 4, 521-527.
[7] L. D. Petkovic, M. S. Petkovic and D. Zivkovic, Hansen-Patrick’s Family Is of Laguerre’s Type, Novi Sad J. Math. 33 (2003), no. 1, 109-115.
[8] Kenneth A. Ross, Elementary Analysis, Springer-Verlag New York Inc., 1980.
[9] J. Stoer and R. Bulirsh, Introduction to Numerical Analysis, 244-313, Springer- Verlag New York Inc., 1980.
[10] J. F. Traub, Iterative Methods for the Solution of Equations, Chelsea Publishing Company, 1982.
[11] Stephen Wolfram, The Mathematica Book, 4th ed., Cambridge University Press, 1999.
*
Department of Pure Mathematics University of Waterloo
Waterloo, Ontario, Canada N2L 3G1 Faculty of Science, University of Malaya 50603, Kuala Lumpur, Malaysia
E-mail: conpana@empal.com